Ｍ／Ｇ／１の定常状態累積分布の近似式

待ち行列理論

「Ｍ／Ｇ／１の定常状態分布の近似式」で求めた近似式は、累積確率、つまり、システム内に、ジョブがk個以下存在する確率P(k)

  • P(k)=\Bigsum_{j=0}^kp(j)・・・・・（１）

を近似する場合に、誤差が蓄積されることはなく、よい近似を生成出来るようです。というのは、「Ｍ／Ｄ／１の定常状態分布の近似式の精度」で近似式の精度を下のグラフに示しましたが、

このグラフから分かるようにＭ／Ｄ／１の時、近似式の誤差が大きいのはp(1)の誤差とp(2)の誤差の２つだけであり、しかもこの両者は符号が反対で絶対値がほぼ同じなので、p(1)+p(2)の誤差がp(1)やp(2)の誤差より小さくなるからです。


では、話をＭ／Ｇ／１の場合に戻し、この待ち行列のジョブの累積確率P(k)を求めてみましょう。「Ｍ／Ｇ／１の定常状態分布の近似式」から、p(k)の近似式は

  • p(0)=1-u・・・・・（２）
  • k{\ge}1の時
    • p(k){\approx}\frac{2(1-u)}{1+c_e^2}\left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)^k・・・・・（３）

でした。まず、

  • P(0)=p(0)

ですから、（２）から

  • P(0)=1-u・・・・・（４）

です。次にk{\ge}1の時

  • P(k)=P(0)+\Bigsum_{j=1}^kp(j)

なので、（３）と（４）から

  • P(k){\approx}1-u+\Bigsum_{j=1}^k\frac{2(1-u)}{1+c_e^2}\left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)^j
    • =1-u+\frac{2(1-u)}{1+c_e^2}\left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)\frac{1- \left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)^k}{1- \left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)}
    • =1-u+2(1-u)u\frac{1-\left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)^k}{2-(1-c_e^2)u-(1+c_e^2)u}
    • =1-u+2(1-u)u\frac{1-\left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)^k}{2(1-u)}
    • =1-u+u\left[1-\left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)^k\right]=1-u\left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)^k

よって

  • P(k){\approx}1-u\left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)^k・・・・・（５）

式（５）はk{\ge}1という前提がありましたが、その右辺にk=0を代入する

  • 1-u\left(\frac{(1+c_e^2)u}{2-(1-c_e^2)u}\right)^0=1-u

となって（４）の右辺と一致するので式（５）は０以上の任意のkについて近似式として使えることが分かります。


さて、式（５）をＭ／Ｍ／１に適用すると、処理時間は指数分布なので

  • c_e=1・・・・・（６）

よって、これを式（５）に代入すると

  • P(k){\approx}1-u\left(\frac{2u}{2}\right)^k=1-u{\times}u^k=1-u^{k+1}

つまり

  • P(k){\approx}1-u^{k+1}・・・・・（７）

しかし、これはもとの式（３）がＭ／Ｍ／１の時には近似式ではなくて等号が成り立ちますので、（７）も等号が成り立ちます。先に式（３）の右辺に式（６）を代入した時の式を確認しておきます。

  • 式（３）の右辺=\frac{2(1-u)}{1+1}\left(\frac{(1+1)u}{2}\right)^k=(1-u)u^k

となってＭ／Ｍ／１の時の正しい状態確率の式になります（「Ｍ／Ｍ／１における待ち時間の式の導出（２）」の式（９）参照）。よって（３）から導き出された（７）の右辺も近似ではなく正確な式になります。よって、

  • P(k)=1-u^{k+1}・・・・・（７'）

が成り立ちます。


次に、式（５）をＭ／Ｄ／１に適用してみます。処理時間は一定なので

  • c_e=0・・・・・（８）

よって、これを式（５）に代入すると

  • P(k){\approx}1-u\left(\frac{(1+0)u}{2-(1-0)u}\right)^k

つまり

  • P(k){\approx}1-u\left(\frac{u}{2-u}\right)^k・・・・・（９）

これは近似式なので、今度はその精度を知りたくなります。


「Ｍ／Ｄ／１の定常状態累積分布の近似式の精度」に続きます。