Chapter map

1. 1. Loss
2. 2. Single hypothesis
3. 3. Deviation
4. 4. Sample size
5. 5. Single bound
6. 6. Hypothesis class
7. 7. Union bound
8. 8. Numerical value
9. 9. Confidence
10. 10. Solve epsilon
11. 11. Log term
12. 12. Gap result
13. 13. Target gap
14. 14. Sample formula
15. 15. Assumption audit
16. 16. Claim

Visit the How Mathematics Works hub for the wider series and its connections to education, reasoning, science, computing, design and careers.

---

1. Loss

A small example makes the mechanism visible. Use independent losses in [0,1].

A concrete situation

Each summand has range length one.

What the mathematics does not license

Unbounded loss needs another inequality or transformation. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record range. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

2. Single hypothesis

This is where modelling choices begin to affect evidence. Fix one hypothesis before examining the sample.

A concrete situation

Hoeffding controls its empirical mean.

What the mathematics does not license

Data-dependent selection requires additional control. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record h. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

3. Deviation

The central mathematical idea is concrete. Set epsilon=.1.

A concrete situation

The target gap is ten percentage points.

What the mathematics does not license

Risk and empirical risk share the same scale. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record epsilon. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

4. Sample size

Here the geometry becomes operational. Set n=1000.

A concrete situation

There are one thousand independent examples.

What the mathematics does not license

Effective sample size may differ under dependence. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record n. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

5. Single bound

This step deserves a careful pause. Compute 2exp(-2n epsilon^2).

A concrete situation

Exponent is -20.

What the mathematics does not license

This is a two-sided form. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record expression. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

6. Hypothesis class

The useful question is not only how to calculate, but what the calculation assumes. Set |H|=100.

A concrete situation

There are one hundred fixed candidates.

What the mathematics does not license

Continuous classes need other capacity control. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record size. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

7. Union bound

A small example makes the mechanism visible. Multiply the single bound by one hundred.

A concrete situation

Any-hypothesis failure is at most 200e^-20.

What the mathematics does not license

Cap probability bounds at one when loose. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record formula. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

8. Numerical value

This is where modelling choices begin to affect evidence. Evaluate 200e^-20.

A concrete situation

Value is about 4.12e-7.

What the mathematics does not license

Do not describe an upper bound as exact probability. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record value. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

9. Confidence

The central mathematical idea is concrete. Set delta=.05.

A concrete situation

Desired success probability is at least .95.

What the mathematics does not license

Delta is a failure probability. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record delta. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

10. Solve epsilon

Here the geometry becomes operational. Rearrange 2|H|e^-2n epsilon^2 <= delta.

A concrete situation

epsilon is sqrt[ln(2|H|/delta)/(2n)].

What the mathematics does not license

Use natural logarithms. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record formula. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

11. Log term

This step deserves a careful pause. Compute ln(4000).

A concrete situation

Value is about 8.29405.

What the mathematics does not license

Keep precision before the square root. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record value. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

12. Gap result

The useful question is not only how to calculate, but what the calculation assumes. Compute sqrt(8.29405/2000).

A concrete situation

epsilon is about .0644.

What the mathematics does not license

This is uniform over the finite class. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record result. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

13. Target gap

A small example makes the mechanism visible. Set epsilon=.05.

A concrete situation

Solve for required n.

What the mathematics does not license

Round sample size upward. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record target. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

14. Sample formula

This is where modelling choices begin to affect evidence. Use n>=ln(4000)/(2*.05^2).

A concrete situation

Raw value is about 1658.81.

What the mathematics does not license

Integer n must be at least 1659. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record result. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

15. Assumption audit

The central mathematical idea is concrete. Check boundedness, independence and fixed class.

A concrete situation

The theorem is eligible only when checks pass.

What the mathematics does not license

Distribution shift is separate. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Document evidence. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

16. Claim

Here the geometry becomes operational. State loss range, class size, n, epsilon and delta.

A concrete situation

The worked sufficient n is 1659.

What the mathematics does not license

Do not promise model accuracy from sample size alone. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Bound conclusion. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

A seven-day practice lab

1. Day 1: define the decision, observation unit, X variables and Y or reference condition.
2. Day 2: reproduce the smallest worked example and check every dimension, unit and sign.
3. Day 3: build a transparent baseline and write what it assumes.
4. Day 4: fit the main method inside a training-only pipeline; record every parameter.
5. Day 5: challenge one assumption with a deliberately difficult dataset or operating regime.
6. Day 6: compare validation metrics with the practical workload created by errors.
7. Day 7: present one supported conclusion, one unresolved uncertainty and one safe next experiment.

