Past exam of the mathematics course of the University of Cambridge / 2017 / ib / Paper 4 / 9H / Solution

Let $S_0=0$ and let each increment of the simple symmetric random walk be uniformly chosen from $\{\pm e_1,\pm e_2,\pm e_3\}$. A return requires an even number of steps. In $2n$ steps returning to zero, let $a,b,c$ be the respective numbers of positive steps in the three directions; there must also be $a,b,c$ negative steps, so $a+b+c=n$. Counting step sequences givesThe terms $p_{abc}=n!/(3^{n}a!b!c!)$ form a multinomial distribution, so $\sum p_{abc}^2\le (\max p_{abc})\sum p_{abc}=\max p_{abc}$. The permitted combinatorial inequalities give $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/4^n\le C_1{n}^{-1/2}$ and ${\max }_{a+b+c=n}{p}_{abc}\le C_2/n$ for $n\ge 1$. The second bound also follows by noting that the largest multinomial coefficient occurs when $a,b,c$ differ by at most one and then applying Stirling formula. ThusTo prove the origin is a transient state, let $q$ be the probability of at least one return after time zero. The Strong Markov property at successive returns gives $\mathbb{P}(N\ge k)=q^k$ for the number $N$ of later returns. Therefore $\mathbb{E}(N+1)={\sum }_j{u}_j$ would be infinite if $q=1$. The bound forces $q<1$, proving that the origin is a transient state. Translation invariance gives the same conclusion at every lattice point. The coordinate walks need not be treated as independent; the counting via multinomial coefficients already incorporates their dependence.