# PAC Mode Estimation using PPR Martingale Confidence Sequences

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 29 references that are in the map.
- First posted on arXiv 10 Sep 2021.

## Builds on (most cited first, 7 of 7)

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Confidence sequences for sampling without replacement](https://mlsanity.com/paper/2006.04347/) (2020)
- [Sample Complexity for Winner Prediction in Elections](https://mlsanity.com/paper/1502.04354/) (2015)
- [Sequential Mode Estimation with Oracle Queries](https://mlsanity.com/paper/1911.08197/) (2019)
- [YODA: Enabling computationally intensive contracts on blockchains with Byzantine and Selfish nodes](https://mlsanity.com/paper/1811.03265/) (2018)

## Built on by (most cited first, 5 of 5)

- [Optimal Self-Consistency for Efficient Reasoning with Large Language Models](https://mlsanity.com/paper/2511.12309/) (2025)
- [Optimal Bayesian Stopping for Efficient Inference of Consistent LLM Answers](https://mlsanity.com/paper/2602.05395/) (2026)
- [Identifying Copeland Winners in Dueling Bandits with Indifferences](https://mlsanity.com/paper/2310.00750/) (2023)
- [Strategic Self-Consistency](https://mlsanity.com/paper/2609.30352/) (2026)
- [Adaptive Self-Consistency: From Black-Box Sampling to Distribution-Valued Feedback](https://mlsanity.com/paper/2609.38931/) (2026)

## Abstract (arXiv)

We consider the problem of correctly identifying the textitmode of a discrete distribution P with sufficiently high probability by observing a sequence of i.i.d. samples drawn from P. This problem reduces to the estimation of a single parameter when P has a support set of size K = 2. After noting that this special case is tackled very well by prior-posterior-ratio (PPR) martingale confidence sequences citepwaudby-ramdas-ppr, we propose a generalisation to mode estimation, in which P may take K ≥ 2 values. To begin, we show that the "one-versus-one" principle to generalise from K = 2 to K ≥ 2 classes is more efficient than the "one-versus-rest" alternative. We then prove that our resulting stopping rule, denoted PPR-1v1, is asymptotically optimal (as the mistake probability is taken to 0). PPR-1v1 is parameter-free and computationally light, and incurs significantly fewer samples than competitors even in the non-asymptotic regime. We demonstrate its gains in two practical applications of sampling: election forecasting and verification of smart contracts in blockchains.