Documentation

Dynamics.Azuma

A maximal Azuma–Hoeffding inequality along i.i.d. uniform rounds #

Martingale concentration in the finite-probability layer: a process X_{j+1} = step X_j ρ_j driven by i.i.d. uniform rounds ρ_j : R (expectations by expList), and increments D (X_j) ρ_j with zero conditional mean, avg (D y) = 0 for every state y, and bounded by c. Their partial sums M_k = incrementSum step D x (l.take k) form a martingale, and

P(∃ k ≤ n, M_k ≥ λ) ≤ exp(-λ² / (2 n c²))

(K. Azuma, Weighted sums of certain dependent random variables, Tôhoku Math. J. 19, 1967; W. Hoeffding, J. Amer. Statist. Assoc. 58, 1963, Theorem 2 for the independent case), in the maximal form obtained from Ville's (Doob's) maximal inequality for the exponential supermartingale exp(θ M_k - k θ² c² / 2).

The state type σ is arbitrary (not necessarily finite), so this covers every martingale with respect to the rounds: take for σ the histories List R.

Why not Mathlib. Mathlib's Azuma–Hoeffding inequality (ProbabilityTheory.measure_sum_ge_le_of_hasCondSubgaussianMGF) is measure-theoretic (a filtration, conditional sub-Gaussian MGFs) and bounds P(M_n ≥ λ) at the final time only, not P(∃ k ≤ n, M_k ≥ λ); its Hoeffding lemma (hasSubgaussianMGF_of_mem_Icc_of_integral_eq_zero) is stated for integrals. Using them would need a bridge from avg/expList to measures on the path space, which this library avoids. Dynamics.Concentration and Dynamics.Chernoff only treat sums of independent coordinates (with Hoeffding's lemma for Bernoulli variables, one_sub_add_mul_exp_le), hence the elementary proofs here.

theorem Dynamics.ite_one_zero_le_of_imp {P Q : Prop} [Decidable P] [Decidable Q] (h : P → Q) :
(if P then 1 else 0) ≤ if Q then 1 else 0

An indicator is monotone in its event.

Sums of increments along the rounds #

noncomputable def Dynamics.incrementSum {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) (D : σ → R → ℝ) (x : σ) (l : List R) :

The sum ∑_{j < |l|} D (X_j) (l_j) of the increments D along the rounds l, for the process X_0 = x, X_{j+1} = step X_j l_j. When every avg (D y) vanishes, k ↦ incrementSum step D x (l.take k) is a martingale along i.i.d. uniform rounds l.

