Your classifier scored 85% on 1,000 test examples. Is the true accuracy 85%, or could it be 80%? And when an integral has no formula, how do you compute it anyway? One answer covers both questions: inequalities that put a hard ceiling on how often an average can be wrong, and Monte Carlo, the habit of replacing a hard calculation with a lot of cheap random draws.
Learning Objectives
After this lesson, you will be able to:
State Markov, Chebyshev and Hoeffding, say what each one needs to know about the variable, and see why each is loose but never wrong
Use Hoeffding to compute how many test examples you need for the observed accuracy to be within ε of the truth with probability 1 − δ, and verify the answer by simulation
Recognise Jensen's inequality (proved in the Information Theory & Entropy lesson) in a five-line numeric example: the average of a function is not the function of the average
Tell the Law of Large Numbers (where the average goes) from the Central Limit Theorem (how it wobbles on the way)
Estimate π and an expectation by Monte Carlo, confirm the 1/√N error rate in code, say which part of the error can grow with dimension, and use importance sampling to estimate a rare event
This lesson has two halves. Part A asks how wrong an average can be when you know very little about the data: Markov uses the mean, Chebyshev adds the variance, Hoeffding adds boundedness and tells you how big a test set must be. A short reminder of Jensen's inequality and the contrast between the Law of Large Numbers and the Central Limit Theorem close it. Part B then turns the average into a tool: Monte Carlo estimation, importance sampling for rare events, and why sampling beats grids.
#Markov's Inequality: Bounding a Tail from the Mean
Suppose all you know about a website is that the average page load takes 2 seconds. You know nothing else: not the shape, not the spread. Can you say anything about how often a load takes 10 seconds or more? Surprisingly, yes. Markov's inequality says that for any non-negative random variable X and any a > 0:
P(X≥a)≤aE[X]
Why is it true? Split the average into the part from outcomes below a and the part from outcomes at or above a. The second part is at least a × P(X ≥ a), and the first part is not negative, so E[X] ≥ a × P(X ≥ a). Divide by a and you are done. Non-negativity is what lets you throw the first part away.
The price of knowing so little is looseness. Simulate loads from an Exponential distribution with mean 2 s and compare the bound with the truth:
A Pyodide-backed scratchpad for math lessons.
Loading visualization...
The bound for a load of 10 s or more is 0.200, while the simulated probability is only 0.0068 (the exact value is e^−5 = 0.0067). Markov overstates the risk about 30 times here. The table shows the bound is useless at a = 2, where it just says "at most 100%".
But the bound is not wrong, and it cannot be improved without more information. The last line of the output shows a two-point variable that is 0 with probability 0.8 and 10 with probability 0.2. Its mean is 2 and P(X ≥ 10) is about 0.2, matching the bound. So Markov is the best you can do when the mean is all you know.
Markov used only the mean. If you also know the variance, you can bound how far a variable strays from its mean, in either direction. Apply Markov to the non-negative quantity (X − μ)² and you get Chebyshev's inequality:
P(∣X−μ∣≥kσ)≤k21
For a Normal distribution you already know much sharper numbers: the 68-95-99.7 rule says about 95% of the mass lies within 2 standard deviations. Chebyshev says at least 75%. Compare the two on the same k, and add a skewed distribution to see Chebyshev stay valid where the Normal rule would fail:
A Pyodide-backed scratchpad for math lessons.
Loading visualization...
At k = 2 the Normal puts only 0.0455 of its mass outside, against Chebyshev's ceiling of 0.25. The Exponential has a fatter tail beyond 3 standard deviations (0.0186, against the Normal's 0.0027), so the Normal rule would understate its tail about 7 times, while Chebyshev still holds. The last line shows the ceiling is reachable: a three-point variable puts about 0.25 of its mass at distance 2.
#Hoeffding's Inequality: How Many Test Examples Do You Need?
Chebyshev is polynomial in k. When you are bounding the average of many independent bounded variables, an exponential bound is available, and it is the workhorse of learning theory. If X₁, …, Xₙ are independent and each lies in [0, 1], then the sample mean X̄ satisfies Hoeffding's inequality:
P(∣Xˉn−μ∣≥ε)≤2e−2nε2
Now the use that matters for ML. A model is right or wrong on each test example, so each outcome is a 0 or 1 and the observed accuracy is a sample mean. You want the observed accuracy to be within ε = 0.02 of the true accuracy with probability at least 1 − δ = 0.95. Set the right side equal to δ and solve for n:
2e−2nε2≤δ⟺n≥2ε2ln(2/δ)
Before you run it, commit to a guess about the size of n.
What Do You Think?
You want the test accuracy to be within 2 percentage points (ε = 0.02) of the true accuracy, with 95% confidence (δ = 0.05), and you only know each example is scored 0 or 1. Which test-set size does Hoeffding's inequality tell you to collect?
Now verify it. Pretend the true accuracy is 0.85, draw test sets of various sizes, and count how often the observed accuracy misses by 0.02 or more:
A Pyodide-backed scratchpad for math lessons.
Loading visualization...
The calculation gives n = 4612. For comparison, Chebyshev (using Var ≤ 1/(4n)) asks for 12,500, nearly three times as many, and a Normal approximation asks for about 1,225 at p = 0.85 or 2,401 in the worst case p = 0.5. In the simulation the real miss rate falls from 0.2399 at n = 500 to 0.0143 at n = 2000, and at n = 4612 it is only 0.0003, far below the promised 0.05. The guarantee holds with a large safety margin because Hoeffding must cover the worst possible distribution of outcomes, not only the one you happen to have.
Two cautions. First, Hoeffding assumes the test examples are independent draws from the same distribution you will deploy on; a test set with duplicates or leakage voids the guarantee. Second, if you try many models on the same test set and keep the best, the winner's score is optimistic, and you need a larger n (or a fresh test set) to account for the selection.
Pick a source and slide the threshold to see how far the Markov and Chebyshev curves sit above the real tail (the Exponential at a = 5 gives 0.200 against 0.0068), then open the Hoeffding tab and drag n to 4,612 to watch the bound reach δ while the simulated miss rate stays near zero.
Markov, Chebyshev and Hoeffding bound how far an average strays. Jensen's inequality compares two different averages: the function of the average and the average of the function. The Information Theory & Entropy lesson proves it and uses it for KL ≥ 0 and the ELBO, so only a numeric reminder is repeated here. For a convex function f (a bowl, such as x²) and any random variable X:
With X equal to 1 or 3, f(E[X]) = 2² = 4 while E[f(X)] = (1 + 9)/2 = 5. For the concave log, the log of the average of [1, 10, 100] is 3.6109 and the average of the logs is 2.3026. The direction flips with the curve, and the more spread the values, the wider the gap.
#Two Promises: The Law of Large Numbers and the CLT
You have now seen several bounds on an average. Two big theorems also describe an average, and because they promise different things people mix them up. The Sampling, Standard Error & the Bootstrap lesson teaches the Central Limit Theorem (CLT) properly; here is only the contrast.
LLN: Xˉnn→∞μ,CLT: nσXˉn−μdN(0,1)
The random-variables lesson showed the LLN with a die. Here both promises are measured on a skewed distribution, an Exponential with mean 1 and standard deviation 1, which looks nothing like a bell:
A Pyodide-backed scratchpad for math lessons.
Loading visualization...
The LLN promises where the average goes. The chance the sample mean is more than 0.1 from the truth falls from 0.9254 at n = 1 to 0.0019 at n = 1000. The CLT promises how it wobbles on the way. The spread of the mean follows σ/√n (0.3156 at n = 10, 0.0318 at n = 1000), and the scaled error √n(mean − 1) holds steady near 1.0 at every n. Read the full table in the output.
Both promises have fine print: the LLN needs a finite mean and the CLT needs a finite variance. A Cauchy variable has heavy enough tails that its mean does not exist, and the last lines of the output show its running average still jumping around (0.572, 1.121, −0.772, 0.460, −0.392) a million draws in.
Quick check
You average 400 independent measurements and get 7.2. A colleague asks what justifies reporting a ± error bar that looks like a bell curve. Which theorem is doing the work?
Part A bounded an average you already had. Part B asks the reverse question: when an expectation has no formula, can you build the average yourself? Monte Carlo estimation says yes, importance sampling rescues it when the interesting region is rare, and a grid comparison shows why random samples win when there are many dimensions.
Now put the LLN to work. If you want the expectation E[f(X)] and you can draw samples of X, draw N of them and average f. The LLN says the answer converges; the CLT says how fast.
Before the formula, predict how the error behaves when you buy more samples.
What Do You Think?
Your Monte Carlo estimate has a standard error of 0.0546 using 1,600 samples. You quadruple the budget to 6,400 samples. What do you expect the standard error to become?
E[f(X)]≈μ^N=N1i=1∑Nf(xi),SE(μ^N)=Nσf
Here σ_f (sigma-f) is the standard deviation of the values f(X), the one number that sets the size of the error. The estimate is unbiased: repeat the whole N-sample experiment many times and the estimates average out to the true E[f(X)], scattering around it by about the standard error but never leaning to one side. Be exact about what the dimension does: the rate 1/√N is the same in 2 or 2 million dimensions, but σ_f is a property of f and can be larger when X has more coordinates.
Estimating π. Drop random points in the unit square. The fraction landing inside the quarter circle x² + y² ≤ 1 equals the area of the quarter circle, π/4. So π ≈ 4 × (fraction inside). Each point is a 0 or 1, so this is an expectation of an indicator.
A Pyodide-backed scratchpad for math lessons.
Loading visualization...
With N = 100 points the estimate is 3.08000, and with a million it is 3.14249. The standard deviation of the estimate over repeated experiments follows the theory 1.6422/√N closely at every size, as the last three output lines show.
Now confirm the rate on a less artificial target: estimate E[e^X] for X ~ Normal(0, 1), whose exact value is e^0.5 = 1.6487.
A Pyodide-backed scratchpad for math lessons.
Loading visualization...
Here σ_f = 2.1612. At N = 1,600 the empirical standard deviation of the estimate is 0.0546 against a theory value of 0.0540. Across all five sizes the log-log slope of error against N is −0.500, exactly the −1/2 the theory predicts, and each quadrupling of N shrinks the error by about 2. A single run of 10,000 samples reports its own error bar, and the truth sits inside it.
Plain Monte Carlo wastes samples when the interesting region is rare. Estimate P(Z > 4) for a standard Normal. The exact answer is 3.167e-05. With N = 10,000 draws you expect only 0.3 of a sample above 4, so a plain run sees no hit at all with probability (1 − 3.167e-05)^10,000 = 0.729, about 73%.
The idea, with five draws. Instead of drawing from the standard Normal p, draw from a proposal q = Normal(4, 1), centred on the rare region, so about half the draws land above 4. Those draws are over-produced, so each one gets a weight w = p(y)/q(y) that says how much less likely p is to make that value than q is. For these two Normals the ratio simplifies:
Take five draws from q: 3.2, 4.1, 4.6, 3.9 and 5.0. Only 4.1, 4.6 and 5.0 are above 4. Their weights are e^(−8.4) = 2.25e-04, e^(−10.4) = 3.04e-05 and e^(−12) = 6.1e-06, and the other two draws contribute 0. The estimate is the average of (hit × weight) over all five draws:
(2.25e-04 + 3.04e-05 + 6.1e-06) / 5 = 5.2e-05
From only five draws that is the right order of magnitude (exact 3.2e-05), where five plain draws would almost surely report 0. Far-out hits get tiny weights because p rarely makes values that large, which is what undoes the over-sampling and keeps the average unbiased. Now the general formula:
Importance sampling is exactly what the five-draw example did. With the same proposal Normal(4, 1) and weight e^(−4y + 8), compare the two estimators over 500 repeated runs of 10,000 draws:
A Pyodide-backed scratchpad for math lessons.
Loading visualization...
Naive Monte Carlo averages 2.58e-05 with a standard deviation of 5.17e-05, a relative error of 1.63 (worse than useless), and 78% of its runs saw zero hits. Importance sampling averages 3.17e-05 with a standard deviation of only 6.67e-07, a relative error of 0.021. That is a variance reduction of about 6016x: the same accuracy from several thousand times fewer samples. The 6016 is the ratio of two sample variances from 500 seeded runs, and the naive one rests on a few rare hits, so it is noisy; the exact analytic ratio is about 6,998x, and the visualization below shows both.
Throw darts to watch the π estimate settle inside its 1/√N band, read the log-log slope on the Error vs N tab, then open Importance sampling and compare the spread of the two estimators on P(Z > 4).
The Bayesian inference lesson used a grid to compute a posterior, and noted it collapses with many parameters. Here is the arithmetic. A grid with m points per axis in d dimensions needs m^d evaluations. At 10 points per axis that is 100 evaluations in 2 dimensions, 100,000 in 5, 10,000,000,000 in 10 and 100,000,000,000,000,000,000 in 20. Monte Carlo's error is σ_f/√N: the 1/√N rate is the same in every dimension, although the constant σ_f depends on f.
Give both methods the same budget of 10,000 function evaluations and integrate f(x) = exp(−‖x‖²) over the unit cube in d dimensions, where the exact answer is (0.7468)^d:
A Pyodide-backed scratchpad for math lessons.
Loading visualization...
In 1 and 2 dimensions the grid is essentially exact while Monte Carlo is off by a few tenths of a percent, and at d = 4 the grid is still ahead. The lines cross between d = 4 and d = 6, where the budget buys only 4 points per axis. By d = 10 (2 points per axis) the grid is off by 10.9% against Monte Carlo's 0.8%, and at d = 20 the budget buys a single grid point per axis, giving an error of 131% against 1.1%. The grid gets exponentially worse; Monte Carlo barely notices.
When you cannot find a proposal q that you can both sample from and evaluate, another family of methods builds samples from a random walk instead of independent draws. That idea is picked up in the Markov Chains & MDPs lesson later in this track.
The training loss is an expectation over the whole dataset, and its gradient is an average over every example. A minibatch gradient averages only B random examples, which is a Monte Carlo estimate: unbiased, with a standard error that falls like 1/√B. The cell below shows the noise on one coordinate shrinking as the batch grows while the average stays at the full gradient. This is why larger batches buy diminishing returns, and why the learning rate and batch size are tuned together.
Averaging K independently noisy predictions cuts the variance of the error by K when the models make independent mistakes, which is the LLN at work. Dropout at test time (MC dropout) draws K random sub-networks and averages them, and its spread across draws is a cheap uncertainty estimate. The catch is correlation: if the models' errors are correlated, the variance has a floor of ρσ² (ρ is the correlation, σ² the variance of one model's error), and adding more models cannot push below it. A short derivation follows the cell.
A diffusion model generates an image by starting from pure noise and applying many small stochastic denoising steps. Each step draws a random sample and moves a little towards the data distribution, much like a Markov chain (a random walk where each step depends only on where you are now, covered in a later lesson), and the final image is one sample from the learned distribution. Generating many images and averaging a score over them is an ordinary Monte Carlo estimate on top of that.
Check both numerical claims in one cell: the minibatch gradient and the ensemble variance.
A Pyodide-backed scratchpad for math lessons.
Loading visualization...
Minibatch gradients. The full gradient on coordinate 0 is −2.1253. The mean of the minibatch gradients stays near it at every B, while the standard deviation falls from 15.8623 at B = 1 to 0.6792 at B = 512. The column sd × √B stays between 15 and 16, so the noise is σ/√B.
Ensembles. With independent errors (ρ = 0) the variance of the average matches 1/K. With correlation ρ = 0.5 it only falls to 0.529 at K = 16, matching ρ + (1 − ρ)/K, so the floor is 0.5.
The three bounds in this lesson are promises about a tail, so the quickest way to trust them is to measure a real tail and set the promises beside it. Here you simulate an Exponential variable, see how loose Markov and Chebyshev are, check that the Hoeffding sample size keeps its promise, and then try a small variance-reduction trick on a Monte Carlo average. The generator is seeded, so your numbers should match the ones below.
pythonplayground.py · Pyodide
1
2
3
4
5
6
7
8
9
10
11
Tests · Verify the real tail is about 0.0177, Markov is 0.25 and about 14 times the truth, Chebyshev is 0.1111 and about 6 times the truth, Hoeffding n = 2050, the simulated miss rate is below 0.05, and the antithetic standard error is smaller than the plain one.
The run printed a real tail of 0.01768 (the exact value is e^-4 = 0.0183). Markov's bound of 0.2500 is 14.1 times larger and Chebyshev's 0.1111 is 6.3 times larger. Both are safe and both are loose, and Chebyshev wins here only because it also uses the variance.
Hoeffding gave n = 2,050 for ε = 0.03 and δ = 0.05. Across 2,000 repeats the sample mean missed by 0.03 or more in 0.75% of them, well under the 5% allowed. The bound is a guarantee for every bounded variable, so for a fair coin it is conservative.
In the stretch step, plain Monte Carlo estimated E[exp(Z)] as 1.6276 with standard error 0.02091, and antithetic pairs gave 1.6496 with standard error 0.01179, against the exact 1.6487. The pairs cost two evaluations of exp for each draw of Z, and exp(z) and exp(-z) move in opposite directions, so their average is steadier. Try changing the seed or N and see which numbers move.
Markov (P(X ≥ a) ≤ E[X]/a, for X ≥ 0) needs only the mean; Chebyshev (P(|X − μ| ≥ kσ) ≤ 1/k²) adds the variance. Both are loose, in this lesson by 30 times (Markov: 0.200 against 0.0068) and by 5 times (Chebyshev at k = 2: 0.25 against 0.0455 for a Normal), but they are never wrong and Markov is tight for a two-point variable
Hoeffding's inequality for bounded independent variables gives P(|X̄ − μ| ≥ ε) ≤ 2e^(−2nε²), so n ≥ ln(2/δ)/(2ε²). For ε = 0.02 and δ = 0.05 that is 4,612 test examples, and halving ε quadruples n
Jensen's inequality (proved in the Information Theory & Entropy lesson) says a convex f gives f(E[X]) ≤ E[f(X)]: 4 against 5 for x² on . The average of a function is not the function of the average
The Law of Large Numbers says the average goes to the mean; the Central Limit Theorem says the leftover error is about Normal with standard deviation σ/√n. They are different promises, and both need finite moments
A Monte Carlo estimate is a sample average with standard error σ/√N: quadrupling N halves the error (log-log slope −0.500 in the simulation). The 1/√N rate is the same in every dimension, but the constant σ_f can grow with it
Importance sampling draws from a proposal q and weights each sample by p/q, which keeps the estimate unbiased and cuts the variance of a rare-event estimate by several thousand times (6,016 measured, about 6,998 exact)
Minibatch gradients, ensembles and diffusion sampling are Monte Carlo averages, and their noise follows the same square-root law
A server's average response time is 50 ms and times can never be negative. Using only that fact, what is the strongest statement Markov's inequality gives about P(time ≥ 500 ms)?
Next up: Multivariate Gaussian & Joint Distributions. You can now bound how wrong an average can be and estimate any expectation by sampling. Next you will move from one random variable to many at once: how a covariance matrix shapes a cloud of correlated data, and how conditioning and marginalising a Gaussian work.
Your Reflection
Saves automatically
What’s one thing you learned? What’s still confusing?