{"id":"c3a24cde-2bdb-4cc4-8b44-3459298c83b2","arxiv_id":"2606.32015","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Optimal expected time to complete the online monotone array filling game with i.i.d. uniform samples is (1/2 + o(1)) n log n, with a separation shown for the with-replacement variant.","lead":"The paper examines an online game filling an array with uniform random numbers while keeping entries non-decreasing, finding the optimal expected completion time is asymptotically (1/2 + o(1)) n log n. A matching lower bound holds for any strategy and an explicit deterministic strategy achieves the upper bound.","discovery_kind":"new_application","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader's weakest assumption matches the abstract's explicit statement that the lower bound covers randomized adaptive strategies. With no further technical detail available to expose a flaw in the potential-function or information-theoretic argument, the claim stands as internally consistent.","tokens_in":1776,"tokens_out":236,"duration_ms":22462,"concrete_test":"Implement the explicit deterministic strategy from the paper and simulate its expected completion time on n=10^5; check whether the ratio to n log n lies inside [0.49, 0.51] for multiple independent runs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim establishes matching (1/2 ± o(1)) n log n bounds on v_n for all randomized adaptive strategies under i.i.d. Unif[0,1] samples and the monotonicity constraint alone. The abstract states an explicit deterministic upper-bound strategy and a lower bound that applies even to adaptive randomization; no internal inconsistency, hidden assumption on non-adaptivity, or gap in the i.i.d. model is apparent from the stated result.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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)).","tokens_in":1837,"tokens_out":545,"duration_ms":40837,"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":[{"comment":"§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.","section":"§2"},{"comment":"§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.","section":"§3"}],"minor_comments":[{"comment":"Abstract: the sentence 'no strategy, even if randomized and adaptive' could be cross-referenced to the precise statement of the lower-bound theorem.","section":"Abstract"},{"comment":"Notation: the definition of v_n should appear in the main body before its first use in the abstract and introduction.","section":"Introduction"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the thorough review and positive recommendation. We address each major comment below.","responses":[{"response":"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_made":"yes","referee_comment":"[§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."},{"response":"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_made":"yes","referee_comment":"[§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."}],"tokens_in":1501,"tokens_out":427,"duration_ms":42458,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that this paper settles the asymptotic expected time for filling a length-n array online with i.i.d. Unif[0,1] samples while keeping occupied entries non-decreasing: no strategy beats (1/2 - o(1)) n log n in expectation, and an explicit deterministic strategy hits at most (1/2 + o(1)) n log n. The with-replacement version drops to O(n sqrt(log n)).\n\nWhat is new is the 1/2 factor itself and the matching bounds that apply even to randomized adaptive strategies. The coupon-collector baseline they compare against is the natural (1+o(1)) n log n, so the improvement is concrete. They also give a clean separation by exhibiting a deterministic overwrite strategy that is asymptotically faster.\n\nThe work is grounded in direct analysis of the process rather than reductions or fitted parameters. The lower bound argument appears to track the information or ordering constraints directly, and the upper bound comes from an explicit rule rather than existence.\n\nThe soft spots are minor and typical for this style of result. The o(1) hides lower-order terms that are not characterized, and the with-replacement bound is only an upper bound with no matching lower bound shown. The abstract states the claims clearly, but without the full proofs in front of me I cannot check the technical details of the lower-bound argument for adaptivity.\n\nThis is for researchers in online algorithms and stochastic processes who care about constrained filling or selection problems. It is a self-contained, cleanly stated result with explicit constructions, so it deserves a serious referee rather than a desk reject.","headline":"Paper pins down tight (1/2 ± o(1)) n log n asymptotics for the monotone array completion game and shows a separation for the overwrite variant.","tokens_in":2275,"tokens_out":411,"would_cite":false,"duration_ms":21878,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"The optimal expected time to complete an online monotone array is (1/2 + o(1)) n log n.","keywords":["online algorithms","monotone array","completion time","coupon collector","uniform samples","deterministic strategy","with-replacement model"],"falsifier":"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.","tokens_in":2678,"feed_emoji":"","tokens_out":672,"duration_ms":30992,"temperature":0.7,"pith_summary":"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.","feed_headline":"Monotone array completes in (1/2+o(1))n log n steps","feed_subtitle":"Matching bounds show optimal play halves coupon-collector time; with-replacement version reaches O(n sqrt(log n))","key_machinery":"The irrevocable placement rule that preserves non-decreasing order on i.i.d. Unif[0,1] samples.","core_discovery":"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)).","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Optimal v_n is (1/2+o(1))n log n for monotone array","Matching bounds halve coupon collector for array fill","Deterministic monotone array strategy (1/2+o(1))n log n","O(n sqrt(log n)) for with-replacement array version"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"Incoming values are independent uniform random numbers on the unit interval and the only rule is that occupied positions must stay non-decreasing.","fun_headline_variants_meta":{"raw":{"variants":["Optimal v_n is (1/2+o(1))n log n for monotone array","Matching bounds halve coupon collector for array fill","Deterministic monotone array strategy (1/2+o(1))n log n","O(n sqrt(log n)) for with-replacement array version"]},"model":"grok-4.3","cost_usd":0.005739,"raw_usage":{"total_tokens":2770,"prompt_tokens":734,"num_sources_used":0,"completion_tokens":75,"cost_in_usd_ticks":57387000,"prompt_tokens_details":{"text_tokens":734,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1961,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":734,"tokens_out":75,"duration_ms":18003,"temperature":1.0,"reasoning_tokens":1961,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-01T02:10:50.909923+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}