Online Discrepancy of Sparse Random Vectors over Long Horizons

@misc{wengiel2026online,
  title = {{Online Discrepancy of Sparse Random Vectors over Long Horizons}},
  author = {Nicola Wengiel},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.34410},
  eprint = {2610.34410},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.34410},
}

TY  - UNPB
TI  - Online Discrepancy of Sparse Random Vectors over Long Horizons
AU  - Nicola Wengiel
PY  - 2026
DA  - 2026/10/25
PB  - arXiv
DO  - 10.48550/arxiv.2610.34410
UR  - https://arxiv.org/abs/2610.34410
AB  - We study online vector balancing for independent sparse random vectors: each arrival is supported on a uniformly random set of s of the n coordinates, with nonzero entries equal to one (binary model) or independent random signs (signed model), and an online algorithm must sign each vector upon arrival. The prefix discrepancy is the largest ℓ_∞-norm of the signed sums up to the horizon T, the terminal discrepancy that of the sum at time T. For binary inputs with 2≤ s≤ n/2 and T=Θ(n), Altschuler and Tikhomirov showed that both are of order √s+loglog n; they asked how the prefix discrepancy depends on the horizon and whether a matching terminal bound holds at every prescribed time. Over long horizons, the two differ. For every fixed s≥2 and c>0, every online algorithm, even a randomized one that knows the horizon, incurs with high probability prefix discrepancy Ω(loglog n+(log T/log n)^α_s) for n≤ T≤ e^cn, where α_s=(2^s−1−1)/(2^s−1). For s=2, quadratic Greedy matches this bound; for fixed s≥3, we give an online algorithm with prefix discrepancy O(loglog n+(log T/log n)^1/2). In contrast, a deterministic algorithm that knows neither the horizon nor the failure probability keeps the terminal discrepancy O_k(√s+loglog n) at each prescribed time, with failure probability n^−k for every fixed k, for 2≤ s≤ n/2 (binary model) and 2≤ s≤ n (signed model); for s=2, quadratic Greedy itself does so. This answers their terminal question, and the same order is optimal for prefixes at all polynomial horizons T≥ n. The lower bound uses a finite safety game realized within the input law; the upper bounds use moments of elementary symmetric polynomials and, at terminal times, a cosh potential or a translated gauge with a Foster inequality at every state.
ER  -