Tech Notes
Concentration Inequalities and Tail Bounds
A compact cheat sheet collecting probability bounds with their conditions, standard forms and references. It covers single-variable bounds, bounds on sums of independent variables and the laws of large numbers, and more advanced inequalities, with short notes on when each applies, such as how many samples a Hoeffding confidence interval needs.
- 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, McDiarmid
- Usage notes and core references
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.
