Theorem Statement
Assumptions
- finite variance
Proof Sketch
Apply Markov to the nonnegative random variable (X - mu)^2. The event |X - mu| >= t is the same as (X - mu)^2 >= t^2, so the numerator becomes Var(X) and the denominator becomes t^2.
Proof Obligations
Finite variance and positive threshold
assumptionVerify the variable has finite variance and the deviation threshold is positive before replacing the event |X - mu| >= t by the squared event.
Without finite variance the numerator is not a usable quantity, and a nonpositive threshold makes the displayed tail event meaningless.
- source
- wainwright-2019:sec2.1
Square the deviation before applying Markov
proof stepThe proof works because (X - mu)^2 is nonnegative and the event |X - mu| >= t is equivalent to (X - mu)^2 >= t^2.
Applying Markov directly to X - mu would lose nonnegativity and invalidate the tail-bound argument.
- source
- wainwright-2019:sec2.1
Variance-only information gives polynomial decay
boundaryChebyshev should be used as the variance-only baseline; it cannot deliver the logarithmic finite-sample rates obtained from bounded-variable concentration.
Treating Chebyshev like a sub-Gaussian inequality overstates what the assumptions justify.
Centered deviation form is required
boundaryUse the theorem on deviations from the mean, not raw tails around zero, unless the mean is known and the event has been translated correctly.
Forgetting the centering step can turn a variance bound into a statement about the wrong event.
- source
- wainwright-2019:sec2.1
Source Locators
High-Dimensional Statistics (2019)
proofChapter 2 — Basic tail and concentration bounds
wainwright-2019:ch2
- kind
- chapter
- review
- reviewed / A
- extract
- manual
Chapter-level canonical support for Chebyshev-style tail bounds.
High-Dimensional Statistics (2019)
proofSection 2.1.1 — From Markov to Chernoff
wainwright-2019:sec2.1
- kind
- section
- review
- reviewed / A
- extract
- manual
- number
- 2.1.1
Anchor: From Markov to Chernoff
Reviewed section-level support for deriving Chebyshev as a Markov-style variance tail bound.
Curated Trace
- 1
Variance is the expectation of the squared distance from the mean.
Checkpoint
Confirm the second moment is finite.
- 2Markov templatetool
The squared deviation is nonnegative, so Markov applies.
Checkpoint
Translate |X - mu| >= t into a squared event.
- 3Chebyshev inequalitytheorem
Substituting Var(X) and t^2 gives the polynomial tail bound.
Checkpoint
The bound cannot deliver log(1/delta) sample complexity by itself.
- 4Weak convergence usedownstream
Chebyshev on the sample mean gives the standard weak law route.
Checkpoint
Track the 1/n variance shrinkage, not just the final limit.
Failure Modes
Variance-only information gives polynomial decay
Chebyshev should be used as the variance-only baseline; it cannot deliver the logarithmic finite-sample rates obtained from bounded-variable concentration.
Risk: Treating Chebyshev like a sub-Gaussian inequality overstates what the assumptions justify.
Check: Chebyshev should be used as the variance-only baseline; it cannot deliver the logarithmic finite-sample rates obtained from bounded-variable concentration.
- source
- wainwright-2019:ch2
Centered deviation form is required
Use the theorem on deviations from the mean, not raw tails around zero, unless the mean is known and the event has been translated correctly.
Risk: Forgetting the centering step can turn a variance bound into a statement about the wrong event.
Check: Use the theorem on deviations from the mean, not raw tails around zero, unless the mean is known and the event has been translated correctly.
- source
- wainwright-2019:sec2.1