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).expFormal artifact
Lean source
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
Alice pr le
alice_pr_le
Plain-language statement
Honest Alice has error ≥ e with probability ≤ q
Source project: debate
Person-level attribution pending.
Alice steps cost
alice_steps_cost
Plain-language statement
Alice makes few queries, regardless of Bob and Vera
Source project: debate
Person-level attribution pending.
Alices close
alices_close
Plain-language statement
Alice produces (p,y) with p close to o.probs y with good probability
Source project: debate
Person-level attribution pending.