3
$\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
    Commented Feb 9, 2021 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$ Commented Feb 9, 2021 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
    Commented Feb 9, 2021 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
    Commented Feb 9, 2021 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
    Commented Feb 9, 2021 at 4:07

1 Answer 1

5
$\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
  • 3
    $\begingroup$ Nice answer. One can also use Berry--Esseen for non-identically distributed variables to get a quantitative, finite-sample, bound. $\endgroup$
    – passerby51
    Commented Feb 9, 2021 at 21:11
  • $\begingroup$ guy & @passerby51, how do you get so good at this stuff? Any tips for learning faster? $\endgroup$ Commented Feb 10, 2021 at 0:03
  • $\begingroup$ @guy, small nit: I think that $p_i = \alpha/(\alpha + i -1)$, not $p_i = \alpha/(\alpha + i)$? $\endgroup$ Commented Feb 10, 2021 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
    Commented Feb 10, 2021 at 16:53
  • 2
    $\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
    Commented Feb 11, 2021 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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