Lemma 2.14 — distinguishing Bernoulli distributions with samples
ProvedGaussTesting.lemma_2_14gaussian-statesp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquantum-property-testingstatistics
Let and , and consider two Bernoulli distributions with means and . Let be the threshold
Take the mean of independent samples and return if and if . There is an absolute constant such that whenever
this rule succeeds with probability at least under each mean:
where is .
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.