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.
 A: 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.
A: 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.
