The threshold for online balancing of i.i.d. binary vectors
Abstract
Consider the task of online vector balancing for stochastic arrivals X1,…,XT, where the Xi are independent uniformly random d--sparse binary vectors in {0,1}n. This is a random analogue of the online Beck--Fiala problem. We show that uniformly for 2≤ d≤ n/2 and T = Θ(n), the optimal online prefix discrepancy maxt≤ T|∑i=1tσi Xi|∞ is of order Θ(max{√d,loglog n}). The upper bound is achieved by an efficient online algorithm. Thus, for d≤(loglog n)2, the optimal discrepancy is Θ(loglog n) and is independent of the sparsity up to constant factors, whereas above this scale it is Θ(√d), matching the order of the offline discrepancy. This identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model.
Related
- Online Discrepancy of Sparse Random Vectors over Long Horizons
- Online Bayesian Model Averaging with Joint Uncertainty Quantification for Models and Regression Coefficients in Binary Regression
- Modular resurgent structures for vectors
- Palindromic real-rooted polynomials and h-vectors of polytopes
- Unbalancing unit vectors
BibTeX
@misc{altschuler2026threshold,
title = {{The threshold for online balancing of i.i.d. binary vectors}},
author = {Dylan J. Altschuler and Konstantin Tikhomirov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14975},
eprint = {2609.14975},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14975},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The threshold for online balancing of i.i.d. binary vectors
AU - Dylan J. Altschuler
AU - Konstantin Tikhomirov
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.14975
UR - https://arxiv.org/abs/2609.14975
AB - Consider the task of online vector balancing for stochastic arrivals X_1,…,X_T, where the X_i are independent uniformly random d--sparse binary vectors in {0,1}^n. This is a random analogue of the online Beck--Fiala problem. We show that uniformly for 2≤ d≤ n/2 and T = Θ(n), the optimal online prefix discrepancy max_t≤ T|∑_i=1^tσ_i X_i|_∞ is of order Θ(max{√d,loglog n}). The upper bound is achieved by an efficient online algorithm. Thus, for d≤(loglog n)^2, the optimal discrepancy is Θ(loglog n) and is independent of the sparsity up to constant factors, whereas above this scale it is Θ(√d), matching the order of the offline discrepancy. This identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model.
ER -