Chinese restaurant process

For any positive integer ${\displaystyle n}$, let ${\displaystyle {\mathcal {P}}_{n}}$ denote the set of all partitions of the set ${\displaystyle \{1,2,3,...,n\}\triangleq [n]}$. The Chinese restaurant process takes values in the infinite Cartesian product ${\displaystyle \prod _{n\geq 1}{\mathcal {P}}_{n}}$.

The value of the process at time ${\displaystyle n}$ is a partition ${\displaystyle B_{n}}$ of the set ${\displaystyle [n]}$, whose probability distribution is determined as follows. At time ${\displaystyle n=1}$, the trivial partition ${\displaystyle B_{1}=\{\{1\}\}}$ is obtained (with probability one). At time ${\displaystyle n+1}$ the element "${\displaystyle n+1}$" is either:

1. added to one of the blocks of the partition ${\displaystyle B_{n}}$, where each block is chosen with probability ${\displaystyle |b|/(n+1)}$ where ${\displaystyle |b|}$ is the size of the block (i.e. number of elements), or
2. added to the partition ${\displaystyle B_{n}}$ as a new singleton block, with probability ${\displaystyle 1/(n+1)}$.

The random partition so generated has some special properties. It is exchangeable in the sense that relabeling ${\displaystyle \{1,...,n\}}$ does not change the distribution of the partition, and it is consistent in the sense that the law of the partition of ${\displaystyle [n-1]}$ obtained by removing the element ${\displaystyle n}$ from the random partition ${\displaystyle B_{n}}$ is the same as the law of the random partition ${\displaystyle B_{n-1}}$.

The probability assigned to any particular partition (ignoring the order in which customers sit around any particular table) is

${\displaystyle \Pr(B_{n}=B)={\frac {\prod _{b\in B}(|b|-1)!}{n!}},\qquad B\in {\mathcal {P}}_{n}}$

where ${\displaystyle b}$ is a block in the partition ${\displaystyle B}$ and ${\displaystyle |b|}$ is the size of ${\displaystyle b}$.

The definition can be generalized by introducing a parameter ${\displaystyle \theta >0}$ which modifies the probability of the new customer sitting at a new table to ${\displaystyle {\frac {\theta }{n+\theta }}}$ and correspondingly modifies the probability of them sitting at a table of size ${\displaystyle |b|}$ to ${\displaystyle {\frac {|b|}{n+\theta }}}$. The vanilla process introduced above can be recovered by setting ${\displaystyle \theta =1}$. Intuitively, ${\displaystyle \theta }$ can be interpreted as the effective number of customers sitting at the first empty table.

Chinese restaurant table

Parameters	${\displaystyle \theta >0}$ ${\displaystyle n\in \{1,2,\ldots \}}$
Support	${\displaystyle k\in \{1,2,\ldots ,n\}}$
PMF	${\displaystyle {\frac {\Gamma (\theta )}{\Gamma (n+\theta )}}|s(n,k)|\theta ^{k}}$
Mean	${\displaystyle \theta (\psi (\theta +n)-\psi (\theta ))}$ (see digamma function)

The Chinese restaurant table distribution (CRT) is the probability distribution on the number of tables in the Chinese restaurant process.[4] It can be understood as the sum of ${\displaystyle n}$ independent Bernoulli random variables, each with a different parameter:

${\displaystyle {\begin{aligned}K&=\sum _{i=1}^{n}b_{i}\\[4pt]b_{i}&\sim \operatorname {Bernoulli} \left({\frac {\theta }{i-1+\theta }}\right)\end{aligned}}}$

The probability mass function of ${\displaystyle K}$ is given by [5]

${\displaystyle f(k)={\frac {\Gamma (\theta )}{\Gamma (n+\theta )}}|s(n,k)|\theta ^{k},\quad k=1,\dots ,n,}$

where ${\displaystyle s}$ denotes Stirling numbers of the first kind.

This construction can be generalized to a model with two parameters, ${\displaystyle \theta }$ & ${\displaystyle \alpha }$,[2][6] commonly called the strength (or concentration) and discount parameters respectively. At time ${\displaystyle n+1}$, the next customer to arrive finds ${\displaystyle |B|}$ occupied tables and decides to sit at an empty table with probability

