Note that you have two weeks to complete this homework.

Carefully prove Theorem 1.3 from Lecture 12. You may assume a strengthening of Theorem 1.2: That it holds whenever is a projection, i.e., whenever , in which case the statement is

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 be a regular graph on vertices (i.e., all the degrees are the same). Show that the cover time of is at most .

(a’) [extra credit]Show that actually the cover time of is .

(b)Now suppose that is such that every vertex has degree strictly larger than . Prove that the cover time is .

[Hint: Show that between every pair of vertices , you can find short, edge-disjoint paths.]

(c)Given an example of a regular graph with all vertex degrees at least whose cover time is (and prove it).

Let and be two probability measures on a finite set .
The *total variation distance between and * is given by

A *coupling* of and is a pair of random variables such that
has law and has law . Prove that for any coupling of and , we have

Then prove that there exists a coupling achieving this bound, i.e. such that

Suppose that we have a graph so that the corresponding Markov chain is aperiodic and irreducible (for undirected graphs, this is equivalent to being connected and non-bipartite). Let denote the stationary measure.

Let be the distribution of the random walk started at after steps, and define

Also set

Show that for every , we have .

Now consider a pair of random processes that are coupled random walks on in the following sense: and both evolve marginally according to the distribution of the random walk. And if then . Define the random variable

Use parts (a) and (b) to show that

Recall that the mixing time of the random walk is .

Consider the random walk on the hypercube where every vertex has a self loop of weight . (So with probability , the walk stays in place, and with probability , it goes to a random neighbor.) This random walk is equivalent to the following: Suppose we are at a vertex . At every step, choose a coordinate uniformly at random and an independent uniform value and set .

We can define a coupling as in part (c) by having and make the same choice of and at every step. Use part (c) to show that .

Let and be positive integers with , and let denote the collection of all subsets of of cardinality so that . Consider the following random walk on : If we are at a subset , then with probability we stay at , and with probability , we choose uniformly random elements and independently and then move to the set .

Use a coupling argument to show that the mixing time is .