# Expected number of steps to transform a permutation to the identity

Start from an identity permutation P=[1,2,3,4,5], each step choose two random integers k and l in [1,5]. Then swap P[k] and P[l]. Stop the process until P again becomes identity. Observe that the expected number of steps is 120. I can not prove it theoretically. Please guide me.

-
"permutation identity" is a term of art which does not mean what you are using the term for; edited title. –  Arturo Magidin Feb 27 '12 at 19:07

Choosing two values randomly and swapping them creates a doubly stochastic Markov chain on the space $\cal S$ of all permutations. The unique invariant probability distribution is uniform on this space, and (by Markov chain theory) the expected number of steps to return to the original position is the reciprocal of the mass at that state: i.e., $\mathbb{E}_e(T_e)=1/\pi(e)=|{\cal S}|=120$.

In my answer to this question, I solve another problem with the same method and try to explain the result intuitively.

-
I've always wanted to learn more about Markov chains, but I have no idea where to start - what branch of mathematics is this considered (that is, what should I be searching Amazon for :P)? –  BlueRaja - Danny Pflughoeft Feb 27 '12 at 21:23
@BlueRaja-DannyPflughoeft Start with this free book! pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf –  Byron Schmuland Feb 27 '12 at 21:26
Also, see here: statslab.cam.ac.uk/~james/Markov –  Byron Schmuland Feb 27 '12 at 21:27
Thank you very much. I will read the book carefully. –  user12290 Feb 28 '12 at 12:24