Lemma 3.2 — Ω(d/ε²) samples for coin-bias estimation
OpenListReplicableBias.LowerBound.Supplement.lemma_3_2list-replicabilityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitysample-complexity
There is an absolute constant such that for every , every , and every randomized adaptive -toss sampling algorithm that solves the -CoinBiasEstimationProblem,
The constant does not depend on or . The paper cites this classical bound ([KCG16, Sca24]); the proof of Theorem 5.11 uses it for list sizes .
Differences from the source:
- encoding: arbitrary randomized adaptive algorithms with sample access to d coins, using N samples, output in ℝ^d ∪ {⊥} → the published SamplingAlgorithm d N (arbitrary probability seed space, prefix-dependent coin choices, fixed horizon N) with failure as none; reason: the base mission's model of §3.2 and Appendix B; private randomness is in the seed and an algorithm that stops early is padded with ignored tosses, so N is the worst-case toss count
- reading: N = Ω(d/ε²) with ε, δ fixed first → one constant chosen before every other parameter; reason: the hidden constant cannot depend on ε, which appears inside the bound; the uniform reading is the stronger one
Preamble
import Mathlib import Definitions.Def_ListReplicableBias_LowerBound_Supplement_Estimation noncomputable section open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace ListReplicableBias.LowerBound.Supplement
open ListReplicableBias.LowerBound
/-- Lemma 3.2, PDF p. 3. One absolute constant c, chosen before d, ε, δ, N and A. -/
theorem lemma_3_2 :
∃ c : ℝ, 0 < c ∧ ∀ d : ℕ, ∀ ε δ : ℝ, ε ∈ Set.Ioo (0 : ℝ) (1 / 8) →
δ ∈ Set.Ioo (0 : ℝ) (1 / 8) →
∀ (N : ℕ) (A : SamplingAlgorithm d N), IsBiasEstimator A ε δ →
c * (d : ℝ) / ε ^ 2 ≤ (N : ℝ) := by sorry
end ListReplicableBias.LowerBound.Supplement
Source
Chen, Bastan, Pavan, Vinodchandran, The Price of List Replicability: Tight Bounds for Bias Estimation, STOC 2027 submission #681 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/681.pdf, Lemma 3.2, PDF p. 3