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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [§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.
- [§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, 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)
- [§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.
- [§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.
- [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.
- [§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
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.
-
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
assumptions (4)
- ad hoc to paper Theorem 4.1 of Chen [4] holds as stated and applies to the stopping rule used here.
- domain assumption The observations X1, X2, ... are independent and identically distributed Bernoulli variables.
- standard math Bounded convergence and the monotonicity of stopping times justify the limit argument in Theorem 8.
- standard math Taylor expansions are valid for the worst-case efficiency ratio when beta is close to zero.
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
Reference graph
Works this paper leans on
-
[4]
A theory of truncated inverse sampling,
X. Chen, “A theory of truncated inverse sampling,” Sequential Analysis, vol. 37, pp. 455–486, 2019
work page 2019
-
[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
work page 2018
-
[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
work page 2013
-
[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
work page 2012
-
[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
work page 1952
-
[6]
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
work page 2015
-
[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
work page 2008
-
[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
work page 2014
Show all 25 references
-
[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
2011
-
[10]
M. M. Desu and D. Raghavarao, Sample Size Methodology , Academic Press, 1990
1990
-
[11]
G. S. Fishman, Monte Carlo: Concepts, Algorithms, and Applications , Springer, 2003
2003
-
[12]
Is statistics too difficult?
F. Hampel, “Is statistics too difficult?” The Canadian Journal of Statistics , vol. 26, pp. 497-513, 1998
1998
-
[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
2006
-
[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
1963
-
[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
2011
-
[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
2010
-
[17]
Mitchell, Machine Learning, Mc Graw Hill, 1997
T. Mitchell, Machine Learning, Mc Graw Hill, 1997
1997
-
[18]
Mitzenmacher and E
M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Prob abilistic Analysis, Cambridge University Press, Second edition, 2017
2017
-
[19]
Motwani and P
R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995
1995
-
[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
2013
-
[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
2008
-
[22]
V. N. Vapnik, The Nature of Statistical Learning , Springer, 1995
1995
-
[23]
V. N. Vapnik, Statistical Learning Theory , Wiley, 1998
1998
-
[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
2002
-
[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
2006
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.