A GUIDED TOUR OF CHERNOFF BOUNDS

被引：269

作者：

HAGERUP, T

RUB, C

机构：

[1] Fachbereich Informatik, Universität des Saarlandes, D-6600 Saarbrücken, FRG

来源：

INFORMATION PROCESSING LETTERS | 1990年 / 33卷 / 06期

关键词：

Bernoulli trials; Chernoff bounds; coin tossing; probabilistic analysis;

D O I：

10.1016/0020-0190(90)90214-I

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. © 1990.

引用

页码：305 / 308

页数：4

共 7 条

[1] FAST PROBABILISTIC ALGORITHMS FOR HAMILTONIAN CIRCUITS AND MATCHINGS
ANGLUIN, D
VALIANT, LG
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1979, 18 (02) : 155 - 193
[2] A MEASURE OF ASYMPTOTIC EFFICIENCY FOR TESTS OF A HYPOTHESIS BASED ON THE SUM OF OBSERVATIONS
CHERNOFF, H
[J]. ANNALS OF MATHEMATICAL STATISTICS, 1952, 23 (04): : 493 - 507
[3] Erdos P., 1974, PROBABILISTIC METHOD
[4] HOFRI M, 1987, PROBABILISTIC ANAL A
[5] Karp R., 1988, CLASS NOTES U CALIFO
[6] PROBABILISTIC CONSTRUCTION OF DETERMINISTIC ALGORITHMS - APPROXIMATING PACKING INTEGER PROGRAMS
RAGHAVAN, P
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 37 (02) : 130 - 143
[7] VALIANT LG, 1979, 13TH P ANN ACM S THE, P263

← 1 →