Chernoff bound

E837386

concentration inequality probabilistic inequality tail bound

The Chernoff bound is a probabilistic inequality that gives exponentially decreasing upper bounds on the tail probabilities of sums of independent random variables.

Try in SPARQL Jump to: Surface forms Statements Referenced by

Observed surface forms (1)

Surface form	Occurrences
Hoeffding inequality	1

Statements (48)

Predicate	Object
instanceOf	concentration inequality ⓘ probabilistic inequality ⓘ tail bound ⓘ
appliesTo	Bernoulli random variables ⓘ Poisson trials ⓘ binomial distribution ⓘ sum of independent random variables ⓘ
assumes	bounded random variables in common forms ⓘ independence of random variables ⓘ
characterizes	lower tail probability ⓘ upper tail probability ⓘ
comparedTo	Chebyshev inequality NERFINISHED ⓘ Hoeffding inequality NERFINISHED ⓘ Markov inequality NERFINISHED ⓘ
field	information theory ⓘ probability theory ⓘ statistics ⓘ theoretical computer science ⓘ
generalizes	Hoeffding inequality in some formulations ⓘ
gives	exponential upper bound on tail probability ⓘ
hasForm	additive Chernoff bound ⓘ multiplicative Chernoff bound NERFINISHED ⓘ two-sided Chernoff bound NERFINISHED ⓘ
namedAfter	Herman Chernoff NERFINISHED ⓘ
property	bounds decay exponentially in the number of trials ⓘ
provides	non-asymptotic tail estimates ⓘ
relatedTo	Chernoff information NERFINISHED ⓘ Cramér–Chernoff method NERFINISHED ⓘ Kullback–Leibler divergence NERFINISHED ⓘ exponential Markov inequality ⓘ large deviations theory ⓘ moment generating function ⓘ
strongerThan	Chebyshev inequality in many settings NERFINISHED ⓘ Markov inequality in many settings ⓘ
typicalStatement	P(X ≤ (1-δ)μ) ≤ exp(-μ g(δ)) for δ ∈ (0,1) ⓘ P(X ≥ (1+δ)μ) ≤ exp(-μ f(δ)) for δ > 0 ⓘ
usedFor	bounding deviation from expectation ⓘ concentration of measure ⓘ derandomization ⓘ error analysis in communication systems ⓘ randomized algorithms analysis ⓘ sample complexity bounds in learning theory ⓘ
usedIn	analysis of randomized algorithms for load balancing ⓘ coding theory ⓘ hashing and balls-into-bins analysis ⓘ hypothesis testing ⓘ network reliability analysis ⓘ queueing theory ⓘ

Referenced by (3)

Full triples — surface form annotated when it differs from this entity's canonical label.

Chernoff information → relatedTo → Chernoff bound ⓘ

Bernstein inequalities → relatedTo → Chernoff bound ⓘ

this entity surface form: Hoeffding inequality

Bernstein inequalities → relatedTo → Chernoff bound ⓘ