All proofs
Project-declaredLean 4.8.0 · mathlib@b5eba5954288

Hoeffdings lemma

hoeffdings_lemma

Project documentation

The Beroulli case of Hoeffding's lemma

Exact Lean statement

lemma hoeffdings_lemma {p : ℝ} (m : p ∈ Icc 0 1) {t : ℝ} (t0 : 0 ≤ t) :
    (bernoulli p).exp (λ x ↦ (t * bif x then 1 else 0).exp) ≤ (t*p + t^2/8).exp

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
lemma hoeffdings_lemma {p : } (m : p  Icc 0 1) {t : } (t0 : 0  t) :    (bernoulli p).exp (λ x  (t * bif x then 1 else 0).exp)  (t*p + t^2/8).exp := by  simp only [exp_bernoulli_exp m]  have p1 : 0  1-p := by linarith [m.2]  by_cases tz : t = 0  · simp [tz]  replace t0 := (Ne.symm tz).lt_of_le t0; clear tz  rw [Real.exp_log (L_pos m), Real.exp_le_exp]  rcases L_taylor m t0 with a,_,h  simp only [L] at h; rw [h]; clear h; norm_num  generalize hb : p * a.exp = b  have b0 : 0  b := by rw [hb]; exact mul_nonneg m.1 (Real.exp_nonneg _)  have amgm : (1-p:) * b / (1 - p + b)^2  1/4 := mul_div_sq_sum_le p1 b0  simp only [mul_comm b _, mul_div _ _ (2 : )] at amgm   apply le_trans (add_le_add_right (mul_le_mul_of_nonneg_right amgm _) _)  swap; apply div_nonneg (pow_nonneg (le_of_lt t0) _) (by norm_num)  have e : (1:)/(4:) * (t^2 / (2:)) = t^2 / 8 := by ring  simp only [e, add_comm (t*p) _]; rfl
Project
debate
License
Apache-2.0
Commit
de3a6e500ae1
Source
Prob/Chernoff.lean:96-113

Reuse this declaration

Bring the exact result into your workflow

The import identifies the source module. Your project still needs the pinned package dependency shown on this page.

What this badge means

This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.

Continue in this project

Related declarations

Project-declaredLean 4.8.0

Alice pr le

alice_pr_le

Plain-language statement

Honest Alice has error ≥ e with probability ≤ q

probabilitycomplexity theoryinteractive protocols

Source project: debate

Person-level attribution pending.

View proof record
Project-declaredLean 4.8.0

Alice steps cost

alice_steps_cost

Plain-language statement

Alice makes few queries, regardless of Bob and Vera

probabilitycomplexity theoryinteractive protocols

Source project: debate

Person-level attribution pending.

View proof record
Project-declaredLean 4.8.0

Alices close

alices_close

Plain-language statement

Alice produces (p,y) with p close to o.probs y with good probability

probabilitycomplexity theoryinteractive protocols

Source project: debate

Person-level attribution pending.

View proof record