Math 311

Class 12

Symmetric Random Walk

• States: \(0, \pm 1, \pm 2, \dots\)

• Transition probabilities:

  • \(P_{i, i+1} = \frac{1}{2}\)
  • \(P_{i, i-1} = \frac{1}{2}\)

Irreducible.

Are all the states recurrent or transient?

An Observation

Given two states \(i\) and \(j\), define

\[f_{i,j} = \operatorname{P}\left(X_n = j \text{ for some } n > 0\mid X_0 = i\right)\]

If \(i\) is recurrent and \(i \leftrightarrow j\) then \(f_{i,j} = 1\).

Properties of Recurrent States

Let \(j\) be a recurrent state.

• Mean time to return:

  Assume \(X_0 = j\).

  Define \(N_j = \min\{n > 0\colon X_n = j\}\).

  Define \(m_j = \operatorname{E}(N_j \mid X_0 = j)\)

• Long run proportion:

  Define \(\displaystyle I_n = \begin{cases} 1 & \text{ if } X_n = j\\ 0 & \text{ otherwise} \end{cases}\)

  Define \(\displaystyle M_{jn} = \operatorname{E}\left(\sum_{k=1}^n I_k\right)\).

  Define \(\displaystyle\pi_j = \lim_{n\to\infty} \frac{M_{jn}}{n}\)

Suppose the Markov chain \(X\) is irreducible and recurrent. Then

\[\pi_j = \frac{1}{m_j}\]

regardless of the initial state \(X_0\)!

Further Classification

Definition: If \(j\) is a recurrent state and \(m_j < \infty\), we say that \(j\) is positive recurrent, otherwise it is null recurrent.

Equivalently:

• positive recurrent means \(\pi_j > 0\)
• null recurrent means \(p_j = 0\)