Black-box constructions for exchangeable sequences of random multisets

Creighton Heaukulani; Daniel M. Roy

REVIEW 1 major objections 5 minor 4 references

Black-box constructions for exchangeable sequences of random multisets

T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Exchangeable Bernoulli processes directed by an unknown random base measure can be converted, black-box, into an exchangeable sequence of negative binomial processes with the same directing measure, for any r>0, without ever constructing…

desk verdict A clean black-box reduction from negative binomial to Bernoulli processes; the main theorems hold up, with two small blemishes that should be fixed but do not change the conclusions. read the letter →

arxiv 1908.06349 v1 pith:VALKCH4Z submitted 2019-08-17 math.PR stat.ML

Creighton Heaukulani , Daniel M. Roy This is my paper · ORCID

classification math.PRstat.ML MSC 60G5560G0960G57

keywords exchangeablesequencesnegativebinomialprocessBernoullirandommultisetsurnschemecompletelymeasuresIndianbuffetBayesiannonparametrics

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 proves a black-box construction: from any exchangeable array of Bernoulli processes (random point processes whose atoms carry mass 0 or 1) directed by a random base measure B whose atoms all have mass less than one, it produces an exchangeable sequence of point processes that, conditioned on B, are independent negative binomial processes NBP(r,B). The construction never represents B explicitly, and if B has finite total mass, each output multiset is almost surely determined by finitely many atoms from a prefix of the input array, so exact simulation is possible even for base measures with countably infinite support. This gives a uniform way to sample random multisets in Bayesian nonparametric models, where previous exact constructions were tailored to specific base measures such as the beta process. The method composes with known constructions of exchangeable Bernoulli processes for beta processes, generalized beta processes, and hierarchies, yielding exact negative binomial process samplers for all of them.

What carries the argument

The negative binomial urn scheme (Definition 3.1) is the central object: given an array (Y_{n,m}) of Bernoulli processes, it forms Y_n as the union of the supports of the first ⌈r⌉ rows and assigns to each atom the count of Bernoulli successes before r failures (integer case), or the output of the negative binomial factory (Algorithm 4.1) for general r>0. The negative binomial factory is a rejection sampler whose proposal is NB(⌈r⌉,p), accepted with probability (r)_W/(⌈r⌉)_W; for the diffuse part of the base measure the argument uses the fact that the ordinary components of the input processes are independent Poisson processes whose supports are almost surely disjoint, so the rejection step reduces to a Poisson thinning that multiplies the intensity by r/⌈r⌉. The proof works through the Laplace functional (2.6), using Lemma A.1 to identify each fixed-atom mass as NB(r,B{s}) and the thinning calculation to identify the diffuse part as a Poisson process of intensity r times the diffuse component of B.

What would settle it

Take B with a single atom of mass p in (0,1) and no diffuse part, simulate the integer-r urn scheme from an exchangeable Bernoulli array directed by B, and compare the empirical distribution of X_1 at that atom to NB(r,p): a mismatch at any p would disprove Theorem 3.1. A sharper check is to add a diffuse component and test whether the ordinary part of X_1 is Poisson with intensity r times the diffuse part; if the Bernoulli inputs are modified so their ordinary components ever coincide, that Poisson character should fail, exposing the reliance on disjoint supports.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.1 (integer r) and Theorem 4.1 (any r>0): if B is a random element of M0, the space of measures whose atoms are all <1, and (Y_{n,m}) is an exchangeable array of Bernoulli processes directed by B, then the negative binomial urn scheme outputs a sequence (X_n) that is conditionally i.i.d. NBP(r,B). For integer r, each X_n{γ} at an atom γ is the number of successes before r failures in the Bernoulli trials Y_{n,1}{γ}, Y_{n,2}{γ},...; for non-integer r, a rejection sampler called the negative binomial factory proposes NB(⌈r⌉,p) variates from the same Bernoulli stream and accepts with probability (r)_W/(⌈r⌉)_W. The proof shows that the Laplace functional of X_n equals the NBP(r,B) functional of Proposition 2.1: fixed atoms independently receive NB(r,B{s}) masses, and the union of the diffuse ordinary parts, after the rejection step, is thinned to a Poisson process with intensity r times the diffuse part of B. Therefore the scheme extracts the negative binomial process directly from Bernoulli-process inputs, for any base measure in M0 that admits an exchangeable Bernoulli-process representation.

