Chernoff bound

Applying Markov's inequality to \(e^{X\cdot t}\) for \(t>0\) gives: \[ p\left(X > a\right) = p\left(e^{X\cdot t} > e^{ta}\right) \leq \frac{\mathbb{E}\left[e^{X\cdot t}\right]}{e^{ta}} \]

Why can we apply Markov's inequality here? Because \(e^{tx}\) is monotonically increasing in \(x\), so the same proof goes through.

• stanford cs229 notes
• chernoff hoeffding lecture notes

• hoeffding's inequality – which can also be used to bound the probability that the sum of random variables deviates from the expected value