Random Walks and Martingales

Why a test checked after every batch of users eventually rejects a true null hypothesis, and how a test can be checked as often as one likes without losing its level. Proves gambler's ruin probabilities and expected durations by first-step equations; defines martingales through conditional expectation and proves the optional stopping theorem for bounded stopping times and for bounded stopped processes, with the general conditions cited; re-derives gambler's ruin and proves Wald's identity with it; proves Ville's maximal inequality, that every likelihood ratio and every Bayes factor is a martingale under the null hypothesis, and the error bounds and termination of Wald's sequential probability ratio test; proves, with Kolmogorov's zero-one law cited, that repeated z tests reject a true null with probability 1. Measures on a simulated A/B test with a 40% click rate that peeking after every 100 pairs of users raises the false positive rate from 0.05 to 0.43 by 20,000 pairs, while a test martingale on discordant pairs stays below 0.05 at a cost in power. Worked problems on a short gambler's ruin, the doubling bet that meets Ville's bound exactly, the sequential test's error bounds and a mixture likelihood ratio against a p-value.

An A/B test on a search page shows each new pair of users the two versions, one each, and records whether each user clicks. Both versions have a click rate of 40%, so there is nothing to find. The analyst runs the usual two-proportion test after every 100 pairs and stops at the first $p$-value below 0.05. In a simulation of that practice, 42.7% of the experiments declared a difference before 20,000 pairs. Why does looking more often manufacture discoveries, and is there a test that may be looked at after every pair without that happening?

Both answers come from the theory of random walks and martingales. A random walk is a running sum $S_n = S_0 + X_1 + \cdots + X_n$ of independent and identically distributed (i.i.d.) steps. The difference in clicks between the two versions after $n$ pairs is one, and its standardized value, the test statistic, wanders like one. A martingale is the fortune of a player in a fair game: whatever has happened, its expected next value is its present value. Fair games cannot be beaten by choosing when to stop, within limits that the optional stopping theorem makes exact, and the likelihood ratio of the data is such a game when the null hypothesis is true. That gives tests that may stop at any time.

First we treat the simple random walk and the gambler's ruin problem with nothing but conditional probability. Then we define martingales and stopping times, prove the optional stopping theorem, and use it to solve gambler's ruin again and to prove Wald's identity. Next come Ville's maximal inequality, likelihood ratios as martingales, Wald's sequential test and tests valid at any stopping time, and the proof that repeated naive tests reject eventually. Finally the A/B test is measured. The article assumes Conditional Expectation and is part of Stochastic Processes and Time Series; Markov Chains and Stationary Distributions supplies the general method for absorbing chains of which gambler's ruin is a case.

Random walks

Let $X_1, X_2, \ldots$ be i.i.d. steps with mean $\mu$ and variance $\sigma^2$, and $S_n = S_0 + X_1 + \cdots + X_n$ with a fixed start $S_0$. The walk has mean $S_0 + n\mu$ and variance $n\sigma^2$, by linearity and the variance of a sum of independent variables (Expectation, Variance and Covariance). The simple random walk has steps $+1$ with probability $p$ and $-1$ with probability $q = 1 - p$; it is symmetric when $p = q = 1/2$.

Random walks appear on this site in several guises.

  • The A/B test. Let $C_{A,i}$ and $C_{B,i}$ be the click indicators of the $i$th pair. The difference $D_n = \sum_{i \le n}(C_{B,i} - C_{A,i})$ is a random walk with steps in $\{-1, 0, 1\}$. When both versions have the same click rate the steps have mean 0, and the two-proportion $z$ statistic is $D_n$ divided by an estimate of its standard deviation $\sigma\sqrt{n}$.
  • Poisson arrival times. The arrival times of The Poisson Process are a random walk with exponential steps.
  • Search on a plateau. On a shoulder of a fitness landscape, sideways moves with random tie-breaking are a symmetric simple random walk, as Hill Climbing shows; the walk crosses a distance $m$ in about $m^2$ steps.

Gambler's ruin

A gambler starts with $a$ units, bets one unit at a time, wins each bet with probability $p$, where $0 < p < 1$, and stops on reaching $b$ units or on losing everything, where $0 < a < b$. The fortune is a simple random walk from $S_0 = a$, stopped at the time $\tau = \min\{n : S_n = 0 \text{ or } S_n = b\}$. What is the chance of reaching $b$, and how long does the game last? Write $P_a$ and $E_a$ for probability and expectation when the walk starts at $a$.

