A Simple Method for PMF Estimation on Large Supports

Alex ShtoffarXiv 2025 · DOI · arXiv

Abstract

Estimating probability distributions for sparse, heavy-tailed data on large supports is challenging for standard non-parametric tools. We propose a fast, automated method that treats the data as a signal on a graph and applies a data-dependent low-pass filter. By utilizing the spectral properties of a modified Laplacian matrix, the approach captures sharp peaks and heavy tails that typically baffle Kernel Density Estimators (KDEs). The method is computationally efficient, scaling linearly with the support size, and provides a robust alternative for production data pipelines.

Introduction

Nonparametric Probability Mass Function (PMF) estimation on large discrete supports (where the number of possible values $N$ ranges from thousands to millions) is a common but difficult task. Standard methods often struggle in this regime:

  • Histograms: Choosing the right bin size for heavy-tailed data is difficult; too large a bin loses detail, while too small a bin retains too much noise.
  • Gaussian KDEs: These tend to "over-smooth" spiky distributions, blurring distinct modes into a single blob.
  • Logspline: While accurate, it can be computationally expensive and numerically unstable on complex real-world datasets.

The goal is a method that is fast, automated (no manual bandwidth tuning), and robust enough for production environments.

Methodology: The Schrödinger Connection

The core innovation is treating the empirical PMF as a signal on a line graph and applying a data-dependent spectral filter. The method constructs a symmetric tridiagonal matrix $H = L - \text{diag}(p)$, where $L$ is a standard path graph Laplacian and $p$ is the vector of empirical frequencies (the "potential").

This operator $H$ is essentially a discrete version of a Schrödinger operator. In physics, the "potential" (the data $p$) traps the "wavefunction" (the eigenvectors). Consequently, the basis vectors naturally concentrate their mass where the data is most frequent. This allows the model to fit sharp spikes while remaining smooth elsewhere.

Eigenvectors of the Laplacian spectrum.

The noisy empirical PMF is projected onto the subspace spanned by the $k$ eigenvectors corresponding to the smallest eigenvalues of $H$. Because $H$ is tridiagonal, this eigen-decomposition is extremely efficient, requiring only $O(kN)$ time and memory. The authors also provide a data-driven heuristic to select the optimal $k$ based on an orthogonal series risk estimate, removing the need for human intervention.

Results and Performance

The method was evaluated on a variety of synthetic distributions, including bimodal/trimodal power laws, Zipf distributions, and "rippled" power laws. On "spiky" distributions, the method significantly outperforms Gaussian KDEs, which fail to capture the height and isolation of the peaks.

Eigenspace projections for synthetic distributions.

In real-world tests using the Spambase and Bank Marketing datasets, the Laplacian method remained stable across all features, whereas the popular logspline method occasionally failed to converge or produced unreasonable estimates. The proposed method is generally as accurate as logspline but faster and more reliable for automated pipelines, performing excellently even with small sample sizes (e.g., 250 samples for a support of 5,000).

Discussion and Limitations

While the method excels at capturing spikes, it struggles with abrupt discontinuities, such as the "Mid plateau" synthetic case. Because it is fundamentally a smoothness-based spectral approach, it tends to "ring" or blur sharp edges, as seen in the projections for the plateau distribution. Future work may involve exploring different graph structures or rewards (like KL-divergence) to improve results, although the current tridiagonal structure is key to its $O(kN)$ efficiency.

Summary updated

Abstract

We study nonparametric estimation of a probability mass function (PMF) on a large discrete support, where the PMF is multi-modal and heavy-tailed. The core idea is to treat the empirical PMF as a signal on a line graph and apply a data-dependent low-pass filter. Concretely, we form a symmetric tri-diagonal operator, the path graph Laplacian perturbed with a diagonal matrix built from the empirical PMF, then compute the eigenvectors, corresponding to the smallest feq eigenvalues. Projecting the empirical PMF onto this low dimensional subspace produces a smooth, multi-modal estimate that preserves coarse structure while suppressing noise. A light post-processing step of clipping and re-normalizing yields a valid PMF. Because we compute the eigenpairs of a symmetric tridiagonal matrix, the computation is reliable and runs time and memory proportional to the support times the dimension of the desired low-dimensional supspace. We also provide a practical, data-driven rule for selecting the dimension based on an orthogonal-series risk estimate, so the method "just works" with minimal tuning. On synthetic and real heavy-tailed examples, the approach preserves coarse structure while suppressing sampling noise, compares favorably to logspline and Gaussian-KDE baselines in the intended regimes. However, it has known failure modes (e.g., abrupt discontinuities). The method is short to implement, robust across sample sizes, and suitable for automated pipelines and exploratory analysis at scale because of its reliability and speed.
BibTeX
@misc{shtoff2025simple,
  author = {Alex Shtoff},
  title = {{A Simple Method for PMF Estimation on Large Supports}},
  year = {2025},
  eprint = {2510.15132},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.15132},
}
Figure