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.
โ 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?