05. Markov Chains - Introduction

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

Link to original

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

Link to original

---

5.1 Markov Chains

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

Link to original

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$$

Link to original

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)$$

Link to original

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

Link to original

Joint Distribution of a Markov Chain

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

For $i_0,i_1,\cdots ,i_n\in I$ then

$$\mathbb{P}(X_0=i_0,X_1=i_1,\cdots ,X_n=i_n)={\lambda }_{i_0}{p}_{i_0{i}_1}{p}_{i_1{i}_2}\cdots p_{i_{n-1}{i}_n}$$

Proof

$$\begin{array}{rl}\mathbb{P}(& X_0=i_0,X_1=i_1,\cdots ,X_n=i_n)\\ & =\mathbb{P}(X_0=i_0)\mathbb{P}(X_1=i_1\mid X_0=i_0)\mathbb{P}(X_2=i_2\mid X_1=i_1,X_0=i_0)\times \cdots \\ & \cdots \times \mathbb{P}(X_n=i_n\mid X_{n-1}=i_{n-1},\cdots ,X_0=i_0)\\ & =\mathbb{P}(X_0=i_0)\mathbb{P}(X_1=i_1\mid X_0=i_0)\mathbb{P}(X_2=i_2\mid X_1=i_1)\cdots \mathbb{P}(X_n=i_n\mid X_{n-1}=i_{n-1})\\ & ={\lambda }_{i_0}{p}_{i_0{i}_1}{p}_{i_1{i}_2}\cdots p_{i_{n-1}{i}_n}\end{array}$$

Link to original

Markov Chain Distribution

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

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

Link to original

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}$.

Link to original

---

5.2 $n$-Step Transition Probabilities

$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$

Link to original

Chapman-Kolmogorov Equations

$$p_{ij}^{(n+m)}=\sum _{k\in I}{p}_{ik}^{(n)}{p}_{kj}^{(m)}$$

$$p_{ij}^{(n)}=(P^n{)}_{i,j}$$

where $P^n$ is the $n$-th power of Transition Matrix

Proof

(1) Partition by value of intermediate state $X_n$, and apply Law of Total Probability

$$\begin{array}{rl}\mathbb{P}(X_{n+m}=j\mid X_0=i)& =\sum _k\mathbb{P}(X_n=k\mid X_0=i)\mathbb{P}(X_{n+m}=j\mid X_n=k,X_0=i)\\ & =\sum _k\mathbb{P}(X_n=k\mid X_0=i)\mathbb{P}(X_{n+m}=j\mid X_n=k)\\ & =\sum _k{p}_{ik}^{(n)}{p}_{kj}^{(m)}\end{array}$$

(2) Inductively

$$\begin{array}{rl}{p}_{ij}^{(2)}& =\sum _k{p}_{ik}{p}_{kj}=(P^2{)}_{i,j}\\ p_{ij}^{(3)}& =\sum _k{p}_{ik}^{(2)}{p}_{kj}^{(1)}=\sum _k(P^2{)}_{i,k}(P{)}_{k,j}=(P^{2}P{)}_{i,j}=(P^3{)}_{i,j}\end{array}$$

and so on

Link to original

Joint Distribution of a Markov Chain

Let $\lambda$ be the initial distribution (distribution of $X_0$ then

Distribution of $X_1$ is $\lambda P$
Generally distribution of $X_n$ is

$$\lambda P^n$$

Proof

Note that we treat $\lambda$ as a row vector

$$\begin{array}{rl}\mathbb{P}(X_n=j)& =\sum _i\mathbb{P}(X_0=i)\mathbb{P}(X_n=j\mid X_0=i)\\ & =\sum _i\mathbb{P}(X_0=i)\mathbb{P}(X_n=j\mid X_0=i)\\ & =\sum _i\mathbb{P}(X_0=i)p_{ij}^{(n)}\\ & =\sum _i{\lambda }_i(P^n{)}_{ij}\\ & =(\lambda P^n{)}_j\end{array}$$

Hence result follows

Link to original

---

5.3 A Few Examples

Refer to Lecture Note for examples - page 43

---

5.4 Exploring the Markov Property

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}$$

Link to original

---

5.5 Class Structure

Leads To

Let $i,j\in I$ then

