×

Comparing with octopi. (English. French summary) Zbl 1471.60063

Given a graph \(G\) on \(n\) vertices, the interchange process on \(G\) is a random walk on \(S_n\) which chooses a random edge \((i,j)\) of \(G\) at each step and applies the transposition \((i,j)\) to the permutation in \(S_n\). The walk can either be discrete (with a probability of \(1/2\) of staying in place to avoid single steps always switching parity) or continuous (take steps according to a Poisson process). These graphs are of interest in interacting particle systems and quantum mechanics.
The authors use the octopus inequality [P. Caputo et al., J. Am. Math. Soc. 23, No. 3, 831–851 (2010; Zbl 1203.60145)] to prove bounds on the mixing behavior for general graphs \(G\), including a comparison to the mixing time for the complete graph \(K_n\). They also use representation theory of the symmetric group to bound the probability that the random walk reaches a large cycle in \(S_n\), and a related result for the quantum Heisenberg ferromagnet.

MSC:

60G50 Sums of independent random variables; random walks
60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
20C30 Representations of finite symmetric groups
05C80 Random graphs (graph-theoretic aspects)
81Q35 Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices

Citations:

Zbl 1203.60145
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] R. Adamczak, M. Kotowski and P. Milos. Phase transition for the interchange and quantum Heisenberg models on the Hamming graph. Preprint, 2018. Available at https://arxiv.org/abs/1808.08902.
[2] D. Aldous and J. A. Fill. Reversible Markov chains and random walks on graphs. Book draft, Available at https://www.stat.berkeley.edu/users/aldous/RWG/book.html.
[3] G. Alon and G. Kozma. The probability of long cycles in interchange processes. Duke Math. J. 162 (9) (2013) 1567-1585. Available at https://projecteuclid.org/euclid.dmj/1370955539. · Zbl 1269.82041 · doi:10.1215/00127094-2266018
[4] G. Alon and G. Kozma. The mean-field quantum Heisenberg ferromagnet via representation theory. Ann. Inst. Henri Poincaré, to appear. Available at https://arxiv.org/abs/1811.10530.
[5] B. Morris. The mixing time for simple exclusion. Ann. Appl. Probab. 16 (2) (2006) 615-635. Available at https://projecteuclid.org/euclid.aoap/1151592245. · Zbl 1133.60037 · doi:10.1214/105051605000000728
[6] N. Berestycki. Mixing times of Markov chains: Techniques and examples. Lecture notes, 2016. Available at http://www.statslab.cam.ac.uk/ beresty/Articles/mixing3.pdf.
[7] N. Berestycki and G. Kozma. Cycle structure of the interchange process and representation theory. Bull. Soc. Math. France 143 (2) (2015) 265-280. Available at https://smf.emath.fr/publications/structure-des-cycles-dans-le-processus-de-transpositions-et-theorie-des. · Zbl 1354.60113 · doi:10.24033/bsmf.2686
[8] P. Caputo, T. M. Liggett and T. Richthammer. Proof of Aldous’ spectral gap conjecture. J. Amer. Math. Soc. 23 (3) (2010) 831-851. Available at http://www.ams.org/journals/jams/2010-23-03/S0894-0347-10-00659-4/home.html. · Zbl 1203.60145 · doi:10.1090/S0894-0347-10-00659-4
[9] F. Cesi. A few remarks on the octopus inequality and Aldous’ spectral gap conjecture. Comm. Algebra 44 (1) (2016) 279-302. Available at https://www.tandfonline.com/doi/full/10.1080/00927872.2014.975349. · Zbl 1334.05057 · doi:10.1080/00927872.2014.975349
[10] J. P. Chen. The moving particle lemma for the exclusion process on a weighted graph. Electron. Commun. Probab. 22 (2017) 47. 13 pp., Available at https://projecteuclid.org/euclid.ecp/1506931447. · Zbl 1372.05207 · doi:10.1214/17-ECP82
[11] M. Correggi, A. Giuliani and R. Seiringer. Validity of the spin-wave approximation for the free energy of the Heisenberg ferromagnet. Comm. Math. Phys. 339 (1) (2015) 279-307. · Zbl 1321.82040 · doi:10.1007/s00220-015-2402-0
[12] A. B. Dieker. Interlacings for random walks on weighted graphs and the interchange process. SIAM J. Discrete Math. 24 (1) (2010) 191-206. · Zbl 1213.60125 · doi:10.1137/090775361
[13] J. Gordon and A. Kerber. The Representation Theory of the Symmetric Group. Encyclopedia of Mathematics and Its Applications 16. Addison-Wesley Publishing Co., Reading, MA, 1981. With a foreword by P. M. Cohn. With an introduction by Gilbert de B. Robinson. · Zbl 0491.20010
[14] S. Handjani and D. Jungreis. Rate of convergence for shuffling cards by transpositions. J. Theoret. Probab. 9 (4) (1996) 983-993. · Zbl 0878.60043 · doi:10.1007/BF02214260
[15] J. Hermon and R. Pymar. The exclusion process mixes (almost) faster than independent particles. Preprint, 2018. Available at https://arxiv.org/abs/1808.10846. · Zbl 1476.60133
[16] J. Jonasson. Mixing times for the interchange process. ALEA Lat. Am. J. Probab. Math. Stat. 9 (2) (2012) 667-683. Available at http://alea.impa.br/articles/v9/09-26.pdf. · Zbl 1290.60071
[17] A. Korányi. On a theorem of Löwner and its connections with resolvents of selfadjoint transformations. Acta Sci. Math. (Szeged) 17 (1956) 63-70. Available at http://pub.acta.hu/acta/showCustomerArticle.action?id=6460&dataObjectType=article&returnAction=showCustomerVolume. · Zbl 0074.10202
[18] D. A. Levin, Y. Peres and E. L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson, Available at http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf. · Zbl 1160.60001
[19] L. Lovász and P. Winkler Mixing times. In Microsurveys in Discrete Probability (Princeton, NJ, 1997). DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 41, 85-133. Amer. Math. Soc., Providence, RI, 1998. Available at http://web.cs.elte.hu/ lovasz/mixtimes.ps. · Zbl 0908.60065
[20] P. Milos and B. Sengül. Existence of a phase transition of the interchange process on the Hamming graph. Electron. J. Probab. 24 (2019) 64. 21 pp. Available at https://arxiv.org/pdf/1605.03548.pdf. · Zbl 1466.60107 · doi:10.1214/18-EJP171
[21] B. Morris and Y. Peres. Evolving sets, mixing and heat kernel bounds. Probab. Theory Related Fields 133 (2) (2005) 245-266. · Zbl 1080.60071 · doi:10.1007/s00440-005-0434-7
[22] R. I. Oliveira. Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk. Ann. Probab. 41 (2) (2013) 871-913. Available at https://projecteuclid.org/euclid.aop/1362750945. · Zbl 1274.60242 · doi:10.1214/11-AOP714
[23] D. Persi and L. Saloff-Coste. Comparison techniques for random walk on finite groups. Ann. Probab. 21 (4) (1993) 2131-2156. Available at http://www.jstor.org/stable/2244713. · Zbl 0790.60011 · doi:10.1214/aop/1176989013
[24] D. Persi and M. Shahshahani. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 (2) (1981) 159-179. · Zbl 0485.60006 · doi:10.1007/BF00535487
[25] J. Quastel. Diffusion of color in the simple exclusion process. Comm. Pure Appl. Math. 45 (6) (1992) 623-679. Available at: https://onlinelibrary.wiley.com/doi/abs/10.1002/cpa.3160450602. · Zbl 0769.60097 · doi:10.1002/cpa.3160450602
[26] A. Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1 (1992) 351-370. · Zbl 0801.90039 · doi:10.1017/S0963548300000390
[27] B. Tóth. Improved lower bound on the thermodynamic pressure of the spin 1/2 Heisenberg ferromagnet. Lett. Math. Phys. 28 (1) (1993) 75-84. · Zbl 0772.60103
[28] D. · Zbl 1040.60063 · doi:10.1214/aoap/1075828054
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.