Note that you have two weeks to complete this homework.

1. Verification of Theorem 1.3

Carefully prove Theorem 1.3 from Lecture 12. You may assume a strengthening of Theorem 1.2: That it holds whenever $\mathbb{E}[Y]=P$ is a projection, i.e., whenever $\lambda_1(P),\ldots,\lambda_n(P) \in \{0,1\}$, in which case the statement is $\newcommand{\e}{\varepsilon} \newcommand{\P}{\mathbb{P}} \newcommand{\R}{\mathbb{R}}$

$$\P\left[(1-\e) P \preceq \frac{1}{n} \sum_{i=1}^n Y_i \preceq (1+\e) P\right] \geq 1 - 2 d e^{-\e^2 n/4L}.$$

2. Cover times of regular graphs

For this problem, you should use the connection between random walks and electrical networks established in Lecture 14.

You may also need to employ the Rayleigh monotonicity principle we discussed in class: When the resistance of an edge in a network increases, no effective resistance can decrease.

(a) Let $G$ be a regular graph on $n$ vertices (i.e., all the degrees are the same). Show that the cover time of $G$ is at most $O(n^2 \log n)$.

(a’) [extra credit] Show that actually the cover time of $G$ is $O(n^2)$.

(b) Now suppose that $G$ is such that every vertex has degree strictly larger than $n/2$. Prove that the cover time is $O(n \log n)$.

[Hint: Show that between every pair of vertices $u, v$, you can find $\Omega(n)$ short, edge-disjoint paths.]

(c) Given an example of a regular graph with all vertex degrees at least $n/2 − O(1)$ whose cover time is $\Omega(n^2)$ (and prove it).

3. The coupling method

(a) Total variation and couplings

Let $\mu$ and $\nu$ be two probability measures on a finite set $\Omega$. The total variation distance between $\mu$ and $\nu$ is given by

$$d_{TV}(\mu,\nu) = \frac12 \sum_{\omega \in \Omega} |\mu(\omega)-\nu(\omega)|\,.$$

A coupling of $\mu$ and $\nu$ is a pair of random variables $(X,Y)$ such that $X$ has law $\mu$ and $Y$ has law $\nu$. Prove that for any coupling $(X,Y)$ of $\mu$ and $\nu$, we have

$$\Pr[X \neq Y] \geq d_{TV}(\mu,\nu)\,.$$

Then prove that there exists a coupling $(X,Y)$ achieving this bound, i.e. such that

$$\Pr[X \neq Y] = d_{TV}(\mu,\nu)\,.$$

(b) Forgetting implies mixing

Suppose that we have a graph $G=(V,E)$ so that the corresponding Markov chain is aperiodic and irreducible (for undirected graphs, this is equivalent to $G$ being connected and non-bipartite). Let $\pi(v)=\frac{\mathrm{deg}(v)}{2|E|}$ denote the stationary measure.

Let $p_t^{(x)}$ be the distribution of the random walk started at $x \in V$ after $t$ steps, and define

$$\Delta(t) = \max_{x \in V} d_{TV}\left(p_t^{(x)}, \pi\right)$$

Also set

$$D(t) = \max_{x,y \in V} d_{TV}\left(p_t^{(x)},p_t^{(y)}\right)$$

Show that for every $t$, we have $\Delta(t) \leq D(t) \leq 2 \Delta(t)$.

(c) Coupling means forgetting

Now consider a pair of random processes $(\{X_t\}, \{Y_t\})$ that are coupled random walks on $G$ in the following sense: $\{X_t\}$ and $\{Y_t\}$ both evolve marginally according to the distribution of the random walk. And if $X_t=Y_t$ then $X_{t+1}=Y_{t+1}$. Define the random variable

$$T_{xy} = \min \{ t: X_t = Y_t \mid X_0=x,Y_0=y \}$$

Use parts (a) and (b) to show that $\Delta(t) \leq \max_{x,y \in V} \Pr[T_{xy} > t]\,.$

(d) Coupling on the hypercube

Recall that the mixing time of the random walk is $\tau_{\mathrm{mix}} = \min \{ t : \Delta(t) \leq 1/2e \}$.

Consider the random walk on the hypercube $\{0,1\}^n$ where every vertex has a self loop of weight $1/2$. (So with probability $1/2$, the walk stays in place, and with probability $1/2$, it goes to a random neighbor.) This random walk is equivalent to the following: Suppose we are at a vertex $x \in \{0,1\}^n$. At every step, choose a coordinate $i \in \{1,\ldots,n\}$ uniformly at random and an independent uniform value $b \in \{0,1\}$ and set $x_i=b$.

We can define a coupling $(\{X_t\},\{Y_t\})$ as in part (c) by having $X_t$ and $Y_t$ make the same choice of $i$ and $b$ at every step. Use part (c) to show that $\tau_{\mathrm{mix}} = O(n \log n)$.

(e) Coupling on the slice

Let $n$ and $k$ be positive integers with $k \leq n/2$, and let $\Omega$ denote the collection of all subsets of $\{1,2,\ldots,n\}$ of cardinality $k$ so that $|\Omega| = {n \choose k}$. Consider the following random walk on $\Omega$: If we are at a subset $S$, then with probability $1/2$ we stay at $S$, and with probability $1/2$, we choose uniformly random elements $a \in S$ and $b \in \{1,\ldots,n\} \setminus S$ independently and then move to the set $(S \cup \{b\}) \setminus \{a\}$.

Use a coupling argument to show that the mixing time is $O(n \log k)$.