# Simple Analysis of Priority Sampling

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Aug 2023.

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

- [Coupling without Communication and Drafter-Invariant Speculative Decoding](https://mlsanity.com/paper/2408.07978/) (2024)

## Abstract (arXiv)

We prove a tight upper bound on the variance of the priority sampling method (aka sequential Poisson sampling). Our proof is significantly shorter and simpler than the original proof given by Mario Szegedy at STOC 2006, which resolved a conjecture by Duffield, Lund, and Thorup.