In
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set ...
, 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
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous ...
with state space
, transition rate from state
to
given by
and equilibrium distribution given by
, the global balance equations are given by
::
or equivalently
::
for all
. Here
represents the probability flux from state
to state
. 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
into state
. In general it is computationally intractable to solve this system of equations for most queueing models.
Detailed balance
For a
continuous time Markov chain
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous ...
(CTMC) with
transition rate matrix
Transition or transitional may refer to:
Mathematics, science, and technology Biology
* Transition (genetics), a point mutation that changes a purine nucleotide to another purine (A ↔ G) or a pyrimidine nucleotide to another pyrimidine (C ↔ ...
, if
can be found such that for every pair of states
and
::
holds, then by summing over
, 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
and
.
A
discrete time Markov chain
In probability, a discrete-time Markov chain (DTMC) is a sequence of random variables, known as a stochastic process, in which the value of the next variable depends only on the value of the current variable, and not any variables in the past. Fo ...
(DTMC) with transition matrix
and equilibrium distribution
is said to be in detailed balance if for all pairs
and
,
::
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
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
In queueing theory, a discipline within the mathematical theory of probability, a G-network (generalized queueing network, often called a Gelenbe network) is an open network of G-queues first introduced by Erol Gelenbe as a model for queueing syst ...
model showed this not to be the case.
Notes
{{Queueing theory
Queueing theory