Random walks generated by the Ewens distribution on the symmetric group
Algebraic Combinatorics, Volume 6 (2023) no. 4, pp. 907-927.

This paper studies Markov chains on the symmetric group S n where the transition probabilities are given by the Ewens distribution with parameter θ>1. The eigenvalues are identified to be proportional to the content polynomials of partitions. We show that the mixing time is bounded above by a constant depending only on the parameter if θ is fixed. However, if it agrees with the number of permuted elements (θ=n), the sequence of chains has a total variation cutoff at logn log2.

Published online:
DOI: 10.5802/alco.290
Classification: 60C05, 05E10
Keywords: Ewens distribution, mixing time, random walks on groups, YJM elements
Özdemir, Alperen 1

1 Georgia Institute of Technology School of Mathematics 686 Cherry St NW Atlanta, GA 30332 (USA)
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
     author = {\"Ozdemir, Alperen},
     title = {Random walks generated by the {Ewens} distribution on the symmetric group},
     journal = {Algebraic Combinatorics},
     pages = {907--927},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {4},
     year = {2023},
     doi = {10.5802/alco.290},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.290/}
AU  - Özdemir, Alperen
TI  - Random walks generated by the Ewens distribution on the symmetric group
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 907
EP  - 927
VL  - 6
IS  - 4
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.290/
DO  - 10.5802/alco.290
LA  - en
ID  - ALCO_2023__6_4_907_0
ER  - 
%0 Journal Article
%A Özdemir, Alperen
%T Random walks generated by the Ewens distribution on the symmetric group
%J Algebraic Combinatorics
%D 2023
%P 907-927
%V 6
%N 4
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.290/
%R 10.5802/alco.290
%G en
%F ALCO_2023__6_4_907_0
Özdemir, Alperen. Random walks generated by the Ewens distribution on the symmetric group. Algebraic Combinatorics, Volume 6 (2023) no. 4, pp. 907-927. doi : 10.5802/alco.290. https://alco.centre-mersenne.org/articles/10.5802/alco.290/

[1] Abramowitz, Milton; Stegun, Irene A. Handbook of mathematical functions with formulas, graphs, and mathematical tables, U.S. Government Printing Office, Washington, D.C., 1964, xiv+1046 pages

[2] Aigner, Martin A course in enumeration, Graduate Texts in Mathematics, 238, Springer, Berlin, 2007, x+561 pages

[3] Arratia, Richard; Barbour, A. D.; Tavaré, Simon Poisson process approximations for the Ewens sampling formula, Ann. Appl. Probab., Volume 2 (1992) no. 3, pp. 519-535 | MR | Zbl

[4] Behrends, Ehrhard Introduction to Markov chains (With special emphasis on rapid mixing), Advanced Lectures in Mathematics, Friedr. Vieweg & Sohn, Braunschweig, 2000, x+232 pages | DOI

[5] Ceccherini-Silberstein, Tullio; Scarabotti, Fabio; Tolli, Filippo Representation theory of the symmetric groups (The Okounkov-Vershik approach, character formulas, and partition algebras), Cambridge Studies in Advanced Mathematics, 121, Cambridge University Press, Cambridge, 2010, xvi+412 pages

[6] Crane, Harry The ubiquitous Ewens sampling formula, Statist. Sci., Volume 31 (2016) no. 1, pp. 1-19 | MR | Zbl

[7] Diaconis, Persi Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Institute of Mathematical Statistics, Hayward, CA, 1988, vi+198 pages | DOI

[8] Diaconis, Persi The cutoff phenomenon in finite Markov chains, Proc. Nat. Acad. Sci. U.S.A., Volume 93 (1996) no. 4, pp. 1659-1664 | DOI | MR | Zbl

[9] Diaconis, Persi; Greene, Curtis Applications of Murphy’s elements (1989) no. 335, pp. 1-22 (Technical report)

[10] Diaconis, Persi; Hanlon, Phil Eigen-analysis for some examples of the Metropolis algorithm, Hypergeometric functions on domains of positivity, Jack polynomials, and applications (Tampa, FL, 1991) (Contemp. Math.), Volume 138, Amer. Math. Soc., Providence, RI, 1992, pp. 99-117 | DOI | MR | Zbl

[11] Diaconis, Persi; Shahshahani, Mehrdad Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete (1981) no. 2, pp. 159-179 | DOI | MR | Zbl

[12] Ewens, Warren J. The sampling theory of selectively neutral alleles, Theor. Popul. Biol., Volume 3 (1972) no. 1, pp. 87-112 | DOI | MR | Zbl

[13] Garsia, Adriano M.; Eğecioğlu, Ömer Lectures in algebraic combinatorics (Young’s construction, seminormal representations, 𝔰𝔩(2) representations, heaps, basics on finite fields), Lecture Notes in Mathematics, 2277, Springer, Cham, 2020, xiv+230 pages

[14] Hanlon, Phil A Markov chain on the symmetric group and Jack symmetric functions, Discrete Math., Volume 99 (1992) no. 1-3, pp. 123-140 | DOI | MR | Zbl

[15] Jiang, Yunjiang Mixing time of Metropolis chain based on random transposition walk converging to multivariate Ewens distribution, Ann. Appl. Probab., Volume 25 (2015) no. 3, pp. 1581-1615 | MR | Zbl

[16] Jucys, A.-A. A. Symmetric polynomials and the center of the symmetric group ring, Rep. Mathematical Phys., Volume 5 (1974) no. 1, pp. 107-112 | DOI | MR | Zbl

[17] Kerov, S. V. Transition probabilities of continual Young diagrams and the Markov moment problem, Funktsional. Anal. i Prilozhen., Volume 27 (1993) no. 2, p. 32-49, 96 | MR | Zbl

[18] Kerov, S. V. The boundary of Young lattice and random Young tableaux, Formal power series and algebraic combinatorics (New Brunswick, NJ, 1994) (DIMACS Ser. Discrete Math. Theoret. Comput. Sci.), Volume 24, Amer. Math. Soc., Providence, RI, 1996, pp. 133-158 | MR | Zbl

[19] Lassalle, Michel Jack polynomials and some identities for partitions, Trans. Amer. Math. Soc., Volume 356 (2004) no. 9, pp. 3455-3476 | DOI | MR | Zbl

[20] Levin, David A.; Peres, Yuval; Wilmer, Elizabeth L. Markov chains and mixing times, American Mathematical Society, Providence, RI, 2009, xviii+371 pages (With a chapter by James G. Propp and David B. Wilson)

[21] Macdonald, I. G. Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979, viii+180 pages

[22] Murphy, G. E. A new construction of Young’s seminormal representation of the symmetric groups, J. Algebra, Volume 69 (1981) no. 2, pp. 287-297 | DOI | MR | Zbl

[23] Sagan, Bruce E. The symmetric group (Representations, combinatorial algorithms, and symmetric functions), Graduate Texts in Mathematics, 203, Springer-Verlag, New York, 2001, xvi+238 pages

[24] Saloff-Coste, Laurent Random walks on finite groups, Probability on discrete structures (Encyclopaedia Math. Sci.), Volume 110, Springer, Berlin, 2004, pp. 263-346 | DOI | Zbl

[25] Takács, Lajos The problem of coincidences, Arch. Hist. Exact Sci. (1979/80) no. 3, pp. 229-244 | MR | Zbl

[26] Vershik, A. M.; Okunʼkov, A. Yu. A new approach to representation theory of symmetric groups. II, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), Volume 307 (2004), p. 57-98, 281

Cited by Sources: