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

Metadata

DOI10.5802/ahl.99
Keywords Log-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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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, ACM Press (2003), pp. 287-296 | DOI | MR | Zbl

[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 | DOI | Numdam | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | Zbl

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

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

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

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

[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 | DOI | MR

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | Zbl

[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., IEEE (2002), pp. 721-729 | DOI

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | Zbl

[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 | Zbl

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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