${\displaystyle {\frac {\theta +|B|\alpha }{n+\theta }},}$

or at an occupied table ${\displaystyle b}$ of size ${\displaystyle |b|}$ with probability

${\displaystyle {\frac {|b|-\alpha }{n+\theta }}.}$

In order for the construction to define a valid probability measure it is necessary to suppose that either ${\displaystyle \alpha <0}$ and ${\displaystyle \theta =-L\alpha }$ for some ${\displaystyle L\in \{1,2,,...\}}$; or that ${\displaystyle 0\leq \alpha <1}$ and ${\displaystyle \theta >-\alpha }$.

Under this model the probability assigned to any particular partition ${\displaystyle B}$ of ${\displaystyle [n]}$, in terms of the Pochhammer k-symbol, is

${\displaystyle \Pr(B_{n}=B)={\frac {(\theta +\alpha )_{|B|-1,\alpha }}{(\theta +1)_{n-1,1}}}\prod _{b\in B}(1-\alpha )_{|b|-1,1}}$

where, by convention, ${\displaystyle (a)_{0,c}=1}$, and for ${\displaystyle b>0}$

${\displaystyle (a)_{b,c}=\prod _{i=0}^{b-1}(a+ic)={\begin{cases}a^{b}&{\text{if }}c=0,\\\\{\dfrac {c^{b}\,\Gamma (a/c+b)}{\Gamma (a/c)}}&{\text{otherwise}}.\end{cases}}}$

Thus, for the case when ${\displaystyle \theta >0}$ the partition probability can be expressed in terms of the Gamma function as

${\displaystyle \Pr(B_{n}=B)={\frac {\Gamma (\theta )}{\Gamma (\theta +n)}}{\dfrac {\alpha ^{|B|}\,\Gamma (\theta /\alpha +|B|)}{\Gamma (\theta /\alpha )}}\prod _{b\in B}{\dfrac {\Gamma (|b|-\alpha )}{\Gamma (1-\alpha )}}.}$

In the one-parameter case, where ${\displaystyle \alpha }$ is zero, this simplifies to

${\displaystyle \Pr(B_{n}=B)={\frac {\Gamma (\theta )\,\theta ^{|B|}}{\Gamma (\theta +n)}}\prod _{b\in B}\Gamma (|b|).}$

Or, when ${\displaystyle \theta }$ is zero,

${\displaystyle \Pr(B_{n}=B)={\frac {\alpha ^{|B|-1}\,\Gamma (|B|)}{\Gamma (n)}}\prod _{b\in B}{\frac {\Gamma (|b|-\alpha )}{\Gamma (1-\alpha )}}.}$

As before, the probability assigned to any particular partition depends only on the block sizes, so as before the random partition is exchangeable in the sense described above. The consistency property still holds, as before, by construction.

If ${\displaystyle \alpha =0}$, the probability distribution of the random partition of the integer ${\displaystyle n}$ thus generated is the Ewens distribution with parameter ${\displaystyle \theta }$, used in population genetics and the unified neutral theory of biodiversity.

Animation of a Chinese restaurant process with scaling parameter ${\displaystyle \theta =0.5,\ \alpha =0}$. Tables are hidden once the customers of a table can not be displayed anymore; however, every table has infinitely many seats. (Recording of an interactive animation.[7])

The Chinese restaurant process is closely connected to Dirichlet processes and Pólya's urn scheme, and therefore useful in applications of Bayesian statistics including nonparametric Bayesian methods. The Generalized Chinese Restaurant Process is closely related to Pitman–Yor process. These processes have been used in many applications, including modeling text, clustering biological microarray data,[10] biodiversity modelling, and image reconstruction [11][12]

• Ewens sampling formula
• Preferential attachment
• Hilbert's paradox of the Grand Hotel

• Introduction to the Dirichlet Distribution and Related Processes by Frigyik, Kapila and Gupta
• A talk by Michael I. Jordan on the CRP:
  • http://videolectures.net/icml05_jordan_dpcrp/