5.1 Markov Chains

Discrete-Time Markov Chains

A discrete-time Markov chain (DTMC) is a model used to represent systems that move randomly between states in discrete steps, where the future state depends only on the current state. Formally, a sequence of random variables $(X_n{)}_{n\in \mathbb{N}}$ is a DTMC on the state space $\mathcal{X}$ if it satisfies the Markov property,
$\mathbb{P}(X_{n+1}=x_{n+1}\mid X_n=x_n,\dots ,X_0=x_0)=\mathbb{P}(X_{n+1}=x_{n+1}\mid X_n=x_n)=P(x_n,x_{n+1}).$
When $\mathcal{X}$ is finite, the set of one-step transition probabilities $\{P(x_n,x_{n+1}):x_n,x_{n+1}\in \mathcal{X}\}$ can be organized into a row-stochastic one-step transition probability matrix $P\in {\mathbb{R}}^{|\mathcal{X}|\times |\mathcal{X}|}$, such that its rows sum to one. Then, the $k$-step transition equation is given as $P_k(x,y)=\mathbb{P}(X_k=y\mid X_0=x)=P^k(x,y)$.

States in $\mathcal{X}$ can be characterized using hitting times. The hitting time $T_x=\min \{n\in {\mathbb{Z}}_{+}:X_n=x\}$ of a state $x\in \mathcal{X}$ in a Markov chain is a random variable denoting the number of time steps required for the chain to visit $x$ for the first time. Let ${\rho }_{x,y}=\mathbb{P}(T_y<\infty \mid X_0=x)$ be the probability of reaching state $y$ when starting at state $x$. Then:

• State $x$ is transient if there’s a nonzero chance of never returning after leaving (i.e., ${\rho }_{x,x}<1$).
• State $x$ is recurrent if you’re guaranteed to return to it eventually (i.e., ${\rho }_{x,x}=1$). That is:
  • State $x$ is null recurrent if the chain takes an infinite amount of time, on average, to return to $x$ (i.e., $\mathbb{E}[T_x\mid X_0=x]=\infty$).
  • State $x$ is positive recurrent if $\mathbb{E}[T_x\mid X_0=x]<\infty$.
    • State $x$ is absorbing if you never leave it once you enter it (i.e., $\mathbb{E}[T_x\mid X_0=x]=0$).

We say that state $x$ communicates with state $y$ (i.e., $x\leftrightarrow y$) if it is possible to reach both state $y$ from state $x$ and state $x$ from state $y$, for which ${\rho }_{x,y}>0$ and ${\rho }_{y,x}>0$. A communicating class is a maximal set of states $C\subseteq \mathcal{X}$ which communicate with each other, such that $x\leftrightarrow y,\forall x,y\in C$. A Markov chain is irreducible if every state can be reached from every other state, such that $C=\mathcal{X}$. More particularly:

• If a finite Markov chain is irreducible, then it contains exclusively positive recurrent states.
• If an infinite Markov chain is irreducible, then it contains exclusively positive recurrent, null recurrent, or transient states.

Properties

(Chapman-Kolmogorov Eq.) $P^{k+\ell }(x,y)=\sum _{i\in \mathcal{X}}{P}^k(x,i)P^{\ell }(i,y)⟺P^{k+\ell }=P^k{P}^{\ell }$.

You might be asking why the frick is simple matrix multiplication an equation named after two mathematicians.

(Mean Hitting Time) $\mathbb{E}[T_x\mid X_0=x_0]=\{\begin{array}{ll}1+\sum _{i\in \mathcal{X}}P(x_0,i)\cdot \mathbb{E}[T_x\mid X_0=i]& \text{if }x\ne x_0\\ 0& \text{if }x=x_0\end{array}$

(Mean Total Visits) Let $N_x=\sum _{n\in \mathbb{N}}{1}_{\{X_n=x\}}$. Then, $\mathbb{E}[N_x\mid X_0=x]=\frac{{\rho }_x}{1-{\rho }_x}$ .

Note that this equation converges only for transient states.

(Mean Prob. of Reachability) $\mathbb{E}[T_x<T_y]$

Examples

Gambler's Ruin