Pigeonhole Design: Balancing Sequential Experiments from an Online Matching Perspective 2: Every Pigeonhole Design on [0,1] Has Worst-Case Expected Discrepancy Ω(T^(1/4))Research Paper
Motivation
Online platforms run experiments on subjects that arrive one at a time: a user opens an app, a customer reaches a checkout page, a patient enters a trial. Each subject must be assigned to control or treatment at once, before the next one arrives, and the quality of the final estimate depends on how well the two groups resemble each other in their observed covariates. Classical sequential randomization such as Efron's biased coin (Efron 1971) balances the group sizes; Zhao and Zhou (arXiv:2201.12936, Management Science 2025) instead measure imbalance by an online matching cost and ask how small it can be made against an adversarial sequence of covariates.
Their pigeonhole design partitions the covariate space into cells and balances the two groups inside each cell. With one continuous covariate the paper shows (Lemma 3 and Corollary 1) that uniform cells achieve an expected cost of order , against for complete randomization (Lemma 2). This mission concerns the matching lower bound, Lemma 4: no choice of pigeonholes does better than .
Setting
A horizon of subjects, with even, arrives at times . Subject carries a covariate , and the whole sequence is fixed in advance by an oblivious adversary. An assignment puts each subject in the control group or the treated group .
The discrepancy of the split (display (1), p. 11) is the cost of a minimum-weight perfect matching between the two groups:
A pigeonhole design (Definition 3, p. 16) takes a partition of into pigeonholes. When subject arrives:
- if one group already holds subjects, joins the other group;
- otherwise, with and the control and treated subjects already in the pigeonhole of , subject joins control if , treatment if , and either group with probability in case of a tie.
The design's expected discrepancy on is the average over these fair coins.
An interval partition is given by breakpoints , ; its pigeonholes are , and the cell lengths are .
Formalization targets
Goal: Lemma 4 (p. 18)
There are an absolute constant and a threshold such that for every even and every interval partition of , some arrival sequence gives
The partition is arbitrary and the hard sequence is chosen after it; and do not depend on or on the partition.
Milestones (proof of Lemma 4, pp. ec15–ec16)
- Lemma EC.2 (p. ec3), the binomial mean absolute deviation: for ,
- Per-pigeonhole bound. On the alternating instance, which places consecutive pairs in cell (the pairs in the last cell), the expected discrepancy is at least .
- Cauchy–Schwarz display. With ,
- Jensen display. If then , with equality iff every .
- Few pigeonholes, for a fixed : some instance gives .
- Many pigeonholes, for a fixed : some instance gives .
Milestones 5 and 6 (with ) together give the goal.
Significance
Lemma 4 makes the upper bound of Lemma 3 meaningful as an optimality statement: among all pigeonhole designs on one continuous covariate, uniform cells are optimal up to the factor . It also locates the source of the rate in a tension between two kinds of randomness. Long cells let fair coins inside a cell create imbalance across the cell's length. Many cells leave one unmatched subject per cell, and these must be matched across cells. The rate cannot be improved by tuning the partition alone; doing better requires designs outside the pigeonhole class.
The paper's proof is a short sketch, and no part of it has been machine-checked. A formal proof would supply an explicit hard instance for every interval partition, including the rounding of the counts to even integers and the instance for the many-cell case, which the paper leaves unspecified. Lemma EC.2 is a classical result (Blyth 1980) that also has no formal proof in Mathlib.
Difficulty
The algebra of milestones 3 and 4 is elementary. The difficulty lies in the two cases.
In the few-cell case, the per-cell bound of milestone 2 must be computed from the design's actual run. That requires showing that on the alternating instance the first member of each pair always meets a tie in its cell, and that the global cap never alters an assignment. The matching cost must then be bounded below. On the line the optimal matching is determined by the order of the points, so a cell's internal imbalance cannot be cancelled by subjects of other cells, and this needs proof. The ideal counts are not even integers, and the rounding must not destroy the bound.
The many-cell case is the least specified step. The paper's sketch (an odd number of subjects per cell, then a coupling with complete randomization) does not say where the unmatched subjects lie. As printed, it does not handle a partition that mixes one long interval with many short ones; such a partition must be handled by a combination of the two constructions. Lemma EC.2 needs a sharp local estimate of the binomial distribution: the error term is , which is finer than what a plain central limit theorem gives.
Formalization scope
- Covariates and time. with every . Subjects and cells are indexed from , so the paper's subject is index and its cell is index .
- Discrepancy. Display (1) is an assignment problem, and it is encoded as the infimum over bijections between the two groups. If the groups differ in size this infimum is Lean's junk value . The pigeonhole design always ends with subjects in each group, so this value is never reached; it could only make a lower bound harder.
- Randomness. The design reads a coin vector , and coin is used only when subject meets a tie. The expected discrepancy is the average over all coin vectors, which is exactly the paper's law. Step 1 (the cap) is checked before the pigeonhole rule.
- Partitions. Lemma 4 says "any pigeonhole design", and Definition 3 allows any partition. The proof treats partitions of into intervals, and the goal is stated for those, encoded by breakpoints. Partitions into arbitrary measurable sets are not covered.
- Asymptotics. is read as: there exist and , chosen before and the partition, such that for every even and every partition there exists a hard sequence. is the real power. In the two cases, and are read as and for an arbitrary fixed , on which and may depend. In Lemma EC.2, is fixed before the constant.
- Printed slips corrected. The proof's is read as . Its "due to Lemma EC.4" is read as Lemma EC.2, because the count is binomial, not hypergeometric. In milestone 2 the per-cell constant is absolute and the gap factor is the exact width ; the counts are arbitrary even integers, since is not an integer in general.
- Ruled out. None of the following counts as a proof of the goal: the junk discrepancy of an unbalanced split; a bound on one run of the design, or on its best run, instead of the average over all coin vectors; constants that depend on , or the partition; a hard sequence chosen before the partition.
- Infrastructure. A complete development needs: the one-dimensional optimal matching (sorted matching, or the distance between counting functions); a lemma computing the design's run on structured instances; and the binomial mean absolute deviation. The first and third are reusable well beyond this mission, and contributions of them are welcome. An extension of the goal to arbitrary finite partitions of is also welcome, but it is not claimed here.
Selected references
- J. Zhao and Z. Zhou, Pigeonhole Design: Balancing Sequential Experiments from an Online Matching Perspective, arXiv:2201.12936v6, 2024; Management Science, 2025. https://arxiv.org/abs/2201.12936
- C. R. Blyth, Expected absolute error of the usual estimator of the binomial parameter, The American Statistician 34(3), 155–157, 1980. https://doi.org/10.1080/00031305.1980.10483022
- B. Efron, Forcing a sequential experiment to be balanced, Biometrika 58(3), 403–417, 1971. https://doi.org/10.1093/biomet/58.3.403