# Noisy Sorting Capacity

Ziao Wang1, Nadim Ghaddar2, Banghua Zhu3, Lele Wang1
This work was presented in part at the 2022 IEEE International Symposium on
Information Theory. 1University of British Columbia, Vancouver, BC V6T1Z4,
Canada, {ziaow<EMAIL_ADDRESS>
2University of California San Diego, La Jolla, CA 92093, USA,
<EMAIL_ADDRESS>
3University of California Berkeley, Berkeley, CA 94720, USA,
<EMAIL_ADDRESS>
###### 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 in the presence of noise. 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
$\operatorname{\textsf{E}}[M]$ and aim at characterizing the maximal ratio
$\frac{n\log n}{\operatorname{\textsf{E}}[M]}$ such that the ordering of the
elements can be estimated with a vanishing error probability asymptotically.
The maximal ratio is referred to as the _noisy sorting capacity_. In this
work, we derive upper and lower bounds on the noisy sorting capacity. We
establish two lower bounds, one for fixed-length algorithms and one for
variable-length algorithms. The proposed algorithms exploit the connection
between noisy searching and channel coding with feedback and incorporate the
insertion sort algorithm with the Burnashev–Zigangirov algorithm for channel
coding with feedback. Moreover, we derive an upper bound for the noisy sorting
capacity and an upper bound for the achievable rates of algorithms based on
insertion sort.

###### Index Terms:

Sorting algorithms, coding for channels with feedback, posterior matching.

##  I Introduction

Sorting is a fundamental operation in computing. Given a set of $n$ elements,
a sorting algorithm sequentially submits queries consisting of pairs of
elements to be compared, and outputs a permutation that arranges the elements
into some global order. In the design of a sorting algorithm, it is desirable
to minimize the number of queries (or pairwise comparisons). Clearly, any
sorting algorithm requires at least $\log(n!)=n\log n-n\log e+\Theta(\log n)$
queries, since there are $n!$ permutations for a set of $n$ elements and each
query reveals at most one bit of information. It is well known that using, for
example, the merge sort algorithm, $n\log n+n+O(\log n)$ queries are
sufficient to sort $n$ elements [1]. Therefore, to sort a set of $n$ elements,
it is both necessary and sufficient to submit $n\log n(1+o(1))$ queries.

Now suppose there is observation noise in the answers to the queries. For
example, the answer to each query is flipped independently with some fixed and
known probability $p\in(0,1/2)$. How many more queries are needed to sort $n$
elements? We aim to find the minimum number of queries such that the
probability of recovering the correct permutation goes to one as $n$ tends to
infinity. As we shall see in this paper, $\Theta(n\log n)$ queries is both
necessary and sufficient for sorting with i.i.d. noise. Towards this end, our
goal will be to characterize the _sorting rate_

$R\triangleq\frac{n\log n}{\operatorname{\textsf{E}}[M]},$ (1)

where $M$ denotes the number of queries, and the expectation accounts for
(possibly) any randomness in the querying strategy. The sorting rate can be
interpreted as the ratio of the minimum number of queries needed on average in
the noiseless case to the average number of queries used in the noisy setting.

Although the sorting rate of the merge sort algorithm in the noiseless case
can be made arbitrarily close to 1 when $n$ is large enough, it is not
immediately obvious if, in the noisy setting, a strictly positive rate is even
possible. For example, let’s consider a modified version of the merge sort
algorithm, where every comparison is repeated a number of times, and the
outcome is taken as the majority vote of the responses. Since there are at
least $k\triangleq n\log n(1+o(1))$ distinct pairwise comparisons to be made
by the merge sort algorithm, there should exist at least one comparison that
will be repeated at most
$\left\lfloor\frac{\operatorname{\textsf{E}}[M]}{k}\right\rfloor\leq\left\lfloor\frac{1}{R}\right\rfloor\triangleq\mu$
times on average. Thus, the probability of error of this modified version of
merge sort can be lower bounded by the error probability of this particular
comparison, which can be further lower bounded by

$\sum_{i=\lceil\mu/2\rceil}^{\mu}\binom{\mu}{i}p^{i}(1-p)^{\mu-i}\geq\frac{1}{\sqrt{2\mu}}\exp\left\\{-\mu
D\left(\frac{1}{2}\Big{\|}p\right)\right\\}\,\not\to 0,$

where $D(a\|b)\triangleq a\log\frac{a}{b}+(1-a)\log\frac{1-a}{1-b}$ and the
lower bound is due to [2, Lemma 4.7.2]. Therefore, for any non-vanishing rate
$R$, a repetition-based merge sort algorithm yields a non-vanishing
probability of error.

###  I-A Related Work

The noisy sorting problem has been studied in the literature in a more general
setting known as active ranking [3, 4, 5, 6, 7]. In this setting, it is
assumed that the observation noise $p_{ij}$ for the comparison of elements $i$
and $j$ is unknown and could be different for different pairs. When
specialized to our noisy sorting problem with $p_{ij}\equiv p$ for all pairs
$(i,j)$, the algorithms proposed in [3], [4], [5], and [6] require
$O(n\log^{2}n)$, $O(n\log n(\log\log n)^{3})$, $O(n^{3}\log n)$ and
$O(n^{3}\log n\log\log n)$ queries respectively. The algorithm proposed in [7]
outputs the _set_ of the $k$ highest ranked items. By running the algorithm
iteratively for $k=1,\ldots,n-1$, one can get the full ranking of the $n$
items with $O(n^{4}\log n)$ queries. Evaluated in our framework, the sorting
rates of these algorithms in [3, 4, 5, 6, 7] are all vanishing. To the best of
our knowledge, the algorithm leading to the best non-vanishing sorting rate is
given in [8]. Later in Theorem 6 of Section III-C, we refine the analysis in
[8] and derive the sorting rate under the proposed framework.

Other related but different settings for noisy sorting in the literature
include the cases when some distance metric for permutations is to be
minimized (rather than the the probability of error) [9, 10, 11, 12, 13, 14,
15, 5, 16], when the noise for each pairwise comparison is not i.i.d. and is
determined by some noise model (e.g. the Bradley–Terry–Luce model[17]) [18,
12, 14, 19, 20, 21], or when the ordering itself is restricted to some subset
of all permutations [22, 23].

Figure 1: Comparison of achievable rates of the proposed noisy sorting
algorithm and the existing algorithm, together with the converse bound.

###  I-B Our contributions

Inspired by Shannon’s formulation of the channel coding problem, the noisy
sorting problem is formulated in this work as one of finding the _sorting
capacity_ , which is the maximum sorting rate $R$ such that the probability of
error can be made arbitrarily small when the number of items $n$ is
sufficiently large. This paper provides upper and lower bounds on the sorting
capacity when the observation noise in each query is i.i.d. Bern$(p)$. For the
converse, an intuitive upper bound on the sorting capacity is the feedback
capacity of the BSC$(p)$ channel. This is because each noisy response of the
query can be viewed as the channel output of a BSC$(p)$ channel where the
channel input is the noiseless response. When each query conveys at most
$1-H(p)$ bits, it takes on average $\log(n!)/(1-H(p))$ queries to convey the
information contained in an unknown permutation. This leads to the upper bound
$1-H(p)$ on the sorting capacity, which is shown as the blue curve in Figure
1. We make this intuitive argument formal in Theorem 3. For the achievability,
to the best of our knowledge, the existing algorithm with the highest
achievable sorting rate is proposed in [8]. The algorithm is based on the
insertion sort algorithm for sorting in the noiseless case. Each insertion
step is done by a noisy searching tree algorithm for estimating the position
of an element in a sorted list with noisy pairwise comparisons. We apply
refined analysis to this algorithm and present the rate it achieves in Theorem
6. Its achievable rate is shown as the black dotted curve in Figure 1. In this
paper, we propose two noisy sorting algorithms that strictly improve the best
known sorting rate. The proposed algorithms build on insertion sort and
exploit connection between noisy insertion and channel coding with feedback.
The first algorithm has the additional feature that the number of queries is
predetermined (i.e., independent from the query responses) and thus termed
_fixed-length_ sorting code. It turns out that replacing the noisy searching
tree algorithm in [8] by the Burnashev–Zigangirov algorithm for channel coding
with feedback strictly improves the sorting rate for all $p\in[0,1]$, as shown
in the red dotted curve in Figure 1. Moreover, by allowing variable-length
algorithms, we further improve the achievable sorting rate to
$\frac{1}{2}(1-H(p))$ as shown in the green dotted curve in Figure 1. Finally,
because we have considered three different noisy sorting codes based on the
insertion sort algorithm, a natural question is: What is the highest
achievable sorting rate for this family of algorithms? It turns out that the
maximum rate achieved by the family of insertion-based noisy sorting codes is
shown to be upper bounded by

$\frac{1}{\frac{1}{1-H(p)}+\frac{1}{D(p||1-p)}},$

where $D(p||1-p)\triangleq p\log\frac{p}{1-p}+(1-p)\log\frac{1-p}{p}$. This
bound is strictly lower than the $1-H(p)$ bound, as plotted as the magenta
curve in Figure 1. The bounds derived in this paper can be seen as a first
step towards establishing a complete characterization of the sorting capacity
in the presence of i.i.d. $\mathrm{Bern}(p)$ noise.

###  I-C Paper Organization and Notation

The rest of the paper is organized as follows. In Section II-A, we formally
define the noisy sorting problem and state the definitions of noisy sorting
rate and noisy sorting capacity. We present our main results in Section II-B,
which are achievability theorems and two two converse theorems for the noisy
sorting problem. In Section III, we prove the two achievability theorems by
proposing two noisy sorting codes. The two converse theorems are proved in
Section IV. In Section V, we conclude our results and introduce some open
problems.

Notation: For an integer $n$, let $[n]=\\{1,2,\ldots,n\\}$. Let
$\log(\cdot)=\log_{2}(\cdot)$. We follow the standard order notation:
$f(n)=O(g(n))$ if $\lim_{n\to\infty}\frac{|f(n)|}{g(n)}<\infty$;
$f(n)=\Omega(g(n))$ if $\lim_{n\to\infty}\frac{f(n)}{g(n)}>0$;
$f(n)=\Theta(g(n))$ if $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$; $f(n)=o(g(n))$
if $\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$; $f(n)=\omega(g(n))$ if
$\lim_{n\to\infty}\frac{|f(n)|}{|g(n)|}=\infty$; and $f(n)\sim g(n)$ if
$\lim_{n\to\infty}\frac{f(n)}{g(n)}=1$.

##  II Problem Formulation and Main Results

###  II-A Noisy Sorting Problem

Suppose an agent wishes to sort a set of $n$ elements based on noisy pairwise
comparisons, where each comparison is incorrect with some fixed and known
probability $p\in[0,1/2)$. We assume that $p$ is bounded away from $1/2$
throughout the paper. The agent submits a query consisting of a pair of
indices $i$ and $j$, and receives a noisy response of whether element $i$ is
ranked higher or lower than element $j$. The goal is to estimate the total
ordering of the elements111For simplicity, we assume that the ranking metrics
among the elements are distinct, i.e., the total ordering is unique.. More
formally, let $\\{\theta_{1},\ldots,\theta_{n}\\}$ be a finite set of real
numbers to be sorted. An ordering is characterized by a permutation mapping
$\pi:[n]\to[n]$ such that

$\theta_{\pi(1)}<\theta_{\pi(2)}<\cdots<\theta_{\pi(n)}.$

At the $k$th time step, the agent submits the query
$(U_{k},V_{k})\triangleq(\theta_{i},\theta_{j})$ for some $i,j\in[n]$, $i\neq
j$, and gets the response $Y_{k}$ which can be expressed as

$Y_{k}=\mathbbm{1}_{\\{U_{k}<V_{k}\\}}\oplus Z_{k},$

where $\mathbbm{1}_{\\{\cdot\\}}$ denotes the indicator function, and
$Z_{k}\sim\mathrm{Bern}(p)$ is a sequence of i.i.d. random variables. The
agent aims to compute an estimate $\hat{\pi}$ of $\pi$ based on the responses.

######  Definition 1.

An _adaptive_ querying strategy $\\{f_{k}\\}_{k\geq 1}$ associated with a
stopping time (i.e., number of queries) $M$ is a causal protocol for
determining the queries

$(U_{k},V_{k})=f_{k}(Y^{k-1},U^{k-1},V^{k-1})$

in the $k$th time step. If the number of queries $M$ is predetermined (i.e.,
independent of the query responses), we say that the querying strategy is
_fixed-length_. Otherwise, the strategy may have a variable stopping time
which can depend on the query responses.

######  Definition 2.

An $(R,n)$ _noisy sorting code_ for the noisy sorting problem consists of an
adaptive querying strategy $\\{f_{k}\\}_{k\geq 1}$ associated with a stopping
time $M$, and an estimator $\hat{\Pi}=\hat{\pi}(Y^{M},U^{M},V^{M})$, where
$\operatorname{\textsf{E}}[M]=\frac{n\log n}{R}$ is the expected number of
queries, and $R$ is the sorting rate. When the querying strategy is fixed-
length, we refer to the code as an $(R,n)$ _fixed-length noisy sorting code_.

######  Definition 3.

A sorting rate $R$ is said to be _achievable_ for the noisy sorting problem if
there exists a sequence of $(R,n)$ noisy sorting codes such that

$\lim\limits_{n\to\infty}\max_{\pi}\operatorname{\textsf{P}}\\{\hat{\Pi}\neq\pi\\}=0.$

######  Definition 4.

A sorting rate $R_{\mathrm{f}}$ is said to be _fixed-length-achievable_ for
the noisy sorting problem if there exists a sequence of $(R_{\mathrm{f}},n)$
fixed-length noisy sorting codes such that

$\lim\limits_{n\to\infty}\max_{\pi}\operatorname{\textsf{P}}\\{\hat{\Pi}\neq\pi\\}=0.$

######  Definition 5.

The _noisy sorting capacity_ $C(p)$ is defined as the supremum over all
achievable sorting rates for the noisy sorting problem when the observation
noise is i.i.d. $\mathrm{Bern}(p)$. The _fixed-length noisy sorting capacity_
$C_{\mathrm{f}}(p)$ is defined analogously.

######  Remark 1.

Because fixed-length noisy sorting codes are special instances of noisy
sorting codes, it follows that $C_{\mathrm{f}}(p)\leq C(p)$ for any $0\leq
p\leq 1$.

######  Remark 2 (Reduction to average error probability).

Suppose we have an $(R,n)$ noisy sorting code that achieves an _average_ error
probability $\operatorname{\textsf{P}}(\hat{\Pi}\neq\Pi)\triangleq\epsilon$
for a uniformly chosen permutation $\Pi\sim\mathrm{Unif}(\mathcal{S}_{n})$.
Such a code can be used to construct an $(R,n)$ noisy sorting code achieving a
_worst case_ error probability identical to the error of the average code,
i.e., $\max_{\pi}\operatorname{\textsf{P}}(\hat{\Pi}\neq\pi)=\epsilon$. To see
this, consider a uniformly chosen permutation $\bar{\Pi}$ and use it to rename
the items $\theta_{1},\ldots,\theta_{n}$ by
$\theta_{\bar{\Pi}(1)},\ldots,\theta_{\bar{\Pi}(n)}$. Then, the noisy sorting
code achieving an average error probability can be used to estimate the
composed permutation $\bar{\Pi}\circ\pi$, which has a uniform distribution.
Thus, we have that
$\operatorname{\textsf{P}}(\hat{\Pi}\neq(\bar{\Pi}\circ\pi))=\epsilon$. Since
we know $\bar{\Pi}$, if we correctly estimate $\hat{\Pi}=\bar{\Pi}\circ\pi$,
we can always retrieve $\pi$ be applying the inverse of $\bar{\Pi}$ to
$\hat{\Pi}$. Therefore, when we analyze the worst case error probability of a
noisy sorting code, we can assume without loss of generality that the true
permutation $\pi$ has a uniform prior.

Input : Unordered elements $\theta_{1},\ldots,\theta_{n}$, crossover
probability $p$.

Output : Permutation estimate $\hat{\pi}$.

1 Initialize $\sigma$ as a $1\times 1$ array with element $n$.

for  _$i=1,\ldots,n-1$_ do

2
$\hat{l}\leftarrow\texttt{SEARCH}\big{(}(\theta_{\sigma(1)},\ldots,\theta_{\sigma(i)}),\>\theta_{n-i}\big{)}$.

3
$\sigma\leftarrow\big{(}\sigma(1:\hat{l}-1),\>\,n-i,\>\,\sigma(\hat{l}:\text{end})\big{)}$.

end for

4$\hat{\pi}\leftarrow\sigma$.

// Treat the $1\times n$ array $\sigma$ as a permutation

5 return _$\hat{\pi}$_

Algorithm 1 Insertion-Based Noisy Sorting Codes

We are also interested in a family of _insertion-based noisy sorting codes_ ,
which we define next. These codes are inspired by the insertion sort algorithm
for sorting in the noiseless case. This algorithm successively inserts each
element in its estimated position with respect to the previously inserted
elements. That is, the algorithm first inserts $\theta_{n-1}$ in its estimated
position with respect to $\theta_{n}$. Then, $\theta_{n-2}$ is inserted in its
estimated position with respect to $\\{\theta_{n-1},\theta_{n}\\}$, and so on,
until all elements are inserted. Hence, in the $i$th iteration step, the
algorithm runs an instance of a searching algorithm to insert $\theta_{n-i}$
in its position with respect to the previously ordered list. In the presence
of noise, a similar technique can be followed using a suitable _noisy
searching_ algorithm. A pseudocode describing the family of insertion-based
noisy sorting codes is given in Algorithm 1, where
$\texttt{SEARCH}\big{(}(\theta_{\sigma(1)},\ldots,\theta_{\sigma(i)}),\>\theta_{n-i}\big{)}$
corresponds to the noisy searching algorithm which returns the position
$\hat{l}$ of $\theta_{n-i}$ within the ordered list
$(\theta_{\sigma(1)},\ldots,\theta_{\sigma(i)})$, assuming the ordering
generated from the previous insertions is correct. Note that different
algorithms in the family of insertion-based noisy sorting codes correspond to
different noisy searching algorithms. The sorting rate of an insertion-based
noisy sorting code is defined as in (1), where $\operatorname{\textsf{E}}[M]$
is the expected number of queries across all searching iterations.

######  Definition 6.

A sorting rate $R_{\mathrm{ins}}$ is said to be _insertion-sort-achievable_
for the noisy sorting problem if there exists a sequence of
$(R_{\mathrm{ins}},n)$ insertion-based noisy sorting codes such that

$\lim\limits_{n\to\infty}\max_{\pi}\operatorname{\textsf{P}}\\{\hat{\Pi}\neq\pi\\}=0.$

######  Definition 7.

The _insertion-based noisy sorting capacity_ $C_{\mathrm{ins}}(p)$ is defined
as the supremum over all insertion-sort-achievable sorting rates for the noisy
sorting problem when the observation noise is i.i.d. $\text{Bern}(p)$.

######  Remark 3.

Since insertion-based noisy sorting codes are special instances of noisy
sorting codes, it follows that $C_{\mathrm{ins}}(p)\leq C(p)$ for any $0\leq
p\leq 1$.

In this work, we derive upper and lower bounds on the sorting capacity $C(p)$.
We also derive a lower bound on the fixed-length noisy sorting capacity
$C_{\mathrm{f}}(p)$ and an upper bound on the insertion-based noisy sorting
capacity $C_{\mathrm{ins}}(p)$. Note that under this information theoretic
formulation of the noisy sorting problem, both the number of elements and the
expected number of queries are taken to infinity, while keeping the ratio of
the two (i.e., the sorting rate) fixed. The goal here is to characterize the
maximum sorting rate that can allow to estimate the permutation $\pi$ with a
vanishing error probability asymptotically. Note that this formulation is
quite different from the approach taken in the existing literature, where the
number of elements is considered to be fixed, and the goal is to minimize the
expected number of queries to achieve some desired error probability. One can
see that our formulation of the problem is similar in nature to Shannon’s
formulation of the channel coding problem.

###  II-B Main Results

The main results of this paper can be summarized in four theorems. The first
two theorems are achievability results. They provide lower bounds for the
noisy sorting capacity and fixed-length noisy sorting capacity respectively.
Both bounds strictly improve the rate attained by the algorithm in [8]. The
other two theorems are converse results. They provide upper bounds for noisy
sorting capacity and insertion-based noisy sorting capacity respectively.

######  Theorem 1 (Achievability).

Any sorting rate

$R<\frac{1}{2}(1-H(p))$

is achievable for the noisy sorting problem using the noisy sorting algorithm
presented in Section III-B, where $H(\cdot)$ denotes the binary entropy
function. In other words, $C(p)\geq\frac{1}{2}(1-H(p))$.

######  Theorem 2 (Achievability of fixed-length noisy sorting codes).

Any sorting rate

$R_{\mathrm{f}}<\frac{1}{2}\log(1/g(p)),$

where $g(p)\triangleq\frac{1}{2}+\sqrt{p(1-p)}$, is achievable for the noisy
sorting problem using the fixed-length noisy sorting algorithm presented in
Section III-A. In other words, $C_{\mathrm{f}}(p)\geq\frac{1}{2}\log(1/g(p))$.

Theorems 1 and 2 will be proved in Section III, by giving specific
constructions of noisy sorting codes. Both constructions that will be
discussed are based on algorithms designed for the _noisy searching problem_ ,
the problem of locating an element within a sorted sequence when noise is
present. Before we describe the code constructions in Section III, we briefly
introduce the noisy searching problem in Section II-C, while setting up the
necessary notation.

######  Theorem 3 (Converse).

The noisy sorting capacity $C(p)$ is upper bounded as

$C(p)\leq 1-H(p).$

######  Theorem 4 (Converse for insertion-based noisy sorting codes).

The insertion-based noisy sorting capacity $C_{\mathrm{ins}}(p)$ is upper
bounded as

$C_{\mathrm{ins}}(p)\leq\frac{1}{\frac{1}{1-H(p)}+\frac{1}{D(p||1-p)}}.$

Intuitively, the result of Theorem 3 is expected, since every query can give
at most $1-H(p)$ bits of information about the unknown permutation $\pi$.
Thus, any sequence of $(R,n)$ noisy sorting codes with vanishing error
probability should have

$\log(n!)\leq\operatorname{\textsf{E}}[M](1-H(p)),$

which directly implies the statement of Theorem 3. The proof of both converse
theorems are based on a converse for the noisy searching problem described in
section II-C. We defer the formal proofs of Theorems 3 and 4 to Section IV.

###  II-C Detour: Noisy Searching Problem

In the noisy searching problem, an agent aims to identify the position of a
given real number $\tilde{\theta}$ within a sorted sequence
$(\tilde{\theta}_{0},\tilde{\theta}_{1},\ldots,\tilde{\theta}_{n})$, where
$\tilde{\theta}_{0}=-\infty$ and $\tilde{\theta}_{n}=\infty$222Throughout the
paper, we use the “tilde” mark over variables that are associated with the
noisy searching problem.. That is, the goal of the agent is to identify the
index $l^{*}$ such that

$\tilde{\theta}_{l^{*}-1}<\tilde{\theta}<\tilde{\theta}_{l^{*}}.$

To aid in the exposition, denote by $I_{i}$ the $i$th sub-interval among the
sorted sequence, i.e., $I_{i}=(\tilde{\theta}_{i-1},\tilde{\theta}_{i}]$ for
each $i\in[n-1]$, and $I_{n}=(\tilde{\theta}_{n-1},\tilde{\theta}_{n})$. At
the $k$th time step, the agent gives the system a query
$\tilde{U}_{k}\triangleq\tilde{\theta}_{i}$ for some $i\in[n-1]$, and receives
a noisy response $\tilde{Y}_{k}$ of whether $\tilde{U}_{k}$ lies to the left
or right of $\tilde{\theta}$. The response $\tilde{Y}_{k}$ can be expressed as

$\tilde{Y}_{k}=\mathbbm{1}_{\\{\tilde{U}_{k}<\tilde{\theta}\\}}\oplus\tilde{Z}_{k},$
(2)

where $\tilde{Z}_{k}\sim\mathrm{Bern}(p)$ is a sequence of i.i.d. random
variables.

Each variable-length noisy searching algorithm consists of an adaptive
_querying strategy_ $\\{\tilde{f}_{k}\\}_{k=1}^{\infty}$, which is a causal
protocol for determining the queries

$\tilde{U}_{k}=\tilde{f}_{k}(\tilde{Y}^{k-1},\tilde{U}^{k-1}).$

The adaptive querying strategy is associated with a stopping time $\tilde{M}$.
Its output is an estimate
$\hat{L}=\hat{l}(\tilde{Y}^{\tilde{M}},\tilde{U}^{\tilde{M}})$ for the
location $l^{*}$. Notice that the random stopping time $\tilde{M}$ represents
the number of the queries made by the algorithm. A desirable goal of designing
noisy searching algorithm is to minimize the expected number of queries
$\operatorname{\textsf{E}}[\tilde{M}]$ while keeping the error probability
$\operatorname{\textsf{P}}(\hat{L}\neq l^{*})$ small.

The noisy searching problem was first introduced by Rényi [24] and Ulam [25]
in the context of a “two-player 20-question game with lies”, and further
developed by Berlekamp [26] and Horstein [27] in the context of coding for
channels with noiseless feedback. The resemblance to the coding problem holds
by viewing the position of $\theta$ as a message that needs to be communicated
over a binary symmetric channel with crossover probability $p$, and the number
of queries submitted by the agent as the number of channel uses. The
availability of noiseless feedback pertains to the fact that the agent can use
the previous received responses to adapt the querying strategy. If the agent
is allowed to query any point on the real line, then Horstein’s coding scheme
[27] suggests a querying strategy for the noisy searching problem: roughly
speaking, query the point that equally bisects the posterior of the target
point $\theta$ given the responses received so far. In fact, Shayevitz and
Feder have shown in [28] the optimality of Horstein’s coding scheme for the
channel coding problem. We discuss the detailed connection between the noisy
searching problem and the channel coding with feedback problem in Section IV.

The noisy searching problem has been also studied in settings where the agent
is restricted to query one of the elements $\theta_{i}$ of the sorted
sequence. It is known in the literature that an expected $\frac{\log
n}{1-H(p)}(1+o(1))$ queries are both necessary and sufficient to achieve
vanishing error probability [29, 30, 31, 32]. In [31, 32, 29], variable-length
algorithms achieving vanishing error probability with the above optimal
expected number of queries are proposed, while [29] also provides fixed-length
construction for the algorithm. In the following, we will describe the both
the variable-length and fixed-length noisy searching algorithms of [29], show
how they can be used to construct noisy sorting codes for the sorting problem,
and derive their achievable rates.

##  III Proof of Achievability results

In this section, we describe our achievability results for noisy sorting.
First, we prove Theorem 2 by proposing a fixed-length noisy sorting code and
analyze its achievable rate. Then, we prove Theorem 1 by modifying the fixed-
length code into a variable-length version and analyze the achievable rate.
Moreover, we apply a refined analysis to an existing noisy sorting code
proposed in [8] to compute its achievable rate. We show that the achievable
rates by the proposed noisy sorting codes are strictly higher than that of the
existing noisy sorting code in [8].

###  III-A Achievability: Fixed-length Noisy Sorting Code

In this section, we prove Theorem 2 by describing a fixed-length noisy sorting
code that can achieve any sorting rate $R<\frac{1}{2}\log(1/g(p))$. A key
ingredient of the proposed sorting code is the Burnashev–Zigangirov (BZ)
algorithm for the noisy searching problem [29], which we delineate below.

_Burnashev–Zigangirov Algorithm for Noisy Searching:_ Recall the noisy
searching problem outlined in Section II-C. Unlike Horstein’s scheme which
queries the median of the posterior distribution of the target point $\theta$,
the BZ algorithm queries one of the two endpoints of the sub-interval
containing the median. With this slight modification, Horstein’s scheme can be
generalized for searching over a finite set (i.e., the set of sub-intervals)
with a tractable analysis of the error probability.

To this end, let

$q_{k}(i)\triangleq\operatorname{\textsf{P}}\\{\tilde{\theta}\in
I_{i}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\tilde{Y}_{1},\ldots,\tilde{Y}_{k},\tilde{U}_{1},\ldots,\tilde{U}_{k}\\}$

denote the posterior distribution of the sub-intervals in the $k$th time step,
initialized uniformly among the sub-intervals, where $1\leq i\leq n$ and
$1\leq k\leq\tilde{m}$. Also, let $j(k)$ be the index of the sub-interval
containing the median of the $(k-1)$th posterior distribution, i.e., $j(k)$ is
the index s.t.

$\sum_{i=1}^{j(k)-1}q_{k-1}(i)\leq\frac{1}{2}\quad\text{and}\quad\sum_{i=1}^{j(k)}q_{k-1}(i)>\frac{1}{2}.$
(3)

The querying strategy of the BZ algorithm is to choose $\tilde{U}_{k}$
randomly among $\\{\tilde{\theta}_{j(k)-1},\tilde{\theta}_{j(k)}\\}$, as
follows. Let

$j^{*}(k)=\begin{cases}j(k)-1&\>\>\>\text{with probability }p^{*}(k),\\\
j(k)&\>\>\>\text{with probability }1-p^{*}(k),\end{cases}$ (4)

where

$p^{*}(k)=\frac{2\sum_{i=1}^{j(k)}q_{k-1}(i)-1}{2q_{k-1}(j(k))},$

and set $\tilde{U}_{k}=\tilde{\theta}_{j^{*}(k)}$. The remaining part of the
algorithm is to update the posteriors $q_{k}(i)$ after receiving the noisy
response $\tilde{Y}_{k}=\tilde{y}_{k}$. It is not difficult to check that this
can be done recursively through the following updates, where a parameter
$\alpha$ such that $p<\alpha<1/2$ is used for the crossover probability
(instead of $p$).333The usage of the parameter $\alpha$ instead of $p$ is an
artifact of the analysis of the algorithm. That is, according to the analysis
in [29], any choice of $\alpha$ such that $p<\alpha<1/2$ guarantees a
vanishing error probability.

$\displaystyle
q_{k}(i)=\begin{cases}\frac{2(1-\alpha)q_{k-1}(i)}{1+(1-2\tilde{y}_{k})(1-2\alpha)\tau(k)}&\>\>\>\text{if
}\tilde{y}_{k}=\mathbbm{1}_{\\{j^{*}(k)\leq i\\}},\\\\[5.0pt] \frac{2\alpha
q_{k-1}(i)}{1+(1-2\tilde{y}_{k})(1-2\alpha)\tau(k)}&\>\>\>\text{otherwise},\end{cases}$
(5)

where

$\tau(k)=2\sum_{i=1}^{j^{*}(k)}q_{k-1}(i)-1.$

After $\tilde{m}$ queries, the output of the BZ algorithm is the index $i$ of
the sub-interval with the largest posterior $q_{\tilde{m}}(i)$.

A pseudocode of the BZ algorithm is given in Algorithm 2. By taking
$\alpha=\frac{\sqrt{p}}{\sqrt{p}+\sqrt{1-p}}$, it is shown in [29] that

$\operatorname{\textsf{P}}\\{\tilde{\theta}\notin
I_{\hat{l}}\\}\leq(n-1)\Big{(}\frac{1}{2}+\sqrt{p(1-p)}\Big{)}^{\tilde{m}}.$
(6)

Input : Ordered sequence $(\tilde{\theta}_{1},\ldots,\tilde{\theta}_{n-1})$,
target $\tilde{\theta}$, number of queries $\tilde{m}$, crossover probability
$p$.

Output : Index $\hat{l}$ of the sub-interval containing $\tilde{\theta}$.

1 $\alpha\leftarrow\frac{\sqrt{p}}{\sqrt{p}+\sqrt{1-p}}$.

2 $q_{0}(i)\leftarrow 1/n$ for each $i\in[n]$.

for  _$k=1,\ldots,\tilde{m}$_ do

3 Find $j(k)$ using inequalities in (3).

4 Set $j^{*}(k)$ according to (4).

5 Set $\tilde{U}_{k}\leftarrow\tilde{\theta}_{j^{*}(k)}$.

6 Receive noisy response $\tilde{Y}_{k}$.

7 Update $q_{k}(i)$ for each $i\in[n]$ as in (5).

end for

8$\hat{l}\leftarrow\arg\max_{i}\,q_{\tilde{m}}(i)$.

9 return _$\hat{l}$_

Algorithm 2 Fixed-length Burnashev–Zigangirov BZ Algorithm

_Proposed Fixed-length Noisy Sorting Code:_ The proposed fixed-length noisy
sorting code uses the well-known insertion sort along with the BZ algorithm.
More specifically, for each $i\in\\{1,\ldots,n-1\\}$, the BZ algorithm is used
to _insert_ $\theta_{n-i}$ in the correct location within the already-sorted
sequence of elements. That is, $\theta_{n-1}$ is initially inserted in its
estimated position with respect to $\theta_{n}$, and then $\theta_{n-2}$ is
inserted in its estimated position with respect to now-known ordering of
$\theta_{n-1}$ and $\theta_{n-2}$, and so on. In the $i$th insertion, this
corresponds to an application of the BZ algorithm with a sorted sequence of
length $i$. Further, the code uses $\lfloor\frac{m}{n-1}\rfloor$ queries for
each insertion, where $m$ denotes the total number of queries for noisy
sorting. Algorithm 3 shows the pseudocode of the proposed fixed-length noisy
sorting code.

Input : Unordered elements $\theta_{1},\ldots,\theta_{n}$, number of queries
$m$, crossover probability $p$.

Output : Permutation estimate $\hat{\pi}$.

1 Initialize $\sigma$ as a $1\times 1$ array with element $n$.

for  _$i=1,\ldots,n-1$_ do

2
$\hat{l}\leftarrow\texttt{BZ}\big{(}(\theta_{\sigma(1)},\ldots,\theta_{\sigma(i)}),\>\theta_{n-i},\>\lfloor\frac{m}{n-1}\rfloor,\>p\big{)}$.

3
$\sigma\leftarrow\big{(}\sigma(1:\hat{l}-1),\>\,n-i,\>\,\sigma(\hat{l}:\text{end})\big{)}$.

end for

4$\hat{\pi}\leftarrow\sigma$.

// Treat the $1\times n$ array $\sigma$ as a permutation

5 return _$\hat{\pi}$_

Algorithm 3 Fixed-length Noisy Sorting Code

Let $P_{e}(i)$ denote the probability of error of the $i$th insertion. Then,
the error probability of the proposed noisy sorting code can be bounded as

$\displaystyle\operatorname{\textsf{P}}\\{\hat{\Pi}\neq\pi\\}$
$\displaystyle\leq\sum_{i=1}^{n-1}P_{e}(i)$
$\displaystyle\overset{(a)}{\leq}\sum_{i=1}^{n-1}i\Big{(}\frac{1}{2}+\sqrt{p(1-p)}\Big{)}^{\lfloor\frac{m}{n-1}\rfloor}$
$\displaystyle\overset{(b)}{\leq}\frac{n(n-1)}{2}\Big{(}\frac{1}{2}+\sqrt{p(1-p)}\Big{)}^{\frac{\log
n}{R}-1}$ $\displaystyle\leq n^{2}\exp{\Big{\\{}-\frac{\ln
n}{R}\log(1/g(p))\Big{\\}}},$

where $g(p)=\frac{1}{2}+\sqrt{p(1-p)}$, $(a)$ follows from the error
probability of the BZ algorithm given in (6), and $(b)$ follows by setting
$m=\lceil\frac{n\log n}{R}\rceil$. It follows that
$\operatorname{\textsf{P}}\\{\hat{\Pi}\neq\pi\\}$ goes to zero as $n\to\infty$
if

$R<\frac{1}{2}\log(1/g(p)),$

which is the desired result.

###  III-B Achievability: Variable-length Noisy Sorting Code

In this section, we prove Theorem 1 by describing a noisy sorting code that
can achieve any sorting rate $R<\frac{1}{2}(1-H(p))$. The code is similar to
the one introduced in Section III-A. The major difference is that each noisy
searching step is performed by a variable-length version of the BZ algorithm.
We describe the difference between the variable-length BZ algorithm and the
fixed-length version in the following section.

_Variable-length BZ algorithm:_ The variable-length BZ algorithm is based on
the same idea of the fixed-length BZ algorithm. There are three differences
between these two versions.

  1. 1.

At each iteration, the variable-length BZ algorithm chooses the index $j^{*}$
of the query point $\tilde{\theta}_{j^{*}}$ by a different principle than (4):

$j^{*}(k)=\begin{cases}j(k)-1&\>\text{with probability }\pi_{1},\\\
j(k)&\>\text{with probability }\pi_{2}\triangleq 1-\pi_{1},\end{cases}$ (7)

where

$\pi_{1}\triangleq\frac{\rho(\tau_{2}(k))-\rho(-\tau_{2}(k))}{\rho(\tau_{1}(k))-\rho(-\tau_{1}(k))+\rho(\tau_{2}(k))-\rho(-\tau_{2}(k))}$
(8)

with

$\rho(x)\triangleq(1-p)\log(1+(1-2p)x)+p\log(1-(1-2p)x)$ (9)

for $|x|\leq 1$, and

$\tau_{1}(k)\triangleq
2\sum_{i=j(k)}^{n}q_{k-1}(i)-1\quad\text{and}\quad\tau_{2}(k)\triangleq
2\sum_{i=1}^{j(k)}q_{k-1}(i)-1.$ (10)

  2. 2.

The $\alpha$ value for posterior update in (5) is chosen to be the crossover
probability for each query $p$, so that the posterior updates exactly follow
the Bayes rule.

  3. 3.

The variable-length algorithm does not post a preset $m$ number of queries.
Instead, it takes a target error probability $P_{e}$ as input and runs for a
random number $\tilde{M}$ of queries. For each $i\in[n]$ and $k\geq 0$, define

$Z_{k}(i)\triangleq\log\frac{q_{k}(i)}{1-q_{k}(i)}.$ (11)

The algorithms terminates at $\tilde{M}$th iteration, where $\tilde{M}$ is the
smallest integer such that $Z_{\tilde{M}}(i)\geq-\log(P_{e})$ for some
$i\in[n]$.

A pseudocode of the variable-length BZ algorithm is given in Algorithm 4.

Input : Ordered sequence $(\tilde{\theta}_{1},\ldots,\tilde{\theta}_{n-1})$,
target $\tilde{\theta}$, tolerated error probability $P_{e}$, crossover
probability $p$.

Output : Index $\hat{l}$ of the sub-interval containing $\tilde{\theta}$.

1 $k\leftarrow 0$.

2 $q_{0}(i)\leftarrow 1/n$ for each $i\in[n]$.

3 Calculate $Z_{0}(i)$ for each $i\in[n]$ as in (11).

while  _$\max_{i}Z_{k}(i) <-\log(P_{e})$_ do

4 $k\leftarrow k+1$

5 Find $j(k)$ using inequalities in (3).

6 Set $j^{*}(k)$ according to (7).

7 Set $\tilde{U}_{k}\leftarrow\tilde{\theta}_{j^{*}(k)}$.

8 Receive noisy response $\tilde{Y}_{k}$.

9 Update $q_{k}(i)$ for each $i\in[n]$ as in (5).

10 Update $Z_{k}(i)$ for each $i\in[n]$ as in (11).

end while

11$\hat{l}\leftarrow\arg\max_{i}\,q_{k}(i)$.

12 return _$\hat{l}$_

Algorithm 4 Variable-length Burnashev–Zigangirov VLBZ Algorithm

For variable-length noisy searching algorithms, we assume the true position
$l^{*}$ follows a uniform prior. For the clarity of notation, we use random
variable $L^{*}$ to denote uniformly distributed true position. By the
property of MAP estimator, we have that the conditional error probability
$\operatorname{\textsf{P}}(\hat{L}\neq
L^{*}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\hat{L}=i)\leq
P_{e}$ for each $i\in[n]$, which further implies that the overall error
probability satisfies that

$\operatorname{\textsf{P}}(\hat{L}\neq L^{*})\leq P_{e}.$ (12)

Now, we present a theorem upper bounding the expected number of queries to
achieve $P_{e}$ error probability by the variable-length BZ noisy searching
scheme.

######  Theorem 5.

The number of queries $\tilde{M}$ in the variable-length BZ noisy searching
scheme satisfies that

$\mathsf{E}[\tilde{M}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}L^{*}=i]\leq\frac{\log
n-\log P_{e}+\log\frac{1-p}{p}}{1-H(p)}$ (13)