Load-bearing premise

The load-bearing premise is that B lies in M0, so every atom of B has mass strictly less than 1, and that the input Bernoulli processes have the standard complete-random decomposition with a diffuse Poisson ordinary component; if an atom had mass 1, the 'count before r failures' would never terminate, and if the ordinary components could share atoms, the Poisson thinning step would break.

Editorial extensions

If this is right

For any random base measure with atoms <1 that admits an exchangeable Bernoulli process construction, one obtains an exact finitary sampler for the corresponding negative binomial process, without truncating the support of B.
Applying the scheme to known Bernoulli-process constructions yields NBP samplers for beta processes, stable beta processes, Gibbs-type beta processes, and arbitrarily deep hierarchies of these.
The construction never represents B explicitly, so it removes the need for MCMC subroutines that correct for truncation in stick-breaking or inverse Lévy representations.
The finite-termination guarantee holds whenever B has finite total mass, meaning each output X_n is almost surely determined by a finite prefix of the input array.

Reading between the lines

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

The rejection sampler in Algorithm 4.1 is effectively a Bernoulli factory for the negative binomial distribution; if used as a subroutine in a larger exact sampling scheme, its expected iteration count (1-p)^{⌈r⌉-r} suggests runtimes become sensitive when atoms have success probability p close to 1.
The a.s. disjointness of the ordinary components is what makes the diffuse part work; this suggests a robustness condition for implementation: if the input Bernoulli processes are not exactly Poisson in their ordinary parts (e.g., numerical approximations that share atoms), the resulting process may deviate from NBP(r,B) in a way concentrated on the diffuse component.
Because the construction is black-box in B, it may be combined with future Bernoulli-process constructions for new base measures beyond the beta/generalized-beta families; the only requirement is an exchangeable Bernoulli sequence, not a completely random or purely atomic B.

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.

Desk Editor's Note

read the letter

Read Heaukulani and Roy (1908.06349). The headline: they give a construction that turns any exchangeable array of Bernoulli processes directed by a random base measure B (atoms <1) into an exchangeable sequence of negative binomial processes directed by the same B, for any r>0. The construction never represents B explicitly and is finitary when B has finite total mass. The integer-r case is the natural idea—take the union of supports of r Bernoulli processes and count successes before r failures—and the r>0 case adds a rejection sampler (a 'negative binomial factory') whose acceptance probability is independent of p. Both are proved correctly.

What's genuinely new: the earlier Heaukulani-Roy construction was tied to beta process base measures; this one is black-box, so it immediately applies to stable beta, Gibbs-type beta, and hierarchies, whatever classes already have Bernoulli process constructions. That is a real methodological advance for Bayesian nonparametrics, even if the mathematical ingredients are standard.

The main theorems are sound. Theorem 3.1's conditioning argument is the right one: fixed atoms reduce to i.i.d. Bernoulli trials; the diffuse part is a sum/thinning of independent Poisson processes. Theorem 4.1's thinning computation is also correct: each diffuse atom is retained with probability r/⌈r⌉, giving intensity r B_tilde. I checked the Laplace functional and the support/union argument; no load-bearing flaw.

Soft spots, in ascending order of importance:

- Lemma 4.1 states the expected number of iterations is (1−p)^{⌈r⌉−r}. That is the acceptance probability, not the expected number of proposals; the correct mean is its reciprocal, (1−p)^{r−⌈r⌉}. The proof repeats the inversion when it says R+1 has mean 1/k. This is a performance claim, not a distributional one, so Theorem 4.1's output law is unaffected. Still, it should be corrected.

