Section 16.3

Paths, Reflection and First Returns

Counting walk paths: first return to equality at time 2n, ruin at an exact time, two walks that stay ordered.

Toolkit

Exact enumeration of lattice paths via the reflection principle and the ballot/hitting-time theorems, used whenever a question asks for a probability or count tied to a *first* passage or an exact-time event rather than an eventual one.

Key facts for a simple symmetric walk with steps $\pm1$ :

Reflection principle: the number of paths from $0$ to $m$ in $n$ steps that touch level $a>0$ (with $m<a$ ) equals the number of unrestricted paths from $0$ to $2a-m$ .
Ballot theorem: among paths with $p$ up-steps and $q$ down-steps ( $p>q$ ) ending positive, the fraction that stay strictly positive throughout is $(p-q)/(p+q)$ .
Hitting-time theorem: $\mathbb{P}(T_k=n)=\frac{k}{n}\mathbb{P}(S_n=k)$ , the probability that the walk first reaches $k>0$ at time $n$ .
First return to $0$ at time $2n$ has probability $\binom{2n}{n}2^{-2n}/(2n-1)$ , obtained from the ballot theorem applied to the two half-excursions.
Two independent walks staying ordered reduce to a single diagonal walk on $\mathbb{Z}^2$ ; reflecting across the diagonal at the first meeting counts “bad” crossing paths.
Catalan numbers $C_n=\frac{1}{n+1}\binom{2n}{n}$ count paths of length $2n$ that stay non-negative, underlying arcsine-law sums.

Problems