### Markov chain fundamentals

- State at time t
- X
_{t}

- Transition probability
- P
_{ij} = P[ X_{t+1} = j | X_{t} = 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[ X_{t} = i ]

- Stationary distribution
- A state distribution for which
**q**^{(t+1)} = **q**^{(t)}

- t-step transition probability
- P
^{(t)}_{ij} = P[ X_{k+t} = j | X_{k} = i ]

- First visit probability
- r
^{(t)}_{ij} = P[ X_{t} = j and X_{s} != j for
1 <= s <= t-1 | X_{0} = i ]

- Total visit probability
- f
_{ij} = sum of r^{(t)}_{ij} over all t > 0

- Expected visit time
- h
_{ij} = sum of t * r^{(t)}_{ij} over all t > 0
if f_{ij} = 1, and infinity otherwise

- Transient state
- A state is transient if f
_{ii} < 1

- Persistent state
- A state is persistent if f
_{ii} = 1

- Null persistent state
- A state is null persistent if f
_{ii} = 1 and h_{ii} 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