Square-root law for online discrepancy of sparse random vectors
Let be independent random vectors, each uniformly distributed among the vectors with exactly nonzero coordinates. An online algorithm chooses signs when arrives, possibly knowing , , and . Define the prefix discrepancy by . For every fixed and , is the optimal prefix discrepancy, with high probability uniformly over , of order ? Equivalently, does there exist an online algorithm achieving and does every online algorithm incur with high probability?
References
- Online Discrepancy of Sparse Random Vectors over Long Horizons — arXiv — Nicola Wengiel
Source: arXiv
Progress summary
A new unrefereed preprint claims to settle the end-point question and the two-sparse case, but the conjectured law remains open for sparsity three or more.
The problem asks whether online discrepancy of sparse random vectors has a sharp square-root dependence over exponentially long horizons, distinguishing prefix from terminal behavior.
October 2026 preprint
Nicola Wengiel’s preprint claims to resolve the terminal-time question, obtain matching prefix behavior for sparsity two, and prove only a nonmatching upper bound for fixed sparsity at least three. Thus it advances but does not settle the full conjecture.
Current status (as of October 2026): The terminal-time question and sparsity-two prefix behavior are claimed in an unrefereed preprint, while the full square-root law for fixed sparsity at least three remains open.
Sources
Solutions 0
No solutions have been posted yet.