Section 11.4

Stopping Rules and Wald's Identity

Random sums run until a threshold: uniforms summing past 1, dice totals reaching a target, running sums hitting multiples, E[S_N] = E[N]E[X].

Toolkit

Wald’s identity governs sums $S_N=\sum_{i=1}^N X_i$ where $N$ is a stopping time for the i.i.d. sequence $X_i$ (determined by the process up to time $N$ , with $\mathbb{E}[N]<\infty$ ):

\mathbb{E}[S_N] = \mathbb{E}[N]\,\mathbb{E}[X].

For “first time exceeding a threshold” problems, when $N$ is defined by $S_{N-1}\le x < S_N$ , the overshoot and $N$ itself can be studied via the renewal-type function $m(x)=\mathbb{E}[N_x]$ , satisfying

m(x) = 1+\int_{\max(0,x-1)}^{x} m(u-t)\,f(t)\,dt

(conditioning on the first step), or in closed form $m(x)=e^x$ for $\mathrm{Unif}(0,1)$ steps on $[0,1]$ , extended piecewise beyond. For a Markov chain on residues mod $k$ with each step uniformly permuting the residue, hitting a fixed residue is geometric with success probability $1/k$ regardless of current state.

Problems