2021/09/10 by Shubham Anand Jain, Jain, Shubham Anand, Rohan Shah +17 · 1 citation
Business, Management and Accounting · Decision Sciences · Mathematics · #Algorithm #Applications (stat.AP) #Applied mathematics #Auction Theory and Applications #Combinatorics #Computer science #Confidence interval #Consumer Market Behavior and Pricing #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Logarithm #Machine Learning (stat.ML) #Martingale (probability theory) #Mathematical analysis #Mathematics #Methodology (stat.ME) #Mode (computer interface) #Probability and Risk Models #Sample size determination #Sequence (biology) #Statistics #Statistics Theory (math.ST) #math.ST #stat.AP #stat.ME #stat.ML #stat.TH
paper · pdf · doi:10.48550/arxiv.2109.05047
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2021/09/10 · arxiv created 2022/04/11 · arxiv updated 2022/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We consider the problem of correctly identifying the mode 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.