Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
"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
add comment

1 Answer

up vote 12 down vote accepted

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.

share|improve this answer
    
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
2  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.