【待ち行列理論】n人が並んでいる確率の計算

はじめに

基本情報技術者試験の冊子を眺めると待ち行列理論（M/M/1モデル）として窓口利用率 $\rho$ を用いて以下の公式で待ち行列に並んでいる人数を算出するよう述べています。

$\cfrac{\rho}{1-\rho}$

本公式は別記事にて導出を行いました。

この記事の結論としては
窓口に既に $k$ 人並んでいる確率が $p_{k}=(1-\rho){\rho}^k$ なので
並んでいる人の数の期待値が $\displaystyle\sum_{k=1}^{\infty}k(1-\rho){\rho}^k$ となり、
無限級数の公式である $\displaystyle\sum_{k=1}^{\infty}kr^k=\cfrac{r}{(1-r)^2}$ を利用して
$\cfrac{\rho}{1-\rho}$ を導出しています。

本記事ではそれぞれの確率の計算を実際に行い、どのように値が収束しているのかを確認します。

値を代入していく

サンプルの値として今回は平均到着率 $\lambda$ を4、平均サービス量 $\mu$ を5とします。
イメージとしては窓口に来る人の時間間隔が平均５分で、手続きにかかる時間の平均が４分であることと同義です。

窓口利用率は以下式なので
$\rho=\cfrac{\lambda}{\mu}$

$\rho$ の具体的な値は0.8となります。

> 4 / 5
[1] 0.8

また、並んでいる人数は冒頭の公式にあてはめて4人となります。

> 0.8/(1-0.8)
[1] 4

よって列に並ぶ平均時間は 4人×4分/人で 16分ですね。

0人が並んでいる確率

さっそく「0人」が並んでいる確率を算出は冒頭の式を利用して $p_{0}=1-\rho$

> 1-0.8
[1] 0.2

0.2となります。

ここからの知見は、並ばずにサービスを受けれる確率が0.2、つまり20%である点です。

逆に誰かが並んでいる確率は80%、この値は窓口利用率と等しいので、窓口利用率というのは窓口ですぐにサービスを受けれず並ぶ必要がある確率とも言えます。

N人が並んでいる確率

以下の式を見れば分かりますがNが大きくなればなるほど確率は単調に下がります。
$p_{k}=(1-\rho){\rho}^k$

0人が並んでいる確率0.2の次から10人が並んでいる確率までをどんどん計算していくと以下のようになります。

N	確率
0	0.2
1	0.16
2	0.128
3	0.1024
4	0.08192
5	0.065536
6	0.0524288
7	0.04194304
8	0.033554432
9	0.026843546
10	0.021474836

Excelで可視化すると以下です。
f:id:mtiit:20190829180949p:plain

N人が並んでいる期待値

次は確率ではなく期待値です。
人数に対して確率は単調減少ですが、期待値ではどうでしょうか。
以下が、同じく0人から10人の期待値です。

N	確率	期待値
0	0.2	0
1	0.16	0.16
2	0.128	0.256
3	0.1024	0.3072
4	0.08192	0.32768
5	0.065536	0.32768
6	0.0524288	0.3145728
7	0.04194304	0.29360128
8	0.033554432	0.26843545
9	0.026843546	0.24159191
10	0.021474836	0.214748365

可視化した結果は以下です。
f:id:mtiit:20190829181651p:plain
凸型の曲線を描きます。

N人が並んでいる期待値の累積和

累積和はNを極限まで大きくすると冒頭の公式にあてはめて「4」になりました。
実際に累積和を0～10で取りました。

N	確率	期待値	期待値の累積和
0	0.2	0	0
1	0.16	0.16	0.16
2	0.128	0.256	0.416
3	0.1024	0.3072	0.7232
4	0.08192	0.32768	1.05088
5	0.065536	0.32768	1.37856
6	0.0524288	0.3145728	1.6931328
7	0.04194304	0.29360128	1.98673408
8	0.033554432	0.26843545	2.255169536
9	0.026843546	0.24159191	2.496761446
10	0.021474836	0.214748365	2.711509811