待ち行列理論の公式。
１ ホリエモンの動画
西成活裕先生とホリエモンの対談動画を見た。・イグ・ノーベル賞受賞の東大教授に聞く、渋滞が起こらないようにする法則とは？【西成活裕×堀江貴文】（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$の関係は
-P(1).jpg)
$\lambda \Delta t P_0 = \mu \Delta t P_1$
$\lambda P_0 = \mu P_1$
両辺を$\mu$で割ると
$\rho P_0 = P_1$
$= (\rho P_0 - P_0)\rho^{n-1}$
$= (\rho - 1)\rho^{n-1}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 + \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 = 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}$である。
両辺を$\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}$である。
よって、$L = \dfrac{\rho}{1 - \rho}$
７ 参考記事
・サルでもわかる待ち行列（オブラブ）・待ち行列の基本形（Ｍ／Ｍ／１）（木暮 仁：「経営と情報」に関する教材と意見）