ＧＩ／Ｍ／１待ち行列の到着時状態分布（１）

Ｄ／Ｍ／１では、ジョブ到着直前にシステム内にジョブが $k$ 個存在する確率 $\pi(k)$ について

$\pi(k)=(1-b)b^k$ 　ただし $b$ は定数　・・・・(1)

が成り立つことが「Ｄ／Ｍ／１待ち行列の到着時刻状態分布（１）」「（２）」から分かりました。一方、Ｍ／Ｍ／１では時間平均での、システム内にジョブが $k$ 個存在する確率 $p(k)$ について

$p(k)=(1-u)u^k$ ・・・・(2)

でした（「Ｍ／Ｍ／１における待ち時間の式の導出（２）」の式(9)参照）。ところがＭ／Ｍ／１の時はＰＡＳＴＡが成立するので、

$\pi(k)=p(k)$ ・・・・(3)

となるため、

$\pi(k)=(1-u)u^k$ ・・・・(4)

となります。よってＭ／Ｍ／１でも式(1)が成り立つことが分かります。そうすると一般のＧＩ／Ｍ／１について式(1)が成り立つのではないか、という予想が立ちます。この予想が成り立つかどうか調べてみましょう。

ジョブが到着する間隔は確率密度 $g(t)$ で分布しているとします。つまりジョブが到着する間隔が $t$ から $t+dt$ の間にある確率は $g(t)dt$ です。ジョブが到着する間隔が $t$ であったとして、この間隔の間にジョブが $k$ 個処理終了する確率を求めます。待っているジョブが $k$ 個以上あると仮定します。すると、これが時間 $t$ 内に $k$ 個終了する確率はポアソン分布になるので「ポアソン分布」の式(1)から

$p(k;t)=\frac{(t/t_e)^k}{k!}\exp(-t/t_e)$ ・・・・(5)

となります。ジョブ到着間隔が $t$ から $t+dt$ の間にある確率は $g(t)dt$ ですから、あるジョブが到着して次のジョブが到着するまでに装置がジョブを $k$ 個処理する確率 $B(k)$ は式(5)と $g(t)dt$ から

$B(k)=\Bigint_0^{\infty}\frac{(t/t_e)^k}{k!}\exp(-t/t_e)g(t)dt$ ・・・・(6)

になります。

あるジョブ到着直前にシステムにジョブが $j$ 個あったとします。その次のジョブ到着直前に $k$ 個になる確率を $C(j,k)$ で表すことにします。この間隔の間にジョブは１個到着しますが、処理完了するジョブは最大、全部終了する可能性があります。つまり最大 $k+1$ 個、終了する可能性があります。よってジョブが２個以上増える確率はゼロです。よって

$C(j,k)=0$ 　　ただし $k{\ge}j+2$ ・・・・(7)

です。さらに、２番目の到着直前にジョブが $k$ 個残っている確率は、 $k{\ge}1$ の場合には式(6)を用いて

$C(j,k)=B(j+1-k)$ 　ただし $1{\le}k{\le}j+1$ ・・・・(8)

となります。２番目の到着直前にジョブが０個残っている確率には式(8)は適用出来ません。というのは１つ前のジョブ到着直前にはシステムにはジョブが $j$ 個しかないので、到着したジョブも含めて $j+1$ 個より多くのジョブが処理完了することはないからです。最初の到着の直前に $j$ 個だった場合に、次の到着直前でのジョブ数の全ての可能性の確率を足せば１になるはずですから、