The calculation of precise probabilities in statistics, computer science, physics and biology under realistic model assumptions and sample sizes is often impractical, and approximation is typically required. Having a bound on the error of commonly used approximations is therefore necessary in many real applications. Stein’s method has proved itself to be a powerful tool in such situations.

The course will cover the fundamentals of Stein’s method, starting with the Poisson and Normal distributions to illustrate the construction of the Stein equation and the derivation of the properties required on its solution. A number of coupling methods for use in the Stein equation will be presented, as well as it use in cases of local dependence. In addition to the basic case of independence, a sampling of potential applications in the Poisson case includes head runs, sequence matching, the birthday and occupancy problems, the Poisson subset numbers, extreme score distributions, and statistics of random graphs, and in the Normal case hierarchical sequences, the combinatorial central limit theorem, simple random sampling, occurrences of patterns in permutations and graphs, coverage processes, the anti-voter model, cone measure projections, and the lightbulb process. Multivariate normal approximation will also be covered, and, time permitting, additional applications of Stein’s method to the Beta, Geometric, Exponential and other distributions.

The level and detailed content of the course will be determined along with the students according to their background and interests.

Prerequisite: At least one advanced course in probability.

Instructors: Larry Goldstein and Yosi Rinott

Students will find themselves better prepared for the course by reading the following introductory papers by ReinertRaic, and Rinott and Rotar.

Interview with Charles Stein

Course Notes

Structure and Evaluation

Lectures, Monday through Saturday mornings, 9:45-10:45, 11:00-12:00, Problem Sessions Monday through Friday 3-5:15 PM

  • Midterm, 30% Tuesday July 9th, afternoon session.
  • Final Exam, 45% Wednesday July 17th, to be discussed Thurday July 18th
  • Homework and course participation, 25%
Main Materials

Fundamentals of Stein’s Method
Ross, N.

Normal Approximation by Stein’s Method
Chen, L., Goldstein, L., and Shao, Q.M.
Springer Verlag, 2010 [Springer Link]

Poisson Approximation
Barbour, A.D., Holst, L., and Janson, S.
Oxford Science Publications, 1992
MR1163825 (93g:60043)

Additional References

Two Moments Suffice for Poisson Approximations: The Chen-Stein Method
Arratia, R., Goldstein, L., and Gordon, L.
The Annals of Probability, Vol. 17, No. 1. (Jan., 1989), pp. 9-25
MR0972770 (90b:60021) [pdf]

Poisson Approximation and the Chen-Stein Method
Arratia; R., Goldstein, L. and Gordon, L.
Statistical Science, Vol. 5, No. 4. (Nov., 1990), pp. 403-424.
MR1092983 (92e:62036) [pdf]

Approximations to profile score distributions.
Goldstein, L. and Waterman, M.
Journal of Computational Biology, vol. 1, No. 1 (1994), pp. 93-104.

Total Variation Distance for Poisson Subset Numbers
Goldstein, L, and Reinert, G.
Annals of Combinatorics (2006), vol 10, pp. 333–341

On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted U-statistics.
Rinott, Y., Rotar, V.
Ann. Appl. Probab. 7 (1997), no. 4, 1080–1105.
MR1484798 [pdf]

Multivariate normal approximations by Stein’s method and size bias couplings.
Goldstein, L, and Rinott, Y.
J. Appl. Probab. (1996), vol 33, pp. 1–17.

A Permutation Test for Matching
Goldstein, L. and Rinott, Y.
Metron vol 61, (2003), no. 3, pp. 375-388 (2004).

Normal approximation for coverage models over binomial point processes
Goldstein, L., and Penrose, M. D.
Annals of Applied Probability (2010), vol 20, pp. 696-721.
[pdf][arXiv:0812.3084][project Euclid]

On The Number of Pure Strategy Nash Equilibria in Random Games
Rinott, Y. and Scarsini, M. (2000)
Games and Economic Behavior 33, 274-293.

A multivariate CLT for local dependence with n^-1/2 log n rate.
Rinott, Y. and Rotar, V. (1997).
J. Multivariate analysis 56 (1996) 333-350

Some examples of Normal approximations by Stein’s method.
Dembo, A. and Rinott Y. (1996).
In Random Discrete Structures, IMA volume 76, 25-44. Aldous, D. and Pemantle, R. Eds., Springer-verlag.

A normal approximations for the number of local maxima of a random function on a graph.
Baldi, P., Rinott, Y. and Stein, C. (1989).
Probability, Statistics and Mathematics, Papers in Honor of Samuel Karlin. T. W. Anderson, K.B. Athreya and D. L. Iglehart eds., Academic Press, 59-81.

On normal approximations of distributions in terms of dependency graphs.
Baldi, P. and Rinott, Y. (1989)
Annals of Probability 17, 1646-1650.

Asymptotic normality of some graph related statistics
Baldi, P. and Rinott, Y. (1989)
J. Applied Probability, 26, 171-175.

On normal approximation rates for certain sums of dependent random variables.
Rinott, Y. (1994).
J. Computational and Applied Math. 55 135–143

A Probabilistic Proof of the Lindeberg-Feller Central Limit Theorem
Goldstein, L.
American Mathematical Monthly (2009), vol 116, pp. 45–60

Bounds on the Constant in the Mean Central Limit Theorem
Goldstein, L.
Annals of Probability (2010), vol 38, pp. 1672-1689.

Degree asymptotics with rates for preferential attachment random graphs
Peköz, E., Röllin, A., and Ross, Nathan R.

Notes of a Course in Stein’s Method given by Sourav Chatterjee at Berkeley

Publication pages of Larry Goldstein and Yosi Rinott