06 - Markov Chains

State Space of a Random Process

Let $X_n$ for $n=0,1,\cdots$ be a sequence of random variables

State Space $I$ is set of values that $X_n$ take

Probability Distribution on $I$

Probability Distribution on $I$ is collection

$$\lambda =({\lambda }_i,i\in I)\text{ with }{\lambda }_i\ge 0\text{ for all }i$$

and

$$\sum _{i\in I}{\lambda }_i=1$$

Note that $\lambda$ is treated as a row vector

Markov Chain

Let $X=(X_0,X_1,X_2,\cdots )$ be a sequence of random variables taking value in $I$ then

Process $X$ is called a Markov Chain if

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

for all $n\ge 0,i_0,i_1,\cdots ,i_{n+1}\in I$

Note that Markov Chains are memoryless so future is independent of past given the present

Time-Homogeneous Markov Chain

Markov Chain $X=(X_0,X_1,\cdots )$ is Time-Homogeneous if

$$\mathbb{P}(X_{n+1}=j\mid X_n=i)\text{ is independent of }n$$

Transition Probabilities

Consider Time-Homogenous Markov Chain $X=(X_0,X_1,\cdots )$ then

Transition Probabilities is defined by

$$p_{i,j}\equiv p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$$

Homogenous Chain

Homogenous Chain is defined by

1. Initial Distribution $\lambda$ of $X_0$ where

$${\lambda }_i:=\mathbb{P}(X_0=0)\text{ for each }i\in I$$

2. Transition Matrix

$$P=(p_{ij}{)}_{i,j\in I}$$

where $P$ is a square matrix indexed by $I$ so $i$th row of $P$ is distribution of $X_{n+1}\mid X_n=i$

Note that $P$ is a stochastic matrix so every row of $P$ is a probability distribution

Markov Chain Distribution

Let $X$ be a Markov Chain with Initial Distribution $\lambda$ and Transition Matrix $P$ then

$$X\sim \mathrm{Markov}(\lambda ,P)$$

Notation for Conditional Probability and Expectation Given Initial State

Let $(X_n)$ be a Markov chain then

$$\begin{array}{rl}{\mathbb{P}}_i(\cdot )& :=\mathbb{P}(\cdot \mid X_0=i)\\ {\mathbb{E}}_i[\cdot ]& :=\mathbb{E}[\cdot \mid X_0=i]\end{array}$$

So ${\mathbb{P}}_i(X_1=j)=p_{ij}$.

$n$-Step Transition Probability

Let $X=(X_0,X_1,X_2,\cdots )$ be a Markov Chain with values in $I$

$n$-Step Transition Probability is defined by

$$p_{ij}^{(n)}=\mathbb{P}(X_{r+n}=j\mid X_r=i)$$

which holds independent of $r$

Functional Construction of a Markov Chain

Let $(X_n)$ be a Markov Chain
Let $(Y_n,n\ge 0)$ be a random process

If there exists function $f$ such that for all $n$

$$Y_{n+1}=f(Y_n,X_{n+1})$$

where $X_{n+1}$ is independent of $Y_0,Y_1,\cdots ,Y_n$ then

$$(Y_n)\text{ is a Markov Chain}$$

Proof

$$\begin{array}{rl}\mathbb{P}(Y_{n+1}& =i_{n+1}\mid Y_n=i_n,\cdots ,Y_0=i_0)\\ & =\mathbb{P}(f(i_n,X_{n+1})=i_{n+1}\mid Y_n=i_n,\cdots ,Y_0=i_0)\\ & =\mathbb{P}(f(i_n,X_{n+1})=i_{n+1})(\text{as }{X}_{n+1}\text{ is independent from }{Y}_0\cdots Y_n)\\ & =\mathbb{P}(f(i_n,X_{n+1})=i_{n+1}\mid Y_n=i_n)(\text{as }{X}_{n+1}\text{ is independent from }{Y}_n)\\ & =\mathbb{P}(Y_{n+1}=i_{n+1}\mid Y_n=i_n)\end{array}$$