Consider a random walk $\left(X_i\right)$ where $X_i$ equals $1$ (right) or $-1$ (left). Define $$S_m=\sum_{i=1}^m X_i;$$
i.e., $S_m$ is the location of the walk after $m$ steps. Define a random walk for which $\mathbb{P}\left(X_i=1\right)$ is equal to:
- $p>1/2$ when $S_{i-1}<0$,
- $q=1-p$ when $S_{i-1}>0$,
- $1/2$ whenever $S_{i-1}=0$.
The paper On a particular one-dimensional random walk, by Robert Burton, 1962 proves that $\sum_{m=1}^{2n}\mathbb{P}\left(S_m = 0\right)\sim \left(2-1/p\right)n$ (note that the event $S_m=0$ means that the walk is located at the origin after $m$ steps, which implies $m$ must be even).
In the proof, the author defines $P_m\left(k\right)=\mathbb{P}\left(S_{2m}=k\right)$ and claims that $$P_{m+1}\left(0\right)=2p^{2}P_{m}\left(1\right)+pP_{m}\left(0\right).$$
However, I obtained $p^2P_{m}\left(-1\right)+\left(p+q\right)P_{m}\left(0\right)+q^{2}P_{m}\left(1\right)$ since the location after $m$ steps is either at $-2$, $0$, or $2$; to get back to the origin in two steps, we either need to go two to the right, two to the left, or one left and one right.
Since $p+q=1$, my expression simplifies to $p^2P_{m}\left(-1\right)+P_{m}\left(0\right)+q^{2}P_{m}\left(1\right)$. How can I obtain the author's equivalence relation?
Best Answer
As mentioned in the comment, $P_m(k) = \mathbb{P}(S_{2m}=2k)$, but your working shows that you get this right, so it's likely to be a typo.
Be careful of definitions. $p$ is not the probability to move towards the right, $p$ is the probability to move towards $0$ when we are not at $0$, by symmetry, $P_m(-1) = P_m(1)$.
When we are at $2$ or $-2$, we need to move towards $0$ twice, resulting in a probability of $p^2$.
When we are at $0$, we need probability $\frac12$ to move away from $0$ and then $p$ to move back to $0$. The first move can be to the left or right.
\begin{align} P_{m+1}(0) &= p^2P_m(-1) + \frac12\left(p+p \right)P_m(0) + p^2P_m(1) \\ &=(p^2+p^2)P_m(1)+pP_m(0)\\ &=2p^2P_m(1) + pP_m(0) \end{align}