Pith. sign in

REVIEW 3 major objections 4 minor 25 references

Probability Estimation with Truncated Inverse Binomial Sampling

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 1908.06907 v1 pith:SQQHIFXY submitted 2019-08-19 math.ST cs.SYeess.SYstat.MLstat.TH

classification math.STcs.SYeess.SYstat.MLstat.TH MSC 62L1262L1060G40
keywords truncatedinversebinomialsamplingprobabilityestimationrectangularrandomwalkmixederrorcriterionChernoff-HoeffdingboundBernoulliparametersequentialstoppingruleMonteCarlosimulation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [§3.1, Theorem 1] 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.
  2. [§3.2.2, Chernoff–Hoeffding derivation] 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.
  3. [§3.3, Theorem 8] 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.
minor comments (4)
  1. [§3.2.2] 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.
  2. [§5] 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.
  3. [Throughout] 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.
  4. [§3.3] The estimator in Theorem 8 is denoted '~p', which is visually confusing; a standard notation such as p̂_N or p̃ would be clearer.

Circularity Check

1 steps flagged · score 4.0 of 10

Rectangular-walk guarantee is a direct corollary of the author's own Theorem 1, restated from Chen [4] without proof; the sole internal cross-check contains a false identity.

  1. self citation load bearing [Section 3.1 (Theorem 1), Section 3.1 (Theorem 2), Section 4.2 (Rectangular Random Walk)]
    "The following result is a restatement of Theorem 4.1 of Chen [4]. ... Making use of Theorem 1, we have derived the following result. ... According to Theorem 2, the mixed criterion (6) is satisfied."

    Every subsequent guarantee, including the proposed rectangular random walk method in Section 4.2, follows from Theorem 1, which is not proved in this paper but is imported from the author's own prior work (Chen [4]). The central probabilistic claim of the method is exactly Theorem 2's conclusion with L and W set to the stated values; no independent proof or verification is supplied inside the paper. The only attempt to corroborate Theorem 1 internally, the derivation of the Chernoff-Hoeffding bound in Section 3.2.2, uses the false identity Pr(A∪B)=Pr(A) when A⊂B, so it cannot serve as independent support. The load-bearing step therefore reduces to an unverified (in this text) self-citation.

full rationale

The paper is transparent that Theorem 1 is a restatement of Theorem 4.1 of Chen [4] and does not claim to prove it anew. Nevertheless, the main contribution's accuracy guarantee is essentially a corollary of that self-cited theorem. The algebraic passage from Theorem 1 to Theorem 2 is a real derivation, and the worst-case efficiency analysis in Section 5 is an independent Taylor-approximation calculation, so the paper is not wholly circular. However, the foundational mixed-error guarantee is load-bearing and is taken on faith from the author's own prior publication. The attempted independent cross-check in Section 3.2.2, reducing the theory to the Chernoff-Hoeffding bound, is mathematically flawed: for β>α/p, the event |p̂−p|<α implies the relative-error event, so the union of the two events is the relative-error event, not the absolute-error event as claimed. Consequently, the paper's only internal corroboration of Theorem 1 is invalid, and the central guarantee rests on an unproved self-citation. This is a partial circularity, but not a full one, because the paper does provide nontrivial corollaries and a new method that are not themselves definitions.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central statistical guarantee is imported from the author's earlier Theorem 4.1 (Chen [4]) and every theorem in the paper reduces to it; the rectangular walk is a corollary. There are no fitted parameters and no invented physical or statistical entities. The efficiency factor is an approximate Taylor result, not an exact theorem for all beta.