$i$ leads to $j$ (also written as $i\to j$) if

$${\mathbb{P}}_i(X_n=j)>0\text{ for some }n\ge 0$$

Or equivalently

$$p_{ij}^{(n)}>0\text{ for some }n\ge 0$$

Note that $i\to j$ if you can reach state $j$ from state $i$ eventually

Link to original

Communication of States

Let $i,j\in I$ then

If $i\to j$ and $j\to i$ then

$$i\text{ communicates with }j\text{ or }i\leftrightarrow j$$

Link to original

Communicating Classes

Let $I$ be a state space then

$$\leftrightarrow \text{ is an equivalence relation}$$

so $\leftrightarrow$ partitions state space $I$ into communicating classes

Link to original

Closed Class

Let $I$ be a state space
Let $C\subseteq I$ be a class then

$C$ is closed if

$$p_{ij}=0\text{ for all }i\in C,j\notin C$$

Or equivalently

$$i\text{centernot}\to j\text{ for all }i\in C,j\notin C$$

Note that $C$ is closed if you can never escape that class

Link to original

Absorbing State

Let $I$ be a state space then

If $\{i\}$ is a closed class then

$$p_{ii}=1\text{ and }i\text{ is an absorbing state}$$

Link to original

Open Class

Let $I$ be a state space
Let $C\subseteq I$ be a class then

$C$ is open if it is not closed

Link to original

Irreducible

Let $I$ be a state space

$I$ is irreducible if it consists of a single communicating class so

$$i\to j\text{ for all }i,j\in I$$

Link to original

---

5.6 Periodicity

Period

Let $I$ be a state space then

Period of state $i\in I$ is defined by

$$\text{gcd of set}\{n:p_{ii}^{(n)}>0\}$$

Otherwise it is not defined

Note that it is essentially the gcd of the number of moves it takes to return back to itself

Link to original

Aperodic

Let $I$ be a state space then

State $i\in I$ is aperiodic if

$$i\text{ has period }1$$

Or equivalently

$$p_{ii}^{(n)}>0\text{ for all sufficiently large }n$$

Link to original

Period Is a Class Property

All states in a communicating class have the same period

Note that a class with an aperiodic state means every state is aperiodic

Proof

Suppose $i\leftrightarrow j$ and $d\mid n$ whenever $p_{ii}^{(n)}>0$

Since $i$ and $j$ communicate then

$$\exists a,b\text{ such that }{p}_{ij}^{(a)}>0\text{ and }{p}_{ji}^{(b)}>0$$

Then

$$p_{ii}^{(a+b)}>0$$

Suppose $p_{jj}^{(m)}>0$ then

$$p_{ii}^{(a+m+b)}>0$$

Then

$$d\mid (a+b)\text{ and }d\mid (a+m+b)$$

Hence

$$d\mid m$$

Thus

$$\{n:p_{ii}^{(n)}\}\text{ and }\{m:p_{jj}^{(m)}>0\}\text{ have the same divisors}$$

Hence have the same greatest common divisor

Link to original

---

5.7 Hitting Probabilities

Hitting / Absorbtion Probability

Let $A\subset I$ where $I$ is the state space then

Hitting Probability of $A$ starting from state $i$ is defined by

$$h_i^A={\mathbb{P}}_i(X_n\in A\text{ for some }n\ge 0)$$

where if $A$ is closed then $h_i^A$ is called the Absorption Probability

Link to original

Characterisation of Hitting Probabilities

Vector of Hitting Probabilities $(h_i^A,i\in I)$ is minimal non-negative solution to equations

