Adm: Created page with "==待ち行列== 窓口に並ぶ客の人数 ''i'' をモデルしよう。単位時間において以下の事象が発生する。 * もし ''i < n'' だったら、確率 ''&..."

2011-10-13T13:26:21Z

Created page with "==待ち行列== 窓口に並ぶ客の人数 ''i'' をモデルしよう。単位時間において以下の事象が発生する。 * もし ''i < n'' だったら、確率 ''&..."

New page

==待ち行列==
窓口に並ぶ客の人数 ''i'' をモデルしよう。
単位時間において以下の事象が発生する。
* もし ''i < n'' だったら、確率 ''α'' で客が一人増える。
* もし ''i > 0'' なら、確率 ''β'' で先頭から順に客は減る。
* それ以外の場合、客の数は変化しない。

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

<math>
\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}
</math>

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

<math>
\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}
</math>

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

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

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

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

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

<math>
\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}
</math>

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

<math>\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)</math>

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

Aritalab:Lecture/NetworkBiology/Markov Chains/Queue - Revision history

Adm: Created page with "==待ち行列== 窓口に並ぶ客の人数 ''i'' をモデルしよう。 単位時間において以下の事象が発生する。 * もし ''i < n'' だったら、確率 ''&..."

Adm: Created page with "==待ち行列== 窓口に並ぶ客の人数 ''i'' をモデルしよう。単位時間において以下の事象が発生する。 * もし ''i < n'' だったら、確率 ''&..."