fair_binomial_exp_tail_bound
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).
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.
uses
add_comm,add_pow,Finset.sum_congr,one_pow,mul_onelemma 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
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.
uses
Finset.mem_Iic.mp,pow_add,Nat.add_sub_cancel',Real.exp_nat_mul,Real.exp_addhave 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
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.
uses
Finset.sum_congr,Finset.mul_sum,Real.exp_nat_mul,mul_pow,Real.cosh_eq,Real.exp_add,mul_add,mul_one,mul_assocrw [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
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.
uses
ProbabilityTheory.mgf,ProbabilityTheory.integral_binomial,smul_eq_mul,fair_binomial_exp_tail_bound_sum_idlemma 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
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.
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_leopen 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 _ _
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.
uses
integrable_binomial,measure_ge_le_exp_mul_mgf,fair_binomial_exp_tail_bound_mgf_eqhave 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
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.
uses
integrable_binomial,measure_le_le_exp_mul_mgf,fair_binomial_exp_tail_bound_mgf_eq,Real.cosh_neghave 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
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.
uses
pow_le_pow_left₀,Real.cosh_le_exp_half_sq,Real.exp_nat_mul,Real.exp_add,Real.exp_le_exp.mprhave 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
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.
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.
- The proof establishes a bound of 2 * exp(-α^2 * n / 6) rather than the sharper 2 * exp(-α^2 * n / 2); the exponent is relaxed from -α^2 * n / 2 to -α^2 * n / 6 on line 107.
- The random variable X on the abstract probability space (Ω, μ) is immediately transferred on line 59 to the canonical binomial measure on ℕ via its law.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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