= Solution
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 equation>
$$
u_0=1,\qquad u_n=\sum_{k=1}^n f_k u_{n-k}\quad(n\geq1).
$$
For $0<s<1$, define the <probability generating functions> $U(s)=\sum_{n\geq0}u_ns^n$ and $F(s)=\sum_{n\geq1}f_ns^n=\mathbb E_0[s^T]$. Absolute convergence, or nonnegative summation, justifies the convolution identity $U=1+FU$. The <binomial series> gives
$$
U(s)=\sum_{k\geq0}\binom{2k}{k}\left(\frac{s^2}{4}\right)^k=\frac1{\sqrt{1-s^2}}.
$$
Solving the renewal identity gives \b[the <first-return generating function of the simple symmetric random walk>]
$$
\boxed{\mathbb E_0[s^T]=F(s)=1-\sqrt{1-s^2},\qquad 0<s<1.}
$$
As consistency checks, $F(s)\to1$ as $s\uparrow1$, confirming recurrence, while $F'(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_0T=\infty$, confirming <null recurrent states>.
Back to article page
