A sharp log-Sobolev inequality for the multislice
Annales Henri Lebesgue, Volume 4 (2021) , pp. 1143-1161.

Metadata

KeywordsLog-Sobolev constant, random transpositions, colored exclusion process

Abstract

We determine the log-Sobolev constant of the multi-urn Bernoulli–Laplace diffusion model with arbitrary parameters, up to a small universal multiplicative constant. Our result extends a classical estimate of Lee and Yau (1998) and confirms a conjecture of Filmus, O’Donnell and Wu (2018). Among other applications, we completely quantify the small-set expansion phenomenon on the multislice, and obtain sharp mixing-time estimates for the colored exclusion process on various graphs.


References

[AK20] Alon, Gil; Kozma, Gady Comparing with octopi, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 56 (2020) no. 4, pp. 2672-2685 | Article | MR 4164852 | Zbl 07354140

[BD06] Berestycki, Nathanaël; Durrett, Rick A phase transition in the random transposition random walk, Probab. Theory Relat. Fields, Volume 136 (2006) no. 2, pp. 203-233 | Article | MR 2240787 | Zbl 1102.60005

[BT03] Bobkov, Sergey G.; Tetali, Prasad Modified log-Sobolev inequalities, mixing and hypercontractivity, Proceedings of the thirty-fifth annual ACM symposium on theory of computing (STOC 2003), San Diego, CA, USA,. New York (2003), pp. 287-296 | Article | MR 2120475 | Zbl 1192.60020

[CDPP09] Caputo, Pietro; Dai Pra, Paolo; Posta, Gustavo Convex entropy decay via the Bochner–Bakry–Emery approach, Ann. Inst. Henri Poincaré, Probab. Stat., Volume 45 (2009) no. 3, pp. 734-753 | Article | Numdam | MR 2548501 | Zbl 1181.60142

[CLR10] Caputo, Pietro; Liggett, Thomas M.; Richthammer, Thomas Proof of Aldous’ spectral gap conjecture, J. Am. Math. Soc., Volume 23 (2010) no. 3, pp. 831-851 | Article | MR 2629990 | Zbl 1203.60145

[CP07] Caputo, Pietro; Posta, Gustavo Entropy dissipation estimates in a zero-range dynamics, Probab. Theory Relat. Fields, Volume 139 (2007) no. 1-2, pp. 65-87 | Article | MR 2322692 | Zbl 1126.60082

[CP19] Connor, Stephen B.; Pymar, Richard J. Mixing times for exclusion processes on hypergraphs, Electron. J. Probab., Volume 24 (2019), 73 | Article | MR 3978223 | Zbl 07089011

[Dia88] Diaconis, Persi Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes - Monograph Series, 11, Institute of Mathematical Statistics, 1988 | MR 964069 | Zbl 0695.60012

[DPPP02] Dai Pra, Paolo; Paganoni, Anna Maria; Posta, Gustavo Entropy inequalities for unbounded spin systems, Ann. Probab., Volume 30 (2002) no. 4, pp. 1959-1976 | Article | MR 1944012 | Zbl 1013.60076

[DS81] Diaconis, Persi; Shahshahani, Mehrdad Generating a random permutation with random transpositions, Z. Wahrscheinlichkeitstheor. Verw. Geb., Volume 57 (1981) no. 2, pp. 159-179 | Article | MR 626813 | Zbl 0485.60006

[DS87] Diaconis, Persi; Shahshahani, Mehrdad Time to reach stationarity in the Bernoulli–Laplace diffusion model, SIAM J. Math. Anal., Volume 18 (1987) no. 1, pp. 208-218 | Article | MR 871832 | Zbl 0617.60009

[DSC93a] Diaconis, Persi; Saloff-Coste, Laurent Comparison techniques for random walk on finite groups, Ann. Probab., Volume 21 (1993) no. 4, pp. 2131-2156 | MR 1245303 | Zbl 0790.60011

[DSC93b] Diaconis, Persi; Saloff-Coste, Laurent Comparison theorems for reversible Markov chains, Ann. Appl. Probab., Volume 3 (1993) no. 3, pp. 696-730 | MR 1233621 | Zbl 0799.60058

[DSC96] Diaconis, Persi; Saloff-Coste, Laurent Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab., Volume 6 (1996) no. 3, pp. 695-750 | Article | MR 1410112 | Zbl 0867.60043

[FI19] Filmus, Yuval; Ihringer, Ferdinand Boolean constant degree functions on the slice are juntas, Discrete Math., Volume 342 (2019) no. 12, 111614 | Article | MR 3990024 | Zbl 07118718

[Fil20] Filmus, Yuval FKN theorem for the multislice, with applications, Comb. Probab. Comput., Volume 29 (2020) no. 2, pp. 200-212 | Article | MR 4079633 | Zbl 07359150

[FOW19] Filmus, Yuval; O’Donnell, Ryan; Wu, Xinyu A log-Sobolev inequality for the multislice, with applications, 10th Innovations in Theoretical Computer Science (Leibniz International Proceedings in Informatics (LIPIcs)), Volume 124, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019, 34 | Article | MR 3899828

[Goe04] Goel, Sharad Modified logarithmic Sobolev inequalities for some models of random walk, Stochastic Processes Appl., Volume 114 (2004) no. 1, pp. 51-79 | Article | MR 2094147 | Zbl 1074.60080

[GQ03] Gao, Fuqing; Quastel, Jeremy Exponential decay of entropy in the random transposition and Bernoulli–Laplace models, Ann. Appl. Probab., Volume 13 (2003) no. 4, pp. 1591-1600 | Article | MR 2023890 | Zbl 1046.60003

