×

zbMATH — the first resource for mathematics

A probabilistic interpretation of the Macdonald polynomials. (English) Zbl 1255.05194
Summary: The two-parameter Macdonald polynomials are a central object of algebraic combinatorics and representation theory. We give a Markov chain on partitions of \(k\) with eigenfunctions the coefficients of the Macdonald polynomials when expanded in the power sum polynomials. The Markov chain has stationary distribution a new two-parameter family of measures on partitions, the inverse of the Macdonald weight (rescaled). The uniform distribution on cycles of permutations and the Ewens sampling formula are special cases. The Markov chain is a version of the auxiliary variables algorithm of statistical physics. Properties of the Macdonald polynomials allow a sharp analysis of the running time. In natural cases, a bounded number of steps suffice for arbitrarily large \(k\).

MSC:
05E05 Symmetric functions and generalizations
05E10 Combinatorial aspects of representation theory
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Aldous, D. and Diaconis, P. (1999). Longest increasing subsequences: From patience sorting to the Baik-Deift-Johansson theorem. Bull. Amer. Math. Soc. ( N.S. ) 36 413-432. · Zbl 0937.60001 · doi:10.1090/S0273-0979-99-00796-X
[2] Aldous, D. J. (1999). Deterministic and stochastic models for coalescence (aggregation and coagulation): A review of the mean-field theory for probabilists. Bernoulli 5 3-48. · Zbl 0930.60096 · doi:10.2307/3318611
[3] Andersen, H. C. and Diaconis, P. (2007). Hit and run as a unifying device. J. Soc. Fr. Stat. & Rev. Stat. Appl. 148 5-28.
[4] Andrews, G. E. (1998). The Theory of Partitions . Cambridge Univ. Press, Cambridge. · Zbl 0996.11002
[5] Arratia, R., Barbour, A. D. and Tavaré, S. (2003). Logarithmic Combinatorial Structures : A Probabilistic Approach . Eur. Math. Soc., Zürich. · Zbl 1040.60001
[6] Assaf, S. H. (2007). Dual equivalence graphs, ribbon tableaux and Macdonald polynomials. Ph.D. thesis, Dept. Mathematics, Univ. California, Berkeley.
[7] Awata, H., Kubo, H., Odake, S. and Shiraishi, J. (1996). Quantum \({\mathscr{W}}_{N}\) algebras and Macdonald polynomials. Comm. Math. Phys. 179 401-416. · Zbl 0873.17016 · doi:10.1007/BF02102595
[8] Bertoin, J. (2006). Random Fragmentation and Coagulation Processes. Cambridge Studies in Advanced Mathematics 102 . Cambridge Univ. Press, Cambridge. · Zbl 1107.60002 · doi:10.1017/CBO9780511617768
[9] Betz, V., Ueltschi, D. and Velenik, Y. (2011). Random permutations with cycle weights. Ann. Appl. Probab. 21 312-331. · Zbl 1226.60130 · doi:10.1214/10-AAP697
[10] Billingsley, P. (1972). On the distribution of large prime divisors. Period. Math. Hungar. 2 283-289. · Zbl 0242.10033 · doi:10.1007/BF02018667
[11] Borgs, C., Chayes, J. T., Frieze, A., Kim, J. H., Tetali, P., Vigoda, E. and Vu, V. H. (1999). Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics. In 40 th Annual Symposium on Foundations of Computer Science ( New York , 1999) 218-229. IEEE Comput. Soc., Los Alamitos, CA.
[12] Borodin, A., Okounkov, A. and Olshanski, G. (2000). Asymptotics of Plancherel measures for symmetric groups. J. Amer. Math. Soc. 13 481-515 (electronic). · Zbl 0938.05061 · doi:10.1090/S0894-0347-00-00337-4
[13] Brémaud, P. (1999). Markov Chains : Gibbs Fields , Monte Carlo Simulation , and Queues. Texts in Applied Mathematics 31 . Springer, New York. · Zbl 0949.60009
[14] Ceccherini-Silberstein, T., Scarabotti, F. and Tolli, F. (2008). Harmonic Analysis on Finite Groups : Representation Theory , Gelfand Pairs and Markov Chains. Cambridge Studies in Advanced Mathematics 108 . Cambridge Univ. Press, Cambridge. · Zbl 1149.43001
[15] Cherednik, I. (1992). Double affine Hecke algebras, Knizhnik-Zamolodchikov equations, and Macdonald’s operators. Int. Math. Res. Not. IMRN 9 171-180. · Zbl 0770.17004 · doi:10.1155/S1073792892000199
[16] Diaconis, P. and Hanlon, P. (1992). Eigen-analysis for some examples of the Metropolis algorithm. In Hypergeometric Functions on Domains of Positivity , Jack Polynomials , and Applications ( Tampa , FL , 1991). Contemporary Mathematics 138 99-117. Amer. Math. Soc., Providence, RI. · Zbl 0789.05091 · doi:10.1090/conm/138/1199122
[17] Diaconis, P. and Holmes, S. P. (2002). Random walks on trees and matchings. Electron. J. Probab. 7 17 pp. (electronic). · Zbl 1007.60071 · doi:10.1214/EJP.v7-105 · emis:journals/EJP-ECP/EjpVol7/paper6.abs.html · eudml:122458
[18] Diaconis, P., Mayer-Wolf, E., Zeitouni, O. and Zerner, M. P. W. (2004). The Poisson-Dirichlet law is the unique invariant distribution for uniform split-merge transformations. Ann. Probab. 32 915-938. · Zbl 1049.60088 · doi:10.1214/aop/1079021468
[19] Diaconis, P. and Ram, A. (2000). Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques. Michigan Math. J. 48 157-190. Dedicated to William Fulton on the occasion of his 60th birthday. · Zbl 0998.60069 · doi:10.1307/mmj/1030132713
[20] Diaconis, P. and Ram, A. (2010). A probabilistic interpretation of the Macdonald polynomials. Available at . 1007.4779 · arxiv.org
[21] Diaconis, P. and Shahshahani, M. (1981). Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 159-179. · Zbl 0485.60006 · doi:10.1007/BF00535487
[22] Edwards, R. G. and Sokal, A. D. (1988). Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm. Phys. Rev. D (3) 38 2009-2012. · doi:10.1103/PhysRevD.38.2009
[23] Ercolani, N. M. and Ueltschi, D. (2011). Cycle structure of random permutations with cycle weights. Available at . 1102.4796 · Zbl 1226.60130 · doi:10.1214/10-AAP697 · arxiv.org
[24] Fristedt, B. (1993). The structure of random partitions of large integers. Trans. Amer. Math. Soc. 337 703-735. · Zbl 0795.05009 · doi:10.2307/2154239
[25] Fulman, J. (2002). Random matrix theory over finite fields. Bull. Amer. Math. Soc. ( N.S. ) 39 51-85. · Zbl 0984.60017 · doi:10.1090/S0273-0979-01-00920-X
[26] Garsia, A. and Remmel, J. B. (2005). Breakthroughs in the theory of Macdonald polynomials. Proc. Natl. Acad. Sci. USA 102 3891-3894 (electronic). · Zbl 1208.05148 · doi:10.1073/pnas.0409705102
[27] Ghosh, J. K. and Ramamoorthi, R. V. (2003). Bayesian Nonparametrics . Springer, New York. · Zbl 1029.62004
[28] Gontcharoff, V. (1944). Du domaine de l’analyse combinatoire. Bull. Acad. Sci. USSR Sér. Math. [ Izvestia Akad. Nauk SSSR ] 8 3-48.
[29] Gordon, I. (2003). On the quotient ring by diagonal invariants. Invent. Math. 153 503-518. · Zbl 1039.20019 · doi:10.1007/s00222-003-0296-5
[30] Haglund, J., Haiman, M. and Loehr, N. (2005). A combinatorial formula for Macdonald polynomials. J. Amer. Math. Soc. 18 735-761 (electronic). · Zbl 1061.05101 · doi:10.1090/S0894-0347-05-00485-6
[31] Haglund, J., Haiman, M. and Loehr, N. (2005). Combinatorial theory of Macdonald polynomials. I. Proof of Haglund’s formula. Proc. Natl. Acad. Sci. USA 102 2690-2696 (electronic). · Zbl 1208.05149 · doi:10.1073/pnas.0408497102
[32] Haglund, J., Haiman, M. and Loehr, N. (2008). A combinatorial formula for nonsymmetric Macdonald polynomials. Amer. J. Math. 130 359-383. · Zbl 1246.05162 · doi:10.1353/ajm.2008.0015
[33] Haiman, M. (2006). Cherednik algebras, Macdonald polynomials and combinatorics. In International Congress of Mathematicians , Vol. III 843-872. Eur. Math. Soc., Zürich. · Zbl 1099.33014
[34] Hanlon, P. (1992). A Markov chain on the symmetric group and Jack symmetric functions. Discrete Math. 99 123-140. · Zbl 0774.05098 · doi:10.1016/0012-365X(92)90370-U
[35] Hoppe, F. M. (1987). The sampling theory of neutral alleles and an urn model in population genetics. J. Math. Biol. 25 123-159. · Zbl 0636.92007 · doi:10.1007/BF00276386
[36] Hora, A. and Obata, N. (2007). Quantum Probability and Spectral Analysis of Graphs . Springer, Berlin. With a foreword by Luigi Accardi. · Zbl 1141.81005
[37] Jiang, J. (2011). Multiplicative measures on partitions, asymptotic theory. Preprint, Dept. Mathematics, Stanford Univ.
[38] Kerov, S. V. (2003). Asymptotic Representation Theory of the Symmetric Group and Its Applications in Analysis. Translations of Mathematical Monographs 219 . Amer. Math. Soc., Providence, RI. Translated from the Russian manuscript by N. V. Tsilevich, With a foreword by A. Vershik and comments by G. Olshanski. · Zbl 1031.20007
[39] Knop, F. and Sahi, S. (1997). A recursion and a combinatorial formula for Jack polynomials. Invent. Math. 128 9-22. · Zbl 0870.05076 · doi:10.1007/s002220050134
[40] Levin, D. A., Peres, Y. and Wilmer, E. L. (2009). Markov Chains and Mixing Times . Amer. Math. Soc., Providence, RI. With a chapter by James G. Propp and David B. Wilson. · Zbl 1160.60001
[41] Logan, B. F. and Shepp, L. A. (1977). A variational problem for random Young tableaux. Adv. Math. 26 206-222. · Zbl 0363.62068 · doi:10.1016/0001-8708(77)90030-5
[42] Macdonald, I. G. (1995). Symmetric Functions and Hall Polynomials , 2nd ed. The Clarendon Press Oxford Univ. Press, New York. With contributions by A. Zelevinsky, Oxford Science Publications. · Zbl 0824.05059
[43] Macdonald, I. G. (2000/01). Orthogonal polynomials associated with root systems. Sém. Lothar. Combin. 45 Art. B45a, 40 pp. (electronic). · Zbl 1032.33010 · emis:journals/SLC/wpapers/s45macdonald.html · eudml:123294
[44] Macdonald, I. G. (2003). Affine Hecke Algebras and Orthogonal Polynomials. Cambridge Tracts in Mathematics 157 . Cambridge Univ. Press, Cambridge. · Zbl 1024.33001
[45] Newman, M. E. J. and Barkema, G. T. (1999). Monte Carlo Methods in Statistical Physics . The Clarendon Press Oxford Univ. Press, New York. · Zbl 1012.82019
[46] Okounkov, A. (2001). Infinite wedge and random partitions. Selecta Math. ( N.S. ) 7 57-81. · Zbl 0986.05102 · doi:10.1007/PL00001398
[47] Okounkov, A. (2002). Symmetric functions and random partitions. In Symmetric Functions 2001: Surveys of Developments and Perspectives. NATO Sci. Ser. II Math. Phys. Chem. 74 223-252. Kluwer Academic, Dordrecht. · Zbl 1017.05103 · doi:10.1007/978-94-010-0524-1_6
[48] Okounkov, A. (2005). The uses of random partitions. In XIVth International Congress on Mathematical Physics 379-403. World Sci. Publ., Hackensack, NJ. · Zbl 1120.05301
[49] Olshanski, G. (2011). Random permutations and related topics. In The Oxford Handbook on Random Matrix Theory (G. Akermann, J. Baik and P. Di Francesco, eds.). Oxford Univ. Press. To appear. Available at . · Zbl 1242.05006 · www.bookdepository.co.uk
[50] Pitman, J. (2006). Combinatorial Stochastic Processes. Lecture Notes in Math. 1875 . Springer, Berlin. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7-24, 2002, With a foreword by Jean Picard. · Zbl 1103.60004 · doi:10.1007/b11601500
[51] Ram, A. and Yip, M. (2011). A combinatorial formula for Macdonald polynomials. Adv. Math. 226 309-331. · Zbl 1291.05210 · doi:10.1016/j.aim.2010.06.022
[52] Saloff-Coste, L. (1997). Lectures on finite Markov chains. In Lectures on Probability Theory and Statistics ( Saint-Flour , 1996). Lecture Notes in Math. 1665 301-413. Springer, Berlin. · Zbl 0885.60061 · doi:10.1007/BFb0092621
[53] Stanley, R. P. (1989). Some combinatorial properties of Jack symmetric functions. Adv. Math. 77 76-115. · Zbl 0743.05072 · doi:10.1016/0001-8708(89)90015-7
[54] Vershik, A. M. (1996). Statistical mechanics of combinatorial partitions, and their limit configurations. Funktsional. Anal. i Prilozhen. 30 19-39, 96. · Zbl 0868.05004 · doi:10.1007/BF02509449
[55] Veršik, A. M. and Kerov, S. V. (1977). Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux. Dokl. Akad. Nauk SSSR 233 1024-1027.
[56] Yakubovich, Y. (2009). Ergodicity of multiplicative statistics. Available at . 0901.4655 · Zbl 1242.05021 · doi:10.1016/j.jcta.2012.03.002 · arxiv.org
[57] Zhao, J. T. (2011). Universality results for measures on partitions. Preprint, Dept. Mathematics, Stanford Univ.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.