The threshold for online balancing of i.i.d. binary vectors
TL;DR
This paper identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model, where the independent uniformly random vectors are independent of the sparsity up to constant factors.
Abstract
Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{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 $\max\limits_{t\leq T}\left\|\sum_{i=1}^t\sigma_i X_i\right\|_\infty$ is of order \[ \Theta\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.