📚TheoryIntermediate

Concentration Inequalities

Key Points

•
Concentration inequalities give high-probability bounds that random outcomes stay close to their expectations, even without knowing the full distribution.
•
Markov and Chebyshev are general but loose; Hoeffding, Chernoff, and Bernstein are sharper when variables are bounded or sub-Gaussian.
•
For sums of independent Bernoulli variables, Chernoff bounds show exponential decay of tail probabilities with the mean.
•
Hoeffding’s inequality turns boundedness into tight, distribution-free confidence intervals for sample means.
•
McDiarmid’s inequality handles any Lipschitz function of independent inputs via bounded differences, not just sums.
•
Sub-Gaussian and sub-exponential classes summarize tail behavior via moment-generating functions and yield unified bounds.
•
These tools power generalization guarantees, sample complexity estimates, and runtime analyses in algorithms and ML.
•
In C++, you can compute bounds in O(1) time and validate them with Monte Carlo simulations in O(n · trials).

Prerequisites

→Random variables and distributions — Understand what expectations, variances, and independence mean to apply inequalities correctly.
→Expectation and variance — Markov and Chebyshev require E[X] and Var(X); all bounds compare deviations to these quantities.
→Independence and identical distribution (i.i.d.) — Hoeffding, Chernoff, and McDiarmid assume independence for sharp exponential bounds.
→Bounded random variables — Hoeffding and Bernstein require known ranges [a,b] to quantify concentration.
→Moment generating functions (MGFs) — Chernoff’s method and sub-Gaussian definitions rely on MGFs for exponential tail bounds.
→Exponential and logarithmic functions — Bounds are expressed with exp and log; manipulating them is essential for solving for n, t, or δ.
→KL divergence and information theory (optional) — KL-based Chernoff bounds for Binomial tails are the tightest multiplicative forms.
→Union bound — Needed to extend single-variable concentration to finite sets of events or hypotheses.
→Big-O notation — Interpreting sample complexity like n = O((1/ε^2) log(1/δ)) requires asymptotic notation.

Detailed Explanation

Tap terms for definitions

01Overview

Concentration inequalities are tools that bound how far a random quantity is likely to deviate from its expected value. Instead of describing the full probability distribution, they provide simple, usually exponential, upper bounds on tail probabilities like P(|X − E[X]| ≥ t). Classic examples include Markov and Chebyshev inequalities, which apply broadly but can be loose, and sharper results like Hoeffding, Chernoff, and Bernstein, which require additional structure such as boundedness, independence, or knowledge of variance. For functions of many independent variables, McDiarmid’s inequality uses a bounded-differences condition to obtain concentration without assuming linearity.

In data science and machine learning, these inequalities underpin generalization bounds and sample complexity: they tell us how many samples are needed to estimate a mean within a target error with high confidence. In algorithms, they justify that randomized procedures perform close to their expectations with high probability. The central message is that when variables are independent and not too wild (e.g., bounded), the average behaves predictably: deviations shrink rapidly as the sample size grows. This predictability is often expressed via exponential tails, making it practical to choose parameters that achieve desired error and confidence levels.

02Intuition & Analogies

Imagine measuring the average height of students by randomly sampling a class. If each sample is a student’s height, the overall average won’t jump wildly when you add or remove a single student—it nudges a little. The more independent measurements you take, the more these little nudges cancel out. Concentration inequalities formalize this “stability” of averages by quantifying how unlikely it is for the result to stray far from the true average.

Think of flipping a fair coin n times. The number of heads will almost always be close to n/2. While it’s possible to get all heads, the chance shrinks exponentially with n. Chernoff and Hoeffding bounds capture this exponential shrinkage. If the outcomes are only mildly restricted—say, bounded between 0 and 1—Hoeffding still guarantees that the average concentrates around the mean. If each input can only change the output a tiny amount (like replacing one student in the sample), McDiarmid says the function is stable and thus concentrates.

