A discrete time Markov chain is a stochastic process characterized by a sequence of random variables $\{X_n\}$ where $X_n \sim \pi n$ and the Markov property is obeyed ****(i.e. each $X_n$ in the sequence is conditionally independent of all previous elements given $X{n-1}$).
$$ \textbf{State Space }\mathcal{X} = \{1, \dots , m\} \\ \textbf{Initial Distribution } \pi _0 \in \R^{1 \times m} \hspace{60pt} \\ \textbf{State Transition Matrix } P \in \R^{m \times m}\hspace{84pt} $$
The following is a table of terminology used in the study of Markov chains.
| Terminology | Definition | Intuition |
|---|---|---|
| Accessible $i \rightarrow j$ | A state $j$ is accessible from $i$ if there exists an $n \in \N$$\Z$$n \in \N$$r_{ij}(n) > 0$. Moreover, we denote the set of all accessible states from $i$ as $A(i)$. | A state $j$ is reachable from $i$. |
| Communicating $i \leftrightarrow j$ | States $i$ and $j$ are communicating if $j \in A(i)$ and $i \in A(j)$. This is an equivalence relation on $\mathcal{X}$. | States $i$ and $j$ are reachable from each other. |
| Recurrent | A state $i$ is recurrent if for all $j \in A(i)$, $A(j) = A(i)$. | If $i$ is visited once, it is returned to infinitely often in the long term. |
| Transient | A state $i$ is transient if $i$ is not recurrent. | There exists a state $j$ accessible from $i$ for which traveling to guarantees $i$ will never be returned to. |
| Absorbing | A recurrent state $i$ is absorbing if $p_{ij} = 1$ when $i = j$ and $p_{ij} =0$ otherwise. | Absorbing states are never left. |
| Communicating Class | A communicating class $C$ is the maximal set of communicating states; i.e. it is the equivalence class of communicating states, so $A(i) = A(j)$ for all $i, j \in C$. | Everything in $C$ can reach everything in $C$. |
| Recurrent Class | A recurrent class $R$ ****is a communicating class which contains only recurrent states. Moreover, if $i$ is recurrent, $A(i)$ forms a recurrent class. | A recurrent class is a closed communicating class; i.e. once it is entered, it is never left. |
| Transient Class | A transient class $T$ ****is a communicating class which contains only transient states. | A transient class is an open communicating class; there is no guarantee that the chain will stay in it. |
| Irreducible | A Markov chain is irreducible if its state space forms a communication class; i.e. for any $i, j \in \mathcal{X}$, $A(i) = A(j)$. | Everything is reachable from everything. |
| Periodic | A recurrent class $R$ is periodic if there exists a partition $\{S_n\}{n=1}^d$, $d >1$, of $R$ such that all transitions from one subset is to another subset in a cyclic order; i.e. for $i \in S{k}$ and $p_{ij} > 0$ then $j \in S_{k+1}$ if $k < d$ and $j \in S_1$ if $k=d$. | States in $R$ are visited in some cyclic pattern. |
| Aperiodic | A recurrent class $R$ is aperiodic if it is not periodic. This is true if and only if there exists $n\geq 1$ and $i \in R$ s.t. for all $j \in R$, $r_{ij}(n) > 0$. | There is some state $i \in R$ which can reach every other state $j \in R$ in exactly the same number of timesteps. |
The probability $r_{ij}(n)$ of the Markov chain being in a state $j$ at a timestep $n$ given that it started in a state $i$ can be computed with the Chapman-Kolmogorov Equation.
$$ r_{ij}(n) = \sum {k=1}^m r{ik}(n-1)p_{kj} $$
$$ \pi_n = \pi _0 P^n $$
Chains with multiple recurrent classes may exhibit long term behavior which depends on whether or not the initial state is in a particular recurrent class. For this reason, we often decompose a Markov Chain into separate recurrent classes to study this long term behavior locally.
A Markov chain that contains a single aperiodic recurrent class guarantees that all states in the class are visited infinitely often without any dependence on an initial state. The steady state convergence theorem states that these state visits converge in distribution to a unique stationary distribution $\pi^*$.