Abstract
This note provides an elementary proof of the folklore fact that draws from a Dirichlet distribution (with parameters less than 1) are typically sparse, meaning most coordinates are small. We show that for a Dirichlet distribution with parameter $\alpha = 1/n$, the number of significant coordinates is bounded by $O(\ln n)$ with high probability.
Introduction
In machine learning applications such as Latent Dirichlet Allocation (LDA) and Bayesian nonparametrics, the Dirichlet distribution is the standard prior for categorical distributions. It is widely recognized that when the concentration parameter $\alpha$ is less than 1, the resulting draws are sparse—the probability mass concentrates on a few coordinates while others remain near zero. Despite being a staple of "folklore," rigorous and simple formal bounds quantifying this sparsity have been surprisingly scarce. This paper fills this gap by providing concrete theorems that bound the number of coordinates exceeding a given threshold $\epsilon$ as the dimensionality $n$ increases.
Methodology
The primary challenge in analyzing Dirichlet draws is the dependency between coordinates (they must sum to 1). To circumvent this, we utilize an alternate representation: a Dirichlet vector $(X_1, \dots, X_n)$ can be constructed by normalizing $n$ independent and identically distributed (i.i.d.) Gamma random variables, $X_i = Y_i / \sum Y_j$.
The proof strategy involves analyzing the properties of the underlying i.i.d. Gamma variables, applying a novel inequality for the Gamma distribution's cumulative distribution function (CDF), and using multiplicative Chernoff bounds to show that both the total sum and the count of variables exceeding a threshold remain within predictable limits.
Empirical Validation
To validate the theoretical bounds, synthetic simulations were conducted. The author sampled 1,000 Dirichlet distributions for various dimensions $n$ (up to 1,000) and parameter choices $\alpha \in \{n^{-1}, n^{-2}\}$.
As shown in the figure above, when $\alpha = 1/n$, the number of coordinates exceeding a threshold scales logarithmically with $n$, confirming that the $\ln n$ factor in the theoretical bounds is a real phenomenon and not a proof artifact. Furthermore, as the threshold $\epsilon$ decreases (e.g., from $n^{-1}$ to $n^{-4}$), the number of significant coordinates grows linearly.
In the extreme sparsity case where $\alpha = 1/n^2$ (shown above), the number of significant coordinates remains very small regardless of $n$, often dropping to just one or two as the dimensionality increases. This empirical evidence supports the theoretical claim that for very small $\alpha$, the distribution becomes extremely "spiky."
Key Theoretical Results
The paper establishes several key bounds on sparsity:
- Standard Sparsity ($\alpha = 1/n$): Theorem 1.1 states that the probability of more than $6c_0 \ln n$ coordinates exceeding the threshold $1/n^{c_0}$ is at most $1/n^{c_0}$. In a 1,000-dimensional space, very few coordinates will ever be significantly large.
- Extreme Sparsity ($\alpha = 1/n^2$): Theorem 1.3 shows that if $\alpha = 1/n^2$, there is at least a 64% probability that no more than 5 coordinates will exceed the threshold $n^{-2}$, regardless of how large $n$ is (for $n \ge 3$).
- Generalized Bounds: Theorem 1.2 provides a flexible framework for researchers to calculate specific constants for their model constraints.
Limitations and Conclusion
While the methods provide tight bounds for the standard case, they are somewhat "loose" for extremely small parameters ($\alpha = o(1/n)$). For instance, while simulations suggest only one coordinate is typically large when $\alpha = 1/n^2$, the theoretical bound in Theorem 1.3 is limited to 5 coordinates. Tightening these bounds for high-sparsity regimes remains an area for future refinement. Overall, this work provides the necessary formal foundation for the long-held intuition regarding Dirichlet sparsity in machine learning.
Summary updated