情報システム理論と待ち行列理論1：メモ

参考文献

L. Kleinrock著 Queueing Systems vol.1 John Wiley and Sons出版

(下の真っ黒なリンクは、リンク切れではなくこの本の表紙が完全に黒いためです。個人的にはラプラススティルチェス変換の説明を他の文献で理解した以外は基礎からとてもわかりやすい本でした、内容は待ち行列理論の基礎からです。二冊構成になっていてリンクしたのはそのうちの一冊です、二冊めはムズいらしい。基本的にこの記事の記号もこの本にそっていく予定です。)

待ち行列の導入のための定義

記号

${ P(e) := eが真になる確率\\ A(t) := P(到着時間間隔 \leq t) \\ B(T) := P(サービス時間 \leq x) \\ C_k := k番目の客(customer)\\ N(t) := 時刻tにシステム内部に存在する客の数\\ V(t) := 時刻tにシステム内部にいる客へのすべてのサービスが終了するのに必要な時間\\ \tau_k := k番目の客が到着する時刻\\ t_k := \tau_k - \tau_{k-1} つまりk-1番めの客が来てから次の客がくるまでの時間\\ x_k := C_kに必要なサービス時間\\ \bar{p} := 確率変数pの平均\\ \alpha(t) := 時刻tまでにシステムに到着した客の数\\ \delta(t) := 時刻tまでにシステムから出て行く客の数\\ つまり、N(t) = \alpha(t) - \delta(t)\\ \lambda := そのシステムの単位時間あたりの来客数\\ T:= 一人の客がシステムで消費する平均時間長\\ \bar{N} := システム内部の平均客数\\ そして、\bar{N} = \lambda \bar{T} (リトルの公式、リトルの法則。後ほど登場)\\ }$

一旦読み飛ばして可能な定義、あとで文中で定義

時刻tにシステム内にk人いる確率は ${ P_k(t) := P(X(t) = k) }$
時刻tにシステム内にk人いる確率は ${ P_k(t) := P(X(t) = k) }$ と書くことにする。
${ (t,t+\Delta t) }$ 区間にシステム内の人数がiからjに変化する確率を ${ p_{i,j}(\Delta t) }$ と書く。

確率過程(stochastic process)

確率過程とは - OR事典 Weblio辞書

マルコフ過程

確率過程のうちで
${ P[X_{n+1} = x_{n+1} | X_n = x_n , \dots , X_0 = x_0 ] = P[X_{n+1} = x_{n+1} | x_n = x_n] }$
となるもの。

離散的マルコフ過程を前提とした記号

いきなり状態といった言葉がでてきますが状態遷移図の状態です。
${ p_{ij} = P(X_n = j| X_{n-1} = i)\\ p_{ij}^k = P(X_n = j| X_{n-k} = i) \\ = \sum_{m} p_{mk}^1 p_{im}^{k-1}\\ f_i^n = 状態iから出発してはじめて再び状態iになるのにnステップかかる確率\\ f_i = \sum_{k=0}^{\infty} f_i^k = P( 再び状態iになる確率 )\\ M_i = \sum_{k=0}^{\infty} k f_i^k = 再び状態iになるのに必要なステップ数\\ \pai_k^n = P(X_n = k)\\ }$

出生死滅過程

　システムに入っている人数がk人の時のシステムの状態を ${ E_k }$ と記述することにする。システムが出生死滅過程とは、以下のようなもの。
<a href="https://kotobank.jp/word/%E5%87%BA%E7%94%9F%E6%AD%BB%E6%BB%85%E9%81%8E%E7%A8%8B-1173983">出生死滅過程(しゅっせいしめつかてい)とは - コトバンク</a>
出生死滅過程(しゅっせいしめつかてい)とは - コトバンク

　これはマルコフ過程の特別な場合と解釈できる。つまり、 ${ E_k }$ に遷移できるのは ${ E_{k-1} }$ か ${ E_{k+1} }$ のどちらかからだけのマルコフ過程。この制限があるから数列のようにしてうまく確率の式を解くことができる、と個人的に。そして新しく
${ \lambda_k = 状態 E_k から E_{k+1} になる確率\\ \mu_k = 状態 E_k から E_{k-1} になる確率\\ }$
と定義。つまり、状態遷移図を書いたときの状態がすぐ”となり”に移る確率がこれ。いま ${ \Delta t }$ を「 ${ \Delta t }$ の間にシステム内部の人数が二人以上変化する確率が十分小さくなる」ようにとることにする。こうすることで、たとえば ${ E_k から E_{k+2}}$ となる確率を無視できるほどに小さい確率であると扱うようにする。そしてこうすることで以下では無視できるほどに小さい確率はオーダー表記で ${ o(\Delta t) }$ でまとめて一つのこうとして扱うことが可能になった。そして、今状態 ${ E_k }$ にあるとしてここから状態が変化する確率は

${ P[(t,t+\Delta t)の区間で一人システムに来客 | システム内部にはk人存在] \\ = \lambda_k\Delta t + o(\Delta t)\\ P[(t,t+\Delta t)の区間で一人システムから退去 | システム内部にはk人存在] \\ = \mu_k\Delta t + o(\Delta t)\\ P[(t,t+\Delta t)の区間で一人もシステムに来客しない | システム内部にはk人存在] \\ = 1 - \lambda_k\Delta t + o(\Delta t)\\ P[(t,t+\Delta t)の区間で一人システムに来客 | システム内部にはk人存在] \\ = 1 - \mu_k\Delta t + o(\Delta t)\\ }$

と記述できる。ここで、上記の式を毎回かくのが面倒なので新しく定義を導入。

時刻tにシステム内にk人いる確率は ${ P_k(t) := P(X(t) = k) }$ と書くことにする。
${ (t,t+\Delta t) }$ 区間にシステム内の人数がiからjに変化する確率を ${ p_{i,j}(\Delta t) }$ と書く。こうすることで時刻 ${( t+\Delta t )}$ でシステムにk人いる確率 ${ P_k(t + \Delta t) }$ は以下のように記述できる。

${ P_k(t+\Delta t)\\ = P_k(t)p_{k,k}(\Delta t) + P_{k-1}(t)p_{k-1,k}(\Delta t) + P_{k+1}(t)p_{k+1,k}(\Delta t) + o(\Delta t) }$

上記の式は初めの項から順番に

状態kで ${\Delta t}$ 間には変化なしの確率
${\Delta t}$ 間に一人増えて状態kになる確率
${\Delta t}$ 間に一人減って状態kになる確率
${\Delta t}$ 間に二人以上の増減があったけど無視していいほどに小さい

