A threshold for online balancing of sparse i.i.d. vectors

Consider the task of $\mathit{\text{online}}$ vector balancing for stochastic arrivals $(X_i{)}_{i\in [T]}$, where the time horizon satisfies $T=\mathrm{\Theta }(n)$, and the $X_i$ are i.i.d uniform $d$–sparse $n$–dimensional binary vectors, with $2\le d\le (\log \log n{)}^2\mathrm{/}\log \log \log n$. We show that for this range of parameters, every online algorithm incurs discrepancy at least $\mathrm{\Omega }(\log \log n)$, and there is an efficient algorithm which achieves a matching discrepancy bound of $O(\log \log n)$ w.h.p. This establishes an asymptotic gap, both existential and algorithmic, between the online and offline versions of the average–case Beck–Fiala problem. Strikingly, the optimal online discrepancy in the considered setting is order $\log \log n$, independent of $d$ and the norms of the vectors $(X_i{)}_i$. Our assumptions on $d$ are nearly optimal, as this independence ceases when $d=\omega ((\log \log n{)}^2)$.