X is Binomial(100, 1/2). Compare what Markov, Chebyshev and Hoeffding give for P(X >= 70) against the exact value, and say what each bound is actually using.

X is Binomial(100, 1/2). Compare what Markov, Chebyshev and Hoeffding give for P(X >= 70) against the exact value, and say what each bound is actually using.

Approach: Apply each inequality in turn to the same tail event, compute the exact binomial sum, then compare the orders of magnitude and attribute the gaps to the information each bound uses.

Markov gives 0.714, Chebyshev 0.0625, Hoeffding 3.35 * 10^{-4}, and the exact tail is 3.93 * 10^{-5}. The Markov inequality uses only the mean of 50, giving 50/70 = 0.714, which is worthless at this deviation. The Chebyshev inequality adds the variance of 25 and bounds P(|X - 50| >= 20) by 25/400 = 0.0625. The Hoeffding bound uses that every term is confined to [0,1] and returns exp(-2 * 20^2/100) = e^{-8} = 3.35 * 10^{-4}. That captures the exponential decay. Hoeffding is off by a factor of 8.5 while Chebyshev is off by a factor of 1600. Two moments cannot produce exponential decay, and the moment generating function is what supplies it.

Follow-up: At what deviation size do the Chebyshev and Hoeffding bounds cross?

Key concepts: markov inequality, chebyshev inequality, hoeffding bound, moment generating function.