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?