ConceptTheory & Algos
Chernoff bound
A tail bound providing exponential decay probabilities for sums of independent random variables.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Chernoff bound analysis for hash collision1Chernoff bound application to skip list levels1Chernoff bound for unknown mean with bounds1Dangerous node1Error amplification1Expected run length analysis1Level-1 inequality1Lower tail1Negative association1Randomized load balancing1Sampling theorem1Upper tail1
Lecturers
7Each in their own terms, from the easiest level.
Ryan O'Donnell
A technique using exponential functions and Markov's inequality to bound the tail probabilities of sums of independent random variables.Ankur Moitra
Tom Leighton
A bound that gives an exponentially small upper bound on the probability that the sum of mutually independent random variables exceeds its expected value by a multiplicative factor.Venkatesan Guruswami
Tail bounds used to formally prove that the probability of error decreases exponentially with the number of trials.Srini Devadas
A bound on the tail probabilities of sums of independent random variables.Erik Demaine
A tail bound used to show that the probability of a random variable deviating significantly from its mean is extremely small with high probability.Nikhil Bansal
A technique for bounding the tail distribution of a sum of independent random variables.
Lectures that assume it
2Connections
25The lectures that define it or assume it, and the concepts next to it.