# 8.4 Logarithmic Sobolev inequalities

xxx For NOTES: For history and literature, see ([117], first paragraph and end of Section 1).

xxx For NOTES: Somewhere mention relaxing to nonreversible chains.

## 8.4.1 The log-Sobolev time $\tau_{l}$

Given a probability distribution $\pi$ on a finite set $I$, define

xxx For NOTES: Persi’s $\mbox{{\cal L}}(g)$ is double ours.

 $\mbox{{\cal L}}(g):=\sum_{i}\pi_{i}g^{2}(i)\log(|g(i)|/\|g\|_{2})$ (8.52)

for $g\not\equiv 0$, recalling $\|g\|^{2}_{2}=\sum_{i}\pi_{i}g^{2}(i)$ and using the convention $0\log 0=0$. By Jensen’s inequality,

 $\mbox{{\cal L}}(g)\geq 0$, with equality if and only if $|g|$ is constant.

Given a finite, irreducible, reversible Markov chain with stationary distribution $\pi$, define the logarithmic Sobolev (or log-Sobolev) time by

xxx For NOTES: Persi’s $\alpha$ is $1/(2\tau_{l})$.

xxx Note $\tau_{l}<\infty$. (Show?) See also Corollary 8.27.

 $\tau_{l}:=\sup\{\mbox{{\cal L}}(g)/\mbox{{\cal E}}(g,g):g\not\equiv\mbox{% constant}\}.$ (8.53)

Notice the similarity between (8.53) and the extremal characterization of $\tau_{2}$ (Chapter 3, Theorem yyy:22):

 $\tau_{2}=\sup\{\|g\|^{2}_{2}/\mbox{{\cal E}}(g,g):\sum_{i}\pi_{i}g(i)=0,\ \ % g\not\equiv 0\}.$

We discuss exact computation of $\tau_{l}$ in Section 8.4.3, the behavior of $\tau_{l}$ for product chains in Section 8.4.4, and a comparison method for bounding $\tau_{l}$ in Section 8.4.5. In Section 8.4.2 we focus on the connection between $\tau_{l}$ and mixing times. A first such result asserts that the relaxation time does not exceed the log-Sobolev time:

###### Lemma 8.22

$\tau_{2}\leq\tau_{l}$.

xxx Remarks about how “usually” equality?

xxx For NOTES: Proof from [302], via [117].

Proof. Given $g\not\equiv\mbox{constant}$ and $\epsilon$, let $f:=1+\epsilon g$. Then, writing $\bar{g}=\sum_{i}\pi_{i}g(i)$, and with all asymptotics as $\epsilon\to 0$,

 $\displaystyle\log|f|^{2}$ $\displaystyle=$ $\displaystyle 2\epsilon g-\epsilon^{2}g^{2}+O(\epsilon^{3}),$ $\displaystyle\log\|f\|^{2}_{2}$ $\displaystyle=$ $\displaystyle 2\epsilon\bar{g}+\epsilon^{2}\|g\|^{2}_{2}-2\epsilon^{2}\bar{g}^% {2}+O(\epsilon^{3}),$ $\displaystyle\log\frac{|f|^{2}}{\|f\|^{2}_{2}}$ $\displaystyle=$ $\displaystyle 2\epsilon(g-\bar{g})+\epsilon^{2}(2\bar{g}^{2}-\|g\|^{2}_{2}-g^{% 2})+O(\epsilon^{3}).$

Also,

 $f^{2}=1+2\epsilon g+\epsilon^{2}g^{2};$

thus

 $f^{2}\log(|f|^{2}/\|f\|^{2}_{2})=2\epsilon(g-\bar{g})+\epsilon^{2}(3g^{2}-\|g% \|^{2}_{2}-4g\bar{g}+2\bar{g}^{2})+O(\epsilon^{3})$

and so

 $\mbox{{\cal L}}(f)=\epsilon^{2}(\|g\|^{2}_{2}-\bar{g}^{2})+O(\epsilon^{3})=% \epsilon^{2}{{\rm var}}_{\pi}\,g+O(\epsilon^{3}).$

Furthermore, $\mbox{{\cal E}}(f,f)=\epsilon^{2}\mbox{{\cal E}}(g,g)$; therefore

 $\tau_{l}\geq\frac{\mbox{{\cal L}}(f)}{\mbox{{\cal E}}(f,f)}=\frac{{{\rm var% }}_{\pi}\,g}{\mbox{{\cal E}}(g,g)}+O(\epsilon).$

Finish by letting $\epsilon\to 0$ and then taking the supremum over $g$.

## 8.4.2 $\tau_{l}$, mixing times, and hypercontractivity

