# Monte Carlo algorithm that determines if a permutation of the integers 1 through $n$ has already been sorted.

This question is from "Discrete Mathematics and Its Applications", from Kenneth Rosen, 6th Edition.

Devise a Monte Carlo algorithm that determines whether a permutation of the integers 1 through $n$ has already been sorted (that is, it is in increasing order), or instead, is a random permutation. A step of the algorithm should answer “true” if it determines the list is not sorted and “unknown” otherwise. After $k$ steps, the algorithm decides that the integers are sorted if the answer is “unknown” in each step. Show that as the number of steps increases, the probability that the algorithm produces an incorrect answer is extremely small. [Hint: For each step, test whether certain elements are in the correct order. Make sure these tests are independent.]

Here is my attempt at a solution:

Algorithm (informal description): Given a permutation of the integers 1 through $n$, in each step of the algorithm, one element is randomly chosen from the permutation, with a total of $k$ steps. In each step, if the value of the chosen element is $i$, the algorithm checks if the element is in the correct position, that is, if it is in the $i^{th}$ position of the permutation (with $1\leq i\leq n$). If it is in the correct position, the result is "unknown"; otherwise, the result is "true". For example, in the permutation $162453$, the number $4$ is in the $4^{th}$ position, therefore it is in the correct position in the permutation. If all steps give the result "unknown" , the algorithm determines that the permutation is sorted; otherwise, it determines that the integers are not sorted.

I posted the details as an answer, but I'm not sure whether it is correct and completely consistent. Thank you in advance.

-

How about this: Select $i$ uniformly from $1\ldots n-1$, and then $j$ uniformly from $i+1\ldots n$, so we have $i<j$.

Now check if $a_i < a_j$. If not, we can be sure that the elements of the permutation are not sorted; halt. But if $a_i < a_j$, we are still unsure.

In a random permutation, we will have $a_i < a_j$ with probability $\frac12$. So if we run the algorithm for $k$ steps, and we are still unsure, then we have $2^{-k}$ confidence that the permutation is sorted and not random.

-
Having thought about it some more, I was not able to think of any advantage that my algorithm has over yours, whereas yours seems to me to increase the confidence much more rapidly on average and also to have worst-case behavior that is much less bad than mine. For example, for the permutation $\langle 2,1,3,4,5\ldots,n\rangle$ yours detects the unsortedness $\frac2n$ of the time, but mine only $\frac1{n^2-n}$ of the time. – MJD Jun 20 '12 at 15:31
Although the algorithm I described seems to increase the confidence more rapidly, the problem is that, since the probability that I found depends on $n$, the number of integers of the permutation, I think that deciding that a particular integer is in the correct order would change the probability of the next test, because the next test would be done in a list with one integer less (but I'm not very sure whether my reasoning is correct). In the case of the algorithm that you posted, it seems that the tests are independent, because the probability $1/2$ doesn't involve $n$. – anonymous Jun 22 '12 at 19:15

Here is my attempt at a solution:

Algorithm (informal description): Given a permutation of the integers 1 through $n$, in each step of the algorithm, one element is randomly chosen from the permutation, with a total of $k$ steps. In each step, if the value of the chosen element is $i$, the algorithm checks if the element is in the correct position, that is, if it is in the $i^{th}$ position of the permutation (with $1\leq i\leq n$). If it is in the correct position, the result is "unknown"; otherwise, the result is "true". For example, in the permutation $162453$, the number $4$ is in the $4^{th}$ position, therefore it is in the correct position in the permutation. If all steps give the result "unknown" , the algorithm determines that the permutation is sorted; otherwise, it determines that the integers are not sorted.

The probability that this algorithm answers incorrectly is the probability that it decides the integers are sorted when they are not. That is, it is the probability that, in each one of the $k$ steps, the randomly chosen number is in the correct position, given that the permutation is not sorted. In any particular step, the number of permutations where the $k^{th}$ number is in the correct position is $(n-1)! - 1$ (that is, all the other $n-1$ numbers permutate while the $k^{th}$ number is fixed, the minus one is to exclude the permutation where all the integers are sorted). And there are $n!-1$ possible unsorted permutations for the $n$ numbers. So, the probability that the algorithm answers "unknown" in a particular step is $\dfrac{(n-1)! - 1}{n!-1}$. We can see that the tests are independent, because the probability that the algorithm answers "unknown" in each test is not dependent on the previous tests.

So, the probability that the algorithm answers "unknown" in $k$ steps is:

$\left[\dfrac{(n-1)! - 1}{n!-1}\right ]^k$

Since the numerator is smaller than the denominator, this number is very small if we make $k$ large.

-
The fact that the tests are not independent needs a proof. Especially, if you found one error, then probability that you have two errors increases (you can't have only one misplaced number in a permutation). I guess the analysis might be done in a way that it does not matter (because you stop after first error), however, I think that the current proof is not sound. – dtldarek Jun 21 '12 at 7:32
@dtldarek: I think that the tests are really not independent, because the probability that the answer is "unknown" in each step depends on the number of elements of the permutation. So, if, in one step, the algorithm determines that one element is in the correct position, the next step would be done in a list with one element less, and the probability would have a different value. Is this reasoning correct? – anonymous Jun 21 '12 at 12:07