{"id":"09eca51c-b8b1-4d23-a6c6-65f788e4735f","arxiv_id":"2607.21275","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The acceptance-complement method can generate gamma, beta, and every log-concave density with known mode in bounded, loop-free time using a fixed grid built from black-box density evaluations.","lead":"This paper develops a constant-time alternative to rejection sampling for random variate generation, applied to gamma, beta, and all log-concave densities with known mode. A generalist might read it because deterministic-time sampling has practical value in simulation, exact algorithms, and batch Monte Carlo work.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Universal log-concave sampler hinges on unproved tail inequality (8) and the asserted n=7, δ=2/5 bound on ∫q; if either fails, the 16-interval acceptance-complement construction is invalid.","rationale":"The reader's CONDITIONAL verdict and weakest-assumption identification match my reading. The central constructive idea—a fixed 16-interval acceptance-complement scheme for all log-concave densities—is plausible and the algorithm is well-specified, but the proof of Theorem 1 is compressed at exactly the point where correctness depends: the tail inequality (8) and the numerical bound that gives ∫q≤1. I independently checked the numerical bound for n=7, δ=0.4 and obtained ≈0.954<1, and I verified the gamma A value at a=5 is ≈0.825<1, so I found no counterexample. The concern is therefore not that the claims are false, but that the paper asserts load-bearing inequalities ('one can show A<1', 'φ<1', 'any choice 0.3467≤δ≤0.4643 will do') without proof or code. This is enough to keep the verdict CONDITIONAL, but not to reject: the missing derivations are checkable and my spot checks support them. I would not move the verdict to ACCEPT until the inequalities are supplied, and I see no basis for REJECT.","tokens_in":10875,"tokens_out":34263,"duration_ms":330917,"concrete_test":"Derive (8) rigorously: for any log-concave f with mode m, concavity of log f gives ∫_m^x f ≥ (x−m)(f(m)−f(x))/log(f(m)/f(x)) ≤ 1; this plus (7) should yield the displayed tail bound. Then evaluate the ∫q bound at n=7, δ=2/5: 2δ[1+e^{−nδ(1−e^{1−nδ})}(n/(nδ(1−e^{1−nδ}))−1)] = 0.954<1. If either check fails, the 16-interval construction in Theorem 1 collapses; if both pass, the theorem's gap is one of presentation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5's Theorem 1 stands or falls on the bound ∫q≤1. The proof bounds ∫q using (9), which is exactly the tail inequality (8) applied at s_n. Inequality (8) is derived by a terse extremal argument: 'the largest value of f(x) ... occurs when log f is linear ... and zero outside [m,x],' with a displayed integral set equal to 1. A rigorous derivation should instead use the chord lower bound from concavity of log f: ∫_m^x f ≥ (x−m)(f(m)−f(x))/log(f(m)/f(x)), and ∫_m^x f ≤1, then combine with (7). The paper does not give this argument; the extremal density is discontinuous at the mode, so attainment also needs a limiting discussion. The further claim that n=7 and δ∈[0.3467,0.4643] make the displayed bound <1 is a pure numerical assertion with no derivation. If (8) or the numerical bound is wrong, q=Q−r has integral >1 and the universal sampler is not valid. A parallel unproved load-bearing inequality is 'A<1 for a≥5' after Eq. (2), needed for the gamma Algorithm 5, and 'φ<1 for a≥6.2829' in §4. My spot checks (bound at n=7, δ=0.4 ≈0.954; A(5)≈0.825) suggest these are true, so the concern is missing verification rather than a demonstrated contradiction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper revisits the acceptance-complement method for random variate generation, showing that to sample from a density f it suffices to construct r ≤ f and q ≥ f − r with ∫q ≤ 1, yielding a one-iteration (loopless) sampler. It gives a four-part acceptance-complement generator for gamma(a) for a ≥ 5 (Algorithm 5), a gamma-function-free variant for a ≥ 6.2829 (Section 4), and a universal sampler for all log-concave densities with known mode and black-box density evaluations (Algorithm 7, Theorem 1) using a 16-interval grid. The central claim is that deterministic, uniformly bounded execution time is achievable for these families with a finite number of density evaluations per sample.","tokens_in":11276,"tokens_out":9688,"duration_ms":95237,"significance":"If the claims are correct, this is a useful conceptual advance: it replaces geometrically distributed rejection loops with constant-time acceptance-complement samplers, and it provides the first universal bounded-time method for log-concave densities. The paper is commendably explicit: Algorithms 5–7 are concrete, the constructions rely on a parameter-free tail bound from Devroye [5] rather than fitted constants, and no empirical tuning is involved. The main ideas are elegant and the spot checks in the reader's report support the numerical claims. However, several load-bearing inequalities are asserted without proof, and the proof of Theorem 1 is a sketch at exactly the point where correctness depends on a sharp tail bound and a numerical verification. These gaps are local and fillable, but they must be addressed before the paper is publishable.","major_comments":[{"comment":"The proof of Theorem 1 rests on the tail inequality (8), but its derivation is only a sketch. The extremal density 'when log f is linear ... and zero outside [m,x]' is discontinuous at the mode, so attainment requires a limiting discussion, and no rigorous argument is given. A recoverable route is to use concavity of log f to obtain the chord lower bound ∫_m^x f ≥ (x−m)(f(m)−f(x))/log(f(m)/f(x)), then use ∫ f = 1 and inequality (7) to derive (8). Since (9) and the bound on ∫q are direct consequences of (8), this point is load-bearing for Theorem 1 and Algorithm 7.","section":"§5, Inequality (8)"},{"comment":"The proof asserts, without derivation, that 'The first n for which this bound drops below 1 for some x is n=7. Any choice 0.3467≤δ≤0.4643 will do. The minimal value is approximately 0.9540 and occurs for δ≈0.3968.' This numerical verification is exactly what guarantees ∫q ≤ 1 and hence the validity of Algorithm 7. Please provide a complete argument—for example, a monotonicity and calculus proof for n=7 and δ=2/5, or a certified numerical bound—rather than an unstated computer check.","section":"§5, after Eq. (9)"},{"comment":"Algorithm 5 is only valid if A < 1 on the stated range a ≥ 5. The text says 'Combining this, one can show that A < 1 for a ≥ 5' with no proof. If A ≥ 1, the proposed q does not satisfy ∫q ≤ 1 and the acceptance-complement construction fails. Because this inequality is load-bearing for the gamma algorithm, the proof must be supplied using the stated Stirling bound.","section":"§3, after Eq. (2)"},{"comment":"The gamma-function-free modification requires 0 ≤ φ ≤ 1. The text asserts the upper bound is '< 1 for a ≥ 6.2829' without proof. This inequality is load-bearing for the modified Algorithm 5 when Γ(a) is not available. Provide a derivation of the threshold and the bound, including the behavior of ψ(√(a−1)).","section":"§4, after Eq. (6)"}],"minor_comments":[{"comment":"The lower limit in the displayed integral is written as 0; it should be m (or the mode should be normalized to 0 before the calculation).","section":"§5, displayed integral in proof of (8)"},{"comment":"The text in (4) and the surrounding discussion state the condition as 'if W ≤ 1−A', while Algorithm 5 uses 'if W ≥ 1−A'. The replacement and the equivalence calculation should use W ≥ 1−φ(Z), giving probability E[φ(Z)] = A. As written, the directions are inconsistent and confusing.","section":"§4, Eq. (4)"},{"comment":"The line 'generate I such that P{J=j}' mixes I and J; it should read 'generate J such that P{J=j}'.","section":"Algorithm 6"},{"comment":"The phrase 'for some x' in the numerical bound should be 'for some δ'; the independent variable in that bound is δ.","section":"§5, after Eq. (9)"},{"comment":"In the probability statement for J, define r_{n+1}=r_{−(n+1)}=0 explicitly in the algorithm itself, as is done in the surrounding text, to make the weights (Q_j−r_j)/A well defined.","section":"Algorithm 7"}],"recommendation":"major_revision","confidential_remarks":"The paper is promising and the missing inequalities are likely true (independent spot checks support them). I recommend major revision rather than rejection because the gaps are localized and fillable: the authors need to supply rigorous derivations for (8), for the n=7/δ=2/5 numerical bound, for A<1 at a≥5, and for φ<1 at a≥6.2829. The Section 4 threshold notation should also be cleaned up. With those additions, the paper would be a solid contribution to random variate generation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main thing you should know: this paper actually delivers something new. Devroye gives a 16-interval acceptance-complement method that works for every log-concave density with known mode and black-box density access, with uniformly bounded execution time. That is not in the older literature. He also gives a gamma generator that avoids computing the gamma function, simplifying Greaves's one-liners. Those are real contributions, and the paper is honest about their limits: the universal method needs 16 density evaluations per variate and is mainly for batch simulation, and the open problems are stated plainly.\n\nThe modified acceptance-complement relaxation (allowing ∫q≤1 instead of requiring q to be a density) is a small but useful extension of Kronmal and Peterson. The algorithms themselves are explicit and the algebra for the gamma envelope checks out. I spot-checked the bound at n=7, δ=0.4 and got roughly 0.954, and A(5) ≈ 0.825, so the numerical assertions look true.\n\nWhere the paper is soft: the proof of Theorem 1 depends on tail inequality (8), which is derived by a terse extremal argument. The stress-test note is right that a rigorous derivation should use the chord lower bound from concavity of log f, and the extremal density is discontinuous at the mode, so attainment needs a limiting discussion. The paper just says \"one can show\" for A<1 at a≥5 and φ<1 at a≥6.2829, and the n=7, δ∈[0.3467,0.4643] claim is a pure numerical assertion with no derivation. None of these appear to be wrong based on my checks, but they are load-bearing. No code or numerical experiments are included, which is a pity for a computational paper.\n\nThe citation pattern is fine. The key self-citation is inequality (7) from Devroye's 1984 log-concave rejection paper, which is an independent parameter-free bound that the new construction uses, not a circular step. The debt to Greaves is acknowledged.\n\nOverall: the central argument holds up in structure, but the proof of inequality (8) and the threshold checks need to be filled in before I'd trust the universal theorem without doing the work myself. This deserves a serious referee, but the referee should ask for complete derivations of (8) and the numerical bounds, and ideally a small simulation or code to verify the algorithms in practice. I'd take it as a conditional accept with major revision.\n\nIf you work in random variate generation, cite it. It is a legitimate advance, not a footnote.","headline":"A genuinely new universal acceptance-complement sampler for log-concave densities with bounded deterministic time, but several load-bearing inequalities are asserted rather than proved.","tokens_in":11737,"tokens_out":1423,"would_cite":true,"duration_ms":17921,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C10","65C05","11K45","68U20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The acceptance-complement method can generate exact random variates from any log-concave density in one pass, with a fixed bound on run time.","keywords":["acceptance-complement method","random variate generation","log-concave density","gamma distribution","rejection method","one-liner algorithm","deterministic runtime","simulation"],"falsifier":"Evaluate both sides of the tail inequality numerically over a dense grid of (x−m)f(m) values for several log-concave densities (e.g., Laplace, logistic, gamma with shape just above 1) and look for a violation; equivalently, compute ∫q for the paper's grid with δ = 2/5, n = 7 on those densities and check whether it stays below 1. For the gamma claim, compute A in Eq. (2) for a = 5 and nearby values to verify A < 1, since the paper gives no derivation.","tokens_in":10747,"feed_emoji":"🎲","tokens_out":10590,"duration_ms":95834,"temperature":0.7,"pith_summary":"This paper argues that the acceptance-complement method can replace the rejection method in random variate generation, turning a random number of attempts into a single pass. The headline result is a universal sampler: for any log-concave density (a large family of single-peaked densities such as the normal and gamma with shape at least 1) with a known mode and black-box density evaluations, a 16-interval squeeze gives an exact generator whose execution time is uniformly bounded, independent of the density. The same technique yields a loopless gamma generator for shape at least 5, and a version that avoids evaluating the gamma function for shape at least 6.2829, with smaller shapes handled by an exact scaling identity. If the construction holds, this would be the first simulation method with deterministic, uniformly bounded runtime for the whole log-concave family, and it would give one-liner generators for gamma, beta, and related distributions.","feed_headline":"16 fixed intervals replace rejection loops for log-concave sampling","feed_subtitle":"A universal squeeze gives deterministic-runtime samplers for gamma, beta, and all log-concave densities.","key_machinery":"The central object is a squeeze pair (r, Q) built from point evaluations of f on a grid centered at the mode: r uses inner grid values as a lower step function, Q uses outer grid values plus exponential tails as an upper envelope. The method samples from q = Q−r with probability A = ∫q and from r otherwise. For log-concave densities, the tail inequality f(x) ≤ f(m) exp(−(x−m)f(m)(1−exp(1−(x−m)f(m)))) keeps A below 1 for n = 7, δ = 2/5, giving a deterministic one-pass guarantee. For gamma, a four-piece envelope (two flats plus two exponential tails) plays the same role, with A < 1 for a ≥ 5; a representation A = E[φ(|N|/√(a−1))] removes the gamma function from the decision step for a ≥ 6.2829","core_discovery":"The central claim is that the acceptance-complement method, usually a special-purpose tool, can be made universal. For any log-concave density f with known mode m and a black-box evaluator of f, the paper builds a symmetric 16-interval grid around m, a lower step function r, and an upper envelope Q with 0 ≤ r ≤ f ≤ Q and ∫(Q−r) ≤ 1. One uniform draw then chooses between sampling from q = Q−r and sampling from r; both branches return an exact variate in one pass, no rejection loop. The bound on ∫q comes from a tail inequality for log-concave densities. The same machinery gives a loopless gamma generator for a ≥ 5, a gamma-function-free version for a ≥ 6.2829, and smaller shapes via G_a = U^{1","pith_inferences":["The paper leaves open the smallest universal partition size; testing grids with fewer than 16 intervals on parametric log-concave families could reveal a tighter constant.","The gamma-function-free trick—expressing a normalizing constant as an expectation over a simple random variable—may generalize to other densities with hard-to-compute normalizing constants, provided a bounded φ with E[φ(Z)] = A can be found.","If the tail inequality admits a sharper form, the grid could be coarsened, making the universal sampler faster; conversely, a counterexample to the inequality would force a redesign of the 16-interval envelope.","Because the algorithms are loopless, they are natural candidates for hardware or machine-code implementations, a consequence the paper notes but leaves undeveloped."],"forward_implications":["For any log-concave density, each generated variate costs one density evaluation plus bounded overhead, with 15 grid values precomputed once per density.","Gamma variates of shape a ≥ 5 are generated by a loopless algorithm when Γ(a) is available; for a ≥ 6.2829, no special-function evaluation is needed, and smaller shapes are exact via G_a = U^{1/a}G_{a+1}.","Beta, beta-prime, and variance-gamma variates become one-liners as deterministic functions of gamma and normal one-liners.","Batch simulation from log-concave densities becomes competitive with rejection samplers, because the 16-point table is built once and per-sample work is constant.","The same finite-partition construction extends to any unimodal density with known mode and explicit tail bounds, and to multimodal densities with known extrema."],"fun_headline_variants":["Deterministic-time sampling for all log-concave densities","One uniform draw, no rejection loop: universal acceptance-complement","16-interval grid yields exact samplers for gamma and beta","Loopless random variates for log-concave densities","Acceptance-complement goes universal for log-concave"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The bounded-time guarantee rests on the tail inequality f(x) ≤ f(m) exp(−(x−m)f(m)(1−exp(1−(x−m)f(m)))) for log-concave densities, whose proof is a terse extremal argument; if it fails, the 16-interval envelope's area can exceed 1, and separately the gamma algorithm for a ≥ 5 depends on an asserted inequality A < 1 that is stated without proof.","fun_headline_variants_meta":{"raw":{"variants":["Deterministic-time sampling for all log-concave densities","One uniform draw, no rejection loop: universal acceptance-complement","16-interval grid yields exact samplers for gamma and beta","Loopless random variates for log-concave densities","Acceptance-complement goes universal for log-concave"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00017,"raw_usage":{"total_tokens":1059,"prompt_tokens":652,"completion_tokens":407,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":396,"completion_tokens_details":{"reasoning_tokens":336}},"tokens_in":396,"tokens_out":407,"duration_ms":4313,"temperature":1.0,"reasoning_tokens":336,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T07:56:40.383421+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate both sides of the tail inequality numerically over a dense grid of (x−m)f(m) values for several log-concave densities (e.g., Laplace, logistic, gamma with shape just above 1) and look for a violation; equivalently, compute ∫q for the paper's grid with δ = 2/5, n = 7 on those densities and check whether it stays below 1. For the gamma claim, compute A in Eq. (2) for a = 5 and nearby values to verify A < 1, since the paper gives no derivation.","supporting_citations":[],"review_version":1}