Stein’s method and random character ratios
HTML articles powered by AMS MathViewer
- by Jason Fulman PDF
- Trans. Amer. Math. Soc. 360 (2008), 3687-3730 Request permission
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
- David Aldous and Persi Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. (N.S.) 36 (1999), no. 4, 413–432. MR 1694204, DOI 10.1090/S0273-0979-99-00796-X
- Eiichi Bannai and Tatsuro Ito, Algebraic combinatorics. I, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984. Association schemes. MR 882540
- Alexei Borodin, Andrei Okounkov, and Grigori Olshanski, Asymptotics of Plancherel measures for symmetric groups, J. Amer. Math. Soc. 13 (2000), no. 3, 481–515. MR 1758751, DOI 10.1090/S0894-0347-00-00337-4
- Alexei Borodin and Grigori Olshanski, $Z$-measures on partitions and their scaling limits, European J. Combin. 26 (2005), no. 6, 795–834. MR 2143199, DOI 10.1016/j.ejc.2004.06.003
- Alexei Borodin and Grigori Olshanski, Harmonic functions on multiplicative graphs and interpolation polynomials, Electron. J. Combin. 7 (2000), Research Paper 28, 39. MR 1758654
- Chatterjee, S. and Fulman, J., Exponential approximation by exchangeable pairs and spectral graph theory, (2006), preprint math.PR/0605552 at http://xxx.lanl.gov.
- Percy Deift, Integrable systems and combinatorial theory, Notices Amer. Math. Soc. 47 (2000), no. 6, 631–640. MR 1764262
- Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069
- Persi Diaconis and Susan P. Holmes, Random walks on trees and matchings, Electron. J. Probab. 7 (2002), no. 6, 17. MR 1887626, DOI 10.1214/EJP.v7-105
- Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179. MR 626813, DOI 10.1007/BF00535487
- Richard Durrett, Probability: theory and examples, 2nd ed., Duxbury Press, Belmont, CA, 1996. MR 1609153
- Alex Eskin and Andrei Okounkov, Asymptotics of numbers of branched coverings of a torus and volumes of moduli spaces of holomorphic differentials, Invent. Math. 145 (2001), no. 1, 59–103. MR 1839286, DOI 10.1007/s002220100142
- Pierre Eymard and Bernard Roynette, Marches aléatoires sur le dual de $SU(2)$, Analyse harmonique sur les groupes de Lie (Sém. Nancy-Strasbourg, 1973–75), Lecture Notes in Math., Vol. 497, Springer, Berlin, 1975, pp. 108–152 (French). MR 0423457
- Jason Fulman, Stein’s method and Plancherel measure of the symmetric group, Trans. Amer. Math. Soc. 357 (2005), no. 2, 555–570. MR 2095623, DOI 10.1090/S0002-9947-04-03499-3
- Jason Fulman, Stein’s method, Jack measure, and the Metropolis algorithm, J. Combin. Theory Ser. A 108 (2004), no. 2, 275–296. MR 2098845, DOI 10.1016/j.jcta.2004.07.003
- Jason Fulman, An inductive proof of the Berry-Esseen theorem for character ratios, Ann. Comb. 10 (2006), no. 3, 319–332. MR 2284273, DOI 10.1007/s00026-006-0290-x
- Jason Fulman, Martingales and character ratios, Trans. Amer. Math. Soc. 358 (2006), no. 10, 4533–4552. MR 2231387, DOI 10.1090/S0002-9947-06-03865-7
- Benedict H. Gross, Some applications of Gel′fand pairs to number theory, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 2, 277–301. MR 1074028, DOI 10.1090/S0273-0979-1991-16017-9
- Philip J. Hanlon, Richard P. Stanley, and John R. Stembridge, Some combinatorial aspects of the spectra of normally distributed random matrices, Hypergeometric functions on domains of positivity, Jack polynomials, and applications (Tampa, FL, 1991) Contemp. Math., vol. 138, Amer. Math. Soc., Providence, RI, 1992, pp. 151–174. MR 1199126, DOI 10.1090/conm/138/1199126
- P. N. Hoffman and J. F. Humphreys, Projective representations of the symmetric groups, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1992. $Q$-functions and shifted tableaux; Oxford Science Publications. MR 1205350
- Akihito Hora, Central limit theorem for the adjacency operators on the infinite symmetric group, Comm. Math. Phys. 195 (1998), no. 2, 405–416. MR 1637801, DOI 10.1007/s002200050395
- Akihito Hora, Central limit theorems and asymptotic spectral analysis on large graphs, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 1 (1998), no. 2, 221–246. MR 1628244, DOI 10.1142/S0219025798000144
- V. N. Ivanov, The Gaussian limit for projective characters of large symmetric groups, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 283 (2001), no. Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 6, 73–97, 259 (Russian, with English and Russian summaries); English transl., J. Math. Sci. (N.Y.) 121 (2004), no. 3, 2330–2344. MR 1879064, DOI 10.1023/B:JOTH.0000024615.07311.fe
- 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.
- Kurt Johansson, Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math. (2) 153 (2001), no. 1, 259–296. MR 1826414, DOI 10.2307/2661375
- Serguei Kerov, Gaussian limit for the Plancherel measure of the symmetric group, C. R. Acad. Sci. Paris Sér. I Math. 316 (1993), no. 4, 303–308 (English, with English and French summaries). MR 1204294
- S. V. Kerov, Anisotropic Young diagrams and symmetric Jack functions, Funktsional. Anal. i Prilozhen. 34 (2000), no. 1, 51–64, 96 (Russian, with Russian summary); English transl., Funct. Anal. Appl. 34 (2000), no. 1, 41–51. MR 1756734, DOI 10.1007/BF02467066
- Gérard Letac, Les fonctions sphériques d’un couple de Gel′fand symétrique et les chaînes de Markov, Adv. in Appl. Probab. 14 (1982), no. 2, 272–294 (French, with English summary). MR 650123, DOI 10.2307/1426521
- I. G. Macdonald, Symmetric functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR 1354144
- Macwilliams, F. and Sloane, N., The theory of error-correcting codes, Elsevier Science B.V., Amsterdam, 1977.
- Sho Matsumoto, Correlation functions of the shifted Schur measure, J. Math. Soc. Japan 57 (2005), no. 3, 619–637. MR 2139724
- Andrei Okounkov, Random matrices and random permutations, Internat. Math. Res. Notices 20 (2000), 1043–1095. MR 1802530, DOI 10.1155/S1073792800000532
- Andrei Okounkov, The uses of random partitions, XIVth International Congress on Mathematical Physics, World Sci. Publ., Hackensack, NJ, 2005, pp. 379–403. MR 2227852
- Gesine Reinert, Couplings for normal approximations with Stein’s method, Microsurveys in discrete probability (Princeton, NJ, 1997) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 41, Amer. Math. Soc., Providence, RI, 1998, pp. 193–207. MR 1630415, DOI 10.1089/cmb.1998.5.223
- Yosef Rinott and Vladimir 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 (1997), no. 4, 1080–1105. MR 1484798, DOI 10.1214/aoap/1043862425
- Yosef Rinott and Vladimir Rotar, Normal approximations by Stein’s method, Decis. Econ. Finance 23 (2000), no. 1, 15–29. MR 1780090, DOI 10.1007/s102030050003
- Bruce E. Sagan, The symmetric group, 2nd ed., Graduate Texts in Mathematics, vol. 203, Springer-Verlag, New York, 2001. Representations, combinatorial algorithms, and symmetric functions. MR 1824028, DOI 10.1007/978-1-4757-6804-6
- Jean-Pierre Serre, Linear representations of finite groups, Graduate Texts in Mathematics, Vol. 42, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott. MR 0450380
- Qi-Man Shao and Zhong-Gen Su, The Berry-Esseen bound for character ratios, Proc. Amer. Math. Soc. 134 (2006), no. 7, 2153–2159. MR 2215787, DOI 10.1090/S0002-9939-05-08177-3
- Piotr Śniady, Gaussian fluctuations of characters of symmetric groups and of Young diagrams, Probab. Theory Related Fields 136 (2006), no. 2, 263–297. MR 2240789, DOI 10.1007/s00440-005-0483-y
- Charles Stein, Approximate computation of expectations, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 7, Institute of Mathematical Statistics, Hayward, CA, 1986. MR 882007
- John R. Stembridge, On Schur’s $Q$-functions and the primitive idempotents of a commutative Hecke algebra, J. Algebraic Combin. 1 (1992), no. 1, 71–95. MR 1162642, DOI 10.1023/A:1022485331028
- Audrey Terras, Fourier analysis on finite groups and applications, London Mathematical Society Student Texts, vol. 43, Cambridge University Press, Cambridge, 1999. MR 1695775, DOI 10.1017/CBO9780511626265
- Audrey Terras, Survey of spectra of Laplacians on finite symmetric spaces, Experiment. Math. 5 (1996), no. 1, 15–32. MR 1412951
- Craig A. Tracy and Harold Widom, A limit theorem for shifted Schur measures, Duke Math. J. 123 (2004), no. 1, 171–208. MR 2060026, DOI 10.1215/S0012-7094-04-12316-4
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
- MR Author ID: 332245
- Email: fulman@usc.edu
- 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.
- © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 360 (2008), 3687-3730
- MSC (2000): Primary 05E10; Secondary 60C05
- DOI: https://doi.org/10.1090/S0002-9947-08-04371-7
- MathSciNet review: 2386242