Markovianský proces příjezdu - Markovian arrival process

v teorie front, disciplína v rámci matematické teorie pravděpodobnosti, a Markovianský proces příjezdu (MAPA nebo MArP^[1]) je matematický model pro dobu mezi příchody úloh do systému. Nejjednodušší takový proces je Poissonův proces kde je čas mezi každým příjezdem exponenciálně distribuováno.^[2][3]

Procesy byly poprvé navrženy Neuts v roce 1979.^[2][4]

Definice

Proces příjezdu Markov je definován dvěma maticemi D₀ a D₁ kde prvky D₀ představují skryté přechody a prvky D₁ pozorovatelné přechody. The bloková matice Q níže je a matice přechodové rychlosti pro Markovův řetězec v nepřetržitém čase.^[5]

${displaystyle Q = left [{egin {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} } hned] ;.}$

Nejjednodušším příkladem je Poissonův proces, kde D₀ = −λ a D₁ = λ tam, kde existuje pouze jeden možný přechod, je pozorovatelný a probíhá rychlostí λ. Pro Q aby byla platná matice rychlosti přechodu, platí následující omezení D_i

${displaystyle {egin {aligned} 0leq [D_ {1}] _ {i, j} &$

Speciální případy

Markov modulovaný Poissonův proces

The Markov modulovaný Poissonův proces nebo MMPP kde m Poissonovy procesy se přepínají mezi podkladem Markovův řetězec v nepřetržitém čase.^[6] Pokud každý z m Poissonovy procesy mají rychlost λ_i a Markovův modulační spojitý čas m × m matice přechodové rychlosti R, pak je reprezentace MAP

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

Proces obnovy fázového typu

The proces obnovy fázového typu je proces příjezdu Markov s distribuovaný fázový typ pobyt mezi příjezdy. Například pokud má proces příjezdu distribuci času mezi příjezdy PH${displaystyle ({oldsymbol {alpha}}, S)}$ s výstupním vektorem označeným ${displaystyle {oldsymbol {S}} ^ {0} = - S {oldsymbol {1}}}$, proces příjezdu má generátorovou matici,

${displaystyle Q = left [{egin {matrix} S & {oldsymbol {S}} ^ {0} {oldsymbol {alpha}} & 0 & 0 & dots 0 & S & {oldsymbol {S}} ^ {0} {oldsymbol {alpha}} & 0 & dots 0 & 0 & S & {oldsymbol {S}} ^ {0} {oldsymbol {alpha}} & tečky vdots & vdots & ddots & ddots & ddots end {matrix}} ight]}$

Dávkový proces příjezdu Markova

The hromadný proces příjezdu Markovian (BMAP) je zobecněním procesu příjezdu Markovian tím, že umožňuje více než jeden příjezd najednou.^[7] Homogenní případ má rychlostní matici,

${displaystyle Q = left [{egin {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}} ight];}$

Příchod velikosti ${displaystyle k}$ nastane pokaždé, když v submatici dojde k přechodu ${displaystyle D_ {k}}$. Dílčí matice ${displaystyle D_ {k}}$ mít prvky ${displaystyle lambda _ {i, j}}$, sazba a Poissonův proces, takový, že

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

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

${displaystyle [D_ {0}] _ {i, i} <0;}$

a

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

Kování

MAP lze namontovat pomocí algoritmus očekávání – maximalizace.^[8]

Software

• Sada nástrojů KPC knihovna MATLAB skripty pro přizpůsobení MAP datům.^[9]

Viz také

• Racionální proces příjezdu

Reference