Week 3 - lecture 2


Date: 01/09/22

3.4. Birth and death chains
3.5. A markov chain from linear algebra
3.6. Counting and diameter lower bounds
3.7. Bottleneck Ratio 

LECTURE presentation

Video lecture


1.* Let \{S_n\} be simple random walk on the integers, with S_0=0. Show that P(S_n \ge \ell) \le e^{-\ell^2/(2n)} for all n,\ell \ge 1. Hint: Prove the inequality \cosh(x) \le e^{x^2/2} for all real x, and use it to bound E(e^{\lambda S_n}).

2.*  Let  T be a b-ary tree of height k, that has 1+b+\dots+b^k vertices.  What are the best upper and lower bounds you can prove for the mixing time of lazy SRW on T?

3. Let GL_n(2) be the set of invertible n \times n matrices mod 2. Find the cardinality of GL_n(2). Hint: consider choosing the rows of the matrix one by one.

4.* Let M be a subset of the group of permutations \bf S_n. consider the Markov chain on \bf S_n obtained by picking a permutation g_n in M uniformly at random (independently of previous g_j), and defining X_{n}=X_{n-1}g_n.

(a)  Write a lower bound for the mixing time of this chain in terms of n and |M|.

(b) Suppose that M consists of transpositions. What is the  smallest possible size of M for which this chain is irreducible?

(c) If M consists of transpositions, can this chain be aperiodic?

(d) Suppose that M consists of all transpositions, and we consider the lazy version of the chain above. Can you improve the lower bound from part (a) in this case?


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