到着定理

数学的確率論の一分野である待ち行列理論における到着定理[ 1 ] ^（ランダム観測者特性、ROP 、またはジョブ観測者特性^[2]とも呼ばれる）は、「ステーションに到着すると、ジョブは、そのジョブがないシステムが任意の瞬間に定常状態にあるかのようにシステムを観察する」と述べています^{[3] 。}

到着定理は、各ノードに無制限のキューを持つオープンな積形式ネットワークでは常に成立しますが、より一般的なネットワークでも成立します。積形式ネットワークで到着定理が満たされるための必要十分条件は、Boucherie & Dijk (1997) でパーム確率の観点から示されています。 ^[4]同様の結果は、一部のクローズドネットワークでも成立します。到着定理が成立しない積形式ネットワークの例には、可逆キングマンネットワーク^{[4] [5]}や遅延プロトコルを持つネットワークなどがあります。^[3]

ミトラニは、「入ってくるジョブから見たノードiの状態は、ランダムな観察者から見た状態とは異なる分布を持つ。例えば、入ってくるジョブは、ノードiに存在するすべての「 k」個のジョブを見ることはできない。なぜなら、入ってくるジョブ自体がすでに存在するジョブの中にいることはできないからだ」という直感を提供している。^[6]

ポアソン過程の場合、この特性はPASTA特性（ポアソン到着時間平均を参照）と呼ばれることが多く、外部のランダムな観察者から見た状態の確率は、到着する顧客から見た状態の確率と同じであることを示しています。 ^{[7]この特性は、速度パラメータが状態に応じて変化することが許可されている}二重確率ポアソン過程の場合にも当てはまります。^[8]

m 個のキューを持つオープンジャクソン ネットワークでは、ネットワークの状態を と記述します。 は、ネットワークが状態 にある均衡確率であるとします。この場合、任意のノードへの到着直前にネットワークが状態 にある確率も です。 ${\textstyle \mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}$${\textstyle \pi (\mathbf {n} )}$${\textstyle \mathbf {n} }$${\textstyle \mathbf {n} }$${\textstyle \pi (\mathbf {n} )}$

この定理は、連続時間における定常状態を考慮したジャクソンの定理からは導かれないことに注意する。ここでは、到着時間という特定の時点に着目している。^[9]この定理は、1981年にセヴシックとミトラニによって初めて発表された。^[10]

m個のキューを持つ閉じたゴードン・ニューウェルネットワークにおいて、ネットワークの状態を と書きます。状態 へ移動中の顧客について、到着直前に顧客がシステムの状態を「見る」確率を と書きます 。${\displaystyle {\mathbf {n} =(n_{1},n_{2},\ldots ,n_{m})}}$${\displaystyle i}$${\displaystyle {\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}}$

${\displaystyle \mathbf {n} -\mathbf {e} _{i}=(n_{1},n_{2},\ldots ,n_{i}-1,\ldots ,n_{m}).}$

この確率は、顧客が1人少ない同じタイプのネットワークの状態の定常状態確率と同じです。^{[11]これは、SevcikとMitrani、 [10]}とReiserとLavenberg ^[12]によって独立して発表され、その結果は平均値分析の開発に使用されました。 ${\displaystyle {\alpha _{i}(\mathbf {n} -\mathbf {e} _{i})}}$${\displaystyle {\mathbf {n} -\mathbf {e} _{i}}}$