The threshold for online balancing of i.i.d. binary vectors

Abstract

Consider the task of online vector balancing for stochastic arrivals $X_1,\dots ,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\le d\le n/2$ and $T=\Theta (n)$, the optimal online prefix discrepancy $\underset{t\le T}{\max }{\Vert {\sum }_{i=1}^t{\sigma }_i{X}_i\Vert }_{\infty }$ is of order \[ Θ\big(\max\{\sqrt d,\log\log n\}\big). \] The upper bound is achieved by an efficient online algorithm. Thus, for $d\le (\log \log n{)}^2$, the optimal discrepancy is $\Theta (\log \log n)$ and is independent of the sparsity up to constant factors, whereas above this scale it is $\Theta (\sqrt{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.

arXiv commentSupersedes and replaces arxiv.org/abs/2509.02432, which has the same lower bound, but only has an upper bound for the ultra-sparse regime