for any $i\in[n]$, which further implies that the overall expected number of
queries $\mathsf{E}[\tilde{M}]$ satisfies the same inequality

$\mathsf{E}[\tilde{M}]\leq\frac{\log n-\log P_{e}+\log\frac{1-p}{p}}{1-H(p)}.$
(14)

The proof of Theorem 5 given in [29] is written in Russian. For completeness,
we present an English version of the proof in the appendix.

_Proposed Variable-length Noisy Sorting code:_ The proposed variable-length
noisy sorting code calls the variable-length BZ algorithm at each insertion
step. The pseudocode is described in Algorithm 5.

Input : Unordered elements $\theta_{1},\ldots,\theta_{n}$, tolerated error
probability $P_{e}$, crossover probability $p$.

Output : Permutation estimate $\hat{\pi}$.

1 Initialize $\sigma$ as a $1\times 1$ array with element $n$.

for  _$i=1,\ldots,n-1$_ do

2
$\hat{l}\leftarrow\texttt{VLBZ}\big{(}(\theta_{\sigma(1)},\ldots,\theta_{\sigma(i)}),\>\theta_{n-i},\>\frac{P_{e}}{n},\>p\big{)}$.

3
$\sigma\leftarrow\big{(}\sigma(1:\hat{l}-1),\>\,n-i,\>\,\sigma(\hat{l}:\text{end})\big{)}$.

