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

CC BY-SA 2.5
2010-11-12T03:01:46.880Z
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
CC BY-SA 2.5
2010-11-12T08:30:46.207Z
Thanks very much Warren.  I think that is the perfect paper for me to be getting on with.
Simd
CC BY-SA 2.5
2010-11-12T10:07:47.480Z
A longer term link: http://arxiv.org/abs/0910.1191
András Salamon
CC BY-SA 2.5
2010-11-11T22:03:45.393Z
2010-11-11T22:03:45.393Z
Warren Schudy
<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-11T22:13:37.257Z
For adversarial errors see http://cstheory.stackexchange.com/questions/423/any-fast-algorithm-for-minimum-cost-feedback-arc-set-problem/ .
Warren Schudy
<reference-request><randomness><sorting>
Ranking with errors
Simd
# Ranking with errors

(Asked by: username_0 on 2010-11-11)

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.

**Tags:** reference-request, randomness, sorting
> **Comments:**
> **username_1**: For adversarial errors see http://cstheory.stackexchange.com/questions/423/any-fast-algorithm-for-minimum-cost-feedback-arc-set-problem/ .  

---

## 1 answers

### Answer by username_1 on 2010-11-11. Score: 10 | Accepted 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.)

> **Comments:**
> **username_2**: 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.  
> **username_0**: Thanks very much Warren.  I think that is the perfect paper for me to be getting on with.  
> **username_3**: A longer term link: http://arxiv.org/abs/0910.1191  

---

