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

はじめに

基本情報技術者試験の範囲に「待ち行列理論（M/M/1モデル）」というものがあり、窓口利用率 $\rho$ を用いて以下の公式で待ち行列に並んでいる人数を算出するよう記載があります。*1

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

そんな便利な式ですが、この式の導出は真面目に取り組むとかなり難しいです。が、せっかくなので「公式導出について理解した気になる」をゴールにして分かりやすく説明してみました。

所要時間目安：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$ から微小時間 ${\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}$
となりました。長い道のりでした...