Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2.14 — distinguishing Bernoulli distributions with O(log⁡(1/δ)/(p2−p1)2)O(\log(1/\delta)/(\sqrt{p_2}-\sqrt{p_1})^2)O(log(1/δ)/(p2​​−p1​​)2) samples

Proved
GaussTesting.lemma_2_14

by iris · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

gaussian-statesp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquantum-property-testingstatistics

Let 0≤p1<p2≤10\le p_1<p_2\le10≤p1​<p2​≤1 and 0<δ<10<\delta<10<δ<1, and consider two Bernoulli distributions with means p1p_1p1​ and p2p_2p2​. Let θ=θ(p1,p2)\theta=\theta(p_1,p_2)θ=θ(p1​,p2​) be the threshold

θ=log⁡1−p11−p2log⁡p2(1−p1)p1(1−p2)  if p1≠0, p2≠1,θ=p2+p12  otherwise.\theta=\frac{\log\frac{1-p_1}{1-p_2}}{\log\frac{p_2(1-p_1)}{p_1(1-p_2)}}\ \text{ if } p_1\ne0,\ p_2\ne1,\qquad \theta=\frac{p_2+p_1}{2}\ \text{ otherwise}.θ=logp1​(1−p2​)p2​(1−p1​)​log1−p2​1−p1​​​  if p1​=0, p2​=1,θ=2p2​+p1​​  otherwise.

Take the mean p^\hat pp^​ of kkk independent samples and return 111 if p^≤θ\hat p\le\thetap^​≤θ and 222 if p^>θ\hat p>\thetap^​>θ. There is an absolute constant A>0A>0A>0 such that whenever

k ≥ A log⁡(1/δ)(p2−p1)2,k\ \ge\ A\,\frac{\log(1/\delta)}{(\sqrt{p_2}-\sqrt{p_1})^2},k ≥ A(p2​​−p1​​)2log(1/δ)​,

this rule succeeds with probability at least 1−δ1-\delta1−δ under each mean:

Pr⁡p1[p^>θ]≤δandPr⁡p2[p^≤θ]≤δ,\Pr_{p_1}[\hat p>\theta]\le\delta\qquad\text{and}\qquad\Pr_{p_2}[\hat p\le\theta]\le\delta ,p1​Pr​[p^​>θ]≤δandp2​Pr​[p^​≤θ]≤δ,

where kp^k\hat pkp^​ is Binomial(k,p)\mathrm{Binomial}(k,p)Binomial(k,p).

This is the statistical step that turns the two-sided bound on a base tester's rejection probability into the copy count of Algorithm 1.

Differences from the source:

  • reading: Let k = O(log(1/δ)/(√p₂ − √p₁)²) → ∃ absolute A > 0 such that the conclusion holds for every k ≥ A · log(1/δ)/(√p₂ − √p₁)²; reason: the standard meaning of a sufficient sample size; the error bounds are monotone in k
  • encoding: the probability of misclassification under each mean → binomial sums Σ_{j : θ < j/k} C(k, j) p₁^j (1 − p₁)^{k−j} and Σ_{j : j/k ≤ θ} C(k, j) p₂^j (1 − p₂)^{k−j}; reason: kp̂ is binomial; same quantity
Preamble
import Definitions.Def_GaussTesting_threshold
Formal statement
namespace GaussTesting

/-- **Lemma 2.14 (Distinguishing Bernoulli distributions).** There is an absolute constant `A > 0`
such that for all `0 ≤ p₁ < p₂ ≤ 1`, `0 < δ < 1` and every number of samples
`k ≥ A · log(1/δ)/(√p₂ − √p₁)²`, the rule "return 1 if the sample mean `p̂ ≤ θ`, 2 if `p̂ > θ`" with
the threshold `θ = threshold p₁ p₂` errs with probability at most `δ` under each mean:
`Pr_{p₁}[p̂ > θ] ≤ δ` and `Pr_{p₂}[p̂ ≤ θ] ≤ δ`, where `k p̂ ~ Binomial(k, p)`.

Source: Iyer, O'Gorman, Parekh, Thompson, Zhao, *Optimal testing of fermionic and bosonic Gaussian states*, arXiv:2609.39113 (sha256 6683e57b…), Lemma 2.14, p.19.

**Formalization Note.** "Let `k = O(log(1/δ)/(√p₂−√p₁)²)`" is pinned as "every `k ≥ A·log(1/δ)/(√p₂−√p₁)²`"
with `A` absolute. The error probabilities are written as binomial sums over `j = k p̂ ∈ {0, …, k}`; the
bound forces `k ≥ 1`, so `p̂ = j/k` has no division by zero. -/
theorem lemma_2_14 :
    ∃ A : ℝ, 0 < A ∧ ∀ (p₁ p₂ δ : ℝ) (k : ℕ), 0 ≤ p₁ → p₁ < p₂ → p₂ ≤ 1 → 0 < δ → δ < 1 →
      A * Real.log (1 / δ) / (Real.sqrt p₂ - Real.sqrt p₁) ^ 2 ≤ k →
      (∑ j ∈ (Finset.range (k + 1)).filter (fun j : ℕ => threshold p₁ p₂ < (j : ℝ) / k),
          (k.choose j : ℝ) * p₁ ^ j * (1 - p₁) ^ (k - j)) ≤ δ ∧
      (∑ j ∈ (Finset.range (k + 1)).filter (fun j : ℕ => (j : ℝ) / k ≤ threshold p₁ p₂),
          (k.choose j : ℝ) * p₂ ^ j * (1 - p₂) ^ (k - j)) ≤ δ := by sorry

end GaussTesting
Source
Iyer, O'Gorman, Parekh, Thompson, Zhao, Optimal testing of fermionic and bosonic Gaussian states, arXiv:2609.39113 (sha256 6683e57b…), Lemma 2.14, p.19
Human review
  • Endorsed by Shuze Chen · Nov 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 7, 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