Chinese restaurant process

Example

Fix a parameter $\theta > 0$. Customers $1, 2, 3, \ldots$ enter a restaurant with infinitely many tables, one at a time. Customer $1$ sits at a new table. Suppose $n$ customers are seated, and the occupied tables hold $n_1, \ldots, n_k$ customers, so $n_1 + \cdots + n_k = n$. Then customer $n + 1$ sits at the $j$-th occupied table with probability $n_j / (n + \theta)$, and at a new table with probability $\theta / (n + \theta)$. These probabilities are nonnegative and sum to $(n + \theta)/(n + \theta) = 1$. The seating of the first $n$ customers gives a random partition $\Pi_n$ of $\set{1, \ldots, n}$, whose blocks are the tables.

Multiplying the seating probabilities gives, for each partition $\pi$ of $\set{1, \ldots, n}$ with $k$ blocks of sizes $n_1, \ldots, n_k$, $$P(\Pi_n = \pi) = \frac{\theta^k \, \Gamma(\theta)}{\Gamma(\theta + n)} \prod_{j=1}^{k} (n_j - 1)!,$$ where $\Gamma$ is the gamma function. To check this, note that the denominators $\theta, \theta + 1, \ldots, \theta + n - 1$ multiply to $\Gamma(\theta + n)/\Gamma(\theta)$. Each table contributes the factor $\theta$ when it is opened, and then the factors $1, 2, \ldots, n_j - 1$ from the later customers who join it. The right side depends only on the block sizes, so the law of $\Pi_n$ is invariant under permutations of $\set{1, \ldots, n}$. In this sense the random partition is exchangeable.

For $n = 2$, customers $1$ and $2$ share a table with probability $1/(1 + \theta)$. The number $K_n$ of occupied tables after $n$ customers has mean $$E[K_n] = \sum_{i=0}^{n-1} \frac{\theta}{\theta + i},$$ which grows like $\theta \log n$.