I am looking for references for the following problem, which I feel must have been studied before. I have n items and I want to rank them. I randomise once at the beginning of the process and then for each pair of items I have an x% chance of getting the right ordering, let us say independently. I then use these comparison results to rank the items. I would like to know how good/bad the ranking can be given unbounded computation and also any methods for finding a good ranking in reasonable time. Let us also say that there is a true total ordering under the hood.

I am aware of some of the literature on binary sorting with errors but the papers I found, at least, seem to answer a different set of questions.


1 Answer 1


If I understand your question correctly it is answered in Braverman and Mossel's "Sorting with Noisy Information" http://arxiv.org/PS_cache/arxiv/pdf/0910/0910.1191v1.pdf (see also conference version titled "Noisy Sorting without Resampling" IIRC.)

  • $\begingroup$ This is an excellent reference, which answers the question as I interpreted it. It also mentions the query complexity, which requires $O(n\log(n))$ (possibly erroneous) comparison queries. $\endgroup$ Commented Nov 12, 2010 at 3:01
  • $\begingroup$ Thanks very much Warren. I think that is the perfect paper for me to be getting on with. $\endgroup$
    – Simd
    Commented Nov 12, 2010 at 8:30
  • $\begingroup$ A longer term link: arxiv.org/abs/0910.1191 $\endgroup$ Commented Nov 12, 2010 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.