Equations
Instances For
    @[simp]
    theorem Dynamics.incrementSum_nil {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) (D : σ → R → ℝ) (x : σ) :
    incrementSum step D x [] = 0
    @[simp]
    theorem Dynamics.incrementSum_cons {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) (D : σ → R → ℝ) (x : σ) (a : R) (l : List R) :
    incrementSum step D x (a :: l) = D x a + incrementSum step D (step x a) l
    theorem Dynamics.incrementSum_add {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) (D E : σ → R → ℝ) (x : σ) (l : List R) :
    incrementSum step (fun (y : σ) (a : R) => D y a + E y a) x l = incrementSum step D x l + incrementSum step E x l

    Sums of increments are additive in the increments.

    theorem Dynamics.incrementSum_mono {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) {D E : σ → R → ℝ} (h : ∀ (y : σ) (a : R), D y a ≤ E y a) (x : σ) (l : List R) :
    incrementSum step D x l ≤ incrementSum step E x l

    Larger increments have a larger sum.

    @[simp]
    theorem Dynamics.incrementSum_zero {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) (x : σ) (l : List R) :
    incrementSum step (fun (x : σ) (x_1 : R) => 0) x l = 0
    theorem Dynamics.incrementSum_nonneg {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) {D : σ → R → ℝ} (h : ∀ (y : σ) (a : R), 0 ≤ D y a) (x : σ) (l : List R) :
    0 ≤ incrementSum step D x l

    Nonnegative increments have a nonnegative sum.

    theorem Dynamics.incrementSum_mul_sub {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) (D : σ → R → ℝ) (θ b : ℝ) (x : σ) (l : List R) :
    incrementSum step (fun (y : σ) (a : R) => θ * D y a - b) x l = θ * incrementSum step D x l - ↑l.length * b

    incrementSum of the affine increments θ D - b (the exponent of the exponential supermartingale).

    theorem Dynamics.incrementSum_neg {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) (D : σ → R → ℝ) (x : σ) (l : List R) :
    incrementSum step (fun (y : σ) (a : R) => -D y a) x l = -incrementSum step D x l

    Negated increments.

    theorem Dynamics.incrementSum_telescope {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) (φ ψ : σ → ℝ) (x : σ) (l : List R) :
    incrementSum step (fun (y : σ) (a : R) => φ (step y a) - φ y - ψ y) x l = φ (List.foldl step x l) - φ x - incrementSum step (fun (y : σ) (x : R) => ψ y) x l

    Increments of the form φ (step y a) - φ y - ψ y telescope.

    theorem Dynamics.incrementSum_take {σ : Type u_1} {R : Type u_2} (step : σ → R → σ) (ψ : σ → ℝ) (x : σ) (l : List R) (k : ℕ) (hk : k ≤ l.length) :
    incrementSum step (fun (y : σ) (x : R) => ψ y) x (List.take k l) = ∑ j ∈ Finset.range k, ψ (List.foldl step x (List.take j l))

    The sum of a state function along the first k rounds.

    Hoeffding's lemma, Ville's inequality and Azuma–Hoeffding #

    theorem Dynamics.avg_exp_mul_le {R : Type u_2} [Fintype R] {f : R → ℝ} {c : ℝ} (hmean : avg f = 0) (hb : ∀ (a : R), |f a| ≤ c) (θ : ℝ) :
    (avg fun (a : R) => Real.exp (θ * f a)) ≤ Real.exp (θ ^ 2 * c ^ 2 / 2)

    Hoeffding's lemma (Hoeffding 1963, (4.16)) for a uniform draw: if f has mean zero and |f| ≤ c, then avg (exp (θ f)) ≤ exp (θ² c² / 2).

    theorem Dynamics.expList_ville {σ : Type u_1} {R : Type u_2} [Fintype R] (step : σ → R → σ) (E : σ → R → ℝ) (M : σ → List R → ℝ) (hM0 : ∀ (x : σ), M x [] = 0) (hM : ∀ (x : σ) (a : R) (l : List R), M x (a :: l) = E x a + M (step x a) l) (hE : ∀ (y : σ), (avg fun (a : R) => Real.exp (E y a)) ≤ 1) (n : ℕ) (x : σ) {μ : ℝ} :
    0 < μ → (expList R n fun (l : List R) => if ∃ k ≤ n, μ ≤ Real.exp (M x (List.take k l)) then 1 else 0) ≤ 1 / μ

    Ville's maximal inequality along i.i.d. uniform rounds (finite horizon). Let M x (a :: l) = E x a + M (step x a) l, M x [] = 0, with avg (exp (E y ·)) ≤ 1 for every y, so that k ↦ exp (M x (l.take k)) is a nonnegative supermartingale started at 1. Then it reaches μ > 0 at some step k ≤ n with probability at most 1 / μ.

    theorem Dynamics.expList_exp_incrementSum_le {σ : Type u_1} {R : Type u_2} [Fintype R] (step : σ → R → σ) {D : σ → R → ℝ} {F : σ → ℝ} (h : ∀ (y : σ), (avg fun (a : R) => Real.exp (D y a) * F (step y a)) ≤ F y) (n : ℕ) (x : σ) :
    (expList R n fun (l : List R) => Real.exp (incrementSum step D x l) * F (List.foldl step x l)) ≤ F x

    Exponential supermartingale along i.i.d. uniform rounds (finite horizon). If one round never increases exp (D y ·) · F (step y ·) in expectation, avg (exp (D y a) F (step y a)) ≤ F y, then exp (incrementSum step D x l) · F (l.foldl step x) has expectation at most F x after any number n of rounds. With F = 1 it is the fixed-time bound for the supermartingale of expList_ville.

    theorem Dynamics.expList_azuma {σ : Type u_1} {R : Type u_2} [Fintype R] (step : σ → R → σ) (D : σ → R → ℝ) {c : ℝ} (hmean : ∀ (y : σ), avg (D y) = 0) (hbound : ∀ (y : σ) (a : R), |D y a| ≤ c) (x : σ) (n : ℕ) {lam : ℝ} (hlam : 0 ≤ lam) :
    (expList R n fun (l : List R) => if ∃ k ≤ n, lam ≤ incrementSum step D x (List.take k l) then 1 else 0) ≤ Real.exp (-(lam ^ 2 / (2 * ↑n * c ^ 2)))

    Maximal Azuma–Hoeffding inequality (Azuma 1967; Hoeffding 1963, Theorem 2, for independent summands). If the increments have zero mean over a uniform round, avg (D y) = 0, and are bounded, |D y a| ≤ c, then over n i.i.d. uniform rounds the martingale M_k = incrementSum step D x (l.take k) reaches λ ≥ 0 at some step k ≤ n with probability at most exp(-λ² / (2 n c²)).