Lemma 6.5 — a uniform shift fails to be α-good with probability exactly 2α/ε
OpenListReplicableBias.LowerBound.Supplement.lemma_6_5list-replicabilityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitysample-complexity
Let and let .
- For every ,
- The same equality holds when is a random variable with values in , independent of .
This exact failure probability bounds the bad-shift event of Lemma 6.10 and the probability that a coin stays active in Lemma 6.12.
Differences from the source:
- encoding: a random p ∈ [0, 1] independent of U → an arbitrary probability measure ν on ℝ with ν([0, 1]ᶜ) = 0, and the product law ν ⊗ Unif([0, ε)); reason: independence means the joint law is the product of the marginals
- encoding: Unif([0, ε)) and probabilities → Lebesgue measure conditioned on [0, ε); probabilities as ℝ≥0∞ masses equal to ENNReal.ofReal (2α/ε); reason: the same law; 2α/ε ∈ (0, 1] so no truncation occurs
Preamble
import Mathlib import Definitions.Def_ListReplicableBias_LowerBound_Geometry import Definitions.Def_ListReplicableBias_LowerBound_Supplement_Rounding noncomputable section open MeasureTheory ProbabilityTheory open scoped ENNReal
Formal statement
namespace ListReplicableBias.LowerBound.Supplement
open ListReplicableBias.LowerBound
/-- Lemma 6.5, PDF p. 8, both clauses, as equalities. Clause 2: p is a random
variable with values in [0, 1] (law ν) independent of U (product law). -/
theorem lemma_6_5 (ε α : ℝ) (hα : α ∈ Set.Ioc (0 : ℝ) (ε / 2)) :
(∀ p ∈ Set.Icc (0 : ℝ) 1,
uniformShift ε {u | ¬ IsGoodShift ε α p u} = ENNReal.ofReal (2 * α / ε)) ∧
(∀ ν : Measure ℝ, IsProbabilityMeasure ν → ν (Set.Icc (0 : ℝ) 1)ᶜ = 0 →
(ν.prod (uniformShift ε)) {z : ℝ × ℝ | ¬ IsGoodShift ε α z.1 z.2} =
ENNReal.ofReal (2 * α / ε)) := 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 6.5, PDF pp. 8–9