On reverse hypercontractivity

Introduction

Log-Sobolev and hypercontractive inequalities play a fundamental role in a number of areas in analysis and probability theory including the study of Gaussian processes (see, e.g., [Gro78, Jan97]), analysis of Markov chains (see, e.g., [SC97]) and discrete Fourier analysis starting in [KKL88, Tal94].

The strength of a simple hypercontractive inequality like (1.1) lies in the fact that it tensorizes. This led to many applications in discrete Fourier analysis (starting with [KKL88]) and even earlier in the study of Gaussian processes. Extending (1.1) to other spaces turned out to be a non-trivial task. For the case of the spaces $(\Omega,\mu)=(\{0,1\},\alpha\delta_{0}+(1-\alpha)\delta_{1})$, with $\alpha\leq 1/2$, the first bounds were established by Talagrand [Tal94]. Exact formulas have been obtained by Oleszkiewicz [Ole03] in the cases where either $p>2=q$ or $p=2>q>1$. Wolff then extended these results [Wol07] to general discrete spaces and, in a slightly less precise form, to all $p>q\geq 2$ and all $2\geq p>q>1$: let $(\Omega,\mu)$ be a finite probability space with $\alpha=\min_{\omega\in\Omega}\mu\{\omega\}>0$; then there exists some universal positive constant $\varepsilon$ such that for $p,q$ as above and certain $t_{0}=t_{0}(p,q,\alpha)$, given by an explicit though complicated formula,

A ‘reverse’ hypercontractivity is shortly proved and discussed in a paper by Borell [Bor82] in the 80’s. This result, proven for the measure $(\Omega,\mu)=(\{0,1\},\frac{1}{2}(\delta_{0}+\delta_{1}))$, states that

This inequality which also tensorizes is indeed ‘reverse’ in many ways. Not only the inequality goes ‘the other way’ and the roles of $p$ and $q$ get reversed, it is also the case that $p$ and $q$ are less than $1$ (indeed they may be negative(!); note, however, that the function $f$ has to take positive values).

As far as we know, Borell’s result was first used in a paper published more than 20 years later [MOR+06], where it is used to analyze mixing of short random walks on the discrete cube $\{0,1\}^{n}$ as well as to provide tight bounds on the Non-Interactive Correlation Distillation (NICD) problem.

Motivated by generalization of applications in [MOR+06] as well as by other applications that will be discussed later, we wish to extend Borell’s results to other discrete probability spaces. Noting the similarity of the inequalities (1.1) and (1.2) it is tempting to conjecture (as the first named author have done) that the formulas for hypercontracitivity and reverse hypercontractivity are ‘the same’: in particular, for discrete spaces there is a dependency on the size of the smallest atom in space as in the above-mentioned results for hypercontractivity. The conjecture is further supported by the fact that for diffusions both hypercontractivity and reverse hypercontractivity are equivalent to the standard log-Sobolev inequality (for more details see [Bak94]; some pioneering results relating hypercontractivity to reverse hypercontractivity were obtained already in [BJ]).

The conjecture turns out to be far from true. In fact our results show that for every discrete probability space $(\Omega,\mu)$:

In particular, reverse hypercontractive inequalities hold uniformly for all probability spaces.

It is well known that hypercontractive inequalities are intimately related to logarithmic Sobolev inequalities and our proof of (1.3) is based on extension of this connection to ‘norms’ $p<1$ (such extensions were noted before, see, e.g., Bakry’s lecture notes [Bak94]). At the heart of the proof is a new monotonicity result showing that under the appropriate normalization log-Sobolev inequalities are monotone in the norm parameter $p$ for all $p\in$. This result in turn is based on an extension of the Stroock-Varopoulos inequality to general norms. The result allows us to show how reverse hypercontractive inequalities follow directly from standard hypercontractive inequalities and furthermore from standard log-Sobolev and modified log-Sobolev inequalities.

After we develop the theory of reverse hypercontractive inequalities, we derive a number of novel results regarding mixing of Markov chains run for short time starting from large sets, in general cubes, the symmetric group and Ising configurations (via Glauber dynamics). We further derive a quantitative Arrow’s Theorem for general distributions and inverse polynomial bounds for the NICD problem for general $m$-sided dice. We proceed with formal definitions and statements of the main results.

2. General setup

for any $f\in{\mathcal{H}}$, and any $\omega\in\Omega$ such that $f\leq f(\omega)$ on $\Omega$, there is $(Lf)(\omega)\geq 0$.

Alternatively, one can replace the fourth condition by the non-negativeness of the carré du champ (as a function-valued quadratic form), i.e., $L(f^{2})\leq 2fLf$ for $f\in{\mathcal{H}}$. The Markov semigroup of operators $(T_{t})_{t\geq 0}:{\mathcal{H}}\rightarrow{\mathcal{H}}$ generated by $L$ is given by

Recall that in this setup we have $T_{t}1=1$ for $t\geq 0$ and ${\mathcal{E}}(f,1)=0$ for $f\in{\mathcal{H}}$. The operators $T_{t}$ are symmetric linear contractions in $L^{p}$-norm for every $p\in[1,\infty)$ and $t\geq 0$. They are mean-preserving, i.e.,

Recall that $\|\cdot\|_{p}$ is a true norm for $p\geq 1$ but it is only a pseudo-norm (triangle inequality fails) for $p<1$ (unless $|\Omega|=1$). It is an easy and well-known fact that for any $f\in{\mathcal{H}}_{(0,\infty)}$ the map $p\mapsto\|f\|_{p}$ is continuous and non-decreasing.

Note that the map $p\mapsto p^{\prime}$ is a continuous order-reversing involution on $(-\infty,1)$ and $(1,\infty)$ with fixed points and $2$. It is worth observing that $(2-p)^{\prime}=2-p^{\prime}$ for $p\neq 1$, even though we will not make use of this fact.

3. Log-Sobolev inequalities

We now recall the definition of log-Sobolev inequalities.

