工場統計力学（建設中！）

Ｍ／Ｇ／１のp(k)の確率母関数（２）

待ち行列理論

Ｍ／Ｇ／１待ち行列の $p(k)$ の確率母関数を求める別な方法は次の通りです。今度は、ジョブが処理終了時点での残りのシステム内ジョブ数は、このジョブが到着してから到着したジョブ数に（ＦＩＦＯなので）等しい、という事実から考察します。ジョブの待ち時間の確率変数を $W$ とします。ジョブの処理時間の確率変数を $S$ とします。するとこのジョブが処理終了する時に待ち行列システム内にあるジョブは $W+S$ の間に到着したことになります。 $W+S$ の確率密度関数を $h(t)$ とします。時間 $t$ の間にジョブが $k$ 個到着する確率はポアソン分布の式（「ポアソン分布」参照）

$p(k,t)=\frac{({\lambda}t)^k}{k!}\exp(-{\lambda}t)$ ・・・・(17)

なので、 $p(k)$ は

$p(k)=\Bigint_0^{\infty}\frac{({\lambda}t)^k}{k!}\exp(-{\lambda}t)h(t)dt$ ・・・・(18)

となります。
「Ｍ／Ｇ／１のp(k)の確率母関数（１）」の式(5)

$L^*(z)=\Bigsum_{k=0}^{\infty}p(k)z^k$ ・・・・(5)

に式(18)を代入すると

- $=\Bigint_0^{\infty}\exp(-{\lambda}t)h(t)\Bigsum_{k=0}^{\infty}\frac{({\lambda}t)^k}{k!}z^kdt$
- $=\Bigint_0^{\infty}\exp(-{\lambda}t)h(t)\Bigsum_{k=0}^{\infty}\frac{({\lambda}zt)^k}{k!}dt$
- $=\Bigint_0^{\infty}\exp(-{\lambda}t)h(t)\exp({\lambda}zt)dt$

よって

$L^*(z)=\Bigint_0^{\infty}\exp(-({\lambda}-{\lambda}z)t)h(t)dt$ ・・・・(19)

となります。ところで $h(t)$ のラプラス変換を $H^*(s)$ で表すと

$H^*(s)=\Bigint_0^{\infty}\exp(-st)h(t)dt$ ・・・・(20)

ですから、式(19)は

$L^*(z)=H^*({\lambda}-{\lambda}z)$ ・・・・(21)

と書けます。このように「Ｍ／Ｇ／１のp(k)の確率母関数（１）」とは別の方法で $p(k)$ の確率母関数 $L^*(z)$ を求めることが出来ました。

この式(21)と「Ｍ／Ｇ／１のp(k)の確率母関数（１）」の式(16)

$L^*(z)=\frac{(1-u)(z-1)G(\lambda-{\lambda}z)}{z-G(\lambda-{\lambda}z)}$ ・・・・(16)

を組み合わせると何が分かるでしょうか？　
さて、 $h(t)$ は $W+S$ の確率密度関数でした。一方、式(16)の $G(s)$ は処理時間 $S$ の確率密度関数 $g(t)$ のラプラス変換でした。そこで、 $W$ の確率密度関数を $w(t)$ で表せば、

$h(t)=\Bigint_t^{\infty}w(\tau)g(t-\tau)d\tau$ ・・・・(22)

となります。すると

$\Bigint_0^{\infty}\exp(-st)h(t)dt=\Bigint_t^{\infty}\Bigint_0^t\exp(-s\tau)w(\tau)\exp(-s(t-\tau))g(t-\tau)d\tau{dt}$ ・・・・(23)

ここで

$x=t-\tau$ ・・・・(24)

と置いて、 $(\tau,t)$ の代わりに $(\tau,x)$ で積分することにすれば、 $\tau$ と $x$ の積分の積分区間はともに $0$ から $\infty$ になるので

$\Bigint_0^{\infty}\exp(-st)h(t)dt=\Bigint_t^{\infty}\Bigint_0^{\infty}\exp(-s\tau)w(\tau)\exp(-sx)g(x)d{\tau}dx$

よって

$\Bigint_0^{\infty}\exp(-st)h(t)dt=\Bigint_t^{\infty}\exp(-s\tau)w(\tau)d\tau\Bigint_0^{\infty}\exp(-sx)g(x)dx$ ・・・・(25)

ここで $w(t)$ のラプラス変換をそれぞれ $W^*(s)$ で表すことにし、 $g(t)$ のラプラス変換は $G(s)$ であることに注意すれば式(25)は

$H^*(s)=W^*(s)G(s)$ ・・・・(26)

となります。式(26)と式(21)から

$L^*(z)=W^*({\lambda}-{\lambda}z)G({\lambda}-{\lambda}z)$ ・・・・(26)

となります。式(16)と式(26)から

$W^*({\lambda}-{\lambda}z)G({\lambda}-{\lambda}z)=\frac{(1-u)(z-1)G(\lambda-{\lambda}z)}{z-G(\lambda-{\lambda}z)}$

よって

$W^*({\lambda}-{\lambda}z)=\frac{(1-u)(z-1)}{z-G(\lambda-{\lambda}z)}$ ・・・・(27)

ここで

$s=\lambda-{\lambda}z$

と置けば

$z=\frac{\lambda-s}{\lambda}$

なので式(27)は

$W^*(s)=\frac{(1-u)(\frac{\lambda-s}{\lambda}-1)}{\frac{\lambda-s}{\lambda}-G(s)}$

よって

$W^*(s)=\frac{(1-u)(\lambda-s-\lambda)}{\lambda-s-{\lambda}G(s)}$
$W^*(s)=\frac{(1-u)s}{s-\lambda+{\lambda}G(s)}$ ・・・・(28)

となります。この式によって待ち時間 $W$ の分布が処理時間 $S$ の分布から求めることが出来そうです。

本エントリーを作成するに際して、滝根哲哉教授の「確率離散事象論講義資料」　
http://www-optima.amp.i.kyoto-u.ac.jp/~takine/tmp/shiryou.pdf
を参考に致しました。感謝致します。