Questions for a student, parent or mentor

• Which part of the model is a mathematical definition, and which part is a choice?
• What small calculation would catch a sign, scale or dimension error?
• What evidence comes from training, validation and the untouched test?
• What benign condition could look like a fault or prediction failure?
• How would the answer change for another response, asset, school project or time period?
• What should a human review before acting on the score?

A method-specific audit before deployment

Hoeffding bounds convert bounded independent observations into finite-sample probability statements. For variables in [0,1], the sample mean differs from its expectation by at least epsilon with probability at most 2 exp(-2n epsilon squared). The inequality is distribution-free within its assumptions, although it can be conservative.

For a finite hypothesis class, a union bound controls the chance that any hypothesis has a large empirical-to-population risk gap. A standard two-sided form is at most 2|H| exp(-2n epsilon squared). Dependence between hypotheses does not invalidate the union bound, but dependence between examples can invalidate the underlying Hoeffding step.

With |H|=100, n=1000 and epsilon=.1, the upper probability is 200 exp(-20), about 4.12 times 10 to the minus 7. For confidence delta=.05, solving gives epsilon=sqrt[ln(2|H|/delta)/(2n)]=sqrt[ln(4000)/2000], about .0644.

To target epsilon=.05 at delta=.05 with one hundred hypotheses, the same formula requires n at least ln(4000)/(2*.05 squared), which rounds up to 1659. The number is a sufficient bound under bounded independent loss, not a promise that exactly 1659 examples make every model accurate.

---

Frequently asked questions

What does Hoeffding’s inequality control?

Deviation of a bounded independent sample average from its expectation.

Why add a union bound?

To control the chance that any member of a finite hypothesis class deviates too much.

Must hypotheses be independent?

No. The union bound does not require that, but sample-level concentration still needs its assumptions.

Is the probability bound exact?

No. It is an upper bound and may be conservative.

Why round sample size upward?

A sufficient integer sample count must meet or exceed the real-valued threshold.

What must be reported?

Loss range, independence, class size, n, epsilon, delta, one- or two-sided form and logarithm convention.

---

Primary source and fact-check note

Wassily Hoeffding, “Probability Inequalities for Sums of Bounded Random Variables,” Journal of the American Statistical Association 58(301), 1963. Definitions and core claims in this article were checked against this primary publication. Calculations shown here were independently recomputed. Examples are educational illustrations; they are not reported industrial performance results.

Useful next reading

• VC dimension
• Rademacher complexity
• PAC-Bayes bounds
• Algorithmic stability
• How Mathematics Works

Keep the options open. Mathematics education supports clearer questions, transferable problem-solving skills and informed choices across science, engineering, computing, AI, statistics, design and many other careers. It does not guarantee intelligence, income, admission or employment; those outcomes depend on far more than one subject or model.

Extended laboratory: capacity, assumptions, error and concentration

Range audit

Verify every loss lies in the declared interval.

Dependence audit

Check whether examples satisfy the concentration assumptions.

Class audit

Count a fixed finite class before applying the union bound.

Constant audit

Keep one-sided or two-sided factors and logarithm base consistent.

Mechanism workshop: calculate, challenge and transfer

Manual reconstruction

Rebuild the smallest example for finite-sample concentration. Label every set, probability and convention.

Assumption map

Place each theorem assumption beside the step it permits.

Counterexample

Change one assumption and show which conclusion fails.

Sensitivity

Vary one point count, prior, noise term, class size or confidence input.

Numerical verification

Recompute with an independent script or spreadsheet before rounding.

Student transfer

Apply the mechanism to a small classifier or regression experiment.

Parent explanation

Explain why the mathematics prevents confident but unsupported AI claims.

Evidence ladder

Separate identity, theorem, simulation and practical interpretation.

Limit statement

Write one supported conclusion, one overclaim and one repaired claim.

Next measurement

Choose a held-out, perturbation or replication check and explain its role.

Evidence notebook: reconstruct every mathematical step

Evidence notebook 1: Loss

Step 1 isolates loss. Use independent losses in [0,1]. The reproducible result is: Each summand has range length one. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Unbounded loss needs another inequality or transformation. Record range. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 2: Single hypothesis

