The Chinese Restaurant Process is very simple and best explained by example. Suppose there is a Chinese restaurant that has 4 tables. There are currently 7 customers: 4 customers at table #1, 2 customers at table #2, 1 customer at table #3, and no customers at table #4. When new customer #8 enters, he will be seated at one of the 4 tables with probabilities:
p(table #1) = 4 / (7 + 1) = 4/8 p(table #2) = 2 / (7 + 1) = 2/8 p(table #3) = 1 / (7 + 1) = 1/8 p(table #4) = 1 / (7 + 1) = 1/8 ----- 1
The probability of being seated at an occupied table is ni / (m + a) where ni is the number of people currently at the table, m is the total number of customers currently at all tables, and a is variable parameter that controls the process.
There will always be one empty table. The probability of being seated at the empty table is a / (m + a).
The Chinese Restaurant Process is an example of “the rich get richer”. Tables with the most customers seated are the most likely to get the next new customer. The larger the value of a is, the less extreme the tendency is.
Tables are assumed to have infinite size, and when a new customer is seated at the one empty table, a new empty table is wheeled out.
The Chinese Restaurant Process is very closely related to the mathematical Dirichlet process. Both processes pop up in problems such as statistical text models, data clustering, biological models, and image reconstruction.
Left: I’ll take a large size, thin crust, topped with olives and penicillin. Center: No thanks. Right: I’ll have some loaves and fishes, and a glass of Holy water.