arXiv:1801.00513v2 [] 3 Jan 2018

An elementary derivation of the Chinese restaurant
process from Sethuraman’s stick-breaking process
Jeffrey W. Miller∗
Harvard University, Department of Biostatistics
January 4, 2018

Abstract
The Chinese restaurant process and the stick-breaking process are the two most
commonly used representations of the Dirichlet process. However, the usual proof of
the connection between them is indirect, relying on abstract properties of the Dirichlet
process that are difficult for nonexperts to verify. This short note provides a direct proof
that the stick-breaking process gives rise to the Chinese restaurant process, without
using any measure theory.

1

Introduction

Sethuraman (1994) showed that the Dirichlet process has the following stick-breaking repQk−1
iid
(1 − vi ) for k = 1, 2, . . ., and
resentation: if v1 , v2 , . . . ∼ Beta(1, α), πk = vk i=1
iid

θ1 , θ2 , . . . ∼ H, then the random discrete measure
P =

∞
X

πk δθk

(1)

k=1

is distributed according to the Dirichlet process DP(α, H) with concentration parameter α
and base distribution H. This representation has been instrumental in the development of
many nonparametric models (MacEachern, 1999, 2000; Hjort, 2000; Ishwaran and Zarepour,
2000; Ishwaran and James, 2001; Griffin and Steel, 2006; Dunson and Park, 2008; Chung
and Dunson, 2009; Rodriguez and Dunson, 2011; Broderick et al., 2012), has facilitated the
understanding of these models (Favaro et al., 2012; Teh et al., 2007; Thibaux and Jordan,
2007; Paisley et al., 2010), and is central to various inference algorithms (Ishwaran and James,
2001; Blei and Jordan, 2006; Papaspiliopoulos and Roberts, 2008; Walker et al., 2007; Kalli
et al., 2011).
The author gratefully acknowledges support from the National Science Foundation (NSF) grant DMS1045153 and the National Institutes of Health (NIH) grant 5R01ES017436.
∗

1

It is well-known that, as shown by Antoniak (1974), the Dirichlet process induces a
distribution on partitions as follows: if P ∼ DP(α, H) where H is nonatomic (i.e., H({θ}) =
iid
0 for any θ), x1 , . . . , xn |P ∼ P , and C is the partition of {1, . . . , n} induced by x1 , . . . , xn ,
then
P(C = C) =

α|C| Γ(α) Y
Γ(|c|).
Γ(α + n) c∈C

(2)

The sequential sampling process corresponding to this partition distribution is known as the
Chinese restaurant process, or Blackwell–MacQueen urn process.
The following key fact is a direct consequence of these two results (Sethuraman’s and
iid
Antoniak’s): if π = (π1 , π2 , . . .) is defined as above, z1 , . . . , zn |π ∼ π, and C is the partition
induced by z1 , . . . , zn , then the distribution of C is given by Equation 2. This can be seen
by noting that when H is nonatomic, the distribution of C is the same as when it is induced
by x1 , . . . , xn |P .
While this key fact follows directly from the results of Sethuraman and Antoniak, the
proofs of their results are rather abstract and are not easy to verify, especially for those
without expertise in measure theory. The purpose of this note is to prove this important
connection between the Chinese restaurant process and the stick-breaking process using only
elementary, non-measure-theoretic arguments. Our proof is completely self-contained and
does not rely on any properties of the Dirichlet process.
In previous work, Paisley (2010) showed by elementary calculations that if the base
distribution H is a discrete distribution on {1, . . . , K}, and P is defined by the stick-breaking
process as in Equation 1, then (P (1), . . . , P (K)) ∼ Dirichlet(αH(1), . . . , αH(K)) (providing
a direct non-measure-theoretic proof of this well-known property). Thus, despite the similar
sounding title of the article by Paisley (2010), the result shown there is altogether different
from what we show here.

2

Main result

We use [n] to denote the set {1, . . . , n}, and N to denote {1, 2, 3, . . .}. As is standard, we
represent
St a partition of [n] as a set C = {c1 , . . . , ct } of nonempty disjoint sets c1 , . . . , ct such
that i=1 ci = [n]. Thus, t = |C| is the number of parts in the partition, and |c| is the
number of elements in a given part c ∈ C. We say that C is the partition of [n] induced by
z1 , . . . , zn if it has the property that for any i, j ∈ [n], i and j belong to the same part c ∈ C
if and only if zi = zj . We use bold font to denote random variables.
Theorem 2.1. Suppose
iid

v1 , v2 , . . . ∼ Beta(1, α)
πk = vk

k−1
Y

(1 − vi ) for k = 1, 2, . . . ,

i=1

iid

z1 , . . . , zn |π = π ∼ π, that is, P(zi = k | π) = πk ,
2

and C is the partition of [n] induced by z1 , . . . , zn . Then
P(C = C) =

α|C| Γ(α) Y
Γ(|c|).
Γ(n + α) c∈C

