Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5, pp. 50–51 — multiplicative Chernoff bounds for the mean of n i.i.d. geometric variables

Proved
MNLBandit.UCB.theorem_5

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

chernoff-boundconcentration-inequalitygeometric-distributionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let X1,…,XnX_1,\dots,X_nX1​,…,Xn​ (n≥1n\ge1n≥1) be i.i.d. geometric random variables with parameter p∈(0,1]p\in(0,1]p∈(0,1], i.e. Pr⁡(Xi=m)=(1−p)mp\Pr(X_i=m)=(1-p)^mpPr(Xi​=m)=(1−p)mp for m=0,1,2,…m=0,1,2,\dotsm=0,1,2,…, and let μ=EXi=1−pp\mu=\mathbb E X_i=\frac{1-p}{p}μ=EXi​=p1−p​. For every δ>0\delta>0δ>0:

  1. (upper tail)
Pr⁡(1n∑i=1nXi>(1+δ)μ)≤{exp⁡(−nμδ22(1+δ)(1+μ)2)if μ≤1,exp⁡(−nδ2μ26(1+μ)2(3−2δμ1+μ))if μ≥1 and δ∈(0,1);\Pr\Big(\frac1n\sum_{i=1}^nX_i>(1+\delta)\mu\Big)\le\begin{cases}\exp\Big(-\dfrac{n\mu\delta^2}{2(1+\delta)(1+\mu)^2}\Big)&\text{if }\mu\le1,\\[3mm]\exp\Big(-\dfrac{n\delta^2\mu^2}{6(1+\mu)^2}\Big(3-\dfrac{2\delta\mu}{1+\mu}\Big)\Big)&\text{if }\mu\ge1\text{ and }\delta\in(0,1);\end{cases}Pr(n1​i=1∑n​Xi​>(1+δ)μ)≤⎩⎨⎧​exp(−2(1+δ)(1+μ)2nμδ2​)exp(−6(1+μ)2nδ2μ2​(3−1+μ2δμ​))​if μ≤1,if μ≥1 and δ∈(0,1);​
  1. (lower tail)
Pr⁡(1n∑i=1nXi<(1−δ)μ)≤{exp⁡(−nδ2μ6(1+μ)2(3−2δμ1+μ))if μ≤1,exp⁡(−nδ2μ22(1+μ)2)if μ≥1.\Pr\Big(\frac1n\sum_{i=1}^nX_i<(1-\delta)\mu\Big)\le\begin{cases}\exp\Big(-\dfrac{n\delta^2\mu}{6(1+\mu)^2}\Big(3-\dfrac{2\delta\mu}{1+\mu}\Big)\Big)&\text{if }\mu\le1,\\[3mm]\exp\Big(-\dfrac{n\delta^2\mu^2}{2(1+\mu)^2}\Big)&\text{if }\mu\ge1.\end{cases}Pr(n1​i=1∑n​Xi​<(1−δ)μ)≤⎩⎨⎧​exp(−6(1+μ)2nδ2μ​(3−1+μ2δμ​))exp(−2(1+μ)2nδ2μ2​)​if μ≤1,if μ≥1.​

The two cases overlap at μ=1\mu=1μ=1, where both bounds hold. These are the paper's extension of the multiplicative Chernoff–Hoeffding bounds to unbounded (geometric) variables; they drive the concentration of the epoch averages in Lemma A.2.

Formalization Note. The sample is the product measure of nnn copies of Mathlib's geometricMeasure p, whose mass at mmm is (1−p)mp(1-p)^mp(1−p)mp, exactly the paper's convention. The paper leaves the range of δ\deltaδ implicit in three of the four cases; δ>0\delta>0δ>0 is required (for δ∈(−1,0)\delta\in(-1,0)δ∈(−1,0) the first bound fails). For δ≥1\delta\ge1δ≥1 the lower-tail event is empty.

Preamble
import Mathlib
Formal statement
namespace MNLBandit.UCB

open MeasureTheory ProbabilityTheory

theorem theorem_5 (n : ℕ) (hn : 1 ≤ n) (p : unitInterval) (hp : p ≠ 0) (δ : ℝ) (hδ : 0 < δ) :
    let μ : ℝ := (1 - (p : ℝ)) / (p : ℝ)
    let P : Measure (Fin n → ℕ) := Measure.pi (fun _ : Fin n => geometricMeasure p)
    let Xbar : (Fin n → ℕ) → ℝ := fun x => (∑ k, (x k : ℝ)) / (n : ℝ)
    (μ ≤ 1 → P {x | Xbar x > (1 + δ) * μ} ≤
        ENNReal.ofReal (Real.exp (-((n : ℝ) * μ * δ ^ 2) / (2 * (1 + δ) * (1 + μ) ^ 2)))) ∧
    (1 ≤ μ → δ < 1 → P {x | Xbar x > (1 + δ) * μ} ≤
        ENNReal.ofReal (Real.exp (-((n : ℝ) * δ ^ 2 * μ ^ 2 / (6 * (1 + μ) ^ 2))
          * (3 - 2 * δ * μ / (1 + μ))))) ∧
    (μ ≤ 1 → P {x | Xbar x < (1 - δ) * μ} ≤
        ENNReal.ofReal (Real.exp (-((n : ℝ) * δ ^ 2 * μ / (6 * (1 + μ) ^ 2))
          * (3 - 2 * δ * μ / (1 + μ))))) ∧
    (1 ≤ μ → P {x | Xbar x < (1 - δ) * μ} ≤
        ENNReal.ofReal (Real.exp (-((n : ℝ) * δ ^ 2 * μ ^ 2) / (2 * (1 + μ) ^ 2)))) := by sorry

end MNLBandit.UCB
Source
Agrawal, Avadhanula, Goyal, Zeevi, MNL-Bandit: A Dynamic Learning Approach to Assortment Selection, arXiv:1706.03880v2, pp. 50–51, Theorem 5
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me