Chernoff Bound

An exponential upper bound on the tail probability of a sum of random variables obtained by optimizing Markov's inequality applied to a moment-generating function; it quantifies how unlikely large deviations are.

An exponential upper bound on tail probabilities for random sums or aggregates obtained by applying Markov's inequality to a moment-generating function (MGF) and optimizing the exponential tilt: for S a sum, P(S ≥ t) ≤ inf_{s>0} e^{-s t} E[e^{s S}].