end for

4$\hat{\pi}\leftarrow\sigma$.

// Treat the $1\times n$ array $\sigma$ as a permutation

5 return _$\hat{\pi}$_

Algorithm 5 Variable-Length Noisy Sorting Code

With the proposed variable-length noisy sorting algorithm, we are ready to
prove Theorem 1. Towards that end, we analyze the error probability of the
algorithm and bound its expected number of queries with $P_{e}$ in the
algorithm set to $\frac{1}{\log n}$.

_Error Analysis:_ As we mentioned in Remark 2, we can assume without loss of
generality that $\pi$ follows a uniform prior. In this proof, for the clarity
of notation, we use random variable $\Pi$ to denote the uniformly distributed
true permutation. For each insertion step, we have already bounded its error
probability under the assumption of a uniform prior for its correct position.
Here we still need to argue that given the uniform prior on the permutation
$\Pi$, the true position for each insertion step follows a uniform prior.
Towards that goal, we introduce an alternative representation of a permutation
proposed in [33] known as the Lehmer code, and utilize two of its properties.

######  Definition 8.

For a permutation $\pi\in\mathcal{S}_{n}$, the Lehmer code is an $n$-tuple
$L(\pi)=(L(\pi)_{1},\ldots,L(\pi)_{n})$, where
$L(\pi)_{i}=|\\{j>i:\pi(j)<\pi(i)\\}|$.

