Balance equation
Encyclopedia
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.
, the global balance equations are given for every state i in S by
Here
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.
For a discrete time Markov chain with transition matrix P and equilibrium distribution
the global balance equation is
For a continuous time Markov chain with generator matrix Q if
can be found such that for every pair of states i and j
holds, then the global balance equations are satisfied and
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 i and j.
A discrete time Markov chains with transition matrix P and equilibrium distribution
is said to be in detailed balance if for all pairs i and j,
When a solution can be found, as in the case of a CTMC, the computation is usually much quicker than directly solving.
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 it 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.
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, a balance equation is an equation
Equation
An equation is a mathematical statement that asserts the equality of two expressions. In modern notation, this is written by placing the expressions on either side of an equals sign , for examplex + 3 = 5\,asserts that x+3 is equal to 5...
that describes the probability flux associated with a Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
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 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 q(i,j) and equilibrium distribution given by, the global balance equations are given for every state i in S by
Here
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.For a discrete time Markov chain with transition matrix P and equilibrium distribution
the global balance equation is
Detailed balance
- See article detailed balanceDetailed balanceThe principle of detailed balance is formulated for kinetic systems which are decomposed into elementary processes : At equilibrium, each elementary process should be equilibrated by its reverse process....
For a continuous time Markov chain with generator matrix Q if
can be found such that for every pair of states i and j
holds, then the global balance equations are satisfied and
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 i and j.
A discrete time Markov chains with transition matrix P and equilibrium distribution
is said to be in detailed balance if for all pairs i and j,
When a solution can be found, as in the case of a CTMC, the computation is usually much quicker than directly solving.
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 or independent balance equations). 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 it 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
Product form solution
In probability theory, a product form solution is a particularly efficient form of solution for determining some metric of a system with distinct sub-components, where the metric for the collection of components can be written as a product of the metric across the different components...
, but Gelenbe
Erol Gelenbe
Sami Erol Gelenbe is a Turkish computer scientist, engineer and applied mathematician who currently holds the Dennis Gabor Professorship at Imperial College...
's G-network model showed this not to be the case.