# Testing exchangeability: fork-convexity, supermartingales, and e-processes

arXiv: https://arxiv.org/abs/2102.00630 · HTML: https://mlsanity.com/paper/2102.00630/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2021.

## Built on by (most cited first, 30 of 32)

- [E-detectors: a nonparametric framework for sequential change detection](https://mlsanity.com/paper/2203.03532/) (2022)
- [Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approach](https://mlsanity.com/paper/2408.07511/) (2024)
- [Sequential Kernelized Independence Testing](https://mlsanity.com/paper/2212.07383/) (2022)
- [WATCH: Adaptive Monitoring for AI Deployments via Weighted-Conformal Martingales](https://mlsanity.com/paper/2505.04608/) (2025)
- [Model-X Sequential Testing for Conditional Independence via Testing by Betting](https://mlsanity.com/paper/2210.00354/) (2022)
- [Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations](https://mlsanity.com/paper/2212.14411/) (2022)
- [A unified framework for bandit multiple testing](https://mlsanity.com/paper/2107.07322/) (2021)
- [Comparing Sequential Forecasters](https://mlsanity.com/paper/2110.00115/) (2021)
- [Huber-Robust Confidence Sequences](https://mlsanity.com/paper/2301.09573/) (2023)
- [On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds](https://mlsanity.com/paper/2504.19952/) (2025)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Theoretical guarantees for change localization using conformal p-values](https://mlsanity.com/paper/2510.08749/) (2025)
- [Testing For Distribution Shifts with Conditional Conformal Test Martingales](https://mlsanity.com/paper/2602.13848/) (2026)
- [The extended Ville's inequality for nonintegrable nonnegative supermartingales](https://mlsanity.com/paper/2304.01163/) (2023)
- [Combining Evidence Across Filtrations](https://mlsanity.com/paper/2402.09698/) (2024)
- [Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation](https://mlsanity.com/paper/2410.15057/) (2024)
- [Distribution-free changepoint localization after sequential change detection](https://mlsanity.com/paper/2606.01256/) (2026)
- [Anytime-valid t-tests and confidence sequences for Gaussian means with unknown variance](https://mlsanity.com/paper/2310.03722/) (2023)
- [Sequential Kernelized Stein Discrepancy](https://mlsanity.com/paper/2409.17505/) (2024)
- [Multi-Armed Sequential Hypothesis Testing by Betting](https://mlsanity.com/paper/2603.17925/) (2026)
- [Betting on Moments: Legendre Jumper Martingales for Online Exchangeability Testing](https://mlsanity.com/paper/2606.20859/) (2026)
- [Conformal testing: binary case with Markov alternatives](https://mlsanity.com/paper/2111.01885/) (2021)
- [Positive Semidefinite Matrix Supermartingales](https://mlsanity.com/paper/2401.15567/) (2024)
- [Deceptive Risk Minimization: Out-of-Distribution Generalization by Deceiving Distribution Shift Detectors](https://mlsanity.com/paper/2509.12081/) (2025)
- [Conformal Blindness: A Note on A-Cryptic change-points](https://mlsanity.com/paper/2601.01147/) (2026)
- [Optimal sequential tests yield log-optimal e-processes](https://mlsanity.com/paper/2605.12720/) (2026)
- [Bet on Features: Anytime-Valid and Feature-Aware Auditing of Conditional Quantile Forecasters](https://mlsanity.com/paper/2607.11653/) (2026)
- [Efficient Online LLM Watermark Detection via Rao-Blackwellized E-Processes](https://mlsanity.com/paper/2607.21958/) (2026)
- [When the Martingale Never Stops Firing: Anytime-Valid Gating on Real Forecast Streams](https://mlsanity.com/paper/2608.30502/) (2026)
- [When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity](https://mlsanity.com/paper/2610.03646/) (2026)

## Abstract (arXiv)

Suppose we observe an infinite series of coin flips X1,X2,ldots, and wish to sequentially test the null that these binary random variables are exchangeable. Nonnegative supermartingales (NSMs) are a workhorse of sequential inference, but we prove that they are powerless for this problem. First, utilizing a geometric concept called fork-convexity (a sequential analog of convexity), we show that any process that is an NSM under a set of distributions, is also necessarily an NSM under their "fork-convex hull". Second, we demonstrate that the fork-convex hull of the exchangeable null consists of all possible laws over binary sequences; this implies that any NSM under exchangeability is necessarily nonincreasing, hence always yields a powerless test for any alternative. Since testing arbitrary deviations from exchangeability is information theoretically impossible, we focus on Markovian alternatives. We combine ideas from universal inference and the method of mixtures to derive a "safe e-process", which is a nonnegative process with expectation at most one under the null at any stopping time, and is upper bounded by a martingale, but is not itself an NSM. This in turn yields a level α sequential test that is consistent; regret bounds from universal coding also demonstrate rate-optimal power. We present ways to extend these results to any finite alphabet and to Markovian alternatives of any order using a "double mixture" approach. We provide an array of simulations, and give general approaches based on betting for unstructured or ill-specified alternatives. Finally, inspired by Shafer, Vovk, and Ville, we provide game-theoretic interpretations of our e-processes and pathwise results.