Wald's Sequential Probability Ratio Test (SPRT)

Let $\mathcal{A} = \{(y_1, \ldots, y_N) : g_{\mathrm{SPRT}} = 1\}$ denote the acceptance region for $\mathcal{H}_1$. By definition, $$P_f = \int_{\mathcal{A}} f_0^{\otimes N}(\mathbf{y}) d\mathbf{y}, \qquad P_d = \int_{\mathcal{A}} f_1^{\otimes N}(\mathbf{y}) d\mathbf{y}.$$

On $\mathcal{A}$ we have $\ell^{(N)} \geq A$, which means $\prod_{i=1}^N f_1(y_i) \geq e^A \prod_{i=1}^N f_0(y_i)$. Therefore $f_1^{\otimes N}(\mathbf{y}) \geq e^A f_0^{\otimes N}(\mathbf{y})$ on $\mathcal{A}$.

Integrating both sides over $\mathcal{A}$ against Lebesgue measure, $$P_d = \int_{\mathcal{A}} f_1^{\otimes N} \geq e^A \int_{\mathcal{A}} f_0^{\otimes N} = e^A P_f,$$ so $P_f \leq e^{-A} P_d \leq e^{-A}$.

Repeat on $\mathcal{A}^c = \{g_{\mathrm{SPRT}} = 0\}$: on this event $\ell^{(N)} \leq B$, i.e., $f_0^{\otimes N} \geq e^{-B} f_1^{\otimes N}$. Integrating yields $1 - P_f \geq e^{-B}(1 - P_d)$, or $1 - P_d \leq e^{B}(1 - P_f) \leq e^{B}$.

Ignoring the excess over the boundary replaces the inequalities by equalities, giving $e^{A} = P_d/P_f$ and $e^{B} = (1-P_d)/(1-P_f)$. Substituting $P_f = \alpha$, $1 - P_d = \beta$ yields the stated formulas. $\blacksquare$

Write $S_N = \sum_{i=1}^\infty X_i \mathbb{1}\{N \geq i\}$. Taking expectations (Fubini is justified by $\mathbb{E}\sum_i |X_i| \mathbb{1}\{N \geq i\} = \mathbb{E}[|X_1|] \cdot \mathbb{E}[N] < \infty$), $$\mathbb{E}[S_N] = \sum_{i=1}^\infty \mathbb{E}[X_i \mathbb{1}\{N \geq i\}].$$

Since $\{N \geq i\} = \{N \leq i-1\}^c$ is measurable with respect to $X_1, \ldots, X_{i-1}$, it is independent of $X_i$. Hence $\mathbb{E}[X_i \mathbb{1}\{N \geq i\}] = \mu \cdot \Pr(N \geq i)$.

Using $\mathbb{E}[N] = \sum_{i=1}^\infty \Pr(N \geq i)$, $$\mathbb{E}[S_N] = \mu \sum_{i=1}^\infty \Pr(N \geq i) = \mu \cdot \mathbb{E}[N]. \quad \blacksquare$$

The increments are i.i.d.\ with mean $\mathbb{E}_i[\ell(Y_1)] = D_{i}$ under $\mathcal{H}_i$. The stopping time $N$ has finite mean (this requires a separate argument, e.g., the LLR random walk has nonzero drift so $N$ has exponential tails). By TWald's Identity, $$\mathbb{E}_i[\ell^{(N)}] = D_{i} \cdot \mathbb{E}_i[N].$$

Ignoring the excess over the boundary, $\ell^{(N)} \approx A$ when the SPRT accepts $\mathcal{H}_1$ and $\ell^{(N)} \approx B$ when it accepts $\mathcal{H}_0$. Under $\mathcal{H}_0$, acceptance of $\mathcal{H}_1$ occurs with probability $\alpha$, so $$\mathbb{E}_0[\ell^{(N)}] \approx \alpha A + (1-\alpha) B.$$ Under $\mathcal{H}_1$, acceptance of $\mathcal{H}_0$ occurs with probability $\beta$, so $$\mathbb{E}_1[\ell^{(N)}] \approx (1-\beta) A + \beta B.$$

Combining with Wald's identity, $$\mathbb{E}_0[N] \approx \frac{\alpha A + (1-\alpha) B}{D_{0}}, \quad \mathbb{E}_1[N] \approx \frac{(1-\beta) A + \beta B}{D_{1}}.$$ Note that $D_{0} < 0$, while the numerator (dominated by $(1-\alpha)B < 0$) is also negative, so $\mathbb{E}_0[N] > 0$. $\blacksquare$

Consider the Bayesian problem with prior $(\pi_0, \pi_1)$, cost $c$ per sample, and $0$-$1$ loss for wrong decisions. The optimal stopping rule compares the posterior to two thresholds that depend on the sampling cost.

A direct calculation shows that the posterior-based thresholds are equivalent to LLR-based thresholds, so the SPRT is the optimal Bayes rule for some $(c, \pi_0, \pi_1)$.

By a duality between the Bayes and minimax formulations (cf. Siegmund 1985), the SPRT that achieves error levels $(\alpha, \beta)$ with the Wald thresholds also minimizes $\mathbb{E}_i[N]$ over all tests with those error levels. Full proof requires the theory of optimal stopping; see Siegmund for a modern treatment. $\blacksquare$