# 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
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