【待ち行列理論】待ち人数の公式を導出する

はじめに

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

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

ここで $\rho=\cfrac{\lambda}{\mu}$ で $\lambda$ は平均到着率で $\mu$ は平均サービス量です。*1

この式の導出、真面目に取り組むとかなり難しいのですが、せっかくなので「公式導出について理解した気になる」をゴールにして分かりやすく説明してみました。
とはいっても数式はかなり出てくるので心が折れれば離脱してください。

所要時間目安：10分

以下は道中で利用する公式や前提です。

無限級数の公式

$\displaystyle\sum_{k=0}^{\infty}ar^k=\cfrac{a}{1-r}$
$\displaystyle\sum_{k=1}^{\infty}kr^k=\cfrac{r}{(1-r)^2}$

上記公式はrの絶対値が1未満の時に成り立ちます。理系の方は高校数学で見たはずです。

微分方程式

$\cfrac{f(t+{\Delta}t)-f(t)}{{\Delta}t}=\cfrac{df(t)}{dt}$
かつ定常状態であれば $\cfrac{df(t)}{dt}=0$

要は関数fに時間変化がなくなれば、時間で微分した値は $0$ になります。

列に並んでいる人の公式を算出する

イメージ

最終的に算出したいゴールをまずはイメージします。
列に並んでいる人数の期待値が知りたければ、列に並んでいる人数のそれぞれの確率が分かれば算出できます。
例えば、窓口に０人並んでいる確率が0.2、窓口に１人並んでいる確率が0.5、窓口に２人並んでいる確率が0.3、窓口に３人以上並んでいる確率は0だとすれば

> 1*0.5+2*0.3
[1] 1.1

つまり1.1人並んでいると算出できました。

これを一般化すれば窓口に $k$ 人並んでいる確率が $p_{k}$ とすれば列に並ぶ人の数は
$\displaystyle\sum_{k=1}^{\infty}kp_{k}$
と書けます。

要は、窓口に $k$ 人並んでいる確率 $p_{k}$ を求めることが肝のようです。

窓口に0人並んでいる確率を状態遷移で考える

まずは話を簡単にするべく、窓口に0人並んでいる確率 $p_{0}$ に関する式を求めてみます。
ある時刻 $t$ に窓口に0人並んでいて、そこから微小時間 ${\Delta}t$ 後も0人並んでいる状態を考えてみます。
考えられるパターンは以下の2種類です。

時刻 $t$ に0人並んでいて微小時間の間に客が到着しない
時刻 $t$ に1人並んでいて微小時間の間に客がサービスを受けていなくなる

これを数式で表すと以下になります。
$p_{0}(t+{\Delta}t) = p_{0}(t)(1-{\lambda}{\Delta}t)+p_{1}(t){\mu}{\Delta}t$

平均到着率 $\lambda$ や平均サービス量 $\mu$ に時間をかけることで確率として表現しています。
ちなみに時刻 $t$ に2人並んでいて微小時間の間に2人ともサービスを受けていなくなる確率は、微小時間を限りなく微小にすることで無視できるので考慮に入れていません。

上の状態方程式を整理すると
$p_{0}(t+{\Delta}t)-p_{0}(t)= -p_{0}(t){\lambda}{\Delta}t+p_{1}(t){\mu}{\Delta}t$
↓
$\cfrac{p_{0}(t+{\Delta}t)-p_{0}(t)}{{\Delta}t}= -p_{0}(t){\lambda}+p_{1}(t){\mu}$
↓
$\cfrac{dp_{0}(t)}{dt}=-p_{0}(t){\lambda}+p_{1}(t){\mu}$

ここで冒頭に記載した前提である
定常状態であれば $\cfrac{df(t)}{dt}=0$ という部分を当てはめます。
この定常性は自明ではありませんが、サービス量と到着率が一定であればそれぞれの確率は時間に寄らず一定になりそうな感覚をイメージしてください。

そうすると上の式は
$0=-p_{0}(t){\lambda}+p_{1}(t){\mu}$
↓
$p_{1}(t)=p_{0}(t)\cfrac{{\lambda}}{\mu}$

となりました。
次に窓口に $n$ 人並んでいる時の微小時間後バージョンを考えます。

窓口にn人並んでいる確率を状態遷移で考える

考えられるパターンは以下の3種類です。

