{"ID":5443898,"CreatedAt":"2026-07-01T02:07:11.383974684Z","UpdatedAt":"2026-07-03T17:47:04.346850254Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.32015","arxiv_id":"2606.32015","title":"The online monotone array completion problem","abstract":"Consider the following online filling game. An array of length $n$ is initially empty. At each time step one observes an independent sample from $\\mathrm{Unif}[0,1]$ and must either discard it or place it irrevocably into an empty position of the array, while preserving the constraint that the occupied entries are non-decreasing from left to right. Among all possible strategies, what is the optimal expected time required to fill the array? Let $v_n$ denote this optimal expected completion time. Our main result determines $v_n$ up to lower-order terms: \\[ v_n=\\left(\\frac12+o(1)\\right)n\\log n. \\] More precisely, no strategy, even if randomized and adaptive, can have expected completion time below $\\left(\\frac12-o(1)\\right)n\\log n$, while we provide an explicit deterministic strategy whose expected completion time is at most $\\left(\\frac12+o(1)\\right)n\\log n$. For comparison, the natural coupon-collector strategy, which partitions $[0,1]$ into $n$ equal intervals and reserves one array position for each interval, has expected completion time $(1+o(1))n\\log n$. We also consider a with-replacement version of the game, in which previously placed entries may be overwritten. For this variant, we give a deterministic strategy with expected completion time $O(n\\sqrt{\\log n})$, thereby establishing a separation between the two models.","short_abstract":"Consider the following online filling game. An array of length $n$ is initially empty. At each time step one observes an independent sample from $\\mathrm{Unif}[0,1]$ and must either discard it or place it irrevocably into an empty position of the array, while preserving the constraint that the occupied entries are non-...","url_abs":"https://arxiv.org/abs/2606.32015","url_pdf":"https://arxiv.org/pdf/2606.32015v1","authors":"[\"Vishesh Jain\",\"Dylan King\",\"Clayton Mizgerd\"]","published":"2026-06-30T17:47:07Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.PR\"]","methods":"[]","has_code":false}