# Remarks on Lecture 3

Today we saw the connection between mixing times of random walks and the second eigenvalue of the normalized Laplacian. Recall that ${G=(V,E,w)}$ is an ${n}$-vertex, weighted graph.

First, we introduced the lazy walk matrix,

$\displaystyle W_G = \frac{1}{2} (I + A_G D_G^{-1})\,,$

which is related to the normalized Laplacian via,

$\displaystyle W_G = I - \frac{1}{2} D_G^{1/2} \mathcal{L}_G D_G^{-1/2}\,.$

In particular, if we arrange the eigenvalues of ${W_G}$ as ${1=\beta_1 \geq \beta_2 \geq \cdots \geq \beta_n}$, then

$\displaystyle \beta_i = 1 - \frac{\lambda_i}{2}\,,$

where ${\lambda_i}$ is the ${i}$th smallest eigenvalue of ${\mathcal{L}_G}$. Furthermore, the eigenfunctions of ${W_G}$ are given by ${g = D_G^{1/2} f}$, where ${f}$ is an eigenfunction of ${\mathcal L_G}$.

The eigenfunctions of ${W_G}$ are orthogonal with respect to the inner product

$\displaystyle (f,g) = \sum_{u \in V} \frac{1}{w(u)} f(u) g(u)\,.$

We will refer to this Hilbert space as ${\ell^2(1/w)}$. Recall that ${\|f\|_{\ell^2(1/w)} = \sqrt{(f,f)} = \sqrt{\sum_{v \in V} \frac{1}{w(v)} f(v)^2}}$.

If we define the stationary distribution ${\pi : V \rightarrow [0,1]}$ by

$\displaystyle \pi(u) = \frac{w(u)}{w(V)} = \frac{w(u)}{2 w(E)},$

then ${W_G \pi = \pi}$.

Let ${f_1, f_2, \ldots, f_n}$ be an ${\ell^2(1/w)}$-orthornormal system of eigenvectors for ${W_G}$. Now fix an initial distribution ${p_0 : V \rightarrow [0,1]}$ and write,

$\displaystyle p_0 = \sum_{i=1}^n \alpha_i f_i\,.$

Then we have,

$\displaystyle p_t = W^t p_0 = \pi + \sum_{i > 1} \alpha_i \left(1-\frac{\lambda_i}{2}\right)^t f_i\,.$

In particular,

$\displaystyle \|p_t - \pi\|_{\ell^2(1/w)}^2 = \sum_{i > 1} \alpha_i^2 \left(1-\frac{\lambda_i}{2}\right)^{2t} \leq \left(1-\frac{\lambda_2}{2}\right)^{2t} \sum_{i > 1} \alpha_i^2 \leq \left(1-\frac{\lambda_2}{2}\right)^{2t} \|p_0\|_{\ell^2(1/w)}^2\,.$

Let ${\pi_* = \min_{u \in V} \pi(u)}$ be the minimum stationary measure. A particularly strongly notion of mixing time is given by the following definition.

$\displaystyle \tau_{\infty} = \sup_{p_0} \min \left\{ t : \|p_t - \pi\|_{\infty} < \frac{\pi_*}{4} \right\}\,$

where the supremum is taken over all initial distributions ${p_0}$. By time ${\tau_{\infty}}$, the distribution ${p_t}$ is pointwise very close to the stationary distribution ${\pi}$.

Let ${w^* = \max_{u \in V} w(u)}$ and ${w_* = \min_{u \in V} w(u)}$. Using our preceding calculation, we have

$\displaystyle \|p_t - \pi\|_{\infty} \leq \sqrt{w^*} \|p_t - \pi\|_{\ell^2(1/w)} \leq \sqrt{w^*} \left(1-\frac{\lambda_2}{2}\right)^{t} \|p_0\|_{\ell^2(V,w)} \leq \left(1-\frac{\lambda_2}{2}\right)^{t} \sqrt{\frac{w^*}{w_*}}\,.$

Observe that ${\frac{w^*}{w_*} \leq \frac{1}{\pi_*}}$, so if we now choose ${t \asymp \frac{1}{\lambda_2} \log \frac{1}{\pi_*}}$ appropriately, then

$\displaystyle \|p_t - \pi\|_{\infty} < \frac{\pi_*}{4},$

yielding our main result:

$\displaystyle \tau_{\infty} \lesssim \frac{1}{\lambda_2} \log \frac{1}{\pi_*}\,.$

One can also proof that ${\tau_{\infty} \gtrsim \frac{1}{\lambda_2}}$ (see the exercises). In general, we will be concerned with weaker notions of mixing. We’ll discuss those when they arise.

### Excersies

Prove that ${\tau_{\infty} \gtrsim \frac{1}{\lambda_2}}$ for any graph G.