Past exam of the mathematics course of the University of Cambridge / 2016 / ib / Paper 1 / 20H / c

Let $u_n={\mathbb{P}}_0(X_n=0)$ and $f_n={\mathbb{P}}_0(T=n)$. Decomposing at the first return and using the Markov property gives the renewal equationFor $0<s<1$, define the probability generating functions $U(s)={\sum }_{n\ge 0}{u}_n{s}^n$ and $F(s)={\sum }_{n\ge 1}{f}_n{s}^n={\mathbb{E}}_0[s^T]$. Absolute convergence, or nonnegative summation, justifies the convolution identity $U=1+FU$. The binomial series givesSolving the renewal identity gives the first-return generating function of the simple symmetric random walkAs consistency checks, $F(s)\to 1$ as $s\uparrow 1$, confirming recurrence, while $F^{\prime }(s)=s/\sqrt{1-s^2}\to \infty$. By monotone convergence of ${\sum }_{n}n{f}_n{s}^{n-1}$, this last limit is ${\mathbb{E}}_{0}T=\infty$, confirming null recurrent states.