Jump to content

Balance equation

From Wikipedia, the free encyclopedia
(Redirected from Global balance equation)

In probability theory, a balance equation is an equation that describes the probability flux associated with a Markov chain in and out of states or set of states.[1]

Global balance

[edit]

The global balance equations (also known as full balance equations[2]) are a set of equations that characterize the equilibrium distribution (or any stationary distribution) of a Markov chain, when such a distribution exists.

For a continuous time Markov chain with state space , transition rate from state to given by and equilibrium distribution given by , the global balance equations are given by[3]

or equivalently

for all . Here represents the probability flux from state to state . So the left-hand side represents the total flow from out of state i into states other than i, while the right-hand side represents the total flow out of all states into state . In general it is computationally intractable to solve this system of equations for most queueing models.[4]

Detailed balance

[edit]

For a continuous time Markov chain (CTMC) with transition rate matrix , if can be found such that for every pair of states and

holds, then by summing over , the global balance equations are satisfied and is the stationary distribution of the process.[5] If such a solution can be found the resulting equations are usually much easier than directly solving the global balance equations.[4]

A CTMC is reversible if and only if the detailed balance conditions are satisfied for every pair of states and .

A discrete time Markov chain (DTMC) with transition matrix and equilibrium distribution is said to be in detailed balance if for all pairs and ,[6]

When a solution can be found, as in the case of a CTMC, the computation is usually much quicker than directly solving the global balance equations.

Local balance

[edit]

In some situations, terms on either side of the global balance equations cancel. The global balance equations can then be partitioned to give a set of local balance equations (also known as partial balance equations,[2] independent balance equations[7] or individual balance equations[8]).[1] These balance equations were first considered by Peter Whittle.[8][9] The resulting equations are somewhere between detailed balance and global balance equations. Any solution to the local balance equations is always a solution to the global balance equations (we can recover the global balance equations by summing the relevant local balance equations), but the converse is not always true.[2] Often, constructing local balance equations is equivalent to removing the outer summations in the global balance equations for certain terms.[1]

During the 1980s it was thought local balance was a requirement for a product-form equilibrium distribution,[10][11] but Gelenbe's G-network model showed this not to be the case.[12]

Notes

[edit]
  1. ^ a b c Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. ISBN 0-201-54419-9.
  2. ^ a b c Kelly, F. P. (1979). Reversibility and stochastic networks. J. Wiley. ISBN 0-471-27601-4.
  3. ^ Chandy, K.M. (March 1972). "The analysis and solutions for general queueing networks". Proc. Sixth Annual Princeton Conference on Information Sciences and Systems, Princeton U. Princeton, N.J. pp. 224–228.
  4. ^ a b Grassman, Winfried K. (2000). Computational probability. Springer. ISBN 0-7923-8617-5.
  5. ^ Bocharov, Pavel Petrovich; D'Apice, C.; Pechinkin, A.V.; Salerno, S. (2004). Queueing theory. Walter de Gruyter. p. 37. ISBN 90-6764-398-X.
  6. ^ Norris, James R. (1998). Markov Chains. Cambridge University Press. ISBN 0-521-63396-6. Retrieved 2010-09-11.
  7. ^ Baskett, F.; Chandy, K. Mani; Muntz, R.R.; Palacios, F.G. (1975). "Open, closed and mixed networks of queues with different classes of customers". Journal of the ACM. 22 (2): 248–260. doi:10.1145/321879.321887.
  8. ^ a b Whittle, P. (1968). "Equilibrium Distributions for an Open Migration Process". Journal of Applied Probability. 5 (3): 567–571. doi:10.2307/3211921. JSTOR 3211921.
  9. ^ Chao, X.; Miyazawa, M. (1998). "On Quasi-Reversibility and Local Balance: An Alternative Derivation of the Product-Form Results". Operations Research. 46 (6): 927–933. doi:10.1287/opre.46.6.927. JSTOR 222945.
  10. ^ Boucherie, Richard J.; van Dijk, N.M. (1994). "Local balance in queueing networks with positive & negative customers". Annals of Operations Research. 48 (5): 463–492. doi:10.1007/bf02033315. hdl:1871/12327.
  11. ^ Chandy, K. Mani; Howard, J.H. Jr; Towsley, D.F. (1977). "Product form and local balance in queueing networks". Journal of the ACM. 24 (2): 250–263. doi:10.1145/322003.322009.
  12. ^ Gelenbe, Erol (Sep 1993). "G-Networks with Triggered Customer Movement". Journal of Applied Probability. 30 (3): 742–748. doi:10.2307/3214781. JSTOR 3214781.