Lemma 4 — every pigeonhole design with interval pigeonholes on [0,1] has worst-case expected discrepancy Ω(T^{1/4})
ProvedPigeonholeDesign.Lower.lemma_4Consider sequential experiments with one continuous covariate (, ): subjects (with even) arrive with covariates fixed in advance, and the cost of the final split into a control group and a treated group is the discrepancy , the minimum weight of a perfect matching between and under .
Let the pigeonhole design use any partition of into intervals , with and . There are an absolute constant and a threshold such that for every even and every such partition, some arrival sequence gives
where the expectation is over the fair coins of the design. In words: every pigeonhole design suffers a worst-case expected discrepancy of order .
Together with Lemma 3 and Corollary 1 of the paper (an upper bound for uniform pigeonholes), this shows that the uniform pigeonhole design is optimal among pigeonhole designs up to a logarithmic factor.
Formalization Note The paper states the lemma for "any pigeonhole design", and Definition 3 allows any partition of the covariate space; the proof treats partitions of into intervals, and the statement is formalized for those. The constants and are absolute, chosen before , and the breakpoints, and the hard instance is chosen after the partition. The expectation is the average over all coin vectors, not the discrepancy of a single run. is the real power.
import Mathlib import Definitions.Def_PigeonholeDesign_Lower_Setting
namespace PigeonholeDesign.Lower
theorem lemma_4 :
∃ c : ℝ, 0 < c ∧ ∃ T₀ : ℕ, ∀ T : ℕ, T₀ ≤ T → Even T →
∀ (K : ℕ) (_hK : 1 ≤ K) (b : Breakpoints K), ∃ x : Fin T → ℝ, (∀ t, x t ∈ Set.Icc (0 : ℝ) 1) ∧
c * (T : ℝ) ^ ((1 : ℝ) / 4) ≤ PigeonholeDesign.Upper.phdExp (intervalHole b) x := by sorry
end PigeonholeDesign.Lower
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.