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.