When customers enter in a restaurant, at times they would have to wait for a table to be clear for them to sit (Happens a lot a Reb Robins at the Provo Mall).

Tables3.JPG

In order to speed up the process, in some old Chinese restaurants, customers who do not know each other may be assigned to sit together at a table, this way they could get a table much quicker. In modern times, this could be best described by the cafeteria, where random people could come and sit by you at a table.

The Chinese Restaurant Process uses an analogy to this. Imagine a restaurant with unlimited number of tables; when a new customer comes in, he/she may either sit at a new table, or sit at a table that has already been occupied.

This is shown in the following diagram:

Tables.JPG‎

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:

1. added to one of the blocks of the partition Bn, where each block is chosen with probability |b|/(n + 1) where |b| is the size of the block, or

2. added to the partition Bn as a new singleton block, with probability 1/(n + 1).

The random partition so generated is exchangeable in the sense that relabeling {1, …, n} 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. 1

• A Chinese restaurant has infinitely many tables
• Each table can have infinitely many seats
• A new customer could sit next to a customer at a table or sit at a new table next to the ones occupied.

At each time n+1 (n>0) unit a new customer comes in (element n+1), he/she could choose from the following n+1 places: next to each of the n customers already sat at the tables, or at a new table.

P(customer sits at a table occupied by others) = $\frac{m_i}{n+1}$, $m_i$ is the number of people sitting at the table

P(customer sits at a new table) = $\frac{1}{n+1}$

This is illustrated in the following diagram:

Tables2.JPG‎

The Chinese Restaurant analogy could be generalized to a model with the following parameters:

$\vartheta$ : which is called the discount parameter and $\alpha$ : which is called the strength parameter.

The probability of a new customer coming in at time n+1 and finding B tables which customers and decides to sit at a new table is given by:

$\frac{\vartheta + |B|\alpha}{n+\vartheta}$

and the probability that the new customer joins the other customers at an occupied table is given by:

$\frac{|b|-\alpha}{n+\vartheta}$

with $\alpha<0$ and $\vartheta=L\alpha$, L= {1,2,3…} or

$0\le\alpha\le1$ and $\vartheta>-\alpha$

Thus the probability of a new customer sitting at any partition (table ) B could be expressed by a Gamma function:

$P(B_n=B)=\frac{\Gamma(\vartheta)}{\Gamma(\vartheta+n)}\frac{\alpha^{|B|}\Gamma(\vartheta/\alpha+|B|))}{\Gamma(\vartheta/\alpha)}\prod_{b\in B}\frac{\Gamma(|b|-\alpha)}{\Gamma(1-\alpha)}$

When $\alpha$ is 0, the above equation simplifies to:

$\frac{\Gamma(\vartheta)\vartheta^{|B|}}{\Gamma(\vartheta+n)}\prod_{b\in B}\Gamma(|b|)$ This is also called Ewens distribution with only one parameter $\vartheta$, which is used in population genetics and the unified neutral theory of biodiversity.

For the Ewens distribution, where $\alpha$ is 0 and $\vartheta$ is a positive real number, given n customers, the expected number of tables is given by the formula:

$\sum_{k=1}^n\frac{\vartheta}{\vartheta+k-1}$

The Chinese Restaurant Process has been used applications such as modeling text, clustering biological microarray data, and detecting objects in images.

1. Wikipedia, “Chinese Restaurant Process”, Online: ://en.wikipedia.org/wiki/Chinese_restaurant_process

2. Lecture #1, COS 597C, David Blei

3. Xiaodong's tech notes on computer vision and machine learning. Online: ://xiaodong-yu.blogspot.com/2009/09/chinese-restaurant-process-and-chinese.html

Briefly describe the analogy in the Chinese Restaurant Process, and compute the probabilities of the new customer sitting at each table:

Tables4.JPG