[HP18] Hermon, Jonathan; Peres, Yuval A characterization of L 2 mixing and hypercontractivity via hitting times and maximal inequalities, Probab. Theory Relat. Fields, Volume 170 (2018) no. 3-4, pp. 769-800 | Article | MR 3773799 | Zbl 1403.60067

[HP20] Hermon, Jonathan; Pymar, Richard J. The exclusion process mixes (almost) faster than independent particles, Ann. Probab., Volume 48 (2020) no. 6, pp. 3077-3123 | Article | MR 4164461 | Zbl 07276948

[HS19a] Hermon, Jonathan; Salez, Justin Entropy dissipation estimates for inhomogeneous zero-range processes (2019) (https://arxiv.org/abs/1903.01410)

[HS19b] Hermon, Jonathan; Salez, Justin Modified log-Sobolev inequalities for strong-Rayleigh measures (2019) (https://arxiv.org/abs/1902.02775)

[HS19c] Hermon, Jonathan; Salez, Justin A version of Aldous’ spectral-gap conjecture for the zero range process, Ann. Appl. Probab., Volume 29 (2019) no. 4, pp. 2217-2229 | Article | MR 3984254 | Zbl 07120707

[HS21] Hermon, Jonathan; Salez, Justin The interchange process on high-dimensional products, Ann. Appl. Probab., Volume 31 (2021) no. 1, pp. 84-98 | Article | MR 4254474

[Jon12] Jonasson, Johan Mixing times for the interchange process, ALEA, Lat. Am. J. Probab. Math. Stat., Volume 9 (2012) no. 2, pp. 667-683 | MR 3069380 | Zbl 1290.60071

[JS02] Jerrum, Mark R.; Son, Jung-Bae Spectral gap and log-Sobolev constant for balanced matroids, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. (2002), pp. 721-729 | Article

[JSTV04] Jerrum, Mark R.; Son, Jung-Bae; Tetali, Prasad; Vigoda, Eric Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains, Ann. Appl. Probab., Volume 14 (2004) no. 4, pp. 1741-1765 | Article | MR 2099650 | Zbl 1067.60065

[KKL88] Kahn, J.; Kalai, G.; Linial, N. The influence of variables on Boolean functions, [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science (1988), pp. 68-80 | Article

[LK99] Lovász, László; Kannan, Ravi Faster mixing via average conductance, Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999, ACM Press, 1999, pp. 282-287 | Article | MR 1798047 | Zbl 1345.60078

[LL11] Lacoin, Hubert; Leblond, Rémi Cutoff phenomenon for the simple exclusion process on the complete graph, ALEA, Lat. Am. J. Probab. Math. Stat., Volume 8 (2011), pp. 285-301 | MR 2869447 | Zbl 1276.60005

[LY93] Lu, Sheng Lin; Yau, Horng-Tzer Spectral gap and logarithmic Sobolev inequality for Kawasaki and Glauber dynamics, Commun. Math. Phys., Volume 156 (1993) no. 2, pp. 399-433 | MR 1233852 | Zbl 0779.60078

[LY98] Lee, Tzong-Yow; Yau, Horng-Tzer Logarithmic Sobolev inequality for some models of random walks, Ann. Probab., Volume 26 (1998) no. 4, pp. 1855-1873 | Article | MR 1675008 | Zbl 0943.60062

[Mat88] Matthews, Peter A strong uniform time for random transpositions, J. Theor. Probab., Volume 1 (1988) no. 4, pp. 411-423 | Article | MR 958246 | Zbl 0716.60074

[Mor06] Morris, Ben The mixing time for simple exclusion, Ann. Appl. Probab., Volume 16 (2006) no. 2, pp. 615-635 | Article | MR 2244427 | Zbl 1133.60037

[MT06] Montenegro, Ravi; Tetali, Prasad Mathematical aspects of mixing times in Markov chains, Found. Trends Theor. Comput. Sci., Volume 1 (2006) no. 3, pp. 237-354 | Article | MR 2341319 | Zbl 1193.68138

[Oli13] Oliveira, Roberto I. Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk, Ann. Probab., Volume 41 (2013) no. 2, pp. 871-913 | Article | MR 3077529 | Zbl 1274.60242

[O’D14] O’Donnell, Ryan Analysis of Boolean functions, Cambridge University Press, 2014 | Article | MR 3443800 | Zbl 1336.94096

[Sca97] Scarabotti, Fabio Time to reach stationarity in the Bernoulli–Laplace diffusion model with many urns, Adv. Appl. Math., Volume 18 (1997) no. 3, pp. 351-371 | Article | MR 1436486 | Zbl 0886.60006

[Sch05] Schramm, Oded Compositions of random transpositions, Isr. J. Math., Volume 147 (2005), pp. 221-243 | Article | MR 2166362 | Zbl 1130.60302

[Tey20] Teyssier, Lucas Limit profile for random transpositions, Ann. Probab., Volume 48 (2020) no. 5, pp. 2323-2343 | Article | MR 4152644 | Zbl 07276926

[Wil04] Wilson, David B. Mixing times of Lozenge tiling and card shuffling Markov chains, Ann. Appl. Probab., Volume 14 (2004) no. 1, pp. 274-325 | Article | MR 2023023 | Zbl 1040.60063

[Yau97] Yau, Horng-Tzer Logarithmic Sobolev inequality for generalized simple exclusion processes, Probab. Theory Relat. Fields, Volume 109 (1997) no. 4, pp. 507-538 | Article | MR 1483598 | Zbl 0903.60087