情報ネットワーク(スライド3〜4)part2

前のに続けて書いてもよかったけど長くなったので、新しく。

M/M/1/K待ち行列
M/M/1待ち行列は、到着がポアソン分布で、処理が指数分布で、処理する場所は1つの待ち行列でした。

M/M/1/K待ち行列は、さらに、行列には最大K人までしか並べないという条件がつきます。
K+1人目がやってきても、棄却(なかったことに)します。
行列が並ぶスペースがもう残ってなくて、他のお客さんにも迷惑なので空いたらまた来てください。といった具合ですね。

この場合、M/M/1待ち行列の場合と同様に、漸化式から求めます。
$0\leq n\lt K$ の状態遷移は、M/M/1待ち行列と一緒ですので、端の条件を新しく加えます。

$(\lambda + \mu ) P_n = \lambda P_{n-1} + \mu P_{n+1}$ 　　　 $(0\lt n \lt K)$
$\lambda P_0 = \mu P_1$
$\lambda P_{K-1} = \mu P_K$
より、
$P_n = \rho^nP_0$
また、
$\sum_{n=0}^{K}P_n = 1$ より、
$P_0 = \frac{1-\rho}{1-\rho^{K+1}}$

一見キモイけどただの等比級数だから、覚えなくても導出すればいいね。

ちなみに、平均ジョブ数(N)と、平均遅延時間(D)は、

$N = \sum_{n=0}^{K}nP_n =\frac{\rho(1-\rho^{K+1})-(K+1)\rho^{K+1}(1-\rho)}{(1-\rho)(1-\rho^{K+1})}$
$D = \frac{N}{\lambda (1-P_K)}$

です。なぜこうなるかはよくわかりませんが、等比級数が得意な方は是非とも計算してみてください。
平均遅延時間は、ジョブの棄却を考えると、実効的な到着率が $\lambda(1-P_K)$ になるためだそうですが、直感的にはあまりわかりません。
おそらくK人待ってる時は到着率が0になるからだと思われます。

M/M/S待ち行列
M/M/1待ち行列の処理するところがS個に増えたもの。
解放は基本的にM/M/1と一緒。
多分出ないから省略。

M/G/1待ち行列
処理時間分布に指数分布ではなく、一般分布を用いたもの。

隠れマルコフの方法
なんかすごく懐かしい言葉。ジョブの処理を開始した時刻や、終了した時刻などの特別な時刻に対して状態方程式を導くことで、解析をおこなう。

M/G/1結構大事っぽいよなぁ〜。
でも出るかといわれると微妙だなぁ。
読むのメンドくさいから切ろう。
ていうか、資料多い…。バイトの時間めいっぱい使ってやってんのに、全然進まん…。