Noisy Sorting Capacity
- 8 July 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (9) , 6121-6138
Abstract
Sorting is the task of ordering n elements using pairwise comparisons. It is well known that $m=\Theta (n\log n)$ comparisons are both necessary and sufficient when the outcomes of the comparisons are observed with no noise. In this paper, we study the sorting problem when each comparison is incorrect with some fixed yet unknown probability p. Unlike the common approach in the literature which aims to minimize the number of pairwise comparisons m to achieve a given desired error probability, we consider randomized algorithms with expected number of queries $\textsf {E}[M]$ and aim at characterizing the maximal sorting rate $\frac {n\log n}{\mathop {\mathrm {\textsf {E}}}\nolimits [M]}$ such that the ordering of the elements can be estimated with a vanishing error probability asymptotically. The maximal rate is referred to as the noisy sorting capacity. In this work, we derive upper and lower bounds on the noisy sorting capacity. The two lower bounds — one for fixed-length algorithms and one for variable-length algorithms — are established by combining the insertion sort algorithm with the well-known Burnashev-Zigangirov algorithm for channel coding with feedback. Compared with existing methods, the proposed algorithms are universal in the sense that they do not require the knowledge of p, while maintaining a strictly positive sorting rate. Moreover, we derive a general upper bound on the noisy sorting capacity, along with an upper bound on the maximal rate that can be achieved by sorting algorithms that are based on insertion sort.Keywords
All Related Versions
Funding Information
- Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery (RGPIN-2019-05448)
- NSERC Collaborative Research and Development (CRDPJ 54367619)
- National Science Foundation (IIS-1901252, CCF-1909499)
This publication has 19 references indexed in Scilit:
- Noisy Sorting Capacity2022
- Optimal Feedback Communication Via Posterior MatchingIEEE Transactions on Information Theory, 2011
- The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well)2008
- Active Learning and Sampling2008
- Probability and Random Processes2001
- Adventures of a MathematicianPhysics Today, 1976
- Some problems in dissonance theory research on information selectivity.Psychological Bulletin, 1967
- Sequential transmission using noiseless feedbackIEEE Transactions on Information Theory, 1963
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963
- Teaching combinatorial tricks to a computer1960