RobotGuide
Math foundations/Four inequalities: the quantitative answer to «how many samples are enough»

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.

45 min4 theorems9 proof steps4 self-test questions

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):

P(X≥t) = E[1X≥t] ≤ E[X/t] = E[X]/t. ∎

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?

  1. Let X̄ = (1/n)ΣX_i, X_i~Bernoulli(p). μ=0.3, Var(X̄) = p(1−p)/n = 0.21/100 = 0.0021.
  2. 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).
  3. [object Object]
  4. [object Object]
  5. Sample size: invert Hoeffding. Require e−2n(0.1)² ≤ 0.01 → n ≥ ln(100)/(2·0.01) = 4.605/0.02 ≈ 230.
Answer

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 hereThe counterpart in RLUsed in
Hoeffding sample sizesHow many episodes policy evaluation needs, how much traffic an A/B comparison needsused in →
Jensen (log concave)Handling E[log π] in policy gradients, nonnegativity of KL divergenceused in →
Jensen (f convex)The direction check E[KL] ≥ KL(E[·]) in trust-region derivationsused in →
ChebyshevMini-batch variance analysis, rough tuning of learning ratesused 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.

Up next

The full series · 27 articles

T1The Matrix Is a Ledger for Rotation≈ 25 minT2From Slope to Gradient: The First Line of Every Robot Learning Algorithm≈ 25 minT3Vectors and forces: the physical reading of the dot productAbout 20 minT4Two Rulers and a Better Rulerabout 25 minT5The Ledger of One Motor Revolution: Radians, Speed, and Powerabout 20 minT6Complex multiplication is rotation: the one-dimensional version of quaternionsAbout 20 minT7Bases and coordinates: why robots put everything in matrices45 minT8Matrix Multiplication: Chaining Transformations, Not a Table OperationAbout 40 minT9The Jacobian: Rotate a Joint One Degree — How Far Does the End Effector Move?About 45 minT10Eigenvectors: The Directions a Matrix Dare Not Touchabout 45 minT11SVD and the Pseudoinverse: When There Is No Exact Solution, Find the Nearest Oneabout 50 minT12Taylor expansion: putting a straight line to work in place of a curveAbout 40 minT13Probability spaces: why «random» needs axioms50 minT14Expectation: A Rigorous Construction of «Average»About 55 minT15Conditional Expectation: What the Vertical Bar Really Means≈ 60 minT16Four inequalities: the quantitative answer to «how many samples are enough»45 minT17Norms and fixed points: where «it always converges» comes from55 minT18Markov Chains: When the Time Average Equals the Ensemble Averageabout 55 minT19The Mathematical Construction of the MDP: What One Axiom Is Worthabout 50 minT20Dynamic Programming: The Accounting for Two Iterations≈ 50 minT21Optimization: why constraints cannot rely on penalties aloneAbout 55 minT22Stochastic Approximation: Every Term in the Learning-Rate Formulaabout 55 minT23The Mathematics of Contact: Hertz Theoryabout 45 minT24Friction and the Friction Cone: The Geometry of Constraintsabout 40 minT25Force Closure and Grasp Metrics: ε Is a Linear ProgramAbout 50 minT26Contact Kinematics: Why Rolling Is Not «Sliding Along»≈ 45 minT27Slip detection: from «I felt it» to «I computed it»About 50 min