Postscript version of this file

STAT 380 Lecture 10

Reading for Today's Lecture: Chapter 4 sections 1-3.

Goals of Today's Lecture:

• Define communicating classes

• Define recurrent, transient, periodic states.

Classification of States

State i leads to state j if ${\bf P}^n_{ij} > 0$ for some n. It is convenient to agree that ${\bf P}^0={\bf I}$ the identity matrix; thus i leads to i.

Note i leads to j and j leads to k implies i leads to k(Chapman-Kolmogorov).

States i and j communicate if i leads to j and j leads to i.

The relation of communication is an equivalence relation; it is reflexive, symmetric and transitive: if i and j communicate and j and k communicate then i and kcommunicate.

Example (+ signs indicate non-zero entries):

$${\bf P}= \left[\begin{array}{ccccc} 0& 1 & 0 & 0 &0 \\ 0 & 0... ...\\ + & 0 & 0 & + & 0 \\ 0 & + & 0 & + & + \end{array}\right]$$

For this example:

$1 \leadsto 2$, $2 \leadsto 3$, $3 \leadsto 1$ so 1,2,3 are all in the same communicating class.

$4 \leadsto 1, 2, 3$ but not vice versa.

$5 \leadsto 1,2,3,4$ but not vice versa.

So the communicating classes are

$$\{1,2,3\} \quad \{4\} \quad \{5\}$$

A Markov Chain is irreducible if there is only one communicating class.

Notation:

$$f_i=P(\exists n>0: X_n=i\vert X_0=i)$$

State i is recurrent if f_i=1, otherwise transient.

If f_i=1 then Markov property (chain starts over when it gets back to i) means prob return infinitely many times (given started in i or given ever get to i) is 1.

Consider chain started from transient i. Let N be number of visits to state i (including visit at time 0). To return m-1 times must return once then starting over return m-1 times, then never return. So:

P(N=m) = f_i^m-1(1-f_i)

for $m=1,2,\ldots$.

N has a Geometric distribution and ${\rm E}(N) = 1/(1-f_i)$.

Another calculation:

$$N=\sum_0^\infty 1(X_k=i)$$

so

$${\rm E}(N) = \sum_0^\infty P(X_k=i)$$

If we start the chain in state i then this is

$${\rm E}(N) = \sum_0^\infty {\bf P}^n_{ii}$$

and i is transient if and only if

$$\sum_0^\infty {\bf P}^n_{ii} < \infty \, .$$

For last example: 4 and 5 are transient. Claim: states 1, 2 and 3 are recurrent.

Proof: argument above shows each transient state is visited only finitely many times. So: there is a recurrent state. (Note use of finite number of states.) It must be one of 1, 2 and 3. Proposition: If one state in a communicating class is recurrent then all states in the communicating class are recurrent.

Proof: Let i be the known recurrent state so

$$\sum_n {\bf P}^n_{ii} = \infty$$

Assume i and j communicate. Find integers m and k such that

$${\bf P}^m_{ij} > 0$$

and

$${\bf P}^k_{ji} > 0$$

Then

$${\bf P}^{m+n+k}_{jj} \ge {\bf P}^k_{ji} {\bf P}^n_{ii}{\bf P}^m_{ij}$$

Sum RHS over n get $\infty$ so

$$\sum_n {\bf P}^n_{jj} = \infty$$

Proposition also means that if 1 state in a class is transient so are all.

State i has period d if d is greatest common divisor of

$$\{n: {\bf P}^n_{ii} > 0\}$$

If i and j are in the same class then i and j have same period. If d=1 then state i is called aperiodic; if d>1 then i is periodic.

$${\bf P}= \left[\begin{array}{ccccc} 0& 1 & 0 & 0 &0 \\ 0 & 0... ...\\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array}\right]$$

For this example $\{1,2,3\}$ is a class of period 3 states and $\{4,5\}$ a class of period 2 states.

$${\bf P}= \left[\begin{array}{ccc} 0& 1/2 & 1/2 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{array}\right]$$

has a single communicating class of period 2.

A chain is aperiodic if all its states are aperiodic.

Infinite State Spaces

Example: consider a sequence of independent coin tosses with probability pof Heads on a single toss. Let X_n be number of heads minus number of tails after n tosses. Put X₀=0.

X_n is a Markov Chain. State space is $\Bbb Z$, the integers and

$${\bf P}_{ij} = \begin{cases} p & j=i+1 \\ 1-p & j=i-1 \\ 0 & \text{otherwise} \end{cases}$$

This chain has one communicating class (for $p\neq 0,1$) and all states have period 2. According to the strong law of large numbers X_n/n converges to 2p-1. If $p\neq 1/2$ this guarantees that for all large enough n $X_n \neq 0$, that is, the number of returns to 0 is not infinite. The state 0 is then transient and so all states must be transient.

For p = 1/2 the situation is different. It is a fact that

$${\bf P}^n_{00} = P(\text{\char93 H = \char93 T at time $n$})$$

For n even this is the probability of exactly n/2 heads in n tosses.

Local Central Limit Theorem (normal approximation to P(-1/2 < X_n < 1/2)) (or Stirling's approximation) shows

$$\sqrt{2m}P(\text{Binomial}(2m,1/2) = m) \to (2\pi)^{-1/2}$$

so:

$$\sum_n {\bf P}^n_{00} = \infty$$

That is: 0 is a recurrent state.