Considering sorting algorithms based solely on binary comparisons of the elements to be sorted(algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when those comparisons are unreliable?
We assume the elements of the sequence $x = (x_1,x_2,...,x_n)$ to be sorted are distinct. We assume further that the only comparisons subject to error are those made between elements being sorted; comparisons among indices and so on are always correct. Errors in element comparisons are random events, spontaneous and independent of each other, of position and of value, with a common probability of $p$. We assume that the input list is presented in random order, each of the $n!$ random orders being equiprobable.
What is the expectation of the number of elements in the previous $m$ elements that should be placed at the previous $m$ positions after being sorted? That is, the sorted output with unreliable comparisons is $(y_1,y_2,...,y_m,...,y_n)$. The correct sorted output is $(z_1,z_2,...,z_m,...,z_n)$. What is the expectation of the number of elements in $(y_1,y_2,...,y_m)$ which are less than $z_{m+1}$? Suppose we want an ascending order.
The settings are the same with the settings in the below paper. http://www2.math.uu.se/~svante/papers/sj153_QSerror.pdf