Lemma EC.5 — ALG^C is invariant under permutations of the arrival sequence
ProvedPigeonholeDesign.Upper.lemma_EC_5completely-randomized-designdiscrepancyexperimental-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1symmetry
Let be two arrival sequences and a bijection with for every . Then the completely randomized design has the same expected discrepancy on both sequences:
The completely randomized design ignores arrival order, so its performance depends only on the multiset of covariates. This reduces the worst case of Lemma 2 to sorted instances.
Formalization Note The sequences are functions on Fin T and . No range restriction on the covariates is needed.
Preamble
import Mathlib import Definitions.Def_PigeonholeDesign_Upper_Setting
Formal statement
namespace PigeonholeDesign.Upper
theorem lemma_EC_5 {T : ℕ} (σ : Equiv.Perm (Fin T)) (x : Fin T → ℝ) :
crdExp (x ∘ σ) = crdExp x := by sorry
end PigeonholeDesign.Upper
Source
Zhao and Zhou, Pigeonhole Design: Balancing Sequential Experiments from an Online Matching Perspective, arXiv:2201.12936v6, p. ec4 (PDF p. 42), Lemma EC.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.