Lemma 6.3 — shifted rounding moves by strictly less than ε
ProvedListReplicableBias.LowerBound.Supplement.lemma_6_3list-replicabilityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitysample-complexity
Let . For every ,
and for every and every ,
This is the accuracy of rounding: every member of the canonical list is strictly -close to the bias vector (Lemma 6.7).
Differences from the source:
- encoding: vectors in ℝ^d with the ℓ∞ norm → functions Fin d → ℝ with their sup norm; reason: the same finite coordinates and the same distance
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.3, PDF p. 8: u-rounding moves a real, and a vector in sup norm, by
strictly less than ε. -/
theorem lemma_6_3 (ε u : ℝ) (hu : u ∈ Set.Ico (0 : ℝ) ε) :
(∀ x : ℝ, |roundShift ε u x - x| < ε) ∧
(∀ (d : ℕ) (x : Fin d → ℝ), ‖roundVec ε u x - x‖ < ε) := 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.3, PDF p. 8