Probability of $X_{n+1}=x$ in a random walk

Question

I have the following problem regarding random walks:

Given a simple random walk $\{ X_n : n=0,1,2,\dots \} $ in $\mathbb{Z}$ and $p+q=1$ show that $$P(X_{n+1}=x) = p P(X_n = x-1 ) + qP(X_n = x+1 )$$

I don't know where to start, it seems intuitive since it is just like the Law of Total Probability. I also have this result to help me: $P(X_{n+1}=j|X_n = i)=\begin{cases} p & \text{ if }j=i+1 \\ q & \text{ if } j = i-1\end{cases}$. I don't know how to put it all together, thanks for the help.

Answer 1

Here is a proof using characteristic functions. The characteristic function of $X_n$ is $$\varphi_{X_n}(a)=E[e^{iaX_n}]=E[e^{ia\sum^n Y_k}]=(qe^{-ia}+pe^{ia})^n$$ thanks to IIDness of the increments $(Y_k)_{k \leq n}$. So $$\begin{aligned}\varphi_{X_{n+1}}(a)&=(qe^{-ia}+pe^{ia})^n(qe^{-ia}+pe^{ia})=\\ &=q(qe^{-ia}+pe^{ia})^ne^{-ia}+p(qe^{-ia}+pe^{ia})^ne^{ia}=\\ &=q\varphi_{X_n}(a)e^{-ia}+p\varphi_{X_n}(a)e^{ia}\end{aligned}$$ By using the shift properties of characteristic functions, if we invert back to $P_{X_n}(k)$ we get $$P_{X_{n+1}}(k)=qP_{X_{n}}(k+1)+pP_{X_{n}}(k-1)$$

---

To show the shifting property:

$$(2\pi)^{-1}\int \varphi_{X_n}(a)e^{-ia}e^{-iak}da=(2\pi)^{-1}\int \varphi_{X_n}(a)e^{-ia(k+1)}da=P_{X_n}(k+1)$$

Answer 2

Actually there is not much to prove I think.

$p(X_{n+1}=x)=\sum_{a \in Z} p(X_{n+1}=x|X_{n}=a)p(X_{n}=a)$

This is the law of total probability. Now only two conditional probabilities are nonzero in your case, namely $a=x-1$ and $a=x+1$.