######  Lemma 1.

The Lehmer code defines a bijection from the set of all permutations
$\mathcal{S}_{n}$ to the Cartesian product space
$([n-1]\cup\\{0\\})\times([n-2]\cup\\{0\\})\times\cdots\times\\{0\\}$.

######  Lemma 2.

Suppose $\Pi\sim\mathrm{Unif}(\mathcal{S}_{n})$. Then the
$L(\Pi)_{i}\sim\mathrm{Unif}\\{0,\ldots,n-i\\}$ for each $i\in[n]$.
Furthermore, the entries $L(\Pi)_{1},\ldots,L(\Pi)_{n}$ are mutually
independent.

Recall that the true underlying ranking of
$\\{\theta_{1},\ldots,\theta_{n}\\}$ is given by
$\theta_{\Pi(1)}<\theta_{\Pi(2)}<\cdots<\theta_{\Pi(n)}.$ By the definition of
Lehmer code, $L(\Pi^{-1})_{i}$ measures the number of items from
$\\{\theta_{i+1}\ldots,\theta_{n}\\}$ that are smaller than $\theta_{i}$. Also
notice that the $i$th insertion step of the variable-length noisy sorting code
is using the VLBZ algorithm to estimate the number of items from
$\\{\theta_{n-i+1},\ldots,\theta_{n}\\}$ that are smaller than $\theta_{n-i}$.
Therefore, the $i$th insertion step of the code is essentially estimating the
$(n-i)$th entry $L(\Pi^{-1})_{n-i}$ of the Lehmer code. Because there is a
one-to-one mapping between permutations and Lehmer codes, every insertion step
needs to be correct to output the correct estimation for $\Pi$. For
$i\in[n-1]$, let $\mathcal{E}_{i}$ denote the event that estimation at $i$th
insertion step is incorrect. We have

$\displaystyle\operatorname{\textsf{P}}(\hat{\Pi}=\Pi)$
$\displaystyle=\operatorname{\textsf{P}}(\mathcal{E}_{1}^{c}\cap\cdots\cap\mathcal{E}_{n-1}^{c})$
$\displaystyle=\prod_{k=1}^{n-1}\operatorname{\textsf{P}}(\mathcal{E}_{k}^{c}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\cap_{i=1}^{k-1}\mathcal{E}_{i}^{c})$
$\displaystyle=\prod_{k=1}^{n-1}\left(1-\operatorname{\textsf{P}}(\mathcal{E}_{k}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\cap_{i=1}^{k-1}\mathcal{E}_{i}^{c})\right)$
$\displaystyle\geq
1-\sum_{k=1}^{n-1}\operatorname{\textsf{P}}(\mathcal{E}_{k}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\cap_{i=1}^{k-1}\mathcal{E}_{i}^{c}).$

By Lemma 2, we know that each of $n$ entries of $L(\Pi^{-1})$ are uniformly
distributed and they are independent of each other. Therefore,
$\operatorname{\textsf{P}}(\mathcal{E}_{i}|\cap_{k=1}^{i-1}\mathcal{E}_{k}^{c})$
represents the error probability of the variable-length BZ algorithm called at
$i$th insertion step given a uniform prior for the correct position. By the
error probability of MAP estimator and because that we set the tolerated error
probability for each insertion step to $\frac{1}{n\log n}$, we know that
$\operatorname{\textsf{P}}(\mathcal{E}_{i}|\cap_{k=1}^{i-1}\mathcal{E}_{k}^{c})\leq\frac{1}{n\log
n}$ for each $i\in[n-1]$. Thus, we get that
$\operatorname{\textsf{P}}(\hat{\Pi}\neq\Pi)\leq\frac{1}{\log n}$, i.e., the
error probability of the algorithm achieves vanishing error probability as
$n\rightarrow\infty$.

_Number of Queries:_ Now, we analyze the expected number of queries of the
proposed variable-length noisy sorting code. Let $M_{i}$ denote the number of
queries at $i$th insertion. By Theorem 5, we know that the total number of
queries $M$ satisfies that

