豊前アルゴリズム

待ち行列理論（確率論の一分野）において、ブーゼンのアルゴリズム（または 畳み込みアルゴリズム）は、ゴードン・ニューウェル定理における正規化定数G( N )を計算するアルゴリズムである。この手法は、ジェフリー・P・ブーゼンが1971年の博士論文^{[ 1 ]}で初めて提案し、その後1973年に査読付き学術誌に掲載された^{[ 2 ]}。G( N )の計算は、閉待ち行列ネットワークの定常確率分布を計算するために必要となる^{[ 3 ] 。}

正規化定数の単純な計算を実行するには、すべての状態を列挙する必要があります。N 人の循環顧客とM 人のサービス施設がある閉ネットワークの場合、 G( N ) は個々の項の合計であり、各項はM 個の因数の累乗で構成され、その合計はNになります。Buzen のアルゴリズムは、 NM 回の乗算とNM回の加算のみを使用してG( N )を計算します。この劇的な改善により、ゴードン・ニューウェルの定理を、実際のコンピュータ システムや柔軟な製造システム、相互接続されたサービス施設のネットワーク内でボトルネックや待ち行列が形成される可能性のあるその他のケースのモデルに適用できるようになりました。 ^{[ 4 ]} G(1)、G(2)...G( N -1)の値は、他の重要な関心対象の量を計算するために使用できますが、アルゴリズムの副産物として計算されます。 ${\displaystyle {\tbinom {N+M-1}{M-1}}}$

問題の設定

M個のサービス施設とN人の循環顧客を持つ閉待ち行列ネットワークを考える。サービス施設iにおける顧客のサービス時間は、パラメータμ _iを持つ指数分布に従う確率変数で与えられ、サービス施設iでのサービスを終えた顧客は、確率p _ijで次のサービス施設jへ移動すると仮定する。^{[ 3 ]}

をサービス施設iの顧客数がi = 1, 2, ... , M に対してn _iに等しい定常状態確率とする。ゴードン・ニューウェルの定理 から、 ${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})}$

${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}}$ ${\displaystyle \left(X_{1}\right)^{n_{1}}}$ ${\displaystyle \left(X_{2}\right)^{n_{2}}}$.... ${\displaystyle \left(X_{M}\right)^{n_{M}}}$

この結果は通常、より簡潔に次のように記述されます。

${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}\prod _{i=1}^{M}\left(X_{i}\right)^{n_{i}}}$

X _iの値は次のように解くことによって決定される。

${\displaystyle \mu _{j}X_{j}=\sum _{i=1}^{M}\mu _{i}X_{i}p_{ij}\quad {\text{ for }}j=1,\ldots ,M.}$

G ( N )は、すべての値の合計が1になるように選ばれた正規化定数である。Buzenのアルゴリズムは、G( N )を計算する最初の効率的な手順である。^{[ 2 ] [ 4 ]} ${\displaystyle {\tbinom {N+M-1}{M-1}}}$ ${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})}$

アルゴリズムの説明

G( N )を計算するために加算する必要がある個々の項はすべて次の形式になります。

${\displaystyle \left(X_{1}\right)^{n_{1}}}$ ${\displaystyle \left(X_{2}\right)^{n_{2}}}$....この項の集合は2つのグループに分けられることに注意してください。最初のグループは、指数が1以上のすべての項で構成されます。これは、これらの項のそれぞれから1乗を因数分解できることを意味します。   ${\displaystyle \left(X_{M}\right)^{n_{M}}}$ ${\displaystyle \left(X_{M}\right)}$ ${\displaystyle \left(X_{M}\right)}$

を因数分解すると、驚くべき結果が得られる。第1グループの修正項は、同じネットワークから顧客を1人削除した正規化定数を計算する際に使用した項と同一である。したがって、第1グループの項の合計は「X _M ×G( N -1)」と表すことができる。この知見は、アルゴリズム開発の基礎となっている。^{[ 4 ]} ${\displaystyle \left(X_{M}\right)}$  

次に、2番目のグループについて考えてみましょう。このグループのすべての項におけるX _Mの指数 は0です。その結果、サービス施設Mは、このグループのすべての項から実質的に消え去ります（すべての場合において1に減少するため）。これにより、残りのM -1個のサービス施設 の顧客総数はNとなります。2番目のグループには、これらのN人の顧客のあらゆる可能な配置が含まれます。

この概念を正確に表現するために、M個のサービス施設を持つ特定のネットワークについて、 X ₁、X ₂、… X _M が得られたと仮定します。任意のn ≤ Nおよびm ≤ Mについて、 g( n,m )を、 n人の顧客、m個のサービス施設(1,2,… m )、および  元のシーケンスX ₁、X ₂、… X _Mの最初のm個の要素  と一致するX ₁、X ₂、… X _mの値を持つネットワークの正規化定数として定義します。

この定義によれば、第2グループの項の合計はg( N , M -1)と書くことができます。

また、最初のグループの項の合計である「 X _M × G( N -1)」は、「 X _M × g( N -1, M )」と書き直すことができることもすぐにわかります。  

さらに、ゴードン・ニューウェルの定理における正規化定数G( N )はg( N , M )と書き直すことができる。

G( N )は第1群​​と第2群の項の合計に等しいので、

