Simple Symmetric Random Walk — Combinatorics, Convolution, and Fourier
Purpose & Overview
We study the simple symmetric random walk on $\mathbb Z$, develop basic recurrences, prove the return probability by combinatorics, recast the walk via discrete convolution, and compute the same probability with Fourier series. This page also includes a short programming assignment.
\[
\mathbb P(S_{2m}=0)=\frac1{2^{2m}}\binom{2m}{m},\qquad \mathbb P(S_{2m+1}=0)=0.
\]
Model: the walk and its basic recurrence
Let $(S_k)_{k\ge 0}$ be the simple symmetric random walk on $\mathbb Z$:
\[
S_0=0,\qquad S_k=S_{k-1}+X_k,
\]
where $X_k\in\{1,-1\}$ are independent with $\mathbb P(X_k=\pm1)=\tfrac12$.
Write $P_k(n)=\mathbb P(S_k=n)$. Conditioning on the first step yields the nearest-neighbor recursion
\[
P_k(n)=\tfrac12\,P_{k-1}(n-1)+\tfrac12\,P_{k-1}(n+1).\tag{$\dagger$}
\]
Observation: $P_{2\ell+1}(0)=0$ for all $\ell$, because a sum of an odd number of $\pm1$ cannot be $0$.
Return probability by counting
For a fixed $k$, let $\Omega_k=\{(x_1,\dots,x_k):x_j\in\{\pm1\}\}$. Each sequence has probability $(\tfrac12)^k$. If $R(w)$ counts $+1$’s and $L(w)$ counts $-1$’s, then $R(w)+L(w)=k$ and
\[
S_k(w)=R(w)-L(w)=2R(w)-k.
\]
Hence $S_k(w)=0$ iff $R(w)=k/2$, which forces $k$ even: write $k=2m$. Returning to the origin is equivalent to taking exactly $m$ right and $m$ left steps. The number of such sequences is $\binom{2m}{m}$. Therefore
\[
\mathbb P(S_{2m}=0)=\frac{1}{2^{2m}}\binom{2m}{m},\qquad \mathbb P(S_{2m+1}=0)=0.
\]
Convolution formulation
Define $s:\mathbb Z\to[0,1]$ by
\[
s(j)=\begin{cases}\tfrac12,& j=1,\\ \tfrac12,& j=-1,\\ 0,&\text{otherwise.}\end{cases}
\]
For functions $p,q:\mathbb Z\to\mathbb R$, set
\[
(p*q)(n)=\sum_{k\in\mathbb Z} p(k)\,q(n-k).
\]
Since $s$ is supported on $\{\pm1\}$,
\[
(p*s)(n)=\tfrac12\,p(n-1)+\tfrac12\,p(n+1).
\]
Comparing with $(\dagger)$ gives the compact formula
\[
P_k=P_{k-1}*s=P_0*s^{*k},\qquad P_0(n)=\mathbf 1_{\{0\}}(n).
\]
Fourier series on $\mathbb Z$ and convolution
For $a\in \ell^1(\mathbb Z)$, define the Fourier series
\[
\widehat a(t)=\sum_{n\in\mathbb Z} a(n)\,e^{-2\pi i n t},\qquad t\in[0,1).
\]
Then
\[
a(m)=\int_0^1 \widehat a(t)\,e^{2\pi i m t}\,dt,\qquad m\in\mathbb Z.
\]
If $a,b\in\ell^1(\mathbb Z)$, the convolution $a*b\in\ell^1(\mathbb Z)$ and
\[
\widehat{a*b}(t)=\widehat a(t)\,\widehat b(t).
\]
\begin{aligned}
\widehat{a\ast b}(t)
&= \sum_{n\in\mathbb{Z}} (a\ast b)(n)\,e^{-2\pi i n t} \\
&= \sum_{n\in\mathbb{Z}} \sum_{k\in\mathbb{Z}} a(k)\,b(n-k)\,e^{-2\pi i n t}
\quad(\mathrm{expand}\ a\ast b) \\
&= \sum_{k\in\mathbb{Z}} a(k)\, \sum_{j\in\mathbb{Z}} b(j)\,e^{-2\pi i (j+k)t} \\
&= \left(\sum_{k\in\mathbb{Z}} a(k)\,e^{-2\pi i k t}\right)
\left(\sum_{j\in\mathbb{Z}} b(j)\,e^{-2\pi i j t}\right) \\
&= \widehat a(t)\,\widehat b(t).
\end{aligned}
\]
Fourier computation of $\mathbb P(S_{2m}=0)$
Since $P_k=s^{*k}$, we have $\widehat{P_k}(t)=(\widehat s(t))^{k}$. Compute
\[
\widehat s(t)=\tfrac12 e^{-2\pi i t}+\tfrac12 e^{2\pi i t}=\cos(2\pi t).
\]
Hence
\[
\widehat{P_k}(t)=\cos^k(2\pi t)
\quad\text{and}\quad
P_k(m)=\int_0^1 \cos^k(2\pi t)\,e^{2\pi i m t}\,dt.
\]
In particular,
\[
P_{2m}(0)=\int_0^1 \cos^{2m}(2\pi t)\,dt
=\frac{1}{2^{2m}}\sum_{k=0}^{2m}\binom{2m}{k}\int_0^1 e^{2\pi i (2m-2k)t}\,dt
=\frac{1}{2^{2m}}\binom{2m}{m}.
\]
The last equality uses $\int_0^1 e^{2\pi i r t}\,dt=\mathbf 1_{\{r=0\}}$.
Sanity checks for small $k$
- $k=2$: $P_2(2)=\tfrac14$, $P_2(0)=\tfrac12$, $P_2(-2)=\tfrac14$.
- $k=3$: $P_3(3)=\tfrac18$, $P_3(1)=\tfrac38$, $P_3(-1)=\tfrac38$, $P_3(-3)=\tfrac18$ and $P_3(0)=0$ (odd step count).
Homework (Mathematica)
- Write a function that returns $\displaystyle \mathbb P(S_{2m}=0)=\dfrac{1}{2^{2m}}\binom{2m}{m}$ for any non-negative integer $m$.
- Use your function to estimate $\mathbb P(S_{10^3}=0)$ (you may work in arbitrary precision).
Problem — Return to 0 with steps \(\{-2,-1,1,2,5\}\) (Fourier only)
Statement. A random walker on \(\mathbb{Z}\) starts at \(0\). At each step the walker chooses one of \(\{-2,-1,1,2,5\}\) with equal probability \(1/5\). Find, for each \(n\in\mathbb{N}\), the return probability \( \mathbb{P}(S_n=0) \) without combinatorics — use only convolution and the Fourier transform. Then evaluate it in Mathematica.
Convolution/Fourier setup.
Let \(s:\mathbb{Z}\to[0,1]\) be the one–step distribution
\[
s(k)=\begin{cases}
\tfrac15,& k\in\{-2,-1,1,2,5\},\\[2pt]
0,& \text{otherwise.}
\end{cases}
\]
For the \(n\)-step distribution \(P_n=s^{\ast n}\) we have, with the
Fourier series \(\widehat f(t)=\sum_{m\in\mathbb{Z}} f(m)e^{-2\pi i m t}\) on \(t\in[0,1)\),
\[
\widehat{P_n}(t)=\big(\widehat s(t)\big)^n,\qquad
P_n(0)=\int_0^1 \big(\widehat s(t)\big)^n\,dt.
\]
Here
\[
\widehat s(t)=\tfrac15\!\Big(e^{+4\pi i t}+e^{+2\pi i t}+e^{-2\pi i t}+e^{-4\pi i t}+e^{-10\pi i t}\Big).
\]
Thus the desired probability is
\[
\boxed{\ \mathbb{P}(S_n=0)=\displaystyle\int_0^1 \!\!\left[\tfrac15\!\Big(e^{4\pi i t}+e^{2\pi i t}+e^{-2\pi i t}+e^{-4\pi i t}+e^{-10\pi i t}\Big)\right]^n dt\ }.
\]
Mathematica code (numerical evaluation). Copy–paste into a Mathematica notebook.
(* Characteristic function (Fourier series on t in [0,1)) *)
phi[t_] := (1/5) (Exp[4 Pi I t] + Exp[2 Pi I t] + Exp[-2 Pi I t] +
Exp[-4 Pi I t] + Exp[-10 Pi I t]);
(* Return probability P(S_n = 0) *)
ReturnProb0[n_Integer?NonNegative, wp_:50] := Module[{val},
val = NIntegrate[(phi[t])^n, {t, 0, 1},
WorkingPrecision -> wp,
Method -> {"GlobalAdaptive", "SymbolicPreprocessing" -> 0}];
Chop[Re[val], 10^(-wp/3)] (* remove tiny imag parts *)
];
(* Examples *)
Table[{n, ReturnProb0[n, 70]}, {n, 0, 12}]
Notes: \(P(S_0=0)=1\) by convention. The integral is real and nonnegative; small imaginary parts arise numerically and are removed with Chop. Increase wp for larger \(n\).