$$h_i^A=\{\begin{array}{ll}1& \text{ if }i\in A\\ \sum _j{p}_{ij}{h}_j^A& \text{ if }i\notin A\end{array}$$

Note that minimal means that if $(x_i,i\in I)$ is another non-negative solution to system then $h_i\le x_i$ for all $i$

Proof

If $i\in A$ then $h_i^A=1$

Otherwise if $i\notin A$ then

$$\begin{array}{rl}{h}_i^A& ={\mathbb{P}}_i(X_n\in A\text{ for some }n\ge 0)\\ & ={\mathbb{P}}_i(X_n\in A\text{ for some }n\ge 1)\\ & =\sum _j{\mathbb{P}}_i(X_1=j)\mathbb{P}(X_n\in A\text{ for some }n\ge 1\mid X_0=i,X_1=j)\\ & =\sum _j{p}_{ij}\mathbb{P}(X_n\in A\text{ for some }n\ge 1\mid X_1=j)\\ & =\sum _j{p}_{ij}{h}_j^A\end{array}$$

Let $(x_i,i\in I)$ be any non-negative solution then
Prove by induction on $M$: For any $M\in \mathbb{N}$ and for all $i\in I$ then

$$x_i\ge {\mathbb{P}}_i(X_n\in A\text{ for some }n\le M)$$

For $M=0$ then

$$\text{LHS is }1\text{ for }i\in A\text{ and }\text{RHS is }0\text{ for }i\notin A$$

So it holds for $M=0$

Induction Step so suppose

$$x_i\ge {\mathbb{P}}_i(X_n\in A\text{ for some }n\le M-1)\text{ for all }i\in I$$

If $i\in A$ then $x_i=1$ so holds
Otherwise If $i\notin A$ then

$$\begin{array}{rl}{\mathbb{P}}_i(X_n\in A\text{ for some }n\le M)& =\sum _j{p}_{ij}{\mathbb{P}}_i(X_n\in A\text{ for some }n\in \{1,2,\cdots M\}\mid X_1=j)\\ & =\sum _j{p}_{ij}{\mathbb{P}}_j(X_n\in A\text{ for some }n\in \{0,1,\cdots ,M-1\})\\ & \le \sum _j{p}_{ij}{x}_j\\ & =x_i\end{array}$$

Hence induction step is complete

So statement holds for all $i$ and $M$

So as sequence of events $x_i\ge {\mathbb{P}}_i(X_n\in A\text{ for some }n\le M)$ is increasing in $M$ then

$$\begin{array}{rl}{x}_i& \ge \underset{M\to \infty }{\lim }{\mathbb{P}}_i(X_n\in A\text{ for some }n\le M)\\ & ={\mathbb{P}}_i\left(\bigcup _M\{X_n\in A\text{ for some }n\le M\}\right)\\ & ={\mathbb{P}}_i(X_n\in A\text{ for some }n)\\ & =h_i^A\end{array}$$

Link to original

Gambler's Ruin

Let

$$\begin{array}{rlrl}{p}_{00}& =1& & \\ p_{i,i-1}& =q=1-p& & \text{ for }i\ge 1\\ p_{i,i+1}& =p& & \text{ for }i\ge 1\end{array}$$

Then

Hitting probabilities $h_i={\mathbb{P}}_i(\text{hit }0)$ are

• $p<q$: Certain Ruin

$$h_i=1\text{ for all }i$$

• $p=q$: Certain Ruin - No Drift

$$h_i=1\text{ for all }i$$

• $p>q$: Positive Probability of Escape

$$h_i={\left(\frac{q}{p}\right)}^i$$

Obtained by solving the minimal non-negative solution to $h_0=1$, $h_i=p{h}_{i+1}+q{h}_{i-1}$ for $i\ge 1$

Link to original

---

5.8 Recurrence and Transience

Transient State

State $i\in I$ is transient if

$${\mathbb{P}}_i(X_n=i\text{ for some }n\ge 1)=p<1$$

Then total number of visits to $i$ has geometric distribution with parameter $1-p$

$${\mathbb{P}}_i(\text{hit }i\text{ infinitely often})=0$$

Link to original

Recurrent State

State $i\in I$ is transient if

$${\mathbb{P}}_i(X_n=i\text{ for some }n\ge 1)=1$$

Then

$${\mathbb{P}}_i(\text{hit }i\text{ infinitely often})=1$$

Link to original

Characterisation of Recurrence via Return Probabilities

Let $I$ be a state space then

State $i\in I$ is recurrent if and only if

$$\sum _{n=0}^{\infty }{p}_{ii}^{(n)}=\infty$$

Proof

Total number of visits to $i$ is

$$\sum _{n=0}^{\infty }1(X_n=i)$$

which as expectation

$$\sum _{n=0}^{\infty }\mathbb{E}[1(X_n=i)]=\sum _{n=0}^{\infty }\mathbb{P}(X_n=i)=\sum _{n=0}^{\infty }{p}_{ii}^{(n)}$$

If $i$ is transient then total number of visits to $i$ is geometric with parameter $1-p$ hence

$$\text{mean }=\frac{1}{1-p}<\infty$$

Otherwise if $i$ is recurrent then number of visits to $i$ is infinite with probability $1$ hence

$$\text{mean }=\infty$$

Link to original

Recurrence and Transience Are Class Properties

Let $C$ be a communicating class

1. Either all states in $C$ are recurrent or all are transient
   In which case the whole class is referred to as recurrent or transient

2. Every recurrent class is closed

3. Every finite closed class is recurrent

Link to original

---

5.9 Random Walk in ${\mathbb{Z}}^d$

5.9.1-4 - $d=1,2,3,4$

Recurrence and Transience of Simple Random Walk in ${\mathbb{Z}}^d$

Simple symmetric random walk on ${\mathbb{Z}}^d$ is:

• Recurrent for $d=1$ and $d=2$
• Transient for $d\ge 3$

Proved using Stirling’s formula: $p_{00}^{(2m)}$ decays like $m^{-d/2}$, which sums to $\infty$ iff $d\le 2$

Link to original

---

5.9.5 Mean Hitting Time

First Hitting Time

Let $A\subset I$ be a subset of State Space then

First Hitting-Time of set $A$ is defined by

$$H^A=\min \{n:X_n\in A\}$$

with property

$$h_i^A={\mathbb{P}}_i(H^A<\infty )$$

Note that $H^A$ can take infinity

Link to original

Mean Hitting Time

Let $A\subset I$ be a subset of State Space then

Mean Hitting Time of $A$ from $i$ is defined by

$$k_i^A={\mathbb{E}}_i[H^A]$$

If $h_i^A<1$ then

$${\mathbb{P}}_i(H^A=\infty )>0⟹k_i^A=\infty$$

Link to original

Characterisation of Mean Hitting Times

Let $I$ be the state space then

Vector of Mean Hitting Times

$$k^A=(k_i^A,i\in I)$$

is the minimal non-negative solution to

$$k_i^A=\{\begin{array}{ll}0& \text{ if }i\in A\\ 1+{\sum }_j{p}_{ij}{k}_j^A& \text{ if }i\notin A\end{array}$$

Proof

Condition on first jump so for $i\notin A$

$$\begin{array}{rl}{k}_i^A& ={\mathbb{E}}_i[H^A]=\sum _j{\mathbb{E}}_i[H^A\mid X_1=j]{\mathbb{P}}_i(X_1=j)\\ & =\sum _j{p}_{ij}(1+k_j^A)\\ & =1+\sum _j{p}_{ij}{k}_j^A\end{array}$$

Minimality can be shown using similar idea to Characterisation of Hitting Probabilities

Link to original

---

5.9.6 Gambler’s Ruin Continued

Mean Hitting Times for Gambler's Ruin

The expected time $k_i={\mathbb{E}}_i(H_0)$ satisfies $k_i=\beta i$. Then:

• $p<q$: Finite Mean Hitting Time

$$k_i=\frac{i}{q-p}$$

• $p>q$:

$$k_i=\infty \text{ as }{h}_i<1$$

• $p=q$: Hits $0$ with probability $1$, but mean time is infinite

$$k_i=\infty$$

Link to original

---

5.10 Null Recurrence and Positive Recurrence

Mean Return Time

Let $I$ be a state space then

Mean Return Time for state $i$ is defined by

$$\begin{array}{rl}{m}_i& :={\mathbb{E}}_i[\min \{n\ge 1:X_n=i\}]\\ & =1+\sum p_{ij}{k}_j^{\{i\}}\end{array}$$

where $k_j^{\{i\}}$ is the mean hitting time of $i$ starting from $j$

Link to original

Null Recurrence and Positive Recurrence

Let $m_i={\mathbb{E}}_i(T_i)$ be the mean return time to state $i$

Let $i$ be recurrent then

1. If $m_i=\infty$ then

$$i\text{ is null recurrent }$$

2. If $m_i<\infty$ then

$$i\text{ is positive recurrent }$$

If $i$ is transient then $m_i=\infty$ trivially (return time is infinite with positive probability)

Link to original