A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914098987401216 |
|---|---|
| author | Pabbaraju, Chirag Valiant, Gregory Verma, Rishi |
| author_facet | Pabbaraju, Chirag Valiant, Gregory Verma, Rishi |
| contents | This paper revisits the classical problem of determining the bias of a weighted coin, where the bias is known to be either $p = 1/2 + \varepsilon$ or $p = 1/2 - \varepsilon$, while minimizing the expected number of coin tosses and the error probability. The optimal strategy for this problem is given by Wald's Sequential Probability Ratio Test (SPRT), which compares the log-likelihood ratio against fixed thresholds to determine a stopping time. Classical proofs of this result typically rely on analytical, continuous, and non-constructive arguments. In this paper, we present a discrete, self-contained proof of the optimality of the SPRT for this problem. We model the problem as a biased random walk on the two-dimensional (heads, tails) integer lattice, and model strategies as marked stopping times on this lattice. Our proof takes a straightforward greedy approach, showing how any arbitrary strategy may be transformed into the optimal, parallel-line "difference policy" corresponding to the SPRT, via a sequence of local perturbations that improve a Bayes risk objective. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_15790 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses Pabbaraju, Chirag Valiant, Gregory Verma, Rishi Statistics Theory Data Structures and Algorithms This paper revisits the classical problem of determining the bias of a weighted coin, where the bias is known to be either $p = 1/2 + \varepsilon$ or $p = 1/2 - \varepsilon$, while minimizing the expected number of coin tosses and the error probability. The optimal strategy for this problem is given by Wald's Sequential Probability Ratio Test (SPRT), which compares the log-likelihood ratio against fixed thresholds to determine a stopping time. Classical proofs of this result typically rely on analytical, continuous, and non-constructive arguments. In this paper, we present a discrete, self-contained proof of the optimality of the SPRT for this problem. We model the problem as a biased random walk on the two-dimensional (heads, tails) integer lattice, and model strategies as marked stopping times on this lattice. Our proof takes a straightforward greedy approach, showing how any arbitrary strategy may be transformed into the optimal, parallel-line "difference policy" corresponding to the SPRT, via a sequence of local perturbations that improve a Bayes risk objective. |
| title | A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses |
| topic | Statistics Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.15790 |