Past exam of the probability course of the University of Oxford / 2021 / 3 / b

Here $a,b$ are coprime integers.

Fix any two integers $i,j$. By Bézout's identity, there are integers $u,v$ with $au-bv=j-i$. Replacing $(u,v)$ by $(u+kb,v+ka)$ leaves this identity unchanged. Choose $k$ large enough that both entries are nonnegative. A path with $u+kb$ upward steps and $v+ka$ downward steps then takes $i$ to $j$, with strictly positive probability $p^{u+kb}{q}^{v+ka}$. There are no boundary restrictions on this state space.

This applies in both directions, so every pair of states communicates. Hence

A return path with $u$ upward steps and $v$ downward steps satisfies $au=bv$. Since $a,b$ are coprime, this is equivalent to $u=bk$ and $v=ak$ for an integer $k\ge 1$. Its length is therefore $k(a+b)$.

Conversely, for each such $k$, any ordering of $bk$ upward and $ak$ downward steps is an allowed positive-probability return path. The possible strictly positive return times are exactly the positive multiples of $a+b$. By the definition of the period of a state in a Markov chain as their greatest common divisor,In particular, none of the states is aperiodic.

Suppose a stationary distribution $\pi$ exists. Its stationarity equations areSince ${\sum }_j{\pi }_j=1$, its masses tend to zero as $|j|\to \infty$, and a positive maximum $M={\pi }_{j_0}$ is attained. Both terms on the right are at most $M$. Since $p,q>0$ and $p+q=1$, equality forces ${\pi }_{j_0-a}={\pi }_{j_0+b}=M$. Applying the same argument repeatedly at $j_0-a,j_0-2a,\dots$ givesThese are infinitely many distinct states, contradicting ${\sum }_j{\pi }_j=1$. ThusThis maximum principle proof uses neither a finite expected value of the state nor the coprimality assumption.

First identify the recurrence type, rather than infer an occupation limit from a one-time probability. At time $k(a+b)$, return to zero requires exactly $kb$ upward steps. The binomial distribution giveswhere the last step is Stirling's approximation. At all other positive times the return probability is zero. Hence ${\sum }_{n\ge 0}{\mathbb{P}}_0(S_n=0)=\infty$. The recurrence criterion by return probabilities proves the recurrent property; by the irreducible Markov chain property established in (i), every state is recurrent. The equivalence of positive recurrence and existence of a stationary distribution for an irreducible Markov chain on a countable state space, together with (iii), makes this chain null recurrent.

For completeness, the zero occupation proportion follows directly by treating returns as a renewal process. Let $L_1,L_2,\dots$ be successive strictly positive return-cycle lengths to zero. The Strong Markov property makes them independent and identically distributed, the recurrent property makes them finite almost surely, and the null recurrent property gives $\mathbb{E}{L}_1=\infty$. For each positive integer $K$, the strong law of large numbers applied to $\min (L_j,K)$ givesTake a common event of probability one for these countably many $K$. By the monotone convergence theorem, the right side increases to infinity. Thus the number of completed return cycles by time $n$, divided by $n$, tends to zero. Counting the initial visit changes this ratio by at most $1/n$. Consequently,The walk visits zero infinitely often, but the asymptotic fraction of time spent there is zero.