==Table Sharing==

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). 

[[media:cs-677sp10: 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:

[[media:cs-677sp10:Tables.JPG‎]]

==Definition==

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. [https://facwiki.cs.byu.edu/cs677sp10/index.php/Chinese_Restaurant_Process#References 1]

==Assumptions==

* 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.

==Probabilities==

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:


[[media:cs-677sp10:Tables2.JPG‎]]

==Generalization==
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 [http://en.wikipedia.org/wiki/Unified_neutral_theory_of_biodiversity unified neutral theory of biodiversity].


==Expected Number of Tables==
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}$

==Applications==

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

==References==

1. Wikipedia, "Chinese Restaurant Process", Online: [http://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: [http://xiaodong-yu.blogspot.com/2009/09/chinese-restaurant-process-and-chinese.html]

==Questions==

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

[[media:cs-677sp10: Tables4.JPG]]