Concentration: Hoeffding, Chebyshev and Markov
Try it: Concentration: Hoeffding, Chebyshev and Markov
The sample mean of m i.i.d. bounded samples concentrates around the true mean μ: repeated seeded experiments estimate P(|sample mean − μ| ≥ ε) and compare it with Hoeffding's bound 2·exp(−2mε²), Chebyshev's bound Var/ε² and Markov's bound for the one-sided event.
How it works
- Draw θ1, …, θm i.i.d. Bernoulli(p) (bounded in [a, b] = [0, 1], common mean μ = p) and track the running sample mean.
- The deviation event is |sample mean − μ| ≥ ε for a chosen positive tolerance ε.
- Hoeffding: P(|mean − μ| ≥ ε) ≤ 2·exp(−2mε²/(b − a)²); Chebyshev with Var[mean] = p(1 − p)/m: ≤ p(1 − p)/(mε²); Markov for the non-negative mean: P(mean ≥ μ + ε) ≤ μ/(μ + ε).
- Repeat the whole experiment many times (seeded) and count how often each event happens.
- Compare the observed frequencies with the bounds: they are upper bounds, not the exact probability.
Default run (32 steps): θ1, …, θm are i.i.d. Bernoulli(0.5) samples, each in [a, b] = [0, 1], with true mean μ = 0.5. m = 100, ε = 0.1, seed 7. … 200 experiments: |mean − μ| ≥ 0.1 happened 3 times (frequency 0.015) — Hoeffding allows at most 0.2707, Chebyshev 0.25. One-sided mean ≥ μ + ε: 1 times (0.005) vs Markov 0.8333.
Simplified: Samples are Bernoulli(p) (0 or 1), so [a, b] = [0, 1]; the randomness comes from a seeded pseudo-random generator (mulberry32). Observed frequencies are estimates from a finite number of experiments.
Loading the simulation…