- Theorem 4.1's proof says for s in the support of the union, 'only one entry is one' from the empty intersection of supports. That conclusion needs the pairwise disjointness of independent diffuse Poisson processes, which is true but unstated. Minor.

- Theorem 3.2 is asserted as a straightforward consequence; there is no proof. For a math.PR paper, that is acceptable but a bit thin.

- The text contains a stray '/suppress' before Latuszyński's name in two places (and in the acknowledgements). Presumably a LaTeX artifact; should be cleaned.

None of these threaten the central results. The paper has no code or experiments, but it is a construction paper; reproducibility is at the methods level, and the proofs are checkable.

Who is this for? Bayesian nonparametrics people who want exact simulation of negative binomial processes with non-beta base measures, and probabilists interested in exchangeable constructions. It deserves a serious referee.

My recommendation: send it to review. The main theorems are correct and the contribution is modest but real. The referee should ask for the Lemma 4.1 fix and a one-line clarification on the disjointness.

Referee Report

1 major / 5 minor

Summary. The paper develops black-box constructions for exchangeable sequences of random multisets. Given an exchangeable array of Bernoulli processes directed by a random base measure B in M0, the authors construct a sequence (X_n) that is conditionally i.i.d. negative binomial process with parameter r and base measure B. Theorem 3.1 covers positive integer r by a 'negative binomial urn scheme' in which counts are generated as successes before r failures from the input Bernoulli processes. Theorem 4.1 extends the construction to any r>0 by adding a rejection-sampling subroutine called a negative binomial factory. The algorithms never represent B explicitly, and are finitary when B has finite total mass. Applications to beta processes, hierarchies of beta processes, and generalized beta processes are discussed.

Significance. If the results are correct, the paper gives a genuinely useful reduction: any finitary construction of an exchangeable sequence of Bernoulli processes directed by a random base measure can be converted, in a black-box way, into a finitary construction of exchangeable negative binomial processes directed by the same base measure. This covers several popular Bayesian nonparametric models and avoids the inexact truncations of stick-breaking or inverse-Levy methods. The integer-r construction is clean and the Poisson-superposition/thinning reasoning is elegant. The r>0 extension is more delicate and, in its current form, needs an important clarification in the proof.

major comments (1)

[Section 4, Algorithm 4.1 and proof of Theorem 4.1, Eqs. (4.7)-(4.8)] The proof of the ordinary component in Theorem 4.1 is incomplete and relies on an implicit convention about how the rejection-sampling iterations consume the input p-coin sequence. As written, Algorithm 4.1 says only 'Simulate W_k ~ NB(⌈r⌉,p) with p-coins'; it does not state that each proposal uses a fresh disjoint block of the infinite sequence. Under the natural reading that W_k is computed from the same infinite sequence, in the diffuse case W_k=1 for every k, so the loop would always terminate with output 1, and the sentence 'otherwise it outputs \bar X_{n,j}=0 a.s.' would be false; the claimed Poisson thinning to intensity r\tilde H_0 would fail. Please specify explicitly that each proposal consumes a fresh block of the input sequence, and add the missing argument: after a rejected W_1=1, the next block contains no success, so W_2=0 and is accepted with probability 1. This is the load-bearing step for Theorem 4.1.

minor comments (5)

