Paper
Fast Algorithms for Exact Confidence Intervals in Randomized Experiments with Binary Outcomes
Authors
Peng Zhang
Abstract
We construct exact confidence intervals for the average treatment effect in randomized experiments with binary outcomes using sequences of randomization tests. Our approach does not rely on large-sample approximations and is valid for all sample sizes. Under a balanced Bernoulli design or a matched-pairs design, we show that exact confidence intervals can be computed using only $O(\log n)$ randomization tests, yielding an exponential reduction in the number of tests compared to brute-force. We further prove an information-theoretic lower bound showing that this rate is optimal. In contrast, under balanced complete randomization, the most efficient known procedures require $O(n\log n)$ randomization tests (Aronow et al., 2023), establishing a sharp separation between these designs. In addition, we extend our algorithm to general Bernoulli designs using $O(n^2)$ randomization tests.
Metadata
Related papers
Fractal universe and quantum gravity made simple
Fabio Briscese, Gianluca Calcagni • 2026-03-25
POLY-SIM: Polyglot Speaker Identification with Missing Modality Grand Challenge 2026 Evaluation Plan
Marta Moscati, Muhammad Saad Saeed, Marina Zanoni, Mubashir Noman, Rohan Kuma... • 2026-03-25
LensWalk: Agentic Video Understanding by Planning How You See in Videos
Keliang Li, Yansong Li, Hongze Shen, Mengdi Liu, Hong Chang, Shiguang Shan • 2026-03-25
Orientation Reconstruction of Proteins using Coulomb Explosions
Tomas André, Alfredo Bellisario, Nicusor Timneanu, Carl Caleman • 2026-03-25
The role of spatial context and multitask learning in the detection of organic and conventional farming systems based on Sentinel-2 time series
Jan Hemmerling, Marcel Schwieder, Philippe Rufin, Leon-Friedrich Thomas, Mire... • 2026-03-25
Raw Data (Debug)
{
"raw_xml": "<entry>\n <id>http://arxiv.org/abs/2602.20498v1</id>\n <title>Fast Algorithms for Exact Confidence Intervals in Randomized Experiments with Binary Outcomes</title>\n <updated>2026-02-24T02:53:34Z</updated>\n <link href='https://arxiv.org/abs/2602.20498v1' rel='alternate' type='text/html'/>\n <link href='https://arxiv.org/pdf/2602.20498v1' rel='related' title='pdf' type='application/pdf'/>\n <summary>We construct exact confidence intervals for the average treatment effect in randomized experiments with binary outcomes using sequences of randomization tests. Our approach does not rely on large-sample approximations and is valid for all sample sizes. Under a balanced Bernoulli design or a matched-pairs design, we show that exact confidence intervals can be computed using only $O(\\log n)$ randomization tests, yielding an exponential reduction in the number of tests compared to brute-force. We further prove an information-theoretic lower bound showing that this rate is optimal. In contrast, under balanced complete randomization, the most efficient known procedures require $O(n\\log n)$ randomization tests (Aronow et al., 2023), establishing a sharp separation between these designs. In addition, we extend our algorithm to general Bernoulli designs using $O(n^2)$ randomization tests.</summary>\n <category scheme='http://arxiv.org/schemas/atom' term='stat.ME'/>\n <published>2026-02-24T02:53:34Z</published>\n <arxiv:primary_category term='stat.ME'/>\n <author>\n <name>Peng Zhang</name>\n </author>\n </entry>"
}