Markov chain fundamentals
- State at time t
- Xt
- Transition probability
- Pij = P[ Xt+1 = j | Xt = i ]
- Distribution on states at time t
- q(t) = (q(t)1, q(t)2, q(t)3, ..., q(t)n ), where q(t)i =P[ Xt = i ]
- Stationary distribution
- A state distribution for which q(t+1) = q(t)
- t-step transition probability
- P(t)ij = P[ Xk+t = j | Xk = i ]
- First visit probability
- r(t)ij = P[ Xt = j and Xs != j for
1 <= s <= t-1 | X0 = i ]
- Total visit probability
- fij = sum of r(t)ij over all t > 0
- Expected visit time
- hij = sum of t * r(t)ij over all t > 0
if fij = 1, and infinity otherwise
- Transient state
- A state is transient if fii < 1
- Persistent state
- A state is persistent if fii = 1
- Null persistent state
- A state is null persistent if fii = 1 and hii is infinite.
(These don't occur in finite Markov chains.)
- Strong component
- A maximal subgraph in which every state is reachable from every other state
- Final strong component
- A strong component with no edges leaving the subgraph
- Irreducible Markov chain
- A Markov chain whose graph consists of a single strong component
- Periodic state
- A state is periodic if there are integers T > 1 and a so that for some
initial distribution if t is not of the form a + Ti then q(t)i = 0
- Aperiodic Markov chain
- A Markov chain with no periodic states
- Ergodic state
- A state that is aperiodic and (non-null) persistent
- Ergodic Markov chain
- A Markov chain is ergodic if all states are ergodic
The Fundamental Theorem of Markov Chains:
The following properties hold for any finite, irreducible, aperiodic Markov chain:
- All states are ergodic
- There is a unique stationary distribution. This distribution gives
nonzero probability to each state.
- Each state are persistent and the expected return time is the inverse
of the probability given that state by the stationary distribution
- If N(i, t) is the number of visits to state i in t steps, then the
limit of N(i, t)/t as t goes to infinity is the probability given to state i by the stationary distribution
Reference:
Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan,
Cambridge University Press, 1995