Exponential Markov bound

Applying Markov's inequality to

e^{tX}

gives

Pr (X \geq x) \leq e^{- t x} M_{X} (t), t > 0.

Optimizing this expression is the basic Chernoff-bound method.

 Ancestors (7)