Concentration Inequalities (Chebyshev, Hoeffding — Bridge to December) TODO
Concept
Concentration inequalities are a family of results bounding how tightly a random variable clusters around its expectation. Markov's inequality is the weakest form, bounding the tail of a non-negative variable using only its mean. Chebyshev's inequality adds variance information, guaranteeing that the probability of deviating from the mean by more than k standard deviations is at most 1/k². Hoeffding's inequality guarantees that for the average of independent variables each bounded within a finite interval, the probability of deviation decays exponentially in both the sample size and the deviation width. The consistent principle across this family is that stronger assumptions — non-negativity, then finite variance, then boundedness plus independence — yield sharper tail bounds. The practical use is solving in reverse: how many samples do you need to hit a target accuracy at a target confidence level — and that guarantee becomes meaningless the moment the independence assumption breaks.
Determining a defensible sample size for sampling-based estimation, A/B decisions, or the failure probability of a randomized algorithm requires these inequalities — a sample count picked by gut feel is usually either too small or wastefully large.
Code & Formula
# Day 37 — 집중부등식(Chebyshev·Hoeffding)
# 시뮬레이션으로 실제 이탈확률을 구하고, Chebyshev·Hoeffding 상한과 비교해 부등식이 보장임을 확인한다.
import random
import math
random.seed(0)
# Chebyshev: P(|X - mu| >= k*sigma) <= 1/k^2, X ~ Uniform(0,1) 표본평균으로 확인
n_trials = 200_000
mu_uniform = 0.5
var_uniform = 1 / 12
sigma_uniform = math.sqrt(var_uniform)
k = 2.0
count_exceed = 0
for _ in range(n_trials):
x = random.uniform(0, 1)
if abs(x - mu_uniform) >= k * sigma_uniform:
count_exceed += 1
empirical_prob = count_exceed / n_trials
chebyshev_bound = 1 / k ** 2
print(f"Chebyshev: P(|X-mu|>={k}*sigma) 실제 = {empirical_prob:.4f}, 상한 1/k^2 = {chebyshev_bound:.4f}")
print(f"-> 실제 <= 상한 ? {empirical_prob <= chebyshev_bound}\n")
# Hoeffding: 독립 [0,1] 변수 n개 평균이 참평균에서 t 이상 벗어날 확률 <= 2*exp(-2*n*t^2)
n_samples = 100
t = 0.1
n_experiments = 20_000
count_exceed_hoeffding = 0
true_mean = 0.5
for _ in range(n_experiments):
sample = [random.uniform(0, 1) for _ in range(n_samples)]
sample_mean = sum(sample) / n_samples
if abs(sample_mean - true_mean) >= t:
count_exceed_hoeffding += 1
empirical_hoeffding = count_exceed_hoeffding / n_experiments
hoeffding_bound = 2 * math.exp(-2 * n_samples * t ** 2)
print(f"Hoeffding: P(|mean-mu|>={t}) 실제 = {empirical_hoeffding:.5f}, 상한 = {hoeffding_bound:.5f}")
print(f"-> 실제 <= 상한 ? {empirical_hoeffding <= hoeffding_bound}")
Exercise
Compute, using both Chebyshev's and Hoeffding's inequalities, how many coin flips are needed to estimate a biased coin's heads probability to within 0.01 at 95% confidence, and compare how different the two required sample sizes are.
Practical Connection
This same reasoning is exactly what's used to judge how many trials are needed before a measured average from a prediction-market simulation or a matching-engine load test can be trusted.
Where it lands in Jayverse
- Verex: compute a Hoeffding-based minimum sample size before trusting a simulated fill-rate or latency number from the CLOB backtest. Log the confidence level next to any published dev metric, and drop the guarantee the moment samples aren't independent (same block, correlated fills).
- OFA: size the number of auction rounds needed before trusting a "solver X wins Y% of the time" claim, using the Hoeffding bound since outcomes are bounded. Flag it void when rounds share a solver or a block, since that breaks independence.
- Number: state the sample size behind any published indicator backtest in Hoeffding terms. Add it as a field on the reading so a reader can tell over-fit noise from a genuine edge.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| bound (v.) | (범위를) 제한하다, 경계를 정하다 · 확률변수가 평균에서 얼마나 벗어나는지 위아래로 한정할 때. "bounding how tightly a random variable clusters" |
| cluster around | ~ 주위에 몰려 있다 · 값들이 평균 근처에 밀집해 있을 때. "clusters around its expectation" |
| decay exponentially | 지수적으로 감소하다 · 편차 확률이 표본 수가 늘수록 급격히 줄어들 때. "the probability of deviation decays exponentially" |
| yield (v.) | (결과·수치를) 산출하다, 내놓다 · 더 강한 가정이 더 날카로운 결과를 낳을 때. "yield sharper tail bounds" |
| solve in reverse | 거꾸로 풀다, 역으로 계산하다 · 목표 정확도에서부터 필요한 표본 수를 역산할 때. "the practical use is solving in reverse" |
| the moment (conj.) | ~하는 순간 (바로) · 전제조건이 깨지는 즉시 결과가 무의미해질 때. "becomes meaningless the moment the independence assumption breaks" |
| picked by gut feel | 감(느낌)으로 고른 · 근거 없이 직관만으로 정한 수치를 비판할 때. "a sample count picked by gut feel" |
| Markov's inequality | 마르코프 부등식 · 음이 아닌 확률변수의 꼬리 확률을 평균만으로 상한을 구하는, 가장 약한 형태의 집중부등식. "Markov's inequality is the weakest form" |
| Chebyshev's inequality | 체비셰프 부등식 · 분산 정보를 더해 평균에서 k표준편차 이상 벗어날 확률이 1/k² 이하임을 보장하는 부등식. "the probability of deviating from the mean by more than k" |
| Hoeffding's inequality | 회프딩 부등식 · 유한 구간에 갇힌 독립 확률변수들의 평균이 표본 크기와 편차 폭 둘 다에 지수적으로 확률이 감소함을 보장하는 부등식. "Hoeffding's inequality guarantees that for the average of independent variables" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.