Definitions 6.1, 6.2, 6.6 — good shifts, shifted rounding, canonical list, uniform shift
DefinitionListReplicableBias_LowerBound_Supplement_Roundinglist-replicabilityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitysample-complexity
Fix a grid width .
- A shift is -good for if the half-open interval , shifted by , lies in one grid cell: there is an integer with
- The -rounding of is ; for a vector it is applied coordinatewise.
- The canonical list of is .
- The random shift has law .
These objects drive the upper-bound algorithms of §6: a random shift makes rounding of a noisy estimate agree with rounding of the true bias, and the canonical list is the list of possible outputs.
Formalization Note Good shifts are defined for every real (the algorithm applies the notion to empirical means), and the range is a hypothesis of each result rather than part of the predicate. The finiteness and size of are Lemma 6.7, not part of the definition. The uniform law is Lebesgue measure conditioned on .
Definition code
import Mathlib
noncomputable section
open MeasureTheory ProbabilityTheory
namespace ListReplicableBias.LowerBound.Supplement
/-- Definition 6.1, PDF p. 8: the shift u is α-good for p when the half-open
interval [p − α, p + α), shifted by u, lies inside one half-open grid cell
[kε, (k+1)ε) for some integer k. Stated for every real p (Algorithm 1 applies it
to empirical means); the range u ∈ [0, ε) is a hypothesis of each result. -/
def IsGoodShift (ε α p u : ℝ) : Prop :=
∃ k : ℤ, Set.Ico ((p + u) - α) ((p + u) + α) ⊆
Set.Ico ((k : ℝ) * ε) (((k : ℝ) + 1) * ε)
/-- Definition 6.2, PDF p. 8: the u-rounding R_u(x) = ⌊(x + u)/ε⌋ · ε. -/
def roundShift (ε u x : ℝ) : ℝ := (⌊(x + u) / ε⌋ : ℝ) * ε
/-- Definition 6.2, PDF p. 8: coordinatewise u-rounding of a vector. -/
def roundVec {d : ℕ} (ε u : ℝ) (x : Fin d → ℝ) : Fin d → ℝ :=
fun i => roundShift ε u (x i)
/-- Definition 6.6, PDF p. 9: the canonical list L_p = {R_u(p) | u ∈ [0, ε)}.
Its finiteness and size bound are Lemma 6.7, not part of the definition. -/
def canonicalList {d : ℕ} (ε : ℝ) (p : Fin d → ℝ) : Set (Fin d → ℝ) :=
{y | ∃ u ∈ Set.Ico (0 : ℝ) ε, y = roundVec ε u p}
/-- The uniform law Unif([0, ε)) of the random shift (Lemma 6.5, Algorithm 1
line 1): Lebesgue measure conditioned on the half-open interval [0, ε). -/
def uniformShift (ε : ℝ) : Measure ℝ := volume[|Set.Ico (0 : ℝ) ε]
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, Definitions 6.1, 6.2, PDF p. 8; Definition 6.6, PDF p. 9; Lemma 6.5, PDF p. 8