Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-27T09:46:44.310Z Has data issue: false hasContentIssue false
  • English
  • Français

Step Size in Stein's Method of Exchangeable Pairs

Published online by Cambridge University Press:  10 August 2009

NATHAN ROSS
NATHAN ROSS*
Affiliation:
Department of Mathematics, University of Southern California, 3620 South Vermont Avenue, KAP 108, Los Angeles, California 90089-2532, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Stein's method of exchangeable pairs is examined through five examples in relation to Poisson and normal distribution approximation. In particular, in the case where the exchangeable pair is constructed from a reversible Markov chain, we analyse how modifying the step size of the chain in a natural way affects the error term in the approximation acquired through Stein's method. It has been noted for the normal approximation that smaller step sizes may yield better bounds, and we obtain the first rigorous results that verify this intuition. For the examples associated to the normal distribution, the bound on the error is expressed in terms of the spectrum of the underlying chain, a characteristic of the chain related to convergence rates. The Poisson approximation using exchangeable pairs is less studied than the normal, but in the examples presented here the same principles hold.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 6 , November 2009 , pp. 979 - 1017
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Arratia, R., Goldstein, L. and Gordon, L. (1989) Two moments suffice for Poisson approximations: The Chen–Stein method. Ann. Probab. 17 9–25.CrossRefGoogle Scholar
[2]Arratia, R., Goldstein, L. and Gordon, L. (1990) Poisson approximation and the Chen–Stein method. Statist. Sci. 5 403–434.Google Scholar
[3]Askey, R. (1975) Orthogonal Polynomials and Special Functions, SIAM, Philadelphia, PA.CrossRefGoogle Scholar
[4]Baldi, P., Rinott, Y. and Stein, C. (1989) A normal approximation for the number of local maxima of a random function on a graph. In Probability, Statistics, and Mathematics, Academic Press, Boston, MA, pp. 59–81.Google Scholar
[5]Bannai, E. and Ito, T. (1984) Algebraic Combinatorics I: Association Schemes, Benjamin/Cummings, Menlo Park, CA.Google Scholar
[6]Barbour, A. D. and Chen, L. H. Y., eds (2005) An Introduction to Stein's Method, Vol. 4 of Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Singapore University Press.CrossRefGoogle Scholar
[7]Barbour, A. D., Holst, L. and Janson, S. (1992) Poisson Approximation, Vol. 2 of Oxford Studies in Probability, Clarendon Press, New York.CrossRefGoogle Scholar
[8]Bolthausen, E. (1984) An estimate of the remainder in a combinatorial central limit theorem. Z. Wahrsch. Verw. Gebiete 66 379–386.CrossRefGoogle Scholar
[9]Brémaud, P. (1999) Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues, Vol. 31 of Texts in Applied Mathematics. Springer, New York.Google Scholar
[10]Brown, T. C. and Phillips, M. J. (1999) Negative binomial approximation with Stein's method. Method. Comput. Appl. Probab. 1 407–421.CrossRefGoogle Scholar
[11]Chatterjee, S. (2008) A new method of normal approximation. Ann. Probab. 36 1584–1610.CrossRefGoogle Scholar
[12]Chatterjee, S. (2009) Fluctuations of eigenvalues and second order Poincaré inequalities. Probab. Theory Rel. Fields 143 1–40.CrossRefGoogle Scholar
[13]Chatterjee, S., Diaconis, P. and Meckes, E. (2005) Exchangeable pairs and Poisson approximation. Probab. Surv. 2 64–106 (electronic).CrossRefGoogle Scholar
[14]Chen, L. H. Y. and Shao, Q.-M. (2001) A non-uniform Berry–Esseen bound via Stein's method. Probab. Theory Rel. Fields 120 236–254.Google Scholar
[15]Chen, L. H. Y. and Shao, Q.-M. (2005) Stein's method for normal approximation. In An Introduction to Stein's Method, Singapore University Press, pp. 1–59.Google Scholar
[16]Diaconis, P. and Greene, C. (1989) Applications of Murphy's elements. Technical Report 335, Stanford University.Google Scholar
[17]Diaconis, P. and Shahshahani, M. (1981) Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 159–179.Google Scholar
[18]Eagleson, G. K. (1969) A characterization theorem for positive definite sequences on the Krawtchouk polynomials. Austral. J. Statist. 11 29–38.Google Scholar
[19]Fulman, J. (2004) Stein's method and non-reversible Markov chains. In Stein's Method: Expository Lectures and Applications, Vol. 46 of IMS Lecture Notes Monograph Series, Institute of Mathematical Statistics, pp. 69–77.Google Scholar
[20]Fulman, J. (2005) Stein's method and Plancherel measure of the symmetric group. Trans. Amer. Math. Soc. 357 555–570 (electronic).Google Scholar
[21]Fulman, J. (2008) Convergence rates of random walk on irreducible representations of finite groups. J. Theoret. Probab. 21 193–211.CrossRefGoogle Scholar
[22]Fulman, J. (2008) Stein's method and random character ratios. Trans. Amer. Math. Soc. 360 3687–3730.CrossRefGoogle Scholar
[23]Goldstein, L. (2005) Berry–Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing. J. Appl. Probab. 42 661–683.CrossRefGoogle Scholar
[24]Goldstein, L. and Reinert, G. (1997) Stein's method and the zero bias transformation with application to simple random sampling. Ann. Appl. Probab. 7 935–952.Google Scholar
[25]Goldstein, L. and Rinott, Y. (1996) Multivariate normal approximations by Stein's method and size bias couplings. J. Appl. Probab. 33 1–17.CrossRefGoogle Scholar
[26]Ingram, R. E. (1950) Some characters of the symmetric group. Proc. Amer. Math. Soc. 1 358–369.CrossRefGoogle Scholar
[27]Johnson, N. L., Kemp, A. W. and Kotz, S. (2005) Univariate Discrete Distributions, 3rd edn, Wiley Series in Probability and Statistics, Wiley-Interscience, Hoboken, NJ.CrossRefGoogle Scholar
[28]MacWilliams, F. J. and Sloane, N. J. A. (1977) The Theory of Error-Correcting Codes I, Vol. 16 of North-Holland Mathematical Library, North-Holland, Amsterdam.Google Scholar
[29]Reinert, G. (1998) Couplings for normal approximations with Stein's method. In Microsurveys in Discrete Probability (Princeton 1997), Vol. 41 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, Providence, RI, pp. 193–207.CrossRefGoogle Scholar
[30]Rinott, Y. and Rotar, V. (1997) 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 1080–1105.Google Scholar
[31]Rinott, Y. and Rotar, V. (2000) Normal approximations by Stein's method. Decis. Econ. Finance 23 15–29.CrossRefGoogle Scholar
[32]Röllin, A. (2007) Translated Poisson approximation using exchangeable pair couplings. Ann. Appl. Probab. 17 1596–1614.CrossRefGoogle Scholar
[33]Röllin, A. (2008) A note on the exchangeability condition in Stein's method. Statist. Probab. Lett. 78 (13) 1800–1806.Google Scholar
[34]Sagan, B. E. (2001) The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd edn, Vol. 203 of Graduate Texts in Mathematics, Springer, New York,Google Scholar
[35]Seneta, E. (2001) Characterization by orthogonal polynomial systems of finite Markov chains. J. Appl. Probab. 38A 42–52.CrossRefGoogle Scholar
[36]Stein, C. (1986) Approximate Computation of Expectations, Vol. 7 of IMS Lecture Notes Monograph Series, Institute of Mathematical Statistics, Hayward, CA.CrossRefGoogle Scholar