Misplaced Pages

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.

Global balance

The global balance equations (also known as full balance equations) 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

${\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.

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. If such a solution can be found the resulting equations are usually much easier than directly solving the global balance equations.

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 chain (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}$,

${\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, independent balance equations or individual balance equations). These balance equations were first considered by Peter Whittle. 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. Often, constructing local balance equations is equivalent to removing the outer summations in the global balance equations for certain terms.

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

Notes

1. ^ Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. ISBN 0-201-54419-9.
2. ^ 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. ^ 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. ^ 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.

v t e Queueing theory
Single queueing nodes	D/M/1 queue M/D/1 queue M/D/c queue M/M/1 queue Burke's theorem M/M/c queue M/M/∞ queue M/G/1 queue Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue
Arrival processes	Poisson point process Markovian arrival process Rational arrival process
Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network
Service policies	FIFO LIFO Processor sharing Round-robin Shortest job next Shortest remaining time
Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method
Limit theorems	Fluid limit Mean-field theory Heavy traffic approximation Reflected Brownian motion
Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue
Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering
Category

• Queueing theory