In this subsection we discuss the connection between the $L^{2}$ threshold time parameter

 ${\hat{\tau}}=\inf\{t>0:\sqrt{{\hat{d}}(2t)}=\max_{i}\|P_{i}(X_{t}\in\cdot)-\pi% (\cdot)\|_{2}\leq e^{-1}\}$ (8.54)

and the log-Sobolev time $\tau_{l}$. As in Section 8.3, we again consider the fundamental quantity

 $N(s)=\|{\bf P}_{s}\|_{2\to\infty}$

arising in the bound on $\sqrt{{\hat{d}}(2t)}$ in Lemma 8.13, and recall from Section 8.3.1 that

 $N(s)$ decreases strictly monotonically from $\pi^{-1/2}_{*}$ at $s=0$ to $1$ as $s\uparrow\infty$.

The function $N$ is continuous. It would be nice (especially for use in conjunction with the comparison technique) if we could characterize, in terms of the Dirichlet form ${\cal E}$, the value of $s$, call it $s^{*}$, such that $N(s)$ equals $2$ (say), but such a characterization is not presently available.

xxx For NOTES?: A partial result is Theorem 3.9 in [117], taking $q=\infty$.

###### Open Problem 8.23

Characterize $s^{*}$ in terms of ${\cal E}$.

To carry on along these general lines, it turns out to be somewhat more convenient to substitute use of

 $\hskip{21.681pt}\|P(X_{t}\in\cdot)-\pi(\cdot)\|_{2}\leq\|P(X_{0}\in\cdot)\|_{% \frac{q}{q-1}}\,\|{\bf P}_{s}\|_{2\to q}\,e^{-(t-s)/\tau_{2}},\ \ \ 2\leq q<\infty,$ (8.55)

an immediate consequence of Lemmas 8.11 and 8.12 and (8.34), for use of Lemma 8.13. The reason is that, like $N(s)$, $\|{\bf P}_{s}\|_{2\to q}$ decreases monotonically to $1$ as $s\uparrow\infty$; but, unlike $N(s)$, it turns out that

 for each $q\geq 2$, $\|{\bf P}_{s}\|_{2\to q}$ equals $1$ for all sufficiently large $s$. (8.56)

The property (8.56) is called hypercontractivity, in light of the facts that, for fixed $s$, ${\bf P}_{s}$ is a contraction on $L^{2}$ and $\|{\bf P}_{s}\|_{2\to q}$ is increasing in $q$. Let

 $s_{q}:=\inf\{s\geq 0:\|{\bf P}_{s}\|_{2\to q}\leq 1\}=\inf\{s:\|{\bf P}_{s}\|_% {2\to q}=1\};$

then $s_{2}=0, and we will see presently that $s_{q}<\infty$ for $q\geq 2$. The following theorem affords a connections with the log-Sobolev time $\tau_{l}$ (and hence with the Dirichlet form ${\cal E}$).

###### Theorem 8.24

