Lemma 6.4 — three facts about good shifts
ProvedListReplicableBias.LowerBound.Supplement.lemma_6_4list-replicabilityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitysample-complexity
Let , and with .
- If is -good for , then for all .
- If is -good for , then is -good for .
- If is -good for , then .
These facts make the rounding of an accurate empirical mean coincide with the rounding of the true bias, which is the source of replicability in Algorithm 1 (Lemma 6.11).
Differences from the source: none.
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.4, PDF p. 8, all three clauses. -/
theorem lemma_6_4 (ε u α p phat : ℝ) (hu : u ∈ Set.Ico (0 : ℝ) ε) (hα : 0 < α)
(hp : p ∈ Set.Icc (0 : ℝ) 1) (hphat : phat ∈ Set.Icc (0 : ℝ) 1)
(hclose : |phat - p| ≤ α) :
(IsGoodShift ε α p u →
∀ x ∈ Set.Ico (p - α) (p + α), ∀ y ∈ Set.Ico (p - α) (p + α),
roundShift ε u x = roundShift ε u y) ∧
(IsGoodShift ε (3 * α) p u → IsGoodShift ε (2 * α) phat u) ∧
(IsGoodShift ε (2 * α) phat u → roundShift ε u p = roundShift ε u phat) := 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.4, PDF p. 8