# Random walks on symmetric groups

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!$$.

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!$$.