A sharp log-Sobolev inequality for the multislice

Salez, Justin

doi:10.5802/ahl.99

Salez, Justin ¹

¹ Université Paris-Dauphine & PSL, CEREMADE - UMR 7534, Place du Maréchal de Lattre de Tassigny, F-75775, Paris Cedex 16, (France)

Annales Henri Lebesgue, Volume 4 (2021), pp. 1143-1161.

Abstract
Résumé

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.

Nous déterminons, à une petite constante multiplicative près, la constante de log-Sobolev de la diffusion de Bernoulli–Laplace multi-urne avec paramètres arbitraires. Ce résultat étend une estimée classique de Lee et Yau (1998) et confirme une conjecture de Filmus, O’Donnell et Wu (2018). Entre autres applications, nous quantifions complètement le phénomène d’expansion des petits ensembles, et obtenons des estimées optimales pour le temps de mélange du processus d’exclusion coloré sur divers graphes.

Received: 2020-04-19
Accepted: 2021-02-05
Published online: 2021-09-22

DOI: 10.5802/ahl.99

Classification: 60J27, 60J10, 05C81
Mots-clés : Log-Sobolev constant, random transpositions, colored exclusion process

Author's affiliations:

Salez, Justin ¹

¹ Université Paris-Dauphine & PSL, CEREMADE - UMR 7534, Place du Maréchal de Lattre de Tassigny, F-75775, Paris Cedex 16, (France)

@article{AHL_2021__4__1143_0,
     author = {Salez, Justin},
     title = {A sharp {log-Sobolev} inequality for the multislice},
     journal = {Annales Henri Lebesgue},
     pages = {1143--1161},
     publisher = {\'ENS Rennes},
     volume = {4},
     year = {2021},
     doi = {10.5802/ahl.99},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/ahl.99/}
}

TY  - JOUR
AU  - Salez, Justin
TI  - A sharp log-Sobolev inequality for the multislice
JO  - Annales Henri Lebesgue
PY  - 2021
SP  - 1143
EP  - 1161
VL  - 4
PB  - ÉNS Rennes
UR  - http://www.numdam.org/articles/10.5802/ahl.99/
DO  - 10.5802/ahl.99
LA  - en
ID  - AHL_2021__4__1143_0
ER  -

%0 Journal Article
%A Salez, Justin
%T A sharp log-Sobolev inequality for the multislice
%J Annales Henri Lebesgue
%D 2021
%P 1143-1161
%V 4
%I ÉNS Rennes
%U http://www.numdam.org/articles/10.5802/ahl.99/
%R 10.5802/ahl.99
%G en
%F AHL_2021__4__1143_0

Salez, Justin. A sharp log-Sobolev inequality for the multislice. Annales Henri Lebesgue, Volume 4 (2021), pp. 1143-1161. doi : 10.5802/ahl.99. http://www.numdam.org/articles/10.5802/ahl.99/

References
Cited by

[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

Cited by Sources: