# 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 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 ${\displaystyle {\mathcal {S}}}$, transition rate from state ${\displaystyle i}$ to ${\displaystyle j}$ given by ${\displaystyle q_{ij}}$ and equilibrium distribution given by ${\displaystyle \pi }$, the global balance equations are given by[3]

${\displaystyle \pi _{i}=\sum _{j\in S}\pi _{j}q_{ji},}$

or equivalently

${\displaystyle \pi _{i}\sum _{j\in S\setminus \{i\}}q_{ij}=\sum _{j\in S\setminus \{i\}}\pi _{j}q_{ji}.}$

for all ${\displaystyle i\in S}$. Here ${\displaystyle \pi _{i}q_{ij}}$ represents the probability flux from state ${\displaystyle i}$ to state ${\displaystyle j}$. 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 ${\displaystyle j\neq i}$ into state ${\displaystyle i}$. In general it is computationally intractable to solve this system of equations for most queueing models.[4]

## Detailed balance

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

${\displaystyle \pi _{i}q_{ij}=\pi _{j}q_{ji}}$

holds, then by summing over ${\displaystyle j}$, the global balance equations are satisfied and ${\displaystyle \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 ${\displaystyle i}$ and ${\displaystyle j}$.

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

${\displaystyle \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 ${\displaystyle \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.
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 and negative customers". Annals of Operations Research. 48: 463–492. doi:10.1007/bf02033315.
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: 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.