CSE 525 (Spring 2019): HW #6

Due: Thurs, May 30th, 11:59pm

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 is a projection, i.e., whenever , in which case the statement is

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 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).

3. The coupling method

(a) Total variation and couplings

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

(b) Forgetting implies mixing

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 .

(c) Coupling means forgetting

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

(d) Coupling on the hypercube

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 .

(e) Coupling on the slice

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 .