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

Hagerup, Torben; Rüb, Christine

Inf. Process. Lett. 33, No. 6, 305-308 (1990).

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.

MSC:

60E15

Inequalities; stochastic orderings

Keywords:

Bernoulli trials; Chernoff bounds; coin tossings

References:

[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)