# Near-optimal algorithms for private estimation and sequential testing of collision probability

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 36 references that are in the map.
- First posted on arXiv 18 Apr 2025.

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

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication](https://mlsanity.com/paper/1802.04705/) (2018)
- [Testing Identity of Structured Distributions](https://mlsanity.com/paper/1410.2266/) (2014)
- [Test without Trust: Optimal Locally Private Distribution Testing](https://mlsanity.com/paper/1808.02174/) (2018)
- [Frequency Estimation under Local Differential Privacy [Experiments, Analysis and Benchmarks]](https://mlsanity.com/paper/2103.16640/) (2021)
- [Private and Communication-Efficient Algorithms for Entropy Estimation](https://mlsanity.com/paper/2305.07751/) (2023)

## Abstract (arXiv)

We present new algorithms for estimating and testing collision probability, a fundamental measure of the spread of a discrete distribution that is widely used in many scientific fields. We describe an algorithm that satisfies (α, β)-local differential privacy and estimates collision probability with error at most ε using tildeOleft(fraclog(1/β)α2 ε2right) samples for α ≤ 1, which improves over previous work by a factor of frac1α2. We also present a sequential testing algorithm for collision probability, which can distinguish between collision probability values that are separated by ε using tildeO(frac1ε2) samples, even when ε is unknown. Our algorithms have nearly the optimal sample complexity, and in experiments we show that they require significantly fewer samples than previous methods.