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

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