for every $f\in{\mathcal{H}}_{(0,\infty)}$. We will say that $1$-logSob is satisfied with constant $C>0$ if

for $f\in{\mathcal{H}}_{(0,\infty)}$. Finally, we will say that -logSob is satisfied with constant $C>0$ if

for every $f\in{\mathcal{H}}_{(0,\infty)}$.

Logarithmic Sobolev inequalities were introduced by Gross in his seminal paper [Gro75]. Gross defined logarithmic Sobolev inequality for $p>1$. The definition was later extended by Bakry [Bak94] to any real $p$ (including $1$-logSob inequality). Finally, we remark that $1$-logSob inequality is also known in the literature as modified log-Sobolev inequality (see, e.g., [Wu00, GQ03, Goe04, BT06]). The 1-logSob inequality is also called “entropic inequality” as it implies the exponential decay of entropy along the semigroup.

Our definition uses a novel and non-standard normalization factor $\frac{p^{2}}{4(p-1)}$ in (1.4). The choice of this normalization makes our $p$-logSob constants invariant under Hölder conjugation (see Lemma 3.2). Moreover, this normalization is crucial to prove the main result of the paper - the monotonicity of the inequality for $p\in$ (see Theorem 1.7).

In our main result we prove a general result relating $p$-logSob inequalities for different values of $p$.

Let $0\leq q\leq p\leq 2$. Assume that $p$-logSob holds with a constant $C>0$. Then also $q$-logSob holds true with the same constant $C$.

It has been proved in [Bak94, Proposition 3.1] that if $2$-logSob holds with constant $C$, then any $p$-logSob also holds with the same constant and for $p>0$ the converse is true in case of diffusions with invariant measure $\mu$.

Using the fact that simple operators satisfy $1$-logSob with the constant $4$ (proved in [BT06]; the proof is reproduced in our Lemma 3.5 below) we obtain the following corollary:

4. Reverse hypercontractive estimates

Using Theorem 1.7 we derive the following general reverse hypercontractive bounds:

If a symmetric Markov semigroup $(T_{t})_{t\geq 0}$ satisfies $r$-logSob with constant $C$ and $r\geq 1$ then for all $q<p<1$ and every $f\in{\mathcal{H}}_{(0,\infty)}$ for all $t\geq\frac{C}{4}\log\frac{1-q}{1-p}$ we have $\|T_{t}f\|_{q}\geq\|f\|_{p}$.

Using Corollary 1.9 this implies in turn that:

In fact, for simple operators we derive the following stronger result:

The reverse hypercontractive inequality (1.2) for a simple operator and the space $\{-1,1\}$ with the uniform measure was derived prior to ours by Borell. His result is tight.

5. Application 1: Mixing of large sets in Markov chains

Our first application of the new inequality is to mixing of Markov chains from large sets. The statement and proof of the theorem below are a generalization of the main result of [MOR+06] where it was proven for the random walk on the discrete cube $\{0,1\}^{n}$.

First, the Expander Mixing Lemma (see, e.g., [AS08, Chapter 9]) implies that if Poincaré inequality holds with constant $D$ then:

The inequality (1.6) will be better (up to constants) than our inequality (1.5) in the case where the sets $A$ and $B$ are large, say $\pi\{A\}\pi(B)\geq 2\sqrt{\pi\{A\}\pi\{B\}}e^{-t/D}$, since in this case we obtain the lower bound of $\frac{1}{2}\pi\{A\}\pi\{B\}$ which is (except for the factor $2$) the best that one can hope for. However, in the case where the sets $A$ and $B$ are small, say $\pi\{A\}\pi\{B\}\leq\sqrt{\pi\{A\}\pi\{B\}}e^{-t/D}$, the expander mixing lemma gives nothing while (1.5) gives a lower bound that is a power of the measures of the original sets.

The second technique uses total variation mixing times. Indeed, if the worst total variation distance at time $t$ is at most $\epsilon$, then we have:

Again - applying this bound requires that one of the sets $A$ or $B$ is large (of measure at least $\epsilon$). Moreover, in many examples the time $t$ when the total variation distance is at most $1/e$ is much larger than the $1$-logSob constant $C$. Therefore if $t$ is of order $C$, then the mixing time bound (1.7) gives nothing while our result (1.5) gives an efficient lower bound.

We demonstrate this point by proving new mixing bounds from large sets for various classical Markov chains, including:

Short random walks on general product spaces. In this case we derive tighter results in subsection 9.1.

The random transposition card shuffle on the symmetric group. Here it is known that hat the 1-logSob constant $C$ of this chain is of order $n$ [GQ03, BT03, Goe04] while the mixing time is $\Theta(n\log n)$. Thus again, we obtain new results on mixing from large sets. Similar logic applies to the Top-to-random transposition walk on symmetric group, see [Goe04, DFP92] for the 1-logSob constant and the mixing time. We provide the details in subsections 9.4 and 9.5.

Random walk on the spanning trees of certain graphs. See subsection 9.6.

The Bernoulli-Laplace model. See subsection 9.7.

A natural Markovian queueing process - the $q/q/\infty$ Markov process. The last example is interesting since it has infinite $2$-logSob constant and an infinite mixing time. More details on this example are given in subsection 9.2

6. Application 2: A general quantitative Arrow theorem

Arrow’s Impossibility Theorem [Arr50, Arr63] is a fundamental result in social choice theory. It considers $n$ voters who rank $k$ candidates. Arrow considered functions $F:S_{k}^{n}\to\{-1,1\}^{k\choose 2}$ that aggregate individual rankings (elements of the permutation group $S_{k}$) to result in a preference between every pair of the $k$ alternatives. Arrow showed that if the following desired properties hold simultaneously when $k\geq 3$:

Transitivity - $F(\sigma)$ induces a transitive ranking for all $\sigma\in S_{k}^{n}$,

Unanimity - for every pair of alternatives $a$ and $b$, if all voters rank $a$ above $b$ then $F$ also ranks $a$ above $b$,

