Question

Question: 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.]

Short answer

Answer

The Monte Carlo algorithm is:

Procedure MonteCarloNotIncreasing

$a_1{a}_2...a_n:$(permutation of the integers through $n$and $n⩾1$,

$k$: positive integer with $k⩽n$)

for$i:=1$to.

If $a_i\ne i$then return true

return unknown

Step-by-step solution

Given information  

A permutation of the integers$1$through $n$has already been sorted (that is, it is in increasing order),or instead it is a random permutation

Definition and formulas

We call the algorithm “MonteCarloNotIncreasing” and the input is a permutationof the integersthrough and a positive integer$\mathit{k}\mathbf{}\mathbf{(}\mathit{k}\mathbf{⩽}\mathit{n}\mathbf{)}$.

Designing the Algorithm

The Monte Carlo algorithm is:

($a_1{a}_2...a_n:$permutation of the integers through$n$and $n⩾1$,$k$: positive integer with$k⩽n$)

In each step of the algorithm, we will check whether the consecutive elements of the permutations are in the correct increasing order (with $a_1=1$, $a_2=2,...a_n=n$).

If we get any element that is not in the correct position, then we return the value “true”

And the algorithm always stops after $k$steps.

for$i:=1$to$n$.

If$a_i\ne i$then return true

If we don’t get any element in the incorrect position, then we return “unknown”.

return unknown

Combining all these steps, we obtain the algorithm:

Procedure MonteCarloNotIncreasing

($a_1{a}_2...a_n:$permutation of the integers through and $n⩾1$,

: positive integer with$k⩽n$)

for$i:=1$to.

If $a_i\ne i$then return true

return unknown