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