Rovnice rovnováhy - Balance equation
v teorie pravděpodobnosti, a bilanční rovnice je rovnice který popisuje pravděpodobnostní tok spojený s a Markovův řetězec dovnitř a ven ze států nebo sady států.[1]
Globální rovnováha
The globální bilanční rovnice (také známý jako úplné bilanční rovnice[2]) jsou souborem rovnic, které charakterizují rovnovážné rozdělení (nebo jakákoli stacionární distribuce) Markovova řetězce, pokud taková distribuce existuje.
Pro Markovův řetězec nepřetržitého času se stavovým prostorem , rychlost přechodu ze stavu na dána a rovnovážné rozdělení dané , jsou globální bilanční rovnice dány vztahem[3]
nebo ekvivalentně
pro všechny . Tady představuje pravděpodobnostní tok ze stavu do stavu . Takže levá strana představuje celkový tok ze stavu mimo stav i do jiných států než i, zatímco pravá strana představuje celkový tok ze všech stavů do stavu . Obecně je výpočetně neřešitelné řešit tento systém rovnic pro většinu modelů ve frontě.[4]
Podrobný zůstatek
Pro Markovův řetězec nepřetržitého času (CTMC) s matice přechodové rychlosti , pokud lze najít tak, že pro každý pár států a
drží, pak sečtením , globální bilanční rovnice jsou splněny a je stacionární distribuce procesu.[5] Pokud lze takové řešení najít, jsou výsledné rovnice obvykle mnohem jednodušší než přímé řešení rovnic globální rovnováhy.[4]
CTMC je reverzibilní tehdy a jen tehdy, pokud jsou splněny podrobné podmínky rovnováhy pro každou dvojici států a .
A diskrétní čas Markovovy řetězce (DTMC) s přechodovou maticí a rovnovážné rozdělení se říká, že je v podrobné rovnováze, pokud jde o všechny páry a ,[6]
Pokud lze najít řešení, jako v případě CTMC, je výpočet obvykle mnohem rychlejší než přímé řešení rovnic globální rovnováhy.
Místní zůstatek
V některých situacích se termíny na obou stranách globálních rovnic ruší. Rovnice globálního vyvážení lze poté rozdělit tak, aby poskytovaly množinu lokální bilanční rovnice (také známý jako parciální bilanční rovnice,[2] nezávislé bilanční rovnice[7] nebo jednotlivé bilanční rovnice[8]).[1] Tyto rovnovážné rovnice byly poprvé zváženy Peter Whittle.[8][9] Výsledné rovnice jsou někde mezi detailní rovnováhou a rovnicemi globální rovnováhy. Jakékoli řešení k místním bilančním rovnicím je vždy řešením globálních bilančních rovnic (globální bilanční rovnice můžeme obnovit sečtením příslušných lokálních bilančních rovnic), ale obrácení není vždy pravdivé.[2] Konstrukce lokálních bilančních rovnic je často ekvivalentní odstranění vnějších součtů v globálních bilančních rovnicích pro určité termíny.[1]
Během 80. let se předpokládalo, že místní rovnováha je požadavkem pro distribuce rovnováhy produktu a formy,[10][11] ale Gelenbe je G-síť tento model ukázal, že tomu tak není.[12]
Poznámky
- ^ A b C Harrison, Peter G.; Patel, Naresh M. (1992). Modelování výkonu komunikačních sítí a počítačových architektur. Addison-Wesley. ISBN 0-201-54419-9.
- ^ A b C Kelly, F. P. (1979). Reverzibilita a stochastické sítě. J. Wiley. ISBN 0-471-27601-4.
- ^ Chandy, K.M. (Březen 1972). Msgstr "Analýza a řešení pro obecné fronty sítí". Proc. Šestá výroční konference v Princetonu o informačních vědách a systémech, Princeton U. Princeton, N.J. str. 224–228.
- ^ A b Grassman, Winfried K. (2000). Výpočetní pravděpodobnost. Springer. ISBN 0-7923-8617-5.
- ^ Bocharov, Pavel Petrovič; D'Apice, C .; Pechinkin, A.V .; Salerno, S. (2004). Teorie řazení. Walter de Gruyter. p. 37. ISBN 90-6764-398-X.
- ^ Norris, James R. (1998). Markovovy řetězy. Cambridge University Press. ISBN 0-521-63396-6. Citováno 2010-09-11.
- ^ Baskett, F .; Chandy, K. Mani; Muntz, R.R .; Palacios, F.G. (1975). "Otevřená, uzavřená a smíšená síť front s různými třídami zákazníků". Deník ACM. 22 (2): 248–260. doi:10.1145/321879.321887.
- ^ A b Whittle, P. (1968). "Rovnovážné distribuce pro otevřený migrační proces". Journal of Applied Probability. 5 (3): 567–571. doi:10.2307/3211921. JSTOR 3211921.
- ^ Chao, X .; Miyazawa, M. (1998). „Kvazi reverzibilita a místní zůstatek: alternativní odvození výsledků ve formě produktu“. Operační výzkum. 46 (6): 927–933. doi:10,1287 / opre.46.6.927. JSTOR 222945.
- ^ Boucherie, Richard J .; van Dijk, N.M. (1994). „Místní rovnováha ve frontách sítí s pozitivními a negativními zákazníky“. Annals of Operations Research. 48 (5): 463–492. doi:10.1007 / bf02033315. hdl:1871/12327.
- ^ Chandy, K. Mani; Howard, J.H., Jr.; Towsley, D.F. (1977). „Forma produktu a místní rovnováha v sítích zařazených do fronty“. Deník ACM. 24 (2): 250–263. doi:10.1145/322003.322009.
- ^ Gelenbe, Erol (Září 1993). "G-Networks se spuštěným pohybem zákazníků". Journal of Applied Probability. 30 (3): 742–748. doi:10.2307/3214781. JSTOR 3214781.