Expected number of steps - shuffling a sequence

Question

I've been struggling with a problem a CS student friend of mine gave me a few hours ago.

Given that $P$ is an array of integers and $N$ is its size, how many minutes is the following algorithm expected to take?

---

    while isNotSorted(P) do
    { 
        WaitOneMinute();
        RandomShuffle(P)
    }

---

Obviously, this problem involves some probabilities/statistic knowledge and I have no training in those, but it doesn't feel that hard, even if I don't know how to approach it yet.

Can you suggest a solution?

Answer 1

Suppose the integers in the array are distinct. Therefore, only one permutation of the integers corresponds to a sorted array.

Moreover, suppose you use the Fisher-Yates shuffle (or anything where each permutation is equally likely). Since there are $N!$ permutations, each permutation has probability $1/N!$ of appearing.

Now, the expected number of trials until first success is $1/(1/N!)=N!$.

Addendum: without loss of generality, suppose the integers are $1,\ldots,M$ (otherwise you can relabel them; all that matters is their order) and let $n_i$ be the number of times integer $i$ is repeated. Therefore, $\sum_{i=1}^M n_i=N$ is the total number of integers. In this case, the correct permutation occurs with probability $\prod_{i=1}^M n_i!/N!$ so that the expected number of trials until first success is $N!/\prod_{i=1}^M n_i!$.