Sequential Monte Carlo testing by betting

Lasse Fischer, Aaditya RamdasJournal of the Royal Statistical Society Series B (Statistical Methodology) 2025 · DOI

TL;DR

This paper introduces a novel framework for sequential Monte Carlo (SMC) hypothesis testing, allowing for continuous monitoring and early stopping without sacrificing statistical validity. By framing hypothesis testing as a "betting game," the authors develop "anytime-valid" p-values and e-values that are more efficient and flexible than traditional methods, particularly for permutation tests.

What Problem Does This Paper Address?

Traditional Monte Carlo (MC) tests, like permutation tests, involve generating a fixed number of resampled datasets to test a null hypothesis (e.g., exchangeability of data). This fixed number can be computationally inefficient, especially when the evidence against the null is strong or weak early on. While sequential MC tests exist, they often rely on prespecified stopping rules, meaning their validity is only guaranteed at those specific points. This paper addresses the need for SMC tests that can be monitored at any time, providing valid statistical guarantees regardless of when the test is stopped, and aims to reduce computational cost by stopping early when possible.

Methods

The core innovation lies in framing hypothesis testing as a "betting game" where a gambler's wealth represents evidence against the null hypothesis. The authors introduce "test martingales," which are nonnegative martingales with an initial value of one under the null hypothesis. These martingales are constructed using betting strategies that are designed to increase wealth when the null is likely false.

Key techniques include:

  • Testing by Betting: A gambler places bets on outcomes related to test statistics. The gambler's wealth process is a test martingale, ensuring that its expected value is at most one under the null hypothesis.
  • Anytime-Valid Inference: The wealth process allows for the calculation of p-values or e-values at any stopping time, even if that time was not decided in advance. This is achieved through the optional stopping theorem.
  • Log-Optimal Betting Strategy: To guide the betting strategies, the authors derive an "oracle" log-optimal strategy that maximizes the expected logarithm of wealth, a standard objective in betting and information theory.
  • Binomial and Binomial Mixture Strategies: These are practical implementations of the betting framework. The binomial strategy uses a fixed parameter, while the binomial mixture strategy averages over multiple binomial strategies, allowing for more sophisticated control over resampling risk and better asymptotic behavior.
  • Generalization of Existing Tests: The framework is shown to generalize classical permutation tests and the Besag-Clifford sequential test, providing anytime-valid versions of these methods.

Datasets

The paper uses simulated data for experiments and two real-world datasets:

  • Simulated Data: Used to compare the performance of various strategies under different scenarios (e.g., varying strengths of the alternative hypothesis, different significance levels).
  • Real Data 1: A treatment vs. control trial dataset (previously used in Ding [8] and Rosenbaum [28]) for testing Fisher's sharp null hypothesis.
  • Real Data 2: The Capital bikeshare dataset, used for testing conditional independence under a "model-X" framework (following Grünwald et al. [12] and Berrett et al. [2]).

Key Insights and Ideas

  • Framing Hypothesis Testing as Betting: This novel perspective provides a powerful and intuitive way to construct sequential, anytime-valid tests. The gambler's wealth directly translates to evidence against the null.
  • Anytime-Valid Guarantees: The ability to stop at any time and still have valid statistical guarantees is a significant improvement over traditional methods with fixed stopping rules.
  • Efficiency Gains: The proposed strategies can substantially reduce the number of permutations needed to reach a decision, saving computational resources.
  • Resampling Risk Control: The binomial mixture strategy offers a way to control resampling risk, ensuring that repeated runs of the test on the same data are likely to yield the same decision.
  • Generalization of Classical Methods: The framework unifies and extends existing sequential testing procedures, offering a more principled approach.

Key Results

  • Anytime-Valid Generalizations: The paper provides anytime-valid generalizations of the classical permutation p-value and the Besag-Clifford p-value.
  • Reduced Permutations: Simulations show that the proposed binomial and binomial mixture strategies can significantly reduce the number of permutations required for a decision compared to the Besag-Clifford method, often with comparable or slightly lower power.
  • Power Improvement with Stochastic Rounding: Applying stochastic rounding (a randomized technique) can recover power losses in some scenarios, making the binomial mixture strategy highly competitive.
  • Zero Resampling Risk: The binomial mixture strategy with a uniform working prior can achieve zero resampling risk for a range of parameter values.
  • Real Data Performance: The methods perform well on real datasets, demonstrating their practical applicability. For instance, in the bikeshare data, the strategies rejected the null hypothesis quickly.

Limitations and Future Work

  • Oracle Log-Optimal Strategy: The derived log-optimal strategy relies on knowing the true distribution of the limiting permutation p-value, which is generally unknown. The paper proposes "mimicked" log-optimal strategies using working priors as a practical solution.
  • Asymptotic Behavior: While the strategies are anytime-valid, the wealth accumulation can slow down significantly at later stages, as shown by the asymptotic behavior of log-optimal bets.
  • Future Work: The authors suggest exploring applications of their framework to multiple testing problems.

Summary updated

Abstract

Abstract In a Monte Carlo test, the observed dataset is fixed, and several resampled or permuted versions of the dataset are generated in order to test a null hypothesis that the original dataset is exchangeable with the resampled/permuted ones. Sequential Monte Carlo tests aim to save computational resources by generating these additional datasets sequentially one by one and potentially stopping early. While earlier tests yield valid inference at a particular prespecified stopping rule, our work develops a new anytime-valid Monte Carlo test that can be continuously monitored, yielding a p-value or e-value at any stopping time possibly not specified in advance. It generalizes the well-known method by Besag and Clifford, allowing it to stop at any time, but also encompasses new sequential Monte Carlo tests that tend to stop sooner under the null and alternative without compromising power. The core technical advance is the development of new test martingales for testing exchangeability against a very particular alternative based on a testing by betting technique. The proposed betting strategies are guided by the derivation of a simple log-optimal betting strategy, have closed-form expressions for the wealth process, provable guarantees on resampling risk, and display excellent power in practice.
BibTeX
@article{fischer2025sequential,
  author = {Lasse Fischer and Aaditya Ramdas},
  title = {{Sequential Monte Carlo testing by betting}},
  journal = {Journal of the Royal Statistical Society Series B (Statistical Methodology)},
  year = {2025},
  doi = {10.1093/jrsssb/qkaf014},
}
Figure