sorting with noisy but persistent answers

Question

Given a set of elements $A$ and a probability of noise $p<0.5$. For any two elements $x,y\in A$ we can ask the oracle $O$ to know where $x$ stands w.r.t $y$ (0 means $x$ is smaller than $y$ and 1 means the other way).

The oracle answers correctly with probability $1-p$. The noise is random and independent but persistent in a sense that if the oracle answers incorrectly for one pair $(x,y)$ it will give the same answer if questioned on the same pair again.

Is there any known strategy to sort $A$ with high probability?

Answer 1

For constant $p>0$ there is no way to exactly sort $A$ with high probability. Think, e.g., of the first two elements: they will seem to be in the wrong order with probability $p$ and no other comparison provides any information on their order.

In fact, if an algorithm returns a permutation of $A$ that has maximum dislocation¹ $D$ with high probability, then $D = \Omega(\log |A|)$.

The algorithm in the paper by Braverman and Mossel suggested by Yuval returns a permutation with maximum dislocation $O(\log |A|)$ and, in particular, returns the maximum-likelihood permutation. However, its running time can be quite large.

The following papers have improved the time complexity (in chronological order) for the problem of sorting with (asymptotically) optimal $O(\log |A|)$ maximum dislocation. Here the returned permutation does not need to be the maximum-likelihood one and $p$ needs to be smaller than some constant ($1/32$, $1/20$, or $1/16$):

• Tolerant algorithms: Lowers the complexity to $O(|A|^2)$.

• Sorting with recurrent comparison errors Lowers the complexity to $O(|A|^2)$. The returned permutation also has $O(|A|)$ total dislocation in expectation. This is probably the easiest algorithm to implement.

• Optimal Dislocation with Persistent Errors in Subquadratic Time Same dislocation bounds as the above paper but in $\tilde{O}(|A|^{3/2})$ time.

• Optimal Sorting with Persistent Comparison Errors. Lowers the complexity to $O(|A| \log |A|)$. The returned permutation has $O(|A|)$ total dislocation, w.h.p.

---

¹ The dislocation of an element in a permutation is the absolute difference between its position and its rank (position in the sorted sequence).

Answer 2

Your problem has been considered by Braverman and Mossel in their paper Noisy sorting without resampling. The paper has generated quite a lot of follow-up work, some of which might be more practical than the original algorithm suggested by Braverman and Mossel.