A guided tour of Chernoff bounds
作者： Torben Hagerup , Christine Rüb
DOI: 10.1016/0020-0190(90)90214-I
关键词: Series (mathematics) 、 Bernoulli trial 、 Random variable 、 Mathematics 、 Mathematical proof 、 Probabilistic analysis of algorithms 、 Zero–one law 、 Chernoff bound 、 Combinatorics 、 Coin flipping
摘要: Abstract We give elementary derivations of the various inequalities collectively known as Chernoff bounds. bounds are strong upper on probability obtaining very few or many heads in series independent coin tossings. This note aims at making results and their proofs accessible to a wider audience; it contains little no new material.
acm.org
elsevier.com
sci-hub.se 参考文章(6)
Joel Spencer, Probabilistic Methods in Combinatorics ,(1974)
Micha Hofri, Probabilistic analysis of algorithms ,(1987)
L. G. Valiant, G. J. Brebner, Universal schemes for parallel communication Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81. pp. 263- 277 ,(1981) , 10.1145/800076.802479
Herman Chernoff, A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations Annals of Mathematical Statistics. ,vol. 23, pp. 493- 507 ,(1952) , 10.1214/AOMS/1177729330
D. Angluin, L.G. Valiant, Fast probabilistic algorithms for hamiltonian circuits and matchings Journal of Computer and System Sciences. ,vol. 18, pp. 155- 193 ,(1979) , 10.1016/0022-0000(79)90045-X
Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs Journal of Computer and System Sciences. ,(1988) , 10.1016/0022-0000(88)90003-7