Markov and Chebyshev are like very cautious weathermen: they can warn you that a storm might happen without much detail. They need minimal information (just the mean or variance), so they’re universal but pessimistic. In contrast, Chernoff, Hoeffding, and Bernstein are like meteorologists with radar data: with extra structure (independence, boundedness, variance), they can predict that big deviations are exceptionally rare, decaying exponentially as you gather more data. This intuition explains why we trust averages and why more data makes estimates more reliable.

03Formal Definition

A concentration inequality is a bound on tail probabilities such as P(

∣ X - E [X] ∣

≥ t) or P(X − E[X] ≥ t), typically of the form P(⋯) ≤ g(t, n, params), where g decreases rapidly (often exponentially) in sample size n or deviation t. For a sum S =

\sum_{i = 1}^{n}

X_{i}

of independent random variables, classic forms assert exponential tails under boundedness or moment conditions. For example, if

X_{i}

∈ [

a_{i}

b_{i}

], Hoeffding yields P(S − E[S] ≥ t) ≤

\exp\left

( -

\frac{2 t ^{2}}{\sum _{i = 1}^{n} ( b _{i} - a _{i} ) ^{2}}

\right

). For Bernoulli sums S ~ Bin(n, p) with mean μ = np, a multiplicative Chernoff bound gives P(S ≥ (1 +

δ) μ)

≤

\exp\left

( - μ

D_{+}

(

δ)

\right

) where

D_{+}

(

δ)

is a nonnegative function (often lower bounded by

δ^{2} /3

for δ ∈ [0, 1]). McDiarmid’s inequality treats functions f of independent inputs

X_{1}

, …,

X_{n}

that satisfy bounded differences: changing the i-th coordinate alters f by at most

c_{i}

. Then P(f(X) − E[f(X)] ≥ t) ≤

\exp\left

( -

\frac{2 t ^{2}}{\sum _{i = 1}^{n} c _{i}^{2}}

\right

). Sub-Gaussian and sub-exponential classes codify tail behavior via moment generating functions (MGFs). A centered sub-Gaussian X satisfies E[

e^{λ X}

] ≤

e^{λ^{2} σ^{2} /2}

for all λ ∈ ℝ, implying P(

∣ X ∣

≥ t) ≤ 2

e^{- t^{2} / (2 σ^{2})}

. Many inequalities can be seen as corollaries of such MGF-based controls.

04When to Use

Minimal information: Use Markov when X ≥ 0 and only E[X] is known. Use Chebyshev when you know variance Var(X) but little else. They are general but loose.
Bounded variables: Use Hoeffding when independent X_i lie in known intervals [a_i, b_i]. It gives distribution-free, exponential tail bounds for sums/means.
Bernoulli or count data: Use Chernoff for sums of independent Bernoulli (or bounded-in-[0,1]) variables to get sharp multiplicative bounds, especially for relative errors.
Known variance and boundedness: Use Bernstein (or Bennett) when you know both variance and bounds; it improves Hoeffding for small variance or moderate t by mixing quadratic and linear terms in the exponent.
Functions of independent inputs: Use McDiarmid when f is Lipschitz in Hamming/coordinate changes (bounded differences). This covers averages, empirical risk, and many statistics.
Learning theory: Use these to derive generalization bounds, sample complexity N = O((1/ε^2) log(1/δ)) for estimating means within ε with confidence 1−δ, and to perform uniform convergence via union bounds over finite hypothesis classes.

⚠️Common Mistakes

Applying a sharp inequality without verifying assumptions (e.g., using Chernoff without independence or with unbounded variables). Always check independence, boundedness, or MGF conditions.
Mixing mean vs. sum parameters: Hoeffding and Bernstein have distinct forms for S = ∑X_i and for the sample mean X̄. Ensure you scale t and the bounds consistently by n.
Ignoring parameter ranges: The simple Chernoff bound P(S ≥ (1+δ)μ) ≤ e^{−δ^2 μ/3} assumes δ ∈ [0,1]. For larger δ, use the KL-based form or the δ−ln(1+δ) version.
Forgetting two-sided factors: Turning a one-sided bound into a two-sided one typically introduces a factor of 2. Don’t omit it when bounding |X̄ − μ|.
Overusing Chebyshev/Markov: They can be orders of magnitude looser than Hoeffding/Bernstein; use them only when stronger assumptions fail.
Miscomputing variance for Chebyshev: For sample means, Var(X̄) = Var(X)/n. Plugging Var(X) instead of Var(X̄) can inflate bounds by a factor n.
Overfitting bounds via data-dependent t: If you pick t after looking at data repeatedly, adjust with union bounds or use uniform (e.g., VC) bounds to avoid optimistic conclusions.

