Lectures & Tutorials
Cheat Sheet: Tail Bounds, T11.9 (bonus)
Part of the series Quantum Error Mitigation (Boulder Summer School 2023).
Also published as a tech note; please cite that.
A compact reference table of probability tail bounds used to reason about sampling error, such as how many shots are needed for a confidence interval on a mean. Each inequality is listed with its conditions, common form, alternate forms and sources, with brief notes on when to use which.
- Single-variable bounds: Markov, reverse Markov, Chebyshev, Cantelli, Chernoff, Jensen
- Sums of independent variables: Hoeffding's lemma, Chernoff-Hoeffding, Azuma, laws of large numbers
- Advanced bounds: Bennett, Bernstein, Efron-Stein and McDiarmid
- Practical note on the number of samples needed for a 1-α confidence interval
Summary and key points drafted by a language model from the slides, not yet reviewed by me. The slides are the source.
Cite
@techreport{minevndt119,
author = {Zlatko K. Minev},
title = {{Concentration Inequalities and Tail Bounds}},
type = {Technical Note},
number = {T11.9},
institution = {Zlatko's Quantum Notebook},
url = {https://zlatko-minev.github.io/zlatko-minev-quantum-repository/items/t11-9-concentration-inequalities-and-tail-bounds/}
}Reuse
Unless a deck says otherwise, the slides and notes here are © Zlatko K. Minev and shared under CC BY-NC-ND 4.0: you're welcome to read, download and share them, unchanged and non-commercially, with credit and a link back. Commercial use or a reworked slide or figure in your own talk, course or paper needs permission; please ask, the answer is usually yes. If you use something in teaching or a publication, I'd love a short note telling me where.
Some slides include figures, photos, logos or excerpts from other people and institutions, credited where they appear. Those aren't mine to license, so please ask the original source. Spotted a missing credit? Tell me and I'll fix it.