assumptions (4)
  • ad hoc to paper Theorem 4.1 of Chen [4] holds as stated and applies to the stopping rule used here.
    All probability estimation guarantees in the paper are derived from Theorem 1, which is explicitly a restatement of the author's earlier theorem; no proof is reproduced, so the entire edifice rests on this external result.
  • domain assumption The observations X1, X2, ... are independent and identically distributed Bernoulli variables.
    The model is stated in Theorem 1 and is standard for Monte Carlo sampling of an event indicator. It limits the method to static Bernoulli trials rather than general stochastic processes.
  • standard math Bounded convergence and the monotonicity of stopping times justify the limit argument in Theorem 8.
    The proof of inverse binomial sampling as alpha tends to 0 uses bounded convergence; this is standard, but the almost-sure convergence of the stopping time m_alpha to N is asserted rather than fully demonstrated.
  • standard math Taylor expansions are valid for the worst-case efficiency ratio when beta is close to zero.
    Equation (7) uses ln(1+beta) approximately beta minus beta^2/2; the paper does not quantify the error for finite beta, so the clean factor (1/4)(beta/alpha) is an approximation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Probability Estimation with Truncated Inverse Binomial Sampling." pith.science (2026). https://pith.science/paper/SQQHIFXY

@misc{pith2026190806907,
  author       = {Pith},
  title        = {Pith review of: Probability Estimation with Truncated Inverse Binomial Sampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SQQHIFXY}},
  note         = {Machine review of arXiv:1908.06907}
}
read the original abstract

In this paper, we develop a general theory of truncated inverse binomial sampling. In this theory, the fixed-size sampling and inverse binomial sampling are accommodated as special cases. In particular, the classical Chernoff-Hoeffding bound is an immediate consequence of the theory. Moreover, we propose a rigorous and efficient method for probability estimation, which is an adaptive Monte Carlo estimation method based on truncated inverse binomial sampling. Our proposed method of probability estimation can be orders of magnitude more efficient as compared to existing methods in literature and widely used software.

Figures

Figures reproduced from arXiv: 1908.06907 by the authors.

Figure 1
Figure 1. Rectangular Random Walk Define the relative frequency pb = Sm m as an estimator for the desired probability p. According to Theorem 2, the mixed criterion (6) is satisfied. We call the above random walk as Rectangular Random Walk as the point with coordinate (n, Sn) is moving until it is out of the rectangular domain B. 5 Worst-Case Analysis In this section, we shall investigate the worst-case performance of the met… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [4]

    A theory of truncated inverse sampling,

    X. Chen, “A theory of truncated inverse sampling,” Sequential Analysis, vol. 37, pp. 455–486, 2019

  2. [1]

    A survey of statistical model checkin g,

    G. Agha and K. Palmskog, “A survey of statistical model checkin g,” ACM Transactions on Modeling and Computer Simulation, vol. 28, pp. 1–39, 2018

  3. [2]

    A randomized approach for robust con trol of uncertain UA Vs,

    E. Capello and R. Tempo, “A randomized approach for robust con trol of uncertain UA Vs,” 2nd IF AC Workshop on Research, Education and Development of Unm anned Aerial Systems , pp. 226–231, Compiegne, France, November 2013

  4. [3]

    A simulation-based approach for contr ol design of uncertain UA Vs,

    E. Capello and R. Tempo, “A simulation-based approach for contr ol design of uncertain UA Vs,” IEEE Conference on Decision and Control , pp. 3086–3091, December 10-13, 2012. Maui, Hawaii, USA

  5. [5]

    A measure of asymptotic efficiency for tests of a h ypothesis based on the sum of obser- vations,

    H. Chernoff, “A measure of asymptotic efficiency for tests of a h ypothesis based on the sum of obser- vations,” Annals of Mathematical Statistics , vol. 23, pp. 493–507, 1952

  6. [6]

    Up paal SMC tutorial

    A. David, K. Larsen, A. Legay, M. Mikucionis, and D. Poulsen, “Up paal SMC tutorial”, International Journal on Software Tools for Technology Transfer , vol. 17, pp. 397–415, 2015

  7. [7]

    RACT - Randomized algorithms control toolbox: A tutorial introduction,

    F. Dabbene, C. Lagoa, P. Shcherbakov, and A. Tremba, “RACT - Randomized algorithms control toolbox: A tutorial introduction,” IEEE International Symposium on Intelligent Control , 2008

  8. [8]

    Randomized methods for control of u ncertain systems,

    F. Dabbene and R. Tempo,“Randomized methods for control of u ncertain systems,” Encyclopedia of Systems and Control , Springer-Valag, 2014

