A guided tour of Chernoff bounds. (English) Zbl 0702.60021

Summary: We give elementary derivations of the various inequalities collectively known as Chernoff bounds. Chernoff bounds are strong upper bounds on the probability of obtaining very few or very many heads in series of independent coin tossings. This note aims at making known results and their proofs accessible to a wider audience; it contains little or no new material.


60E15 Inequalities; stochastic orderings
Full Text: DOI


[1] Angluin, D.; Valiant, L.G., Fast probabilistic algorithms for Hamiltonian circuits and matchings, J. comput. system sci., 18, 155-193, (1979) · Zbl 0437.05040
[2] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. math. statist., 23, 493-507, (1952) · Zbl 0048.11804
[3] Erdös, P.; Spencer, J., Probabilistic methods in combinatorics, (1974), Academic Press New York · Zbl 0308.05001
[4] Hofri, M., Probabilistic analysis of algorithms, (1987), Springer New York
[5] Karp, R.M., Probabilistic analysis of algorithms, () · Zbl 0391.90090
[6] Raghavan, P., Probabilistic construction of deterministic algorithms: approximating packing integer programs, J. comput. system sci., 37, 130-143, (1988) · Zbl 0659.90066
[7] Valiant, L.G.; Brebner, G.J., Universal schemes for parallel communication, Proc. 13th ann. ACM symp. on theory of computing, 263-277, (1979)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.