Chinese Restaurant Process

Chinese restaurant process is a discrete-time stochastic process that describes how a sequence of customers entering a restaurant choose tables — and it serves as a metaphor for how the Dirichlet process generates cluster assignments. The process is simple: the first customer sits at the first table. Each subsequent customer either joins an existing table with probability proportional to the number of customers already seated there, or starts a new table with probability proportional to a concentration parameter.

This urn-like allocation rule produces a rich-get-richer dynamic: larger tables attract more customers, while the concentration parameter controls the rate at which new tables are created. The distribution of table sizes follows a power law, and the expected number of tables grows logarithmically with the number of customers. The metaphor extends naturally to the Pitman-Yor process, where a discount parameter modifies the seating rule to produce even heavier-tailed distributions.

The Chinese restaurant process is not merely a colorful metaphor. It is an exact probabilistic specification of the clustering behavior that emerges from the Dirichlet process and its generalizations, and it has been applied to topic modeling, language modeling, and any domain where the number of latent categories must be inferred rather than assumed.