Independence of irrelevant alternatives (IIA) - for every pair of alternatives, the resulting outcome regarding the preference between $a$ and $b$ is determined by the individual preferences between $a$ and $b$,

then $F$ is a dictator function, i.e., it is determined by a single voter.

It is natural to ask how robust is the result when considering natural distributions over $S_{k}^{n}$. This question was analyzed by Kalai [Kal02] who studied it for the case of the uniform distribution over $S_{3}^{n}$ and showed that for every $\epsilon>0$, there exists a $\delta>0$ such that if $F$ satisfies:

Following a challenge by Kalai, Mossel [Mos12] proved a stronger result for any number of alternatives and without the assumption that $F$ is fair. His result shows that for $k\geq 3$ and every $\epsilon>0$, there exists a $\delta>0$ such that if $F$ satisfies

A key ingredient of the proof in [Mos12] is the use of reverse hypercontractive inequalities. It is further noted in [Mos12] that it should be possible to extend the proof to general product distributions on $S_{k}^{n}$ given appropriate reverse hypercontractive bounds for general two point spaces. Our results imply the following extension.

We note that considering general product distributions gives a more realistic model of actual voting (though the independence assumption in this line of work is still problematic in real voting scenarios).

7. Application 3: Non-interactive correlation distillation from dice source

The problem of non-interactive correlation distillation deals with players who receive correlated random strings and whose collective goal is to agree with the highest possible probability on a random variable with a given distribution. Suppose there are $k\geq 2$ players and a ‘cosmic source’. Assume first that the source generates a string $x$ of $n$ i.i.d. bits. Each player gets to receive an independent noisy copy of $x$. Each player then produces a single random bit based on her input. The players wish to have unanimous agreement on their outputs but are not allowed to communicate. The problem is to understand to what extent the players can successfully ‘distill’ the correlations in their strings into a shared random bit.

where the supremum is taken over all choices of balanced functions $(F_{i})_{1\leq i\leq k}$. Since a balanced function defined on $n$ variables can be also thought of a balanced function of $(n+1)$ variables, for a fixed $k$ and $\rho$, $\mathcal{M}_{\rho}(k,n)$ is a non-decreasing function of $n$ and so, $\lim_{n\to\infty}\mathcal{M}_{\rho}(k,n)$ exists. One of the main results of [MOR+06] says that when $m=2$, we have

The upper bound of the above result uses an application of reverse hypercontractivity for simple semigroup on symmetric two-point space. Here we generalize this bound and give an inverse polynomial bounds (in $k$) on the agreement probability for general $m$.

Fix $\rho\in(0,1)$. Then there exist positive constants $\gamma_{1}=\gamma_{1}(\rho),\gamma_{2}=\gamma_{2}(\rho),c_{1}=c_{1}(m,\rho)$ and $c_{2}=c_{2}(m,\rho)$ such that for all $k\geq 2$,

The first named author enjoyed the hospitality of Isaac Newton Institute, Cambridge while completing part of this research. The second named author enjoyed hospitality of University of California, Berkeley and Isaac Newton Institute, Cambridge while doing this research. We thank Dominique Bakry, Franck Barthe, Nick Crawford, Michel Ledoux and Cyril Roberto for helpful comments and discussions. We thank an anonymous referee for numerous helpful suggestions including suggesting simpler proof of Lemma 2.3.

Comparison of Dirichlet forms

The following theorem extends the classical Stroock-Varopoulos inequality [Str84, Var85] (covering the case $p=2$, $q\in(1,2]$ of the present result). Theorem 2.1 is the main tool in proving Theorem 1.7. Note that some terms in the statement below may take negative values.

Let $p,q\in(0,2]\setminus\{1\}$ and $p>q$. Then

for every $g\in{\mathcal{H}}_{(0,\infty)}$.

The above result has a natural extension to the case $p=1$ or $q=1$, with ${\mathcal{E}}(\log g,g)$ replacing the right (resp. left) hand side of the asserted inequality; then it suffices to use functions $\varphi_{1}(x)=\log x$ and $\varphi_{2}(x)=x$ (or $\psi_{1}(x)=\log x$ and $\psi_{2}(x)=x$, respectively) in the proof. One can also simply pass to the limit.

The proof of the theorem will use the following lemmas.

for all $a,b\in I$. Then for every $f:\Omega\rightarrow I$ there is

where by $\varphi_{1}(f)$ we denote $\varphi_{1}\circ f\in{\mathcal{H}}$, etc.

for all $a,b\in I$. Then for every $f:\Omega\rightarrow I$ there is

is nonnegative. Clearly, $\Phi(x,x)=0$ and $\frac{\partial\Phi}{\partial a}(x,x)=0$ for all $x\in I$. Now it is enough to notice that the assumptions of Lemma 2.4 yield $\frac{\partial}{\partial b}\frac{\partial}{\partial a}\Phi\leq 0$ which implies that $\Phi(\cdot,x)$ is non-decreasing on $[x,\infty)\cap I$ and non-increasing on $(-\infty,x]\cap I$. ∎

It suffices to use Lemma 2.4 with $I=(0,\infty)$, $\varphi_{1}(x)=px^{1/p}$, $\varphi_{2}(x)=p^{\prime}x^{1/p^{\prime}}$, $\psi_{1}(x)=qx^{1/q}$, and $\psi_{2}(x)=q^{\prime}x^{1/q^{\prime}}$. Indeed, to verify the assumptions of Lemma 2.4 one needs to check whether for all $a,b>0$,

This is, however, obvious since the function $w\mapsto s^{w}+s^{-w}$ is even and convex for every $s>0$ and thus it is non-decreasing on $(0,\infty)$. Choosing $s=a/b$ and recalling that $0<1/p-1/2\leq 1/q-1/2$ ends the proof. ∎

For any $f\in{\mathcal{H}}_{(0,\infty)}$ there is