Key Formulas

Markov Inequality

Pr (X \geq a) \leq \frac{E [ X ]}{a}

Explanation: For any nonnegative random variable X and a>0, the probability that X exceeds a is at most its mean divided by a. Use when only the expectation is known.

Chebyshev Inequality

Pr (∣ X - μ ∣ \geq kσ) \leq \frac{1}{k ^{2}}

Explanation: For any random variable with mean μ and standard deviation $σ,$ large deviations of size kσ occur with probability at most 1/ $k^{2}$ . It uses only variance information.

Cantelli (One-Sided Chebyshev)

Pr (X - μ \geq t) \leq \frac{σ ^{2}}{σ ^{2} + t ^{2}}

Explanation: A one-sided refinement of Chebyshev that can be tighter for upper tails. Useful when bounding only one side of deviations.

Hoeffding for Means

Pr (\overline{X} - μ \geq t) \leq 2 exp (- \frac{2 n t ^{2}}{( b - a ) ^{2}})

Explanation: For independent Xi in [a,b] with mean $μ,$ the sample mean concentrates exponentially around $μ .$ The interval width (b−a) controls tightness.

Hoeffding for Sums

Pr (S - E [S] \geq t) \leq exp (- \frac{2 t ^{2}}{\sum _{i = 1}^{n} ( b _{i} - a _{i} ) ^{2}})

Explanation: For independent Xi in [ $a_{i}$ , $b_{i}$ ], the sum S concentrates with an exponent depending on the sum of squared ranges.

Chernoff (Multiplicative Upper Tail)

Pr (S \geq (1 + δ) μ) \leq exp (- μ [δ - ln (1 + δ)])

Explanation: For a sum of independent Bernoulli or sub-Gaussian-like terms with mean $μ,$ the upper tail decays exponentially. Valid for all $δ > 0$ and tighter than quadratic forms for large $δ .$

Chernoff (Simplified)

Pr (S \geq (1 + δ) μ) \leq exp (- \frac{δ ^{2} μ}{3}), 0 \leq δ \leq 1

Explanation: A convenient, slightly looser version for relative errors up to 100%. It clearly shows exponential decay in μ and $δ^{2} .$

Bernstein for Means

Pr (\overline{X} - μ \geq t) \leq 2 exp (- \frac{n t ^{2}}{2 σ ^{2} + \frac{2}{3} ( b - a ) t})

Explanation: Uses both variance $σ^{2}$ and boundedness [a,b]. It improves over Hoeffding when variance is small or t is moderate.

McDiarmid Inequality (One-Sided)

Pr (f (X) - E [f (X)] \geq t) \leq exp (- \frac{2 t ^{2}}{\sum _{i = 1}^{n} c _{i}^{2}})

Explanation: If changing Xi affects f by at most $c_{i}$ , then f concentrates around its mean. This handles many non-linear statistics.

Sub-Gaussian Tail

E [e^{λ (X - μ)}] \leq exp (\frac{λ ^{2} σ ^{2}}{2}) \Rightarrow Pr (∣ X - μ ∣ \geq t) \leq 2 e^{- t^{2} / (2 σ^{2})}

Explanation: An MGF-based definition of sub-Gaussian variables leads to Gaussian-like tail bounds. Useful as a unifying template.

Chernoff via KL

Pr (S \geq n q) \leq exp (- n D (q ∥ p)), S \sim Bin (n, p)

Explanation: For Binomial tails, the bound uses KL divergence D(q||p)=q $ln \frac{q}{p}$ +(1−q) $ln$ ((1−q)/(1−p)). It is tight and valid for any $q > p$ .

Union Bound

