Expectation over sequencial random shuffles

Question

I'm trying to understand this concept with this following problem:

Logan is cleaning his apartment. In particular, he must sort his old favorite sequence, , of positive integers in nondecreasing order. He's tired from a long day, so he invented an easy way (in his opinion) to do this job. His algorithm can be described by the following pseudocode:

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

Can you determine the expected number of minutes that Logan will spend waiting for to be sorted?

Let's say we need to evaluate this situation:

array with 2 items:

5,2

Solution:

There are two permutations possible after a random shuffle, and each of them has probability . The probability to get the sequence sorted after the first minute is . The probability that will be sorted after the second minute is , the probability will be sorted after the third minute is , and so on. So, the answer is equal to the following sum:

$\sum_{i=1}^\infty i*2^{-i} = 2.000000$

I understand that this is an expectation problem.

But I can't get the correct situation for a list different of 2 as size. As explained above

Can some one explain me what happens with 3 as size of the list?

Answer 1

Suppose he must sort the numbers $\{1,2,\dots,n\}$

If $\mu$ denotes the expected number of minutes then: $$\mu=\frac1{n!}1+(1-\frac1{n!})(1+\mu)$$

Here $\frac1{n!}$ is the probability that he is ready after one minute.

If he is not then he must start over again and has lost one minute.

This equality tells us that : $$\mu=n!$$

More formally:

If $E$ denotes the event that he succeeds in one minute then:

$$\mathbb EX=\mathbb E(X\mid E)P(E)+\mathbb E(X\mid E^c)P(E^c)$$ and this with $$\mathbb E(X\mid E^c)=1+\mathbb EX$$

Answer 2

Assuming they're all distinct, the process succeeds with probability $1$ divided by the number of possible permutations, which is $n!$ for a sequence of $n$ positive integers. So it takes $n!$ steps on average.

Answer 3

The probability that $n$ distinct items are ordered in the favorite order after one minute is

$\frac1{n!}$

The probability that $n$ distinct items are ordered in the favorite order after k minutes is

$P(X=k)=\frac1{n!}\cdot \left(1-\frac1{n!} \right)^{k-1}$

The expected value is related to the geometric distribution.

$$E(X)=\sum_{k=1}^{\infty} k\cdot P(X=k)=\sum_{k=1}^{\infty} k\cdot \frac1{n!}\cdot \left(1-\frac1{n!} \right)^{k-1}=n!$$