Struct ConcentrationBound 

pub struct ConcentrationBound;

Concentration bounds for sums of independent bounded random variables.

Implementations

impl ConcentrationBound

pub fn hoeffding(t: f64, intervals: &[(f64, f64)]) -> f64

Hoeffding’s inequality: returns the upper bound on P(S_n - E[S_n] ≥ t) for n summands each bounded in [a_i, b_i].

Bound: exp(-2t² / Σ(b_i - a_i)²).

pub fn markov(expectation: f64, a: f64) -> f64

Markov inequality: P(X ≥ a) ≤ E[X] / a for non-negative X.

pub fn chebyshev(k: f64) -> f64

Chebyshev inequality: P(|X - μ| ≥ k·σ) ≤ 1/k².

pub fn chernoff_upper(mu: f64, delta: f64) -> f64

Chernoff bound for the sum of Bernoulli(p_i) variables with mean μ.

Upper tail: P(X ≥ (1+δ)μ) ≤ (e^δ / (1+δ)^(1+δ))^μ.

pub fn bernstein(t: f64, variance_sum: f64, c: f64) -> f64

Bernstein inequality for bounded random variables with variance s².

P(S_n ≥ t) ≤ exp(-t² / (2(s² + ct/3))) where c is the bound on individual terms.

pub fn sub_gaussian_tail(t: f64, sigma: f64) -> f64

Sub-Gaussian tail bound: P(X ≥ t) ≤ exp(-t²/(2σ²)) for σ-sub-Gaussian X.