# Ranking with errors

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.

-
For adversarial errors see cstheory.stackexchange.com/questions/423/… . –  Warren Schudy Nov 11 '10 at 22:13
add comment

## 1 Answer

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.)

-
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. –  Derrick Stolee Nov 12 '10 at 3:01
Thanks very much Warren. I think that is the perfect paper for me to be getting on with. –  Raphael Nov 12 '10 at 8:30
A longer term link: arxiv.org/abs/0910.1191 –  András Salamon Nov 12 '10 at 10:07
add comment