$\displaystyle\operatorname{\textsf{E}}[M]$
$\displaystyle=\sum_{i=1}^{n-1}\operatorname{\textsf{E}}[M_{i}]$
$\displaystyle\leq\sum_{i=1}^{n-1}\frac{\log(i+1)-\log\tilde{P}_{e}(i)+\log\frac{1-p}{p}}{1-H(p)}$
$\displaystyle\leq\frac{\log(n!)+n\log n+n\log\log
n+n\log\frac{1-p}{p}}{1-H(p)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{2n\log n+O(n\log\log
n)}{1-H(p)},$

where (a) follows by Stirling’s approximation. The proof is completed by
realizing that $\lim_{n\to\infty}\frac{n\log
n}{\operatorname{\textsf{E}}[M]}\geq\frac{1-H(p)}{2}$.

###  III-C Comparison with Existing Algorithms

As discussed in the introduction, the algorithms proposed in [3, 4, 5, 6, 7]
all achieve vanishing rates when evaluated in our framework, while the
algorithm proposed in [8] achieves some non-vanishing rate. In [34], Ren and
Liu proposed an algorithm based on the algorithm in [8] that applies to a more
general noise setting when the observation noise $p_{ij}$ for the comparison
of elements $i$ and $j$ is unknown and could be different for different pairs.
However, their proposed algorithm does not improve the query complexity upon
the algorithm in [8] in the original noise setting when the observation noise
$p$ is fixed and known. Therefore, in this section, we focus on the noisy
sorting algorithm proposed in [8]. We obtain the sorting rate of this
algorithm with a refined error analysis. It is shown (see Fig. 1) that the two
proposed noisy sorting codes described in Section III-A and Section III-B both
strictly improve the sorting rate of the algorithm in [8] for all
$p\in(0,1/2)$.

_Noisy Searching using Comparison Trees:_ Consider the noisy searching problem
outlined in Section II-C. The algorithm in [8] defines a binary tree $T$,
where each node in the tree is labeled with a pair of indices $(i,j)$
representing interval $(\tilde{\theta}_{i},\tilde{\theta}_{j}]$, for $0\leq
i<j\leq n$. The root of the tree is labeled with the index pair $(0,n)$. The
rest of the tree is defined recursively as follows: For each node with a label
$(i,j)$ such that $j-i\geq 2$, two children are generated such that the left
child has the label $(i,\lceil\frac{i+j}{2}\rceil)$, and the right child has
the label $(\lceil\frac{i+j}{2}\rceil,j)$. By the above process, we build a
binary tree $T$ that contains $n$ leaves, each representing one of the
possible intervals in $\\{I_{i}\\}$ (recall the definition of sub-intervals
$I_{i}=(\tilde{\theta}_{i-1},\tilde{\theta}_{i}]$ for $i\in[n-1]$, and
$I_{n}=(\tilde{\theta}_{n-1},\tilde{\theta}_{n})$). To allow searching with
noisy queries, the algorithm defines an extended tree $T^{*}$ by attaching a
length-$s$ chain of nodes to each leaf node in $T$ having the same label as
the leaf node. Fig. 2 shows an illustration of the trees $T$ and $T^{*}$ for
the case when $n=6$ and $s=3$.

$(0,6)$
---
$(0,3)$
---
$(3,6)$
---
$(0,2)$
---
$(2,3)$
---
$(3,5)$
---
$(5,6)$
---
$(0,1)$
---
$(1,2)$
---
$(2,3)$
---
$(0,1)$
---
$(0,1)$
---
$(0,1)$
---
$(1,2)$
---
$(1,2)$
---
$(1,2)$
---
$(2,3)$
---
$(2,3)$
---
$(3,4)$
---
$(3,4)$
---
$(3,4)$
---
$(3,4)$
---
$(4,5)$
---
$(4,5)$
---
$(4,5)$
---
$(4,5)$
---
$(5,6)$
---
$(5,6)$
---
$(5,6)$
---
Figure 2: Illustration of the extended tree $T^{*}$ for $n=6$ and $s=3$.

The algorithm performs a random walk on the nodes of $T^{*}$ starting from the
root node, as follows. Let $(i,j)$ be the label of the current node reached by
the random walk. First, we verify if $\theta$ belongs to the corresponding
interval. To do this, the queries $\tilde{\theta}_{i}$ and
$\tilde{\theta}_{j}$ are submitted $\beta$ times each, for some integer
$\beta$ taken as input to the algorithm. If the majority vote of the responses
indicates that either $\tilde{\theta}\leq\tilde{\theta}_{i}$ or
$\tilde{\theta}>\tilde{\theta}_{j}$, we claim that the verification fails and
the algorithm steps back to the parent node of $(i,j)$. In case the
verification succeeds, if $j-i\geq 2$, i.e., the current node is neither a
leaf node in $T$ nor an extended node, the algorithm checks if
$\tilde{\theta}$ is larger or smaller than the median element of the current
interval. This is done by submitting, $\beta$ times, the query
$\tilde{\theta}_{\lceil\frac{i+j}{2}\rceil}$. The algorithm proceeds in the
direction indicated by the majority vote of the responses. Otherwise when
$j-i=1$, the algorithm proceeds to the only child of the current node.
Algorithm 6 shows the pseudocode of this comparison tree algorithm.

Input : Ordered sequence $(\tilde{\theta}_{1},\ldots,\tilde{\theta}_{n-1})$,
target $\tilde{\theta}$, number of queries $\tilde{m}$, integer $\beta$.

Output : Index $\hat{l}$ of the sub-interval containing $\tilde{\theta}$.

1 $i\leftarrow 0$, $j\leftarrow n$,
$s\leftarrow\lceil\frac{\tilde{m}}{3\beta}\rceil$.

2 Construct $T^{*}$ as described in text.

3 for  _$k=1,\ldots,s$_ do

4 $b\leftarrow 0$.

// failure bit

5 if  _$i\neq 0$_ then

6 Submit query $\tilde{U}_{k}\leftarrow\tilde{\theta}_{i}$ for $\beta$ times.

7 Get noisy responses $\tilde{Y}_{1},\ldots,\tilde{Y}_{\beta}$.

8 if  _$\sum_{i=1}^{\beta}\tilde{Y}_{i} <\lceil\frac{\beta}{2}\rceil$_ then
$b\leftarrow 1$.

9 if  _$j\neq n$_ then

10 Submit query $\tilde{U}_{k}\leftarrow\tilde{\theta}_{j}$ for $\beta$ times.

11 Get noisy responses $\tilde{Y}_{1},\ldots,\tilde{Y}_{\beta}$.

12 if  _$\sum_{i=1}^{\beta}\tilde{Y}_{i}\geq\lceil\frac{\beta}{2}\rceil$_ then
$b\leftarrow 1$.

13 if  _$b=1$_ then

14 $(i,j)\leftarrow\texttt{parent}\big{(}(i,j)\big{)}$.

15 else if  _$j-i\geq 2$_ then

16 Submit query
$\tilde{U}_{k}\leftarrow\tilde{\theta}_{\lceil\frac{i+j}{2}\rceil}$ for
$\beta$ times.

17 Get noisy responses $\tilde{Y}_{1},\ldots,\tilde{Y}_{\beta}$.

18 if  _$\sum_{i=1}^{\beta}\tilde{Y}_{i} <\lceil\frac{\beta}{2}\rceil$_ then

19 $(i,j)\leftarrow\texttt{left\\_child}\big{(}(i,j)\big{)}$.

20 else

21 $(i,j)\leftarrow\texttt{right\\_child}\big{(}(i,j)\big{)}$.

22 else

// extended chain

23 $(i,j)\leftarrow\texttt{child}\big{(}(i,j)\big{)}$.

end for

24$\hat{l}\leftarrow i+1$.

25 return _$\hat{l}$_

Algorithm 6 Noisy Searching Tree NST Algorithm

_Insertion Sort with Noisy Comparison Tree:_ As before, a noisy sorting code
can be constructed by integrating the noisy searching algorithm (Algorithm 6)
as part of an insertion-based algorithm, as discussed in Section III-A. This
can be done by simply replacing Line 2 of Algorithm 3 by the following
function call,

$\hat{l}\leftarrow\texttt{NST}\big{(}(\theta_{\sigma(1)},\ldots,\theta_{\sigma(i-1)}),\>\theta_{n-i},\>\left\lfloor\tfrac{m}{n-1}\right\rfloor,\>\beta\big{)},$

where $\beta$ is a parameter inputted to the noisy sorting algorithm, and
corresponds to the number of query repetitions done at each node of the tree.

_Rate of Algorithm:_ In this section, we apply a refined error analysis to the
algorithm described above. The achievable rate of the algorithm is stated in
the following theorem.

######  Theorem 6 (Refined rate of the algorithm in [8]).

For $0<\delta<\frac{1}{2}$, sorting rate $R$ is achievable if

$\displaystyle 3\beta(p,\delta)R$ $\displaystyle<1-2\delta,$ (15)
$\displaystyle 3\beta(p,\delta)R$ $\displaystyle<\frac{1}{\ln
2}D\left(\frac{1}{2}-\frac{3\beta(p,\delta)R}{2}\bigg{|}\bigg{|}\delta\right),$
(16)

where $\beta(p,\delta)$ is the smallest integer $\beta$ such that

$1-\left(1-\sum_{i=\lceil\beta/2\rceil}^{\beta}\binom{\beta}{i}p^{i}(1-p)^{\beta-i}\right)^{3}\leq\delta.$

This rate is achieved using the algorithm in Section [8] with parameters
$\beta=\beta(p,\delta)$ and $m=\lceil\frac{n\log n}{R}\rceil$.

To prove Theorem 6, we first consider the noisy searching problem and upper
bound the probability of error of Algorithm 6 in the following Lemma.

######  Lemma 3.

Let $0<\delta<\frac{1}{2}$ and positive integer $\tilde{m}$ be such that

$\frac{1}{2}-\frac{\log n}{2s}>\delta,$ (17)

where $s=\lceil\frac{\tilde{m}}{3\beta(p,\delta)}\rceil$ and $\beta(p,\delta)$
is the smallest integer $\beta$ such that

$1-\left(1-\sum_{i=\lceil\beta/2\rceil}^{\beta}\binom{\beta}{i}p^{i}(1-p)^{\beta-i}\right)^{3}\leq\delta.$

Then Algorithm 6 with input parameters $\beta=\beta(p,\delta)$ and $\tilde{m}$
outputs the correct interval for $\tilde{\theta}$ with probability at least

$1-\exp\left(-sD\left(\frac{1}{2}-\frac{\log
n}{2s}\bigg{|}\bigg{|}\delta\right)\right).$

###### Proof of Lemma 3.

Let $u$ be the leaf node in the extended tree $T^{*}$ that represents the
correct interval for $\tilde{\theta}$. Orient all the edges in $T^{*}$ towards
the node $u$. By the definition of a tree, such an orientation is unique.
Moreover, for each node $v\neq u$ in the tree, there exists exactly one edge
connected to $v$ that is directed outwards from $v$, while all other edges
connected to $v$ are directed towards $v$.

Recall that in Algorithm 6, a repetition code of length $\beta$ is used for
each comparison. At each node $v\neq u$ in $T^{*}$, at most three comparisons
are made (two for verification of the interval and one for comparing with the
median element). A sufficient condition for the random walk to go along the
outgoing edge from $v$ is that all comparisons yield correct responses. Thus,
the probability of this event is at least

$(1-\tau)^{3}$

where
$\tau\triangleq\sum_{i=\lceil\beta/2\rceil}^{\beta}\binom{\beta}{i}p^{i}(1-p)^{\beta-i}$.
Thus, by taking $\beta=\beta(p,\delta)$, we are guaranteed that this
probability is at least $1-\delta$.

Now, to bound the probability of error of Algorithm 6, let $S_{\mathrm{f}}$
denote the number of forward steps that go along the direction of an edge, and
let $S_{\mathrm{b}}$ denote the number of backward steps that go against the
direction of an edge. A sufficient condition for the algorithm to output the
correct interval is that $S_{\mathrm{f}}-S_{\mathrm{b}}\geq\lceil\log
n\rceil$, since the tree $T$ has depth $\lceil\log n\rceil$. This condition
can be equivalently written as $S_{\mathrm{f}}-S_{\mathrm{b}}\geq\log n$ since
$S_{\mathrm{f}}$ and $S_{\mathrm{b}}$ are integers. Since
$S_{\mathrm{f}}+S_{\mathrm{b}}=s=\lceil\frac{\tilde{m}}{3\beta(p,\delta)}\rceil$,
it follows that the probability of error of Algorithm 6 can be upper bounded
by

$\displaystyle\operatorname{\textsf{P}}\left\\{S_{\mathrm{f}}-S_{\mathrm{b}}<\log
n\right\\}$
$\displaystyle\leq\operatorname{\textsf{P}}\left\\{S_{\mathrm{b}}>\tfrac{s-\log
n}{2}\right\\}$
$\displaystyle\leq\operatorname{\textsf{P}}\left\\{\mathrm{Binom}\left(s,\delta\right)>\tfrac{s-\log
n}{2}\right\\}$ $\displaystyle\leq\exp\left(-sD\left(\frac{1}{2}-\frac{\log
n}{2s}\bigg{|}\bigg{|}\delta\right)\right),$

where the last inequality follows by condition (17) and the Chernoff bound
[35, Theorem 1]. ∎

###### Proof of Theorem 6.

Let $m=\lceil\frac{n\log n}{R}\rceil$ be the total number of queries for noisy
sorting, where the sorting rate $R$ satisfies conditions (15) and (16) of
Theorem 6. Let $\tilde{m}=\lfloor\frac{m}{n-1}\rfloor$ be the number of
queries used in each insertion, and let
$s=\lceil\frac{\tilde{m}}{3\beta(p,\delta)}\rceil$.444For simplicity of
presentation, we assume in the proof that $\frac{\log n}{R}$ is an integer.
Let $P_{e}(i)$ denote the probability of error of the $i$th insertion. In
order to upper bound $P_{e}(i)$ using Lemma 3, we first verify the condition
of Lemma 3. Notice that

$s=\left\lceil\frac{\tilde{m}}{3\beta(p,\delta)}\right\rceil=\left\lceil\frac{\lfloor\frac{\lceil\frac{n\log
n}{R}\rceil}{n-1}\rfloor}{3\beta(p,\delta)}\right\rceil\geq\frac{\log
n}{3R\beta(p,\delta)}.$

It follows that

$\frac{1}{2}-\frac{\log
n}{2s}\geq\frac{1}{2}-\frac{3R\beta(p,\delta)}{2}>\delta,$

where the last inequality holds since $R$ satisfies condition (15). Therefore,
the error probability of the noisy sorting algorithm of [8] can be bounded by

$\displaystyle\operatorname{\textsf{P}}\\{\hat{\Pi}\neq\pi\\}\leq\sum_{i=2}^{n}P_{e}(i)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{i=2}^{n}\exp\left\\{-\frac{\tilde{m}}{3\beta(p,\delta)}D\left(\frac{1}{2}-\frac{3\beta(p,\delta)\log
i}{2\tilde{m}}\Big{|}\Big{|}\delta\right)\right\\}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}n\exp\left\\{-\frac{\tilde{m}}{3\beta(p,\delta)}D\left(\frac{1}{2}-\frac{3\beta(p,\delta)\log
n}{2\tilde{m}}\Big{|}\Big{|}\delta\right)\right\\}$
$\displaystyle\leq\exp\left\\{\log n\left(\ln
2-\frac{1}{3R\beta(p,\delta)}D\left(\frac{1}{2}-\frac{3R\beta(p,\delta)}{2}\Big{|}\Big{|}\delta\right)\right)\right\\}$

where $(a)$ follows by applying Lemma 3, and $(b)$ follows since $D(x||y)$ is
an increasing function in $x$ whenever $0<y<x<\frac{1}{2}$. Hence,
$\operatorname{\textsf{P}}\\{\hat{\Pi}=\pi\\}$ goes to zero as
$n\rightarrow\infty$ if the sorting rate $R$ satisfies condition (16). ∎

Note that the analysis in [8] considers the special case of
$\delta=\frac{1}{3}$, whereas our analysis considers any $0<\delta<1/2$ such
that (15) and (16) hold. It turns out that such a generalization of the
analysis significantly improves the achievable sorting rates of the algorithm.
Finally, we point out that the achievable sorting rates shown in Fig. 1 for
the existing algorithm correspond to the best choice of $\delta$ for each $p$.

##  IV Proof of Converse Results

In this section, we prove the two converse results Theorem 3 and Theorem 4. A
key building block of both proofs is a converse theorem on the _channel coding
with feedback problem_ in [30]. In the following, we first formally define the
channel coding with feedback problem and state the converse result.

###  IV-A Coding Problem on a BSC$(p)$ Channel with Noiseless Feedback

Suppose the transmitter has a set of $n$ possible messages
$\\{\psi_{1},\ldots,\psi_{n}\\}$ and he wants to transmit one of them to the
receiver through a BSC$(p)$ channel. At each iteration $k$, the transmitter
sends a bit $\tilde{X}_{k}$ and the receiver receives
$\tilde{Y}_{k}=\tilde{X}_{k}\oplus\tilde{Z}_{k}$, where
$\tilde{Z}_{k}\sim\mathrm{Bern}(p)$ is a sequence of i.i.d. random variables.
Furthermore, after receiving each transmitted bit, the receiver can
communicate with the transmitter through a noiseless discrete feedback
channel. The alphabet of the feedback channel is assumed to be arbitrarily
large but finite. A variable-length transmission scheme is specified as
follows: To start the transmission, the receiver sends a signal
$\tilde{W}_{0}$ to the transmitter through the feedback channel. At iteration
$k$, the bit $\tilde{X}_{k}$ sent by the transmitter is decided by a causal
protocol
$\tilde{X}_{k}=\tilde{f}_{k}(\Psi^{*},\tilde{X}_{1}^{k-1},\tilde{W}_{0}^{k-1})$,
where $\Psi^{*}$ is the true message transmitter wants to send. Then the
receiver receives $\tilde{Y}_{k}=\tilde{X}_{k}\oplus\tilde{Z}_{k}$ and
generates
$\tilde{\lambda}_{k}=\tilde{g}_{k}(\tilde{Y}_{1}^{k},\tilde{W}_{0}^{k-1})$,
where $\tilde{\lambda}_{k}\in[n+1]$. In the case when
$\tilde{\lambda}_{k}\in[n]$, the transmission is terminated and the receiver
outputs $\hat{\Psi}=\psi_{\tilde{\lambda}_{k}}$. Otherwise, the receiver
decides to continue transmission, and generate
$\tilde{W}_{k}=\tilde{h}_{k}(\tilde{Y}_{1}^{k},\tilde{W}_{0}^{k-1})$ to send
to the transmitter through the feedback channel. The total number of bits sent
by the transmitter is denoted as $\tilde{M}$. The performance of a
transmission scheme is evaluated by two quantities. The probability of error
$\tilde{P}_{e}\triangleq\operatorname{\textsf{P}}(\hat{\Psi}\neq\Psi^{*})$ and
the expected number of queries $\operatorname{\textsf{E}}[\tilde{M}]$.
Assuming the true message $\Psi^{*}$ has a uniform prior over the message set
$\\{\psi_{1},\ldots,\psi_{n}\\}$, we have the following converse bound for any
transmission scheme.

######  Theorem 7 (Theorem 1 in [30]).

For any variable-length transmission scheme on the $\mathrm{BSC}(p)$ channel
with feedback, the expected number of bits sent by the transmitter satisfies
that

$\operatorname{\textsf{E}}[\tilde{M}]>\frac{\log
n}{1-H(p)}+\frac{\log\frac{1}{\tilde{P}_{e}}}{D(p||1-p)}-\frac{\log\log\frac{n}{\tilde{P}_{e}}}{D(p||1-p)}-\frac{\tilde{P}_{e}\log
n}{1-H(p)}+O(1).$ (18)

In the following two sections, we use Theorem 7 to prove Theorem 3 and Theorem
4 by connecting the noisy sorting problem and the noisy searching problem to
the channel coding with feedback problem.

###  IV-B Converse: Variable-length Noisy Sorting Codes

To prove Theorem 3, we show that for each noisy sorting code that sorts $n$
elements with $M$ queries and average case error probability
$\operatorname{\textsf{P}}(\hat{\Pi}\neq\Pi)=P_{e}$ under the uniform prior
for the true permutation $\Pi$, it induces a coding scheme for the channel
coding with feedback problem with $n!$ possible input messages. The induced
coding scheme also has $M$ number of bits sent and error probability $P_{e}$.
Then Theorem 3 follows from Theorem 7.