Pr (i = 1 ⋃ m A_{i}) \leq i = 1 \sum m Pr (A_{i})

Explanation: Controls the probability that any of several bad events occurs by summing their probabilities. Enables simultaneous guarantees, e.g., over hypotheses.

Azuma–Hoeffding

Pr (M_{n} - M_{0} \geq t) \leq exp (- \frac{2 t ^{2}}{\sum _{i = 1}^{n} c _{i}^{2}})

Explanation: For martingales with bounded differences $∣ M_{i} - M_{i - 1} ∣$ ≤ $c_{i}$ , deviations are exponentially unlikely. Generalizes Hoeffding beyond independence.

Complexity Analysis

Computing a concentration bound is typically O(1) time and space: each inequality is a closed-form function of parameters such as n (sample size), t (deviation), known ranges [a,b], and possibly variance

σ^{2} .

For example, Hoeffding’s bound for means uses exp(−2n

t^{2}

/(b−a)^2), and Bernstein’s uses exp(− n

t^{2}

/(2

σ^{2}

+ 2(b−a)t/3)); both can be evaluated with a few arithmetic operations and a call to exp, requiring constant time and memory. When validating bounds empirically by Monte Carlo simulation, complexity depends on the number of trials T and per-trial sample size n. Generating T independent datasets of size n and computing sample means costs O(T·n) time and O(1)–O(n) space depending on whether you store samples or stream them. For sums of Bernoulli variables, using std::binomia

l_{d} i s t r ib u t i o n

reduces per-trial time to O(1) for the sum; otherwise, simulating individual flips is O(n) per trial. Estimating empirical tail probabilities to within additive error ε with confidence 1−δ requires

T = O ((1/ ε^{2}

) log(1/

δ))

trials by Hoeffding, so the full simulation can cost O((n/

ε^{2})

log(1/

δ))

time if each trial processes n samples. Exact tail probabilities for Binomial distributions can be computed via dynamic programming or cumulative sums in O(n)–O(n log n) time depending on implementation, while Chernoff/KL bounds remain O(1). In practice, for large n, one prefers analytic bounds

\frac{C h er n o ff}{Hoe ffd in g}

for speed and numerical stability, resorting to normal approximations or saddlepoint methods when tighter estimates are required. Memory usage remains constant unless storing histograms or samples, in which case it scales with the number of bins or n, respectively.

Code Examples

Empirical vs. Chebyshev and Hoeffding for Bernoulli Means

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Compute Chebyshev and Hoeffding bounds for |Xbar - mu| >= t
5 // for n i.i.d. Bernoulli(p) variables (bounded in [0,1]).
6 int main() {
7     ios::sync_with_stdio(false);
8     cin.tie(nullptr);
9 
10     int n = 1000;            // samples per trial
11     int trials = 20000;      // number of Monte Carlo trials
12     double p = 0.5;          // Bernoulli parameter
13     double t = 0.08;         // deviation threshold for the sample mean
14 
15     // Theoretical quantities
16     double mu = p;                                 // mean of Bernoulli
17     double varX = p * (1.0 - p);                   // variance of a single Bernoulli
18     double varXbar = varX / n;                     // variance of the sample mean
19     double chebyshev = varXbar / (t * t);          // P(|Xbar - mu| >= t) <= Var(Xbar)/t^2
20     double hoeffding = 2.0 * exp(-2.0 * n * t * t); // Hoeffding for Xi in [0,1]
21 
22     // Monte Carlo simulation to estimate the true tail probability
23     mt19937_64 rng(123456789);
24     bernoulli_distribution bern(p);
25 
26     int exceed = 0;
27     for (int tr = 0; tr < trials; ++tr) {
28         int sum = 0;
29         for (int i = 0; i < n; ++i) sum += bern(rng);
30         double xbar = static_cast<double>(sum) / n;
31         if (fabs(xbar - mu) >= t) ++exceed;
32     }
33     double empirical = static_cast<double>(exceed) / trials;
34 
35     cout.setf(ios::fixed); cout << setprecision(6);
36     cout << "Parameters: n=" << n << ", p=" << p << ", t=" << t << "\n";
37     cout << "Empirical P(|Xbar-mu|>=t):    " << empirical << "\n";
38     cout << "Chebyshev upper bound:       " << min(1.0, chebyshev) << "\n";
39     cout << "Hoeffding upper bound:       " << min(1.0, hoeffding) << "\n";
40     return 0;
41 }
42

