In probability theory, the Chinese restaurant process is a discrete-time stochastic process, analogous to seating customers at tables in a restaurant. Imagine a restaurant with an infinite number of circular tables, each with infinite capacity. Customer 1 sits at the first table. The next customer either sits at the same table as customer 1, or the next table. This continues, with each customer choosing to either sit at an occupied table with a probability proportional to the number of customers already there (i.e., they are more likely to sit at a table with many customers than few), or an unoccupied table. At time n, the n customers have been partitioned among m ≤ n tables (or blocks of the partition). The results of this process are exchangeable, meaning the order in which the customers sit does not affect the probability of the final distribution. This property greatly simplifies a number of problems in population genetics, linguistic analysis, and image recognition.

The restaurant analogy first appeared in a 1985 write-up by David Aldous, where it was attributed to Jim Pitman (who additionally credits Lester Dubins).

An equivalent partition process was published a year earlier by Fred Hoppe, using an "urn scheme" akin to Pólya's urn. In comparison with Hoppe's urn model, the Chinese restaurant process has the advantage that it naturally lends itself to describing random permutations via their cycle structure, in addition to describing random partitions.

For any positive integer ${\displaystyle n}$, let ${\displaystyle {\mathcal {P}}_{n}}$ denote the set of all partitions of the set ${\displaystyle \{1,2,3,...,n\}\triangleq [n]}$. The Chinese restaurant process takes values in the infinite Cartesian product ${\displaystyle \prod _{n\geq 1}{\mathcal {P}}_{n}}$.

The value of the process at time ${\displaystyle n}$ is a partition ${\displaystyle B_{n}}$ of the set ${\displaystyle [n]}$, whose probability distribution is determined as follows. At time ${\displaystyle n=1}$, the trivial partition ${\displaystyle B_{1}=\{\{1\}\}}$ is obtained (with probability one). At time ${\displaystyle n+1}$ the element "${\displaystyle n+1}$" is either:

The random partition so generated has some special properties. It is exchangeable in the sense that relabeling ${\displaystyle \{1,...,n\}}$ does not change the distribution of the partition, and it is consistent in the sense that the law of the partition of ${\displaystyle [n-1]}$ obtained by removing the element ${\displaystyle n}$ from the random partition ${\displaystyle B_{n}}$ is the same as the law of the random partition ${\displaystyle B_{n-1}}$.

The probability assigned to any particular partition (ignoring the order in which customers sit around any particular table) is

where ${\displaystyle b}$ is a block in the partition ${\displaystyle B}$ and ${\displaystyle |b|}$ is the size of ${\displaystyle b}$.