In probability theory, the Chinese restaurant process is a discrete-time stochastic process, analogous to seating customers at tables in a Chinese restaurant. Imagine a Chinese 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, or an unoccupied table. At time n, the n customers have been partitioned among m ≤ n tables. 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. David J. Aldous attributes the restaurant analogy to Jim Pitman and Lester Dubins in his 1983 book.
Formal definition
At any positive-integer time n, the value of the process is a partition Bn of the set, whose probability distribution is determined as follows. At time n = 1, the trivial partition is obtained with probability 1. At time n + 1 the element n + 1 is either:
added to one of the blocks of the partition Bn, where each block is chosen with probability |b|/ where |b| is the size of the block, or
added to the partition Bn as a new singleton block, with probability 1/.
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 n − 1 obtained by removing the element n from the random partition at time n is the same as the law of the random partition at time n − 1. The probability assigned to any particular partition is where b is a block in the partition B and |b| is the size of b.
This construction can be generalized to a model with two parameters, θ & α, commonly called the discount and strength parameters. At time n + 1, the next customer to arrive finds |B| occupied tables and decides to sit at an empty table with probability or at an occupied table b of size |b| with probability In order for the construction to define a valid probability measure it is necessary to suppose that either α < 0 and θ = - Lα for some L ∈ ; or that 0 ≤ α < 1 and θ > −α. Under this model the probability assigned to any particular partition B of n, 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 α = 0, the probability distribution of the random partition of the integern 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 Ci be the random block into which the number i is added, for i = 1, 2, 3, ... . Then The probability that Bn is any particular partition of the set is the product of these probabilities as i runs from 1 to n. 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. For example, consider this sequence of choices:. 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 as above.
Expected number of tables
For the one parameter case, with α = 0 and 0 < θ < ∞, 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.
It is possible to adapt the model such that each data point is no longer uniquely associated with a class, 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.
