A threshold for online balancing of sparse i.i.d. vectors
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914104282710016 |
|---|---|
| author | Altschuler, Dylan J. Tikhomirov, Konstantin |
| author_facet | Altschuler, Dylan J. Tikhomirov, Konstantin |
| contents | Consider the task of \textit{online} vector balancing for stochastic arrivals $(X_i)_{i \in [T]}$, where the time horizon satisfies $T = Θ(n)$, and the $X_i$ are i.i.d uniform $d$--sparse $n$--dimensional binary vectors, with $2\leq d \le (\log\log n)^2/\log\log\log n$. We show that for this range of parameters, every online algorithm incurs discrepancy at least $Ω(\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=ω((\log\log n)^2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02432 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A threshold for online balancing of sparse i.i.d. vectors Altschuler, Dylan J. Tikhomirov, Konstantin Probability Discrete Mathematics Combinatorics Consider the task of \textit{online} vector balancing for stochastic arrivals $(X_i)_{i \in [T]}$, where the time horizon satisfies $T = Θ(n)$, and the $X_i$ are i.i.d uniform $d$--sparse $n$--dimensional binary vectors, with $2\leq d \le (\log\log n)^2/\log\log\log n$. We show that for this range of parameters, every online algorithm incurs discrepancy at least $Ω(\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=ω((\log\log n)^2)$. |
| title | A threshold for online balancing of sparse i.i.d. vectors |
| topic | Probability Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2509.02432 |