Our proof of the theorem relies on the following lemmas. Let us abbreviate z =
(z1 , . . . , zn ). Given z ∈ Nn , let Cz denote the partition [n] induced by z.
Lemma 2.2. For any z ∈ Nn ,
m
 Y
Γ(α)  Y
α 
P(z = z) =
Γ(|c| + 1)
Γ(n + α) c∈C
gk + α
k=1

z

where m = max{z1 , . . . , zn } and gk = #{i : zi ≥ k}.
The proofs of the lemmas will be given in Section 3. We use 1(·) to denote the indicator
function, that is, 1(E) = 1 if E is true, and 1(E) = 0 otherwise.
Lemma 2.3. For any partition C of [n],
m(z)
Y
X
α
α|C|
Q
1(Cz = C)
=
gk (z) + α
c∈C |c|
k=1
z∈Nn

where m(z) = max{z1 , . . . , zn } and gk (z) = #{i : zi ≥ k}.
Proof of Theorem 2.1.
X
P(C = C | z = z)P(z = z)
P(C = C) =
z∈Nn

 m(z)

Y
α
Γ(α)  Y
Γ(|c| + 1)
1(Cz = C)
=
Γ(n + α) c∈C
gk (z) + α
k=1
z∈Nn

(a)

X

z

 m(z)
X

Y
α
Γ(α)  Y
1(Cz = C)
=
Γ(|c| + 1)
Γ(n + α) c∈C
gk (z) + α
z∈Nn
k=1
 α|C|
Γ(α)  Y
(b)
=
Γ(|c| + 1) Q
Γ(n + α) c∈C
c∈C |c|

Γ(α)  Y
(c)
=
Γ(|c|) α|C|
Γ(n + α) c∈C
where (a) is by Lemma 2.2, (b) is by Lemma 2.3, and (c) is since Γ(|c| + 1) = |c|Γ(|c|).

3

3

Proofs of lemmas

Proof of Lemma 2.2. Letting ek = #{i : zi = k}, we have
P(z = z | π1 , . . . , πm ) =

n
Y

πzi =

i=1

m
Y

πkek

k=1

and thus
m 
m
ek Y
Y
Qk−1
P(z = z | v1 , . . . , vm ) =
vkek (1 − vk )fk
=
vk i=1 (1 − vi )
k=1

k=1

where fk = #{i : zi > k}. Therefore,
Z
P(z = z) = P(z = z | v1 , . . . , vm )p(v1 , . . . , vm )dv1 · · · dvm
Z Y
m

=
vkek (1 − vk )fk p(v1 ) · · · p(vm )dv1 · · · dvm
k=1

=
(a)

=

=

m Z
Y

k=1
m
Y

k=1
m
Y

k=1
m
Y

vkek (1 − vk )fk p(vk )dvk

αB(ek + 1, fk + α)
αΓ(ek + 1)Γ(fk + α)
Γ(ek + fk + α + 1)

αΓ(ek + 1)Γ(gk+1 + α)
Γ(gk + α + 1)
k=1
m
m
m
Y
 Y
α  Y Γ(gk+1 + α) 
(c)
=
Γ(ek + 1)
gk + α k=1 Γ(gk + α)
k=1
k=1
m
 Y
Y
α  Γ(α)
Γ(|c| + 1)
=
gk + α Γ(n + α)
c∈C
k=1
(b)

=

z

where step (a) holds since
Z
B(r + 1, s + α)
= αB(r + 1, s + α),
xr (1 − x)s Beta(x|1, α)dx =
B(1, α)
step (b) since fk = gk+1 and gk = ek + fk , and step (c) since Γ(x + 1) = xΓ(x).
Let St denote the set of t! permutations of [t].
Lemma 3.1. For any n1 , . . . , nt ∈ N,
X
σ∈St

1
1
=
a1 (σ) · · · at (σ)
n1 · · · nt

where ai (σ) = nσi + nσi+1 + · · · + nσt .
4

Proof. Consider an urn containing t balls of various sizes—specifically, suppose the balls
are labeled 1, . . . , t and have sizes n1 , . . . , nt . Consider the process of sampling without
replacement t times from the urn, supposing that the probability of drawing any given ball
is proportional
Pt to its size. This defines a distribution on permutations σ ∈ St such that,
letting n = i=1 ni ,
nσ1
nσ1
=
,
n
a1 (σ)
nσ2
nσ2
,
=
p(σ2 |σ1 ) =
n − nσ1
a2 (σ)
nσ3
nσ3
p(σ3 |σ1 , σ2 ) =
,
=
n − nσ1 − nσ2
a3 (σ)
p(σ1 ) =

and so on. Therefore, since nσ1 · · · nσt = n1 · · · nt ,
n1 · · · nt
.
(3)
a1 (σ) · · · at (σ)
P
Since p(σ) is a distribution on St by construction, we have σ∈St p(σ) = 1; applying this to
Equation 3 and dividing both sides by n1 · · · nt gives the result.
p(σ) = p(σ1 )p(σ2 |σ1 ) · · · p(σt |σ1 , . . . , σt−1 ) =

