Chinese restaurant process

In probability theory, the Chinese restaurant process is a discrete-time stochastic process, analogous to seating customers at tables in a restaurant.
Imagine a restaurant with an infinite number of circular tables, each with infinite capacity. Customer 1 sits at the first table. The next customer either sits at the same table as customer 1, or the next table. This continues, with each customer choosing to either sit at an occupied table with a probability proportional to the number of customers already there (i.e., they are more likely to sit at a table with many customers than few), or an unoccupied table. At time n, the n customers have been partitioned among m ≤ n tables (or blocks of the partition). The results of this process are exchangeable, meaning the order in which the customers sit does not affect the probability of the final distribution. This property greatly simplifies a number of problems in population genetics, linguistic analysis, and image recognition.

The restaurant analogy first appeared in a 1985 write-up by David Aldous, where it was attributed to Jim Pitman (who additionally credits Lester Dubins).

Formal definition 
For any positive integer , let  denote the set of all partitions of the set . The Chinese restaurant process takes values in the infinite Cartesian product .

The value of the process at time  is a partition  of the set , whose probability distribution is determined as follows.  At time , the trivial partition  is obtained (with probability one). At time  the element "" is either:
 added to one of the blocks of the partition , where each block is chosen with probability  where  is the size of the block (i.e. number of elements), or 
 added to the partition  as a new singleton block, with probability .
The random partition so generated has some special properties. It is exchangeable in the sense that relabeling  does not change the distribution of the partition, and it is consistent in the sense that the law of the partition of  obtained by removing the element  from the random partition  is the same as the law of the random partition .

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

 

where  is a block in the partition  and  is the size of .

The definition can be generalized by introducing a parameter  which modifies the probability of the new customer sitting at a new table to  and correspondingly modifies the probability of them sitting at a table of size  to . The vanilla process introduced above can be recovered by setting . Intuitively,  can be interpreted as the effective number of customers sitting at the first empty table.

Alternative definition 
An equivalent, but subtly different way to define the Chinese restaurant process, is to let new customers choose companions rather than tables. Customer  chooses to sit at the same table as any one of the  seated customers with probability , or chooses to sit at a new, unoccupied table with probability . Notice that in this formulation, the customer chooses a table without having to count table occupancies---we don't need .

Distribution of the number of tables

The Chinese restaurant table distribution (CRT) is the probability distribution on the number of tables in the Chinese restaurant process. It can be understood as the sum of  independent Bernoulli random variables, each with a different parameter:

The probability mass function of  is given by 

where  denotes Stirling numbers of the first kind.

Generalization 
This construction can be generalized to a model with two parameters,  & , commonly called the strength (or concentration) and discount parameters respectively.  At time , the next customer to arrive finds  occupied tables and decides to sit at an empty table with probability

 

or at an occupied table  of size  with probability

 

In order for the construction to define a valid probability measure it is necessary to suppose that either  and  for some ; or that  and .

Under this model the probability assigned to any particular partition  of , in terms of the Pochhammer k-symbol, is

where, by convention, , and for 

Thus, for the case when  the partition probability can be expressed in terms of the Gamma function as

In the one-parameter case, where  is zero, this simplifies to

Or, when  is zero,

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 , the probability distribution of the random partition of the integer  thus generated is the Ewens distribution with parameter , used in population genetics and the unified neutral theory of biodiversity.

Derivation 

Here is one way to derive this partition probability.  Let  be the random block into which the number  is added, for .  Then

The probability that  is any particular partition of the set  is the product of these probabilities as  runs from  to .  Now consider the size of block : it increases by one each time we add one element into it. When the last element in block  is to be added in, the block size is . For example, consider this sequence of choices: (generate a new block )(join )(join )(join ). In the end, block  has 4 elements and the product of the numerators in the above equation gets .  Following this logic, we obtain  as above.

Expected number of tables 
For the one parameter case, with  and , the number of tables is distributed according to the chinese restaurant table distribution. The expected value of this random variable, given that there are  seated customers, is

where  is the digamma function. In the general case () the expected number of occupied tables is

however, note that the  function here is not the standard gamma function.

The Indian buffet process
It is possible to adapt the model such that each data point is no longer uniquely associated with a class (i.e., we are no longer constructing a partition), but may be associated with any combination of the classes. This strains the restaurant-tables analogy and so is instead likened to a process in which a series of diners samples from some subset of an infinite selection of dishes on offer at a buffet. The probability that a particular diner samples a particular dish is proportional to the popularity of the dish among diners so far, and in addition the diner may sample from the untested dishes. This has been named the Indian buffet process
and can be used to infer latent features in data.

Applications 
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, biodiversity modelling, and image reconstruction

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

References

External links
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/

Stochastic processes
Nonparametric Bayesian statistics