Stein's method for the Beta distribution and the Pólya-Eggenberger Urn

Larry B. Goldstein, Gesine ReinertarXiv 2012 · DOI · arXiv

Abstract

Using a characterizing equation for the Beta distribution, Stein's method is applied to obtain bounds of the optimal order for the Wasserstein distance between the distribution of the scaled number of white balls drawn from a Pólya-Eggenberger urn and its limiting Beta distribution. The bound is computed by making a direct comparison between characterizing operators of the target and the Beta distribution, the former derived by extending Stein's density approach to discrete distributions. In addition, refinements are given to Döbler's result for the Arcsine approximation for the fraction of time a simple random walk of even length spends positive, and so also to the distributions of its last return time to zero and its first visit to its terminal point, by supplying explicit constants to the present Wasserstein bound and also demonstrating that its rate is of the optimal order.

Introduction

In probability theory, the Pólya-Eggenberger urn model serves as a foundational reinforcement process. In this model, balls are drawn from an urn and replaced along with additional balls of the same color, creating a path-dependent evolution. While it has long been established that the proportion of balls of a specific color converges to a Beta distribution as the number of draws $n$ approaches infinity, practical applications in statistics and computer science require more than just a proof of convergence. They require a precise understanding of the rate of convergence—specifically, explicit "error bars" for finite $n$.

This paper addresses this gap by providing the first optimal-order error bounds for the Beta approximation of the Pólya-Eggenberger urn. By refining Stein’s method, the authors demonstrate that the convergence rate is exactly $O(1/n)$, a rate that is mathematically impossible to improve for this model.

Methodology: Stein’s Method and the Density Approach

The authors utilize Stein’s method, a sophisticated technique for bounding the distance between two probability distributions. This involves solving a specific differential equation, known as the Stein equation, which characterizes the target distribution.

Characterizing Operators

A key technical innovation in this work is the derivation of a characterizing operator for the Beta distribution based on the Fisher-Wright model, a stochastic process frequently used in population genetics. To bridge the gap between the discrete nature of the urn model (integers representing ball counts) and the continuous nature of the Beta distribution (fractions on the interval $[0, 1]$), the authors extended Stein’s "density approach" to discrete distributions.

Operator Comparison

By creating a discrete characterizing operator for the urn model itself, the researchers were able to perform a direct comparison with the continuous Beta operator. This approach allows for the cancellation of primary terms, isolating the remainder as the error bound. Similarity was measured using the Wasserstein distance, which quantifies the "work" required to transform the discrete distribution into the continuous one.

Key Insights

The $O(1/n)$ Optimality

The paper proves that the error in the approximation shrinks at a rate of $1/n$. Crucially, the authors demonstrate through specific examples (notably Remark 3.1) that this rate is optimal. This provides a definitive answer regarding the efficiency of the Beta approximation for these types of reinforcement models.

The Arcsine Law and Random Walks

The Arcsine distribution is a special case of the Beta distribution, specifically $B(1/2, 1/2)$. The authors applied their general Beta bounds to simple symmetric random walks, specifically looking at the "Arcsine Law" which governs the fraction of time a walk spends on the positive side. This resulted in the first explicit constants for the Arcsine approximation of a walk's last return to zero.

Principal Results

  1. Theorem 1.1 (Urn Approximation): The paper provides a comprehensive Wasserstein bound for the Pólya-Eggenberger urn. This bound is expressed as a function of the initial parameters (white balls $\alpha$, black balls $\beta$) and the reinforcement parameter $m$.
  2. Theorem 1.2 (Random Walk Bounds): For a random walk of length $2n$, the distance $d_W$ between the last return time to zero and the Arcsine law is bounded by: $$d_W \leq \frac{27}{2n} + \frac{8}{n^2}$$ This result provides researchers with a concrete safety margin when applying the Arcsine law to real-world random walk data.

Conclusion and Future Directions

While the constants derived in this paper ($b_0, b_1$) are explicit, they remain mathematically complex and sensitive to the parameters $\alpha$ and $\beta$. Future work may focus on simplifying these constants for specific sub-cases to increase their utility for practitioners. Additionally, while the Wasserstein distance is a robust metric, extending these optimal bounds to the Kolmogorov distance—a more common metric in statistical look-up tables—remains an open area for research. Finally, the "density approach" developed here shows promise for application to other discrete models, such as preferential attachment graphs in network science.

Summary updated

Abstract

Using a characterizing equation for the Beta distribution, Stein's method is applied to obtain bounds of the optimal order for the Wasserstein distance between the distribution of the scaled number of white balls drawn from a Pólya-Eggenberger urn and its limiting Beta distribution. The bound is computed by making a direct comparison between characterizing operators of the target and the Beta distribution, the former derived by extending Stein's density approach to discrete distributions. In addition, refinements are given to Döbler's result [12] for the Arcsine approximation for the fraction of time a simple random walk of even length spends positive, and so also to the distributions of its last return time to zero and its first visit to its terminal point, by supplying explicit constants to the present Wasserstein bound and also demonstrating that its rate is of the optimal order.
BibTeX
@misc{goldstein2012stein,
  author = {Larry B. Goldstein and Gesine Reinert},
  title = {{Stein's method for the Beta distribution and the Pólya-Eggenberger Urn}},
  year = {2012},
  eprint = {1207.1460},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1207.1460},
}

Loading related content...

Figure