# 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

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 continuous time 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

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 (DTMC) 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 the global balance equations.

## Local balance

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

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). "Annals of Operations Research" 48. pp. 463–492. |chapter= ignored (help)
11. ^ Chandy, K. Mani; Howard, J.H., Jr; Towsley, D.F. (1977). "Journal of the ACM" 24. pp. 250–263. |chapter= ignored (help)
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.