###### tags: `プログラミング授業`

# 待ち行列テスト対策
諸注意：
　ここに記したのはざっくりとした理論だけです（確率分布の導出まで）。期待値の導出、プログラミング言語による記述、シミュレーション等の内容は一切載っていません.

## 目次
* ポアソン過程(ポアソン到着)
* 出生死滅過程
* 行列の様子を数式で表そう
* 定常状態の分析（定常状態から確率分布を求める）
* 感想と反省
## ◆ ポアソン過程(ポアソン到着)

### タピオカ屋に客がやってくる！

１時間という時間を非常に小さい時間間隔Δt（0.1秒）で分割してみます(Δt=0.1/3600 [時間])。すると、１時間は36,000この微小時間に分割される。ここで、客が到着する頻度を、１時間あたり平均λ回であるとする。このとき、λはあくまで平均の値でありどのタイミングで客が到着するかはわからないことに注意。そして、分割された36,000個の時点それぞれについて確率 λ・Δtでランダムに客が到着すると考える。
　少しわかりずらいので例を考える。λ=10(１時間に平均１０人到着)だとすると、λ・Δt = 1/3600である。各Δtあたりの到着確率はめちゃくちゃ低いけど１時間あれば10人くるんだよ。確率1/3600のくじだって36,000回引けば10回あたりがくるでしょ。１時間経つということはくじを36,000回引いてるのと同じこと(多分)。

一応ポアソン過程の性質をちゃんと書いておく。

定常性 : 事象が起こる確率はどの時間帯でも同一
無記憶性 : 事象の起きる確率は、それ以前に起こった事象の回数や起こり方には無関係
希少性 ： 微小時間∆の間に事象が2回以上起こる確率は無視できるほど小さい。

とりあえず超ランダムに客が来ると思っておけばいいかな。

## ◆ 出生死滅過程

### おおおお客様が死滅だと！！？

※以下、客がタピオカを購入し終わって去ることを死滅と表現します。(サービス完了も同じ意味)

μを1時間に何人サービスを完了するか（平均サービス率）の変数とすると、一人当たりにかかるサービス所要時間は1/μとなる。つまり、単位時間当たり平均λ(人)の客が到着、平均 μ(人) 分のサービスが完了。

ここで、ρ=λ/μとすると…　　※トラフィック密度と言われているらしい

ρ ≥ 1 : サービス処理が客の到着に追い付かない
=>待ち行列が発散

ρ < 1 : 待ち行列は発散せず，十分な時間が経過
=>系内の客数の分布は一定(定常状態)

　タピオカを購入終わった客は去っていくので、客の到着だけでは行列の長さを考えることはできない。そこで、ポアソン過程では、Δtの微小時間の間にλ・Δtの確率で新しい客がやってくるが、確率μ・Δtで列の先頭にいる人が死滅する(買い終わっていなくなる)という確率過程（出生死滅過程）を考える必要がある。

客の到着と死滅が同時に起こる確率は積事象で2次の項になり、そのような事象の発生は無視できます。


## ◆ 行列の様子を数式で表そう

時刻tに行列がn人であるを確率Pn(t)とする。微小時間Δt経過後に行列がn人の確率は？？
時刻t+Δtでn人になるには以下の3パターンある。

※系内数：サービス中の客の数＋待ち行列中の客の数
##### 1. 時刻tに系内に客はn-1(人)で、その後∆tの間に、1人客が到着、客の死滅はなし

##### 2. 時刻tに系内に客はn+1(人)で、その後 ∆tの間に客が1人死滅、客の到着はなし

##### 3.時刻tに系内に客はn(人)でその後 ∆tの間に客の到着も客の死滅もなし

つまり、微小時間Δt経過後に行列がn人の確率は以下のように表される。(n≥０ということに注意)


⇔

ここで、Δt→０を考えると

## ◆ 定常状態の分析（定常状態から確率分布を求める）

が成り立つとすると(状態確率が時間変化しない一定の値に収束する。状態間の推移があっても状態確率は変わらないということ)、時間微分が０になるので以下のように表せる。　


（λ<μと仮定しています）

※エルゴード性を満たせば定常分布を持つモデルと言えるらしい(エルゴード性の話は難しくてよく分からなかったからカット。)

### ・漸化式を解こう！

まず、上の式を以下のように変形する.

n=1から順番に見ていこう。


つまり、一般に以下の式が成り立つと考えられる。


ここで、であるから

　
※無限級数の部分和を考える.　0≤ρ<1と仮定しているのでの極限値が０に収束します.


となり、定常状態における確率分布を求めることができた！

#### 感想と反省
確率過程の話をせずにいきなりポアソン過程に入っているにも関わらず、説明が雑。
今回はマルコフ過程ということもあって数理的に考えたが、プログラミングの授業としては確率モデルの振る舞いを数値シミュレーションする方が面白いと思うので次回はそれをやろう。あ、あと各種期待値の導出も忘れずに。M/M/cはやらない(そんなに待ち行列好きじゃない。まあ自分が行列に並ぶという行為が嫌いなだけなんだけどね)。

「そこらへんは割とすぐできるのであとでまた書きます」というのにイラっとした人は多分、M/M/1における確率分布はシンプルな式で記述できるのでプログラムはすぐにかける、原理的に確率分布がわかっていれば大体の期待値は求めることができるという、この二点を示してあげれば納得してくれるだろう。
　ただ、待ち行列理論は本来もっと難しい話らしいので、結論としては「私は待ち行列理論をよくわかっていない」ということになるだろう。したがって冒頭でイラっときた人は正解なのだ。

##### 追伸：
プログラミングの授業のテスト対策なのに一行もコード書いてなくて草