1.* Let be simple random walk on the integers, with . Show that for all . Hint: Prove the inequality for all real , and use it to bound .
2.* Let be a b-ary tree of height , that has vertices. What are the best upper and lower bounds you can prove for the mixing time of lazy SRW on ?
3. Let be the set of invertible matrices mod 2. Find the cardinality of . Hint: consider choosing the rows of the matrix one by one.
4.* Let be a subset of the group of permutations . consider the Markov chain on obtained by picking a permutation in uniformly at random (independently of previous ), and defining .
(a) Write a lower bound for the mixing time of this chain in terms of and .
(b) Suppose that consists of transpositions. What is the smallest possible size of for which this chain is irreducible?
(c) If consists of transpositions, can this chain be aperiodic?
(d) Suppose that 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?