Chinese Restaurant Process

The Chinese Restaurant Process (CRP) is one possible representation of the Dirichlet Process. The metaphor works as follows:
1. We have a Chinese restaurant with infinitely many tables. At the start of the day, the restaurant is empty.
2. When the first guest enters the restaurant, he sits at a new table and orders a dish.
3. Each new guest who enters afterwards will start either a new table with probability $$\frac{a}{a+n_k}$$ or decide to sit at the already occupied table $$k$$ with probability $$\frac{n}{a+n_k}$$
As we can see, new customers have a higher probability to sit at tables with lots of guests. This often called "the rich get richer" property of the CRP is the reason why the CRP is a useful building block in clustering: Even though there are in principle infinitely many tables, only a finite, quite small subset will be occupied in practice.

How does the number of tables grow with the number of customers? The answer is logarithmically. We have that $$\mathbb{E}(K) = O \left(\alpha \log(n) \right)$$