Theorem 1 (gambler's ruin). Let $r = q/p$.

  1. $\tau$ is finite with probability 1, and $E_a[\tau] < \infty$.
  2. The probability of reaching $b$ first is $w_a = P_a(S_\tau = b) = a/b$ when $p = q$, and $w_a = (r^a - 1)/(r^b - 1)$ when $p \ne q$.
  3. The expected duration is $e_a = E_a[\tau] = a(b - a)$ when $p = q$, and $e_a = \dfrac{a}{q - p} - \dfrac{b}{q - p}\cdot\dfrac{1 - r^a}{1 - r^b}$ when $p \ne q$.

Here is the plan. Condition on the first bet: afterwards the game is the same game started one unit higher or lower. That gives two linear recurrences with boundary values, and the formulas are their only solutions.

Proof. (1) From any fortune between 0 and $b$, $b$ wins in a row end the game, which has probability $p^b > 0$. The walk's steps in disjoint blocks of $b$ bets are independent, so the game survives $k$ blocks with probability at most $(1 - p^b)^k$. Hence $P_a(\tau > n) \le (1 - p^b)^{\lfloor n/b\rfloor}$, which tends to 0, and by the tail formula for the mean of a variable with values $0, 1, 2, \ldots$ (Expectation, Variance and Covariance),

$$E_a[\tau] = \sum_{n \ge 0} P_a(\tau > n) \le b\sum_{k \ge 0}(1 - p^b)^k = b/p^b < \infty.$$

(2) Condition on the first step. After it, the walk is a simple random walk from $a + 1$ or $a - 1$, independent of the step, so for $0 < a < b$

$$w_a = p\,w_{a+1} + q\,w_{a-1}, \qquad w_0 = 0, \quad w_b = 1.$$

(This is the law of total probability over the value of $X_1$, together with the fact that the steps after the first are i.i.d. and independent of it; the walk is a Markov chain, and Markov Chains and Stationary Distributions states the Markov property.) The system has at most one solution. If $w$ and $w'$ both solve it, $v = w - w'$ satisfies $v_a = p\,v_{a+1} + q\,v_{a-1}$ with $v_0 = v_b = 0$. Let $v_j$ be the largest of $v_0, \ldots, v_b$. If $0 < j < b$, then $v_j$ is a weighted average of $v_{j-1}$ and $v_{j+1}$, neither larger, so both equal $v_j$; repeating the argument moves the maximum step by step to an end, where $v = 0$. So $v \le 0$ everywhere, and the same argument for the smallest value gives $v \ge 0$. It remains to check the formulas. For $p = q$, $a/b$ is linear in $a$, so it equals the average of its values at $a \pm 1$. For $p \ne q$, $r^a$ satisfies the recurrence because $p\,r^{a+1} + q\,r^{a-1} = r^a(pr + q/r) = r^a(q + p)$, and so does any constant; $(r^a - 1)/(r^b - 1)$ is a combination of the two with the right values at 0 and $b$.

(3) Conditioning on the first step again, using part 1 for finiteness and the law of total expectation (setting D of Conditional Expectation),

$$e_a = 1 + p\,e_{a+1} + q\,e_{a-1}, \qquad e_0 = e_b = 0.$$

Two solutions differ by a solution of the homogeneous system above, which is zero, so a solution is unique. For $p = q$: $1 + \tfrac12[(a+1)(b-a-1) + (a-1)(b-a+1)] = 1 + a(b-a) - 1 = a(b - a)$. For $p \ne q$: the term $a/(q - p)$ gives $1 + \frac{p(a+1) + q(a-1)}{q - p} = 1 + \frac{a - (q - p)}{q - p} = \frac{a}{q - p}$, and the second term is a constant times $1 - r^a$, which satisfies the homogeneous recurrence; at $a = 0$ both terms vanish, and at $a = b$ they cancel. $\square$

The recurrences are the equations $B = NR$ and $t = N\mathbf{1}$ for the chain on $\{0, \ldots, b\}$ with absorbing ends, which Markov Chains and Stationary Distributions solves in general (Theorem 8, in the section "Absorbing chains: how long until the surfer is caught"), where they also appear as first-step equations. The script solves that linear system for $b = 40$ and finds the same numbers. Part 1 and the uniqueness in parts 2 and 3 are also cases of that Theorem 8, which proves them for every finite absorbing chain. Levin and Peres (2017, Proposition 2.1) prove the fair case by the same first-step equations.

Example (roulette). A gambler bets one unit at a time on black at roulette, winning with probability 18/38, and starts with 20 units hoping to reach 40 (Durrett, 2019, Example 4.8.10). Here $r = 20/18 = 10/9$ and

$$w_{20} = \frac{(10/9)^{20} - 1}{(10/9)^{40} - 1} = 0.1084.$$

Durrett prints 0.1083. In a fair game the chance would be $20/40 = 0.5$ and the game would last $20 \times 20 = 400$ bets on average; at roulette it lasts 297.6 bets on average. In 30 simulated runs (seeds 71,000,000 to 71,000,029) of 20,000 games each, the share of games won had median 0.1099 (interquartile range 0.1076 to 0.1102). These seeds landed somewhat high; the exact 0.1084 lies well inside the range of the 30 runs, 0.1046 to 0.1120. The mean number of bets had median 298.6 (297.2 to 299.1).

Example (a nearly fair game is not nearly fair over a session). Each bet at roulette loses only $q - p = 1/19$ of a unit on average, which sounds almost fair. Yet the chance of doubling 20 units falls from 0.5 to 0.1084. The small bias acts on every one of about 300 bets, and the walk has time to feel it. The expected loss over the session is 15.66 units, which Wald's identity below obtains as $(q - p)$ times the expected number of bets.

Example (the fair walk comes back, but not soon). Start a symmetric walk at 1 and let $b$ grow. The chance of hitting 0 before $b$ is $1 - 1/b$, which tends to 1, so the walk hits 0 with probability 1. The expected time to hit 0 or $b$ is $1 \times (b - 1)$, and the time to hit 0 is at least that long. So the expected time to hit 0 is at least $b - 1$ for every $b$: it is infinite. The walk returns surely, and the wait has no finite mean. This fact will break the optional stopping theorem below.

Martingales

Fix the sequence of observations $X_1, X_2, \ldots$, which we call the history. A sequence $M_0, M_1, M_2, \ldots$ is a martingale (relative to that history) if each $M_n$ is a function of $X_1, \ldots, X_n$ ($M_0$ a constant), has a finite mean, and

$$E[M_{n+1} \mid X_1, \ldots, X_n] = M_n \qquad \text{for every } n.$$

The conditional expectation is that of Conditional Expectation, given a discrete vector or a vector with a joint density, which covers every example here. The general theory conditions on a growing family of events $\mathcal{F}_n$, the information available at time $n$, and needs the measure-theoretic conditional expectation; this article does not (Durrett, 2019, Sections 4.1 and 4.2). Replacing $=$ by $\le$ gives a supermartingale, and by $\ge$ a submartingale.

By the law of total expectation, $E[M_{n+1}] = E[E[M_{n+1} \mid X_1, \ldots, X_n]] = E[M_n]$, so a martingale has a constant mean: $E[M_n] = M_0$.

The examples rest on one fact. If $Y$ is independent of the vector $X$, then $E[\psi(X, Y) \mid X = x] = E[\psi(x, Y)]$: in the discrete case, $E[\psi(x, Y)\mathbf{1}\{X = x\}] = E[\psi(x, Y)]\,P(X = x)$ by independence, and dividing by $P(X = x)$ gives it; with densities, the conditional density of $Y$ given $X = x$ is the density of $Y$.

Example (four martingales of a random walk). Let $S_n = S_0 + X_1 + \cdots + X_n$ with i.i.d. steps of mean $\mu$, and condition on $X_1, \ldots, X_n$.

  1. $S_n - n\mu$ is a martingale: $E[S_{n+1} - (n+1)\mu \mid X_1, \ldots, X_n] = S_n + E[X_{n+1}] - (n+1)\mu = S_n - n\mu$.
  2. If $\mu = 0$ and the variance is $\sigma^2$, $S_n^2 - n\sigma^2$ is a martingale: $E[(S_n + X_{n+1})^2 \mid \ldots] = S_n^2 + 2S_nE[X_{n+1}] + E[X_{n+1}^2] = S_n^2 + \sigma^2$.
  3. For the simple walk with $p \ne q$, $r^{S_n}$ with $r = q/p$ is a martingale: $E[r^{S_n + X_{n+1}} \mid \ldots] = r^{S_n}(p\,r + q/r) = r^{S_n}(q + p)$.
  4. For any $\theta$ with $\varphi(\theta) = E[e^{\theta X_1}] < \infty$, $e^{\theta S_n}/\varphi(\theta)^n$ is a martingale, by the same computation.

In each case the first equality takes out what is known (part 2 of Theorem 2 of Conditional Expectation) and uses the fact above for the new step. Durrett (2019, Section 4.8.1) calls them the linear, quadratic and exponential martingales.

Lemma 1 (betting on a fair game). Let $M$ be a martingale and $H_1, H_2, \ldots$ bounded stakes, each $H_k$ a function of $X_1, \ldots, X_{k-1}$ (decided before the $k$th round). Then the fortune $W_n = M_0 + \sum_{k=1}^n H_k(M_k - M_{k-1})$ is a martingale. In particular $E[W_n] = M_0$.

Proof. $W_n$ has a finite mean because the stakes are bounded and each $M_k$ has a finite mean. By taking out what is known, $E[H_{n+1}(M_{n+1} - M_n) \mid X_1, \ldots, X_n] = H_{n+1}(E[M_{n+1} \mid X_1, \ldots, X_n] - M_n) = 0$. $\square$

No rule for varying the stakes, using only the past, turns a fair game into a favorable one. Durrett (2019, Theorem 4.2.8) proves the supermartingale version: no betting system beats an unfavorable game.

Survival analysis leans on a consequence of the same step. Martingale increments with finite variances are uncorrelated, though not in general independent, so their variances add. The Log-Rank Test (Theorem 1) and The Kaplan–Meier Estimator (Theorem 4) prove this for their own increments by taking out what is known. Learning theory uses the increments differently: Concentration Inequalities: Hoeffding and Bernstein proves McDiarmid's inequality (its Theorem 5) by bounding each increment of the martingale formed by averaging a function over the observations not yet revealed.

Stopping times and the optional stopping theorem

A stopping time is a random time $\tau$ with values in $\{0, 1, 2, \ldots\} \cup \{\infty\}$ such that whether $\tau = n$ is decided by $X_1, \ldots, X_n$: the indicator $\mathbf{1}\{\tau = n\}$ is a function of them. The first time a walk reaches a set is a stopping time; Markov Chains and Stationary Distributions writes the hitting time of a set $A$ as $T_A$. So is the first time a $p$-value drops below 0.05. The last time a walk is at its maximum before time 100 is not, since deciding it needs the future.

A stopping rule is a way of betting: bet one unit on each round until $\tau$, and nothing after. If the game is fair, can a clever $\tau$ make the expected final fortune differ from the start? Not if $\tau$ is bounded.

Theorem 2 (optional stopping for bounded stopping times). Let $M$ be a martingale and $\tau$ a stopping time with $\tau \le K$ for a constant $K$. Then $E[M_\tau] = M_0$. For a supermartingale $E[M_\tau] \le M_0$.

Proof. Take $H_k = \mathbf{1}\{\tau \ge k\}$. It is decided by $X_1, \ldots, X_{k-1}$, since $\{\tau \ge k\}$ is the complement of $\{\tau \le k - 1\}$. Then $W_n = M_0 + \sum_{k \le n}\mathbf{1}\{\tau \ge k\}(M_k - M_{k-1}) = M_{\min(\tau, n)}$, the sum telescoping up to $\min(\tau, n)$. By Lemma 1, $E[M_{\min(\tau, n)}] = M_0$ for every $n$, and with $n = K$ this is $E[M_\tau] = M_0$. For a supermartingale each term of the sum has conditional mean at most 0, which gives the inequality. $\square$

This is Durrett's (2019) Theorem 4.4.1 for submartingales. Without a bound on $\tau$ the conclusion can fail.

Example (a fair game with a sure profit, given unlimited time). Start the symmetric walk at $S_0 = 1$ and stop at $\tau$, the first visit to 0. The walk is a martingale and $\tau$ is finite with probability 1, yet $S_\tau = 0$, so $E[S_\tau] = 0 \ne 1 = S_0$. Theorem 2 still holds at every bounded time: $E[S_{\min(\tau, n)}] = 1$ for each $n$. Where does the expectation go? Exact enumeration of the paths in the script gives

$n$ $P(\tau > n)$ $E[S_n \mid \tau > n]$
10 0.2461 4.06
100 0.0796 12.56
1,000 0.0252 39.64

The walks still running are ever fewer and ever farther from 0, and their product $P(\tau > n)\,E[S_n \mid \tau > n] = 1$ carries all the mean. A gambler who plays a fair game until ahead by one unit (here, until the opponent's stake is gone) wins with probability 1 but needs unbounded credit and time, and the expected time is infinite, as the previous section showed.

When may an unbounded $\tau$ be used? The answer is a family of conditions that keep the stopped process from carrying mass off to infinity.

Theorem 3 (optional stopping, general conditions). Let $M$ be a martingale and $\tau$ a stopping time with $P(\tau < \infty) = 1$. Then $E[M_\tau] = M_0$ in each of these cases:

  1. the stopped values are bounded: $\lvert M_{\min(\tau, n)}\rvert \le C$ for all $n$;
  2. $E[\tau] < \infty$ and the increments are conditionally bounded: $E[\lvert M_{n+1} - M_n\rvert \mid X_1, \ldots, X_n] \le C$;
  3. $E\lvert M_\tau\rvert < \infty$ and the values $M_n\mathbf{1}\{\tau > n\}$ are uniformly integrable (a family $Y_n$ is uniformly integrable if $\sup_n E[\lvert Y_n\rvert\mathbf{1}\{\lvert Y_n\rvert > K\}] \to 0$ as $K \to \infty$).

For a nonnegative supermartingale, $E[M_\tau] \le M_0$ for every stopping time, with $M_\tau$ defined as the limit of $M_n$ where $\tau = \infty$.

Proof of case 1. $M_{\min(\tau, n)}$ equals $M_\tau$ on $\{\tau \le n\}$, and both are bounded by $C$, so $\lvert E[M_\tau] - E[M_{\min(\tau, n)}]\rvert \le 2C\,P(\tau > n)$. The right side tends to 0, and $E[M_{\min(\tau, n)}] = M_0$ by Theorem 2. $\square$

Cases 2 and 3 and the statement for nonnegative supermartingales are cited: Durrett (2019) proves them as Theorems 4.8.5, 4.8.2 and 4.8.4, with uniform integrability, Fatou's lemma and the martingale convergence theorem, which this unit does not prove. In the counterexample, case 1 fails because the walk is unbounded above, and case 2 because $E[\tau] = \infty$.

Gambler's ruin and Wald's identity, again

Theorem 1 came from linear recurrences. The martingales give the same answers in a line each, and the argument extends to problems where no recurrence is at hand.

Win probability. Stop the walk at $\tau$, the first visit to 0 or $b$. It stays in $[0, b]$, and $\tau$ is finite by part 1 of Theorem 1. For $p = q$, case 1 of Theorem 3 applied to $S_n$ gives $a = E_a[S_\tau] = b\,w_a$, so $w_a = a/b$. For $p \ne q$, applied to $r^{S_n}$, it gives $r^a = w_a r^b + (1 - w_a)$, so $w_a = (r^a - 1)/(r^b - 1)$.

Duration. For $p = q$, use $S_n^2 - n$ (step variance 1) at the bounded time $\min(\tau, n)$: $E_a[S^2_{\min(\tau, n)}] = a^2 + E_a[\min(\tau, n)]$ by Theorem 2. As $n$ grows, $E_a[\min(\tau, n)] = \sum_{k < n}P_a(\tau > k)$ increases to $E_a[\tau]$, and $\lvert E_a[S^2_\tau] - E_a[S^2_{\min(\tau, n)}]\rvert \le 2b^2P_a(\tau > n) \to 0$. So $E_a[\tau] = E_a[S_\tau^2] - a^2 = b^2\,(a/b) - a^2 = a(b - a)$. For $p \ne q$, the same steps with $S_n - n(p - q)$ give $E_a[S_\tau] - a = (p - q)E_a[\tau]$, which is the formula of part 3 after substituting $E_a[S_\tau] = b\,w_a$. Durrett (2019) proves the symmetric case, both parts, as Theorem 4.8.7, and the asymmetric exit probabilities as Theorem 4.8.9.

The last step holds for any walk, and it has a name.

Theorem 4 (Wald's identity). Let the steps be i.i.d. with $E\lvert X_1\rvert < \infty$ and mean $\mu$, and let $\tau$ be a stopping time with $E[\tau] < \infty$. Then $E[S_\tau - S_0] = \mu\,E[\tau]$.

Proof. At the bounded time $\min(\tau, n)$, Theorem 2 applied to the martingale $S_n - n\mu$ gives $E[S_{\min(\tau, n)} - S_0] = \mu\,E[\min(\tau, n)]$. The right side tends to $\mu\,E[\tau]$, as above. On the left, $S_\tau - S_{\min(\tau, n)} = \sum_{k > n}X_k\mathbf{1}\{\tau \ge k\}$. The indicator $\mathbf{1}\{\tau \ge k\}$ is a function of $X_1, \ldots, X_{k-1}$, hence independent of $X_k$, so $E[\lvert X_k\rvert\mathbf{1}\{\tau \ge k\}] = E\lvert X_1\rvert\,P(\tau \ge k)$. The mean of a sum of countably many nonnegative variables is the sum of their means (the monotone convergence theorem, cited from Durrett, 2019, Theorem 1.5.7), so

$$E\lvert S_\tau - S_{\min(\tau, n)}\rvert \le E\lvert X_1\rvert\sum_{k > n}P(\tau \ge k) \to 0,$$

because $\sum_{k \ge 1}P(\tau \ge k) = E[\tau] < \infty$. Hence $E[S_{\min(\tau, n)}] \to E[S_\tau]$, which also shows that $S_\tau$ has a finite mean. $\square$

Durrett (2019, Theorem 4.8.6) derives it from case 2 of Theorem 3. Conditional Expectation proves the mean of a random sum when the number of terms is independent of the terms, and notes that Wald (1944) obtained the same relation for a number of steps that depends on the terms. Theorem 4 proves the relation for every stopping time with a finite mean, a class that includes such exit times. For the roulette game, $E[S_\tau] - 20 = 40 \times 0.1084 - 20$ and $(p - q)E[\tau] = -297.6/19$ are both a loss of 15.66 units.

A maximal inequality

How likely is a fair game ever to multiply a nonnegative fortune by a large factor? Not very, and the bound needs no assumption beyond fairness.

Theorem 5 (Ville's maximal inequality). Let $M$ be a nonnegative supermartingale, in particular a nonnegative martingale. For every $c > 0$ and every $n$,

$$P\Big(\max_{k \le n}M_k \ge c\Big) \le \frac{M_0}{c}, \qquad\text{and hence}\qquad P\Big(\sup_{k}M_k \ge c\Big) \le \frac{M_0}{c}.$$

Here is the idea. Stop the first time the fortune reaches $c$. On the event that it does, the stopped fortune is at least $c$; it is never negative; and its mean is at most $M_0$.

Proof. Let $\tau$ be the first $k \le n$ with $M_k \ge c$, or $n$ if there is none. It is a stopping time bounded by $n$, so $E[M_\tau] \le M_0$ by Theorem 2. Let $A = \{\max_{k \le n}M_k \ge c\}$. On $A$, $M_\tau \ge c$, and $M_\tau \ge 0$ everywhere, so $c\,P(A) \le E[M_\tau\mathbf{1}_A] \le E[M_\tau] \le M_0$. The events $A_n = \{\max_{k \le n}M_k \ge c\}$ increase with $n$ and their union is $\{M_k \ge c \text{ for some } k\}$, whose probability is therefore the limit of $P(A_n)$ by the continuity of probability (Random Variables and Distribution Functions). The event $\{\sup_k M_k \ge c\}$ can be larger by the paths whose supremum equals $c$ without being reached; applying the bound with $c'$ slightly below $c$ and letting $c' \to c$ covers them. $\square$

Durrett (2019) proves the submartingale form as Theorem 4.4.2 (Doob's inequality) and poses this form as Exercise 4.8.2. Ramdas, Grünwald, Vovk and Shafer (2023, Section 2.5) attribute it to Ville (1939), who called it the theorem of gamblers' ruin: a gambler who starts with one unit and bets until winning the casino's entire capital of $c$ units has little chance of succeeding. The bound is reached when the fortune lands exactly on $c$ when it gets there and is 0 whenever it does not, as Problem 2 shows.

Likelihood ratios are martingales

Here is the bridge to statistics. Two models for the same data give a ratio of probabilities, and under the model in the denominator that ratio is a fair game.

Theorem 6 (likelihood ratio martingales). Let $p_n(x_1, \ldots, x_n)$ and $q_n(x_1, \ldots, x_n)$ be two probability models for the first $n$ observations, for every $n$, each consistent ($\sum_x p_{n+1}(x_1, \ldots, x_n, x) = p_n(x_1, \ldots, x_n)$, and likewise for $q$), with $p_n > 0$ on every sequence. If the data follow $p$, then

$$L_n = \frac{q_n(X_1, \ldots, X_n)}{p_n(X_1, \ldots, X_n)}, \qquad L_0 = 1,$$

is a nonnegative martingale with mean 1. The same holds for densities, with integrals in place of sums.

Proof. Under $p$, the conditional probability that $X_{n+1} = x$ given the history $x_1, \ldots, x_n$ is $p_{n+1}(x_1, \ldots, x_n, x)/p_n(x_1, \ldots, x_n)$. So

$$E[L_{n+1} \mid X_1 = x_1, \ldots, X_n = x_n] = \sum_x \frac{p_{n+1}(\ldots, x)}{p_n(\ldots)}\cdot\frac{q_{n+1}(\ldots, x)}{p_{n+1}(\ldots, x)} = \frac{\sum_x q_{n+1}(\ldots, x)}{p_n(\ldots)} = \frac{q_n(x_1, \ldots, x_n)}{p_n(x_1, \ldots, x_n)}. \qquad \square$$

Three cases matter.

  • Two simple hypotheses. For i.i.d. data with probability mass function or density $f_0$ under the null and $f_1$ under the alternative, $L_n = \prod_{i \le n}f_1(X_i)/f_0(X_i)$, the ratio of The Neyman–Pearson Lemma accumulated over the observations.
  • A mixture alternative. If $q_n = \int\prod_i f_\theta(x_i)\,dH(\theta)$ for a distribution $H$ of the parameter, $q$ is the marginal (prior predictive) probability of the data, and $L_n$ is the Bayes factor of Bayes Factors and Posterior Model Probabilities. So a Bayes factor in favor of an alternative is a martingale under a simple null.
  • The A/B test's discordant pairs. Call a pair discordant if exactly one of its two users clicks, and let the second version "win" it if that user saw version B. If both versions have the same click rate $p$, a discordant pair is a win with probability exactly 1/2, whatever $p$. Let the alternative model give each discordant pair the same probability as the null, $2p(1 - p)$, but make it a win with probability $\theta$, where $\theta$ has the beta distribution with parameters $h$ and $h$. Concordant pairs have the same probability under both models and cancel from the ratio. After $m$ discordant pairs with $k$ wins,

$$\Lambda_n = \frac{1}{(1/2)^m}\int_0^1\theta^k(1 - \theta)^{m - k}\,\frac{\theta^{h-1}(1 - \theta)^{h-1}}{B(h, h)}\,d\theta = 2^m\,\frac{B(k + h,\ m - k + h)}{B(h, h)},$$

where $B$ is the beta function. Since $\Lambda_n$ does not involve $p$, it is a martingale under every null distribution with equal click rates. This is the statistic simulated below.

Corollary 1 (a test that may stop at any time). Let $L_n$ be a nonnegative martingale with $L_0 = 1$ under the null hypothesis. The test that rejects at the first $n$ with $L_n \ge 1/\alpha$ has

$$P_0(\text{ever reject}) \le \alpha.$$

Equivalently, $p_n = \min_{0 \le k \le n}1/L_k$ is a $p$-value that is valid at every stopping time $\tau$: $P_0(p_\tau \le \alpha) \le \alpha$.

Proof. Both events lie inside $\{\sup_k L_k \ge 1/\alpha\}$, whose probability is at most $\alpha$ by Theorem 5. $\square$

Johari, Koomen, Pekelis and Walsh (2022, Definition 1 in the arXiv version) call a process with this property an always valid $p$-value, and they build them from mixtures of likelihood ratios, a construction they trace to Robbins (1970). Ramdas, Grünwald, Vovk and Shafer (2023) call nonnegative martingales with $L_0 = 1$ test martingales. The analyst may look after every observation, stop for any reason, or continue, and the level holds.

Wald's sequential probability ratio test

Corollary 1 gives a test that may never stop when the null is true. The sequential probability ratio test, which Wald (1945) introduced (as Ramdas et al., 2023, and Johari et al., 2022, recount), stops under either hypothesis: for two simple hypotheses, sample until the likelihood ratio leaves an interval $(B, A)$ with $B < 1 < A$; reject the null if it exits above $A$, accept it if it exits below $B$. We abbreviate it SPRT.

Theorem 7 (the SPRT stops and keeps its error bounds). Let $Z_i = \ln[f_1(X_i)/f_0(X_i)]$, and suppose $P(Z_i \ne 0) > 0$ under the hypothesis in force (true under both hypotheses whenever $f_1$ and $f_0$ differ on a set of positive probability). Then:

  1. the test stops with probability 1 and its expected sample size is finite, under $f_0$ and under $f_1$;
  2. its error probabilities $\alpha' = P_0(\text{reject})$ and $\beta' = P_1(\text{accept})$ satisfy $\alpha' \le (1 - \beta')/A \le 1/A$ and $\beta' \le B(1 - \alpha') \le B$.

Proof. (1) $\ln L_n$ is a random walk with steps $Z_i$. Since $P(Z_i \ne 0) > 0$, there is an $\varepsilon > 0$ with $P(Z_i > \varepsilon) = \pi > 0$ or $P(Z_i < -\varepsilon) = \pi > 0$; take the first case, the second being the same with signs reversed. Choose $m$ with $m\varepsilon > \ln A - \ln B$. Then $m$ consecutive steps above $\varepsilon$ carry the walk out of $(\ln B, \ln A)$ from anywhere inside, so, as in part 1 of Theorem 1, $P(\tau > km) \le (1 - \pi^m)^k$ and $E[\tau] \le m/\pi^m$.

(2) Take the discrete case. A sequence $x_1, \ldots, x_n$ on which the test stops at $n$ and rejects has probability $\prod f_1(x_i) = L_n\prod f_0(x_i) \ge A\prod f_0(x_i)$ under the alternative. Adding over all such sequences and all $n$ (the test stops with probability 1 under both hypotheses), $1 - \beta' = P_1(\text{reject}) \ge A\,P_0(\text{reject}) = A\alpha'$. In the same way, on sequences where it accepts, $L_n \le B$, so $\beta' = P_1(\text{accept}) \le B\,P_0(\text{accept}) = B(1 - \alpha')$. With densities the sums are integrals. $\square$

The bounds suggest the boundaries $A = (1 - \beta)/\alpha$ and $B = \beta/(1 - \alpha)$ for target error rates $\alpha$ and $\beta$; they would give the targets exactly if the ratio stopped exactly on a boundary. It overshoots, which makes the true error rates smaller than the bounds in most cases. With these boundaries Theorem 7 still guarantees $\alpha' \le 1/A = \alpha/(1 - \beta)$ and $\beta' \le B = \beta/(1 - \alpha)$.

The expected sample size. Wald's identity applied to the walk $\ln L_n$ gives $E[\ln L_\tau] = E[Z]\,E[\tau]$. Under the null, $E_0[Z] = -D(f_0\,\|\,f_1)$, minus the Kullback–Leibler divergence of Cross-Entropy and Kullback–Leibler Divergence, and under the alternative $E_1[Z] = D(f_1\,\|\,f_0)$. Ignoring the overshoot, $\ln L_\tau$ is $\ln A$ or $\ln B$, so

$$E_0[\tau] \approx \frac{\alpha\ln A + (1 - \alpha)\ln B}{-D(f_0\,\|\,f_1)}, \qquad E_1[\tau] \approx \frac{(1 - \beta)\ln A + \beta\ln B}{D(f_1\,\|\,f_0)}.$$

Example (the A/B test as an SPRT). On the discordant pairs, test $\theta = 1/2$ against the value $\theta_1$ that a second version with click rate 0.42 produces against 0.40: $\theta_1 = 0.42 \times 0.60/(0.42 \times 0.60 + 0.40 \times 0.58) = 0.5207$. With $\alpha = 0.05$ and $\beta = 0.20$ the boundaries are $A = 16$ and $B = 0.2105$. The approximation gives expected numbers of discordant pairs of 1,570 under the null and 2,232 under the alternative. In the simulation (30 seeds, 73,000,000 to 73,000,029, 2,000 tests under each hypothesis), the Type I error rate had median 0.0493 (interquartile range 0.0460 to 0.0524) and the Type II rate 0.192 (0.187 to 0.200). The mean numbers of discordant pairs had medians 1,603 (1,590 to 1,621) and 2,272 (2,253 to 2,301), slightly above the approximation, by the overshoot. A one-sided test of a fixed number of discordant pairs with the same two error rates needs 3,619 of them, by the normal approximation to the binomial. A pair is discordant with probability $2 \times 0.4 \times 0.6 = 0.48$ under the null and 0.484 under the alternative, so by Wald's identity again the sequential test uses about 3,341 pairs on average when the versions are equal and 4,693 when they differ.

Why repeated naive tests reject eventually

Back to the analyst who checks after every batch. The two-proportion statistic is a random walk divided by $\sigma\sqrt{n}$, and a random walk divided by $\sqrt{n}$ does not settle down.

Theorem 8 (repeated significance tests reject with probability 1). Let $X_1, X_2, \ldots$ be i.i.d. with mean 0 and variance $\sigma^2$ in $(0, \infty)$, and $S_n = X_1 + \cdots + X_n$. For every $c$ and every $n_0$,

$$P\big(S_n \ge c\,\sigma\sqrt{n} \text{ for some } n \ge n_0\big) = 1.$$

So a $z$ test at any fixed level, computed after every observation or every batch of a fixed size, rejects a true null hypothesis eventually with probability 1. The same holds with $\sigma$ replaced by the sample standard deviation.

Proof. Let $\varepsilon > 0$ and $B_n = \{S_n \ge (c + \varepsilon)\sigma\sqrt{n}\}$. By the central limit theorem, $P(B_n) \to 1 - \Phi(c + \varepsilon) > 0$. The event that infinitely many $B_n$ occur is the decreasing limit of $\bigcup_{m \ge n}B_m$, each of probability at least $\sup_{m \ge n}P(B_m)$, so by the continuity of probability it has probability at least $1 - \Phi(c + \varepsilon)$. On that event $\limsup_n S_n/(\sigma\sqrt{n}) \ge c + \varepsilon > c$. Now let $E = \{\limsup_n S_n/(\sigma\sqrt{n}) > c\}$. Changing finitely many of the $X_i$ changes $S_n$ by a fixed amount, which divided by $\sqrt{n}$ tends to 0, so $E$ does not depend on any finite number of the variables: it is a tail event. By Kolmogorov's zero-one law a tail event of independent variables has probability 0 or 1 (Durrett, 2019, Theorem 2.5.3, and Example 2.5.2 for this kind of event). We showed $P(E) > 0$, so $P(E) = 1$, and on $E$ the walk exceeds $c\,\sigma\sqrt{n}$ for infinitely many $n$, in particular for some $n \ge n_0$. For batches of size $b$, apply the result to the walk of batch sums, which has i.i.d. steps with variance $b\sigma^2$. With the sample standard deviation $s_n$ in place of $\sigma$, $s_n \to \sigma$ with probability 1 by the strong law of large numbers (Laws of Large Numbers), and the ratio $\sigma/s_n$ does not change whether the $\limsup$ exceeds $c$. $\square$

This is Durrett's (2019) Exercise 3.4.2(a), which asks for exactly this combination of the central limit theorem and the zero-one law. The rate is known exactly. The law of the iterated logarithm (Hartman and Wintner, 1941; Durrett, 2019, Theorem 8.5.2) states that $\limsup_n S_n/(\sigma\sqrt{2n\ln\ln n}) = 1$ with probability 1. So, for every $\varepsilon > 0$, the standardized statistic $z_n = S_n/(\sigma\sqrt{n})$ climbs above $(1 - \varepsilon)\sqrt{2\ln\ln n}$ again and again, and eventually stays below $(1 + \varepsilon)\sqrt{2\ln\ln n}$. A boundary that a true null crosses with probability less than 1 therefore cannot stay at or below $(1 - \varepsilon)\sqrt{2\ln\ln n}$ from some $n$ on, for any $\varepsilon > 0$; in particular the fixed 1.96, and any boundary $c_n$ with $\limsup_n c_n/\sqrt{2\ln\ln n} < 1$, is crossed with probability 1. Conversely, a boundary that stays above $(1 + \varepsilon)\sqrt{2\ln\ln n}$ for all $n \ge n_0$ is crossed after $n_0$ with a probability that tends to 0 as $n_0$ grows.

Example (a mixture boundary on the $z$ scale). For normal observations with known $\sigma$ and unknown mean $\delta$, mix the likelihood ratios $\exp(\delta S_n/\sigma^2 - n\delta^2/(2\sigma^2))$ over a normal distribution for $\delta$ with mean 0 and standard deviation $\tau_0$, and write $\rho = \tau_0^2/\sigma^2$. Completing the square in the Gaussian integral gives

$$L_n = \frac{1}{\sqrt{1 + n\rho}}\exp\Big(\frac{n\rho}{2(1 + n\rho)}\,z_n^2\Big),$$

which the script confirms by numerical integration. By Theorem 6 and Corollary 1 it may be monitored continuously, and $L_n \ge 1/\alpha$ exactly when

$$\lvert z_n\rvert \ge \sqrt{\Big(1 + \frac{1}{n\rho}\Big)\Big(\ln(1 + n\rho) + 2\ln\frac{1}{\alpha}\Big)}.$$

With $\alpha = 0.05$ and $\rho = 10^{-3}$ this boundary is 3.04 at $n = 10^4$, 3.59 at $10^6$ and 4.18 at $10^8$, growing like $\sqrt{\ln n}$. The iterated-logarithm curve $\sqrt{2\ln\ln n}$ is 2.11, 2.29 and 2.41 at the same $n$. The fixed-sample boundary 1.96 is below both, which is Theorem 8 seen from the other side.

Peeking at an A/B test, measured

The script simulated the opening's experiment. Each pair has one user per version; a user clicks with probability 0.40 in both versions. A two-sided two-proportion $z$ test at the 0.05 level (pooled variance) is computed after every 100 pairs, and the experiment stops at the first rejection or at a largest number of pairs. There were 30 seeds (72,000,000 to 72,000,029) with 2,000 experiments each; the table gives medians of the share of experiments that ever rejected.

Largest number of pairs 100 200 500 1,000 2,000 5,000 10,000 20,000
Looks 1 2 5 10 20 50 100 200
Share ever rejecting 0.053 0.085 0.142 0.197 0.250 0.323 0.375 0.427

At 20,000 pairs the interquartile range across seeds is 0.419 to 0.431. A single test at 20,000 pairs rejected in a share with median 0.051 (0.046 to 0.054), as designed. The rate climbs over the whole range simulated, from 0.375 at 100 looks to 0.427 at 200, as it must eventually by Theorem 8, which says that it tends to 1; neither Theorem 8 nor the law of the iterated logarithm says how fast. Johari, Koomen, Pekelis and Walsh (2022, Section 1 of the arXiv version) report that with 10,000 samples the Type I error "can easily increase fivefold"; here, at 10,000 pairs, it is 0.375, seven and a half times the nominal 0.05. The course page Type I and Type II Errors measures the same effect for a $t$ test over 100 observations.

The test martingale. The same experiments were monitored with $\Lambda_n$, the beta mixture on discordant pairs, rejecting when $\Lambda_n \ge 1/\alpha = 20$. Two mixtures were used. With $h = 1$ the mixing distribution of $\theta$ is uniform. With $h = 292$ its standard deviation, $1/(2\sqrt{2h + 1})$, equals the effect the experiment is designed to detect, $\theta_1 - 1/2$ with $\theta_1 = 0.5207$; that rule was fixed before the simulation. Over the full 20,000 pairs, the share of null experiments in which the martingale ever reached 20 had median 0.010 (0.009 to 0.012) with $h = 1$ and 0.021 (0.019 to 0.023) with $h = 292$. Both are below 0.05, as Corollary 1 guarantees, and below it by a margin, because $\Lambda_n$ jumps past 20 rather than landing on it, was checked only every 100 pairs, and the experiments stopped at 20,000 pairs, while the guarantee covers all time.

The price. When version B's click rate is 0.42, the fixed test planned for 80% power (Online Evaluation computes 9,489 users per group) rejected at 9,500 pairs in a share with median 0.800 (0.793 to 0.803). By 9,500 pairs the martingale with $h = 292$ had rejected in 0.517 (0.511 to 0.527) and the one with $h = 1$ in 0.271 (0.266 to 0.277). By 20,000 pairs their power was 0.899 (0.894 to 0.904) and 0.689 (0.683 to 0.694), and the experiments that rejected had stopped at a median of 8,400 pairs (8,300 to 8,575 across seeds) and 11,275 pairs (11,200 to 11,400). Validity at every stopping time costs users at the planned size. In exchange, the analyst may stop early when the effect is large, keep going when it is not, and look as often as wished. The mixture matters: one matched to the effect of interest buys much of the power back.

Example (what "peeking" is, as a multiple-testing problem). Looking 200 times is testing one hypothesis 200 times, with strongly dependent statistics. A Bonferroni correction at $0.05/200$ per look would also control the error (Multiple Testing), but it ignores the dependence and fixes the number of looks in advance. Group sequential designs with planned interim analyses, mentioned in Type I and Type II Errors, spend the error rate across a planned schedule. The martingale tests need no schedule at all.

A search that moves at random is the baseline against which directed search is judged, and gambler's ruin answers its first questions. On a plateau of width $b$ with an improving exit at one end and a worsening exit at the other, sideways moves with random tie-breaking are a symmetric walk; from position $a$ it leaves by the improving end with probability $a/b$ after $a(b - a)$ moves on average (Theorem 1). Hill Climbing treats the shoulder with a wall at one end, where the expected time is $m^2 - i^2$; both grow with the square of the width, which is why the cap on sideways moves matters. The random walk of Fitness Landscapes, along which Weinberger's autocorrelation is measured, and simulated annealing at high temperature in Escaping Local Optima, which is close to a random walk, are the same object.

What is proved here, what is cited, and what the experiments show

Proved on this page: gambler's ruin probabilities and durations, with termination (Theorem 1), and again by martingales; the four random-walk martingales and the betting lemma (Lemma 1); optional stopping for bounded stopping times (Theorem 2) and for bounded stopped processes (Theorem 3, case 1); Wald's identity (Theorem 4, with the monotone convergence theorem cited); Ville's maximal inequality (Theorem 5); likelihood ratios, Bayes factors and the discordant-pair mixture as martingales under the null (Theorem 6), and the anytime-valid test (Corollary 1); termination and the error bounds of the SPRT (Theorem 7); that repeated $z$ tests reject a true null with probability 1 (Theorem 8, with Kolmogorov's zero-one law cited); the normal-mixture boundary.

Cited: optional stopping under the conditions of cases 2 and 3 of Theorem 3 and for nonnegative supermartingales (Durrett, 2019, Theorems 4.8.2, 4.8.4, 4.8.5); Kolmogorov's zero-one law and the law of the iterated logarithm (Durrett, 2019, Theorems 2.5.3 and 8.5.2); the monotone convergence theorem; the strong law of large numbers under a finite mean, used for $s_n \to \sigma$ in Theorem 8 (Laws of Large Numbers states and cites it, and proves it under a finite fourth moment, which covers the bounded steps of the A/B test). The unit avoids measure theory as Random Variables and Distribution Functions explains; the martingales here are defined relative to a sequence of observations and use the conditional expectations of Conditional Expectation.

What the experiments show: in simulation, the roulette game, the SPRT and the A/B test behave as the theorems say. Peeking after every 100 pairs raised the false positive rate to 0.427 by 20,000 pairs; the test martingales stayed at 0.010 and 0.021, at the cost of power at the planned sample size. These are observations of one simulated design.

Worked problems

The four problems are posed on this article's examples, not taken from a course. The script tools/experiments/statistics/random-walks-and-martingales.py checks every number.

Problem 1 (a short game). A player starts with 3 units and stops at 0 or 10, betting one unit at a time. Find the probability of reaching 10 and the expected number of bets (a) in a fair game, (b) when each bet is won with probability 0.6.

Solution. (a) By Theorem 1 with $a = 3$ and $b = 10$, $w_3 = 3/10 = 0.3$ and $e_3 = 3 \times 7 = 21$. (b) Now $r = q/p = 0.4/0.6 = 2/3$, so

$$w_3 = \frac{(2/3)^3 - 1}{(2/3)^{10} - 1} = \frac{-0.7037}{-0.9827} = 0.7161, \qquad e_3 = \frac{3}{q - p} - \frac{10}{q - p}\cdot\frac{1 - (2/3)^3}{1 - (2/3)^{10}} = -15 + 50 \times 0.7161 = 20.81.$$

Here $q - p = -0.2$, so $3/(q - p) = -15$ and $-10/(q - p) = 50$. Wald's identity checks it: $E[S_\tau] - 3 = 10 \times 0.7161 - 3 = 4.161$, and $(p - q)E[\tau] = 0.2 \times 20.81 = 4.161$. The favorable game lasts almost exactly as long as the fair one, 20.81 bets against 21, although its outcome is very different.

Problem 2 (the doubling bet meets Ville's bound). A player with 1 unit bets everything on fair coin flips, doubling or losing all. What is the probability of ever holding 32 units, and what does Theorem 5 say about any strategy with a nonnegative fortune in a fair game?

Solution. The fortune is $2^k$ after $k$ straight wins and 0 after the first loss, a nonnegative martingale. Reaching 32 needs five straight wins, probability $(1/2)^5 = 0.03125$. Theorem 5 with $M_0 = 1$ and $c = 32$ bounds the probability for every strategy by $1/32 = 0.03125$. The doubling bet attains the bound because the fortune lands exactly on 32 and never overshoots it, and because every failure ends at 0, which wastes no expected value; the proof of Theorem 5 shows that equality needs both.

Problem 3 (the SPRT's guaranteed error rates). For the A/B test's SPRT with $A = 16$ and $B = 0.2105$, what error rates does Theorem 7 guarantee, and how do they compare with the simulation?

Solution. Theorem 7 gives $\alpha' \le 1/A = 0.0625$ and $\beta' \le B = 0.2105$, whatever the overshoot. The sharper forms $\alpha' \le (1 - \beta')/A$ and $\beta' \le B(1 - \alpha')$ are the reason the targets 0.05 and 0.20 are nearly met. The simulated rates, 0.0493 and 0.192, are below both bounds, by the overshoot.

Problem 4 (a mixture likelihood ratio against a $p$-value). The statistic is computed for the first time after 100 discordant pairs, of which version B has won 60. Compute the uniform-mixture statistic ($h = 1$) and the two-sided binomial $p$-value of a test planned for exactly 100 discordant pairs. What would the anytime-valid test conclude at this single look?

Solution. With $h = 1$, $B(1, 1) = 1$ and $\Lambda = 2^{100}B(61, 41) = 2^{100}\,60!\,40!/101! = 0.91$. The two-sided binomial $p$-value, $2P(K \ge 60)$ for $K$ binomial with 100 trials and probability 1/2, is 0.0569. The fixed-sample test is close to rejecting at 0.05; the mixture ratio is below 1, so $1/\Lambda_{100} = 1.095$, and the $p$-value of this single look, $\min(1, 1/\Lambda_{100}) = 1$, says the evidence counts for nothing yet against the threshold of 20. It is valid because it is at least the running $p_{100}$ of Corollary 1. That running $p_{100} = \min_{k \le 100}1/\Lambda_k$ itself depends on the order of the wins, not only on the final count: ten wins in the first ten discordant pairs give $\Lambda_{10} = 2^{10}B(11, 1) = 1{,}024/11 = 93.1$, and the test would have stopped there. With 62 wins, $\Lambda = 2.21$. The difference is the price of Corollary 1: a statistic that may be checked at every step must discount any single look, and a uniform mixture spreads its bet over effects as large as $\theta = 1$, which the data rule out.

Summary

Result Statement
Gambler's ruin $w_a = a/b$ or $(r^a - 1)/(r^b - 1)$; $e_a = a(b - a)$ or $\frac{a}{q - p} - \frac{b}{q - p}\cdot\frac{1 - r^a}{1 - r^b}$, $r = q/p$
Martingale $E[M_{n+1} \mid X_1, \ldots, X_n] = M_n$; constant mean
Optional stopping $E[M_\tau] = M_0$ for bounded $\tau$, or bounded stopped values, or $E[\tau] < \infty$ with bounded increments
Wald's identity $E[S_\tau - S_0] = \mu E[\tau]$ when $E[\tau] < \infty$
Ville $P(\sup_k M_k \ge c) \le M_0/c$ for $M \ge 0$
Likelihood ratio a martingale with mean 1 under the null; reject at $L_n \ge 1/\alpha$ at any time
SPRT $\alpha' \le (1 - \beta')/A$, $\beta' \le B(1 - \alpha')$; $E[\tau] \approx$ boundary over divergence
Peeking repeated $z$ tests reject a true null with probability 1; the largest excursions of $z_n$ grow like $\sqrt{2\ln\ln n}$