It follows immediately from Lemma 2.4 applied to $I=(0,\infty)$ with $\varphi_{1}(x)=\log x$, $\varphi_{2}(x)=\log x$, $\psi_{1}(x)=x$, and $\psi_{2}(x)=-1/x$. ∎

For any positive $g$, the function $u\mapsto\frac{1}{u(1-u)}{\mathcal{E}}(g^{u},g^{1-u})$ is log-convex on the real line: either it is positive and its logarithm is convex, or it is identically equal to zero (if $g$ is constant). It is also obviously symmetric with respect to $1/2$, so that it is non-decreasing on $[1/2,\infty)$, which is a re-formulation of Theorem 2.1. Indeed, the log-convexity follows easily from the formula (2.1) and Hölder’s inequality, if one can first prove that the functions $u\mapsto(b^{u}-a^{u})/u$ and, equivalently, $u\mapsto(b^{1-u}-a^{1-u})/(1-u)$ are log-convex for any pair of fixed nonnegative numbers $a>b$. This, however, is an immediate consequence of the identity $(b^{u}-a^{u})/u=\int_{a}^{b}s^{u-1}\,ds,$ and Hölder’s inequality. We skip standard discussion of the cases $u=0$ and $u=1$.

Logarithmic Sobolev inequalities

In this section we prove various properties of log-Sobolev inequalities and in particular Theorem 1.7. We begin with a simple claim relating -logSob to the Poincaré inequality. We suspect that both Lemma 3.1 and Lemma 3.2 below were previously known in the literature but we did not find any explicit reference.

-logSob holds with constant $C$ if and only if the standard Poincaré inequality holds with constant $C/2$, i.e.,

For $g\in{\mathcal{H}}$ and $\delta>0$ set $f=e^{\delta g}$. Assuming that $f$ satisfies -logSob with constant $C$ we obtain

By the homogeneity of variance and bilinearity of ${\mathcal{E}}$ we get

On the other hand, let $f\in{\mathcal{H}}$ be positive and assume that the Poincaré inequality holds with constant $C/2$. By using it for $g=\log f$ we arrive at

The following easy observation allows us to restrict study of the $p$-logSob inequalities to the case $p\in$ (also, it reveals that $1$-logSob is, in a sense, a replacement for $\pm\infty$-logSob).

For $p=0$ there is nothing to prove, whereas for $p\neq 0$ it suffices to notice that by setting $g=f^{p}$ we obtain an equivalent ‘self-dual’ version of $p$-logSob:

We now prove Theorem 1.7 using the extension of the classical Stroock-Varopoulos inequality proven in Theorem 2.1.

It is a direct consequence of the ‘self-dual’ reformulation (3.1) of $p$-logSob, Theorem 2.1, and Remark 2.2. The fact that $p$-logSob with constant $C$ implies -logSob (with the same constant) for every $p\neq 0$ may be proved in two natural ways. One can deduce the Poincaré inequality with constant $C/2$ from $p$-logSob by setting $f=e^{\delta g}$ and letting $\delta$ tend to zero (as in the first part of proof of Lemma 3.1, and use Lemma 3.1 to finish the argument). Alternatively, one can first deduce from $p$-logSob the $q$-logSob inequalities (with the same constant) for $q$ arbitrarily close to zero, and then simply apply limit transition $q\to 0$. ∎

In view of Lemma 3.1 and Theorem 1.7, the $p$-logSob inequalities, $p\in$, can be treated as a family interpolating in a continuous and monotone way between the classical Poincaré and logaritmic Sobolev inequalities. Another approach to the interpolation problem may be found in [LO00]. Relation between the two approaches seems unclear to the present authors and perhaps it deserves some further investigation.

However, it is well known that all the $p$-logSob inequalties for $p\in(1,2]$ are in a sense equivalent, at least if we do not care too much about constants (we do not know whether all $p$-logSob inequalities for $p\in(0,1)$ are equivalent in a similar sense).

Let $1<q\leq p\leq 2$. Assume that $q$-logSob holds true with a constant $C>0$. Then also $p$-logSob holds true, with constant $\frac{(p-1)q^{2}}{(q-1)p^{2}}C$.

It follows from [Bak94, Proposition 3.1] that in case of diffusions with invariant measure $\mu$ any $q$-logSob implies any $p$-logSob with the same constant. However, we did not find in the literature any reference to the results of the same form as Proposition 3.3 regarding reversible Markov chains. On the other hand, one can first deduce from $q$-logSob a hypercontractive inequality and then deduce $2$-logSob from it, which in turn yields $p$-logSob. This way around was known before but it yields much worse estimates.

Indeed, since $\frac{(p-1)q^{2}}{(q-1)p^{2}}=\frac{qq^{\prime}}{pp^{\prime}}$ it suffices to prove that ${\mathcal{E}}(g^{1/q},g^{1/q^{\prime}})\leq{\mathcal{E}}(g^{1/p},g^{1/p^{\prime}})$ for every positive $g\in{\mathcal{H}}$, which follows easily from Lemma 2.3 applied to $I=(0,\infty)$, $\varphi_{1}(x)=x^{1/q}$, $\varphi_{2}(x)=x^{1/q^{\prime}}$, $\psi_{1}(x)=x^{1/p}$, and $\psi_{2}(x)=x^{1/p^{\prime}}$. The inequality

Since for every $s>0$ the function $w\mapsto s^{w}+s^{-w}$ is non-decreasing on $[0,\infty)$, we finish the proof by setting $s=a/b$ and noting that $\frac{1}{q}-\frac{1}{2}\geq\frac{1}{p}-\frac{1}{2}\geq 0$. ∎

Usually it is not easy to prove the classical logarithmic Sobolev inequality ($2$-logSob in our notation). On the other hand, the following lemma provides a modified logarithmic Sobolev inequality ($1$-logSob in our notation) for a large class of simple semigroups.

