Kingman's formula: Difference between revisions
Jump to navigation
Jump to search
en>Helpful Pixie Bot m ISBNs (Build KE) |
en>Gareth Jones add link to probability theory in lead |
||
| Line 1: | Line 1: | ||
In [[probability theory]], '''Kolmogorov's criterion''', named after [[Andrey Kolmogorov]], is a [[theorem]] in a necessary and sufficient condition for a [[Markov chain]] or [[continuous-time Markov chain]] to be stochastically identical to its time-reversed version. | |||
==Discrete-time Markov chains== | |||
The theorem states that a Markov chain with [[transition matrix]] ''P'' is [[time reversibility|reversible]] if and only if its transition probabilities satisfy<ref name="kelly">{{cite book|first=Frank P.|last= Kelly|authorlink=Frank P. Kelly|title= Reversibility and Stochastic Networks |publisher=Wiley, Chichester|year= 1979|pages=21-25|url=http://www.statslab.cam.ac.uk/~frank/BOOKS/book/whole.pdf}}</ref> | |||
: <math>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}</math> | |||
for all finite sequences of states | |||
: <math>j_1, j_2, \ldots, j_n \in S .</math> | |||
Here ''p<sub>ij</sub>'' are elements of the transition matrix ''P'' and ''S'' is the state space of the chain. | |||
===Example=== | |||
[[File:Kolmogorov criterion dtmc.svg]] | |||
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, | |||
:<math>p_{ij}p_{jl}p_{lk}p_{ki} = p_{ik}p_{kl}p_{lj}p_{ji}.</math> | |||
==Continuous-time Markov chains== | |||
The theorem states that a [[continuous-time Markov chain]] with [[transition rate matrix]] ''Q'' is [[time reversibility|reversible]] if and only if its transition probabilities satisfy<ref name="kelly" /> | |||
: <math>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}</math> | |||
for all finite sequences of states | |||
: <math>j_1, j_2, \ldots, j_n \in S .</math> | |||
==References== | |||
<references/> | |||
[[Category:Markov processes]] | |||
Revision as of 11:57, 27 September 2013
In probability theory, Kolmogorov's criterion, named after Andrey Kolmogorov, is a theorem in a necessary and sufficient condition for a Markov chain or continuous-time Markov chain to be stochastically identical to its time-reversed version.
Discrete-time Markov chains
The theorem states that a Markov chain with transition matrix P is reversible if and only if its transition probabilities satisfy[1]
for all finite sequences of states
Here pij are elements of the transition matrix P and S is the state space of the chain.
Example
File:Kolmogorov criterion dtmc.svg
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,
Continuous-time Markov chains
The theorem states that a continuous-time Markov chain with transition rate matrix Q is reversible if and only if its transition probabilities satisfy[1]
for all finite sequences of states
References
- ↑ 1.0 1.1 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534