Past exam of the mathematics course of the University of Cambridge / 2016 / ib / Paper 2 / 20H (Markov Chains)

Let $C$ be an open communicating class, and fix $i\in C$. There is a path of positive probability from $i$ to a state outside $C$. Choose a shortest such path, so it does not revisit $i$ before exiting. No state reached outside $C$ can have a path back to $C$: combined with the exit path and communication within $C$, such a path would put it in the same communicating class. Thus with positive probability the chain never returns to $i$. Its return probability is less than one, making $i$ a transient state. This proves transience throughout $C$.

Conversely, suppose a finite communicating class were both closed and transient. Starting inside it, a path stays there forever. Since it has finitely many states, at least one state must be visited infinitely often. But a transient state is visited only finitely often almost surely, and the union of finitely many exceptional null events still has probability zero. This is a contradiction. Every finite transient communicating class is therefore open.

For the infinite counterexample, take the biased random walk on $\mathbb{Z}$ with independent increments $+1$ of probability $3/4$ and $-1$ of probability $1/4$. All states communicate, so $\mathbb{Z}$ is one infinite closed communicating class. The strong law of large numbers gives $X_n/n\to 1/2$ almost surely. Consequently every fixed state is visited only finitely often, and the class is transient. Finiteness is exactly what fails in the preceding argument.

The states $b,d$ form a closed communicating class. Set $p_n=\mathbb{P}(X_n=b\mid X_0=d)$. Within this class,Its fixed point is $8/17$. Subtracting that fixed point and iterating gives the exact transition probability

Let $h$ be the probability of ever hitting $c$ starting at $a$. A first-step analysis gives a direct success with probability $1/3$, a return to the same problem with probability $1/3$, and entry into the closed class $\{b,d\}$ with probability $1/3$, after which $c$ cannot be reached. ThereforeThe possibility of infinitely many self-loops has probability zero and introduces no extra solution of this equation.

The only closed communicating class is $\{b,d\}$; the class $\{a,c\}$ is open and transient. Its one-step probability of staying inside is at most $2/3$, so if $\tau$ is the entrance time into $\{b,d\}$, then $\mathbb{P}(\tau >n)\le (2/3{)}^n$ for an initial state in $\{a,c\}$. Hence entrance occurs almost surely in finite time.

On $\{b,d\}$ it is an irreducible aperiodic Markov chain, because both states have positive self-loop probabilities. The finite irreducible aperiodic countable-state Markov chain convergence theorem says that its transition probabilities converge to its unique stationary distribution. The balance equation ${\pi }_b(3/4)={\pi }_d(2/3)$ with ${\pi }_b+{\pi }_d=1$ gives ${\pi }_b=8/17$ and ${\pi }_d=9/17$.

This limit also holds from $a,c$: condition on the finite entrance time and entrance state. For $\tau \le M$, convergence in the closed class applies to a finite sum; the remaining probability is bounded by $\mathbb{P}(\tau >M)$, which tends to zero as $M\to \infty$. Thus in the order $a,b,c,d$,