arXiv preprint ·
Online Discrepancy of Sparse Random Vectors over Long Horizons
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $\ell_\infty$-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\le s\le n/2$ and $T=Θ(n)$, Altschuler and Tikhomirov showed that both are of order $\sqrt{s}+\log\log 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\ge2$ and $c>0$, every online algorithm, even a randomized one that knows the horizon, incurs with high probability prefix discrepancy $Ω(\log\log n+(\log T/\log n)^{α_s})$ for $n\le T\le e^{cn}$, where $α_s=(2^{s-1}-1)/(2^s-1)$. For $s=2$, quadratic Greedy matches this bound; for fixed $s\ge3$, we give an online algorithm with prefix discrepancy $O(\log\log 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(\sqrt{s}+\log\log n)$ at each prescribed time, with failure probability $n^{-k}$ for every fixed $k$, for $2\le s\le n/2$ (binary model) and $2\le s\le 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\ge 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Uniformity Testing for the Monomer-Dimer Model
Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework
Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
Almost tight distributed approximation for domination in sparse graph classes
Four-Coloring Planar Graphs in Linear Time
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.