4.3a Markov Chains

Markov Chain

A discrete-time Markov chain is a sequence of random variables $(X_n{)}_{n\in \mathbb{N}}$, where the future only depends on the current state. Formally, $(X_n{)}_{n\in \mathbb{N}}$ is a Markov chain if and only 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}\times \mathcal{X}\}$ can be organized into a 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).$

Similarly, a sequence of random variables $(X_t{)}_{t\in {\mathbb{R}}_{+}}$ is a continuous-time Markov chain on $\mathcal{X}$ if it satisfies the continuous-time Markov property,
$\mathbb{P}(X_{t+\delta t}=x_{t+\delta t}\mid X_t=x_t,\dots ,X_0=x_0)=\mathbb{P}(X_{t+\delta t}=x_{t+\delta t}\mid X_t=x_t).$

Different from DTMCs, CTMCs employ a rate matrix

Dependence on Past States $X_n$ fully determines the distribution of the next state $X_{n+1}$ does not imply that $X_{n+1}$ is independent of all $X_{n-k}$ for $k\ge 1$. In general, the random variables in a Markov chain are not independent.

The fact that knowledge of the current state