This article is about Kolmogorov's criterion in the study of Markov chains. For Kolmogorov's criterion in the study of norms on topological vector spaces, see Kolmogorov's normability criterion.
The theorem states that an irreducible, positive recurrent, aperiodic Markov chain with transition matrixP is reversible if and only if its stationary Markov chain satisfies[1]
for all finite sequences of states
Here pij are components of the transition matrix P, and S is the state space of the chain.
ExampleEdit
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,
ProofEdit
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.
The proof for continuous-time Markov chains follows in the same way as the proof for discrete-time Markov chains.
ReferencesEdit
^ abKelly, Frank P. (1979). Reversibility and Stochastic Networks(PDF). Wiley, Chichester. pp. 21–25.
October 15, 2023
kolmogorov, criterion, this, article, about, study, markov, chains, study, norms, topological, vector, spaces, kolmogorov, normability, criterion, probability, theory, named, after, andrey, kolmogorov, theorem, giving, necessary, sufficient, condition, markov,. This article is about Kolmogorov s criterion in the study of Markov chains For Kolmogorov s criterion in the study of norms on topological vector spaces see Kolmogorov s normability criterion In probability theory Kolmogorov s criterion named after Andrey Kolmogorov is a theorem giving a necessary and sufficient condition for a Markov chain or continuous time Markov chain to be stochastically identical to its time reversed version Contents 1 Discrete time Markov chains 1 1 Example 2 Proof 3 Continuous time Markov chains 4 ReferencesDiscrete time Markov chains EditThe 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 1 p j 1 j 2 p j 2 j 3 p j n 1 j n p j n j 1 p j 1 j n p j n j n 1 p j 3 j 2 p j 2 j 1 displaystyle p j 1 j 2 p j 2 j 3 cdots p j n 1 j n p j n j 1 p j 1 j n p j n j n 1 cdots p j 3 j 2 p j 2 j 1 nbsp for all finite sequences of states j 1 j 2 j n S displaystyle j 1 j 2 ldots j n in S nbsp Here pij are components of the transition matrix P and S is the state space of the chain Example Edit nbsp 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 p i j p j l p l k p k i p i k p k l p l j p j i displaystyle p ij p jl p lk p ki p ik p kl p lj p ji nbsp Proof EditLet X displaystyle X nbsp be the Markov chain and denote by p displaystyle pi nbsp its stationary distribution such exists since the chain is positive recurrent If the chain is reversible the equality follows from the relation p j i p i p i j p j displaystyle p ji frac pi i p ij pi j nbsp Now assume that the equality is fulfilled Fix states s displaystyle s nbsp and t displaystyle t nbsp Then P X n 1 t X n i n X 0 s X 0 s displaystyle text P X n 1 t X n i n ldots X 0 s X 0 s nbsp p s i 1 p i 1 i 2 p i n t displaystyle p si 1 p i 1 i 2 cdots p i n t nbsp p s t p t s p t i n p i n i n 1 p i 1 s displaystyle frac p st p ts p ti n p i n i n 1 cdots p i 1 s nbsp p s t p t s P X n 1 displaystyle frac p st p ts text P X n 1 nbsp s X n displaystyle s X n nbsp i 1 X 0 t X 0 t displaystyle i 1 ldots X 0 t X 0 t nbsp Now sum both sides of the last equality for all possible ordered choices of n displaystyle n nbsp states i 1 i 2 i n displaystyle i 1 i 2 ldots i n nbsp Thus we obtain p s t n p s t p t s p t s n displaystyle p st n frac p st p ts p ts n nbsp so p s t n p t s n p s t p t s displaystyle frac p st n p ts n frac p st p ts nbsp Send n displaystyle n nbsp to displaystyle infty nbsp on the left side of the last From the properties of the chain follows that lim n p i j n p j displaystyle lim n to infty p ij n pi j nbsp hence p t p s p s t p t s displaystyle frac pi t pi s frac p st p ts nbsp which shows that the chain is reversible Continuous time Markov chains EditThe theorem states that a continuous time Markov chain with transition rate matrix Q is under any invariant probability vector reversible if and only if its transition probabilities satisfy 1 q j 1 j 2 q j 2 j 3 q j n 1 j n q j n j 1 q j 1 j n q j n j n 1 q j 3 j 2 q j 2 j 1 displaystyle q j 1 j 2 q j 2 j 3 cdots q j n 1 j n q j n j 1 q j 1 j n q j n j n 1 cdots q j 3 j 2 q j 2 j 1 nbsp for all finite sequences of states j 1 j 2 j n S displaystyle j 1 j 2 ldots j n in S nbsp The proof for continuous time Markov chains follows in the same way as the proof for discrete time Markov chains References Edit a b Kelly Frank P 1979 Reversibility and Stochastic Networks PDF Wiley Chichester pp 21 25 Retrieved from https en wikipedia org w index php title Kolmogorov 27s criterion amp oldid 1161986876, wikipedia, wiki, book, books, library,