Proof of Lemma 2.3. Let t = |C|, and suppose c1 , . . . , ct are the parts of C. For σ ∈ St ,
define ai (σ) = |cσi | + · · · + |cσt |. For any z ∈ Nn such that Cz = C, if k1 < · · · < kt are the
distinct values taken on by z1 , . . . , zn , then
m(z)

Y

k=1

kt −kt−1
k1 
k2 −k1


α
α
α
α
···
=
gk (z) + α
gk1 (z) + α
gk2 (z) + α
gkt (z) + α
d1 
d2

dt

α
α
α
···
=
a1 (σ) + α
a2 (σ) + α
at (σ) + α

where di = ki −ki−1 , with k0 = 0, and σ is the permutation of [t] such that cσi = {j : zj = ki }.
Note that the definition of d = (d1 , . . . , dt ) and σ sets up a one-to-one correspondence (that
is, a bijection) between {z ∈ Nn : Cz = C} and {(σ, d) : σ ∈ St , d ∈ Nt }. Therefore,
m(z)

X

z∈Nn

1(Cz = C)

Y

k=1

t 
di
X XY
α
α
=
gk (z) + α σ∈S
ai (σ) + α
t i=1
d∈N
t
Y

X

t
XY

α
ai (σ)

t

=

X

σ∈St i=1 di ∈N
(a)

=

(b)

σ∈St i=1
t

= Qt

α

i=1

where step (a) follows from the geometric series,
step (b) is by Lemma 3.1.
5

P∞

k=1

|ci |

di
α
ai (σ) + α

=Q

αt

c∈C

|c|

xk = 1/(1 − x) − 1 for x ∈ [0, 1), and

References
C. E. Antoniak. Mixtures of Dirichlet processes with applications to Bayesian nonparametric
problems. The Annals of Statistics, 2(6):1152–1174, 1974.
D. M. Blei and M. I. Jordan. Variational inference for Dirichlet process mixtures. Bayesian
Analysis, 1(1):121–143, 2006.
T. Broderick, M. I. Jordan, and J. Pitman. Beta processes, stick-breaking and power laws.
Bayesian Analysis, 7(2):439–476, 2012.
Y. Chung and D. B. Dunson. Nonparametric Bayes conditional distribution modeling with
variable selection. Journal of the American Statistical Association, 104(488), 2009.
D. B. Dunson and J.-H. Park. Kernel stick-breaking processes. Biometrika, 95(2):307–323,
2008.
S. Favaro, A. Lijoi, and I. Pruenster. On the stick-breaking representation of normalized
inverse Gaussian priors. Biometrika, 99(3):663–674, 2012.
J. E. Griffin and M. J. Steel. Order-based dependent Dirichlet processes. Journal of the
American Statistical Association, 101(473):179–194, 2006.
N. L. Hjort. Bayesian analysis for a generalised Dirichlet process prior. Technical Report,
University of Oslo, 2000.
H. Ishwaran and L. F. James. Gibbs sampling methods for stick-breaking priors. Journal of
the American Statistical Association, 96(453), 2001.
H. Ishwaran and M. Zarepour. Markov chain Monte Carlo in approximate Dirichlet and beta
two-parameter process hierarchical models. Biometrika, 87(2):371–390, 2000.
M. Kalli, J. E. Griffin, and S. G. Walker. Slice sampling mixture models. Statistics and
Computing, 21(1):93–105, 2011.
S. N. MacEachern. Dependent nonparametric processes. In ASA Proceedings of the Section
on Bayesian Statistical Science, pages 50–55, 1999.
S. N. MacEachern. Dependent Dirichlet processes. Unpublished manuscript, Department of
Statistics, The Ohio State University, 2000.
J. Paisley. A simple proof of the stick-breaking construction of the Dirichlet Process. Technical report, Princeton University, Department of Computer Science, August 2010.
J. W. Paisley, A. K. Zaas, C. W. Woods, G. S. Ginsburg, and L. Carin. A stick-breaking
construction of the beta process. In Proceedings of the 27th International Conference on
Machine Learning, pages 847–854, 2010.
O. Papaspiliopoulos and G. O. Roberts. Retrospective Markov chain Monte Carlo methods
for Dirichlet process hierarchical models. Biometrika, 95(1):169–186, 2008.
6

A. Rodriguez and D. B. Dunson. Nonparametric Bayesian models through probit stickbreaking processes. Bayesian Analysis, 6(1), 2011.
J. Sethuraman. A constructive definition of Dirichlet priors. Statistica Sinica, 4:639–650,
1994.
Y. W. Teh, D. Görür, and Z. Ghahramani. Stick-breaking construction for the Indian buffet
process. In International Conference on Artificial Intelligence and Statistics, pages 556–
563, 2007.
R. Thibaux and M. I. Jordan. Hierarchical beta processes and the Indian buffet process. In
International Conference on Artificial Intelligence and Statistics, pages 564–571, 2007.
S. G. Walker, A. Lijoi, and I. Prünster. On rates of convergence for posterior distributions
in infinite-dimensional models. The Annals of Statistics, 35(2):738–746, 2007.

7

