Aritalab:Lecture/NetworkBiology/Markov Chains/Queue

待ち行列

窓口に並ぶ客の人数 i をモデルしよう。 単位時間において以下の事象が発生する。

• もし i < n だったら、確率 α で客が一人増える。
• もし i > 0 なら、確率 β で先頭から順に客は減る。
• それ以外の場合、客の数は変化しない。

時刻 t における行列の長さを考えると、有限のマルコフ連鎖になっている。遷移確率は以下のようになる。

$\begin{align} p_{i, i+1} &= \alpha \quad \mbox{if} \quad i < n; \\ p_{i, i-1} &= \beta \quad \mbox{if} \quad i > 0; \\ p_{i, i} &= \begin{cases} 1 - \alpha & \mbox{if } \quad i=0,\\ 1 - \alpha - \beta & \mbox{if } \quad 1 \leq i \leq n - 1, \\ 1 - \beta & \mbox{if } \quad i = n \end{cases} \end{align}$

マルコフ連鎖は既約、有限、非周期的なので唯一の定常分布 $\bar \pi$ を持つ。 満たすべき式は

$\begin{align} \pi_0 &= (1 - \alpha) \pi_0 + \beta \pi_1 \\ \pi_i &= \alpha \pi_{i-1} + (1 -\alpha -\beta) \pi_i + \beta \pi_{i+1} \\ \pi_n &= \alpha \pi_{n-1} + (1-\beta)\pi_n \end{align}$

これを解くと $\pi_i = \pi_0 \Big( \frac{\alpha}{\beta} \Big)^i$。 更に $\sum^n_{i=0} \pi_i = \pi_0 \sum^n_{i=0} \Big( \frac{\alpha}{\beta} \Big)^i = 1$より

$\pi_i = \frac{ (\alpha/\beta)^i }{\sum^n_{i=0} (\alpha/\beta)^i}$

結論

• α > β のときは行列が長い確率の方が大きい
• α = β のとき、行列の長さは0からnまで等確率

同じ結果は、定常状態において α π_i = β π_{i +1} という考察からも導くことができる。π_i = (α/β) π_{i +1} から帰納法で π_i = π₀(α/β)ⁱ となる。

列の長さに上限 n が無い場合、マルコフ連鎖は有限ではない。もし定常分布があるとしたら（ない可能性もある）

$\begin{align} \pi_0 &= (1 - \alpha) \pi_0 + \beta \pi_1 \\ \pi_i &= \alpha \pi_{i-1} + (1 -\alpha -\beta) \pi_i + \beta \pi_{i+1} \ (i \geq 1) \end{align}$

の解が存在しなくてはならない。前出の解から類推して

$\pi_i = \frac{ (\alpha/\beta)^i }{\sum^\infty_{i=0} (\alpha/\beta)^i} = \Big(\frac{\alpha}{\beta}\Big)^i\Big(1-\frac{\alpha}{\beta}\Big)$

が答えになる。このとき　α < β でないと定常分布は存在しない。