[Section 4, Lemma 4.1] The stated expected number of iterations is the reciprocal of the correct value. For the rejection sampler with proposal NB(⌈r⌉,p) and target NB(r,p), the constant is k=(1-p)^{r-⌈r⌉}, and the mean number of iterations is k. Accordingly, in the proof, R+1 has mean k, not 1/k. The output distribution in Lemma 4.1 is unaffected, but the expectation claim should be corrected.
[Section 2.2, Eq. (2.2)] The constants \bar b_s are said to lie in (0,1], but the definition of M0 requires atoms to be strictly less than one. Since the constructions require p<1 for the negative binomial counts to be finite, the interval should be (0,1) (or the definition of M0 should be reconciled with the notation).
[Section 4, proof of Theorem 4.1] The condition ∩_m supp(\tilde Y_{n,m}) = ∅ is weaker than the claimed conclusion that only one entry of the sequence \tilde Y_{n,1}{s}, \tilde Y_{n,2}{s}, ... equals one; what is needed is the pairwise disjointness of the supports of independent diffuse Poisson processes. This is a standard fact, but it should be stated and cited rather than left implicit.
[Section 4, Algorithm 4.1 and Eq. (4.4)] The algorithm should define explicitly how the input p-coin sequence is consumed (fresh block per iteration, consumed sequentially). Also, Eq. (4.4) contains a typo: '( X)n∈N' should be '(X_n)_{n∈N}'.
[Section 4, Theorem 4.1 statement] The statement 'Theorem 3.1 holds with this construction' is informal; it should be replaced by an explicit statement of the conclusion, namely that conditioned on B the (X_n) are i.i.d. NBP(r,B).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the negative binomial urn scheme is a direct, self-contained distributional reduction from Bernoulli processes to negative binomial processes.

full rationale

Score 0. Theorems 3.1 and 4.1 are constructive reductions, not tautologies. Definition 2.1 defines NBP(r, B0) by fixed NB(r, bbar_s) atoms and a Poisson(r Btilde0) ordinary component; Definition 2.2 defines BeP(B0) with Bernoulli(bbar_s) fixed atoms and a Poisson(Btilde0) ordinary component. The negative binomial urn scheme (Section 3) maps the BeP array to an NBP sequence using two textbook facts: Lemma A.1, which derives the NB(r,p) pmf (2.3) from the successes-before-r-failures count of i.i.d. Bernoulli(p) trials, and the superposition of independent Poisson processes. Neither fact presupposes the conclusion; the proof computes the Laplace functional of X_n and matches (2.6). The r > 0 extension is a genuine Bernoulli-factory-style rejection sampler: NB(ceil(r), p) is simulated from p-coins and accepted with probability (r)_W / (ceil(r))_W, and the diffuse-component thinning uses retention probability r/ceil(r) to turn a Poisson process of intensity ceil(r) Htilde0 into one of intensity r Htilde0. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported to forbid alternatives. Self-citations (Roy 2014 for the one-parameter process; Heaukulani and Roy 2016 for the earlier beta-process construction) are used as inputs or for background examples, not as the load-bearing argument. Minor proof slips—the stated expected iterations in Lemma 4.1 is the reciprocal of the correct mean, and Theorem 4.1's proof says W_k = 0 for k >= 2 where in fact W_k = 1—are correctness issues, not circularity.

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

The derivation is self-contained given standard point process machinery. No constants are fitted to data; r and the concentration function c are user-specified model parameters, not estimated. The only nonstandard input is the assumed availability of Bernoulli-process exchangeable sequences, which is the explicit premise of the black-box method.

assumptions (6)

standard math Complete random measures decompose into diffuse, fixed, and ordinary Poisson components (Eq. 2.1).
The Bernoulli and negative binomial process definitions are built on this decomposition.
standard math Disintegration theorem (Kallenberg 2002, Thm. 6.4) allows evaluating conditional Laplace functionals by integrating against the product Bernoulli process law.
Used in the proof of Theorem 3.1 at Eq. 3.4.
standard math Negative binomial variables add over r and can be generated as successes before r failures from i.i.d. Bernoulli trials (Prop. A.1, Lemma A.1).
This is the fixed-atom part of the construction.
standard math Superposition and thinning of Poisson processes.
Used in Theorems 3.1 and 4.1 for the diffuse component of the base measure.
domain assumption Input assumption: an exchangeable array of Bernoulli processes directed by B exists and is available (Section 2.5, Theorems 3.1, 4.1).
This is the explicit premise of the black-box method; the paper does not construct B itself.
domain assumption Base measures are restricted to M0, so atoms have mass less than 1 (Section 2.2).
This ensures every Bernoulli trial has success probability p<1 and the negative binomial count terminates almost surely.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Black-box constructions for exchangeable sequences of random multisets." pith.science (2026). https://pith.science/paper/VALKCH4Z

