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.


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$ Nov 12 '10 at 3:01
  • $\begingroup$ Thanks very much Warren. I think that is the perfect paper for me to be getting on with. $\endgroup$
    – graffe
    Nov 12 '10 at 8:30
  • $\begingroup$ A longer term link: arxiv.org/abs/0910.1191 $\endgroup$ Nov 12 '10 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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