Stein's Method and Applications

The following sections are included:

• CONTENTS

• FOREWORD

• PREFACE

• CHARLES STEIN – PHOTOGRAPHS

• MEMORIES OF THE STEIN WORKSHOP – PHOTOGRAPHS

Given any mean zero, finite variance σ² random variable W, there exists a unique distribution on a variable W* such that EW f(W) = σ²Ef′(W*) for all absolutely continuous functions f for which these expectations exist. This distributional ‘zero bias’ transformation of W to W*, of which the normal is the unique fixed point, was introduced in Goldstein & Reinert (1997) to obtain bounds in normal approximations. After providing some background on the zero bias transformation in one dimension, we extend its definition to higher dimension and illustrate with an application to the normal approximation of sums of vectors obtained by simple random sampling.

We examine the number of appearances of certain types of events in a sequence of independent (but not necessarily identical) trials. We introduce a concept of Renewal which, in this context, in certain ways generalizes Feller's Theory. Under quite general conditions, Poisson limit theorems are obtained, which extend known results. Key tools in that are Stein-Chen method and probabilistic arguments.

We use Stein's method to obtain bounds on the rate of convergence for a class of statistics in geometric probability obtained as a sum of contributions from Poisson points which are exponentially stabilizing, i.e. locally determined in a certain sense. Examples include statistics such as total edge length and total number of edges of graphs in computational geometry and the total number of particles accepted in random sequential packing models. These rates also apply to the 1-dimensional marginals of the random measures associated with these statistics.

This paper concerns an approach to providing rates and asymptotic expansions in the CLT, based on the representation

where f is an arbitrary r times differentiable function, f^(m) is its mth derivative, W is a r.v. with finite first r + 1 moments, γm is the m-th cumulant of W or a characteristic close to it, and R is a remainder which may be small under suitable conditions. If W is a sum of r.v.'s, a good bound for the remainder should reflect the dependency structure between the summands. We review and discuss here known results on such bounds, and provide a new result that essentially widens possibilities of applications.

In dependent systems, rare events have a tendency to appear in clusters which make Poisson distribution a less favourable model as approximation errors are too large to use. For such situations, a compound Poisson distribution seems to be a more suitable choice. Stein's method for the compound Poisson approximation was introduced in Barbour, Chen & Loh (1992) but the approach yields relatively useful Stein factors only when the approximating compound Poisson distribution satisfies jλ_j↓ 0 as j → ∞ where N_j ~ Po (λ_j), j ≥ 1 are independent, because under this condition, a Markov immigration-death process with multiple births and unit per capita death can be brought in to estimate the Stein factors. In this paper, we present a framework of Stein's method for the compound Poisson approximation using immigration-death processes with multiple births and multiple deaths, as well as some preliminary studies on this approach.

Assume that is a Poisson point process of intensity 1 in . Let be a minimal spanning tree (MST) on and let be the independence number of , i.e., the size of largest independent sets. In this paper, we prove a central limit theorem for .

We show (leaving out most of the details) how Stein's method can be used to obtain bounds for the total variation distance between the distribution of the number of points in (0,t] of a stationary finite-state Markov renewal point process, and a compound Poisson distribution. Two bounds are presented, of which the first makes use of an embedded renewal-reward process, where visits to a particular single state serve as renewals. For the second bound, the original point process is first embedded into a process of the same kind, but with an added state, representing “loss of memory” in the original process. An explicit expression for the second bound is given for the case when the original process is a renewal process.

The paper is concerned with the accuracy in total variation of the approximation of the distribution of a sum of independent Bernoulli distributed random d–vectors by the product distribution with Poisson marginals which has the same mean. The best results, obtained using generating function methods, are those of Roos (1998, 1999). Stein's method has so far yielded somewhat weaker bounds. We demonstrate why a direct approach using Stein's method cannot emulate Roos's results, but give some less direct arguments to show that it is possible, using Stein's method, to get very close.

Let {X_i, 1 ≤ i ≤ n} be independent random variables with zero means and finite second moments. Bentkus, Bloznelis & Götze (1996) obtained the Berry-Esseen bound for the Student t-statistic with an unspecified absolute constant. In this note we use Stein's method to give a direct proof of the bound with an explicit absolute constant.

We show that the number of maxima in random, samples taken from [0, 1]^d is asymptotically normally distributed. The method of proof relies on Stein's method and gives a convergence rate.

Two methods are used to compute the expected value of the length of the minimal spanning tree (MST) of a graph whose edges are assigned lengths which are independent and uniformly distributed. The first method yields an exact formula in terms of the Tutte polynomial. As an illustration, the expected length of the MST of the Petersen graph is found to be 34877/12012 = 2.9035… A second, more elementary, method for computing the expected length of the MST is then derived by conditioning on the length of the shortest edge. Both methods in principle apply to any finite graph. To illustrate the method we compute the expected lengths of the MSTs for complete graphs.

We study two classical ensembles of random matrices introduced by Wigner and Wishart. We discuss Stein's method for the asymptotic approximation of expectations of functions of the normalized eigenvalue counting measure of high dimensional matrices. The method is based on differential equations for the densities of the limit laws.

Inspired by Stein's theory in mathematical statistics, we show that the Wiener measure on the pinned path space over a compact Riemannian manifold is uniquely characterized by its integration by parts formula among the set of probability measures on the path space for which the coordinate process is a semimartingale. Because of the presence of the curvature, the usual proof will not be readily extended to this infinite dimensional setting. Instead, we show that the integration by parts formula implies that the stochastic anti-development of the coordinate process satisfies Lévy's criterion.

This article gives a brief survey of some of the popular unbiased randomized quadrature rules that have been proposed in the statistical literature. In particular, the asymptotic distributions (as well as other related properties) of the sample means based on Latin hypercube sampling, randomized orthogonal arrays and scrambled nets are discussed.

Many statistics used to test for association between pairs (y_i, z_i) of multivariate observations, sampled from n individuals in a population, are based on comparing the similarity a_ij of each pair (i, j) of individuals, as evidenced by the values y_i and y_j, with their similarity b_ij based on the values z_i, and Z_j. A common strategy is to compute the sample correlation between these two sets of values. The appropriate null hypothesis distribution is that derived by permuting the z_i's at random among the individuals, while keeping the y_i's fixed. In this paper, a Berry–Esseen bound for the normal approximation to this null distribution is derived, which is useful even when the matrices a and b are relatively sparse, as is the case in many applications. The proofs are based on constructing a suitable exchangeable pair, a technique at the heart of Stein's method.

Under certain conditions, sums of functions of subtrees of a random binary search tree are asymptotically normal. We show how Stein's method can be applied to study these random trees, and survey methods for obtaining limit laws for such functions of subtrees.