Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Stein's method and random character ratios

Author: Jason Fulman
Journal: Trans. Amer. Math. Soc. 360 (2008), 3687-3730
MSC (2000): Primary 05E10; Secondary 60C05
Published electronically: January 25, 2008
MathSciNet review: 2386242
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Stein's method is used to prove limit theorems for random character ratios. Tools are developed for four types of structures: finite groups, Gelfand pairs, twisted Gelfand pairs, and association schemes. As one example an error term is obtained for a central limit theorem of Kerov on the spectrum of the Cayley graph of the symmetric group generated by $ i$-cycles. Other main examples include an error term for a central limit theorem of Ivanov on character ratios of random projective representations of the symmetric group, and a new central limit theorem for the spectrum of certain random walks on perfect matchings. The results are obtained with very little information: a character formula for a single representation close to the trivial representation and estimates on two step transition probabilities of a random walk. The limit theorems stated in this paper are for normal approximation, but many of the tools developed are applicable for arbitrary distributional approximation.

References [Enhancements On Off] (What's this?)

  • 1. Aldous, D. and Diaconis, P., Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. 36 (1999), 413-432. MR 1694204 (2000g:60013)
  • 2. Bannai, E. and Ito, T., Algebraic combinatorics, I. Association schemes, Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984. MR 882540 (87m:05001)
  • 3. Borodin, A., Okounkov, A., and Olshanski, G., Asymptotics of Plancherel measure for symmetric groups, J. Amer. Math. Soc. 13 (2000), 481-515. MR 1758751 (2001g:05103)
  • 4. Borodin, A. and Olshanski, G., Z-measures on partitions and their scaling limits, European J. Combin. 26 (2005), 795-834. MR 2143199 (2006d:60018)
  • 5. Borodin, A. and Olshanski, G., Harmonic functions on multiplicative graphs and interpolation polynomials, Elecron. J. Combin. 7 (2000), Research paper 28, 39 pages. MR 1758654 (2001f:05160)
  • 6. Chatterjee, S. and Fulman, J., Exponential approximation by exchangeable pairs and spectral graph theory, (2006), preprint math.PR/0605552 at
  • 7. Deift, P., Integrable systems and combinatorial theory, Notices Amer. Math. Soc. 47 (2000), 631-640. MR 1764262 (2001g:05012)
  • 8. Diaconis, P., Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes, Volume 11, 1988. MR 964069 (90a:60001)
  • 9. Diaconis, P. and Holmes, S., Random walks on trees and matchings, Elec. J. Probab. 7 (2002), 17 pages (electronic). MR 1887626 (2002k:60025)
  • 10. Diaconis, P. and Shahshahani, M., Generating a random permutation with random transpositions, Z. Wahr. Verw. Gebiete 57 (1981), 159-179. MR 626813 (82h:60024)
  • 11. Durrett, R., Probability: Theory and examples, Second edition, Duxbury Press, Belmont, CA, 1996. MR 1609153 (98m:60001)
  • 12. Eskin, A. and Okounkov, A., Asymptotics of branched coverings of a torus and volumes of moduli spaces of holomorphic differentials, Invent. Math. 145 (2001), 59-103. MR 1839286 (2002g:32018)
  • 13. Eymard, P. and Roynette, B., Marches aléatoires sur le dual de SU(2), in Analyse harmonique sur les groupes de Lie, Springer Lecture Notes in Math, Volume 497 (1975), 108-152. MR 0423457 (54:11435)
  • 14. Fulman, J., Stein's method and Plancherel measure of the symmetric group, Transac. Amer. Math. Soc. 357 (2005), 555-570. MR 2095623 (2005e:05156)
  • 15. Fulman, J., Stein's method, Jack measure, and the Metropolis algorithm, J. Combin. Theory Ser. A 108 (2004), 275-296. MR 2098845 (2005h:60021)
  • 16. Fulman, J., An inductive proof of the Berry-Esseen theorem for character ratios, Ann. Combin. 10 (2006), 319-332. MR 2284273 (2007i:05189)
  • 17. Fulman, J., Martingales and character ratios, Trans. Amer. Math. Soc. 358 (2006), 4533-4552. MR 2231387 (2007e:05178)
  • 18. Gross, B., Some applications of Gelfand pairs to number theory, Bull. Amer. Math. Soc. 24 (1991), 277-301. MR 1074028 (91i:11055)
  • 19. Hanlon, P., Stanley, R., and Stembridge, J., Some combinatorial aspects of the spectra of normally distributed random matrices, in Hypergeometric functions on domains of positivity, Jack polynomials, and applications, Contemporary Mathematics, Volume 138 (1992), 151-174. MR 1199126 (93j:05164)
  • 20. Hoffman, P. and Humphreys, J., Projective representations of the symmetric group, Oxford University Press, New York, 1992. MR 1205350 (94f:20027)
  • 21. Hora, A., Central limit theorem for the adjacency operators on the infinite symmetric group, Comm. Math. Phys. 195 (1998), 405-416. MR 1637801 (99i:46058)
  • 22. Hora, A., Central limit theorems and asymptotic spectral analysis in large graphs, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 1 (1998), 221-246. MR 1628244 (99g:46089)
  • 23. Ivanov, V., The Gaussian limit for projective characters of large symmetric groups, J. Math. Sci. (N.Y.), 121 (2004), 2330-2344. Translated from Zap. Nauchn. Sem. POMI 283 (2001), 73-97. MR 1879064 (2002k:60061)
  • 24. Ivanov, V. and Olshanski, G., Kerov's central limit theorem for the Plancherel measure on Young diagrams, in Symmetric Functions 2001: Surveys of developments and perspectives, Kluwer Academic Publishers, Dodrecht, 2002.
  • 25. Johansson, K., Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math. 153 (2001), 259-296. MR 1826414 (2002g:05188)
  • 26. Kerov, S.V., Gaussian limit for the Plancherel measure of the symmetric group, Compt. Rend. Acad. Sci. Paris, Serie I 316 (1993), 303-308. MR 1204294 (93k:20106)
  • 27. Kerov, S.V., Anisotropic Young diagrams and Jack symmetric functions, Funct. Anal. Appl. 34 (2000), 41-51. MR 1756734 (2001f:05158)
  • 28. Letac, G., Les fonctions sphériques d'un couple de Gelfand symétrique et les chaînes de Markov, Adv. Appl. Probab. 14 (1982), 272-294. MR 650123 (83i:60078)
  • 29. Macdonald, I., Symmetric functions and Hall polynomials, Second edition, Oxford University Press, New York, 1995. MR 1354144 (96h:05207)
  • 30. Macwilliams, F. and Sloane, N., The theory of error-correcting codes, Elsevier Science B.V., Amsterdam, 1977.
  • 31. Matsumoto, S., Correlation functions of the shifted Schur measure, J. Math. Soc. Japan 57 (2005), 619-637. MR 2139724 (2006a:60013)
  • 32. Okounkov, A., Random matrices and random permutations, Internat. Math. Res. Notices 20 (2000), 1043-1095. MR 1802530 (2002c:15045)
  • 33. Okounkov, A., The uses of random partitions, XIVth International Congress on Mathematical Physics, 379-403, World Sci. Publ., Hackensack, NJ 2005. MR 2227852 (2007c:05013)
  • 34. Reinert, G., Couplings for normal approximations with Stein's method, in Microsurveys in discrete probability, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Volume 41 (1998), 193-207. MR 1630415 (99h:60043)
  • 35. Rinott, Y. and Rotar, V., On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted U-statistics, Ann. of Appl. Probab. 7 (1997), 1080-1105. MR 1484798 (99g:60050)
  • 36. Rinott, Y. and Rotar, V., Normal approximations by Stein's method, Decis. Econ. Finance 23 (2000), 15-29. MR 1780090 (2001h:60037)
  • 37. Sagan, B., The symmetric group. Representations, combinatorial algorithms, and symmetric functions, Second edition, Springer-Verlag, New York, 2001. MR 1824028 (2001m:05261)
  • 38. Serre, J-P., Linear representations of finite groups, Springer-Verlag, New York, 1977. MR 0450380 (56:8675)
  • 39. Shao, Q., and Su, Z., The Berry-Esseen bound for character ratios, Proc. Amer. Math. Soc. 134 (2006), 2153-2159. MR 2215787
  • 40. Sniady, P., Gaussian fluctuations of characters of symmetric groups and of Young diagrams, Probab. Theory Related Fields 136 (2006), 263-297. MR 2240789 (2007d:20020)
  • 41. Stein, C., Approximate computation of expectations, Institute of Mathematical Statistics Lecture Notes, Volume 7, 1986. MR 882007 (88j:60055)
  • 42. Stembridge, J., On Schur's Q-functions and the primitive idempotents of a commutative Hecke algebra, J. Algebraic Combin. 1 (1992), 71-95. MR 1162642 (93c:05113)
  • 43. Terras, A., Fourier analysis on finite groups and applications, London Math. Society Student Texts 43, Cambridge University Press, Cambridge, 1999. MR 1695775 (2000d:11003)
  • 44. Terras, A., Survey of spectra of Laplacians on finite symmetric spaces, Experiment. Math. 5 (1996), 15-32. MR 1412951 (97m:11154)
  • 45. Tracy, C. and Widom, H., A limit theorem for shifted Schur measures, Duke Math. Journal 123 (2004), 171-208. MR 2060026 (2006c:60028)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05E10, 60C05

Retrieve articles in all journals with MSC (2000): 05E10, 60C05

Additional Information

Jason Fulman
Affiliation: Department of Mathematics, University of Pittsburgh, Pittsburgh, Pennsylvania 15260
Address at time of publication: Department of Mathematics, University of Southern California, Los Angeles, California 90089-2532

Keywords: Stein's method, normal approximation, Gelfand pair, character ratio, symmetric group, Plancherel measure, association scheme
Received by editor(s): August 16, 2005
Received by editor(s) in revised form: May 13, 2006
Published electronically: January 25, 2008
Additional Notes: The author was supported by NSA grant H98230-05-1-0031 and NSF grant DMS-0503901.
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society