Week 5 - lecture 2

Home » Week 5 - lecture 2

LECTURE presentation

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

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

Week 5 - lecture 2

TOP TOPIC

LECTURE presentation

Video lecture

Homework

Reference

Contact Me