Foundations T16 / 27 · Probability and expectation
Four inequalities: the quantitative answer to «how many samples are enough»
Markov uses only non-negativity, Chebyshev adds variance, Hoeffding adds independence — tighter layer by layer, with more premises layer by layer. How many episodes policy evaluation needs has a formula.
One-line takeaway
Sample sizes are not guessed. For the same event «the mean deviates by 0.1», the Markov bound gives 0.75, Chebyshev gives 0.21, Hoeffding gives 0.135, and the measurement is 0.012 — a loose bound is not a useless one; their job is to give a provable lower bound on the sample size.
«Are 100 episodes enough for evaluation?» «Mini-batch of 64 or 256?» — such questions have quantitative answers, and this piece is their source. The more important byproduct: Jensen's inequality is the underlying tool for handling log terms in policy gradients and for KL divergence derivations.
Why this tool exists
You trained a policy, ran 100 episodes, mean return 42.7. The boss asks: is the true expected return above 43? Your only weapons are the sample mean and its variance estimate — to go from sample to population you must bound «the probability of deviating by more than δ», and computing that bound cannot use the sample again (otherwise circular reasoning).
The way out: use only a small amount of information about the population (mean? variance? boundedness?) to get a worst-case bound. The less information you use, the looser the bound; the more you are willing to assume (independence, boundedness), the tighter it gets. The four inequalities are four stops along this trade-off line.
Set up notation first: X is a random variable, μ=E[X], and we want to bound P(X − μ ≥ t), the probability that X exceeds its mean by t or more.
Definitions
Theorems and proofs
Theorem 4.1 Markov's inequality
For X≥0 and t>0: P(X ≥ t) ≤ E[X]/t. Only non-negativity is assumed; nothing else.
Proof
Build the indicator: 1X≥t ≤ X/t holds at every sample point (when X≥t the left side is 1 ≤ X/t; when X<t the left side is 0, trivially).
Take expectations on both sides (expectation preserves order: A≤B implies E[A]≤E[B], immediate from the sup construction of Definition 2.2):
NoteThe proof uses only «non-negativity» and «order preservation of expectation». The price is a very loose bound — it holds for every nonnegative distribution, i.e. the worst case given zero knowledge of the distribution's shape.
Theorem 4.2 Chebyshev's inequality
P(|X−μ| ≥ t) ≤ Var(X)/t².
Proof
Build the nonnegative variable (X−μ)² and apply Markov to it with threshold t²: P((X−μ)² ≥ t²) ≤ E[(X−μ)²]/t².
On the left, the event { (X−μ)² ≥ t² } is the same event as { |X−μ| ≥ t } (monotonicity of a nonnegative function); on the right, E[(X−μ)²] = Var(X). ∎
NoteSpending variance information buys the squaring of t: the deviation probability decays like t² rather than linearly. Note that the entire trick of the proof is rewriting one event as another — «rewrite the event to be bounded as some nonnegative variable exceeding a threshold» is the universal pattern of this family of inequalities.
Theorem 4.3 Jensen's inequality
If f is convex and X integrable, then E[f(X)] ≥ f(E[X]). For concave f the inequality reverses.
Proof
Supporting-line property of convex functions: for any anchor x₀ there is a slope s such that f(x) ≥ f(x₀) + s·(x − x₀) for all x (the tangent lies below a convex function; at nondifferentiable points take a subgradient).
Take the anchor x₀ = E[X]: f(X) ≥ f(E[X]) + s·(X − E[X]).
Take expectations on both sides, using linearity (Theorem 2.1 in T2): E[f(X)] ≥ f(E[X]) + s·(E[X] − E[X]) = f(E[X]). ∎
NoteThe proof's entire ingredients: supporting line + order preservation + linearity. Applications preview: log is concave, so E[log X] ≤ log E[X] — the effective sample size of importance sampling, the nonnegativity of KL divergence, the lower-bounding trick of EM: all the same result in different costumes.
Theorem 4.4 Hoeffding's inequality (statement)
X_1,…,X_n independent, each in [a,b], sample mean X̄, then P(X̄ − μ ≥ t) ≤ exp(−2nt²/(b−a)²).
Proof
The full proof needs Hoeffding's lemma (control of the moment generating function of a bounded variable), beyond this piece's boundary. We only state and use it.
NoteThe reward for two new premises (independence, boundedness): an n-fold exponential speedup. Chebyshev gives n/t²-type decay; Hoeffding gives e−nt²-type. Every guarantee of law-of-large-numbers caliber (Monte Carlo sample sizes, generalization bounds) rests on bounds of this exponential kind.
Work it by hand
A policy with success rate p=0.3; run n=100 episodes to estimate the success rate. What are the upper bounds on «the estimate is too high by more than 0.1» (Markov/Chebyshev/Hoeffding)? To guarantee this probability ≤1%, how large must n be at least?
- Let X̄ = (1/n)ΣX_i, X_i~Bernoulli(p). μ=0.3, Var(X̄) = p(1−p)/n = 0.21/100 = 0.0021.
- Markov: applied directly to the nonnegative variable X̄−μ it gives P(X̄≥0.4) ≤ 0.3/0.4 = 0.75 — a bound above 0.5, because X̄−μ may be negative and Markov does not exploit symmetry. Instead use P(X̄−μ ≥ 0.1) ≤ E[X̄]/(μ+0.1) = 0.75 (this is everything Markov can give).
- [object Object]
- [object Object]
- Sample size: invert Hoeffding. Require e−2n(0.1)² ≤ 0.01 → n ≥ ln(100)/(2·0.01) = 4.605/0.02 ≈ 230.
The three bounds are 0.75 / 0.21 / 0.1353; the measurement (200,000 simulations) is 0.0122. For 1% confidence Hoeffding says n≥230. Reading: all bounds are conservative (the measurement is an order of magnitude below the bounds), but a bound's job is not to predict the measurement — it is to give a provable minimum sample size; without it, n can only be guessed.
Run the numbers
Where the numbers come from
p=0.3, n=100, threshold t=0.1; measurement from 400,000 simulations against the three bounds:
- Measured P(X̄ > 0.4) = 0.01215
- Markov bound 0.750 (non-negativity only) | Chebyshev bound 0.2100 (plus variance) | Hoeffding bound 0.1353 (plus independence and boundedness)
- Sample size by inverting Hoeffding: n ≥ 230 for 99% confidence; n ≥ 346 for 99.9% confidence
Where this shows up
| The object here | The counterpart in RL | Used in |
|---|---|---|
| Hoeffding sample sizes | How many episodes policy evaluation needs, how much traffic an A/B comparison needs | used in → |
| Jensen (log concave) | Handling E[log π] in policy gradients, nonnegativity of KL divergence | used in → |
| Jensen (f convex) | The direction check E[KL] ≥ KL(E[·]) in trust-region derivations | used in → |
| Chebyshev | Mini-batch variance analysis, rough tuning of learning rates | used in → |
Boundaries: where this article stops
Where this piece stops: the proof of Hoeffding's lemma, the tighter Bennett/Bernstein bounds, and the general theory of concentration inequalities (Talagrand) — none covered. Sufficiency criterion: concentration of the mean of independent bounded samples; Hoeffding already gives an engineering-adequate sample size formula.
Self-test: 4 questions
All hand-computation and «find the flaw in this proof» questions — nothing to memorize. Stuck? Go back to the section.
01What premises do Markov, Chebyshev, and Hoeffding each use, and what does each pay for?
Markov: non-negativity → linear-decay bound. Chebyshev: plus variance → t² decay. Hoeffding: plus independence and boundedness → e−nt² exponential decay. Each layer of premises makes the bound an order of magnitude tighter and the scope of application one notch narrower.
02In the proof of Jensen's inequality, what happens to the «supporting line property» at nondifferentiable points?
A convex function has a subgradient at every nondifferentiable point (the subdifferential is nonempty); take any subgradient slope for the supporting line. The proof never relies on differentiability. That is also why Jensen holds for log (differentiable everywhere), |x| (a cusp), and functions of that kind.
03Why is Chebyshev two-sided while Hoeffding is stated one-sided?
Chebyshev's proof applies Markov to (X−μ)², symmetric by construction, and bounds |X−μ|. Hoeffding's proof path is not symmetric, and the one-sided form is tighter; the two-sided version is just the one-sided times 2. In practice one usually cares about one side only (over- or under-estimating), so the one-sided version fits.
04Evaluating a policy with «99% confidence that the mean return is no less than the measurement minus 0.5», rewards in [0,10]: how many episodes are needed?
Invert Hoeffding: n ≥ ln(1/0.01)·(b−a)²/(2t²) = 4.605·100/(2·0.25) = 921. The bound is very conservative (in practice a few dozen episodes often suffice), but it is a provable floor — use it when writing reports; do not guess.