Concentration inequalities: tail bounds without distribution
Tail bounds (Markov, Chebyshev, Hoeffding) tell you how unlikely a deviation is β without knowing the distribution. Cheaper assumptions, looser bounds.
Markov, Chebyshev, Hoeffding β three tail bounds, three levels of structure. Markov needs only $E[X]$. Chebyshev needs the variance. Hoeffding needs independence + bounded support. Each gives an upper bound on $P(X \ge a)$ without committing to a distribution. Used everywhere: PAC learning, A/B testing sample sizes, Monte Carlo error bars, finance risk floors.
β Intro Β· expand
Try first (productive failure)
Before the worked example: spend 60 seconds taking your best shot at this.
A guess is fine β being briefly wrong about a problem makes the explanation
land harder when you read it. This appears once per tutorial; skip
if you already know the trick.
60s
β Try first Β· expand
Worked example
$X$ is non-negative with $E[X] = 4$. What upper bound does Markov's inequality give on $P(X \ge 20)$?
β Worked example Β· expand
Practice 1 of 3Type a fraction, decimal, or expression β mathjs parses it.
β Practice Β· expand
Reflection
Why is Chebyshev so much tighter than Markov for two-sided deviations? When would you reach for Hoeffding instead of CLT for a tail probability β what does Hoeffding give you that the Normal approximation doesn't?