Step 2 isolates single hypothesis. Fix one hypothesis before examining the sample. The reproducible result is: Hoeffding controls its empirical mean. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Data-dependent selection requires additional control. Record h. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 3: Deviation

Step 3 isolates deviation. Set epsilon=.1. The reproducible result is: The target gap is ten percentage points. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Risk and empirical risk share the same scale. Record epsilon. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 4: Sample size

Step 4 isolates sample size. Set n=1000. The reproducible result is: There are one thousand independent examples. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Effective sample size may differ under dependence. Record n. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 5: Single bound

Step 5 isolates single bound. Compute 2exp(-2n epsilon^2). The reproducible result is: Exponent is -20. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: This is a two-sided form. Record expression. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 6: Hypothesis class

Step 6 isolates hypothesis class. Set |H|=100. The reproducible result is: There are one hundred fixed candidates. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Continuous classes need other capacity control. Record size. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 7: Union bound

Step 7 isolates union bound. Multiply the single bound by one hundred. The reproducible result is: Any-hypothesis failure is at most 200e^-20. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Cap probability bounds at one when loose. Record formula. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 8: Numerical value

Step 8 isolates numerical value. Evaluate 200e^-20. The reproducible result is: Value is about 4.12e-7. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Do not describe an upper bound as exact probability. Record value. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 9: Confidence

Step 9 isolates confidence. Set delta=.05. The reproducible result is: Desired success probability is at least .95. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Delta is a failure probability. Record delta. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 10: Solve epsilon

Step 10 isolates solve epsilon. Rearrange 2|H|e^-2n epsilon^2 <= delta. The reproducible result is: epsilon is sqrt[ln(2|H|/delta)/(2n)]. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Use natural logarithms. Record formula. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 11: Log term

Step 11 isolates log term. Compute ln(4000). The reproducible result is: Value is about 8.29405. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Keep precision before the square root. Record value. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 12: Gap result

Step 12 isolates gap result. Compute sqrt(8.29405/2000). The reproducible result is: epsilon is about .0644. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: This is uniform over the finite class. Record result. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 13: Target gap

Step 13 isolates target gap. Set epsilon=.05. The reproducible result is: Solve for required n. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Round sample size upward. Record target. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 14: Sample formula

Step 14 isolates sample formula. Use n>=ln(4000)/(2*.05^2). The reproducible result is: Raw value is about 1658.81. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Integer n must be at least 1659. Record result. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 15: Assumption audit

Step 15 isolates assumption audit. Check boundedness, independence and fixed class. The reproducible result is: The theorem is eligible only when checks pass. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Distribution shift is separate. Document evidence. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 16: Claim

Step 16 isolates claim. State loss range, class size, n, epsilon and delta. The reproducible result is: The worked sufficient n is 1659. This is evidence about bounded-loss concentration. Preserve the data, units, loss and theorem convention beside every value. The safeguard is: Do not promise model accuracy from sample size alone. Bound conclusion. Change one input while holding the comparison protocol fixed. Recalculate every count, bias, variance, probability or bound that should move. Explain whether the difference came from class geometry, averaging, sampling, noise or approximation. Ask a second reader to reproduce the arithmetic from the recorded inputs. Finish with the narrow conclusion and the evidence still missing.

Failure cases and responsible recovery

Unbounded loss

The stated range condition is essential. Rebuild a counterexample, repeat the calculation under a valid convention and state the missing evidence.

Dependent examples

Serial or clustered data may violate the iid-style step. Rebuild a counterexample, repeat the calculation under a valid convention and state the missing evidence.

Adaptive class

A class chosen after seeing data needs careful accounting. Rebuild a counterexample, repeat the calculation under a valid convention and state the missing evidence.

Factor loss

One-sided and two-sided formulas differ by constants. Rebuild a counterexample, repeat the calculation under a valid convention and state the missing evidence.

Exactness claim

The inequality gives an upper bound, not the true probability. Rebuild a counterexample, repeat the calculation under a valid convention and state the missing evidence.

Union arithmetic

Multiply by class size before solving for confidence. Rebuild a counterexample, repeat the calculation under a valid convention and state the missing evidence.

Rounding down

A sufficient sample size must be rounded upward. Rebuild a counterexample, repeat the calculation under a valid convention and state the missing evidence.

Accuracy promise

A small generalization gap does not ensure small risk. Rebuild a counterexample, repeat the calculation under a valid convention and state the missing evidence.