Balance equation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about balance equations in probability theory. For the concept of balanced equations in chemistry, see chemical 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 in principle can always be solved to give the equilibrium distribution of a Markov chain (when such a distribution exists). For a Markov chain with state space S, transition rate from state i to j given by qij and equilibrium distribution given by \scriptstyle{\pi}, the global balance equations are given for every state i in S by[3]

\sum_{j \in S\setminus \{i\}} \pi_i q_{ij} = \sum_{j \in S\setminus \{i\}} \pi_j q_{ji}.

Here \pi_i q_{ij} represents the probability flux from state i to state j. In general it is computationally intractable to solve this system of equations for most queueing models.[4]

For a discrete time Markov chain with transition matrix P and equilibrium distribution \pi the global balance equation is

\sum_{j \in S\setminus \{i\}} \pi_i p_{ij} = \sum_{j \in S\setminus \{i\}} \pi_j p_{ji}.

Detailed balance[edit]

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

\pi_i q_{ij} = \pi_j q_{ji}

holds, then the global balance equations are satisfied and \pi 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 i and j.

A discrete time Markov chains with transition matrix P and equilibrium distribution \pi is said to be in detailed balance if for all pairs i and j,[6]

\pi_i p_{ij} = \pi_j p_{ji}.

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

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 \pi 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: 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.  edit
  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.  edit
  10. ^ Boucherie, Richard J.; van Dijk, N.M. (1994). "Local balance in queueing networks with positive and negative customers". Annals of Operations Research 48. pp. 463–492. 
  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. pp. 250–263. 
  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.