4
$\begingroup$

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

enter image description here

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

$\endgroup$
9
  • 4
    $\begingroup$ 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. $\endgroup$ – guy Feb 9 at 3:26
  • $\begingroup$ 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? $\endgroup$ – Rylan Schaeffer Feb 9 at 3:29
  • 2
    $\begingroup$ 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. $\endgroup$ – guy Feb 9 at 3:54
  • 1
    $\begingroup$ 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. $\endgroup$ – guy Feb 9 at 4:03
  • 2
    $\begingroup$ 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. $\endgroup$ – guy Feb 9 at 4:07
4
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ Nice answer. One can also use Berry--Esseen for non-identically distributed variables to get a quantitative, finite-sample, bound. $\endgroup$ – passerby51 Feb 9 at 21:11
  • $\begingroup$ guy & @passerby51, how do you get so good at this stuff? Any tips for learning faster? $\endgroup$ – Rylan Schaeffer Feb 10 at 0:03
  • $\begingroup$ @guy, small nit: I think that $p_i = \alpha/(\alpha + i -1)$, not $p_i = \alpha/(\alpha + i)$? $\endgroup$ – Rylan Schaeffer Feb 10 at 15:21
  • 1
    $\begingroup$ @Rylan yes, thanks for the correction. For being "good at this stuff," most of it is just experience. I used to work with DPs a lot. $\endgroup$ – guy Feb 10 at 16:53
  • 1
    $\begingroup$ @RylanSchaeffer, asking good questions is perhaps the first step (which you are doing fine). Experience (as guy said) helps; it becomes easier over time... practice makes perfect. Other things that come to mind: 1) Reading research papers and seeing how others do it (esp. the really good ones). 2) Doing research: Defining a specific problem and reading and thinking around that. 3) Practice, practice, practice! $\endgroup$ – passerby51 Feb 11 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.