We estimate the probability that the sample mean of Bernoulli(p) deviates by at least t from its mean. Chebyshev uses only variance and is typically loose, while Hoeffding uses boundedness to give an exponentially small bound. The simulation shows the empirical tail probability and compares it to both bounds.

Time: O(trials · n) for simulation; O(1) to compute each boundSpace: O(1)

Chernoff Bound for Binomial Tails (with Monte Carlo Check)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Chernoff simplified bound for upper tail: P(S >= (1+delta) mu) <= exp(-delta^2 * mu / 3), for 0<=delta<=1
5 // Also provides a KL-based version: P(S >= k) <= exp(-n * D(k/n || p))
6 
7 static double kl_divergence(double q, double p) {
8     // D(q || p) = q ln(q/p) + (1-q) ln((1-q)/(1-p))
9     // Handle edge cases numerically safely
10     const double eps = 1e-12;
11     q = min(max(q, eps), 1.0 - eps);
12     p = min(max(p, eps), 1.0 - eps);
13     return q * log(q / p) + (1 - q) * log((1 - q) / (1 - p));
14 }
15 
16 int main() {
17     ios::sync_with_stdio(false);
18     cin.tie(nullptr);
19 
20     int n = 2000;          // number of Bernoulli trials
21     double p = 0.3;        // success probability
22     double delta = 0.3;    // relative deviation (0 <= delta <= 1 for the simplified bound)
23 
24     double mu = n * p;
25     int k = static_cast<int>(floor((1.0 + delta) * mu)); // threshold
26 
27     // Bounds
28     double chernoff_simple = exp(-(delta * delta) * mu / 3.0);
29     double q = static_cast<double>(k) / n;               // target proportion
30     double chernoff_kl = exp(-n * kl_divergence(q, p));  // KL-based Chernoff bound
31 
32     // Monte Carlo estimate using Binomial sampler
33     mt19937_64 rng(987654321);
34     binomial_distribution<int> binom(n, p);
35 
36     int trials = 100000; // number of Monte Carlo trials
37     int exceed = 0;
38     for (int t = 0; t < trials; ++t) {
39         int s = binom(rng);
40         if (s >= k) ++exceed;
41     }
42     double empirical = static_cast<double>(exceed) / trials;
43 
44     cout.setf(ios::fixed); cout << setprecision(6);
45     cout << "Parameters: n=" << n << ", p=" << p << ", delta=" << delta << "\n";
46     cout << "Threshold k=(1+delta)mu:     " << k << "\n";
47     cout << "Empirical P(S>=k):           " << empirical << "\n";
48     cout << "Chernoff (simplified) bound:  " << min(1.0, chernoff_simple) << "\n";
49     cout << "Chernoff (KL) bound:          " << min(1.0, chernoff_kl) << "\n";
50     return 0;
51 }
52

For S~Bin(n,p), we compare the empirical upper-tail probability P(S ≥ (1+δ)μ) to Chernoff bounds. The simplified form shows the classic e^{−δ^2 μ/3} scaling for δ∈[0,1]. The KL-based Chernoff bound is typically tighter and valid for any threshold k, using D(q||p).

Time: O(trials) when using std::binomial_distribution; O(1) to evaluate boundsSpace: O(1)

