Consider the following Markov chain for shuffling n cards. In each step, we pick two cards independently and uniformly at random and exchange their positions.

(a) Prove that this Markov chain will converge to the uniform distribution, for all card permutations, starting from any initial permutation.

(b) Prove that ? (?) ? O(n 2 log(1/?)).