A General Purpose Approximation to the Ferguson-Klass Algorithm for Sampling from Lévy Processes Without Gaussian Components

Dawid Bernaciak, Jim E. Griffin

TL;DR

This paper introduces a high-speed, general-purpose approximation to the Ferguson-Klass algorithm for sampling from Lévy processes. By using a multi-part grid approximation of jump intensities, the authors achieve a 1000x speedup over standard methods while maintaining high precision, effectively unlocking the use of complex, non-conjugate Bayesian nonparametric models that were previously too computationally expensive to use.

What Problem Does This Paper Address?

In Bayesian nonparametrics, researchers often use Completely Random Measures (CRMs)—like the Gamma or Beta process—to model things like clustering or latent features. To use these in practice, you need to simulate "jumps" from these processes.

The gold standard for this is the Ferguson-Klass (FK) algorithm. However, the FK algorithm is notoriously slow because it requires repeated numerical integration and inversion of a "tail mass function" for every single jump. Because of this bottleneck, researchers usually stick to "conjugate" models—mathematically convenient cases where the math simplifies—or rely on "tailored" samplers that only work for one specific type of process. There has been a long-standing gap for a "black box" sampler that is both fast and works for any Lévy process without Gaussian components.

Methods

The authors propose a multi-part approximation of the Lévy intensity ($\nu$). Instead of calculating the integral from scratch for every jump, they pre-calculate the intensity on a grid.

  • Piecewise Approximations: They use two main types of functions to fit the intensity within grid bins:
  • Trapezoidal (Linear): Great for larger jump sizes.
  • Polynomial ($x^{-\kappa}$): Specifically designed to handle the "infinite" number of tiny jumps near zero, where linear approximations usually fail.
  • Adaptive Grid Selection: The algorithm automatically determines the boundaries of the grid ($x_0$ for the smallest jumps and $x_n$ for the largest) based on user-defined error tolerances.
  • Optional Rejection Sampling: If the approximation is designed as an "envelope" (always slightly larger than the true intensity), they can use a thinning/rejection step to produce exact samples, though the approximation alone is usually precise enough for most applications.
  • Computational Efficiency: By moving the heavy lifting (integration) to a one-time grid setup, the complexity drops from $O(N \times n \times R)$ (where $R$ is the cost of root-finding) to a much leaner $O(n + N)$.

Datasets

As a methodology-focused paper, the authors evaluated their approach using synthetic simulations of several standard and non-standard processes:

  • Standard CRMs: Gamma, $\sigma$-stable, Beta, and Generalized Gamma processes.
  • Complex Examples:
    • Compound Random Measures (CoRMs): Used to model correlated vectors of CRMs.
  • Occupancy Models: A synthetic dataset simulating animal species presence/detection across 10 sites and 5 sampling occasions to demonstrate how the sampler handles non-conjugate posterior distributions.

Key Insights and Ideas

  • The "Aha" Moment on Grid Spacing: The authors prove that geometric grid spacing is optimal for many common Lévy processes. This allows the grid to be dense near zero (where the intensity is volatile) and sparse for large values, balancing speed and accuracy.
  • Hybrid Modeling: The realization that polynomial approximations are strictly better than linear ones near the origin ($x \to 0$) is crucial. It allows the algorithm to handle the "heavy lifting" of the Lévy process's singularity without blowing up the error.
  • Breaking the Conjugacy Barrier: By providing a fast, general sampler, the authors argue that researchers no longer need to choose their models based on what is "easy to compute." They can now build models that better reflect real-world data, even if the resulting math is "messy."

Key Results

  • Massive Speedups: The proposed method is 1000x to 4500x faster than the standard Ferguson-Klass algorithm for Stable-Beta processes. Even for simpler processes like the Beta process, it remains 700x to 1500x faster.
  • High Precision: The relative error in jump sizes can be controlled by the number of bins. With $10^6$ bins, the relative error drops to a negligible $10^{-9}$.
  • Practical Utility: In the occupancy model example, the authors performed MCMC sampling that would have been "unachievable" with the original FK algorithm due to the time required for repeated posterior evaluations.

Limitations and Future Work

  • Relative Speed: While much faster than the general FK algorithm, the method is still about 5 to 17 times slower than "tailored" samplers (which are hand-optimized for a single specific process).
  • Algebraic Requirement: The method requires the Lévy intensity to be available in an algebraic form to build the grid.
  • Future Directions: The authors suggest that future work could involve even more sophisticated grid spacing schemes or extending the logic to higher-dimensional (multivariate) Lévy processes.

Summary updated

Abstract

We propose a general-purpose approximation to the Ferguson-Klass algorithm for generating samples from Lévy processes without Gaussian components. We show that the proposed method is more than 1000 times faster than the standard Ferguson-Klass algorithm without a significant loss of precision. This method can open an avenue for computationally efficient and scalable Bayesian nonparametric models which go beyond conjugacy assumptions, as demonstrated in the examples section.
BibTeX
@article{bernaciak2025general,
  author = {Dawid Bernaciak and Jim E. Griffin},
  title = {{A General Purpose Approximation to the Ferguson-Klass Algorithm for Sampling from Lévy Processes Without Gaussian Components}},
  journal = {Journal of Computational and Graphical Statistics},
  year = {2025},
  doi = {10.1080/10618600.2025.2602523},
}

Loading related content...

Figure