Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 2 (2005) open journal systems 

Exchangeable pairs and Poisson approximation

Sourav Chatterjee, Stanford University
Persi Diaconis, Stanford University
Elizabeth Meckes, Stanford University

This is a survery paper on Poisson approximation using Stein's method of exchangeable pairs. We illustrate using Poisson-binomial trials and many variations on three classical problems of combinatorial probability: the matching problem, the coupon collector's problem, and the birthday problem. While many details are new, the results are closely related to a body of work developed by Andrew Barbour, Louis Chen, Richard Arratia, Lou Gordon, Larry Goldstein, and their collaborators. Some comparison with these other approaches is offered.

Creative Common LOGO

Full Text: PDF

Chatterjee, Sourav, Diaconis, Persi, Meckes, Elizabeth, Exchangeable pairs and Poisson approximation, Probability Surveys, 2, (2005), 64-106 (electronic).


[1]   D. Aldous. Probability Approximations via the Poisson Clumping Heuristic, volume 77 of Applied Mathematical Sciences. Springer-Verlag, New York, 1989. MR969362

[2]   R. Arratia, A. D. Barbour, and S. Tavaré. Logarithmic Combinatorial Structures: a Probabilistic Approach. EMS Monographs in Mathematics. European Mathematical Society (EMS), Zürich, 2003. MR2032426

[3]   R. Arratia, L. Goldstein, and L. Gordon. Two moments suffice for Poisson approximations: the Chen-Stein method. Ann. Probab., 17(1):9–25, 1989. MR972770

[4]   R. Arratia, L. Goldstein, and L. Gordon. Poisson approximation and the Chen-Stein method. Statist. Sci., 5(4):403–434, 1990. With comments and a rejoinder by the authors. MR1092983

[5]   A. Barbour. Stein’s method and Poisson process convergence. J. Appl. Probab., Special Vol. 25A:175–184, 1988. MR974580

[6]   A. D. Barbour, L. H. Y. Chen, and K. P. Choi. Poisson approximation for unbounded functions. I. Independent summands. Statist. Sinica, 5(2):749–766, 1995. MR1347617

[7]   A. D. Barbour and G. K. Eagleson. Poisson approximation for some statistics based on exchangeable trials. Adv. in Appl. Probab., 15(3):585–600, 1983. MR706618

[8]   A. D. Barbour, L. Holst, and S. Janson. Poisson Approximation, volume 2 of Oxford Studies in Probability. The Clarendon Press Oxford University Press, New York, 1992. Oxford Science Publications. MR1163825

[9]   T. C. Brown and D. Greig. Poisson approximation for point processes via monotone couplings. Ann. Appl. Probab., 6(2):545–560, 1996. MR1398057

[10]   T. C. Brown and A. Xia. On metrics in point process approximation. Stochastics Stochastics Rep., 52(3-4):247–263, 1995. MR1381671

[11]   T. C. Brown and A. Xia. On Stein-Chen factors for Poisson approximation. Statist. Probab. Lett., 23(4):327–332, 1995. MR1342742

[12]   M. Camarri and J. Pitman. Limit distributions and random trees derived from the birthday problem with unequal probabilities. Electron. J. Probab., 5:no. 2, 18 pp. (electronic), 2000. MR1741774

[13]   L. H. Y. Chen. On the convergence of Poisson binomial to Poisson distributions. Ann. Probability, 2(1):178–180, 1974. MR370693

[14]   L. H. Y. Chen. Poisson approximation for dependent trials. Ann. Probability, 3(3):534–545, 1975. MR428387

[15]   L. H. Y. Chen and A. Xia. Stein’s method, Palm theory and Poisson process approximation. Ann. Probab., 32(3B):2545–2569, 2004. MR2078550

[16]   D. E. Critchlow. Metric Methods for Analyzing Partially Ranked Data, volume 34 of Lecture Notes in Statistics. Springer-Verlag, Berlin, 1985. MR818986

[17]   F. N. David and D. E. Barton. Combinatorial Chance. Hafner Publishing Co., New York, 1962. MR155371

[18]   P. R. de Montmort. Essay d’Analyse sur les Jeux de Hazard. Chelsea Publishing Co., New York, second edition, 1980. MR605303

[19]   P. Diaconis. Group Representations in Probability and Statistics. Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988. MR964069

[20]   P. Diaconis. Conditioned approximations: a survey. Preprint, Dept. of Statistics, Stanford Univ., 2004.

[21]   P. Diaconis, R. Graham, and S. P. Holmes. Statistical problems involving permutations with restricted positions. In State of the Art in Probability and Statistics (Leiden, 1999), volume 36 of IMS Lecture Notes Monogr. Ser., pages 195–222. Inst. Math. Statist., Beachwood, OH, 2001. MR1836562

[22]   P. Diaconis and S. Holmes. A Bayesian peek into Feller volume I. Sankhyˉa  Ser. A, 64(3, part 2):820–841, 2002. Special issue in memory of D. Basu. MR1981513

[23]   P. Diaconis and S. Holmes. Stein’s Method: Expository Lectures and Applications. Institute of Mathematical Statistics, Beachwood, Ohio, 2004.

