07 - Class Structure of Markov Chains

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

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

Communicating Classes

Let $I$ be a state space then

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

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

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

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

Open Class

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

$C$ is open if it is not closed

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

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

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

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

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

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$

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

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

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$

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

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

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

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$

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)