McDiarmid’s Inequality for a 1/n-Lipschitz Average

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // We consider f(X) = (1/n) * sum Xi with Xi in [0,1]. Then changing one Xi changes f by at most 1/n.
5 // McDiarmid: P(|f - E[f]| >= t) <= 2 * exp( - 2 * t^2 / sum c_i^2 ), with c_i = 1/n => sum c_i^2 = 1/n.
6 // Thus P(|f - E[f]| >= t) <= 2 * exp(-2 * n * t^2), identical to Hoeffding for means in [0,1].
7 
8 int main() {
9     ios::sync_with_stdio(false);
10     cin.tie(nullptr);
11 
12     int n = 800;               // number of variables in the average
13     int trials = 30000;        // Monte Carlo trials
14     double t = 0.07;           // deviation threshold
15 
16     // We'll draw Xi ~ Uniform[0,1], so E[f] = 0.5 exactly.
17     double Ef = 0.5;
18 
19     // McDiarmid two-sided bound
20     double mcdiarmid = 2.0 * exp(-2.0 * n * t * t);
21 
22     mt19937_64 rng(2024);
23     uniform_real_distribution<double> uni(0.0, 1.0);
24 
25     int exceed = 0;
26     vector<double> x(n);
27     for (int tr = 0; tr < trials; ++tr) {
28         double sum = 0.0;
29         for (int i = 0; i < n; ++i) {
30             x[i] = uni(rng);
31             sum += x[i];
32         }
33         double f = sum / n;
34         if (fabs(f - Ef) >= t) ++exceed;
35     }
36 
37     double empirical = static_cast<double>(exceed) / trials;
38 
39     cout.setf(ios::fixed); cout << setprecision(6);
40     cout << "Parameters: n=" << n << ", t=" << t << " (Xi ~ Uniform[0,1])\n";
41     cout << "Empirical P(|f-Ef|>=t):  " << empirical << "\n";
42     cout << "McDiarmid upper bound:    " << min(1.0, mcdiarmid) << "\n";
43     return 0;
44 }
45

We study f(X)=average(Xi) with Xi∈[0,1]. Changing one coordinate shifts f by at most 1/n, so the bounded-differences condition holds with c_i=1/n. McDiarmid then yields the same two-sided bound as Hoeffding for bounded means. The simulation confirms concentration around 0.5.

