Random walks on symmetric groups

Question

Let $S_n$ be the symmetric group on $n$ elements. Now, we pick a random transpositions to generate random walks on $S_n$ (also assume the probability of picking each transposition is equal of course). There are $n(n-1)/2$ transpositions. How many does is need on average (expectation) to get back to the identity $(1)$? Namely, what is the expectation step of a random walk on $S_n$ first hit the identity?

I could compute the case for 2,3, and 4. The expectations are simply 2, 6, 24. So I guess it is $n!$.

Answer 1

In general, for an irreducible, aperiodic Markov process on a finite state space, the expected return time to a state $x$ is always the reciprocal of the unique steady state probability for $x$. To see this, let $T_0,T_1,T_2,\dots$ be the return times to $x$ when the Markov process starts at $x$, where we define $T_0=0$. Note that $${T_n\over n}=\frac1n\left[(T_1-T_0)+(T_2-T_1)+\dots+(T_n-T_{n-1})\right]$$ By the strong law of large numbers, $T_n/n\to E[T_1]$, the expected return time to $x$. On the other hand, $n/T_n$ is the proportion of visits to $x$ among the first $T_n$ steps of the process, since there were exactly $n$ visits. Since we assumed the process converges to a unique steady state vector, we must also have $n/T_n\to p_{\infty}(x)$.

Your random walk on $S_n$ is irreducible and aperiodic. Since symmetry implies the steady state probability for all group elements is equal, it must be $1/n!$ for each, so the expected return time for all elements is $n!$.