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

(M/M/1モデルのもと)客が到着するスピードが λ\lambda,窓口の処理スピードが μ(>λ)\mu\:(>\lambda) のとき,行列の平均待ち時間は,

ρ1ρ1μ\dfrac{\rho}{1-\rho}\cdot\dfrac{1}{\mu}

ただし,ρ=λμ\rho=\dfrac{\lambda}{\mu}

問題設定

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

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

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

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

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

注意

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

1.微分方程式を立てる

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

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

定理の証明(前半)

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

よって,

p0(t+Δt)p0(t)(1λΔt)+p1(t)μΔtp_0(t+\Delta t)\fallingdotseq p_0(t)(1-\lambda \Delta t)+p_1(t)\mu\Delta t

pn(t+Δt)pn1(t)λΔt+pn(t)(1λΔtμΔt)+pn+1(t)μΔtp_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

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

dp0(t)dt=p0(t)λ+p1(t)μ\dfrac{dp_0(t)}{dt}=-p_0(t)\lambda+p_1(t)\mu

dpn(t)dt=pn1(t)λpn(t)(λ+μ)+pn+1(t)μ\dfrac{dp_n(t)}{dt}=p_{n-1}(t)\lambda-p_n(t)(\lambda+\mu)+p_{n+1}(t)\mu

2.定常分布を求める

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

定理の証明(中盤)

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

よって,p1=λμp0=ρp0p_1=\dfrac{\lambda}{\mu}p_0=\rho p_0

pn+1=pn(1+ρ)pn1ρp_{n+1}=p_n(1+\rho)-p_{n-1}\rho

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

pn=A+Bρnp_n=A+B\rho^{n}

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

以上から pn=(1ρ)ρnp_n=(1-\rho)\rho^n

3.平均待ち時間の導出

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

定理の証明(後半)

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

T=n=1pnnμ=1ρμn=1nρnT=\displaystyle\sum_{n=1}^{\infty}p_n\dfrac{n}{\mu}\\ =\dfrac{1-\rho}{\mu}\displaystyle\sum_{n=1}^{\infty}n\rho^n

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

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

となる。

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

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