QNA読解：III.即座戻りの除去（１） - 工場統計力学（建設中！）

上位エントリー：Word Whitt: The Queueing Network Analyzerの構成
「QNA読解：2.3　クラスとルート毎のインプット（５）」の続きです。即座戻りとは下図のノード $i$ の赤線のようなルートのことを言います。

この経路はノード $i$ から出てノード $i$ に入ります。これが即座戻りです。この即座戻りはQNAの近似品質を下げるそうです。そのため、即座戻りのないネットワークに置き換えることがQNAの品質を高めるということです。この章では、即座戻りを除去し、どのようにノードの諸パラメータを調整して、除去した部分の効果を補うか、について説明しています。

この手続きは、元々Kuehn*1によって提案されていたが、通常、近似の質を上げている。

あるいはこうも述べられています。

　経験は、即座戻りの除去がしばしばよりよい近似をもたらすことを示している（Kuehn*2と、Whitt*3のセクションVとVIIを参照）。

この章では、まず、

即座戻りのルートを除去した場合、それを補足するためにノードの諸パラメータをどのように変更すべきかについて述べます。次に、
混雑尺度を計算する際に、それらの諸パラメータを用いた計算結果にさらに補正が必要であることを述べています。

まずは上記１について、そしてその中でも平均処理時間 $\tau_i$ をどのように変更すべきか、について述べます。
上の図でノード $i$ を終わった客（＝ジョブ）は、 $q_{ii}$ の確率でノード $i$ に戻ってきます。この客はノード $i$ で処理を受けたのち、また $q_{ii}$ の確率でノード $i$ に戻ってきます。この客はノード $i$ から最終的に別のノードに移るまでに何回ノード $i$ を通過するでしょうか？　それは

$1+q_{ii}+q_{ii}^2+q_{ii}^3+.....=\frac{1}{1-q_{ii}}$

となります。ノード $i$ への１回の訪問で客が費やす時間は $\tau_i$ ですから、この客は別のノードに移るまでに

$\frac{\tau_i}{1-q_{ii}}$

時間費やすことになります。よって、即座戻りルートを除去した場合、 $\tau_i$ を $\tau_i/(1-q_{ii})$ に置き換えないと、客がノード $i$ で費やす時間が過少に見積られることになります。即座戻りを除去した後のノードの諸パラメータの補正値を「＾」をつけて表わすことにします。すると

$\hat\tau_i=\tau_i/(1-q_{ii})$

と表わすことが出来ます。以上のことは原論文の以下のところに述べられています。

　QNAは個々の客に、他のノードからの到着時に、他のノードへ向かう前の客の総サービス時間を与えることにより即座戻りを除去する。・・・・・言い換えれば、他のどこかからノード $i$ への個々の訪問プラスすぐに戻る全ての後続の時間は１回の訪問と解釈される。埋め合わせのためにサービス時間は増やされる。

次に遷移確率 $q_{ij}$ はどのように補正されるでしょうか？
まず、即座戻りが除去されますから $\hat{q}_{ii}=0$ になります。では $i{\ne}j$ の場合の $\hat{q}_{ij}$ はどうなるでしょうか？　これは一種の条件確率と解釈できます。つまり客がノード $i$ に戻らなかったとした場合に、その客がノード $j$ に行く確率になります。客がノード $i$ に戻らない確率は $1-q_{ii}$ なので、