pith. sign in

arxiv: 2606.32015 · v1 · pith:VX4JMQOPnew · submitted 2026-06-30 · 💻 cs.DS · math.PR

The online monotone array completion problem

Vishesh Jain , Dylan King , Clayton Mizgerd This is my paper

Pith reviewed 2026-07-01 02:10 UTC · model grok-4.3

classification 💻 cs.DS math.PR
keywords online algorithmsmonotone arraycompletion timecoupon collectoruniform samplesdeterministic strategywith-replacement model
0
0 comments X

The pith

The optimal expected time to complete an online monotone array is (1/2 + o(1)) n log n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the minimal expected number of uniform [0,1] samples needed to fill an n-position array while keeping occupied entries non-decreasing from left to right. It proves a matching lower bound showing no strategy (even randomized and adaptive) can finish faster than (1/2 - o(1)) n log n in expectation, together with an explicit deterministic strategy that meets the (1/2 + o(1)) n log n upper bound. This pins down the constant factor and shows the natural coupon-collector partitioning strategy, which takes (1 + o(1)) n log n, is asymptotically suboptimal by roughly a factor of two. A separate with-replacement variant, allowing overwrites, admits an O(n sqrt(log n)) deterministic strategy.

Core claim

Let v_n be the optimal expected completion time for the online monotone array game. Then v_n equals (1/2 + o(1)) n log n. No strategy can achieve expected time below (1/2 - o(1)) n log n, while an explicit deterministic strategy achieves at most (1/2 + o(1)) n log n. The with-replacement variant admits a deterministic strategy with expected completion time O(n sqrt(log n)).

What carries the argument

The irrevocable placement rule that preserves non-decreasing order on i.i.d. Unif[0,1] samples.

If this is right

  • The standard coupon-collector partitioning strategy is asymptotically twice as slow as optimal.
  • Deterministic strategies suffice to achieve the optimal asymptotic rate.
  • Allowing overwrites yields a qualitatively faster O(n sqrt(log n)) regime.
  • The lower bound continues to hold when strategies may adapt and randomize.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The factor-of-two gap may reflect a general cost of irrevocable decisions under order constraints.
  • The with-replacement separation suggests that update flexibility can reduce the logarithmic overhead in related online placement problems.
  • Exact leading constants or second-order terms in v_n could be extracted by refining the strategy analysis.

Load-bearing premise

Incoming values are independent uniform random numbers on the unit interval and the only rule is that occupied positions must stay non-decreasing.

What would settle it

A concrete strategy (randomized or deterministic) whose expected completion time falls below (1/2 - epsilon) n log n for some fixed epsilon > 0 and infinitely many n would falsify the lower bound.

Figures

Figures reproduced from arXiv: 2606.32015 by Clayton Mizgerd, Dylan King, Vishesh Jain.

Figure 1
Figure 1. Figure 1: A partial array state for n = 10 in which the three filled values 0.10 < 0.35 < 0.80 occupy positions 1, 4, 9. There are three blocks B1, B2, B3, with c = c(B), I = I(B), and L = L(B) = |I(B)| displayed. When a new sample is accepted for placement in the array, there are three possibilities: • an interior move places the sample in a position which splits the chosen block into two nonempty child blocks; • a… view at source ↗
Figure 2
Figure 2. Figure 2: The local rule inside a block Bj . When k locations remain unfilled, the block has a feasible value interval I feas j = [L, R] of length ℓ = R − L. The strategy accepts a sample only if it lies in one of the two gray edge intervals, each of length ℓ/(k + 1). A sample from the left edge interval fills the leftmost empty location and changes the feasible interval to [x, R]; a sample from the right edge inter… view at source ↗
Figure 3
Figure 3. Figure 3: The local with-replacement rule inside a block. If the incoming value x is smaller than some occupied entry, the strategy replaces the leftmost occupied entry larger than x. In the displayed case a1 < x < a2, so a2 is replaced by x. If no occupied entry is larger than x, then x is appended in the next empty slot, if one exists. Lemma 4.1. The strategy S ′ r is well defined and preserves global monotonicity… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper studies the online monotone array completion problem on an initially empty array of length n. At each step an i.i.d. Unif[0,1] sample is observed and must either be discarded or placed irrevocably into an empty cell while preserving the non-decreasing order of occupied entries. The main result shows that the optimal expected completion time v_n satisfies v_n = (1/2 + o(1)) n log n: a matching lower bound of (1/2 - o(1)) n log n holds for every (possibly randomized, adaptive) strategy, while an explicit deterministic strategy achieves an upper bound of (1/2 + o(1)) n log n. The paper also treats the with-replacement variant and gives a deterministic strategy whose expected completion time is O(n sqrt(log n)).

Significance. If the stated bounds hold, the result tightly characterizes the complexity of monotone online array filling and improves by a factor of two on the natural coupon-collector benchmark of (1+o(1)) n log n. The explicit deterministic construction for the upper bound and the fact that the lower bound applies even to adaptive randomized strategies are concrete strengths. The separation between the no-replacement and with-replacement models is also of interest.

major comments (2)
  1. [§2] §2 (lower-bound argument): the claim that the (1/2 - o(1)) n log n lower bound holds for every adaptive randomized strategy rests on a direct analysis of the placement process under the monotonicity constraint; the derivation should explicitly verify that no additional non-adaptivity assumption is used when bounding the expected number of useful samples.
  2. [§3] §3 (upper-bound strategy): the deterministic strategy is described explicitly, yet the analysis establishing the (1/2 + o(1)) n log n upper bound must confirm that the o(1) term is uniform and does not hide n-dependent factors arising from the threshold or interval-partition choices.
