Ｍ／G／∞について

待ち行列理論

「Ｍ／Ｍ／∞について（２）」のつづきです。Ｍ／Ｇ／∞でも「Ｍ／Ｍ／∞について（２）」の式(5)

  • p(k)=\frac{\alpha^k}{k!}p(0)・・・・(5)

が成り立つことを示します。
Ｍ／Ｇ／∞待ち行列では、到着分布がポアソン分布なのでPASTAを使用することが出来ます。今、あるジョブが到着した時にある装置が処理中である確率は、PASTAによって時間平均での処理中である確率であるuに等しくなります。また、式(5)はu\rightar{0}での式なので、u\rightar{0}の場合を考えます。このため、任意のジョブは到着時には待ちがないと考えることが出来ます。待ちがない、ということはジョブは処理を受けるその装置とのみ関係し、他の装置の影響を受けないということになります。すると、全ての装置は独立に処理中になったり空きになったりすると考えることが出来ます。


さて、装置台数sが無限大である場合をいきなり考えるのではなくて、無限大ではないが非常に大きな数のsを考えることにします。sは非常に大きな数なので、ジョブの待ちはないものと考えることが出来る、とします。今、あるジョブが到着した時に、この待ち行列システム内にジョブがk個あるのを見出す確率を\pi(k)で表すことにします。するとある装置が処理中である事象は他の装置の事象とは独立で、かつ、その確率はuですから、到着したジョブが（自分を含めずに）待ち行列システム内にk個のジョブを見出す確率は二項分布

  • \pi(k)=\;_sC_ku^k(1-u)^{s-k}

になります。つまり

  • \pi(k)=\frac{s!}{k!(s-k)!}u^k(1-u)^{s-k}・・・・(7)

となります。式(7)でkをk+1に置き換えると

  • \pi(k+1)=\frac{s!}{(k+1)!(s-k-1)!}u^{k+1}(1-u)^{s-k-1}・・・・(8)

となります。式(8)の両辺を式(7)の両辺で割ると

  • \frac{\pi(k+1)}{\pi(k)}=\frac{s!}{(k+1)!(s-k-1)!}\frac{k!}{(s-k)!}{s!}\frac{u^{k+1}(1-u)^{s-k-1}}{u^k(1-u)^{s-k}
    • =\frac{k!(s-k)!}{(k+1)!(s-k-1)!}\cdot\frac{u}{1-u}=\frac{s-k}{k+1}\cdot\frac{u}{1-u}

よって

  • \frac{\pi(k+1)}{\pi(k)}=\frac{(s-k)u}{k+1}\cdot\frac{1}{1-u}・・・・(9)

となります。さらに式(4)を式(9)に代入すると

  • \frac{\pi(k+1)}{\pi(k)}=\alpha\left(1-\frac{k}{s}\right)\frac{1}{k+1}\cdot\frac{1}{1-u}・・・・(10)

となります。


ここで\alphaを有限に保ったままs\rightar\infty、u\rightar{0}にすることを考えてみます。すると

  • \frac{\pi(k+1)}{\pi(k)}=\alpha\frac{1}{k+1}
  • \frac{\pi(k+1)}{\pi(k)}=\frac{\alpha}{k+1}
  • \pi(k+1)=\frac{\alpha}{k+1}\pi(k)・・・・(11)

となります。ここで到着分布がポアソン分布であることを考えるとPASTAを使うことが出来るので

  • \pi(k)=p(k)・・・・(12)

となります。ここから式(5)が成り立つことが分かります。