Discrete-Time Markov Chain

Definition

A discrete-time Markov chain (DTMC) is a stochastic process $(X_n)_{n \geq 0}$ taking values in a countable state space $S$ that satisfies the Markov Property: for all $n \geq 0$ and all states $i_0, \dots, i_{n+1} \in S$,

$$ \mathbb{P}(X_{n+1} = i_{n+1} \mid X_0 = i_0, \dots, X_n = i_n) = \mathbb{P}(X_{n+1} = i_{n+1} \mid X_n = i_n). $$

The chain is fully specified by:

  1. An initial distribution $\lambda$ on $S$, where $\lambda_i = \mathbb{P}(X_0 = i)$.
  2. A Transition Matrix $P = (p_{ij})_{i,j \in S}$ with $p_{ij} = \mathbb{P}(X_{n+1} = j \mid X_n = i)$.

Time-homogeneity

A DTMC is time-homogeneous if the transition probabilities do not depend on $n$:

$$ \mathbb{P}(X_{n+1} = j \mid X_n = i) = p_{ij} \quad \text{for all } n \geq 0. $$

Unless stated otherwise, Markov chains in this course are assumed time-homogeneous.