Random Walks

Random walks on $\mathbb{Z}$ are the discrete skeleton underneath continuous diffusion models used across science. In physics, the symmetric walk models Brownian diffusion of particles in a fluid, and Pólya's dichotomy explains why a diffusing particle in one or two dimensions returns to its neighborhood infinitely often while in three dimensions it typically escapes — a fact relevant to reaction-diffusion kinetics and the recurrence of gases. In finance, gambler's-ruin-type calculations underlie barrier option pricing and value-at-risk models where an asset's log-price is modeled as a biased or unbiased walk hitting stop-loss or profit-target boundaries, directly generalizing Worked Example 2. In computer science, random walks power PageRank-style algorithms, random walk hashing, self-stabilizing token-passing protocols in distributed systems, and Markov Chain Monte Carlo samplers whose mixing-time analysis depends on recurrence/transience-type estimates. In cryptography, Pollard's rho algorithm for integer factorization and discrete logarithms is explicitly a random walk on a finite group, using birthday-paradox-style collision (return) statistics analogous to $u_{2n}$. In statistics, sequential probability ratio tests (Wald's SPRT) reduce exactly to gambler's ruin on the log-likelihood-ratio scale, using the same linear difference equation solved in Example 2. Finally, the walk's centered version $S_n - n(p-q)$ is the model example of a discrete-time martingale, and its diffusive scaling limit is precisely Brownian motion, while its recursive first-step structure is the direct ancestor of the extinction/survival analysis in Branching Processes.

Ask the tutor: How does the gambler's ruin formula change if the gambler can also stay put with some probability at each step?

Picture the walk as a token on a number line, starting at $0$, jumping right with probability $p$ and left with probability $q=1-p$ at each tick of a clock. Over many steps, the typical position grows like $n(p-q)$ — a straight-line drift — while the fluctuation around that drift grows only like $\sqrt{n}$, by the central limit theorem scaling that anticipates Brownian motion. When $p=q=1/2$ the drift term vanishes entirely, and the walk is only fluctuation: it has no systematic reason to prefer one side of the origin, and this lack of drift is exactly what forces it back through $0$ infinitely often. The key computational device throughout is the first-step decomposition: condition on the outcome of $X_1$, and the walk restarted after one step is again a random walk, now aiming at a shifted target. This self-similarity turns hitting-probability questions into linear recursions that can be solved exactly — the same idea that later solves absorption probabilities in general Markov chains and ruin probabilities in Branching Processes.

Example 1 — Exact return probability for a biased coin, $p = 0.6$. Take $p=0.6$, $q=0.4$. We compute $u_{2n}=\binom{2n}{n}(0.24)^n$ (since $pq = 0.24$) for a few small $n$ to see transience concretely, and then find the exact return probability $f$ using generating functions. The generating function of $(u_{2n})$ is known in closed form: for the simple random walk,

which follows from the binomial series identity $\sum_n \binom{2n}{n} y^n = (1-4y)^{-1/2}$ applied with $y = pqx^2$. The relation between $U(x)$ and $f$ comes from the renewal argument (Step 2–3 of the Lemma's proof) applied at the level of generating functions: if $F(x):=\sum_n P_0(\text{first return at time } n) x^n$ then $U(x) = 1/(1-F(x))$, and $f = F(1) = 1 - 1/U(1)$. Here

Hence

So with $p=0.6$ the walk still returns to its start with probability $0.8$ — quite likely on a single attempt — but by the Lemma the expected number of returns is $f/(1-f) = 0.8/0.2 = 4$, finite, confirming transience: the walk returns a finite (geometric-mean-4) number of times and then escapes to $+\infty$ forever, consistent with $p-q=0.2>0$. Contrast with $p=1/2$: there $4pq=1$, so $U(1)=\infty$ and formally $f = 1-0 = 1$ — perfectly consistent with recurrence and an infinite expected number of returns.

Example 2 — Gambler's ruin on $\{0,1,\dots,N\}$ with $p\ne q$, unequal stakes and asymmetric boundary. A gambler starts with $\$k$ ($0<k<N$) and stakes $\$1$ per round on independent bets, winning with probability $p=0.4$ and losing with probability $q=0.6$. She stops when her fortune hits $0$ (ruin) or $N$ (target). Take $N = 10$, $k = 3$. We find the probability of ultimate ruin, $P_k(\text{hit } 0 \text{ before } N)$. Let $p_k := P_k(\text{hit } N \text{ before } 0)$ for $k=0,\dots,N$, with boundary conditions $p_0 = 0$, $p_N=1$. First-step analysis (condition on the first bet) gives, for $0<k<N$,

This is a linear second-order recursion with characteristic equation $p x^2 - x + q = 0$, whose roots are $x=1$ and $x = q/p$ (checked by substitution: $p\cdot 1 - 1 + q = p+q-1=0$, and $p(q/p)^2 - q/p + q = q^2/p - q/p + q = (q/p)(q-1) + q = -(q/p)(p)+q = -q+q=0$). Since $p\ne q$, the roots $1$ and $q/p$ are distinct, so the general solution is

Boundary conditions: $p_0 = A+B = 0 \Rightarrow A=-B$; and $p_N = A + B(q/p)^N = 1$. Substituting $A=-B$:

Hence

Now plug in numbers: $q/p = 0.6/0.4 = 1.5$, $N=10$, $k=3$. Compute $(q/p)^3 = 1.5^3 = 3.375$ and $(q/p)^{10} = 1.5^{10}$. We compute $1.5^{10}$ stepwise: $1.5^2=2.25$, $1.5^4 = 2.25^2 = 5.0625$, $1.5^5 = 5.0625\times1.5 = 7.59375$, $1.5^{10} = 7.59375^2 = 57.665039...$. Precisely, $7.59375^2 = 57.665039...$; let's verify: $7.59375^2 = 7.59375\times7.59375$. Compute $7.59375\times7 = 53.15625$, $7.59375\times0.59375 = 4.5093...$; sum $\approx 57.6656$. So $(q/p)^{10}\approx 57.6650$. Then

So the probability of reaching $\$10$ before ruin, starting from $\$3$ against an unfavorable game ($p=0.4$), is only about $4.19\%$. Correspondingly, the ruin probability is

illustrating how strongly a small unfavorable edge compounds over even a modest gap to the target — a quantitative version of the transience just proved, now confined to a finite interval.