@misc{pith2026190806349,
  author       = {Pith},
  title        = {Pith review of: Black-box constructions for exchangeable sequences of random multisets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VALKCH4Z}},
  note         = {Machine review of arXiv:1908.06349}
}

read the original abstract

We develop constructions for exchangeable sequences of point processes that are rendered conditionally-i.i.d. negative binomial processes by a (possibly unknown) random measure called the base measure. Negative binomial processes are useful in Bayesian nonparametrics as models for random multisets, and in applications we are often interested in cases when the base measure itself is difficult to construct (for example when it has countably infinite support). While a finitary construction for an important case (corresponding to a beta process base measure) has appeared in the literature, our constructions generalize to any random base measure, requiring only an exchangeable sequence of Bernoulli processes rendered conditionally-i.i.d. by the same underlying random base measure. Because finitary constructions for such Bernoulli processes are known for several different classes of random base measures--including generalizations of the beta process and hierarchies thereof--our results immediately provide constructions for negative binomial processes with a random base measure from any member of these classes.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

[22]

Teh, Y. W., D. G¨ or¨ ur, and Z. Ghahramani. 2007.Stick-breaking construction for the Indian buﬀet process, Proceedings of the 11th international conference on artiﬁ cial intelligence and statistics. Thibaux, R

work page 2007
[1998]

Simulation of L´ evy random ﬁelds, Practical nonparametric and semiparametric Bayesian statistics, pp. 227–242. 12 CREIGHTON HEAUKULANI AND DANIEL M. ROY Zhou, M., L. Hannah, D. Dunson, and L. Carin. 2012.Beta-negative binomial process and Poisson factor analysis , Proceedings of the 15th international conference on artiﬁ cial intelligence and statistics....

work page 2012
[2014]

The continuum-of-urns scheme, generalized beta and indian buﬀet processes, and hierarchies thereof, arXiv:1501.00208 [math.PR]. Teh, Y. W. and D. G¨ or¨ ur. 2009.Indian buﬀet processes with power-law behavior , Advances in neural information processing systems

work page Pith review arXiv 2009
[2019]

Advanced publication: https://projecteuclid.org/euclid.ba/1560909812

Gibbs-type Indian buﬀet processes , Bayesian Analysis (To Appear). Advanced publication: https://projecteuclid.org/euclid.ba/1560909812. Hjort, N. L

work page arXiv

Pith tools

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

[1] [22]

Teh, Y. W., D. G¨ or¨ ur, and Z. Ghahramani. 2007.Stick-breaking construction for the Indian buﬀet process, Proceedings of the 11th international conference on artiﬁ cial intelligence and statistics. Thibaux, R

work page 2007

[2] [1998]

Simulation of L´ evy random ﬁelds, Practical nonparametric and semiparametric Bayesian statistics, pp. 227–242. 12 CREIGHTON HEAUKULANI AND DANIEL M. ROY Zhou, M., L. Hannah, D. Dunson, and L. Carin. 2012.Beta-negative binomial process and Poisson factor analysis , Proceedings of the 15th international conference on artiﬁ cial intelligence and statistics....

work page 2012

[3] [2014]

The continuum-of-urns scheme, generalized beta and indian buﬀet processes, and hierarchies thereof, arXiv:1501.00208 [math.PR]. Teh, Y. W. and D. G¨ or¨ ur. 2009.Indian buﬀet processes with power-law behavior , Advances in neural information processing systems

work page Pith review arXiv 2009

[4] [2019]

Advanced publication: https://projecteuclid.org/euclid.ba/1560909812

Gibbs-type Indian buﬀet processes , Bayesian Analysis (To Appear). Advanced publication: https://projecteuclid.org/euclid.ba/1560909812. Hjort, N. L

work page arXiv