2011

On reverse hypercontractivity

Mossel, Elchanan, Oleszkiewicz, Krzysztof, Sen, Arnab

Understand

We study the notion of reverse hypercontractivity.

We show that reverse hypercontractive inequalities are implied by standard hypercontractive inequalities as well as by the modified log-Sobolev inequality.
Our proof is based on a new comparison lemma for Dirichlet forms and an extension of the Strook-Varapolos inequality.
A consequence of our analysis is that {\em all} simple operators $L=Id-\E$ as well as their tensors satisfy uniform reverse hypercontractive inequalities.

Built on

K. J. Arrow, A difficulty in the concept of social welfare , The Journal of Political Economy 58
1950
Earlier work this paper cites.
by same author, Social choice and individual values , John Wiley and Sons, 1963
1963
Earlier work this paper cites.
A. Bonami, Étude des coefficients de Fourier des fonctions de L p ( G ) L^{p}(G) , Ann. Inst. Fourier (Grenoble) 20
1971
Earlier work this paper cites.
R. Wilson, Social choice theory without the Pareto principle , Journal of Economic Theory 5
1972
Earlier work this paper cites.
E. Nelson, The free Markoff field , J. Functional Analysis 12
1973
Earlier work this paper cites.
W. Beckner, Inequalities in Fourier analysis , Ann. of Math. (2) 102
1975
Earlier work this paper cites.
L. Gross, Logarithmic Sobolev inequalities , Amer. J. Math. 97
1975
Earlier work this paper cites.
by same author, Logarithmic Sobolev inequalities—a survey , Vector space measures and applications (Proc. Conf., Univ. Dublin, Dublin, 1977), I, Lecture Notes in Math., vol. 644, Springer, Berlin, 1978, pp. 196–203. MR 502406 (80f:46035)
1978
Earlier work this paper cites.
S. Barbera, Pivotal voters: A new proof of Arrow’s theorem , Economics Letters 6
1980
Earlier work this paper cites.
C. Borell and S. Janson, Converse hypercontractivity , Séminaire Initiation á l’Analyse, 21e année, 1981/82, Publ. Math. Univ. Pierre Marie Curie 54
1981
Earlier work this paper cites.
P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions , Z. Wahrsch. Verw. Gebiete 57
1981
Earlier work this paper cites.
V. V. Sazonov, Normal approximation—some recent advances , Lecture Notes in Mathematics, vol. 879, Springer-Verlag, Berlin, 1981. MR 643968 (83g:60035)
1981
Earlier work this paper cites.
C. Borell, Positivity improving operators and hypercontractivity , Math. Z. 180
1982
Earlier work this paper cites.
D. W. Stroock, An introduction to the theory of large deviations , Universitext, Springer-Verlag, New York, 1984. MR 755154 (86h:60067a)
1984
Earlier work this paper cites.
N. Th. Varopoulos, Hardy-Littlewood theory for semigroups , J. Funct. Anal. 63
1985
Earlier work this paper cites.
J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions , Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 68–80
1988
Earlier work this paper cites.

Similar