と解釈できる。この式をさらに正確に書くと
${ \\ P_k(t+\Delta t)\\ = P_k(t)(1 - \lambda_k\Delta t + o(\Delta t))(1 - \mu_k\Delta t + o(\Delta t)) \\ + P_{k-1}(t)( \lambda_k \Delta t + o(\Delta t) \\ + P_{k+1} (t)(\mu_k \Delta t + o(\Delta t))\\ + o(\Delta t)\\ \\ = P_k(t) - (\lambda_k + \mu_k)\Delta t P_k(t) + \lambda_{k-1}\Delta t P_{k-1}(t) \\ + \mu_{k+1}\Delta t P_{k+1}(t) + o(\Delta t)\\\\ }$
ただし、システム内部の人数はマイナスにはならないことを考慮してシステム内部の人数が０の時のみ、
${ \\\\ P_0(t+\Delta t)\\ = P_0(t)[1 - \lambda_k\Delta t + o(\Delta t)]\\ + P_{k+1}(t)[\mu_k\Delta t + o(\Delta t)] \\ + o(\Delta t)\\ \\ = P_0(t) - (\lambda_0)\Delta t P_0(t) + \mu_{1}\Delta t P_{1}(t) + o(\Delta t) \\\\ }$
と記述できる。
この式を ${ \Delta t }$ で両辺割ることで微分のときに出てくる式を以下のよう

${ \frac{P_k(t + \Delta t) - P_k(t)}{\Delta t} = -(\lambda_k + \mu_k)P_k(t) + \lambda_{k-1}P_{k-1}(t) + \mu_{k+1}P_{k+1}(t) + \frac{o(\Delta t)}{\Delta t}\\ \frac{P_0(t + \Delta t) - P_0(t)}{\Delta t} = -\lambda_0 P_0(t) + \mu_{1}P_{1}(t) + \frac{o(\Delta t)}{\Delta t}\\ \\ }$
と導出できる。そして ${\frac{o(\Delta t)}{\Delta t}}$ の項は ${\lim_{x \to \infty} \frac{o(\Delta t)}{\Delta t} = 0}$ となるようにしているのだから無視していい。そして、ここまできたら図が役に立つので状態遷移図を書く。どのようなものかは検索したら結構でてくる。
出生死滅過程図 - Google 検索

こうして状態遷移図を記述した。このとき、出生死滅過程では状態 ${ E_k }$ に遷移できる状態は ${ E_{k-1} }$ と ${ E_{k+1} }$ しかないことを考える。すると状態 ${ E_k }$ に入ってくる流れと状態 ${ E_k }$ から出て行く流れを考えることができて、

${ 時刻tでE_k に入る流れ = \lambda_{k-1}P_{k-1}(t) + \mu_{k+1}P_{k+1}(t) \\ 時刻tでE_k を出る流れ = (\lambda_{k} + \mu_{k})P_{k}(t) \\ }$

と記述できる。そして ${ 状態E_k }$ に入る流れ- ${ 状態E_k }$ から出る流れを式にすると

[tex:{

(\lambda_k + \mu_k)P_k(t) + \lambda_{k-1}P_{k-1}(t) + \mu_{k+1}P_{k+1}(t) + \frac{o(\Delta t)}{\Delta t}\\

}]

となる。この式は

とまったく同じである。だから、 ${ \frac{P_k(t + \Delta t) - P_k(t)}{\Delta t} }$ は「状態 ${E_k}$ 周りに境界線を引いてその境界線をまたいだ遷移」に注目した式であると気づく。そしてこの「境界線をまたぐ」遷移をとらえる考え方は後ほどすごく使う（個人的な感想）。

純粋出生過程（pure birth）

　誰も死なない過程、ただ増えるのみ。つまり任意のkについて ${ \mu_k = 0 }$ 。これを今までの式に代入して

${ \frac{d P_k(t)}{dt} = - \lambda_{k}P_k(t) + \lambda_{k-1}P_{k-1}(t) \\ \frac{d P_0(t)}{dt} = - \lambda_{0}P_{0}(t) \\ }$

である。ここで簡単にするために ${ \lambda_0 = \dots = \lambda_k = \dots = \lambda }$ と言う仮定をする。すると ${ \frac{d P_0(t)}{dt} = - \lambda_{0}P_{0}(t) }$ から ${ P_0(t) = e^{-\lambda t} }$ が導かれる。すると

${ \frac{d P_1(t)}{dt} = - \lambda P_1(t) + \lambda e^{-\lambda t} \\ }$

これは1階線形非同次微分方程式の形なので

${ \frac{d P_1(t)}{dt} + \lambda P_1(t) = 0 \\ }$

より ${ P_1(t) = -Ce^{-\lambda t} }$ を得て結局 ${ P_1(t) = \lambda e^{-\lambda t} }$ を得た。これを繰り返せば ${ P_k(t) = \frac{(\lambda t)^k}{k!}e^{-\lambda t} }$ を得る。つまりポアソン分布。

純粋出生過程（pure birth）を通した基本的性質の求め方

単純出生はひとはくるけど誰も出てこないシステムと見て取れる。このシステムの特徴を調べていく。

単位時間あたりの来客数

任意の時間で ${ \lambda }$ 。

時刻tだけ経過したときにシステム内部にいる客の平均数

${ E(k) \\ = \sum_{k=0}^{\infty} k P_k(t) \\ = \sum_{k=0}^\infty k \frac{(\lambda t)^k}{k!}e^{-\lambda t} \\ = \sum_{k=0}^\infty (\lambda t)\frac{(\lambda t)^{(k-1)}}{(k-1)!}e^{-\lambda t} \\ = e^{-\lambda t}(\lambda t) \sum_{k=0}^\infty k \frac{(\lambda t)^k}{k!}e^{-\lambda t} \\ = e^{-\lambda t}(\lambda t)e^{\lambda t} \\ = \lambda t }$
を得る。