待ち行列理論の公式。

１　ホリエモンの動画

　西成活裕先生とホリエモンの対談動画を見た。
・イグ・ノーベル賞受賞の東大教授に聞く、渋滞が起こらないようにする法則とは？【西成活裕×堀江貴文】（YouTube）

西成活裕先生の『東大の先生! 文系の私に超わかりやすく数学を教えてください!』は読んだことがあるけれど、渋滞学についてのお話は新鮮だった。
動画では大雑把な説明だったので、ネットで調べて数学的に確認してみた。

２　リトルの法則

　まず、リトルの法則を確認する。

$L = \lambda W$

・$L$は顧客数の平均。行列なら並んでいる人数の平均である。
・$\lambda$は平均到着時間。その店（行列）に来る人の割合（例：１分間に３人来る）。
来る人と出る人は同じ（均衡状態）と考え、その平均を計算して使用する。
・$W$は顧客１人当たりにかける時間の平均。

例えば、30人（$L = 30$）並んでいて、１分間に３人来る（出る）（$\lambda = 3$）場合、待ち時間は10分（$W = 30 \div 3 = 10$）である。

３　待ち行列理論の公式の導出

　ここから少し難しくなる。M/M/1 待ち行列の理論になる。
上記のリトルの法則では、来る人と出る人が同じだと考えた。
では、来る人と出る人が違う場合、どのように分析できるだろうか。
まず、来る人を$\lambda$（人／時間）、出る人を$\mu$（人／時間）とおく。
そして、来る人（$\lambda$）を出る人（$\mu$）で割り、$\rho = \dfrac{\lambda}{\mu}$とおく。

（1）$\rho \geq 1$のとき

　行列はどんどん長くなるだけである。

（2）$\rho < 1$のとき

　定常過程について考えることができる。このとき、増加と減少がつり合うはずである。
顧客数を$n$人、人数が$n$人である確率を$P_n$とおく。また、時刻の変化を$t$の増減で表現する。

増加と減少がつり合うので次の式が成り立つはずである。

$\lambda \Delta t P_n + \mu \Delta t P_n = \lambda \Delta t P_{n-1} + \mu \Delta t P_{n+1}$

$(\lambda + \mu)P_n = \lambda P_{n-1} + \mu P_{n+1}$

両辺を$\mu$で割ると

$(\rho + 1)P_n = \rho P_{n-1} + P_{n+1}$

また、$P_0, P_1$の関係は

$\lambda \Delta t P_0 = \mu \Delta t P_1$

$\lambda P_0 = \mu P_1$

両辺を$\mu$で割ると

$\rho P_0 = P_1$

４　数列の漸化式を思い出そう

　$(\rho + 1)P_n = \rho P_{n-1} + P_{n+1}$は次のように変形できる。

（1）$P_{n+1} - P_n = \rho(P_n - P_{n-1})$と変形することができる。

よって、$P_n - P_{n-1} = (P_1 - P_0)\rho^{n-1}$

　$= (\rho P_0 - P_0)\rho^{n-1}$

　$= (\rho - 1)\rho^{n-1}P_0$

（2）$P_{n+1} - \rho P_n = P_n - \rho P_{n-1}$と変形することもできる。

よって、$P_n - \rho P_{n-1} = P_1 - \rho P_0$

　$= \rho P_0 - \rho P_0 = 0$

$P_n = \rho P_{n-1}$

（1）より$P_n - P_{n-1} = (\rho - 1)\rho^{n-1}P_0$

$P_n = (\rho - 1)\rho^{n-1}P_0 +  P_{n-1}$

　$= (\rho - 1)\rho^{n-1}P_0 + \dfrac{1}{\rho}P_n$

$P_n - \dfrac{1}{\rho}P_n = (\rho - 1)\rho^{n-1}P_0$

$\dfrac{\rho - 1}{\rho}P_n = (\rho - 1)\rho^{n-1}P_0$

$P_n = (\rho - 1)\rho^{n-1}P_0 \times \dfrac{\rho}{\rho - 1}$

　$= \rho^n P_0$

５　等比数列の和を思い出そう

　$P_0 + P_1 + P_2 + \cdots + P_n + \cdots = 1$である。

$P_0 + \rho P_0 + \rho^2 P_0 + \cdots + \rho^n P_0 + \cdots = 1$

$(1 + \rho + \rho^2 + \cdots + \rho^n + \cdots)P_0 = 1$

$1 + \rho + \rho^2 + \cdots + \rho^n = \dfrac{1 - \rho^{n+1}}{1 - \rho}$である。
$0 < \rho < 1$であるから、$n \to \infty$のとき$\rho^{n+1} \to 0$

よって、$\dfrac{1}{1 - \rho}P_0 = 1$

$P_0 = 1 - \rho$

$P_n = \rho^n (1 - \rho)$

６　最後に$L$を求める

　行列に並んでいる人数の平均を$L$とおくと

$L = 1P_1 + 2P_2 + \cdots + nP_n + \cdots$

　$= (\rho + 2\rho^2 + \cdots + n\rho^n + \cdots)(1 - \rho)$

$\rho + 2\rho^2 + \cdots + n\rho^n = \dfrac{\dfrac{\rho(1 - \rho^n)}{1 - \rho} - n\rho^{n+1}}{1 - \rho}$である。

$0 < \rho < 1$であるから、$n \to \infty$のとき$\rho^n \to 0$、$n\rho^{n+1} \to 0$

よって、$L = \dfrac{\rho}{1 - \rho}$

７　参考記事

・サルでもわかる待ち行列（オブラブ）
・待ち行列の基本形（Ｍ／Ｍ／１）（木暮 仁：「経営と情報」に関する教材と意見）