8 Advanced L2L^{2} Techniques for Bounding Mixing Times (May 19 1999)

8.5 Combining the techniques

To get the maximum power out of the techniques of this chapter, it is sometimes necessary to combine the various techniques. Before proceeding to a general result in this direction, we record a simple fact. Recall (8.36).

Lemma 8.41

If qq and q*q^{*} are conjugate exponents with 2q2\leq q\leq\infty, then

fq*f11-2qf22q   for all ff.\|f\|_{q^{*}}\leq\|f\|^{1-\frac{2}{q}}_{1}\|f\|^{\frac{2}{q}}_{2}\mbox{\ \ \ % for all\/~{}$f$.}

Proof. Apply Hölder’s inequality

gh1gphp*\|gh\|_{1}\leq\|g\|_{p}\,\|h\|_{p^{*}}

with

g=|f|(q-2)/(q-1),   h=|f|2/(q-1),   p=q-1q-2.   g=|f|^{(q-2)/(q-1)},\ \ \ h=|f|^{2/(q-1)},\ \ \ p=\frac{q-1}{q-2}.~{}\ \ \rule% {4.3pt}{4.3pt}
Theorem 8.42

Suppose that a continuous-time reversible chain satisfies

N(t)Ct-D  for 0<tT0<t\leq TN(t)\leq Ct^{-D}\mbox{\ \ for\/ $0<t\leq T$} (8.75)

for some constants C,T,DC,T,D satisfying CT-DeCT^{-D}\geq e. If c0c\geq 0, then

d^(2t)=maxiPi(Xt)-π()2e2-c\sqrt{{\hat{d}}(2t)}=\max_{i}\|P_{i}(X_{t}\in\cdot)-\pi(\cdot)\|_{2}\leq e^{2-c}

for

tT+12τllog[log(CT-D)-1]+cτ2,t\geq T+{\textstyle\frac{1}{2}}\tau_{l}\log\left[\log(CT^{-D})-1\right]+c\tau_% {2},

where τ2\tau_{2} is the relaxation time and τl\tau_{l} is the log-Sobolev time.

Proof. ¿From Lemma 8.11 and a slight extension of (8.34), for any s,t,u0s,t,u\geq 0 and any initial distribution we have

P(Xs+t+u)-π()2P(Xs)q*𝐏tq*2e-u/τ2\|P(X_{s+t+u}\in\cdot)-\pi(\cdot)\|_{2}\leq\|P(X_{s}\in\cdot)\|_{q^{*}}\,\|{% \bf P}_{t}\|_{q^{*}\to 2}\,e^{-u/\tau_{2}}

for any 1q*1\leq q^{*}\leq\infty. Choose q=q(t)=1+e2t/τlq=q(t)=1+e^{2t/\tau_{l}} and q*q^{*} to be its conjugate. Then, as in the proof of Theorem 8.26(a),

𝐏tq*2=𝐏t2q1.\|{\bf P}_{t}\|_{q^{*}\to 2}=\|{\bf P}_{t}\|_{2\to q}\leq 1.

According to Lemma 8.41, (8.39), and (8.75), if 0<sT0<s\leq T then

P(Xs)q*P(Xs)22/qN(s)2/q(Cs-D)2/q.\|P(X_{s}\in\cdot)\|_{q^{*}}\leq\|P(X_{s}\in\cdot)\|^{2/q}_{2}\leq N(s)^{2/q}% \leq(Cs^{-D})^{2/q}.

Now choose s=Ts=T. Combining everything so far,

d^(2(T+t+u))(CT-D)2/q(t)e-u/τ2  for t,u0t,u\geq 0.\sqrt{{\hat{d}}(2(T+t+u))}\leq(CT^{-D})^{2/q(t)}\,e^{-u/\tau_{2}}\mbox{\ \ for% $t,u\geq 0$.}

The final idea is to choose tt so that the first factor is bounded by e2e^{2}. ¿From the formula for q(t)q(t), the smallest such tt is

12τllog[log(CT-D)-1].{\textstyle\frac{1}{2}}\tau_{l}\log\left[\log(CT^{-D})-1\right].

With this choice, the theorem follows readily.    

Example 8.43

Random walk on a dd-dimensional grid.

Return one last time to the walk of interest in Example 8.5. Example 8.21 showed that (8.75) holds with

D=d/4,   C=e(214d2m2)d/4=e(27dm)d/2,   T=dm2/32.D=d/4,\ \ \ C=e(2^{14}d^{2}m^{2})^{d/4}=e(2^{7}dm)^{d/2},\ \ \ T=dm^{2}/32.

Also recall τ212dm2\tau_{2}\leq\frac{1}{2}dm^{2} from (8.49) and τl2dm2\tau_{l}\leq 2dm^{2} from Example 8.40. Plugging these into Theorem 8.42 with c=2c=2 yields

τ^4932m2dlog[14dlogd+194dlog2], which is 5m2dlogd\leq 5m^{2}d\log d for d2d\geq 2.{\hat{\tau}}\leq{\textstyle\frac{49}{32}}m^{2}d\log[{\textstyle\frac{1}{4}}d% \log d+{\textstyle\frac{19}{4}}d\log 2],\mbox{\ which is $\leq 5m^{2}d\log d$ % for $d\geq 2$.}

xxx Finally of right order of magnitude.