{"id":"arxiv/2609.14975","url":"https://arxiv.org/abs/2609.14975","tags":["math.PR","cs.DS","math.CO"],"score":0,"title":"The threshold for online balancing of i.i.d. binary vectors","domain":"math.PR","source":"arxiv","authors":["Dylan J. Altschuler","Konstantin Tikhomirov"],"reviews":0,"subject":"math.PR","summary":"Consider the task of online vector balancing for stochastic arrivals $X_1,\\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$--sparse binary vectors in $\\{0,1\\}^n$. This is a random analogue of the online Beck--Fiala problem. We show that uniformly for $2\\le d\\le n/2$ and $T = Θ(n)$, the optimal online prefix discrepancy $\\max\\limits_{t\\leq T}\\left\\|\\sum_{i=1}^tσ_i X_i\\right\\|_\\infty$ is of order \\[ Θ\\big(\\max\\{\\sqrt d,\\log\\log n\\}\\big). \\] The upper bound is achieved by an efficient online algorithm. Thus, for $d\\le(\\log\\log n)^2$, the optimal discrepancy is $Θ(\\log\\log n)$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}