6
$\begingroup$

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.

  • 0
    "permutation identity" is a term o$f$ art which does *not* mean what you are using the term for; edited title.2012-02-27

1 Answers 1

13

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.

  • 0
    Thank you very much. I will read the book carefully.2012-02-28