Firstly, we view the $n!$ message $\psi_{1},\ldots,\psi_{n!}$ as the $n!$
possible permutations $\pi_{1},\ldots,\pi_{n!}$ on $n$ elements in an
arbitrary order. Let $\pi^{*}$ denote the permutation corresponding to the
true message $\Psi^{*}$. For a noisy sorting code with query strategy
$\\{f_{k}\\}_{k=1}^{\infty}$ associated with stopping time $M$ and estimator
$\hat{\Pi}=\hat{\pi}(\tilde{Y}^{M},U^{M},V^{M})$, the induced coding scheme is
described as follows: To start the transmission, the receiver sends
$\tilde{W}_{0}=f_{1}=(U_{1},V_{1})$, which is the first pair of elements
compared by the noisy sorting code, to the transmitter. For the simplicity of
notation, let $(U_{k},V_{k})\triangleq(\theta_{k_{1}},\theta_{k_{2}})$. The at
each iteration $k=1,2,\ldots,$ the transmitter sends
$\tilde{X}_{k}=\mathbbm{1}_{\pi^{*}(k_{1})<\pi^{*}(k_{2})}$, which is a
function of the message $\pi^{*}$ and $(U_{k},V_{k})$, through the BSC$(p)$
channel. The receiver receives the channel output
$\tilde{Y}_{k}=\tilde{X}_{k}\oplus\tilde{Z}_{k}$ and generates
$\tilde{\lambda}_{k}$ based on the stopping time $M$ of the noisy sorting
code. If the stopping criteria is not satisfied, then $\tilde{\lambda}_{k}$ is
set to $n!+1$, i.e., the transmission continues and the receiver generates the
feedback symbol
$\tilde{W}_{k}=f_{k+1}(\tilde{Y}_{1}^{k},\tilde{W}_{0}^{k-1})=(U_{k+1},V_{k+1})$
to send to the transmitter. Otherwise, the transmission terminates and
$\tilde{\lambda}_{k}$ is set to the message corresponding to the permutation
$\hat{\Pi}=\hat{\pi}(\tilde{Y}^{k},U^{k},V^{k})$, where $\hat{\Pi}$ is the
estimator of the noisy sorting code. In other words, at each iteration, the
receiver sends the queried pair of the noisy sorting code to the transmitter
through the noiseless feedback channel, and the transmitter sends the bit
indicating the comparison between the queried pair through the BSC$(p)$
channel. Upon receiving the bit, the receiver decides to output an estimation
or continue transmission based on the stopping criteria of the noisy sorting
code. One can check that the induced coding scheme has the same error
probability $P_{e}$ and the number of transmitted bits is exactly $M$. By
Theorem 7, we have that the expected number of queries made by the noisy
sorting code satisfies that

$\operatorname{\textsf{E}}[M]>\frac{\log(n!)}{1-H(p)}+\frac{\log\frac{1}{P_{e}}}{D(p||1-p)}-\frac{\log\log\frac{n!}{P_{e}}}{D(p||1-p)}-\frac{P_{e}\log(n!)}{1-H(p)}+O(1),$
(19)

and Theorem 3 follows because the worst case error probability of a noisy
sorting code is always at least the average case error probability.

###  IV-C Converse: Insertion-based Noisy Sorting Codes

The key components of the insertion-based noisy sorting codes are the noisy
searching algorithms applied at each insertion step. Thus, to show the
converse for the family of insertion-based noisy sorting codes, we first state
and prove a converse result for all noisy searching algorithms. Recall the
setup for the noisy searching problem introduced in Section II-C. We have the
following lower bound for the expected number of queries.

######  Theorem 8.

Suppose the true position $l^{*}$ follows a uniform prior. For the clarity of
notation, we use $L^{*}$ to denote the random true position. For any variable-
length noisy searching scheme with error probability
$P_{e}\triangleq\operatorname{\textsf{P}}(\hat{L}\neq L^{*})$, its expected
number of queries $\operatorname{\textsf{E}}[\tilde{M}]$ satisfies that

$\operatorname{\textsf{E}}[\tilde{M}]>\frac{\log
n}{1-H(p)}+\frac{\log\frac{1}{\tilde{P}_{e}}}{D(p||1-p)}-\frac{\log\log\frac{n}{\tilde{P}_{e}}}{D(p||1-p)}-\frac{\tilde{P}_{e}\log
n}{1-H(p)}+O(1).$ (20)

###### Proof of Theorem 8.

Similarly to the proof of Theorem 3, we prove Theorem 8 by drawing a
connection to the channel coding with feedback problem.

To see the connection, we first observe that the $n$ possible messages
$\psi_{1},\ldots,\psi_{n}$ in the channel coding problem can be viewed as the
$n$ sub-intervals $I_{1},\ldots,I_{n}$ respectively. Denote the mid point of
the sub-interval corresponding to the true message $\Psi^{*}$ by $\theta^{*}$.
For a noisy searching scheme with query strategy
$\\{\tilde{f}_{k}\\}_{k=1}^{\infty}$ associated with stopping time $\tilde{M}$
and estimator $\hat{L}=\hat{l}(\tilde{Y}^{\tilde{M}},\tilde{U}^{\tilde{M}})$,
the induced coding scheme is described as follows: To start the transmission,
the receiver sends $\tilde{W}_{0}=\tilde{f}_{1}=\tilde{U}_{1}$, which is the
first query in the query scheme, to the transmitter. Then at each iteration
$k=1,2,\ldots$, the transmitter sends
$\tilde{X}_{k}=\mathbbm{1}_{\\{\tilde{U}_{k}<\theta^{*}\\}}$ through the
BSC$(p)$ channel. The receiver receives the channel output
$\tilde{Y}_{k}=\tilde{X}_{k}\oplus\tilde{Z}_{k}$ and generates
$\tilde{\lambda}_{k}$ based on the stopping time $\tilde{M}$ of the noisy
searching algorithm. If the stopping criteria is not satisfied, then
$\tilde{\lambda}_{k}$ is set to $n+1$, i.e., the transmission continues and
the receiver generates the feedback symbol
$\tilde{W}_{k}=\tilde{f}_{k+1}(\tilde{Y}_{1}^{k},\tilde{W}_{0}^{k-1})=\tilde{U}_{k+1}$
to send to the transmitter. Otherwise, the transmission terminates and
$\tilde{\lambda}_{k}$ is set to message
$\hat{L}=\hat{l}(\tilde{Y}^{k},\tilde{U}^{k})$, where $\hat{L}$ is the
estimator of the noisy searching algorithm. In other words, at each iteration,
the receiver sends the query point to the transmitter through the feedback
channel, and the transmitter sends the bit indicating whether the message is
on the left of the query point through the BSC$(p)$ channel. Upon receiving
the bit, the receiver decides to output an estimation or continue transmission
based on the stopping rule. One can check that the induced coding scheme has
exactly the same error probability $\tilde{P}_{e}$ and the number of bits sent
is exactly $\tilde{M}$. Since each noisy searching algorithm induces a coding
scheme, Theorem 8 follows from Theorem 7. ∎

With Theorem 8, we are now ready to prove Theorem 4. For $i\in[n-1]$, let
$\mathcal{E}_{i}$ denote the event that estimation at $i$th insertion step is
incorrect. We assume without loss of generality that $\pi$ follows a uniform
prior. For the clarity of notation, we use $\Pi$ to denote the uniformly
distributed true permutation. By the similar argument as in the proof of
Theorem 1, we know that

$\operatorname{\textsf{P}}(\hat{\Pi}=\Pi)=\prod_{k=1}^{n-1}\left(1-\operatorname{\textsf{P}}(\mathcal{E}_{k}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\cap_{i=1}^{k-1}\mathcal{E}_{i}^{c})\right),$

where
$\operatorname{\textsf{P}}(\mathcal{E}_{i}|\cap_{k=1}^{i-1}\mathcal{E}_{k}^{c})$
represents the error probability of the noisy searching algorithm called at
$i$th insertion step given a uniform prior for the correct position. Notice
that