時刻 $t$ に $n-1$ 人並んでいて微小時間の間に客が到着するしない
時刻 $t$ に $n$ 人並んでいて微小時間の間に客は到着しないしサービスも受けない
時刻 $t$ に $n+1$ 人並んでいて微小時間の間に客がサービスを受けていなくなる

それらを上と同じように式にして変形すると以下のようになります。
$\cfrac{dp_{n}(t)}{dt}=p_{n-1}(t){\lambda}-p_{n}(t)({\lambda}+{\mu})+p_{n+1}(t){\mu}$
これもまた定常状態を仮定すれば左辺は0になります。
$0=p_{n-1}(t){\lambda}-p_{n}(t)({\lambda}+{\mu})+p_{n+1}(t){\mu}$
上の式は任意のnで成り立つので、例えば $n=1$ を代入してみます。。

$0=p_{0}(t){\lambda}-p_{1}(t)({\lambda}+{\mu})+p_{2}(t){\mu}$

ここで先ほど窓口0人の状態式で導出した $p_{1}(t)=p_{0}(t)\cfrac{{\lambda}}{\mu}$ が使えます。これを代入すると
$0=p_{0}(t){\lambda}-\cfrac{p_{0}(t){\lambda}}{{\mu}}({\lambda}+{\mu})+p_{2}(t){\mu}$
↓
$p_{2}(t)=p_{0}(t)(\cfrac{{\lambda}}{\mu})^{2}$

新たな関係式が出てきました。

次は $n=2$ を代入してみると...？

なんとこれを繰り返えして行けば、窓口にn人並んでいる確率は以下の式で表現できます。
$p_{n}(t)=p_{0}(t)(\cfrac{{\lambda}}{\mu})^{n}$

前半部分で述べた「窓口に $k$ 人並んでいる確率 $p_{k}$ を求めることができれば並んでいる人数は求められる」のゴールが近づいてきました。あとは $p_{0}(t)$ が算出できればゴールは目の前です。

確率の全体は1

窓口に0人並んでいる確率と窓口に1人並んでいる確率と... 窓口に∞人並んでいる確率の合計は100%である1になります。
この情報を利用します。

数式で表現すれば以下となります。
$\displaystyle\sum_{k=0}^{\infty}p_{0}(t)(\cfrac{{\lambda}}{\mu})^{k}=1$ が成り立ちます。

ここで冒頭の前提に書いた $\displaystyle\sum_{k=0}^{\infty}ar^k=\cfrac{a}{1-r}$ を利用すると

$1=\cfrac{p_{0}(t)}{1-\rho}$
$p_{0}(t)=1-\rho$

$\rho=\cfrac{\lambda}{\mu}$ を利用して式をスッキリさせました。

$p_{n}(t)=p_{0}(t)(\cfrac{{\lambda}}{\mu})^{n}$ が
$p_{n}(t)=(1-\rho){\rho}^n$ になりました。最後は期待値を求めます。

いよいよゴールです。

列に並んでいる人数の期待値

$k$ 人並んでいる確率が $p_{k}(t)=(1-\rho){\rho}^k$ なので
$\displaystyle\sum_{k=1}^{\infty}k(1-\rho){\rho}^k$ が求める値です。

$\cfrac{\rho}{1-\rho}$ になるのでしょうか。

ここでも無限級数の公式 $\displaystyle\sum_{k=1}^{\infty}kr^k=\cfrac{r}{(1-r)^2}$ を利用すると
$\displaystyle\sum_{k=1}^{\infty}k(1-\rho){\rho}^k=\cfrac{\rho(1-\rho)}{(1-\rho)^2}=\cfrac{\rho}{1-\rho}$
となりました。長い道のりでした...

終わりに

今回はかなりざっくりした説明で、ポアソン分布や指数分布といった本来の議論の前提をすっ飛ばしてエッセンスだけを紹介しました。のに、この長さです。

ここの整理はずっとしたかったのですが数式の記述が面倒でずっと避けていました。読み返してみても少し行間があるので補足したい思いもありつつ気が向いたら加筆修正します。

ITパスポートや基本情報技術者の参考書で公式だけを覚えておくようにして切り上げるのも納得のボリュームの本内容ですが、あの公式はどっから来ているのだろうか？という素朴な疑問を持たれた方の理解の一助になれば幸いです。

*1:到着率よりもサービス量が小さければ行列の長さは無限大に発散するのでは窓口利用率は1よりも小さい値

(O+P)ut

アウトプット