Engineering / Mathematics — Probabilistic Algorithms
Approximating Functions by Random Sampling
Estimating a quantity by sampling, the sample size required, and the resulting confidence guarantee.
Executive summary
Many quantities that are expensive to compute exactly can be estimated by sampling. The sample size needed for a given accuracy and confidence follows from a concentration inequality.
The characteristic feature is that accuracy improves only as the square root of the sample size, so high precision is expensive.
Learning objectives
- Set up an estimator as a sample mean.
- Derive the sample size from Chebyshev's inequality.
- Recognise the square-root limitation.
01The estimator
To estimate a proportion p, draw n independent samples and take the fraction succeeding. The estimator is unbiased and its variance falls linearly in n.
p̂ = (1/n)Σ Xᵢ, E[p̂] = p, Var[p̂] = p(1−p)/n ≤ 1/(4n)The variance bound uses p(1−p) ≤ 1/4, which holds for every p and so requires no prior knowledge of the quantity being estimated.
02Sample size from Chebyshev
Sample size bound
To ensure P(|p̂ − p| ≥ ε) ≤ δ, it suffices to take
n ≥ 1/(4ε²δ).
Reason. Chebyshev gives P(|p̂ − p| ≥ ε) ≤ Var[p̂]/ε² ≤ 1/(4nε²); set this to δ.
Only pairwise independence is required, since the bound uses the variance of a sum. This is what allows sampling with hash-based pseudorandomness rather than fresh independent draws.
| Accuracy ε | Confidence δ | Samples via Chebyshev | Via exponential bound |
|---|---|---|---|
| 0.01 | 0.05 | 50,000 | ≈ 18,500 |
| 0.001 | 0.05 | 5,000,000 | ≈ 1,850,000 |
| 0.01 | 2^{−64} | ≈ 4.6 × 10¹⁸ | ≈ 222,000 |
03The square-root limitation
The practical consequence is that sampling is excellent for moderate accuracy and hopeless for high precision. Estimating a proportion to two decimal places is routine; to eight is not.
Where high precision is needed, the usual response is not more samples but a different method — an exact algorithm, or variance reduction techniques that lower the constant without changing the exponent.
04Frequently asked questions
Why use Chebyshev when exponential bounds are sharper?
Because Chebyshev needs only pairwise independence. When randomness is expensive or supplied by a bounded-independence hash family, the exponential bounds are unavailable and Chebyshev is what remains.
Does the sample size depend on the population size?
No, which is the counterintuitive and valuable feature. The bound depends only on accuracy and confidence, so estimating a proportion in a population of billions needs no more samples than in a population of thousands.
What if the quantity is not a proportion?
The same analysis applies with the variance of the underlying variable in place of p(1−p), provided that variance is finite and boundable. Unbounded variables need a tail assumption before any bound is available.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 155-158.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.