$\displaystyle\operatorname{\textsf{P}}(\hat{\Pi}=\Pi)$
$\displaystyle=\prod_{k=1}^{n-1}\left(1-\operatorname{\textsf{P}}(\mathcal{E}_{k}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\cap_{i=1}^{k-1}\mathcal{E}_{i}^{c})\right)$
$\displaystyle=\exp{\left(\sum_{i=1}^{n-1}\ln\left(1-\operatorname{\textsf{P}}(\mathcal{E}_{i}|\cap_{k=1}^{i-1}\mathcal{E}_{k}^{c})\right)\right)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\exp{\left(-\sum_{i=1}^{n-1}\operatorname{\textsf{P}}(\mathcal{E}_{i}|\cap_{k=1}^{i-1}\mathcal{E}_{k}^{c})\right)},$

where (a) follows because $\ln x\leq x-1$. We can see that a necessary
condition for
$\lim_{n\rightarrow\infty}\operatorname{\textsf{P}}(\hat{\Pi}=\Pi)=1$ is that
at least $n-w$ terms in
$\operatorname{\textsf{P}}(\mathcal{E}_{1}),\operatorname{\textsf{P}}(\mathcal{E}_{2}|\mathcal{E}_{1}^{c}),\ldots,\operatorname{\textsf{P}}(\mathcal{E}_{n-1}|\mathcal{E}_{1}^{c}\cap\cdots\cap\mathcal{E}_{n-2}^{c})$
are $o(1/n)$, where $w=o(n)$. Assume otherwise, there exists $w=\Omega(n)$
terms that are $\Omega(1/n)$. Then the sum of these $w$ terms must be in the
order $\Omega(1)$, which implies that
$\lim_{n\rightarrow\infty}\operatorname{\textsf{P}}(\hat{\Pi}=\Pi)\neq 1$. We
denote the iteration indices of these $n-w$ terms by $j_{1},\ldots,j_{n-w}$.
In other words, for every $j\in\\{j_{1},\ldots,j_{n-w}\\}$, we have
$\operatorname{\textsf{P}}(\mathcal{E}_{j}|\mathcal{E}_{1}^{c}\cap\cdots\cap\mathcal{E}_{j-1}^{c})=o(1/n)$.

Let $M_{k}$ denote the number of queries in the $k$th insertion step. By
Theorem 8, we have that for every $l\in[n-w]$,

$\operatorname{\textsf{E}}[M_{j_{l}}]>\frac{\log(j_{l}+1)}{1-H(p)}+\frac{\log
n}{D(p||1-p)}+O(\log\log n).$ (21)

Furthermore, we can lower bound the total expected number of queries in the
noisy sorting code as

$\displaystyle\operatorname{\textsf{E}}[M]$
$\displaystyle\geq\operatorname{\textsf{E}}\left[\sum_{l=1}^{n-w}M_{j_{l}}\right]$
$\displaystyle=\sum_{l=1}^{n-w}\operatorname{\textsf{E}}[M_{j_{l}}]$
$\displaystyle>\sum_{l=1}^{n-w}\left[\frac{\log(j_{l}+1)}{1-H(p)}+\frac{\log
n}{D(p||1-p)}+O(\log\log n)\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\sum_{k=1}^{n-w}\left[\frac{\log(k+1)}{1-H(p)}+\frac{\log
n}{D(p||1-p)}+O(\log\log n)\right]$
$\displaystyle=\frac{\log(n-w+1)!}{1-H(p)}+\frac{(n-w)\log
n}{D(p||1-p)}+O(n\log\log n)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}n\log
n\left(\frac{1}{1-H(p)}+\frac{1}{D(p||1-p)}\right)+O(n\log n),$ (22)

where (a) follows by the fact that $j_{1},\ldots,j_{n-w}$ are distinct
indices, so $\sum_{l=1}^{n-w}\log(j_{l}+1)\geq\sum_{k=1}^{n-w}\log(k+1)$, and
(b) follows by Stirling’s approximation and the fact that $w=o(n)$. By
equation (22), we have $R_{\mathrm{ins}}=\frac{n\log
n}{\operatorname{\textsf{E}}[M]}<\frac{1}{\frac{1}{1-H(p)}+\frac{1}{D(p||1-p)}}$,
which completes the proof.

##  V Concluding Remarks

In this paper, we proposed a new framework to study the noisy sorting problem.
We introduced the noisy sorting capacity, which is defined as the maximum
ratio $\frac{n\log n}{\operatorname{\textsf{E}}[M]}$ such that the ranking of
the $n$ elements can be correctly found with probability going to one by an
algorithm with expected number of queries $\operatorname{\textsf{E}}[M]$. We
provide two lower bounds on the noisy sorting capacity, which strictly improve
the best-known achievable rate. We also provide two converse results for the
problem, one for general variable-length noisy sorting algorithms and the
other for the family of insertion-based noisy sorting algorithms.

There are many intriguing open problems that remain. Firstly, we can see from
Figure 1 that there exists a gap between our converse and achievability
results. Therefore, a tighter characterization of the noisy sorting capacity
is of interest. We conjecture that an algorithm based on the idea of posterior
matching in [28] could potentially achieve a higher sorting rate. The main
idea of the algorithm is as follows. The algorithm assumes a uniform prior of
the space $\mathcal{S}_{n}$ of all possible $n!$ permutations. At each
iteration, the algorithm considers each of the $\binom{n}{2}$ possible pair of
items for comparison. Notice that each pair of items
$\\{\theta_{i},\theta_{j}\\}$ naturally partitions the space $\mathcal{S}_{n}$
into two equal-sized parts where the first part includes all the permutations
such that $\theta_{i}<\theta_{j}$ and the other part includes all the
permutations such that $\theta_{i}>\theta_{j}$. The algorithms computes the
sum of posterior over these two parts for each pair and chooses the pair with
smallest difference of the two sums as the query to be made at this iteration.
The iteration is then completed by updating all the posteriors by the response
of the query. The algorithms terminates when at least one of the posterior
reaches a preset threshold. According to empirical experiments, the algorithms
achieves vanishing error probability with less queries than the proposed
algorithms in this paper. Secondly, we have considered the noisy sorting
capacity under the assumption that the error probability for each query is
fixed and known. This leads to a natural extension of the error model where
the error probability between each pair could be distinct and unknown.
Finally, we considered adaptive noisy sorting codes in this working. Another
open questions is how does the capacity change when the noisy sorting codes
are restricted to non-adaptive ones.

##  Appendix A Proof of Theorem 5

The proof is first presented in [29] written in Russian. We include it here
for completeness. Recall that $\tilde{M}$ is the first time step such that
there exists $i\in[n]$ with $Z_{\tilde{M}}(i)\geq-\log P_{e}$. Let
$\tilde{M}^{\prime}$ denote the first time step such that
$Z_{\tilde{M}^{\prime}}(l^{*})\geq-\log P_{e}$. By our definitions, we know
that $\tilde{M}\leq\tilde{M}^{\prime}$. So it satisfies to give an upper bound
for $\operatorname{\textsf{E}}[\tilde{M}^{\prime}]$.

Recall that we defined $Z_{k}(l^{*})=\log\frac{q_{k}(l^{*})}{1-q_{k}(l^{*})}$,
which characterizes the ratio between the posterior of the correct interval
and that of the sum of the rest. For the simplicity of notation, we define
$\bar{q}_{k}\triangleq(q_{k}(1),\ldots,q_{k}(n))$. In the following, we
consider the _expected improvement_
$\operatorname{\textsf{E}}[Z_{k}(l^{*})\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\bar{q}_{k-1}]-Z_{k-1}(l^{*})$
for each time step $t$. We prove that

$\operatorname{\textsf{E}}[Z_{k}(l^{*})\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\bar{q}_{k-1}]-Z_{k-1}(l^{*})\geq
1-H(p)$

at each time step $k$. Then the proof of the theorem is completed by a
martingale argument. To prove the lower bound for the expected improvement, we
fix a positive integer $k\geq 1$. Recall that we defined the median of the
posterior $j(k)$ as

$\sum_{i=1}^{j(k)-1}q_{k-1}(i)\leq\frac{1}{2}\quad\text{and}\quad\sum_{i=1}^{j(k)}q_{k-1}(i)>\frac{1}{2}.$

We consider three different cases: (1) $l^{*}=j(k)$, (2) $l^{*}<j(k)$, and (3)
$l^{*}>j(k)$. Let $h_{1}$, $h_{2}$ and $h_{3}$ denote the expected improvement
for these three cases respectively. By taking the randomness over the choice
of the query point and the noise in the observation model, one can compute

$\displaystyle h_{1}$
$\displaystyle=1-H(p)-\pi_{1}\rho\left(\frac{\tau_{1}(k-1)-q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}\right)-\pi_{2}\rho\left(\frac{\tau_{2}(k-1)-q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}\right);$
(23) $\displaystyle h_{2}$
$\displaystyle=1-H(p)-\pi_{1}\rho\left(\frac{\tau_{1}(k-1)-q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}\right)-\pi_{2}\rho\left(-\frac{\tau_{2}(k-1)+q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}\right);$
(24) $\displaystyle h_{3}$
$\displaystyle=1-H(p)-\pi_{1}\rho\left(-\frac{\tau_{1}(k-1)+q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}\right)-\pi_{2}\rho\left(\frac{\tau_{2}(k-1)-q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}\right),$
(25)

where, recall,

$\pi_{1}\triangleq\frac{\rho(\tau_{2}(k))-\rho(-\tau_{2}(k))}{\rho(\tau_{1}(k))-\rho(-\tau_{1}(k))+\rho(\tau_{2}(k))-\rho(-\tau_{2}(k))}\quad\text{and}\quad\pi_{2}\triangleq
1-\pi_{1}$

with

$\rho(x)\triangleq(1-p)\log(1+(1-2p)x)+p\log(1-(1-2p)x)$

for $|x|\leq 1$, and

$\tau_{1}(k)\triangleq
2\sum_{i=j(k)}^{n}q_{k-1}(i)-1\quad\text{and}\quad\tau_{2}(k)\triangleq
2\sum_{i=1}^{j(k)}q_{k-1}(i)-1.$

By taking derivative, we know that $\rho(x)$ is non-decreasing for $-1\leq
x\leq 1$.

Consider first cases (2) and (3). Notice the fact that $\frac{y-x}{1-x}\leq y$
and $-\frac{y+x}{1-x}\leq-y$ for any $0<x<1$ and $-1\leq y\leq 1$. We have

$\displaystyle h_{2}$ $\displaystyle\geq
1-H(p)-\pi_{1}\rho\left(\tau_{1}(k-1)\right)-\pi_{2}\rho\left(-\tau_{2}(k-1)\right);$
(26) $\displaystyle h_{3}$ $\displaystyle\geq
1-H(p)-\pi_{1}\rho\left(-\tau_{1}(k-1)\right)-\pi_{2}\rho\left(\tau_{2}(k-1)\right).$
(27)

Recall that we set
$\pi_{1}=\frac{\rho(\tau_{2})-\rho(-\tau_{2})}{\rho(\tau_{1})-\rho(-\tau_{1})+\rho(\tau_{2})-\rho(-\tau_{2})}$,
which implies that

$\pi_{1}\rho\left(\tau_{1}(k-1)\right)+\pi_{2}\rho\left(-\tau_{2}(k-1)\right)=\pi_{1}\rho\left(-\tau_{1}(k-1)\right)+\pi_{2}\rho\left(\tau_{2}(k-1)\right).$
(28)

By equations (26), (27) and (28), we have

$\displaystyle h_{2}$ $\displaystyle\geq
1-H(p)-\frac{1}{2}(\pi_{1}\rho\left(\tau_{1}(k-1)\right)+\pi_{2}\rho\left(-\tau_{2}(k-1)\right)+\pi_{1}\rho\left(-\tau_{1}(k-1)\right)+\pi_{2}\rho\left(\tau_{2}(k-1)\right))$
$\displaystyle\geq
1-H(p)-\frac{1}{2}(\pi_{1}(\rho(\tau_{1}(k-1))+\rho(-\tau_{1}(k-1)))+\pi_{2}(\rho(\tau_{2}(k-1))+\rho(-\tau_{2}(k-1))))$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}1-H(p)-\frac{1}{2}\left(\max_{-1\leq
x\leq 1}\rho(x)+\rho(-x)\right),$

where (a) follows because $\pi_{1}+\pi_{2}=1$. But
$\frac{1}{2}\left(\max_{-1\leq x\leq 1}\rho(x)+\rho(-x)\right)\leq 0$, because

$\displaystyle\rho(x)+\rho(-x)$
$\displaystyle=(1-p)\log(1+(1-2p)x)+p\log(1-(1-2p)x)+(1-p)\log(1-(1-2p)x)+p\log(1+(1-2p)x)$
$\displaystyle=\log(1+(1-2p)x)+\log(1-(1-2p)x)$
$\displaystyle=\log(1-(1-2p)^{2}x^{2})\leq 0.$

This shows that $h_{2}\geq 1-H(p)$, and we can get $h_{3}\geq 1-H(p)$ in the
same way.

Now, we consider case (1). Using equation (23) and the fact that
$\tau_{1}+\tau_{2}=2q_{k-1}(l^{*})$, we have

$h_{1}=1-H(p)-\pi_{1}\rho\left(\frac{\tau_{1}(k-1)-q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}\right)-\pi_{2}\rho\left(-\frac{\tau_{1}(k-1)-q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}\right).$
(29)

For simplicity, we denote the term
$\frac{\tau_{1}(k-1)-q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}$ by $T$. Here we want
to show that

$\pi_{1}\rho(T)+\pi_{2}\rho(-T)\leq 0.$ (30)

Towards that goal, we consider two sub-cases $\tau_{1}\leq\tau_{2}$ and
$\tau_{1}\geq\tau_{2}$. In the first case, we have $\pi_{1}\geq\pi_{2}$,
because $\rho(x)-\rho(-x)$ is non-decreasing for $0<x<1$. Let
$\pi_{1}=\frac{1}{2}+\epsilon$ and $\pi_{2}=\frac{1}{2}-\epsilon$ for some
positive constant $\epsilon$. Moreover, we have $T\leq 0$ because
$\tau_{1}(k-1)+\tau_{2}(k-1)=2q_{k-1}(l^{*})$ and $\tau_{1}\leq\tau_{2}$. It
follows that

$\displaystyle\pi_{1}\rho(T)+\pi_{2}\rho(-T)$
$\displaystyle=(\tfrac{1}{2}+\epsilon)((1-p)\log(1+(1-2p)T)+p\log(1-(1-2p)T))$
$\displaystyle+(\tfrac{1}{2}-\epsilon)((1-p)\log(1-(1-2p)T)+p\log(1+(1-2p)T))$
$\displaystyle=\tfrac{1}{2}\log(1-(1-2p)^{2}T^{2})+\epsilon((1-2p)\log(1+(1-2p)T)+(2p-1)\log(1-(1-2p)T)).$

Our claim (30) holds because $\log(1-(1-2p)^{2}T^{2})\leq 0$,
$(1-2p)\log(1+(1-2p)T)\leq 0$ and $(2p-1)\log(1-(1-2p)T)\leq 0$. The proof for
the second sub-case follows similarly.

Therefore, in all three cases, we can lower bound the expected improvement
$\operatorname{\textsf{E}}[Z_{k}(l^{*})\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\bar{q}_{k-1}]-Z_{k-1}(l^{*})\geq
1-H(p)$. Now, we state a lemma to relate the expected improvement to the total
expected number of queries.

######  Lemma 4.

Let $X_{0},X_{1},X_{2},\ldots$ be a discrete-time submartingale with respect
to $\sigma$-algebra filtration
$\mathcal{F}_{0},\mathcal{F}_{1},\mathcal{F}_{2},\ldots$. For
$k=0,1,2,\ldots$, suppose

$\operatorname{\textsf{E}}[X_{k+1}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\mathcal{F}_{k}]\geq
X_{k}+C$ (31)

for some $C>0$, and

$|X_{k+1}-X_{k}|\leq A$ (32)

for some finite constant $A$. Define a stopping-time $\tau$ by
$\tau\triangleq\min\\{k:X_{k}\geq B\\}$. Then the expectation of $\tau$
satisfies inequality

$\operatorname{\textsf{E}}[\tau\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\mathcal{F}_{0}]\leq\frac{B-X_{0}+A}{C}.$
(33)

We first use Lemma 4 to complete the proof of Theorem 5 and then present the
proof of the Lemma at the end of the appendix. In our case, we have that
$\operatorname{\textsf{E}}[Z_{k}(l^{*})\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\bar{q}_{k-1}]-Z_{k-1}(l^{*})\geq
1-H(p)$. Clearly, $Z_{0}(l^{*}),Z_{1}(l^{*}),Z_{2}(l^{*}),\ldots$ form a
submartingale with respect to the sequence of $\sigma$-algebras induced by
$\bar{q}_{0},\bar{q}_{1},\bar{q}_{2},\ldots$. To apply Lemma 4, we still need
to bound the difference $|Z_{k-1}(l^{*})-Z_{k}(l^{*})|$ for each $k$. We claim
that

$|Z_{k-1}(l^{*})-Z_{k}(l^{*})|\leq\log\frac{1-p}{p}.$

To see the claim, we consider two different cases: (1) $l^{*}>j^{*}(k)$ and
(2) $l^{*}\leq j^{*}(k)$, where $j^{*}(k)$ is randomly chosen from $j(k)-1$
and $j(k)$ as in (7).

In the first case, recall that $\tau(k)=2\sum_{i=1}^{j^{*}(k)}q_{k-1}(i)-1.$
By the update rule, we know that the posterior of the correct interval
increases when $\tilde{Y}_{k}=1$, and it is updated as
$q_{k}(l^{*})=q_{k-1}(l^{*})\frac{2(1-p)}{1+(2p-1)\tau(k)}$. When
$\tilde{Y}_{k}=0$, the posterior of the correct interval decreases, and it is
updated as $q_{k}(l^{*})=q_{k-1}(l^{*})\frac{2p}{1+(1-2p)\tau(k)}$. If
$q_{k}(l^{*})=q_{k-1}(l^{*})\frac{2(1-p)}{1+(2p-1)\tau(k)}$, we have

$\displaystyle Z_{k}(l^{*})-Z_{k-1}(l^{*})-\log\frac{1-p}{p}$
$\displaystyle=\log\frac{q_{k-1}(l^{*})\frac{2(1-p)}{1+(2p-1)\tau(k)}}{1-q_{k-1}(l^{*})\frac{2(1-p)}{1+(2p-1)\tau(k)}}-\log\frac{q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}-\log\frac{1-p}{p}$
$\displaystyle=\log\frac{(1-q_{k-1}(l^{*}))\frac{2(1-p)}{1+(2p-1)\tau(k)}}{1-q_{k-1}(l^{*})\frac{2(1-p)}{1+(2p-1)\tau(k)}}-\log\frac{1-p}{p}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\log\frac{2(1-p)}{1+(2p-1)\tau(k)}-\log\frac{1-p}{p}$
$\displaystyle=\log\frac{2p}{1+(2p-1)\tau(k)}$
$\displaystyle=\log\left(1+\frac{2p-(1+(2p-1)\tau(k))}{1+(2p-1)\tau(k)}\right)$
$\displaystyle=\log\left(1+\frac{(2p-1)(1-\tau(k))}{1+(2p-1)\tau(k)}\right)\stackrel{{\scriptstyle(b)}}{{\leq}}0,$
(34)

