Markov chain fundamentals

State at time t

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:
  1. All states are ergodic
  2. There is a unique stationary distribution. This distribution gives nonzero probability to each state.
  3. Each state are persistent and the expected return time is the inverse of the probability given that state by the stationary distribution
  4. 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


Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995