# Probability generating function for 1D symmetric random walk

We have a simple symmetric random walk $(X_n)_{n\geq 0}$ on the integers, starting at $X_0 = 0$. I've shown that it's irreducible, and null-recurrent. We define $T = \inf\{n\geq 1 : X_n = 0\}$, the first time the chain returns to the origin, and I'm asked to compute $\mathbb{E}[s^T]$ for $0<s<1$.

Attempt so far: Conditioning on the first step seems like a good start, giving \begin{equation}\mathbb{E}[s^T] = \frac{1}{2}\left(\mathbb{E}[s^T \mid X_1 = 1] + \mathbb{E}[s^T \mid X_1 = -1]\right).\end{equation} But continuing from here would give the first hitting time of 0 starting from plus or minus 1. Should I instead be looking at $T_i$, the hitting time of 0 starting from $i$? Or should I next condition on $X_2$ to give $T$ again?

Well, by symmetry we have $\mathbb E[s^T \mid X_1 = 1] = \mathbb E[s^T \mid X_1 = -1]$: it doesn't matter which way you go first, both directions are identical. So conditioning on the first step doesn't really tell you anything.
It's the second step where interesting things happen. Let $T_{ij}$ be the hitting time to first reach state $j$ from state $i$; then $\mathbb E[s^{T_{20}}] = \mathbb E[s^{T_{21}}] \cdot \mathbb E[s^{T_{10}}] = \mathbb E[s^{T_{10}}]^2$, the latter by translational symmetry.
Since from $1$, we go to either $2$ or $0$, we have $$\mathbb E[s^{T_{10}}] = \frac12 \left(s \cdot E[s^{T_{20}}] + s\right) = \frac12 \left(s \cdot \mathbb E[s^{T_{10}}]^2 + s\right),$$ and now we're getting somewhere: solving for $\mathbb E[s^{T_{10}}]$ yields $$\mathbb E[s^{T_{10}}] = \frac{1-\sqrt{1-s^2}}{s}$$ and therefore $\mathbb E[s^T] = s \cdot \mathbb E[s^{T_{10}}] = 1 - \sqrt{1-s^2}$.