N. Alon, U. Maurer, and A. Wigderson, Unpublished results, 1991
1991
Cited alongside, same era.
P. Diaconis, J. A. Fill, and J. Pitman, Analysis of top to random shuffles , Combin. Probab. Comput. 1
1992
Cited alongside, same era.
D. Stroock and B. Zegarliński, The equivalence of the logarithmic Sobolev inequality and the Dobrushin-Shlosman mixing condition , Comm. Math. Phys. 144
1992
Cited alongside, same era.
by same author, The logarithmic Sobolev inequality for discrete spin systems on a lattice , Comm. Math. Phys. 149
1992
Cited alongside, same era.
B. Zegarliński, Dobrushin uniqueness theorem and logarithmic Sobolev inequalities , J. Funct. Anal. 105
1992
Cited alongside, same era.
D. Bakry, L’hypercontractivité et son utilisation en théorie des semigroupes , Lectures on probability theory 1581
1994
Cited alongside, same era.
F. Martinelli and E. Olivieri, Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case , Comm. Math. Phys. 161
1994
Cited alongside, same era.
by same author, Approach to equilibrium of Glauber dynamics in the one phase region. II. The general case , Comm. Math. Phys. 161
1994
Cited alongside, same era.
M. Talagrand, On Russo’s approximate 0-1 law , Annals of Probability 22
1994
Cited alongside, same era.
P. Diaconis and L. Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains , Ann. Appl. Probab. 6
1996
Cited alongside, same era.
S. Janson, Gaussian Hilbert Spaces , Cambridge Tracts in Mathematics, vol. 129, Cambridge University Press, Cambridge, 1997. MR 99f:60082
1997
Cited alongside, same era.
L. Saloff-Coste, Lectures on finite Markov chains , Lectures on probability theory and statistics (Saint-Flour, 1996), Lecture Notes in Math., vol. 1665, Springer, Berlin, 1997, pp. 301–413. MR 1490046 (99b:60119)
1997
Cited alongside, same era.

Then

M. Jerrum and J. Son, Spectral gap and log-Sobolev constant for balanced matroids , Proceedings of the 43 43 rd IEEE Symposium on Foundations of Computer Science( FOCS’02) (2002), 721–729
2002
Later among the works it cites.
G. Kalai, A Fourier-theoretic perspective on the Concordet paradox and Arrow’s theorem , Adv. in Appl. Math. 29
2002
Later among the works it cites.
S. G. Bobkov and P. Tetali, Modified log-Sobolev inequalities, mixing and hypercontractivity , Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (New York), ACM, 2003, pp. 287–296 (electronic). MR 2120475 (2005k:60027)
2003
Later among the works it cites.
F. Gao and J. Quastel, Exponential decay of entropy in the random transposition and Bernoulli-Laplace models , Ann. Appl. Probab. 13
2003
Later among the works it cites.
K. Oleszkiewicz, On a nonsymmetric version of the Khinchine-Kahane inequality , Stochastic inequalities and applications, Progr. Probab., vol. 56, Birkhäuser, Basel, 2003, pp. 157–168. MR 2073432 (2005f:60049)
2003
Later among the works it cites.
S. Goel, Modified logarithmic Sobolev inequalities for some models of random walk , Stochastic Process. Appl. 114
2004
Later among the works it cites.
K. Yang, On the (im)possibility of non-interactive correlation distillation , LATIN 2004: Theoretical informatics, Lecture Notes in Comput. Sci., vol. 2976, Springer, Berlin, 2004, pp. 222–231. MR 2095197 (2005f:94045)
2004
Later among the works it cites.
E. Mossel and R. O’Donnell, Coin flipping from a cosmic source: on error correction of truly random bits , Random Structures Algorithms 26
2005
Later among the works it cites.
by same author, Modified logarithmic Sobolev inequalities in discrete settings , J. Theoret. Probab. 19
2006
Later among the works it cites.
E. Mossel, R. O’Donnell, O. Regev, J. .E. Steif, and B. Sudakov, Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality , Israel J. Math. 154
2006
Later among the works it cites.
P. Wolff, Hypercontractivity of simple random variables , Studia Mathematica 180
2007
Later among the works it cites.
N. Alon and J. H. Spencer, The probabilistic method , third ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., Hoboken, NJ, 2008, With an appendix on the life and work of Paul Erdós. MR 2437651 (2009j:60004)
2008
Later among the works it cites.
E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality , Ann. of Math. (2) 171
2010
Later among the works it cites.
N. Keller, A tight quantitative version of Arrow’s impossibility theorem , Journal of the European Mathematical Society (to appear), 2011
2011
Closest in time.
E. Mossel, A quantitative Arrow theorem , Probability Theory and Related Fields 154
2012
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…