For any finite, irreducible, reversible chain,

 $\tau_{l}=\sup_{2

Proof. The theorem is equivalently rephrased as follows:

 $\|{\bf P}_{t}\|_{2\to q}\leq 1$ for all $t\geq 0$ and $2\leq q<\infty$ satisfying $e^{2t/u}\geq q-1$ (8.57)

if and only if $u\geq\tau_{l}$. The proof will make use of the generalization

 $\mbox{{\cal L}}_{q}(g):=\sum_{i}\pi_{i}|g(i)|^{q}\log(|g(i)|/\|g\|_{q})$

of (8.52). Fixing $0\not\equiv g\geq 0$ and $u>0$, we will also employ the notation

 $\displaystyle q(t)$ $\displaystyle:=$ $\displaystyle 1+e^{2t/u},\ \ \ G(t):=\|{\bf P}_{t}g\|^{q(t)}_{q(t)},$ (8.58) $\displaystyle F(t)$ $\displaystyle:=$ $\displaystyle\|{\bf P}_{t}g\|_{q(t)}=\exp\left[\frac{1}{q(t)}\log G(t)\right]$

for $t\geq 0$.

As a preliminary, we compute the derivative of $F$. To begin, we can proceed as at the start of the proof of Lemma 8.10(a) to derive

 $G^{\prime}(t)=-q(t)\,\mbox{{\cal E}}\left({\bf P}_{t}g,({\bf P}_{t}g)^{q(t)-% 1}\right)+\frac{q^{\prime}(t)}{q(t)}E_{\pi}\left[({\bf P}_{t}g)^{q(t)}\log% \left(({\bf P}_{t}g)^{q(t)}\right)\right].$

Then

 $\displaystyle F^{\prime}(t)$ $\displaystyle=$ $\displaystyle\left[\frac{G^{\prime}(t)}{q(t)G(t)}-\frac{q^{\prime}(t)\log G(t)% }{q^{2}(t)}\right]F(t)$ (8.59) $\displaystyle=$ $\displaystyle F(t)^{-(q(t)-1)}\left[\frac{q^{\prime}(t)}{q(t)}\mbox{{\cal L}% }_{q(t)}({\bf P}_{t}g)-\mbox{{\cal E}}\left({\bf P}_{t}g,({\bf P}_{t}g)^{q(t% )-1}\right)\right].$

For the first half of the proof we suppose that (8.57) holds and must prove $\tau_{l}\leq u$, that is, we must establish the log-Sobolev inequality

 $\mbox{{\cal L}}(g)\leq u\,\mbox{{\cal E}}(g,g)$ for every $g$. (8.60)

To establish (8.60) it is enough to consider $0\not\equiv g>0$,

xxx Do we actually use $g\geq 0$ here?

since for arbitrary $g$ we have

 $\mbox{{\cal L}}(g)=\mbox{{\cal L}}(|g|)$ and $\mbox{{\cal E}}(g,g)\geq\mbox{{\cal E}}(|g|,|g|)$. (8.61)

Plugging the specific formula (8.58) for $q(t)$ into (8.59) and setting $t=0$ gives

 $F^{\prime}(0)=\|g\|^{-1}_{2}(u^{-1}\mbox{{\cal L}}(g)-\mbox{{\cal E}}(g,g)).$ (8.62)

Moreover, since

 $\displaystyle F(t)=\|{\bf P}_{t}g\|_{q(t)}$ $\displaystyle\leq$ $\displaystyle\|{\bf P}_{t}\|_{2\to q(t)}\|g\|_{2}\leq\|g\|_{2}\mbox{\ \ \ by~{% }(\ref{rephrase})}$ $\displaystyle=$ $\displaystyle\|{\bf P}_{0}g\|_{2}=F(0),$

the (right-hand) derivative of $F$ at $0$ must be nonpositive. The inequality (8.60) now follows from (8.62).

For the second half of the proof, we may assume $u=\tau_{l}$ and must establish (8.57). For $g\geq 0$, (8.53) and Lemma 8.25 (to follow) give

 $\frac{q}{2}\mbox{{\cal L}}_{q}(g)=\mbox{{\cal L}}(g^{q/2})\leq\tau_{l}\,% \mbox{{\cal E}}(g^{q/2},g^{q/2})\leq\frac{q^{2}\tau_{l}}{4(q-1)}\mbox{{\cal E% }}(g,g^{q-1})$ (8.63)

for any $1. With $q(t):=1+e^{2t/\tau_{l}}$, we have $q^{\prime}(t)=\frac{2}{\tau_{l}}(q(t)-1)$, and replacing $g$ by ${\bf P}_{t}g$ in (8.63) we obtain

 $\frac{q^{\prime}(t)}{q(t)}\mbox{{\cal L}}_{q(t)}({\bf P}_{t}g)-\mbox{{\cal E% }}\left({\bf P}_{t}g,({\bf P}_{t}g)^{q(t)-1}\right)\leq 0.$

From (8.59) we then find $F^{\prime}(t)\leq 0$ for all $t\geq 0$. Since $F(0)=\|g\|_{2}$, this implies

 $\|{\bf P}_{t}g\|_{q(t)}\leq\|g\|_{2}.$ (8.64)

We have assumed $g\geq 0$, but (8.64) now extends trivially to general $g$, and therefore

 $\|{\bf P}_{t}\|_{2\to q(t)}\leq 1.$

This gives the desired hypercontractivity assertion (8.57).

Here is the technical Dirichlet form lemma that was used in the proof of Theorem 8.24.

###### Lemma 8.25

$\mbox{{\cal E}}(g,g^{q-1})\geq\frac{4(q-1)}{q^{2}}\mbox{{\cal E}}(g^{q/2},% g^{q/2})$ for $g\geq 0$ and $1.

xxx Do we somewhere have the following?:

 $\mbox{{\cal E}}(f,g)={\textstyle\frac{1}{2}}\sum_{i}\sum_{j\neq i}\pi_{i}q_{% ij}(f(i)-f(j))(g(i)-g(j)).$ (8.65)

Proof. For any $0\leq a

 $\displaystyle\left(\frac{b^{q/2}-a^{q/2}}{b-a}\right)^{2}$ $\displaystyle=$ $\displaystyle\left(\frac{q}{2(b-a)}\int_{a}^{b}t^{\frac{q}{2}-1}\,dt\right)^{2}$ $\displaystyle\leq$ $\displaystyle\frac{q^{2}}{4(b-a)}\int_{a}^{b}t^{q-2}\,dt=\frac{q^{2}}{4(q-1)}% \frac{b^{q-1}-a^{q-1}}{b-a}.$

This shows that

 $(b^{q-1}-a^{q-1})(b-a)\geq\frac{4(q-1)}{q^{2}}(b^{q/2}-a^{q/2})^{2}$

and the lemma follows easily from this and (8.65).

Now we are prepared to bound ${\hat{\tau}}$ in terms of $\tau_{l}$.

###### Theorem 8.26

(a) If $c\geq 0$, then for any state $i$ with $\pi_{i}\leq e^{-1}$,

 $\|P_{i}(X_{t}\in\cdot)-\pi(\cdot)\|_{2}\leq e^{1-c}$ for $t\geq{\textstyle\frac{1}{2}}\tau_{l}\log\log{\textstyle\frac{1}{\pi_{i}}}+c% \tau_{2}$.

(b)

 ${\hat{\tau}}\leq{\textstyle\frac{1}{2}}\tau_{l}\log\log{\textstyle\frac{1}{\pi% _{*}}}+2\tau_{2}\leq\tau_{l}({\textstyle\frac{1}{2}}\log\log{\textstyle\frac{1% }{\pi_{*}}}+2).$

Proof. Part (b) follows immediately from (8.54), part (a), and Lemma 8.22. To prove part (a), we begin with (8.55):

 $\|P_{i}(X_{t}\in\cdot)-\pi(\cdot)\|_{2}\leq\pi^{-1/q}_{i}\,\|{\bf P}_{s}\|_{2% \to q}\,e^{-(t-s)/\tau_{2}}.$

As in the second half of the proof of Theorem 8.24, let $q=q(s):=1+e^{2s/\tau_{l}}$. Then $\|{\bf P}_{s}\|_{2\to q(s)}\leq 1$. Thus

 $\|P_{i}(X_{t}\in\cdot)-\pi(\cdot)\|_{2}\leq\pi^{-1/q(s)}_{i}\,e^{-(t-s)/\tau_{% 2}},\ \ \ 0\leq s\leq t.$

Choosing $s=\frac{1}{2}\tau_{l}\log\log(\frac{1}{\pi_{i}})$ we have $q(s)=1+\log(\frac{1}{\pi_{i}})$ and thus

 $\|{\bf P}_{i}(X_{t}\in\cdot)-\pi(\cdot)\|_{2}\leq\exp(1-\frac{t-s}{\tau_{2}})$ for $t\geq s$.

We have established the upper bound in the following corollary; for the lower bound, see Corollary 3.11 in [117].

###### Corollary 8.27
 $\tau_{l}\leq{\hat{\tau}}\leq\tau_{l}({\textstyle\frac{1}{2}}\log\log{% \textstyle\frac{1}{\pi_{*}}}+2).$

Examples illustrating the improvement Corollary 8.27 affords over the similar result (8.7) in terms of $\tau_{2}$ are offered in Examples 8.37 and 8.40.

## 8.4.3 Exact computation of $\tau_{l}$

Exact computation of $\tau_{l}$ is exceptionally difficult—so difficult, in fact, that $\tau_{l}$ is known only for a handful of examples. We present some of these examples in this subsection.

###### Example 8.28

Trivial two-state chains.

We consider a discrete-time chain on $\{0,1\}$ that jumps in one step to stationarity (or, since the value of $\tau_{l}$ is unaffected by continuization, the corresponding continuized chain). Thus $(p_{00},p_{01},p_{10},p_{11})=(\theta,1-\theta,\theta,1-\theta)$ with $\theta=\pi_{0}=1-\pi_{1}$. We also assume $0<\theta\leq 1/2$. The claim is that

 $\theta\neq 1/2$ (8.66)

Note that this is continuous and decreasing for $\theta\in(0,1/2]$.

To prove (8.66), we need to show that $\mbox{{\cal L}}(g)/\mbox{{\cal E}}(g,g)\leq\tau(\theta)$ for every nonconstant $g$ on $\{0,1\}$, where $\tau(\theta)$ denotes the righthand side of (8.66), with equality for some $g_{0}$. First suppose $\theta\neq 1/2$. For the inequality, as at (8.60)–(8.61) we may suppose $g\geq 0$ and, by homogeneity,

 $E_{\pi}g=\theta g(0)+(1-\theta)g(1)=1.$

We will work in terms of the single variable

 $x:=1/(g(0)-g(1)),$

so that

 $g(0)=1+\frac{1-\theta}{x},\ \ \ g(1)=1-\frac{\theta}{x}$

and we must consider $x\in(-\infty,-(1-\theta)]\cup[\theta,\infty)$. We calculate

 $\displaystyle\mbox{{\cal E}}(g,g)$ $\displaystyle=$ $\displaystyle\theta(1-\theta)(g(0)-g(1))^{2}=\theta(1-\theta)/x^{2},$ $\displaystyle\|g\|^{2}_{2}$ $\displaystyle=$ $\displaystyle\theta\left(1+\frac{1-\theta}{x}\right)^{2}+(1-\theta)\left(1-% \frac{\theta}{x}\right)^{2}$ $\displaystyle=$ $\displaystyle[\theta(x+1-\theta)^{2}+(1-\theta)(x-\theta)^{2}]/x^{2}=1+\frac{% \theta(1-\theta)}{x^{2}},$ $\displaystyle\ell(x)$ $\displaystyle:=$ $\displaystyle\mbox{{\cal L}}(g)=\theta\left(1+\frac{1-\theta}{x}\right)^{2}% \log\left(1+\frac{1-\theta}{x}\right)$ $\displaystyle +(1-\theta)\left(1-\frac{\theta}{x}\right)^{2}\log\left(1-% \frac{\theta}{x}\right)$ $\displaystyle -\frac{1}{2}\theta\left(1+\frac{\theta(1-\theta)}{x^{2}}% \right)\log\left(1+\frac{\theta(1-\theta)}{x^{2}}\right)$ $\displaystyle=$ $\displaystyle\left[\theta(x+1-\theta)^{2}\log(x+1-\theta)^{2}+(1-\theta)(x-% \theta)^{2}\log(x-\theta)^{2}\right.$ $\displaystyle \left.-(x^{2}+\theta(1-\theta))\log(x^{2}+\theta(1-\theta))% \right]/(2x^{2}),$ $\displaystyle r(x)$ $\displaystyle:=$ $\displaystyle 2\theta(1-\theta)\frac{\mbox{{\cal L}}(g)}{\mbox{{\cal E}}(g% ,g)}=2x^{2}\ell(x)$ $\displaystyle=$ $\displaystyle\theta(x+1-\theta)^{2}\log(x+1-\theta)^{2}+(1-\theta)(x-\theta)^{% 2}\log(x-\theta)^{2}$ $\displaystyle -(x^{2}+\theta(1-\theta))\log(x^{2}+\theta(1-\theta)).$

¿From here, a straightforward but very tedious calculus exercise shows that $r$ decreases over $(-\infty,-(1-\theta)]$, with $r(-\infty)=2\theta(1-\theta)$, and that $r$ is strictly unimodal over $[\theta,\infty)$, with $r(\theta)=0$ and $r(\infty)=2\theta(1-\theta)$. It follows that $r(x)$ is maximized over $(-\infty,-(1-\theta)]\cup[\theta,\infty)$ by taking $x$ to be the unique root to

 $\displaystyle 0$ $\displaystyle=$ $\displaystyle r^{\prime}(x)=4\theta(x+(1-\theta))\log(x+(1-\theta))$ (8.67) $\displaystyle +\,4(1-\theta)(x-\theta)\log(x-\theta)-2x\log(x^{2}+\theta(1% -\theta))$

over $(\theta,\infty)$.

There is on hope for solving (8.67) explicitly unless

 $x^{2}+\theta(1-\theta)=(x+1-\theta)(x-\theta),$

i.e., $x=2\theta(1-\theta)/(1-2\theta)$. Fortunately, this is a solution to (8.67), and it falls in $(\theta,\infty)$. The corresponding value of $r$ is $\frac{\theta(1-\theta)}{1-2\theta}\log\frac{1-\theta}{\theta}$, so (8.66) follows, and we learn furthermore that the function $g$ maximizing $\mbox{{\cal L}}(g)/\mbox{{\cal E}}(g,g)$ is $g_{0}$, with $g_{0}(0)=\frac{1}{2\theta}$ and $g_{0}(1)=\frac{1}{2(1-\theta)}$.

For $\theta=1/2$, the major change is that now $r$ is increasing, rather than unimodal, over $[\theta,\infty)$. Thus $r_{\sup}=2\theta(1-\theta)=1/2$, and (8.66) again follows.

###### Example 8.29

Two-state chains.

Now consider any irreducible chain (automatically reversible) on $\{0,1\}$, with stationary distribution $\pi$. Without loss of generality we may suppose $\pi_{0}\leq\pi_{1}$. We claim that

 $\pi_{0}\neq 1/2$

The proof is easy. The functional $\mbox{{\cal L}}(g)$ depends only on $\pi$ and so is unchanged from Example 8.28, and the Dirichlet form changes from $\mbox{{\cal E}}(g,g)=\pi_{0}\pi_{1}(g(0)-g(1))^{2}$ in Example 8.28 to $\mbox{{\cal E}}(g,g)=p_{01}(g(0)-g(1))^{2}$ here.

Remark. Recall from Chapter 5, Example yyy:4 that $\tau_{2}=1/(p_{01}+p_{10})=\pi_{1}/p_{01}$. It follows that

 $0<\pi_{0}<1/2$

is a continuous and decreasing function of $\pi_{0}$. In particular, we have equality in Lemma 8.22 for a two-state chain if and only if $\pi_{0}=1/2$. Moreover,

 $\pi_{0}\to 0$
###### Example 8.30

Trivial chains.

The proof of Lemma 8.22 and the result of Example 8.28 can be combined to prove the following result: For the “trivial” chain with $p_{ij}\equiv\pi_{j}$, the log-Sobolev time $\tau_{l}$ is given (when $\pi_{*}<1/2$) by

 $\tau_{l}=\frac{\log(\frac{1}{\pi_{*}}-1)}{2(1-2\pi_{*})}.$

We omit the details, referring the reader to Theorem 5.1 of [117].

As an immediate corollary, we get a reverse-inequality complement to Lemma 8.22:

###### Corollary 8.31

For any reversible chain (with $\pi_{*}<1/2$, which is automatic for $n\geq 3$),

 $\tau_{l}\leq\tau_{2}\frac{\log(\frac{1}{\pi_{*}}-1)}{2(1-2\pi_{*})}.$

Proof. The result of Example 8.30 can be written

 $\mbox{{\cal L}}(g)\leq({{\rm var}}_{\pi}\,g)\frac{\log(\frac{1}{\pi_{*}}-1)}% {2(1-2\pi_{*})},$

and ${{\rm var}}_{\pi}\,g\leq\tau_{2}\mbox{{\cal E}}(g,g)$ by the extremal characterization of $\tau_{2}$.

###### Example 8.32

The complete graph.

It follows readily from Example 8.30 that the continuized walk of the complete graph has

 $\tau_{l}=\frac{(n-1)\log(n-1)}{2(n-2)}\sim\frac{1}{2}\log n.$

Since $\tau_{2}=(n-1)/n$, equality holds in Corollary 8.31 for this example.

xxx Move the following warning to follow Corollary 8.27, perhaps?

Warning.  Although the ratio of the upper bound on ${\hat{\tau}}$ to lower bound in Corollary 8.27 is smaller than that in (8.7), the upper bound in Corollary 8.27 is sometimes of larger order of magnitude than the upper bound in (8.7). For the complete graph, (8.7) says

 ${\textstyle\frac{n-1}{n}}\leq{\hat{\tau}}\leq{\textstyle\frac{n-1}{n}}({% \textstyle\frac{1}{2}}\log n+1)$

and Corollary 8.27 yields

 $(1+o(1)){\textstyle\frac{1}{2}}\log n\leq{\hat{\tau}}\leq(1+o(1)){\textstyle% \frac{1}{4}}(\log n)(\log\log n),$

while, from Chapter 5, yyy:(33) it follows that

 ${\hat{\tau}}={\textstyle\frac{1}{2}}\log n+O\left(\frac{\log n}{n}\right).$

As another example, the product chain development in the next subsection together with Example 8.29 will give $\tau_{l}$ exactly for the $d$-cube. On the other hand, the exact value of $\tau_{l}$ is unknown even for many of the simplest examples in Chapter 5. For instance,

###### Open Problem 8.33

Calculate $\tau_{l}$ for the $n$-cycle (Chapter 5 Example yyy:7) when $n\geq 4$.

xxx For NOTES: $n=3$ is complete graph $K_{3}$, covered by Example 8.32. ($\tau_{l}=\log 2$ for $n=3$.)

Notwithstanding Open Problem 8.33, the value of $\tau_{l}$ is known up to multiplicative constants. Indeed, it is shown in Section 4.2 in [117] that

 $\frac{1}{4\pi^{2}}n^{2}\leq\tau_{l}\leq\frac{25}{16\pi^{2}}n^{2}.$

Here is a similar result we will find useful later in dealing with our running example of the grid.

###### Example 8.34

The $m$-path with end self-loops.

For this example, discussed above in Example 8.16, we claim

 $\frac{2}{\pi^{2}}m^{2}\leq\tau_{l}\leq m^{2}.$

The lower bound is easy, using Lemma 8.22:

 $\tau_{l}\geq\tau_{2}=(1-\cos(\pi/m))^{-1}\geq\frac{2}{\pi^{2}}m^{2}.$

For the upper bound we use Corollary 8.27 and estimation of ${\hat{\tau}}$. Indeed, in Example 8.16 it was shown that

 ${\hat{d}}(2t)=N^{2}(t)-1\leq\left[1+(4t/m^{2})^{-1/2}\right]\,\exp(-4t/m^{2}),% \ \ \ t>0.$

Substituting $t=m^{2}$ gives $\sqrt{{\hat{d}}(2t)}\leq\sqrt{3/2}\,e^{-2}, so $\tau_{l}\leq{\hat{\tau}}\leq m^{2}$.

xxx P.S. Persi (98/07/02) points out that H. T. Yau showed $\tau_{l}=\Theta(n\log n)$ for random transpositions by combining $\tau_{l}\geq\tau_{2}$ (Lemma 8.22) and $\tau_{l}\leq\mbox{{\cal L}}(g_{0})/\mbox{{\cal E}}(g_{0},g_{0})$ with $g_{0}=\mbox{delta function}$. I have written notes generalizing and discussing this and will incorporate them into a later version.

## 8.4.4 $\tau_{l}$ and product chains

xxx Remind reader of definition of product chain in continuous time given in Chapter 4 Section yyy:6.2.

xxx Motivate study as providing benchmark chains for comparison method.

xxx Recall from Chapter 4, yyy:(42):

 $\tau_{2}=\max(\tau^{(1)}_{2},\tau^{(2)}_{2}).$ (8.68)

xxx Product chain has transition rates equal (off diagonal) to

 $i_{1}\neq j_{1}$ (8.69)

xxx Dirichlet form works out very nicely for products:

###### Lemma 8.35
 $\mbox{{\cal E}}(g,g)=\sum_{i_{2}}\pi^{(2)}_{i_{2}}\mbox{{\cal E}}^{(1)}(g(% \cdot,i_{2}),g(\cdot,i_{2}))+\sum_{i_{1}}\pi^{(1)}_{i_{1}}\mbox{{\cal E}}^{(% 2)}(g(i_{1},\cdot),g(i_{1},\cdot)).$

Proof. This follows easily from (8.69) and the definition of ${\cal E}$ in Chapter 3 Section yyy:6.1 (cf. (68)).

The analogue of (8.68) for the log-Sobolev time is also true:

xxx For NOTES?: Can give analagous proof of (8.68): see my notes, page 8.4.24A.

###### Theorem 8.36

For a continuous-time product chain,

 $\tau_{l}=\max(\tau^{(1)}_{l},\tau^{(2)}_{l}).$

Proof. The keys to the proof are Lemma 8.35 and the following “law of total ${\cal L}$-functional.” Given a function $g\not\equiv 0$ on the product state space $I=I_{1}\times I_{2}$, define a function $G_{2}\not\equiv 0$ on $I_{2}$ by

 $G_{2}(i_{2}):=\|g(\cdot,i_{2})\|_{2}=\left(\sum_{i_{1}}\pi_{i_{1}}g^{2}(i_{1},% i_{2})\right)^{1/2}.$

Then

 $\displaystyle\mbox{{\cal L}}(g)$ $\displaystyle=$ $\displaystyle\sum_{i_{1},i_{2}}\pi_{i_{1},i_{2}}\,g^{2}(i_{1},i_{2})\left[\log% (|g(i_{1},i_{2})|/G_{2}(i_{2}))+\log(G_{2}(i_{2})/\|g\|_{2})\right]$ $\displaystyle=$ $\displaystyle\sum_{i_{2}}\pi^{(2)}_{i_{2}}\mbox{{\cal L}}^{(1)}(g(\cdot,i_{2% }))+\mbox{{\cal L}}^{(2)}(G_{2}),$

where we have used

 $\|G_{2}\|^{2}_{2}=\|g\|^{2}_{2}.$

Thus, using the extremal characterization (definition) (8.53) of $\tau^{(1)}_{l}$ and $\tau^{(2)}_{l}$,

 $\mbox{{\cal L}}(g)\leq\tau^{(1)}_{l}\sum_{i_{2}}\pi^{(2)}_{i_{2}}\mbox{{% \cal E}}^{(1)}(g(\cdot,i_{2}),g(\cdot,i_{2}))+\tau^{(2)}_{l}\mbox{{\cal E}}% ^{(2)}(G_{2},G_{2}).$ (8.70)

But from

 $|G_{2}(j_{2})-G_{2}(i_{2})|=\left|\|g(\cdot,j_{2})\|_{2}-\|g(\cdot,i_{2})\|_{2% }\right|\leq\|g(\cdot,j_{2})-g(\cdot,i_{2})\|_{2}$

follows

 $\mbox{{\cal E}}^{(2)}(G_{2},G_{2})\leq\sum\pi^{(1)}_{i_{1}}\mbox{{\cal E}}% ^{(2)}(g(i_{1},\cdot),g(i_{1},\cdot)).$ (8.71)

From (8.70), (8.71), Lemma 8.35, and the extremal characterization of $\tau_{l}$ we conclude $\tau_{l}\leq\max(\tau^{(1)}_{l},\tau^{(2)}_{l})$. Testing on functions that depend only on one of the two variables shows that $\tau_{l}=\max(\tau^{(1)}_{l},\tau^{(2)}_{l})$.

Theorem 8.36 extends in the obvious fashion to higher-dimensional products.

###### Example 8.37

The $d$-cube.

The continuized walk on the $d$-cube (Chapter 5, Example yyy:15) is simply the product of $d$ copies of the continuized walk on the $2$-path, each run at rate $1/d$. Therefore, since the log-Sobolev time for the $2$-path equals $1/2$ by Example 8.29, the corresponding time for the $d$-cube is

 $\tau_{l}=d/2=\tau_{2}.$

¿From this and the upper bound in Corollary 8.27 we can deduce

 ${\hat{\tau}}\leq{\textstyle\frac{1}{4}}d\log d+(1-{\textstyle\frac{1}{4}}\log{% \textstyle\frac{1}{\log 2}})d.$

As discussed in this chapter’s introduction, this bound is remarkably sharp and improves significantly upon the analogous bound that uses only knowledge of $\tau_{2}$.  xxx Recall corrections marked on pages 8.2.11–12 of my notes.

## 8.4.5 The comparison method for bounding $\tau_{l}$

In Section 8.1 we compared relaxation times for two chains by using the extremal characterization and comparing Dirichlet forms and variances. For comparing variances, we used the characterization

 ${{\rm var}}_{\pi}\,g=\min_{c\in{\bf R}}\|g-c\|_{2}.$

To extend the comparison method to log-Sobolev times, we need the following similar characterization of ${\cal L}$.

xxx For NOTES: Cite [181].

###### Lemma 8.38

The functional ${\cal L}$ in (8.52) satisfies

 $\mbox{{\cal L}}(g)=\min_{c>0}\sum_{i}\pi_{i}L(g(i),c),\ \ \ g\not\equiv 0,$ (8.72)

with

 $L(g(i),c):=g^{2}(i)\log(|g(i)|/c)-{\textstyle\frac{1}{2}}(g^{2}(i)-c^{2})\geq 0.$ (8.73)

Proof. We compute

 $\displaystyle f(c)$ $\displaystyle:=$ $\displaystyle 2\sum_{i}\pi_{i}L(g(i),c^{1/2})=E_{\pi}(g^{2}\log|g|^{2})-\|g\|^% {2}_{2}\log c-\|g\|^{2}_{2}+c,$ $\displaystyle f^{\prime}(c)$ $\displaystyle=$ $\displaystyle 1-c^{-1}\|g\|^{2}_{2},\ \ \ f^{\prime\prime}(c)=c^{-2}\|g\|^{2}_% {2}>0.$

Thus $f$ is strictly convex and minimized by the choice $c=\|g\|^{2}_{2}$, and so

 $\min_{c>0}\sum_{i}\pi_{i}L(g(i),c)={\textstyle\frac{1}{2}}\min_{c>0}f(c)={% \textstyle\frac{1}{2}}f(\|g\|^{2}_{2})=\mbox{{\cal L}}(g).$

This proves (8.72). Finally, applying the inequality

 $x\geq 0$

to $x=g^{2}(i)$ and $y=c^{2}$ gives the inequality in (8.73).

Now it’s easy to see how to compare log-Sobolev times, since, adopting the notation of Section 8.1, Lemma 8.38 immediately yields the analogue

 $\mbox{{\cal L}}(g)\leq{\tilde{\cal L}}(g)\max_{i}(\pi_{i}/{\tilde{\pi}}_{i})$

of (8.18). In the notation of Corollary 8.2, we therefore have

###### Corollary 8.39 (comparison of log-Sobolev times)
 $\tau_{l}\leq\frac{A}{a}{\tilde{\tau}}_{l}.$
###### Example 8.40

Random walk on a $d$-dimensional grid.

xxx Remarked in Example 8.34 that $\tau_{l}\leq m^{2}$ for $m$-path with end self-loops.

xxx So by Theorem 8.36, benchmark product chain has ${\tilde{\tau}}_{l}\leq dm^{2}$.

Recalling $A\leq 1$ and $a\geq 1/2$ from Example 8.5, we therefore find

 $\tau_{l}\leq 2m^{2}d$ (8.74)

for random walk on the grid. Then Theorem 8.26(b) gives

 ${\hat{\tau}}\leq m^{2}d(\log\log(2n)+4),$

which is of order $m^{2}d(\log d+\log\log m)$. This is an improvement on the $\tau_{2}$-only bound $O(m^{2}d^{2}\log m)$ of (8.50) and may be compared with the Nash-based bound $O(m^{2}d^{2}\log d)$ of (8.51). In Example 8.43 we will combine Nash-inequality and log-Sobolev techniques to get a bound of order $m^{2}d\log d$

xxx right for TV.