Math 311

Class 11

Accessible states

Definition: State \(j\) is accessible from state \(i\) if \(P^n_{ij} > 0\) for some \(n\).

Definition: States \(i\) and \(j\) communicate (denoted \(i \leftrightarrow j\)) if \(i\) is accessible from \(j\) and \(j\) is accessible from \(i\).

• \(i \leftrightarrow i\) (reflexivity)
• If \(i \leftrightarrow j\) then \(j \leftrightarrow i\) (symmetry)
• If \(i \leftrightarrow j\) and \(j \leftrightarrow k\) then \(i \leftrightarrow k\) (transitivity)

\({}\leftrightarrow{}\) is an equivalence relation on the set of all states.

It splits the set of states into equivalence classes

Definition: A Markov chain is irreducible if it only has one class.

Weather model question

• \(0\): sunny
• \(1\): rainy

\[\mathbf{P} = \begin{bmatrix} .9 & .1 \\ .4 & .6 \end{bmatrix}\]

Question: Suppose it rains on day 1. What is the probability that it will never rain again?

Question: Suppose it rains on day 1. What is the probability that it will rain again sometimes in the future?

Gambling model question

\[\mathbf{P} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ .3 & 0 & .7 & 0 \\ 0 & .3 & 0 & .7 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}\]

Question: If you start with $1, what is the probability you will never have exactly $1 again?

Question: If you start with $1, what is the probability you will have exactly $1 again some time in the future?

Classification of States

Given a state \(i\), define:

• \(g_i = {}\) the probability that, when starting in state \(i\), you will never return to state \(i\).
• \(f_i = 1 - g_i = {}\) the probability that, when starting in state \(i\), you will eventually return to state \(i\) in the future.

We say that state \(i\) is:

• recurrent if \(f_i = 1\)
• transient if \(f_i < 1\)

Let \(N_i = {}\) the total number of times the process is the state \(i\).

The state is recurrent if and only if \(\operatorname{E} N_i = \infty\).

Example 1

\[ \begin{bmatrix} 0.7 & 0.3 & 0 & 0 \\ 0.4 & 0.6 & 0 & 0 \\ 0 & 0 & 0.2 & 0.8 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

Which states are recurrent and which are transient?

Example 2

\[ \begin{bmatrix} 0.7 & 0.3 & 0 & 0 \\ 0.4 & 0.5 & 0.1 & 0 \\ 0 & 0 & 0.2 & 0.8 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

Which states are recurrent and which are transient?

Classification and classes

Proposition:

State \(i\) is

• recurrent if \(\displaystyle\sum_{n=1}^{\infty} P^n_{i,i} = \infty\)
• transient if \(\displaystyle\sum_{n=1}^{\infty} P^n_{i,i} < \infty\)

Proposition:

If \(i\) is recurrent and \(j\) communicates with \(i\), then \(j\) is also recurrent.

Corollary:

If \(i\) is transient and \(j\) communicates with \(i\), then \(j\) is also transient.

Note:

A finite Markov chain must have a recurrent state.