Chinese restaurant process

From Wikipedia, the free encyclopedia

This article is not about the Chinese restaurant syndrome.

In probability theory, the Chinese restaurant process is a discrete-time stochastic process, whose value at any positive-integer time n is a partition B_n of the set {1, 2, 3, ..., n} whose probability distribution is determined as follows. At time n + 1 the element n + 1 is either added to one of the blocks of the partition B_n, each block being chosen with a probability proportional to its size, or added to the partition B_n as a new singleton block, with probability $θ / (n + θ)$ , where $θ$ is a positive parameter that remains constant over time.

One fancifully imagines a Chinese restaurant with an infinite number of tables, each with infinite capacity. Each new customer either sits at a table that is already occupied, with probability proportional to the number of customers already sitting at that table, or sits alone at a table not yet occupied, with probability $θ / (n + θ)$ , where n is how many customers were already in the restaurant. (For an account of the custom in actual Chinese restaurants, see table sharing.)

For any partition B of the set

[n] = {1, 2, 3, ..., n},

let |B| be the number of "blocks" or "parts", let b ∈ B indicate that b is one of the blocks, and let |b| be the number of members of the block b. Then we have

$\Pr(B_n = B) = {\theta^{|B|} \Gamma(\theta) \prod_{b\in B}\Gamma(|b|) \over \Gamma(n + \theta)}$

$= {\theta^{|B| } \over \theta(\theta+1)(\theta+2)\cdots(\theta+n-1)} \prod_{b \in B} (|b| - 1)!,$

where Γ is the Gamma function. The following paragraphs describe one way to derive this partition probability.

First, let $c i$ be the index for the $i t h$ block. Then we have

$\Pr(c_i|c_1,\ldots,c_{i-1}) = \frac{\theta \delta(c_i \in \textrm{new} \;\; \textrm{block}) + \sum_{b \in B} |b| \delta(c_i \in b )}{\theta + i-1} = \frac{ \theta^{\delta(c_i \in \; \textrm{new} \;\; \textrm{block})} \prod_{b \in B} |b|^{\delta(c_i \in b)}}{\theta + i-1}$

$\Pr(c_1,\ldots,c_n) = \Pr(c_1)\prod_{i=2}^n \Pr(c_i|c_1,\ldots,c_{i-1})$

where $\delta(\cdot)$ is an indicator function.

Now consider the size of block b: it increases by 1 each time we add one element into it. When the last element in block b is to be added in, the block size is (|b| − 1). For example, consider this sequence of choices: (generate a new block b)(join b)(join b)(join b). In the end, block b has 4 elements and the product of the numerators in the above equation gets $θ * 1 * 2 * 3$ . Following this logic, we obtain $\Pr(B_n = B)$ as above.

The probability distribution of the random partition of the integer n thus generated is the Ewens distribution with parameter θ, used in population genetics.

The Chinese restaurant process is closely connected to Dirichlet processes and Polya's urn scheme. They are nonparametric Bayesian methods. They have been used in many applications, including modeling text, clustering biological microarray data, and detecting objects in images.