Show all 25 references
  1. [9]

    Probabilistic and randomized tools for control design,

    F. Dabbene and R. Tempo, “Probabilistic and randomized tools for control design,” The Control System Handbook – Control System Advanced Methods , CRC Press, Second Edition, 2011

  2. [10]

    M. M. Desu and D. Raghavarao, Sample Size Methodology , Academic Press, 1990

  3. [11]

    G. S. Fishman, Monte Carlo: Concepts, Algorithms, and Applications , Springer, 2003

  4. [12]

    Is statistics too difficult?

    F. Hampel, “Is statistics too difficult?” The Canadian Journal of Statistics , vol. 26, pp. 497-513, 1998

  5. [13]

    APMC 3.0: Approximate ve rification of discrete and continuous time Markov chains,

    T. H´erault, S. Peyronnet, and R. Lassaigne, “APMC 3.0: Approximate ve rification of discrete and continuous time Markov chains,” Proceedings of International Conference on Quantitative E valuation of Systems , pp. 129–130, Riverside, California, 2006. 13

  6. [14]

    Probability inequalities for sums of bounded rando m variables,

    W. Hoeffding, “Probability inequalities for sums of bounded rando m variables,” Journal of the Amer- ican Statistical Association, vol. 58, pp. 13–30, 1963

  7. [15]

    PRISM 4.0: Verific ation of probabilistic real-time systems,

    M. Kwiatkowska, G. Norman, and D. Parker, “PRISM 4.0: Verific ation of probabilistic real-time systems,” Lecture Notes in Computer Science , vol. 6806, pp. 585–591, Springer, 2011

  8. [16]

    Statistical model ch ecking: An overview,

    A. Legay, B. Delahaye, and S. Bensalem, “Statistical model ch ecking: An overview,” Lecture Notes in Computer Science , vol. 6418, Springer, Berlin, 2010

  9. [17]

    Mitchell, Machine Learning, Mc Graw Hill, 1997

    T. Mitchell, Machine Learning, Mc Graw Hill, 1997

  10. [18]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Prob abilistic Analysis, Cambridge University Press, Second edition, 2017

  11. [19]

    Motwani and P

    R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995

  12. [20]

    Tempo, G

    R. Tempo, G. Calafiore, and F. Dabbene, Randomized Algorithms for Analysis and Control of Uncer- tain Systems: With Applications , Second edition, Springer, 2013

  13. [21]

    RACT: Randomized algorithms control toolbox for MATLAB,

    A. Tremba, G. Calafiore, F. Dabbene, E. Gryazina, B. Polyak, P . Shcherbakov, and R. Tempo, “RACT: Randomized algorithms control toolbox for MATLAB,” Proceedings of the 17th World Congress of The International Federation of Automatic Control , pp. 390–395, Seoul, Korea, July 2008

  14. [22]

    V. N. Vapnik, The Nature of Statistical Learning , Springer, 1995

  15. [23]

    V. N. Vapnik, Statistical Learning Theory , Wiley, 1998

  16. [24]

    Vidyasagar, Learning and Generalisation: With Applications to Neural N etworks, Springer, 2nd ed., 2002

    M. Vidyasagar, Learning and Generalisation: With Applications to Neural N etworks, Springer, 2nd ed., 2002

  17. [25]

    Error control for probabilistic model check ing,

    H. L. S. Younes, “Error control for probabilistic model check ing,” Proceedings of International Work- shop on Verification, Model Checking, and Abstract Interpre tation, pp. 142–156, 2006. 14

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.