待ち行列理論(その 2) - Red cat の数学よもやま話

$M/M/1$ 型待ち行列

まずは、最も基本的な $M/M/1$ 型待ち行列を解析してみましょう。時刻 $t$ の時点での系の長さが $n$ である確率を $p_n(t)$ で表します。

時刻 $t+\Delta t$ の時点で系の長さが 0 である確率 $p_0(t+\Delta t)$ を求めてみましょう。以下の 4 パターンが考えられます。

時刻 $t$ の時点で系の長さが 0 で、時刻 $(t,t+\Delta t)$ の間に一人も客が到着しない
時刻 $t$ の時点で系の長さが 0 で、時刻 $(t,t+\Delta t)$ の間に一人の客が到着し、時刻 $(t,t+\Delta t)$ の間に一人のサービスが終了する場合
時刻 $t$ の時点で系の長さが 1 で、時刻 $(t,t+\Delta t)$ の間に一人も客が到着せず、時刻 $(t,t+\Delta t)$ の間に一人のサービスが終了する場合
その他の場合

1. の場合の確率は $p_0(t)(1-\lambda\Delta t)+o(\Delta t)$ です。
2. の場合の確率は $p_0(t)(\lambda\Delta t+o(\Delta t))(\mu\Delta t+o(\Delta t))=o(\Delta t)$ です。
3. の場合の確率は $p_1(t)(1-\lambda\Delta t+o(\Delta t))(\mu\Delta t+o(\Delta t))=\mu\Delta t p_1(t)+o(\Delta t)$ です。
4. の場合の確率は $o(\Delta t)$ とみなせます。
以上を全てまとめると
$p_0(t+\Delta t)=(1-\lambda\Delta t)p_0(t)+\mu\Delta t p_1(t)+o(\Delta t)$
$\frac{p_0(t+\Delta t)-p_0(t)}{\Delta t}=-\lambda p_0(t)+\mu p_1(t)+\frac{o(\Delta t)}{\Delta t}$
となり、 $\Delta t\to 0$ として
${p_0}'(t)=-\lambda p_0(t)+\mu p_1(t)$
と微分方程式が立ちます。これは一階線型ですが、未知関数 $p_1(t)$ が含まれているのでこのままでは解けません。

$n\geq 1$ の場合も考えてみましょう。以下の 5 パターンが考えられます。

時刻 $t$ の時点で系の長さが $n-1$ で、時刻 $(t,t+\Delta t)$ の間に一人の客が到着し、時刻 $(t,t+\Delta t)$ の間に一人もサービスが終了しない場合
時刻 $t$ の時点で系の長さが $n$ で、時刻 $(t,t+\Delta t)$ の間に一人も客が到着せず、時刻 $(t,t+\Delta t)$ の間に一人もサービスが終了しない場合
時刻 $t$ の時点で系の長さが $n$ で、時刻 $(t,t+\Delta t)$ の間に一人の客が到着し、時刻 $(t,t+\Delta t)$ の間に一人のサービスが終了する場合
時刻 $t$ の時点で系の長さが $n+1$ で、時刻 $(t,t+\Delta t)$ の間に一人も客が到着せず、時刻 $(t,t+\Delta t)$ の間に一人のサービスが終了する場合
その他の場合

1. の場合の確率は $p_{n-1}(t)(\lambda\Delta t+o(\Delta t))(1-\mu\Delta t+o(\Delta t))=\lambda\Delta t p_{n-1}(t)+o(\Delta t)$ です。
2. の場合の確率は $p_n(t)(1-\lambda\Delta t+o(\Delta t))(1-\mu\Delta t+o(\Delta t))=p_n(t)-(\lambda+\mu)\Delta t p_n(t)+o(\Delta t)$ です。
3. の場合の確率は $p_n(t)(\lambda\Delta t+o(\Delta t))(\mu\Delta t+o(\Delta t))=o(\Delta t)$ です。
4. の場合の確率は $p_{n+1}(t)(1-\lambda\Delta t+o(\Delta t))(\mu\Delta t+o(\Delta t))=\mu\Delta t p_{n+1}(t)+o(\Delta t)$ です。
5. の場合の確率は $o(\Delta t)$ とみなせます。
以上をまとめると
$p_n(t+\Delta t)=\lambda\Delta t p_{n-1}(t)+p_n(t)-(\lambda+\mu)\Delta t p_n(t)+\mu\Delta t p_{n+1}(t)+o(\Delta t)$
$\frac{p_n(t+\Delta t)-p_n(t)}{\Delta t}=\lambda p_{n-1}(t)-(\lambda+\mu)p_n(t)+\mu p_{n+1}(t)+\frac{o(\Delta t)}{\Delta t}$
となり、 $\Delta t\to 0$ として
${p_n}'(t)=\lambda p_{n-1}(t)-(\lambda+\mu)p_n(t)+\mu p_{n+1}(t)$
と微分方程式が立ちます。

まとめると
${p_0}'(t)=-\lambda p_0(t)+\mu p_1(t)$
${p_n}'(t)=\lambda p_{n-1}(t)-(\lambda+\mu)p_n(t)+\mu p_{n+1}(t) (n\geq 1)$
となり、無限個の微分方程式系が出来上がります。これが簡単に解ければ良いのですが、実はこの微分方程式系を解くのは容易ではありません。そこで、 $\rho=\frac{\lambda}{\mu} \lt 1$ のとき、待ち行列は $t\to\infty$ で平衡状態に落ち着くはずであろう*1、と考えて、漸近的な挙動を調べることになります。(続く)

*1:実際そうなのですが、それを証明するのは非常に困難です。