マルコフ到着過程

待ち行列理論は確率論の一分野であり、マルコフ到着過程（MAPまたはMArP ^[1]）はシステムへのジョブ到着間隔を表す数学モデルである。最も単純な過程はポアソン過程であり、各到着間隔は指数分布に従う。^{[2] [3]}

このプロセスは1979年にマルセル・F・ノイツによって初めて提案されました。 ^{[2] [4]}

マルコフ到着過程は2つの行列D ₀とD _{1によって定義され、} D ₀の要素は隠れた遷移を表し、D ₁の要素は観測可能な遷移を表す。以下のブロック行列 Qは連続時間マルコフ連鎖の遷移率行列である。^[5]

${\displaystyle Q=\left[{\begin{matrix}D_{0}&D_{1}&0&0&\dots \\0&D_{0}&D_{1}&0&\dots \\0&0&D_{0}&D_{1}&\dots \\\vdots &\vdots &\ddots &\ddots &\ddots \end{matrix}}\right]\;.}$

最も単純な例は、 D ₀  = − λかつD ₁  =  λであるポアソン過程であり、この場合、遷移は1つしかなく、観測可能であり、遷移率はλである。Qが有効な遷移率行列であるためには、D _{iに次の制限が適用される。}

${\displaystyle {\begin{aligned}0\leq [D_{1}]_{i,j}&<\infty \\0\leq [D_{0}]_{i,j}&<\infty \quad i\neq j\\\,[D_{0}]_{i,i}&<0\\(D_{0}+D_{1}){\boldsymbol {1}}&={\boldsymbol {0}}\end{aligned}}}$

位相型更新プロセスは、到着間の位相型分散滞在を伴うマルコフ到着プロセスである。例えば、到着プロセスが到着間隔時間分布PHを持ち、終了ベクトルが と表される場合、到着プロセスは生成行列を持つ。 ${\displaystyle ({\boldsymbol {\alpha }},S)}$${\displaystyle {\boldsymbol {S}}^{0}=-S{\boldsymbol {1}}}$

${\displaystyle Q=\left[{\begin{matrix}S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&0&0&\dots \\0&S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&0&\dots \\0&0&S&{\boldsymbol {S}}^{0}{\boldsymbol {\alpha }}&\dots \\\vdots &\vdots &\ddots &\ddots &\ddots \\\end{matrix}}\right]}$

バッチマルコフ到着過程（BMAP）は、一度に複数の到着を許容することでマルコフ到着過程を一般化したものである。^{[6] [7]}同次ケースでは、速度行列は

${\displaystyle Q=\left[{\begin{matrix}D_{0}&D_{1}&D_{2}&D_{3}&\dots \\0&D_{0}&D_{1}&D_{2}&\dots \\0&0&D_{0}&D_{1}&\dots \\\vdots &\vdots &\ddots &\ddots &\ddots \end{matrix}}\right]\;.}$

サイズの到着は、部分行列 で遷移が発生するたびに発生します。部分行列には、ポアソン過程の速度である の要素があり、 ${\displaystyle k}$${\displaystyle D_{k}}$${\displaystyle D_{k}}$${\displaystyle \lambda _{i,j}}$

${\displaystyle 0\leq [D_{k}]_{i,j}}$

${\displaystyle 0\leq [D_{0}]_{i,j}$

${\displaystyle [D_{0}]_{i,i}}$

そして

${\displaystyle \sum _{k=0}^{\infty }D_{k}{\boldsymbol {1}}={\boldsymbol {0}}}$

マルコフ変調ポアソン過程またはMMPPでは、m個のポアソン過程が連続時間マルコフ連鎖によって切り替えられる。^[8] m個のポアソン過程のそれぞれが遷移率λ _iを持ち、変調連続時間マルコフが m  ×  m遷移率行列Rを持つ場合、MAP表現は

${\displaystyle {\begin{aligned}D_{1}&=\operatorname {diag} \{\lambda _{1},\dots ,\lambda _{m}\}\\D_{0}&=R-D_{1}.\end{aligned}}}$

MAPは期待最大化アルゴリズムを使用して適合させることができる。^[9]

• KPC-toolboxはデータにMAPを適合させるためのMATLABスクリプトのライブラリです。 ^[10]

• 合理的な到着プロセス