2015/10/14

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


(M/M/1モデルのもと)客が到着するスピードが $\lambda$,窓口の処理スピードが $\mu\:(>\lambda)$ のとき,行列の平均待ち時間は, $\dfrac{\rho}{1-\rho}\cdot\dfrac{1}{\mu}$
ただし,$\rho=\dfrac{\lambda}{\mu}$

問題設定

行列に並んでいる人たちを一つの窓口で処理している状況を考えます。客が到着するスピード $\lambda$ と窓口の処理スピード $\mu$(厳密な意味は後述)をもとに,行列の平均待ち時間を表すのが目標です。

平均到着率 $\lambda$,平均サービス率 $\mu$ の意味

客の到着時間間隔が平均 $\dfrac{1}{\lambda}$ のポアソン分布に従うものとします。つまり,新たな客が単位時間当たり平均 $\lambda$ 人のスピードで「ランダムに」来ると考えます。
→ポアソン分布の意味と平均・分散

また,窓口が一人の要望を処理する時間は平均 $\dfrac{1}{\mu}$ の指数分布に従うものとします。窓口は単位時間当たり平均 $\mu$ 人のスピードで行列をさばいていくことになります。
→指数分布の意味と具体例

このようなモデルをM/M/1モデルと言います(MはMarkovianの頭文字,1は窓口の数を表す)。

注意

窓口の処理スピード $\mu$ が客の到着スピード $\lambda$ より遅い場合,行列はどんどん長くなってしまい,待ち時間が発散してしまうので,以下では $\mu > \lambda$,つまり $\rho < 1$ とします。

1.微分方程式を立てる

ここから冒頭の定理を3段階に分けて証明していきます。けっこう大変です。

平均待ち時間を求めるのが目標ですが,まずは時刻 $t$ の時点で行列に並んでいる人数が $n$ 人である確率 $p_n(t)$ について考えます。

定理の証明(前半)

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

よって,
$p_0(t+\Delta t)\simeq p_0(t)(1-\lambda \Delta t)+p_1(t)\mu\Delta t$
$p_n(t+\Delta t)\simeq 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$

2.定常分布を求める

$p_n(t)$ の微分方程式を立てることができましたが,厳密に解くのは非常に難しいです。そこで,十分時間が経過した後の $p_n(t)$,つまり $p_n=\displaystyle\lim_{t\to\infty}p_n(t)$ を求めることにします。

定理の証明(中盤)

十分時間が経過した後,確率 $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$

3.平均待ち時間の導出

行列の長さの分布 $p_n(t)$ が分かったので平均待ち時間 $T$ を計算できます。

定理の証明(後半)

行列の長さが $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$
ここで,右辺を等比×等差の和を求める方法を用いて計算すると,
$T=\dfrac{1-\rho}{\mu}\cdot\dfrac{\rho}{(1-\rho)^2}\\
=\dfrac{\rho}{1-\rho}\cdot\dfrac{1}{\mu}$
となる。

なお,この証明はM/M/1 queue(英語のPDF)を参考にしました。

数学好きの知人と一緒にいるときに街中で行列を見ると待ち行列理論の話題になることがあります。