待ち行列理論（M/M/1モデル）の定理とその証明

微小時間 $\Delta t$ の間に，客が1人増える確率は $\lambda\Delta t$，窓口が1人処理する確率は $\mu\Delta t$ である。 $\Delta t$ が十分小さいとき，これらの確率は十分小さいので行列に2つ以上の変化が起きる確率は無視できる。

よって，

$p_0(t+\Delta t)\fallingdotseq p_0(t)(1-\lambda \Delta t)+p_1(t)\mu\Delta t$

$p_n(t+\Delta t)\fallingdotseq p_{n-1}(t)\lambda \Delta t+p_n(t)(1-\lambda\Delta t-\mu\Delta t)+p_{n+1}(t)\mu\Delta t$

これらの式を少し移項して $\Delta t$ で割って $\Delta t\to 0$ の極限を取ると，

$\dfrac{dp_0(t)}{dt}=-p_0(t)\lambda+p_1(t)\mu$

$\dfrac{dp_n(t)}{dt}=p_{n-1}(t)\lambda-p_n(t)(\lambda+\mu)+p_{n+1}(t)\mu$

十分時間が経過した後，確率 $p_n(t)$ は一定値に収束する（本当はこれも証明しないといけない）ので，さきほどの微分方程式で，$t$ が十分大きいとき左辺は $0$ になる。

よって，$p_1=\dfrac{\lambda}{\mu}p_0=\rho p_0$

$p_{n+1}=p_n(1+\rho)-p_{n-1}\rho$

この下側の式は三項間漸化式であり，特性方程式の解は $1,\rho$ なので，一般解は定数 $A,B$ を用いて以下のように書ける（→三項間漸化式の3通りの解き方）：

$p_n=A+B\rho^{n}$

さらに，確率の性質より $\displaystyle\sum_{n=0}^{\infty}p_n=1$ であることから $A=0$，$B=(1-\rho)$ が分かる。

以上から $p_n=(1-\rho)\rho^n$

行列の長さが $n$ 人のとき，平均待ち時間は $\dfrac{n}{\mu}$ であるので，

$T=\displaystyle\sum_{n=1}^{\infty}p_n\dfrac{n}{\mu}\\ =\dfrac{1-\rho}{\mu}\displaystyle\sum_{n=1}^{\infty}n\rho^n$

ここで，右辺を等差×等比，2乗×等比の和を求める２通りの方法を用いて計算すると，

$T=\dfrac{1-\rho}{\mu}\cdot\dfrac{\rho}{(1-\rho)^2}\\ =\dfrac{\rho}{1-\rho}\cdot\dfrac{1}{\mu}$

となる。