{"id":"1489a894-57a8-4d7f-afc7-aac2aca1a5b2","arxiv_id":"1908.06907","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A truncated inverse binomial stopping rule can certify a mixed absolute-relative error bound for a probability estimate with a worst-case sample count near a quarter of the beta/alpha ratio times the Chernoff-Hoeffding count.","lead":"This paper builds statistical guarantees for an adaptive Monte Carlo estimator that stops after a fixed sample cap or after enough successful samples, and claims large efficiency gains over the Chernoff-Hoeffding bound. A generalist should care because the method targets certified rare-event probability estimates at lower simulation cost.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unproved Theorem 1 is the load-bearing input; the paper's only internal check of it, the derivation of the Chernoff-Hoeffding bound in §3.2.2, contains a demonstrable error. No correct independent verification of the rectangular-walk coverage guarantee is supplied.","rationale":"The reader's weakest_assumption correctly identifies Theorem 1 as the load-bearing input: every later theorem, including the rectangular-walk guarantee and the worst-case analysis, is a corollary of that unproved, self-cited restatement. I agree with that assessment. My stress-test adds a concrete reason to worry: §3.2.2, which is the paper's own demonstration that the theory implies the Chernoff-Hoeffding bound, contains a clear sign error in the event identity and a false Taylor lower bound. This does not by itself falsify Theorem 1 or the rectangular walk, but it shows the author's handling of the black box is not reliable enough to leave unverified. The Section 5 small-β Taylor approximation is a weaker concern: the exact ratio f/(2αβ) with f=(1+β)ln(1+β)-β differs from (1/4)(β/α) by only about 3% for β=0.1 and less for β=0.01, so the 'orders of magnitude' conclusion is robust to that approximation. The appropriate remedy is to supply a proof or exact reference with conditions for Theorem 1, correct the Chernoff-Hoeffding derivation, and provide a numerical coverage check of the rectangular walk; until then CONDITIONAL remains the right verdict. Since the reader already recommended CONDITIONAL, my read does not change the verdict.","tokens_in":9532,"tokens_out":24117,"duration_ms":249935,"concrete_test":"Compute, by dynamic programming over n=1,...,floor(L)+1 with L and W from §4.2, the exact failure probability P_fail(p)=Pr{|p̂-p|≥α and |p̂-p|/p≥β} for fixed p, with δ=10⁻³, α=10⁻⁶, β=0.01, and p on a logarithmic grid from 10⁻⁸ to 0.5 plus p=α/β, p=α, and p=α/(β+α). If any P_fail(p) ≥ δ within round-off tolerance, Theorem 1 is false as used and the central guarantee collapses. If all pass, rerun the same check at the boundary α/β+α/2=1/2; this still is not a proof, but it would show the stated constants are not contradicted by the walk's exact distribution.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The rectangular-walk guarantee in §4.2 and the worst-case efficiency claim in §5 both rest on Theorem 2, which is Theorem 1 (restated from Chen [4]) with a simplified constant. The paper gives no proof of Theorem 1, and the one internal consequence that could corroborate it, the derivation of the Chernoff-Hoeffding bound in §3.2.2, is not sound. The text asserts Pr{|p̂-p|<α or |p̂-p|/p<β} = Pr{|p̂-p|<α} because β>α/p, but for β>α/p the relative-error event is larger than the absolute-error event: absolute error implies relative error, not conversely, so the union is the relative-error event. The subsequent Taylor lower bound H(α/(β+α), α/β) ≥ 2α² is also false; for α=0.01, β=0.2 one computes H≈6×10⁻⁵ < 2×10⁻⁴. This does not disprove Theorem 1, but it means the foundational black box is not corroborated by any correct consequence in this paper, and the abstract's claim that the Chernoff-Hoeffding bound is an immediate consequence is unsupported. If Theorem 1 were misstated or inapplicable at the α, β used in §4.2, the coverage guarantee would collapse; no empirical or independent verification is provided.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript develops a theory of truncated inverse binomial sampling and proposes an adaptive Monte Carlo estimator for a Bernoulli probability p. The proposed 'rectangular random walk' stops as soon as the sample path (n, S_n) exits a rectangle of length L and width W, and the resulting estimate p̂ is claimed to satisfy the mixed error guarantee Pr{|p̂−p|<α or |p̂−p|/p<β} > 1−δ. The paper states a general theorem (Theorem 1, restated from the author's Chen [4]) and derives from it simplified sample-size formulas (Theorems 2–6), a purported new derivation of the Chernoff–Hoeffding bound (Section 3.2.2), an inverse-binomial limit (Theorem 8), and a worst-case efficiency comparison with the Chernoff–Hoeffding bound (Section 5), where the worst-case improvement is approximately (1/4)(β/α). The abstract goes further and claims the method can be orders of magnitude more efficient than existing methods.","tokens_in":9854,"tokens_out":12653,"duration_ms":121737,"significance":"If the central guarantee is valid, the proposed rectangular random walk is an attractive and simple sequential procedure: it explicitly controls a mixed absolute/relative error criterion, has a hard worst-case cap of about L+1 simulations, and can yield a substantial reduction relative to fixed-size sampling based on the Chernoff–Hoeffding bound. The elementary derivations of Theorems 2, 3, and 5 from Theorem 1 are mostly correct, and the monotonicity argument in the proof of Theorem 3 is sound. However, the paper's central theorem is imported as a black box, and the manuscript's own attempts to corroborate it—the Chernoff–Hoeffding derivation and the inverse-binomial limit—contain demonstrable mathematical errors. These problems affect advertised consequences of the theory and leave the main coverage guarantee without independent verification in this manuscript. The potential significance is real, but the current presentation does not establish the claims as stated.","major_comments":[{"comment":"Theorem 1 is the load-bearing result of the paper: Theorem 2, and therefore the rectangular random walk guarantee in §4.2, is an immediate corollary of it, and Theorems 4–8 all depend on it. Yet Theorem 1 is merely restated from Chen [4], with no proof and no verification that the hypotheses of [4] are satisfied for the parameter choices used in §4.2. The coverage guarantee in §4.2 collapses if Theorem 1 is misstated or inapplicable, so the author should either include a complete proof of Theorem 1 or clearly state and justify the exact conditions under which the cited theorem applies to the stopping rule used here. Relying on a black box at the core of the proposed method is a serious self-containedness and verifiability problem.","section":"§3.1, Theorem 1"},{"comment":"The derivation of the Chernoff–Hoeffding bound is incorrect. The equality Pr{|p̂−p|<α or |p̂−p|/p<β} = Pr{|p̂−p|<α} is asserted to follow from β > α/p, but this is backwards: when β > α/p, the absolute-error event implies the relative-error event, so the union equals the relative-error event, not the absolute-error event. In addition, the chain replacing ln(2/δ)/H(α/(β+α), α/β) by β ln(2/δ)/(α((1+β)ln(1+β)+(β−α−αβ)ln(1−αβ/(β−α)))) is algebraically false, and the claimed Taylor lower bound H(α/(β+α), α/β) ≥ 2α² is false; for example, with α=0.01 and β=0.2, H≈6×10⁻⁵, far below 2α²=2×10⁻⁴. Consequently, the paper does not in fact derive the Chernoff–Hoeffding bound from its general theory, and the abstract's statement that this bound is an 'immediate consequence' is unsupported.","section":"§3.2.2, Chernoff–Hoeffding derivation"},{"comment":"The proof of Theorem 8 contains a substantial algebraic error in the displayed formula for B. From the definition in Theorem 1, B = β ln(2/δ) / [(β+α)((1+β)ln(1+β) + (β−α−αβ)ln(1−αβ/(β−α)))], which is not equal to the expression (1+β)ln(2/δ) / [(1+β)ln(1+β) + (β/α−1−β)ln(1−αβ/(β−α))] that appears in the proof. With α=0.01 and β=0.2 (and ln(2/δ)=1), the two sides differ by more than an order of magnitude. The claimed convergence of W and the resulting inverse-binomial stopping rule are therefore not established by the proof as written. Since the inverse-binomial limit is one of the advertised special cases of the theory, this proof must be corrected or replaced by an independent argument.","section":"§3.3, Theorem 8"}],"minor_comments":[{"comment":"The condition β > max{α/(1−α), α/p} involves the unknown p, so it cannot be used to select β in a data-free way; this is closely connected to the logical error in the union-event argument and should be addressed if the section is rewritten.","section":"§3.2.2"},{"comment":"The approximation (7) is derived under the assumption that β is small, and the subsequent statement that the average improvement 'can be much greater' than (1/4)(β/α) is not proved; the text should clearly distinguish the rigorous worst-case bound from the heuristic average-efficiency claim.","section":"§5"},{"comment":"There are several presentation issues: the abstract contains a typo ('inver se'), 'softwares' is nonstandard, 'astronautical number' should likely be 'astronomical number', and 'retangular' appears in Section 5. These are minor but should be corrected.","section":"Throughout"},{"comment":"The estimator in Theorem 8 is denoted '~p', which is visually confusing; a standard notation such as p̂_N or p̃ would be clearer.","section":"§3.3"}],"recommendation":"major_revision","confidential_remarks":"The paper's central guarantee rests entirely on a theorem from the author's own prior work, cited as Chen [4], with no proof reproduced. This is a notable self-citation at the core of the submission, and the one internal derivation that might have corroborated the theorem (the Chernoff–Hoeffding argument) is demonstrably wrong. The editor may wish to require the author to provide a full proof of the black-box theorem or obtain an independent verification before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. The rectangular random walk is a genuinely new and simple stopping rule: stop at n > L or S_n > W, estimate S_m/m, and get a mixed absolute-or-relative error guarantee. The worst-case sample-size ratio β/(4α) versus the Chernoff-Hoeffding sample size is a useful back-of-the-envelope result. But the paper's own validation of its foundation is wrong. The derivation of the Chernoff-Hoeffding bound in §3.2.2 asserts that for β > α/p the mixed event equals the absolute-error event. That's backwards: absolute error then implies relative error, so the union is the relative-error event. The accompanying Taylor lower bound H(α/(β+α), α/β) ≥ 2α² is numerically false (try α=0.01, β=0.2). So the abstract's claim that the Chernoff-Hoeffding bound is an immediate consequence of the theory is not supported.\n\nThe main theorems are all corollaries of Theorem 1, which is restated from the author's Chen [4] without proof. That is legitimate if the reference is reliable, but it makes the paper a dependent extension, not a self-contained derivation. A referee should ask for a proof or a precise location. There is also an algebraic step in the proof of Theorem 8 that does not balance; I'd ask the author to recheck the expression for B as α→0. No simulations are reported, and the 'orders of magnitude' headline compares a relaxed mixed criterion against an absolute-error bound, so some of the gain is bought by relaxing the requirement.\n\nWhat the paper does well: the mixed criterion is sensible for rare events, the rectangular walk is concrete and easy to implement, and Theorem 2's simplification of the stopping constants is genuinely useful. The right audience is people who need sequential Monte Carlo with certified error for rare probabilities. If Theorem 1 holds up, the method likely works.\n\nI'd send it to peer review with a request for major revision: prove or precisely cite Theorem 1, fix or delete the CH derivation, correct Theorem 8, and add at least one numerical experiment. It isn't ready to cite yet, but the core idea deserves referee time.","headline":"A promising rectangular-walk extension of truncated inverse sampling that is not self-contained and contains a demonstrably wrong Chernoff-Hoeffding derivation; needs major revision before the efficiency claims can be trusted.","tokens_in":10335,"tokens_out":10739,"would_cite":false,"duration_ms":101646,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L12","62L10","60G40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a simple rectangular stopping rule for Bernoulli simulation guarantees the mixed error bound $\\Pr\\{|\\hat p-p|<\\alpha \\text{ or } |\\hat p-p|/p<\\beta\\}>1-\\delta$ using at most $L+1$ simulations, about…","keywords":["truncated inverse binomial sampling","probability estimation","rectangular random walk","mixed error criterion","Chernoff-Hoeffding bound","Bernoulli parameter","sequential stopping rule","Monte Carlo simulation"],"falsifier":"Compute the failure probability of the rectangular random walk for the stated $L$ and $W$ at adversarial $p$ values, for example $p$ near $\\alpha/\\beta$ or $p$ near $W/L$, by exact dynamic programming or exhaustive simulation of Bernoulli streams; if the failure probability reaches $\\delta$ for any $p\\in(0,1)$, the central guarantee is false. Independently, calculate the exact ratio $\\ln(2/\\delta)/(2\\alpha^2)/(L+1)$ for a small finite $\\beta$ such as $0.01$; if it falls materially below $\\frac{1}{4}\\frac{\\beta}{\\alpha}$, the efficiency claim as stated is not justified.","tokens_in":9317,"feed_emoji":"🎲","tokens_out":6262,"duration_ms":57358,"temperature":0.7,"pith_summary":"The paper develops a general theory of truncated inverse binomial sampling and uses it to build an adaptive Monte Carlo estimator for a Bernoulli probability $p$. The estimator stops as soon as the path $(n, S_n)$ leaves a rectangle, so it needs no pre-chosen sample size. It certifies that, with probability at least $1-\\delta$, the estimate is within absolute error $\\alpha$ or, as an alternative, within relative error $\\beta$ of $p$. The author argues this relaxation makes rigorous probability estimation feasible for very small probabilities, where the classical Chernoff-Hoeffding bound demands astronomically many simulations.","feed_headline":"Rectangular stopping rule shrinks Monte Carlo cost by β/(4α)","feed_subtitle":"Guarantees absolute or relative error with at most L+1 simulations.","key_machinery":"The central object is the rectangular random walk: observe $(n,S_n)$, stop at the first $m$ with $m>L$ or $S_m>W$, and estimate $p$ by $S_m/m$. The constants $L$ and $W$ are chosen from a mixed-error stopping bound so that Theorem 2 certifies the guarantee. The same machinery accommodates fixed-size sampling as a limit, inverse binomial sampling as $\\alpha\\to 0$, and the classical Chernoff-Hoeffding bound as a corollary.","core_discovery":"The paper's central claim is that for any Bernoulli probability $p\\in(0,1)$ and user-chosen margins $0<\\alpha<\\beta<1$ with $\\alpha/\\beta+\\alpha^2\\le 1/2$, the rectangular stopping rule with $L=\\frac{\\beta}{(1+\\beta)\\ln(1+\\beta)-\\beta}\\frac{\\ln(2/\\delta)}{\\alpha}$ and $W=\\frac{\\alpha}{\\beta+\\alpha}L$ produces $\\hat p=S_m/m$ satisfying $\\Pr\\{|\\hat p-p|<\\alpha \\text{ or } |\\hat p-p|/p<\\beta\\}>1-\\delta$. Thus the estimator is allowed to be inaccurate in absolute terms as long as it is accurate relative to the true probability. The worst-case number of simulations is $L+1$, and when $\\beta$ is small this is about $\\frac{1}{4}\\frac{\\beta}{\\alpha}$ times the Chernoff-Hoeffding sample size. The author presents this as a new computationally practical way to certify risk estimates for small probabilities.","pith_inferences":["Editorial inference: the same rectangular stopping idea could plausibly extend from Bernoulli indicators to estimating means of bounded random variables, provided a concentration inequality plays the role of Theorem 1; the paper does not state this extension.","Editorial inference: the clean factor $\\frac{1}{4}\\frac{\\beta}{\\alpha}$ is derived through a small-$\\beta$ Taylor approximation, so for larger $\\beta$ the exact worst-case improvement may be less favorable; users should compute the exact ratio rather than rely on the asymptotic formula.","Editorial inference: the paper bounds only the worst-case stopping time; a natural testable extension is to quantify the expected stopping time as a function of $p$, since the paper notes the average improvement can be much greater than the worst-case factor."],"forward_implications":["A user who accepts a relative-error margin $\\beta$ in place of a very small absolute margin $\\alpha$ can replace the Chernoff-Hoeffding sample size $\\ln(2/\\delta)/(2\\alpha^2)$ with a stopping rule whose worst-case cost is about $\\frac{1}{4}\\frac{\\beta}{\\alpha}$ times that size.","The stopping rule has a bounded sample size of at most $L+1$, so computational resources can be planned in advance, unlike unbounded inverse binomial sampling.","The mixed criterion reduces exactly to the absolute-error criterion when $p<\\alpha/\\beta$, so the method remains trustworthy for very small probabilities relative to $\\alpha$.","Fixed-size sampling, inverse binomial sampling, and the Chernoff-Hoeffding bound all appear as special cases of one general truncation theory, giving a unified way to compare error-control strategies.","In the paper's example, accepting a relative margin of $0.01$ with $\\alpha=10^{-6}$ and $\\delta=10^{-3}$ reduces the required number of simulations by a factor of about 2,500."],"supporting_citations":[{"why":"Supplies Theorem 1, the mixed-error stopping bound restated as the foundation for every subsequent theorem and for the rectangular random walk.","marker":"[4]"},{"why":"Provides the Chernoff bound whose sample-size baseline the new method is compared against.","marker":"[5]"},{"why":"Provides the Hoeffding inequality that completes the classical Chernoff-Hoeffding bound, which the paper derives as a corollary of its general theory.","marker":"[14]"}],"fun_headline_variants":["Rectangular stopping rule slashes Monte Carlo cost to β/(4α) of Chernoff","Dual error guarantee: rectangle stop rule yields p with β/4α fewer runs","Faster probability estimation: rectangular stop rule beats Chernoff by β/4α","Truncated inverse binomial sampling: error-guaranteed p with β/4α cost","Rectangle rule: guaranteed absolute or relative error at β/4α of Chernoff cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The rectangular walk's error guarantee rests on Theorem 1, which is quoted from the author's earlier paper as a black box: if that stopping-rule bound is wrong or misstated, every subsequent guarantee in this paper collapses.","fun_headline_variants_meta":{"raw":{"variants":["Rectangular stopping rule slashes Monte Carlo cost to β/(4α) of Chernoff","Dual error guarantee: rectangle stop rule yields p with β/4α fewer runs","Faster probability estimation: rectangular stop rule beats Chernoff by β/4α","Truncated inverse binomial sampling: error-guaranteed p with β/4α cost","Rectangle rule: guaranteed absolute or relative error at β/4α of Chernoff cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001755,"raw_usage":{"total_tokens":6873,"prompt_tokens":836,"completion_tokens":6037,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":452,"completion_tokens_details":{"reasoning_tokens":5922}},"tokens_in":452,"tokens_out":6037,"duration_ms":40533,"temperature":1.0,"reasoning_tokens":5922,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:31:10.212252+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the failure probability of the rectangular random walk for the stated $L$ and $W$ at adversarial $p$ values, for example $p$ near $\\alpha/\\beta$ or $p$ near $W/L$, by exact dynamic programming or exhaustive simulation of Bernoulli streams; if the failure probability reaches $\\delta$ for any $p\\in(0,1)$, the central guarantee is false. Independently, calculate the exact ratio $\\ln(2/\\delta)/(2\\alpha^2)/(L+1)$ for a small finite $\\beta$ such as $0.01$; if it falls materially below $\\frac{1}{4}\\frac{\\beta}{\\alpha}$, the efficiency claim as stated is not justified.","supporting_citations":[{"cited_title":"A theory of truncated inverse sampling,","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 1, the mixed-error stopping bound restated as the foundation for every subsequent theorem and for the rectangular random walk."},{"cited_title":"A measure of asymptotic efficiency for tests of a h ypothesis based on the sum of obser- vations,","cited_arxiv_id":null,"evidence_quote":"Provides the Chernoff bound whose sample-size baseline the new method is compared against."},{"cited_title":"Probability inequalities for sums of bounded rando m variables,","cited_arxiv_id":null,"evidence_quote":"Provides the Hoeffding inequality that completes the classical Chernoff-Hoeffding bound, which the paper derives as a corollary of its general theory."}],"review_version":1}