[24]   P. Diaconis and A. Ram. Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques. Michigan Math. J., 48:157–190, 2000. Dedicated to William Fulton on the occasion of his 60th birthday. MR1786485

[25]   T. Erhardsson. Compound Poisson approximation for Markov chains using Stein’s method. Ann. Probab., 27(1):565–596, 1999. MR1681149

[26]   W. Feller. An Introduction to Probability Theory and its Applications. Vol. I. Third edition. John Wiley & Sons Inc., New York, 1968. MR228020

[27]   M. Fligner and J. Verducci. Probability Models and Statistical Analyses for Ranking Data. Springer Verlag, New York, 1993. MR1237197

[28]   J. Fulman. Stein’s method and non-reversible markov chains. In Stein’s Method: Expository Lectures and Applications, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 46, pages 69–78. Institute of Mathematical Statistics, Beachwood, Ohio, 2004.

[29]   E. N. Gilbert and H. O. Pollak. Coincidences in Poisson patterns. Bell System Technical J., 36:1005–1033, 1957.

[30]   L. Goldstein and G. Reinert. Stein’s method and the zero bias transformation with application to simple random sampling. Ann. Appl. Probab., 7(4):935–952, 1997. MR1484792

[31]   P. Hall. Introduction to the Theory of Coverage Processes. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons Inc., New York, 1988. MR973404

[32]   S. Janson. Random coverings in several dimensions. Acta Math., 156(1-2):83–118, 1986. MR822331

[33]   I. Kaplansky. Symbolic solution of certain problems in permutations. Bull. Amer. Math. Soc., 50:906–914, 1944. MR11393

[34]   M. Kendall and J. D. Gibbons. Rank Correlation Methods. A Charles Griffin Title. Edward Arnold, London, fifth edition, 1990. MR1079065

[35]   J. E. Kennedy and M. P. Quine. The total variation distance between the binomial and Poisson distributions. Ann. Probab., 17(1):396–400, 1989. MR972796

[36]   J. F. C. Kingman. Poisson Processes, volume 3 of Oxford Studies in Probability. The Clarendon Press Oxford University Press, New York, 1993. Oxford Science Publications. MR1207584

[37]   V. F. Kolchin, B. A. Sevastyanov, and V. P. Chistyakov. Random Allocations. V. H. Winston & Sons, Washington, D.C., 1978. Translated from the Russian, Translation edited by A. V. Balakrishnan, Scripta Series in Mathematics. MR471016

[38]   S. Kounias. Poisson approximation and Bonferroni bounds for the probability of the union of events. Internat. J. Math. Statist. Sci., 4(1):43–52, 1995. MR1380554

[39]   T. G. Kurtz. Strong approximation theorems for density dependent Markov chains. Stochastic Processes Appl., 6(3):223–240, 1977/78. MR464414

[40]   T. G. Kurtz. Representation and approximation of counting processes. In Advances in Filtering and Optimal Stochastic Control (Cocoyoc, 1982), volume 42 of Lecture Notes in Control and Inform. Sci., pages 177–191. Springer, Berlin, 1982. MR794515

[41]   M. Penrose. Random Geometric Graphs, volume 5 of Oxford Studies in Probability. Oxford University Press, Oxford, 2003. MR1986198

[42]   O. E. Percus and J. K. Percus. Probability bounds on the sum of independent nonidentically distributed binomial random variables. SIAM J. Appl. Math., 45(4):621–640, 1985. MR796099

[43]   J. Pitman. Probabilistic bounds on the coefficients of polynomials with only real zeros. J. Combin. Theory Ser. A, 77(2):279–303, 1997. MR1429082

[44]   S. I. Resnick. Extreme Values, Regular Variation, and Point Processes, volume 4 of Applied Probability. A Series of the Applied Probability Trust. Springer-Verlag, New York, 1987. MR900810

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

[46]   J. Riordan. An Introduction to Combinatorial Analysis. Wiley Publications in Mathematical Statistics. John Wiley & Sons Inc., New York, 1958. MR96594

[47]   B. Rosén. On the coupon collector’s waiting time. Ann. Math. Statist., 41:1952–1969, 1970. MR268929

[48]   R. P. Stanley. Enumerative Combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR1676282

[49]   C. Stein. Application of Newton’s identities to the Poisson binomial distribution. Technical Report 354, Dept. of Statistics, Stanford Univ., 1978.

[50]   C. Stein. Asymptotic evaluation of the number of Latin rectangles. J. Combin. Theory Ser. A, 25(1):38–49, 1978. MR499035

[51]   C. Stein. Approximate Computation of Expectations. Institute of Mathematical Statistics Lecture Notes—Monograph Series, 7. Institute of Mathematical Statistics, Hayward, CA, 1986. MR882007

[52]   C. Stein. A way of using auxiliary randomization. In Probability Theory (Singapore, 1989), pages 159–180. de Gruyter, Berlin, 1992. MR1188718

[53]   L. Takács. The problem of coincidences. Arch. Hist. Exact Sci., 21(3):229–244, 1979/80. MR575716

Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787