# Why does Chinese Restaurant Table Distribution look like a Gaussian Distribution?

The Chinese Restaurant Table Distribution describes the probability distribution for the number of non-empty tables in the Chinese Restaurant Process after $$T$$ customers have been seated. Specifically, if $$K_T$$ is the (random) number of non-empty tables after seating $$T$$ customers in a $$CRP(\alpha)$$, its PMF is defined as

$$P(K_T = k) = \frac{\Gamma(\alpha)}{\Gamma(\alpha + T)} |S(T, k)| \alpha^k$$

where $$k \in \{1, ..., T\}$$ and $$|S(\cdot, \cdot)|$$ are unsigned Stirling numbers of the first kind. I discovered that when I fix $$\alpha$$ and plot the distribution for increasing values of $$T$$, the distribution looks more and more like a Gaussian. For alpha=10.01, I plot the distribution from T=1 (red) to T=50 (blue):

My question is: why does the Chinese Restaurant Table distribution look like a Gaussian distribution for medium-to-large $$T$$?

• The number of tables is approximately Poisson, which is approximately Gaussian for large rates. You can get a finite sample bound from Le Cam’s Theorem on how close it is to the approximating Poisson. – guy Feb 9 at 3:26
• I buy that Poisson is approximately Gaussian for large rates, but I'm unfamiliar with the first and third steps. Could you walk me through the derivation? – Rylan Schaeffer Feb 9 at 3:29
• Well, the number of tables is $K_T = \sum_{i = 1}^T I(\text{new table at observation$i$})$, and the terms of the sum are independent. You have a lot of options here for showing that it is close to a Gaussian, as it is a sum of independent random variables. For example, if $p_i = \alpha / (\alpha + i)$ is the probability of a new table at observation $i$, then it is easy enough to check that $\sum_i p_i (1 - p_i) = \infty$, after which you can apply this exercise. – guy Feb 9 at 3:54
• There is no way to simplify the sum, and the bound itself doesn't depend on the sum. Although to apply Le Cam's lemma you might need to take $\alpha \downarrow 0$ slowly. Probably the easiest thing to do is actually just to apply the Lyapounov CLT that I linked to in my last comment, if all you care about is the Gaussian part, and skip Le Cam's theorem. – guy Feb 9 at 4:03
• Also, technically it should be $1 +$ a Poisson, if you go that route, since obviously $K_T \ge 1$. A precise result is given in this paper. – guy Feb 9 at 4:07

We can apply the Lyapounov CLT to show that $$K_T$$ is normal for large $$T$$. Let $$K_T = \sum_{i=1}^T I(\text{new table at i}) = \sum_{i=1}^T Z_i.$$ Then it is well-known that $$Z_i \stackrel{\text{ind}}{\sim} \text{Bernoulli}(p_i)$$ where $$p_i = \alpha / (\alpha + i - 1)$$. Now, $$\sum_{i=1}^\infty p_i (1 - p_i) = \sum_{i=1}^\infty \frac{\alpha i}{(\alpha + i)^2} = \infty$$ by comparison to the harmonic series. Hence we can apply the Lyapnouv CLT to conclude that $$\frac{K_T - E(K_T)}{\sqrt{\text{Var}(K_T)}} \to N(0,1)$$ in distribution, using the argument outlined here to verify the Lyapounov condition for Bernoulli random variables.
• @guy, small nit: I think that $p_i = \alpha/(\alpha + i -1)$, not $p_i = \alpha/(\alpha + i)$? – Rylan Schaeffer Feb 10 at 15:21