minor comments (2)
  1. [Abstract] Abstract: the sentence 'no strategy, even if randomized and adaptive' could be cross-referenced to the precise statement of the lower-bound theorem.
  2. [Introduction] Notation: the definition of v_n should appear in the main body before its first use in the abstract and introduction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and positive recommendation. We address each major comment below.

read point-by-point responses

  1. Referee: [§2] §2 (lower-bound argument): the claim that the (1/2 - o(1)) n log n lower bound holds for every adaptive randomized strategy rests on a direct analysis of the placement process under the monotonicity constraint; the derivation should explicitly verify that no additional non-adaptivity assumption is used when bounding the expected number of useful samples.

    Authors: The lower bound in §2 is derived by directly bounding the expected number of useful samples under the monotonicity constraint, considering the probability that a given sample can be inserted into one of the available positions while preserving order. This calculation depends only on the current occupied values and the uniform distribution; it makes no reference to how the strategy selects positions and therefore applies verbatim to adaptive (and randomized) strategies. We will add an explicit clarifying sentence in the revised §2 to state that the argument invokes no non-adaptivity assumption. revision: yes

  2. Referee: [§3] §3 (upper-bound strategy): the deterministic strategy is described explicitly, yet the analysis establishing the (1/2 + o(1)) n log n upper bound must confirm that the o(1) term is uniform and does not hide n-dependent factors arising from the threshold or interval-partition choices.

    Authors: The upper-bound analysis in §3 selects thresholds and interval partitions whose lengths are functions of n that yield additive error terms vanishing as n → ∞. The o(1) factor is obtained by summing a series of probabilities whose remainders are bounded by quantities that tend to zero independently of any fixed n-dependent constants in the construction. We will insert a short paragraph or footnote in the revised §3 that explicitly verifies uniformity of the o(1) term with respect to the threshold and partition parameters. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper derives matching (1/2 ± o(1))n log n bounds on the optimal expected completion time v_n directly from analysis of the online monotone array completion game under i.i.d. Unif[0,1] samples. The lower bound applies to all randomized adaptive strategies via the monotonicity constraint alone, while the upper bound is realized by an explicit deterministic strategy; neither reduces to a fitted parameter, self-citation, or input renamed as output. The with-replacement variant is handled separately with an O(n sqrt(log n)) strategy establishing separation. No load-bearing step invokes prior self-work, ansatz smuggling, or uniqueness theorems from the authors. The central claims rest on independent game-process analysis rather than any of the enumerated circular patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard i.i.d. uniform sampling and the monotone constraint; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Samples are i.i.d. from Unif[0,1]
    Explicitly stated in the problem setup.

pith-pipeline@v0.9.1-grok · 5791 in / 1062 out tokens · 32890 ms · 2026-07-01T02:10:50.909923+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references

  1. [1]

    1806–1833

    AndersAamand, MikkelAbrahamsen, LorenzoBeretta, andLindaKleist,Online sorting and translational packing of convex polygons, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2023, pp. 1806–1833

    2023

  2. [2]

    Mikkel Abrahamsen, Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen, and László Kozma,Online sorting and online TSP: Randomized, stochastic, and high-dimensional, 32nd Annual European Symposium on Algorithms (ESA 2024), Leibniz International Proceedings in Informatics (LIPIcs), vol. 308, Schloss Dagstuhl – Leibniz- Zentrum für Informatik, 2024, pp. 5:1–5:15

    2024

  3. [3]

    4, 413–432

    David Aldous and Persi Diaconis,Longest increasing subsequences: from patience sorting to the Baik–Deift– Johansson theorem, Bulletin of the American Mathematical Society36(1999), no. 4, 413–432

    1999

  4. [4]

    2, 235–252

    Alessandro Arlotto, Elchanan Mossel, and J Michael Steele,Quickest online selection of an increasing subsequence of specified size, Random Structures & Algorithms49(2016), no. 2, 235–252

    2016

  5. [5]

    9, 3596–3622

    Alessandro Arlotto, Vinh V Nguyen, and J Michael Steele,Optimal online selection of a monotone subsequence: a central limit theorem, Stochastic Processes and their Applications125(2015), no. 9, 3596–3622

    2015

  6. [6]

    F. Thomas Bruss and Freddy Delbaen,Optimal rules for the sequential selection of monotone subsequences of maximum expected length, Stochastic Processes and their Applications96(2001), no. 2, 313–342

    2001

  7. [7]

    2, 287–311

    ,A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length, Stochastic Processes and their Applications114(2004), no. 2, 287–311

    2004

  8. [8]

    4, 1074–1085

    Alexander V Gnedin,Sequential selection of an increasing subsequence from a sample of random size, Journal of applied probability36(1999), no. 4, 1074–1085

    1999

  9. [9]

    4969–4995

    Yang Hu,Nearly optimal bounds for stochastic online sorting, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics (SIAM), 2026, pp. 4969–4995

    2026

  10. [10]

    Samuels and J

    Stephen M. Samuels and J. Michael Steele,Optimal sequential selection of a monotone sequence from a random sample, The Annals of Probability9(1981), no. 6, 937–947. Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago, Chicago, IL 60607, USA Email address:visheshj@uic.edu Department of Mathematics, California Institu...

    1981