G( N ) = g( N , M ) = X _M g( N -1, M ) + g( N , M -1)

この同じ再帰関係は、 1 からNまでのnの任意の中間値、および1 からMまでのmの任意の中間値に対して明らかに存在します。  

これは、g( n,m ) = X _m g( n -1, m ) + g( n,m -1) を意味します。Buzenのアルゴリズムは、この基本的な再帰関係と以下の境界条件を単純に反復的に適用したものです。

g(0, m ) = 1（m = 1, 2, … M）

g( n ,1) = ( Xi ₎ n ^（ n = 0, 1, … N ）

周辺分布、期待顧客数

ゴードン・ニューウェル定理は、分析者が閉行列ネットワークの各状態に関連する定常確率を決定することを可能にします。これらの個々の確率は、他の重要な確率を評価するために合計する必要があります。例えば、サービスセンターiの顧客総数がk以上である確率 P( n _i ≥ k ) は、 n _i ≥ kのすべての値について合計する必要があり、また、各n _iの値について、残りのN – n _i人の顧客がネットワーク内の 他のM -1 個のサービスセンターに分配される可能性のあるすべての方法について合計する必要があります。

これらの周辺確率の多くは、最小限の追加労力で計算できます。これは、P( n _i ≥ k ) の場合に容易にわかります。明らかに、サービスセンターiの顧客数が k 以上であるすべての状態において、X i_はk乗以上でなければなりません。したがって、X _i ^{k は}これらの各確率から因数分解することができ、合計が G( N -k)/G( N )となる修正確率の集合が残ります。この観察から、次のような単純かつ非常に効率的な結果が得られます。

P( n _i ≥ k ) = ( X _i ) ^k G( N - k )/G( N )

この関係を使用して、各サービス施設の周辺分布と予想顧客数を 計算できます。

${\displaystyle \mathbb {P} (n_{i}=k)={\frac {X_{i}^{k}}{G(N)}}[G(N-k)-X_{i}G(N-k-1)]\quad {\text{ for }}k=0,1,\ldots ,N-1,}$

${\displaystyle \mathbb {P} (n_{i}=N)={\frac {X_{i}^{N}}{G(N)}}.}$

サービス施設iの期待顧客数は次のように与えられる。

${\displaystyle \mathbb {E} (n_{i})=\sum _{k=1}^{N}X_{i}^{k}{\frac {G(N-k)}{G(N)}}.}$

G( n )による関心量のこれらの特徴づけもBuzenによるものである。^{[ 2 ]}

実装

X _{m は}関連方程式を解くことで計算済みであり、ルーチンへの入力として利用可能であると仮定します。g( n,m ) は原理的には2次元行列ですが、左端の列の上から始めて各列を一番下まで下り、その後右隣の列へと進むという、列ごとの計算も可能です。ルーチンでは、gの現在の列を表すために単一の列ベクトルCを使用します。

以下のアルゴリズムの最初のループでは、列ベクトルC[n]を初期化し、n≥1の場合にはC[0] = 1、C(n) = 0となるようにします。以降の反復処理では、C[0]は1のままであることに注意してください。  

2番目のループでは、アルゴリズムがm列目に進むにつれて、n≥1におけるC(n)の各値は、対応するg( n,m)の値に等しく設定されます。これは、C(n)の各値を以下のように設定することで実現されます。

g( n,m-1 )にXm_を掛けた g( n-1,m )を足す。  

g( n,m-1 )はC(n)の前の値であり、g( n-1,m )はC(n-1)の現在の値である ことに注意してください。

C [ 0 ] := 1 、n := 1、ステップ1、NまでC [ n ] : = 0 ;m := 1 の場合、ステップ1 、 Mまで実行n := 1 の場合、ステップ1 、 Nまで実行C [ n ] := C [ n ] + X [ m ] * C [ n - 1 ] ;

完了時に、C[n]の最終値は行列g( n,m )の列Mに対応する。したがって、それらは所望の値G (0), G (1), ..., G (N)を表す。^{[ 2 ]}

参考文献

1. Buzen, JP (1971-08-01). DTIC AD0731575: マルチプログラミングのキューイングネットワークモデル.
2. Buzen, JP (1973). 「指数サーバーを備えた閉キューイングネットワークの計算アルゴリズム」(PDF) . Communications of the ACM . 16 (9): 527– 531. doi : 10.1145/362342.362345 . S2CID 10702. 2016年5月13日時点のオリジナル(PDF)からのアーカイブ。 2006年4月15日閲覧。 
3. Gordon, WJ; Newell, GF (1967). 「指数関数的サーバーを備えた閉キューイングシステム」.オペレーションズ・リサーチ. 15 (2): 254. doi : 10.1287/opre.15.2.254 . JSTOR 168557 . 
4. Denning, Peter J. (2016年8月24日). 「ランダム性の再考：ジェフ・ブゼン氏へのインタビュー パート1」 . Ubiquity . 2016年8月号: 1:1–1:17. doi : 10.1145/2986329 .

• Jain: 畳み込みアルゴリズム（授業配布資料）
• Menasce: キューイングアルゴリズムへの畳み込みアプローチ (プレゼンテーション)

「 https://en.wikipedia.org/w/index.php?title=Buzen%27s_algorithm&oldid=1292520983」より取得