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 2≤q≤∞2\leq q\leq\infty, then

∥f∥q*≤∥f∥11-2q⁢∥f∥22q⁢   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

∥g⁢h∥1≤∥g∥p⁢∥h∥p*\|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)≤C⁢t-D⁢  for 0<t≤T0<t\leq TN(t)\leq Ct^{-D}\mbox{\ \ for\/ $0<t\leq T$} (8.75)

for some constants C,T,DC,T,D satisfying C⁢T-D≥eCT^{-D}\geq e. If c≥0c\geq 0, then

d^⁢(2⁢t)=maxi∥Pi(Xt∈⋅)-π(⋅)∥2≤e2-c\sqrt{{\hat{d}}(2t)}=\max_{i}\|P_{i}(X_{t}\in\cdot)-\pi(\cdot)\|_{2}\leq e^{2-c}

for

t≥T+12⁢τl⁢log⁡[log⁡(C⁢T-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,u≥0s,t,u\geq 0 and any initial distribution we have

∥P(Xs+t+u∈⋅)-π(⋅)∥2≤∥P(Xs∈⋅)∥q*∥𝐏t∥q*→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 1≤q*≤∞1\leq q^{*}\leq\infty. Choose q=q⁢(t)=1+e2⁢t/τ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),

∥𝐏t∥q*→2=∥𝐏t∥2→q≤1.\|{\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<s≤T0<s\leq T then

∥P(Xs∈⋅)∥q*≤∥P(Xs∈⋅)∥22/q≤N(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))≤(C⁢T-D)2/q⁢(t)⁢e-u/τ2⁢  for t,u≥0t,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⁢τl⁢log⁡[log⁡(C⁢T-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⁢(214⁢d2⁢m2)d/4=e⁢(27⁢d⁢m)d/2,   T=d⁢m2/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 τ2≤12⁢d⁢m2\tau_{2}\leq\frac{1}{2}dm^{2} from (8.49) and τl≤2⁢d⁢m2\tau_{l}\leq 2dm^{2} from Example 8.40. Plugging these into Theorem 8.42 with c=2c=2 yields

τ^≤4932⁢m2⁢d⁢log⁡[14⁢d⁢log⁡d+194⁢d⁢log⁡2], which is ≤5⁢m2⁢d⁢log⁡d\leq 5m^{2}d\log d for d≥2d\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.

Bibliography