The $p$-logSob inequalities obviously share the tensorization property of the classical logarithmic Sobolev and Poincaré inequalities. This is a standard observation but we include it here for reader’s convenience. For $i=1,$ $2,\ldots,$ $n$ assume that $(\Omega_{i},\mu_{i})$ is a finite (this assumption may be relaxed) probability space with an associated space ${\mathcal{H}}_{i}$ of real functions on $\Omega_{i}$, and a Markov semigroup $(T^{(i)}_{t})_{t\geq 0}:{\mathcal{H}}_{i}\rightarrow{\mathcal{H}}_{i}$ generated by a self-adjoint positive semi-definite operator $L_{i}$ (all of them enjoying properties described in the Preliminaries section). Now let us consider a new semigroup $(T_{t})_{t\geq 0}$ of operators acting on a space ${\mathcal{H}}={\mathcal{H}}_{1}\otimes{\mathcal{H}}_{2}\otimes\ldots\otimes{\mathcal{H}}_{n}$ of real-valued functions on a product probability space

We obtain it by defining its generator $L:{\mathcal{H}}\rightarrow{\mathcal{H}}$ as

Equivalently, we may define it by setting, for $t\geq 0$,

We skip the proof, referring the reader to the classical tensorization argument: subadditivity of entropy (or variance, if $p=0$). ∎

Hypercontractivity

Since, as explained in the preliminaries, $f_{t(p)}$ is also strictly positive, we may apply to it the $p$-logSob inequality, which will yield monotonicity of the map $p\mapsto\|T_{t(p)}f\|_{p}$ upon appropriate choice of the function $t(p)$.

2. Hypercontractivity estimate

Let $r\in(1,2]$ and let $(T_{t})_{t\geq 0}$ be a symmetric Markov semigroup.

Assume that $(T_{t})_{t\geq 0}$ satisfies $r$-logSob with constant $C$. Let $r^{\prime}\leq q\leq p$ or $1<q\leq p\leq r$. Then for every $t\geq\frac{C}{4}\log\frac{p-1}{q-1}$ and every $f\in{\mathcal{H}}$ there is $\|T_{t}f\|_{p}\leq\|f\|_{q}$. In other words, $T_{t}$ is a linear contraction from $L^{q}(\Omega,\mu)$ to $L^{p}(\Omega,\mu)$.

Conversely, if there exists $C>0$ such that

for all $p$ and $q$ such that $1<q<p\leq r$, and for all positive $f\in{\mathcal{H}}$ then $(T_{t})_{t\geq 0}$ sastisfies $r$-logSob with the constant $C$.

That the concepts of logarithmic Sobolev inequality and hypercontractivity are intimately connected goes back to Gross [Gro75]. In fact, the converse part of the above proposition follows from Theorem 1.2 of [Gro75] though we add a short proof here for the sake of completeness. But the hypothesis of the forward direction ($r$-logSob implies hypecontractivity) of our proposition is weaker than that of [Gro75] since [Gro75] assumes that $r$-logSob holds for a nonempty open interval - see Theorem 1.1 of [Gro75] for more details. We also comment that for $r=2$ we recover the part (i) and (ii) of Theorem 3.5 of Diaconis and Saloff-Coste [DSC96] on the classical equivalence of the logarithmic Sobolev inequality and hypercontractivity for the reversible Markov chains (with essentially the same proof).

In the proof of the first assertion without loss of generality we can assume that $f\geq 0$ - indeed, since $T_{t}$ is order preserving, the pointwise inequality $-|f|\leq f\leq|f|$ implies that $|T_{t}f|\leq T_{t}|f|$ pointwise, and thus $\|T_{t}f\|_{p}\leq\|T_{t}|f|\,\|_{p}$ whereas $f$ and $|f|$ have the same $q$-th norm. Furthermore, without loss of generality we may assume that $f$ is strictly positive (which follows by considering functions $f+\varepsilon$ instead of $f$ and then letting $\varepsilon\to 0^{+}$).

Theorem 1.7 and Lemma 3.2 imply that $(T_{t})_{t\geq 0}$ satisfies $s$-logSob with constant $C$ for all $s\in(1,r]\cup[r^{\prime},\infty)$. Let $t(s)=\frac{C}{4}\log\frac{s-1}{q-1}$, so that $t(q)=0$. Then $s^{2}t^{\prime}(s)=\frac{Cs^{2}}{4(s-1)}$ and (4.1) together with the $s$-logSob imply that the map $s\mapsto\|T_{t(s)}f\|_{s}$ in non-increasing on $[q,p]$. Comparing its values at the ends of the interval we arrive at $\|T_{t_{p,q}}f\|_{p}\leq\|f\|_{q}$ for $f>0$, where $t_{p,q}=\frac{C}{4}\log\frac{p-1}{q-1}$. To finish the proof of the first assertion for $t>t_{p,q}$ it suffices to express $T_{t}$ as $T_{t-t_{p,q}}\circ T_{t_{p,q}}$, and use the fact that the semigroup is contractive in $L^{p}$-norm ($p>1$).

To prove the second assertion let us fix some $q\in(1,r)$ and some positive $f\in{\mathcal{H}}$. For $p\in[q,r)$ let $t(p)=\frac{C}{4}\log\frac{p-1}{q-1}$, so that $t(q)=0$. Since the map $p\mapsto\|T_{t(p)}f\|_{p}$ is non-increasing on $[q,r)$ by using (4.1) at $p=q$ we infer that $q$-logSob holds true with the constant $C$. Passing to the limit $q\to r^{-}$ ends the proof. ∎

Reverse hypercontractivity - preliminary results

In this section we prove some preliminary results regarding reverse hypercontractivity.

We first state the following corollary of Jensen’s inequality establishing ‘reverse contraction’:

Indeed, $\Phi$ may be expressed as infimum of a family ${\mathcal{C}}_{\Phi}$ of affine functions:

2. Duality and tensorization

The standard statement of the duality of $L^{p}$-norms is that for $p>1$ and $f\in{\mathcal{H}}$ we have

A slightly less known observation can be found in [Bor82]:

Let $p\in(-\infty,1)$. Then for any positive $f\in{\mathcal{H}}$ there is

We skip its proof since it is an easy exercise.

The standard duality of the $L^{p}$-norms implies that $L^{p^{\prime}}(\Omega,\mu)$ is Banach space dual to $L^{p}(\Omega,\mu)$ for any $p>1$, and from the symmetry of the semigroup $(T_{t})_{t\geq 0}$ we deduce that

The case $p,q\in(-\infty,1)$ is less standard and a bit more delicate (in particular, note that this is no longer the Banach space setting). We will need the following auxiliary result which was previously used by Borell [Bor82].

Let $p,q\in(-\infty,1)$ and $t\geq 0$. Assume that $\|T_{t}f\|_{q}\geq\|f\|_{p}$ for every positive $f\in{\mathcal{H}}$. Then also $\|T_{t}f\|_{p^{\prime}}\geq\|f\|_{q^{\prime}}$ for every positive $f\in{\mathcal{H}}$.

where we have used Lemma 5.2, the symmetry of $T_{t}$, assumptions of the proposition, and again Lemma 5.2. ∎

Assume the set-up of Subsection 3.1. Let $-\infty<q<p<1$. If for each $1\leq i\leq n$, $\|T_{t}^{(i)}f\|_{q}\geq\|f\|_{p}$ for all positive functions $f\in\mathcal{H}_{i}$, then $\|T_{t}f\|_{q}\geq\|f\|_{p}$ for all functions $f\in\mathcal{H}_{(0,\infty)}$.

The proof is an easy modification of the standard argument for showing the usual hypercontractive inequalities tensorize where Minkowski inequality is to be replaced by the reverse Minkowski inequality (Lemma 5.1). We omit details. ∎

Reverse hypercontractivity - general results

We establish an analogue of Proposition 4.1 for $p$ and $q$ below $1$, extending results of Borell, [Bor82]. Now we restrict our considerations to positive functions.

Let $r\in(0,1)$ and let $(T_{t})_{t\geq 0}$ be a symmetric Markov semigroup.

Assume that $(T_{t})_{t\geq 0}$ satisfies $r$-logSob with some constant $C>0$. Let $r^{\prime}\leq q\leq p\leq r$. Then for every $t\geq\frac{C}{4}\log\frac{1-q}{1-p}$ and every positive $f\in{\mathcal{H}}$ there is $\|T_{t}f\|_{q}\geq\|f\|_{p}$.

Conversely, if there exists $C>0$ such that

for all $p$ and $q$ such that $0<q<p\leq r$, and for all positive $f\in{\mathcal{H}}$ then $(T_{t})_{t\geq 0}$ satisfies $r$-logSob with the constant $C$.

Theorem 3.3 of Bakry’s lecture notes [Bak94] established similar equivalence between reverse hypercontractivity and $r$-logSob when $r<1$. Indeed the converse part of Proposition 6.1 follows from that. But the forward direction, which turns out to be more useful in practice, Theorem 3.3 of [Bak94] assumes that $r$-logSob holds for all $r$ belonging to some nonempty open interval instead of a single point.

Let us divide the proof of the first assertion into two basic cases: $0<q\leq p\leq r$ and $r^{\prime}\leq q\leq p<0$ (and in fact we will need to prove only first of them since the second follows then by Proposition 5.3). Once they are proved, the assertion for $0\leq q\leq p\leq r$ and $r^{\prime}\leq q\leq p\leq 0$ will follow by passing to a limit ($q\to 0^{+}$ and $p\to 0^{-}$, respectively), while the case $q<0<p$ will follow from

since $t-\frac{C}{4}\log\frac{1}{1-p}\geq\frac{C}{4}\log(1-q)$ for $t\geq\frac{C}{4}\log\frac{1-q}{1-p}$ (we "glue" the two cases together at zero).

Let us assume $0<q\leq p\leq r$, then. Consider a function $t(q)=\frac{C}{4}\log\frac{1-q}{1-p}$ defined on $(0,p]$. Then $t(p)=0$ and $q^{2}t^{\prime}(q)=\frac{Cq^{2}}{4(q-1)}$, so that by (4.1) the map $q\mapsto\|T_{t(q)}f\|_{q}$ is non-increasing on $(0,p]$ because $r$-logSob implies $q$-logSob, with the same constant $C$, by Theorem 1.7. At the right end of the interval the map takes on the value $\|f\|_{p}$, so that $\|T_{t_{p,q}}f\|_{q}\geq\|f\|_{p}$ for $t_{p,q}=\frac{C}{4}\log\frac{1-q}{1-p}$. For $t>t_{p,q}$ we simply express $T_{t}f$ as $T_{t-t_{p,q}}(T_{t_{p,q}}f)$ and use Lemma 5.1.

To prove the converse assertion, let us fix some $p\in(0,r)$ and a positive $f\in{\mathcal{H}}$. For $q\in(0,p]$ let $t(q)=\frac{C}{4}\log\frac{1-q}{1-p}$, so that $t(p)=0$. Since the map $q\mapsto\|T_{t(q)}f\|_{q}$ is non-decreasing on $(0,p]$ formula (4.1) used at $q=p$ yields $p$-logSob with the constant $C$. Passing to the limit $p\to r^{-}$ ends the proof. ∎

We can now prove Theorem 1.10. In fact we will prove the following result which includes an inverse.

If a symmetric Markov semigroup $(T_{t})_{t\geq 0}$ satisfies $r$-logSob with constant $C$ and $r\geq 1$ then for all $q<p<1$ and every positive $f\in{\mathcal{H}}$ for all $t\geq\frac{C}{4}\log\frac{1-q}{1-p}$ we have $\|T_{t}f\|_{q}\geq\|f\|_{p}$.

Conversely, if for some $C>0$ a symmetric Markov semigroup $(T_{t})_{t\geq 0}$ satisfies $\|T_{\frac{C}{4}\log\frac{1-q}{1-p}}f\|_{q}\geq\|f\|_{p}$ for all $0<q<p<1$ and all positive $f\in{\mathcal{H}}$ then it also satisfies $1$-logSob with the constant $C$.

By Theorem 1.7 for all $r\in(0,1)$ also $r$-logSob holds, with the same constant $C$. The assertion follows immediately from Proposition 6.1.

The converse assertion is easy - Proposition 6.1 implies that $(T_{t})_{t\geq 0}$ satisfies $r$-logSob with the same constant $C$ for all $r\in(0,1)$, and it suffices to pass to the limit ($r\to 1^{-}$). ∎

As in [Bor82, MOR+06] we can now obtain the two function version corollary.

We conclude this section by proving Corollary 1.11.

Indeed, Lemma 3.5 and Proposition 3.7 (in the product case) imply that $(T_{t})_{t\geq 0}$ satisfies $1$-logSob with constant $4$, so that it suffices to use Corollary 6.3. ∎

Improved reverse bounds for simple semigroups

Actually, we can significantly weaken the condition $t\geq\log\frac{1-q}{1-p}$ in Corollary 1.11 for simple operators and prove Theorem 1.12.

It suffices to prove the claim in the case $q<p\leq 0$ - Proposition 5.3 together with an observation that for $0\leq q<p<1$ there is $p^{\prime}<q^{\prime}\leq 0$ and

It is easy to check that $\Psi_{s}$ is a convex function with $\Psi_{s}(0)=\Psi_{s}^{\prime}(0)=0$ and $\Psi_{s}^{\prime\prime}(x)=(1-s)(1+x)^{s-2}$ (actually, the same properties hold true in the case $s>0$, and in the case $s=0$ with $\Psi_{0}(x)=x-\log(1+x)$, but we will not need those). The inequality

holds true for every $x\in(-1,\infty)$. Indeed, due to the properties of $\Psi_{s}$ listed above it suffices to prove that

which immediately follows from the elementary inequality $(1+x)^{\theta}\leq 1+\theta x$, and from the fact that the map

which ends the proof - recall that the exponent $p$ is negative. The first inequality above was just an application of the elementary $(1+x)^{a}\leq 1+ax$, with $a=|p|/|q|\in(0,1)$, $x>-1$. The last inequality follows from the fact that $\Psi_{s}$ obtains its minimum at $s=0$.

The case $p=0$ follows by an obvious limit transition. ∎

Note that we could obtain a better reverse hypercontractivity constant than those given in Theorem 1.12 by first maximizing the function $\Psi_{q}^{\prime\prime}(\theta x)/\Psi_{p}^{\prime\prime}(x)$ over $x\in(-1,\infty)$ and then by trying to solve for $\theta$ in terms of $p$ and $q$ such that (7.2) holds. This would lead to an equation of the form

But unfortunately, in general, $\theta$ can not be recovered explicitly from the above equation. However, in the special case when $-\infty<q<p=0$, $\theta$ can explicitly be solved as

as $q\rightarrow 0^{-}$ and, equivalently, $q^{\prime}\rightarrow 0^{+}$. Thus, under assumptions of Theorem 1.12 about the semigroup, there exists a function $\eta:(-\infty,0)\longrightarrow(0,\infty)$ given by $\eta(q)=-\log\theta(q)$, with $\eta(q)=-\frac{1}{2}q-\frac{1}{4}q^{2}+O(q^{3})$ as $q\rightarrow 0^{-}$, such that for all $q<0$ and positive $f$ we have $\|T_{t}f\|_{q}\geq\|f\|_{0}$ for every $t\geq\eta(q)$. Also, by duality, there exists a function $\tau:(0,1)\longrightarrow(0,\infty)$ given by $\tau(p)=-\log\theta(p^{\prime})$, with $\tau(p)=\frac{1}{2}p+\frac{1}{4}p^{2}+O(p^{3})$ as $p\rightarrow 0^{+}$, such that for all $p\in(0,1)$ and positive $f$ we have $\|T_{t}f\|_{0}\geq\|f\|_{p}$ for every $t\geq\tau(p)$.

for all $t\geq\log\frac{(2-p)(2-q)}{4(1-p)(1-q)}$.

where we used Theorem 1.12 in the first and the second inequality and Lemma 5.1 in the third inequality. ∎

We now obtain the following corollary regarding $\rho$-correlation.

Consider a product space $(\Omega,\mu)=(\prod_{i=1}^{n}\Omega_{i},\otimes_{i=1}^{n}\mu_{i})$ where $(\Omega_{i},\mu_{i})$ are finite probability spaces. We say that $(x,y)\in\Omega^{2}$ are $\rho$-correlated if $x$ is distributed according to $\mu$ and the conditional distribution of $y$ given $x$ is given as follows: for each $i$ independently, with probability $\rho$, $y_{i}=x_{i}$ and with probability $1-\rho$, $y_{i}$ is sampled independently from $\mu_{i}$.

Let $(\Omega,\mu)$ be the product probability space in Definition 7.3. Let $A,B\subseteq\Omega$ be two sets such that $\mu\{A\},\mu\{B\}\geq\epsilon\geq 0$. Let $x$ be distributed according to the product measure $\mu$ and $y$ be a $\rho$-correlated copy of $x$ for some $0\leq\rho<1$. Then

Let $f$ and $g$ be the characteristic functions of the sets $A$ and $B$ respectively. Note that

for all $0<p,q<1$ such that $\rho=\frac{4(1-p)(1-q)}{(2-p)(2-q)}$. We now take $p=q=\frac{2(1-\sqrt{\rho})}{2-\sqrt{\rho}}$ in (7.6) to conclude the proof. ∎

We can also use Corollary 6.4 which deals with general symmetric Markov semigroups to get a lower bound $\epsilon^{\frac{2}{1-\sqrt{\rho}}}$. But this bound is worse than what we have achieved by using Corollary 7.2 that improves on the bounds provided by Corollary 6.4 in the case of simple semigroups.

which holds for all $\rho\in[0,1)$. We skip some tedious but straightforward calculations.

Under assumptions of Lemma 7.4 we also have

where $\kappa$ is some universal constant. This is a significant strengthening when $\rho$ is close to $1$, especially in view of Remark 7.6.

Indeed, it suffices to notice that in the proof of Corollary 7.2 one can take $t_{1}=\tau(p)$ and $t_{2}=\tau(q)$, using Remark 7.1 rather than Theorem 1.12. Thus (7.4) holds true for all $t\geq\tau(p)+\tau(q)$. Let us set $p=q=1-\rho-C\cdot(1-\rho)^{3}$. The asymptotic behavior of $\tau(p)$ established in Remark 7.1 implies that $e^{-2\tau(p)}=1-p+O(p^{3})$ as $p\rightarrow 0^{+}$. Thus, by choosing the constant $C$ large enough and $\hat{\rho}\in(0,1)$ close enough to $1$, we prove that for $\rho\in(\hat{\rho},1)$ there is $e^{-2\tau(p)}\geq\rho$, i.e., $2\tau(p)\leq\log(1/\rho)$, and therefore (7.4) holds true for $t=\log(1/\rho)$. By repeating the proof of Lemma 7.4 we arrive at

for $\rho\in(\hat{\rho},1)$. This, together with (7.5) used for $\rho\leq\hat{\rho}$, yields (7.7).

A similar asymptotic strengthening applies to many further results of the next two sections (whenever one deals with simple semigroups and their tensor products, and also in Section 8 for $\alpha,\alpha^{\star}$ close to zero) but we will omit these generalizations for the sake of brevity.

Reverse hypercontractivity for some non-simple operators

For some of the applications afterwards we will be interested in operators that are not necessarily simple but are obtained by composing a simple operator with a non-simple operator. In this section we extend some of the reverse hypercontractive results to this setup.

Assume that $(\Omega,\mu)$ is a finite probability space and $K$ is Markov kernel on $\Omega$. Let $\nu=\mu K$ and

Thus $S:=T_{-\alpha^{\star}}\circ K$ is Markovian and the kernel $K$ can be written as composition of two Markov kernels in the following way:

Using the decomposition (8.2), by Theorem 1.12 we obtain

Consider the set-up of Proposition 8.1. Then for all $0<p,q<1$ and all nonnegative $f,g$, we have

for all $\alpha^{\star}\geq\log\frac{(2-p)(2-q)}{4(1-p)(1-q)}$.

where $x=(x_{1},x_{2},\ldots,x_{n})$ and $y=(y_{1},y_{2},\ldots,y_{n})$ are $\Omega^{n}$-valued random variables.

Let $f$ and $g$ be the characteristic function of the sets $A$ and $B$ respectively. Note that

for all $0<p,q<1$ such that $1-\alpha=\frac{4(1-p)(1-q)}{(2-p)(2-q)}$. We take $p=q=\frac{2(1-\sqrt{1-\alpha})}{2-\sqrt{1-\alpha}}$ to conclude the proof. ∎

The following example shows that the condition $\alpha>0$ cannot be dropped in general. Take $\Omega=\{0,1\}$ and $\mu$ to be the unbiased Bernoulli measure on $\Omega$. Let the kernel $K$ be as follows:

Mixing of Markov chains for big sets

In this section we prove Theorem 1.14 which establishes mixing for Markov chains satisfying $1$-logSob. We then give a number of examples where the theorem can be applied to yield new results on mixing of Markov chains starting from big sets. We begin with a proof of the theorem:

Take $f$ and $g$ to be the characteristic functions of $A$ and $B$, respectively. Then by Corollary 6.4, for any choice of $0<p,q<1$ with $(1-p)(1-q)=e^{-4t/C}$, we get

By setting $p=\frac{1-e^{-4t/C}}{1+e^{-2t/C}(b/a)}$ and $q=\frac{1-e^{-4t/C}}{1+e^{-2t/C}(a/b)}$ (this choice follows from a simple optimization) we conclude the proof. ∎

and the corresponding Markov semigroup can be expressed as

From Lemma 3.5, Proposition 3.7 and Theorem 1.14 it follows that:

Let $X_{t}$ be the continuous-time random walk on the general hypercube $(\Omega^{n},\mu^{\otimes n})$ with $X_{0}$ distributed according to the product measure $\mu^{\otimes n}$. Let $a,b\geq 0$ and $\tau>0$. Then for any $A,B\subseteq\Omega^{n}$ with $\mu^{\otimes n}\{A\}=e^{-a^{2}/2}$ and $\mu^{\otimes n}\{B\}=e^{-b^{2}/2}$, and for $t\geq\tau n$, we have

In fact, a much better bound can be obtained by repeating the proof of Theorem 1.14 with the two function bound in Corollary 6.4 which applies to simple operators and their tensors:

Let $X_{t}$ be the continuous-time random walk on the general hypercube $(\Omega^{n},\mu^{\otimes n})$ with $X_{0}$ distributed according to the product measure $\mu^{\otimes n}$. Let $a,b\geq 0$ and $\tau>0$. Then for any $A,B\subseteq\Omega^{n}$ with $\mu^{\otimes n}\{A\}=e^{-a^{2}/2}$ and $\mu^{\otimes n}\{B\}=e^{-b^{2}/2}$, and for $t\geq\tau n$, we have

Note that the pair $(X_{0},X_{t})$ is $\rho$-correlated in the sense of Definition 7.3, with $\rho=e^{-t/n}$. Let $p=\frac{(2-2\rho)a}{b\sqrt{\rho}+(2-\rho)a}$ and $q=\frac{(2-2\rho)b}{a\sqrt{\rho}+(2-\rho)b}$, so that $p,q\in(0,1)$ and $\frac{4(1-p)(1-q)}{(2-p)(2-q)}=\rho$. By Corollary 7.2 applied to $f=1_{A}$ and $g=1_{B}$ we have