Time: O(trials · n)Space: O(n) to store a sample vector (can be reduced to O(1) by streaming)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Compute Chebyshev and Hoeffding bounds for \|Xbar - mu\| >= t
5	// for n i.i.d. Bernoulli(p) variables (bounded in [0,1]).
6	int main() {
7	ios::sync_with_stdio(false);
8	cin.tie(nullptr);
9
10	int n = 1000; // samples per trial
11	int trials = 20000; // number of Monte Carlo trials
12	double p = 0.5; // Bernoulli parameter
13	double t = 0.08; // deviation threshold for the sample mean
14
15	// Theoretical quantities
16	double mu = p; // mean of Bernoulli
17	double varX = p * (1.0 - p); // variance of a single Bernoulli
18	double varXbar = varX / n; // variance of the sample mean
19	double chebyshev = varXbar / (t * t); // P(\|Xbar - mu\| >= t) <= Var(Xbar)/t^2
20	double hoeffding = 2.0 * exp(-2.0 * n * t * t); // Hoeffding for Xi in [0,1]
21
22	// Monte Carlo simulation to estimate the true tail probability
23	mt19937_64 rng(123456789);
24	bernoulli_distribution bern(p);
25
26	int exceed = 0;
27	for (int tr = 0; tr < trials; ++tr) {
28	int sum = 0;
29	for (int i = 0; i < n; ++i) sum += bern(rng);
30	double xbar = static_cast<double>(sum) / n;
31	if (fabs(xbar - mu) >= t) ++exceed;
32	}
33	double empirical = static_cast<double>(exceed) / trials;
34
35	cout.setf(ios::fixed); cout << setprecision(6);
36	cout << "Parameters: n=" << n << ", p=" << p << ", t=" << t << "\n";
37	cout << "Empirical P(\|Xbar-mu\|>=t): " << empirical << "\n";
38	cout << "Chebyshev upper bound: " << min(1.0, chebyshev) << "\n";
39	cout << "Hoeffding upper bound: " << min(1.0, hoeffding) << "\n";
40	return 0;
41	}
42

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Chernoff simplified bound for upper tail: P(S >= (1+delta) mu) <= exp(-delta^2 * mu / 3), for 0<=delta<=1
5	// Also provides a KL-based version: P(S >= k) <= exp(-n * D(k/n \|\| p))
6
7	static double kl_divergence(double q, double p) {
8	// D(q \|\| p) = q ln(q/p) + (1-q) ln((1-q)/(1-p))
9	// Handle edge cases numerically safely
10	const double eps = 1e-12;
11	q = min(max(q, eps), 1.0 - eps);
12	p = min(max(p, eps), 1.0 - eps);
13	return q * log(q / p) + (1 - q) * log((1 - q) / (1 - p));
14	}
15
16	int main() {
17	ios::sync_with_stdio(false);
18	cin.tie(nullptr);
19
20	int n = 2000; // number of Bernoulli trials
21	double p = 0.3; // success probability
22	double delta = 0.3; // relative deviation (0 <= delta <= 1 for the simplified bound)
23
24	double mu = n * p;
25	int k = static_cast<int>(floor((1.0 + delta) * mu)); // threshold
26
27	// Bounds
28	double chernoff_simple = exp(-(delta * delta) * mu / 3.0);
29	double q = static_cast<double>(k) / n; // target proportion
30	double chernoff_kl = exp(-n * kl_divergence(q, p)); // KL-based Chernoff bound
31
32	// Monte Carlo estimate using Binomial sampler
33	mt19937_64 rng(987654321);
34	binomial_distribution<int> binom(n, p);
35
36	int trials = 100000; // number of Monte Carlo trials
37	int exceed = 0;
38	for (int t = 0; t < trials; ++t) {
39	int s = binom(rng);
40	if (s >= k) ++exceed;
41	}
42	double empirical = static_cast<double>(exceed) / trials;
43
44	cout.setf(ios::fixed); cout << setprecision(6);
45	cout << "Parameters: n=" << n << ", p=" << p << ", delta=" << delta << "\n";
46	cout << "Threshold k=(1+delta)mu: " << k << "\n";
47	cout << "Empirical P(S>=k): " << empirical << "\n";
48	cout << "Chernoff (simplified) bound: " << min(1.0, chernoff_simple) << "\n";
49	cout << "Chernoff (KL) bound: " << min(1.0, chernoff_kl) << "\n";
50	return 0;
51	}
52

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// We consider f(X) = (1/n) * sum Xi with Xi in [0,1]. Then changing one Xi changes f by at most 1/n.
5	// McDiarmid: P(\|f - E[f]\| >= t) <= 2 * exp( - 2 * t^2 / sum c_i^2 ), with c_i = 1/n => sum c_i^2 = 1/n.
6	// Thus P(\|f - E[f]\| >= t) <= 2 * exp(-2 * n * t^2), identical to Hoeffding for means in [0,1].
7
8	int main() {
9	ios::sync_with_stdio(false);
10	cin.tie(nullptr);
11
12	int n = 800; // number of variables in the average
13	int trials = 30000; // Monte Carlo trials
14	double t = 0.07; // deviation threshold
15
16	// We'll draw Xi ~ Uniform[0,1], so E[f] = 0.5 exactly.
17	double Ef = 0.5;
18
19	// McDiarmid two-sided bound
20	double mcdiarmid = 2.0 * exp(-2.0 * n * t * t);
21
22	mt19937_64 rng(2024);
23	uniform_real_distribution<double> uni(0.0, 1.0);
24
25	int exceed = 0;
26	vector<double> x(n);
27	for (int tr = 0; tr < trials; ++tr) {
28	double sum = 0.0;
29	for (int i = 0; i < n; ++i) {
30	x[i] = uni(rng);
31	sum += x[i];
32	}
33	double f = sum / n;
34	if (fabs(f - Ef) >= t) ++exceed;
35	}
36
37	double empirical = static_cast<double>(exceed) / trials;
38
39	cout.setf(ios::fixed); cout << setprecision(6);
40	cout << "Parameters: n=" << n << ", t=" << t << " (Xi ~ Uniform[0,1])\n";
41	cout << "Empirical P(\|f-Ef\|>=t): " << empirical << "\n";
42	cout << "McDiarmid upper bound: " << min(1.0, mcdiarmid) << "\n";
43	return 0;
44	}
45