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 o ...
, Kolmogorov's criterion, named after
Andrey Kolmogorov
Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Sovi ...
, is a
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of th ...
giving a necessary and sufficient condition for a
Markov chain
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
or
continuous-time Markov chain
A continuous-time Markov chain (CTMC) is a continuous stochastic process in which, for each state, the process will change state according to an exponential random variable and then move to a different state as specified by the probabilities of ...
to be stochastically identical to its time-reversed version.
Discrete-time Markov chains
The theorem states that an irreducible, positive recurrent, aperiodic Markov chain with
transition matrix ''P'' is
reversible if and only if its stationary Markov chain satisfies
:
for all finite sequences of states
:
Here ''p
ij'' are components of the transition matrix ''P'', and ''S'' is the state space of the chain.
Example
Consider this figure depicting a section of a Markov chain with states ''i'', ''j'', ''k'' and ''l'' and the corresponding transition probabilities. Here Kolmogorov's criterion implies that the product of probabilities when traversing through any closed loop must be equal, so the product around the loop ''i'' to ''j'' to ''l'' to ''k'' returning to ''i'' must be equal to the loop the other way round,
:
Proof
Let
be the Markov chain and denote by
its stationary distribution (such exists since the chain is positive recurrent).
If the chain is reversible, the equality follows from the relation
.
Now assume that the equality is fulfilled. Fix states
and
. Then
:
.
Now sum both sides of the last equality for all possible ordered choices of
states
. Thus we obtain
so
. Send
to
on the left side of the last. From the properties of the chain follows that
, hence
which shows that the chain is reversible.
Continuous-time Markov chains
The theorem states that a
continuous-time Markov chain
A continuous-time Markov chain (CTMC) is a continuous stochastic process in which, for each state, the process will change state according to an exponential random variable and then move to a different state as specified by the probabilities of ...
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 ↔ ...
''Q'' is
reversible if and only if its transition probabilities satisfy
:
for all finite sequences of states
:
The proof for continuous-time Markov chains follows in the same way as the proof for discrete-time Markov chains.
References
Markov processes