参考文献
- L. Kleinrock著 Queueing Systems vol.1 John Wiley and Sons出版
(下の真っ黒なリンクは、リンク切れではなくこの本の表紙が完全に黒いためです。個人的にはラプラススティルチェス変換の説明を他の文献で理解した以外は基礎からとてもわかりやすい本でした、内容は待ち行列理論の基礎からです。二冊構成になっていてリンクしたのはそのうちの一冊です、二冊めはムズいらしい。基本的にこの記事の記号もこの本にそっていく予定です。)
待ち行列の導入のための定義
記号
一旦読み飛ばして可能な定義、あとで文中で定義
- 時刻tにシステム内にk人いる確率は
- 時刻tにシステム内にk人いる確率はと書くことにする。
- 区間にシステム内の人数がiからjに変化する確率をと書く。
出生死滅過程
システムに入っている人数がk人の時のシステムの状態をと記述することにする。システムが出生死滅過程とは、以下のようなもの。
出生死滅過程(しゅっせいしめつかてい)とは - コトバンク
これはマルコフ過程の特別な場合と解釈できる。つまり、に遷移できるのはかのどちらかからだけのマルコフ過程。この制限があるから数列のようにしてうまく確率の式を解くことができる、と個人的に。そして新しく
と定義。つまり、状態遷移図を書いたときの状態がすぐ”となり”に移る確率がこれ。いまを「の間にシステム内部の人数が二人以上変化する確率が十分小さくなる」ようにとることにする。こうすることで、たとえばとなる確率を無視できるほどに小さい確率であると扱うようにする。そしてこうすることで以下では無視できるほどに小さい確率はオーダー表記ででまとめて一つのこうとして扱うことが可能になった。そして、今状態にあるとしてここから状態が変化する確率は
と記述できる。ここで、上記の式を毎回かくのが面倒なので新しく定義を導入。
- 時刻tにシステム内にk人いる確率はと書くことにする。
- 区間にシステム内の人数がiからjに変化する確率をと書く。こうすることで時刻でシステムにk人いる確率は以下のように記述できる。
上記の式は初めの項から順番に
- 状態kで間には変化なしの確率
- 間に一人増えて状態kになる確率
- 間に一人減って状態kになる確率
- 間に二人以上の増減があったけど無視していいほどに小さい
と解釈できる。この式をさらに正確に書くと
ただし、システム内部の人数はマイナスにはならないことを考慮してシステム内部の人数が0の時のみ、
と記述できる。
この式をで両辺割ることで微分のときに出てくる式を以下のよう
と導出できる。そしての項はとなるようにしているのだから無視していい。そして、ここまできたら図が役に立つので状態遷移図を書く。どのようなものかは検索したら結構でてくる。
出生死滅過程 図 - Google 検索
こうして状態遷移図を記述した。このとき、出生死滅過程では状態に遷移できる状態はとしかないことを考える。すると状態に入ってくる流れと状態から出て行く流れを考えることができて、
と記述できる。そしてに入る流れ-から出る流れを式にすると
[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}\\
}]
となる。この式は
とまったく同じである。だから、は「状態周りに境界線を引いてその境界線をまたいだ遷移」に注目した式であると気づく。そしてこの「境界線をまたぐ」遷移をとらえる考え方は後ほどすごく使う(個人的な感想)。
純粋出生過程(pure birth)
誰も死なない過程、ただ増えるのみ。つまり任意のkについて。これを今までの式に代入して
である。ここで簡単にするためにと言う仮定をする。すると から が導かれる。すると
これは1階線形非同次微分方程式の形なので
よりを得て結局を得た。これを繰り返せばを得る。つまりポアソン分布。
純粋出生過程(pure birth)を通した基本的性質の求め方
単純出生はひとはくるけど誰も出てこないシステムと見て取れる。このシステムの特徴を調べていく。
単位時間あたりの来客数
任意の時間で。
時刻tだけ経過したときにシステム内部にいる客の平均数
を得る。
システムにくる客数の分散
の式を思い出してと先ほどと同じ計算で求められる。