where (a) follows since $\frac{y-x}{1-x}\leq y$ for any $0<x<1$ and $y\leq 1$,
and (b) follows since $2p-1<0$ and $1-\tau(k)>0$. Similarly, if
$q_{k}(l^{*})=q_{k-1}(l^{*})\frac{2p}{1+(1-2p)\tau(k)}$, we have

$\displaystyle Z_{k}(l^{*})-Z_{k-1}(l^{*})+\log\frac{1-p}{p}$
$\displaystyle=\log\frac{q_{k-1}(l^{*})\frac{2p}{1+(1-2p)\tau(k)}}{1-q_{k-1}(l^{*})\frac{2p}{1+(1-2p)\tau(k)}}-\log\frac{q_{k-1}(l^{*})}{1-q_{k-1}(l^{*})}+\log\frac{1-p}{p}$
$\displaystyle=\log\frac{(1-q_{k-1}(l^{*}))\frac{2p}{1+(1-2p)\tau(k)}}{1-q_{k-1}(l^{*})\frac{2p}{1+(1-2p)\tau(k)}}+\log\frac{1-p}{p}$
$\displaystyle=\log\frac{(1-q_{k-1}(l^{*}))\frac{2(1-p)}{1+(1-2p)\tau(k)}}{1-q_{k-1}(l^{*})\frac{2p}{1+(1-2p)\tau(k)}}$
$\displaystyle=\log\left(\frac{2(1-p)-2(1-p)q_{k-1}(l^{*})}{1+(1-2p)\tau(k)-2pq_{k-1}(l^{*})}\right)$
$\displaystyle=\log\left(1+\frac{2(1-p)-2(1-p)q_{k-1}(l^{*})-1-(1-2p)\tau(k)+2pq_{k-1}(l^{*})}{1+(1-2p)\tau(k)-2pq_{k-1}(l^{*})}\right)$
$\displaystyle=\log\left(1+\frac{(1-2p)(1-\tau(k)-2q_{k-1}(l^{*}))}{1+(1-2p)\tau(k)-2pq_{k-1}(l^{*})}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}0,$ (35)

where (a) follows since $1-\tau(k)=2\sum_{i=j^{*}(k)+1}^{n}q_{k-1}(i)$ and
$l^{*}\geq j^{*}(k)+1$. By (34) and (35), we know that
$|Z_{k}(l^{*})-Z_{k-1}(l^{*})|\leq\log\frac{1-p}{p}$ in this case. The proof
for case (2) goes in the same way as case (1) and it is skipped.

Because $Z_{0}(1)=\cdots=Z_{0}(n)=\log\frac{1}{n-1}$, by Lemma 4, we have

$\displaystyle\operatorname{\textsf{E}}[\tilde{M}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}l^{*}=i]$
$\displaystyle\leq\frac{-\log
P_{e}-\log\frac{1}{n-1}+\log\frac{1-p}{p}}{1-H(p)}$
$\displaystyle\leq\frac{-\log P_{e}+\log n+\log\frac{1-p}{p}}{1-H(p)},$

which completes the proof.

###### Proof of Lemma 4.

For $k=0,1,\ldots$, let $Y_{k}\triangleq X_{k}-kC$. We claim that
$Y_{0},Y_{1},\ldots,$ is also a submartingale with respect to $\sigma$-algebra
filtration $\mathcal{F}_{0},\mathcal{F}_{1},\ldots$. This is because

$\displaystyle\operatorname{\textsf{E}}[Y_{k+1}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\mathcal{F}_{k}]$
$\displaystyle=\operatorname{\textsf{E}}\left[X_{k+1}-kC-C\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\mathcal{F}_{k}\right]$
$\displaystyle\geq X_{k}+C-kC-C$ $\displaystyle=Y_{k}.$

Because $\tau$ is a stopping time with respect to
$\mathcal{F}_{0},\mathcal{F}_{1},\ldots$, by optional stopping time theorem
(see for example [36]), we know that $Y_{k\wedge\tau}$ also forms a
submartingale, where $\wedge$ denotes the minimum operator. We have that

$\displaystyle Y_{0}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\lim_{k\rightarrow\infty}\operatorname{\textsf{E}}[Y_{k\wedge\tau}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\mathcal{F}_{0}]$
$\displaystyle=\lim_{k\rightarrow\infty}\operatorname{\textsf{E}}[X_{k\wedge\tau}-C(k\wedge\tau)\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\mathcal{F}_{0}]$
$\displaystyle\leq\lim_{k\rightarrow\infty}\operatorname{\textsf{E}}[X_{k\wedge\tau}\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\mathcal{F}_{0}]-C\operatorname{\textsf{E}}[\tau\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\mathcal{F}_{0}]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}B+A-C\operatorname{\textsf{E}}[\tau\mathchoice{\,|\,}{\mspace{2.0mu}|\mspace{2.0mu}}{|}{|}\mathcal{F}_{0}],$

where (a) follows because $Y_{k\wedge\tau}$ forms a submartingale, and (b)
follows because $X_{(k\wedge\tau)-1}\leq B$ and
$|X_{(k\wedge\tau)-1}-X_{k\wedge\tau}|\leq A$. The proof is then completed by
realizing that $Y_{0}=X_{0}$. ∎

## Acknowledgment

The authors would like to thank Young-Han Kim and Wei Yu for stimulating
discussions on the problem. This work was supported in part by the NSERC
Discovery Grant No. RGPIN-2019-05448 and in part by the NSERC Collaborative
Research and Development Grant CRDPJ 54367619. Banghua Zhu was supported by
NSF Grants IIS-1901252 and CCF-190949.

## References

  * [1] D. E. Knuth, _The art of computer programming_. Pearson Education, 1997, vol. 3.
  * [2] R. Ash, _Information Theory_ , ser. Dover books on advanced mathematics. Dover Publications, 1990.
  * [3] S. Mohajer, C. Suh, and A. Elmahdy, “Active learning for top-$k$ rank aggregation from noisy comparisons,” in _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ser. ICML’17. JMLR.org, 2017, p. 2488–2497.
  * [4] M. Falahatgar, A. Orlitsky, V. Pichapati, and A. T. Suresh, “Maximum selection and ranking under noisy comparisons,” in _Proceedings of the 34th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, D. Precup and Y. W. Teh, Eds., vol. 70. PMLR, 06–11 Aug 2017, pp. 1088–1096. [Online]. Available: https://proceedings.mlr.press/v70/falahatgar17a.html
  * [5] N. B. Shah and M. J. Wainwright, “Simple, robust and optimal ranking from pairwise comparisons,” _J. Mach. Learn. Res._ , vol. 18, no. 199, pp. 1–38, 2018. [Online]. Available: http://jmlr.org/papers/v18/16-206.html
  * [6] R. Heckel, N. B. Shah, K. Ramchandran, and M. J. Wainwright, “Active ranking from pairwise comparisons and when parametric assumptions do not help,” _Ann. Stat._ , vol. 47, no. 6, pp. 3099 – 3126, 2019. [Online]. Available: https://doi.org/10.1214/18-AOS1772
  * [7] A. Agarwal, S. Agarwal, S. Assadi, and S. Khanna, “Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons,” in _Proceedings of the 2017 Conference on Learning Theory_ , ser. Proceedings of Machine Learning Research, S. Kale and O. Shamir, Eds., vol. 65. PMLR, 07–10 Jul 2017, pp. 39–75. [Online]. Available: https://proceedings.mlr.press/v65/agarwal17c.html
  * [8] U. Feige, P. Raghavan, D. Peleg, and E. Upfal, “Computing with noisy information,” _SIAM J. Comput._ , vol. 23, no. 5, pp. 1001–1018, 1994.
  * [9] N. Ailon, M. Charikar, and A. Newman, “Aggregating inconsistent information: Ranking and clustering,” _J. ACM_ , vol. 55, no. 5, nov 2008. [Online]. Available: https://doi.org/10.1145/1411509.1411513
  * [10] M. Braverman and E. Mossel, “Sorting from noisy information,” 2009. [Online]. Available: https://arxiv.org/abs/0910.1191
  * [11] N. Ailon, “Active learning ranking from pairwise preferences with almost optimal query complexity,” in _Advances in Neural Information Processing Systems_ , J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, Eds., vol. 24. Curran Associates, Inc., 2011. [Online]. Available: https://proceedings.neurips.cc/paper/2011/file/81448138f5f163ccdba4acc69819f280-Paper.pdf
  * [12] S. Negahban, S. Oh, and D. Shah, “Iterative ranking from pair-wise comparisons,” in _Advances in Neural Information Processing Systems_ , F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, Eds., vol. 25. Curran Associates, Inc., 2012\.
  * [13] F. Wauthier, M. Jordan, and N. Jojic, “Efficient ranking from pairwise comparisons,” in _Proceedings of the 30th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, S. Dasgupta and D. McAllester, Eds., vol. 28, no. 3. Atlanta, Georgia, USA: PMLR, 17–19 Jun 2013, pp. 109–117. [Online]. Available: https://proceedings.mlr.press/v28/wauthier13.html
  * [14] A. Rajkumar and S. Agarwal, “A statistical convergence perspective of algorithms for rank aggregation from pairwise data,” in _Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32_ , ser. ICML’14. JMLR.org, 2014, p. I–118–I–126.
  * [15] N. B. Shah, S. Balakrishnan, A. Guntuboyina, and M. J. Wainwright, “Stochastically transitive models for pairwise comparisons: Statistical and computational issues,” in _Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48_ , ser. ICML’16. JMLR.org, 2016, p. 11–20.
  * [16] C. Mao, J. Weed, and P. Rigollet, “Minimax rates and efficient algorithms for noisy sorting,” in _Proceedings of Algorithmic Learning Theory_ , ser. Proceedings of Machine Learning Research, F. Janoos, M. Mohri, and K. Sridharan, Eds., vol. 83. PMLR, 07–09 Apr 2018, pp. 821–847. [Online]. Available: https://proceedings.mlr.press/v83/mao18a.html
  * [17] R. A. Bradley and M. E. Terry, “Rank analysis of incomplete block designs: I. the method of paired comparisons,” _Biometrika_ , vol. 39, no. 3/4, pp. 324–345, 1952. [Online]. Available: http://www.jstor.org/stable/2334029
  * [18] M. Ajtai, V. Feldman, A. Hassidim, and J. Nelson, “Sorting and selection with imprecise comparisons,” in _ACM Trans. Algorithms_ , vol. 12, 07 2009, pp. 37–48.
  * [19] Y. Chen and C. Suh, “Spectral mle: Top-k rank aggregation from pairwise comparisons,” in _Proceedings of the 32nd International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, F. Bach and D. Blei, Eds., vol. 37. Lille, France: PMLR, 07–09 Jul 2015, pp. 371–380. [Online]. Available: https://proceedings.mlr.press/v37/chena15.html
  * [20] X. Chen, Y. Chen, and X. Li, “Asymptotically optimal sequential design for rank aggregation,” _Math. Oper. Res._ , 10 2017.
  * [21] W. Ren, J. Liu, and N. B. Shroff, “Pac ranking from pairwise and listwise queries: Lower bounds and upper bounds,” 2018. [Online]. Available: https://arxiv.org/abs/1806.02970
  * [22] K. G. Jamieson and R. D. Nowak, “Active ranking using pairwise comparisons,” in _Proceedings of the 24th International Conference on Neural Information Processing Systems_ , ser. NIPS’11. Red Hook, NY, USA: Curran Associates Inc., 2011, p. 2240–2248.
  * [23] N. Ailon, R. Begleiter, and E. Ezra, “A new active learning scheme with applications to learning to rank from pairwise preferences,” 2011. [Online]. Available: https://arxiv.org/abs/1110.2136v1
  * [24] A. Rényi, “On a problem of information theory,” _MTA Mat. Kut. Int. Kozl. B_ , vol. 6, no. MR143666, pp. 505–516, 1961.
  * [25] S. Ulam, _Adventures of a mathematician_. New York, NY, USA: Charles Scribner’s Sons, 1976.
  * [26] E. R. Berlekamp, “Block coding with noiseless feedback,” Ph.D. Thesis, MIT, Cambridge, MA, USA, 1964.
  * [27] M. Horstein, “Sequential transmission using noiseless feedback,” _IEEE Trans. Inf. Theory_ , vol. 9, no. 3, pp. 136–143, 1963.
  * [28] O. Shayevitz and M. Feder, “Optimal feedback communication via posterior matching,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 3, pp. 1186–1222, 2011\.
  * [29] M. V. Burnashev and K. Zigangirov, “An interval estimation problem for controlled observations,” _Problemy Peredachi Informatsii_ , vol. 10, no. 3, pp. 51–61, 1974.
  * [30] M. V. Burnashev, “Data transmission over a discrete channel with feedback. random transmission time,” _Problemy Peredachi Informatsii_ , vol. 12, no. 4, pp. 10–30, 1976.
  * [31] M. Ben-Or and A. Hassidim, “The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well),” in _2008 49th Annual IEEE Symposium on Foundations of Computer Science_ , 2008, pp. 221–230.
  * [32] M. Naghshvar, T. Javidi, and M. Wigger, “Extrinsic jensen–shannon divergence: Applications to variable-length coding,” _IEEE Transactions on Information Theory_ , vol. 61, no. 4, pp. 2148–2164, 2015.
  * [33] D. H. Lehmer, “Teaching combinatorial tricks to a computer,” 1960.
  * [34] W. Ren, J. K. Liu, and N. Shroff, “On sample complexity upper and lower bounds for exact ranking from noisy comparisons,” _Advances in Neural Information Processing Systems_ , vol. 32, pp. 10 014–10 024, 2019.
  * [35] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” _Journal of the American Statistical Association_ , vol. 58, no. 301, pp. 13–30, 1963.
  * [36] G. Grimmett and D. Stirzaker, _Probability and random processes_. Oxford university press, 2020.