Week 5 - lecture 2

TOP TOPIC

Date: 01/09/22

5.4. Varopolous-Carne long range inequality

5.5. A stronger diameter lower bound for mixing time

LECTURE presentation

Video lecture

Homework

1.* Let P be the transition matrix corresponding to simple random walk on a finite connected graph G=(V,E). Show that for each t \ge 1, we have \sum_{x \in V} P^{2t}(x,x) \ge 1. Moreover, if the graph is bipartite, then \sum_{x \in V} P^{2t}(x,x) \ge 2.

2.* Let \alpha \in (0,1]. Consider a graph G which consists of a complete graph on n nodes, and a path of length \ell=\lfloor n^{\alpha}\rfloor that emanates from one of them (call it v) and ends in a node w. Give the best upper and lower bounds you can for

(a) The maximal hitting time for SRW in G.

(b) The maximal hitting time for SRW started from w.

(c) The cover time for SRW in G.

(d) The mixing time for SRW in G.

You can safely ignore constant factors, but pay attention to the dependence on n and \alpha.

3. Read and understand the computation of the eigenvalues and eigenvectors for simple random walk on the n-cycle.

Reference

[1] Glasner, Shmuel.
Almost periodic sets and measures on the torus.
Israel J. Math. 32 (1979), no. 2-3, 161–-172.

[2] Berend, Daniel and Peres, Yuval.
Asymptotically dense dilations of sets on the circle.
J. London Math. Soc. (2) 47 (1993), no. 1, 1–-17.

[3] N. Alon and Y. Peres, "Uniform dilations'', Geometric and Functional Analysis, vol. 2, No. 1 (1992), 1–28.

[4] Nair, R. and Velani, S. L.
Glasner sets and polynomials in primes.
Proc. Amer. Math. Soc. 126 (1998), no. 10, 2835–-2840.