What we have learned

A random walk is a sum of independent steps, and gambler's ruin gives the chance and the time for it to leave an interval. Martingales are fair games; stopping one at a bounded time cannot change its mean, and the walk from 1 to 0 shows what goes wrong without a bound. Ville's inequality bounds the chance that a nonnegative fair game ever multiplies its stake, and since a likelihood ratio is a fair game under the null hypothesis, it gives tests that may be stopped at any time. Wald's sequential test stops under either hypothesis with guaranteed error bounds and, in the A/B example, used 44% of the fixed sample on average when the versions were equal and 63% when they differed. A naive test checked again and again rejects a true null eventually, and in the simulated A/B test it did so 42.7% of the time by 20,000 pairs.

Random walks and Poisson processes have independent increments. The series of Autocorrelation and Stationarity do not: each value is correlated with the last, and that article measures how much this changes the variance of a mean.

References

  • Durrett, R. (2019). Probability: Theory and Examples (5th ed.). Cambridge University Press. Read in the author's copy: Theorem 1.5.7 (monotone convergence), Theorem 2.5.3 and Example 2.5.2 (Kolmogorov's zero-one law and tail events), Exercise 3.4.2 (the central limit theorem with the zero-one law), Sections 4.1 and 4.2 (conditional expectation and martingales; Theorem 4.2.8, no betting system), Theorem 4.4.1 (bounded optional stopping), Theorem 4.4.2 (Doob's inequality), Section 4.8 (Theorems 4.8.2, 4.8.4, 4.8.5, optional stopping; Theorem 4.8.6, Wald's equation; Theorems 4.8.7 and 4.8.9, symmetric and asymmetric simple random walk; Example 4.8.10, roulette; Exercise 4.8.2, the maximal inequality for nonnegative supermartingales), Theorem 8.5.2 (the law of the iterated logarithm). record · 15 pages
  • Hartman, P., and Wintner, A. (1941). On the law of the iterated logarithm. American Journal of Mathematics, 63(1), 169–176. https://doi.org/10.2307/2371287. Cited as Durrett (2019) cites it, for his Theorem 8.5.2. record
  • Johari, R., Koomen, P., Pekelis, L., and Walsh, D. (2022). Always valid inference: continuous monitoring of A/B tests. Operations Research, 70(3), 1806–1821. https://doi.org/10.1287/opre.2021.2135. Read in the arXiv version, arXiv:1512.04922v3 (Section 1; Definition 1, always valid p-values; the mixture sequential probability ratio test). record
  • Levin, D. A., and Peres, Y. (2017). Markov Chains and Mixing Times (2nd ed., with contributions by E. L. Wilmer). American Mathematical Society. https://doi.org/10.1090/mbk/107. Read in the authors' copy: Proposition 2.1 (gambler's ruin, fair case). record · 3 pages
  • Ramdas, A., Grünwald, P., Vovk, V., and Shafer, G. (2023). Game-theoretic statistics and safe anytime-valid inference. Statistical Science, 38(4), 576–601. https://doi.org/10.1214/23-STS894. Read in the arXiv version, arXiv:2210.01948 (Section 2.5, Ville's theorem and Ville's inequality). record
  • Robbins, H. (1970). Statistical methods related to the law of the iterated logarithm. The Annals of Mathematical Statistics, 41(5), 1397–1409. https://doi.org/10.1214/aoms/1177696786 record
  • Ville, J. (1939). Étude critique de la notion de collectif. Gauthier-Villars, Paris. record
  • Wald, A. (1944). On cumulative sums of random variables. The Annals of Mathematical Statistics, 15(3), 283–296. https://doi.org/10.1214/aoms/1177731235 record · 2 pages
  • Wald, A. (1945). Sequential tests of statistical hypotheses. The Annals of Mathematical Statistics, 16(2), 117–186. https://doi.org/10.1214/aoms/1177731118 record