AFTD Auto-Formalizing Theoretical Domains

fair_binomial_exp_tail_bound

theoremverifiedformalization

Let n ≥ 1 be an integer and let X be a binomial random variable with parameters n and 1/2 on a probability space (Ω, μ). For any α ∈ (0,1), the probability that |X - n/2| ≥ α n / 2 is at most 2 * exp(-α^2 * n / 6).

Statement

open MeasureTheory ProbabilityTheory
open scoped unitInterval

theorem fair_binomial_exp_tail_bound
    {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]
    (n : ℕ) (hn : 1 ≤ n) (X : Ω → ℕ)
    (hX : HasLaw X (binomial n ⟨1/2, by norm_num⟩) μ)
    (α : ℝ) (hα_pos : 0 < α) (hα_lt_one : α < 1) :
    μ.real {ω | α * (n : ℝ) / 2 ≤ |(X ω : ℝ) - (n : ℝ) / 2|} ≤
      2 * Real.exp (- α ^ 2 * (n : ℝ) / 6)
Formalizes
scout/2610-16830-the-communication-complexity-of-the-coin-problem.md:333 Theorem 2.7
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any probability space $(\Omega, \mu)$, any integer $n \ge 1$, any random variable $X : \Omega \to \mathbb{N}$ whose law under $\mu$ is the binomial distribution with parameters $n$ and success probability $1/2$ (in $[0, 1]$), and any real number $\alpha$ strictly between $0$ and $1$ ($0 < \alpha < 1$): the $\mu$-measure (evaluated to a real number) of the event $\{\omega \in \Omega \mid |X(\omega) - n/2| \ge \alpha n / 2\}$ is at most $2 \exp(-\alpha^2 n / 6)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof establishes an exponential tail bound for a fair binomial variable X ~ Binomial(n, 1/2) using Chernoff's bounding method. First, the moment generating function of the centered variable X - n/2 is evaluated in closed form as cosh(t/2)^n via the binomial theorem. The two-sided tail |X - n/2| ≥ α n / 2 is split into upper and lower tails, each bounded by exp(-α^2 n) cosh(α)^n via Chernoff's inequality at t = ±2α. Using the inequality cosh α ≤ exp(α^2 / 2), each tail is bounded by exp(-α^2 n / 6), and summing them yields the final bound 2 * exp(-α^2 n / 6).

  1. The binomial sum ∑_{k=0}^n (n choose k) (exp t)^k equals (1 + exp t)^n.

    By the binomial theorem (add_pow), expanding (exp t + 1)^n over the range 0 to n gives the sum of (exp t)^m * 1^(n-m) * (n choose m). Commuting the terms and simplifying the powers of 1 establishes the identity for the sum over k ≤ n.

    lines 1–10

    uses add_comm, add_pow, Finset.sum_congr, one_pow, mul_one

    lemma fair_binomial_exp_tail_bound_sum_id (n : ℕ) (t : ℝ) :
        ∑ k ∈ Finset.Iic n,
          ((n.choose k : ℝ) * (1/2:ℝ) ^ k * (1/2:ℝ) ^ (n - k) * Real.exp (t * ((k:ℝ) - (n:ℝ)/2)))
          = Real.cosh (t/2) ^ n := by
      have hsum : ∑ k ∈ Finset.Iic n, ((n.choose k : ℝ) * (Real.exp t)^k) = (1 + Real.exp t)^n := by
        rw [add_comm 1 (Real.exp t), add_pow (Real.exp t) 1 n]
        rw [show Finset.Iic n = Finset.range (n+1) from by ext k; simp]
        refine Finset.sum_congr rfl fun k hk => ?_
        simp only [one_pow, mul_one]
        ring
  2. Each summand factors into a constant factor (1/2)^n * exp(-t*n/2) and (n choose k) * (exp t)^k.

    For any k ≤ n, the product (1/2)^k * (1/2)^(n-k) simplifies to (1/2)^n since k + (n - k) = n. Similarly, the exponential exp(t * (k - n/2)) splits as (exp t)^k * exp(-t*n/2). Rearranging the terms gives the desired factorization.

    lines 11–25

    uses Finset.mem_Iic.mp, pow_add, Nat.add_sub_cancel', Real.exp_nat_mul, Real.exp_add

      have step : ∀ k ∈ Finset.Iic n,
          ((n.choose k : ℝ) * (1/2:ℝ) ^ k * (1/2:ℝ) ^ (n - k) * Real.exp (t * ((k:ℝ) - (n:ℝ)/2)))
          = ((1/2:ℝ)^n * Real.exp (-(t*(n:ℝ)/2))) * ((n.choose k : ℝ) * (Real.exp t)^k) := by
        intro k hk
        have hk' : k ≤ n := Finset.mem_Iic.mp hk
        have hp : (1/2:ℝ)^k * (1/2:ℝ)^(n-k) = (1/2:ℝ)^n := by
          rw [← pow_add, Nat.add_sub_cancel' hk']
        have he : Real.exp (t * ((k:ℝ) - (n:ℝ)/2)) = (Real.exp t)^k * Real.exp (-(t*(n:ℝ)/2)) := by
          rw [← Real.exp_nat_mul, ← Real.exp_add]
          congr 1
          ring
        calc (n.choose k : ℝ) * (1/2:ℝ) ^ k * (1/2:ℝ) ^ (n - k) * Real.exp (t * ((k:ℝ) - (n:ℝ)/2))
            = ((1/2:ℝ)^k * (1/2:ℝ)^(n-k)) * (n.choose k : ℝ) * Real.exp (t * ((k:ℝ) - (n:ℝ)/2)) := by ring
          _ = (1/2:ℝ)^n * (n.choose k : ℝ) * ((Real.exp t)^k * Real.exp (-(t*(n:ℝ)/2))) := by rw [hp, he]
          _ = ((1/2:ℝ)^n * Real.exp (-(t*(n:ℝ)/2))) * ((n.choose k : ℝ) * (Real.exp t)^k) := by ring
  3. The fair binomial exponential sum equals cosh(t/2)^n.

    Factoring out (1/2)^n * exp(-t*n/2) from the sum leaves (1 + exp t)^n. Expressing exp(-t*n/2) as (exp(-t/2))^n allows the entire product to be grouped as ((1/2) * exp(-t/2) * (1 + exp t))^n. Multiplying through yields (1/2) * (exp(t/2) + exp(-t/2)), which is exactly cosh(t/2) by definition, completing the proof of fair_binomial_exp_tail_bound_sum_id.

    lines 26–38

    uses Finset.sum_congr, Finset.mul_sum, Real.exp_nat_mul, mul_pow, Real.cosh_eq, Real.exp_add, mul_add, mul_one, mul_assoc

      rw [Finset.sum_congr rfl step, ← Finset.mul_sum, hsum]
      have h1 : Real.exp (-(t*(n:ℝ)/2)) = (Real.exp (-(t/2)))^n := by
        rw [show -(t * (n:ℝ) / 2) = (n:ℝ) * (-(t/2)) by ring, Real.exp_nat_mul]
      rw [h1, ← mul_pow, ← mul_pow]
      congr 1
      rw [Real.cosh_eq]
      have h2 : Real.exp (-(t/2)) * Real.exp t = Real.exp (t/2) := by
        rw [← Real.exp_add]; congr 1; ring
      rw [mul_add, mul_one]
      have h3 : (1/2:ℝ) * Real.exp (-(t/2)) * Real.exp t = 1/2 * Real.exp (t/2) := by
        rw [mul_assoc, h2]
      rw [h3]
      ring
  4. The moment generating function of the centered fair binomial variable is cosh(t/2)^n.

    Unfolding the definition of ProbabilityTheory.mgf evaluates it as the integral with respect to the binomial measure, which expands via ProbabilityTheory.integral_binomial to the sum evaluated in fair_binomial_exp_tail_bound_sum_id.

    lines 39–46

    uses ProbabilityTheory.mgf, ProbabilityTheory.integral_binomial, smul_eq_mul, fair_binomial_exp_tail_bound_sum_id

    lemma fair_binomial_exp_tail_bound_mgf_eq (n : ℕ) (t : ℝ) :
        ProbabilityTheory.mgf (fun k : ℕ => (k:ℝ) - (n:ℝ)/2)
          (ProbabilityTheory.binomial n ⟨1/2, by norm_num⟩) t = Real.cosh (t/2) ^ n := by
      rw [ProbabilityTheory.mgf, ProbabilityTheory.integral_binomial]
      simp only [smul_eq_mul]
      norm_num
      exact fair_binomial_exp_tail_bound_sum_id n t
  5. The probability of a large deviation is bounded by the sum of the two one-sided tail probabilities.

    After transferring the measure of the event from X to the canonical binomial distribution on ℕ via its law, we set ε = α * n / 2. The event {k | ε ≤ |k - n/2|} is contained in the union of {k | ε ≤ k - n/2} and {k | k - n/2 ≤ -ε}. By monotonicity and subadditivity of the probability measure, the probability of the absolute deviation is at most the sum of the upper and lower tail probabilities.

    lines 47–77

    uses Set.mem_ofPred_eq, Set.mem_union, le_total, Or.inl, abs_of_nonneg, Or.inr, abs_of_nonpos, measureReal_mono, measure_ne_top, measureReal_union_le

    open MeasureTheory ProbabilityTheory
    open scoped unitInterval
    /-- Exponential tail bound for the fair binomial distribution B(n, 1/2). -/
    theorem fair_binomial_exp_tail_bound
        {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]
        (n : ℕ) (hn : 1 ≤ n) (X : Ω → ℕ)
        (hX : HasLaw X (binomial n ⟨1/2, by norm_num⟩) μ)
        (α : ℝ) (hα_pos : 0 < α) (hα_lt_one : α < 1) :
        μ.real {ω | α * (n : ℝ) / 2 ≤ |(X ω : ℝ) - (n : ℝ) / 2|} ≤
          2 * Real.exp (- α ^ 2 * (n : ℝ) / 6) := by
      have hmeas : MeasurableSet {k : ℕ | α * (n:ℝ)/2 ≤ |(k:ℝ) - (n:ℝ)/2|} := by measurability
      rw [hX.measureReal_eq hmeas]
      set ε : ℝ := α * (n:ℝ)/2 with hε
      have hαn : 0 < α^2 * (n:ℝ) := by positivity
      have hsubset : {k : ℕ | ε ≤ |(k:ℝ) - (n:ℝ)/2|}
          ⊆ {k : ℕ | ε ≤ (k:ℝ) - (n:ℝ)/2} ∪ {k : ℕ | (k:ℝ) - (n:ℝ)/2 ≤ -ε} := by
        intro k hk
        simp only [Set.mem_ofPred_eq, Set.mem_union] at hk ⊢
        rcases le_total 0 ((k:ℝ) - (n:ℝ)/2) with h | h
        · exact Or.inl (by rw [abs_of_nonneg h] at hk; exact hk)
        · exact Or.inr (by rw [abs_of_nonpos h] at hk; linarith)
      have hmono : (binomial n ⟨1/2, by norm_num⟩).real {k : ℕ | ε ≤ |(k:ℝ) - (n:ℝ)/2|}
          ≤ (binomial n ⟨1/2, by norm_num⟩).real
            ({k : ℕ | ε ≤ (k:ℝ) - (n:ℝ)/2} ∪ {k : ℕ | (k:ℝ) - (n:ℝ)/2 ≤ -ε}) :=
        measureReal_mono hsubset (measure_ne_top _ _)
      have hunion : (binomial n ⟨1/2, by norm_num⟩).real
          ({k : ℕ | ε ≤ (k:ℝ) - (n:ℝ)/2} ∪ {k : ℕ | (k:ℝ) - (n:ℝ)/2 ≤ -ε})
          ≤ (binomial n ⟨1/2, by norm_num⟩).real {k : ℕ | ε ≤ (k:ℝ) - (n:ℝ)/2}
            + (binomial n ⟨1/2, by norm_num⟩).real {k : ℕ | (k:ℝ) - (n:ℝ)/2 ≤ -ε} :=
        measureReal_union_le _ _
  6. The upper tail probability P(k - n/2 ≥ ε) is at most exp(-α^2 * n) * cosh(α)^n.

    Applying Chernoff's upper bound (measure_ge_le_exp_mul_mgf) with parameter t = 2 * α > 0 bounds the upper tail by exp(-(2*α) * ε) * mgf (2*α). Since ε = α * n / 2, the exponent is -(2*α) * (α * n / 2) = -α^2 * n. By the MGF identity, mgf (2*α) = cosh((2*α)/2)^n = cosh(α)^n.

    lines 78–87

    uses integrable_binomial, measure_ge_le_exp_mul_mgf, fair_binomial_exp_tail_bound_mgf_eq

      have hU : (binomial n ⟨1/2, by norm_num⟩).real {k : ℕ | ε ≤ (k:ℝ) - (n:ℝ)/2}
          ≤ Real.exp (-(α^2 * (n:ℝ))) * Real.cosh α ^ n := by
        have hint : Integrable (fun k : ℕ => Real.exp ((2*α) * ((k:ℝ) - (n:ℝ)/2)))
            (binomial n ⟨1/2, by norm_num⟩) := integrable_binomial _
        have h := measure_ge_le_exp_mul_mgf (μ := binomial n ⟨1/2, by norm_num⟩)
          (X := fun k : ℕ => (k:ℝ) - (n:ℝ)/2) (t := 2*α) ε (by positivity) hint
        rw [fair_binomial_exp_tail_bound_mgf_eq] at h
        rw [show (2*α)/2 = α by ring] at h
        rw [show -(2*α) * ε = -(α^2 * (n:ℝ)) by rw [hε]; ring] at h
        exact h
  7. The lower tail probability P(k - n/2 ≤ -ε) is at most exp(-α^2 * n) * cosh(α)^n.

    Applying Chernoff's lower bound (measure_le_le_exp_mul_mgf) with parameter t = -(2 * α) ≤ 0 bounds the lower tail by exp(-(-(2*α)) * (-ε)) * mgf (-(2*α)). The exponential prefactor is again exp(-α^2 * n), and since cosh is an even function, cosh(-(2*α)/2)^n = cosh(α)^n.

    lines 88–97

    uses integrable_binomial, measure_le_le_exp_mul_mgf, fair_binomial_exp_tail_bound_mgf_eq, Real.cosh_neg

      have hL : (binomial n ⟨1/2, by norm_num⟩).real {k : ℕ | (k:ℝ) - (n:ℝ)/2 ≤ -ε}
          ≤ Real.exp (-(α^2 * (n:ℝ))) * Real.cosh α ^ n := by
        have hint : Integrable (fun k : ℕ => Real.exp ((-(2*α)) * ((k:ℝ) - (n:ℝ)/2)))
            (binomial n ⟨1/2, by norm_num⟩) := integrable_binomial _
        have h := measure_le_le_exp_mul_mgf (μ := binomial n ⟨1/2, by norm_num⟩)
          (X := fun k : ℕ => (k:ℝ) - (n:ℝ)/2) (t := -(2*α)) (-ε) (by linarith) hint
        rw [fair_binomial_exp_tail_bound_mgf_eq] at h
        rw [show (-(2*α))/2 = -α by ring, Real.cosh_neg] at h
        rw [show -(-(2*α)) * (-ε) = -(α^2 * (n:ℝ)) by rw [hε]; ring] at h
        exact h
  8. Each one-sided tail bound is at most exp(-α^2 * n / 6).

    Using the bound cosh α ≤ exp(α^2 / 2), we obtain cosh(α)^n ≤ exp(n * α^2 / 2). Multiplying by exp(-α^2 * n) yields exp(-α^2 * n / 2), which is at most exp(-α^2 * n / 6) because -α^2 * n / 2 ≤ -α^2 * n / 6.

    lines 98–109

    uses pow_le_pow_left₀, Real.cosh_le_exp_half_sq, Real.exp_nat_mul, Real.exp_add, Real.exp_le_exp.mpr

      have hcosh : Real.cosh α ^ n ≤ Real.exp ((n:ℝ) * (α^2/2)) := by
        calc Real.cosh α ^ n ≤ (Real.exp (α^2/2))^n :=
              pow_le_pow_left₀ (by positivity) (Real.cosh_le_exp_half_sq α) n
          _ = Real.exp ((n:ℝ) * (α^2/2)) := by rw [Real.exp_nat_mul]
      have htail : Real.exp (-(α^2 * (n:ℝ))) * Real.cosh α ^ n
          ≤ Real.exp (- α^2 * (n:ℝ) / 6) := by
        calc Real.exp (-(α^2 * (n:ℝ))) * Real.cosh α ^ n
            ≤ Real.exp (-(α^2 * (n:ℝ))) * Real.exp ((n:ℝ) * (α^2/2)) := by gcongr
          _ = Real.exp (-(α^2 * (n:ℝ)) + (n:ℝ) * (α^2/2)) := by rw [← Real.exp_add]
          _ ≤ Real.exp (- α^2 * (n:ℝ) / 6) := by
              apply Real.exp_le_exp.mpr
              linarith
  9. The two-sided tail probability is bounded by 2 * exp(-α^2 * n / 6).

    Combining the union bound with the two one-sided tail bounds, the total probability is at most exp(-α^2 * n / 6) + exp(-α^2 * n / 6) = 2 * exp(-α^2 * n / 6). Linear arithmetic concludes the proof.

    line 110

      linarith
add_comm
Addition is commutative: a + b = b + a.
add_pow
The binomial theorem: (x + y)^n = ∑_{m=0}^n x^m y^{n-m} (n choose m).
Finset.sum_congr
If two finite sets are equal and their summands agree, their sums are equal.
one_pow
Any power of 1 is 1: 1^n = 1.
mul_one
Multiplying by 1 leaves the element unchanged: a * 1 = a.
Finset.mem_Iic.mp
An element k belongs to the interval {x | x ≤ n} if and only if k ≤ n.
pow_add
Powers with the same base add exponents: a^(m+n) = a^m * a^n.
Nat.add_sub_cancel'
For natural numbers with m ≤ n, m + (n - m) = n.
Real.exp_nat_mul
Exponential of an integer multiple: exp(n * x) = (exp x)^n.
Real.exp_add
Exponential of a sum is the product of exponentials: exp(x + y) = exp x * exp y.
Finset.mul_sum
Multiplication distributes over finite sums: a * ∑ f_i = ∑ a * f_i.
mul_pow
In a commutative monoid, powers distribute over multiplication: (a * b)^n = a^n * b^n.
Real.cosh_eq
Definition of the hyperbolic cosine: cosh x = (exp x + exp(-x)) / 2.
mul_add
Multiplication distributes over addition: a * (b + c) = a * b + a * c.
mul_assoc
Multiplication is associative: a * b * c = a * (b * c).
ProbabilityTheory.mgf
The moment generating function of a random variable X at t is the integral of exp(t * X).
ProbabilityTheory.integral_binomial
The integral of a function with respect to the binomial distribution Binomial(n, p) is the weighted sum ∑ (n choose k) p^k (1-p)^(n-k) f(k).
smul_eq_mul
Real scalar multiplication is standard multiplication: a • b = a * b.
fair_binomial_exp_tail_bound_sum_id
Identity: ∑_{k=0}^n (n choose k) (1/2)^k (1/2)^(n-k) exp(t(k - n/2)) = cosh(t/2)^n.
Set.mem_ofPred_eq
Set comprehension membership: x ∈ {y | P y} ↔ P x.
Set.mem_union
An element is in A ∪ B if and only if it is in A or in B.
le_total
In any linear order, a ≤ b or b ≤ a.
Or.inl
Infers a disjunction P ∨ Q from the left disjunct P.
abs_of_nonneg
The absolute value of a non-negative number is itself: |a| = a if 0 ≤ a.
Or.inr
Infers a disjunction P ∨ Q from the right disjunct Q.
abs_of_nonpos
The absolute value of a non-positive number is its negation: |a| = -a if a ≤ 0.
measureReal_mono
Real-valued measure is monotone under set inclusion: s₁ ⊆ s₂ implies μ.real s₁ ≤ μ.real s₂.
measure_ne_top
In a finite measure space, the measure of any set is finite (not top).
measureReal_union_le
Real-valued measure is subadditive on unions: μ.real (s₁ ∪ s₂) ≤ μ.real s₁ + μ.real s₂.
integrable_binomial
Any function on ℕ is integrable with respect to a binomial distribution.
measure_ge_le_exp_mul_mgf
Chernoff upper tail bound: for t ≥ 0, μ.real {X ≥ ε} ≤ exp(-t * ε) * mgf X μ t.
measure_le_le_exp_mul_mgf
Chernoff lower tail bound: for t ≤ 0, μ.real {X ≤ ε} ≤ exp(-t * ε) * mgf X μ t.
fair_binomial_exp_tail_bound_mgf_eq
The moment generating function of the centered fair binomial variable k - n/2 is cosh(t/2)^n.
Real.cosh_neg
Hyperbolic cosine is an even function: cosh(-x) = cosh x.
pow_le_pow_left₀
Taking natural powers preserves order for non-negative reals: 0 ≤ a ≤ b implies a^n ≤ b^n.
Real.cosh_le_exp_half_sq
Standard upper bound on hyperbolic cosine: cosh x ≤ exp(x^2 / 2).
Real.exp_le_exp.mpr
The real exponential function is monotone: a ≤ b implies exp a ≤ exp b.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma fair_binomial_exp_tail_bound_sum_id (n : ℕ) (t : ℝ) :    ∑ k ∈ Finset.Iic n,      ((n.choose k : ℝ) * (1/2:ℝ) ^ k * (1/2:ℝ) ^ (n - k) * Real.exp (t * ((k:ℝ) - (n:ℝ)/2)))      = Real.cosh (t/2) ^ n := by  have hsum : ∑ k ∈ Finset.Iic n, ((n.choose k : ℝ) * (Real.exp t)^k) = (1 + Real.exp t)^n := by    rw [add_comm 1 (Real.exp t), add_pow (Real.exp t) 1 n]    rw [show Finset.Iic n = Finset.range (n+1) from by ext k; simp]    refine Finset.sum_congr rfl fun k hk => ?_    simp only [one_pow, mul_one]    ring  have step : ∀ k ∈ Finset.Iic n,      ((n.choose k : ℝ) * (1/2:ℝ) ^ k * (1/2:ℝ) ^ (n - k) * Real.exp (t * ((k:ℝ) - (n:ℝ)/2)))      = ((1/2:ℝ)^n * Real.exp (-(t*(n:ℝ)/2))) * ((n.choose k : ℝ) * (Real.exp t)^k) := by    intro k hk    have hk' : k ≤ n := Finset.mem_Iic.mp hk    have hp : (1/2:ℝ)^k * (1/2:ℝ)^(n-k) = (1/2:ℝ)^n := by      rw [← pow_add, Nat.add_sub_cancel' hk']    have he : Real.exp (t * ((k:ℝ) - (n:ℝ)/2)) = (Real.exp t)^k * Real.exp (-(t*(n:ℝ)/2)) := by      rw [← Real.exp_nat_mul, ← Real.exp_add]      congr 1      ring    calc (n.choose k : ℝ) * (1/2:ℝ) ^ k * (1/2:ℝ) ^ (n - k) * Real.exp (t * ((k:ℝ) - (n:ℝ)/2))        = ((1/2:ℝ)^k * (1/2:ℝ)^(n-k)) * (n.choose k : ℝ) * Real.exp (t * ((k:ℝ) - (n:ℝ)/2)) := by ring      _ = (1/2:ℝ)^n * (n.choose k : ℝ) * ((Real.exp t)^k * Real.exp (-(t*(n:ℝ)/2))) := by rw [hp, he]      _ = ((1/2:ℝ)^n * Real.exp (-(t*(n:ℝ)/2))) * ((n.choose k : ℝ) * (Real.exp t)^k) := by ring  rw [Finset.sum_congr rfl step, ← Finset.mul_sum, hsum]  have h1 : Real.exp (-(t*(n:ℝ)/2)) = (Real.exp (-(t/2)))^n := by    rw [show -(t * (n:ℝ) / 2) = (n:ℝ) * (-(t/2)) by ring, Real.exp_nat_mul]  rw [h1, ← mul_pow, ← mul_pow]  congr 1  rw [Real.cosh_eq]  have h2 : Real.exp (-(t/2)) * Real.exp t = Real.exp (t/2) := by    rw [← Real.exp_add]; congr 1; ring  rw [mul_add, mul_one]  have h3 : (1/2:ℝ) * Real.exp (-(t/2)) * Real.exp t = 1/2 * Real.exp (t/2) := by    rw [mul_assoc, h2]  rw [h3]  ringlemma fair_binomial_exp_tail_bound_mgf_eq (n : ℕ) (t : ℝ) :    ProbabilityTheory.mgf (fun k : ℕ => (k:ℝ) - (n:ℝ)/2)      (ProbabilityTheory.binomial n ⟨1/2, by norm_num⟩) t = Real.cosh (t/2) ^ n := by  rw [ProbabilityTheory.mgf, ProbabilityTheory.integral_binomial]  simp only [smul_eq_mul]  norm_num  exact fair_binomial_exp_tail_bound_sum_id n topen MeasureTheory ProbabilityTheoryopen scoped unitInterval/-- Exponential tail bound for the fair binomial distribution B(n, 1/2). -/theorem fair_binomial_exp_tail_bound    {Ω : Type*} [MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ]    (n : ℕ) (hn : 1 ≤ n) (X : Ω → ℕ)    (hX : HasLaw X (binomial n ⟨1/2, by norm_num⟩) μ)    (α : ℝ) (hα_pos : 0 < α) (hα_lt_one : α < 1) :    μ.real {ω | α * (n : ℝ) / 2 ≤ |(X ω : ℝ) - (n : ℝ) / 2|} ≤      2 * Real.exp (- α ^ 2 * (n : ℝ) / 6) := by  have hmeas : MeasurableSet {k : ℕ | α * (n:ℝ)/2 ≤ |(k:ℝ) - (n:ℝ)/2|} := by measurability  rw [hX.measureReal_eq hmeas]  set ε : ℝ := α * (n:ℝ)/2 with hε  have hαn : 0 < α^2 * (n:ℝ) := by positivity  have hsubset : {k : ℕ | ε ≤ |(k:ℝ) - (n:ℝ)/2|}      ⊆ {k : ℕ | ε ≤ (k:ℝ) - (n:ℝ)/2} ∪ {k : ℕ | (k:ℝ) - (n:ℝ)/2 ≤ -ε} := by    intro k hk    simp only [Set.mem_ofPred_eq, Set.mem_union] at hk ⊢    rcases le_total 0 ((k:ℝ) - (n:ℝ)/2) with h | h    · exact Or.inl (by rw [abs_of_nonneg h] at hk; exact hk)    · exact Or.inr (by rw [abs_of_nonpos h] at hk; linarith)  have hmono : (binomial n ⟨1/2, by norm_num⟩).real {k : ℕ | ε ≤ |(k:ℝ) - (n:ℝ)/2|}      ≤ (binomial n ⟨1/2, by norm_num⟩).real        ({k : ℕ | ε ≤ (k:ℝ) - (n:ℝ)/2} ∪ {k : ℕ | (k:ℝ) - (n:ℝ)/2 ≤ -ε}) :=    measureReal_mono hsubset (measure_ne_top _ _)  have hunion : (binomial n ⟨1/2, by norm_num⟩).real      ({k : ℕ | ε ≤ (k:ℝ) - (n:ℝ)/2} ∪ {k : ℕ | (k:ℝ) - (n:ℝ)/2 ≤ -ε})      ≤ (binomial n ⟨1/2, by norm_num⟩).real {k : ℕ | ε ≤ (k:ℝ) - (n:ℝ)/2}        + (binomial n ⟨1/2, by norm_num⟩).real {k : ℕ | (k:ℝ) - (n:ℝ)/2 ≤ -ε} :=    measureReal_union_le _ _  have hU : (binomial n ⟨1/2, by norm_num⟩).real {k : ℕ | ε ≤ (k:ℝ) - (n:ℝ)/2}      ≤ Real.exp (-(α^2 * (n:ℝ))) * Real.cosh α ^ n := by    have hint : Integrable (fun k : ℕ => Real.exp ((2*α) * ((k:ℝ) - (n:ℝ)/2)))        (binomial n ⟨1/2, by norm_num⟩) := integrable_binomial _    have h := measure_ge_le_exp_mul_mgf (μ := binomial n ⟨1/2, by norm_num⟩)      (X := fun k : ℕ => (k:ℝ) - (n:ℝ)/2) (t := 2*α) ε (by positivity) hint    rw [fair_binomial_exp_tail_bound_mgf_eq] at h    rw [show (2*α)/2 = α by ring] at h    rw [show -(2*α) * ε = -(α^2 * (n:ℝ)) by rw [hε]; ring] at h    exact h  have hL : (binomial n ⟨1/2, by norm_num⟩).real {k : ℕ | (k:ℝ) - (n:ℝ)/2 ≤ -ε}      ≤ Real.exp (-(α^2 * (n:ℝ))) * Real.cosh α ^ n := by    have hint : Integrable (fun k : ℕ => Real.exp ((-(2*α)) * ((k:ℝ) - (n:ℝ)/2)))        (binomial n ⟨1/2, by norm_num⟩) := integrable_binomial _    have h := measure_le_le_exp_mul_mgf (μ := binomial n ⟨1/2, by norm_num⟩)      (X := fun k : ℕ => (k:ℝ) - (n:ℝ)/2) (t := -(2*α)) (-ε) (by linarith) hint    rw [fair_binomial_exp_tail_bound_mgf_eq] at h    rw [show (-(2*α))/2 = -α by ring, Real.cosh_neg] at h    rw [show -(-(2*α)) * (-ε) = -(α^2 * (n:ℝ)) by rw [hε]; ring] at h    exact h  have hcosh : Real.cosh α ^ n ≤ Real.exp ((n:ℝ) * (α^2/2)) := by    calc Real.cosh α ^ n ≤ (Real.exp (α^2/2))^n :=          pow_le_pow_left₀ (by positivity) (Real.cosh_le_exp_half_sq α) n      _ = Real.exp ((n:ℝ) * (α^2/2)) := by rw [Real.exp_nat_mul]  have htail : Real.exp (-(α^2 * (n:ℝ))) * Real.cosh α ^ n      ≤ Real.exp (- α^2 * (n:ℝ) / 6) := by    calc Real.exp (-(α^2 * (n:ℝ))) * Real.cosh α ^ n        ≤ Real.exp (-(α^2 * (n:ℝ))) * Real.exp ((n:ℝ) * (α^2/2)) := by gcongr      _ = Real.exp (-(α^2 * (n:ℝ)) + (n:ℝ) * (α^2/2)) := by rw [← Real.exp_add]      _ ≤ Real.exp (- α^2 * (n:ℝ) / 6) := by          apply Real.exp_le_exp.mpr          linarith  linarith
See it in the graphDiscuss this resultChallenge it