Past exam of the probability course of the University of Oxford / 2014 / 3

Write the stationary distribution as a row vector $\pi =(a,b,c,d)$. For the first transition matrix, $\pi P=\pi$ gives $a=a/2+d$, $b=a/2+b/2$, $c=b/2$ and $d=c$. Hence $b=a$ and $c=d=a/2$. Normalization yieldsBy the stated common-stationary distribution property, this is also the answer for the second transition matrix.

The first Markov chain is a finite irreducible Markov chain: its positive-probability directed cycle reaches all four states. The self-loop at state 1 makes it an aperiodic Markov chain. Convergence to an invariant distribution therefore givesThe second chain alternates between the sets $\{1,3\}$ and $\{2,4\}$. It is a periodic Markov chain with period two, so $p_{11}^{(2m+1)}=0$. From either state 2 or state 4 the next-step probability of entering state 1 is $2/3$. Therefore $p_{11}^{(2m)}=2/3$ for every $m\ge 1$. The subsequences have different limits, so the second return-probability sequence does not converge.

Start the Markov chain at a state $i$ and define the strictly positive first return time $T_i^{+}=\inf \{n\ge 1:X_n=i\}$. A recurrent state satisfies ${\mathbb{P}}_i(T_i^{+}<\infty )=1$; a transient state has this probability strictly below one. Equivalently a recurrent state is visited infinitely often almost surely when started there, whereas a transient state receives finitely many visits almost surely. The recurrence criterion by return probabilities gives the equivalent testStates in a communicating class share this classification. In an irreducible Markov chain all states communicate, so the chain is called a recurrent Markov chain if all its states are recurrent and a transient Markov chain if all are transient.

Represent the simple random walk by $X_n={\xi }_1+\cdots +{\xi }_n$, where the increments are independent and identically distributed and satisfy $\mathbb{P}({\xi }_k=1)=p$, $\mathbb{P}({\xi }_k=-1)=1-p$. They are integrable and have expectation $2p-1$, so the strong law of large numbers givesIf $p\ne 1/2$, this nonzero drift implies that $X_n$ eventually leaves every fixed finite interval and tends to the appropriate infinity. Hence it visits zero only finitely many times almost surely, so zero is a transient state. By translation of the starting state, every state is transient: the chain is transient for $p\ne 1/2$. This also covers the deterministic endpoint cases $p=0,1$, without assuming Markov chain irreducibility at those endpoints.

For the symmetric simple random walk on the integer line, odd return times are impossible. A return after $2m$ steps requires exactly $m$ positive increments, soby Stirling's approximation. The resulting sum diverges by the p-series criterion. The recurrence criterion by return probabilities therefore makes zero a recurrent state. The simple random walk is an irreducible Markov chain on $\mathbb{Z}$, so the symmetric chain is recurrent.

This is the synchronous product of simple symmetric random walks, rather than a walk that changes only one coordinate at a time. Independence of the three coordinate processes givesOdd-time return probabilities vanish. The p-series with exponent $3/2$ converges, so the sum of all return probabilities is finite. By the recurrence criterion by return probabilities, the origin is a transient state: the three-dimensional process is transient. From the origin its communicating class consists of integer triples whose coordinates have the same parity; translation gives the same classification for every other class.