# On the achromatic number of the Cartesian product of two complete graphs

Mirko Horňák
Institute of Mathematics, P.J. Šafárik University
Jesenná 5, 040 01 Košice, Slovakia
E-mail address<EMAIL_ADDRESS>
###### Abstract

A vertex colouring $f:V(G)\to C$ of a graph $G$ is complete if for any
$c_{1},c_{2}\in C$ with $c_{1}\neq c_{2}$ there are in $G$ adjacent vertices
$v_{1},v_{2}$ such that $f(v_{1})=c_{1}$ and $f(v_{2})=c_{2}$. The achromatic
number of $G$ is the maximum number $\mathrm{achr}(G)$ of colours in a proper
complete vertex colouring of $G$. Let $G_{1}\square G_{2}$ denote the
Cartesian product of graphs $G_{1}$ and $G_{2}$. In the paper
$\mathrm{achr}(K_{r^{2}+r+1}\square K_{q})$ is determined for an infinite
number of $q$s provided that $r$ is a finite projective plane order.

Keywords: graph, complete vertex colouring, achromatic number, Cartesian
product, finite projective plane Mathematics Subject Classification: 05C15,
51E20

##  1 Introduction

Consider a finite simple graph $G$ and a finite set of colours $C$. A vertex
colouring $f:V(G)\to C$ is complete if for any pair $c_{1},c_{2}$ of distinct
colours in $C$ one can find a pair $v_{1},v_{2}$ of adjacent vertices in $G$
such that $f(v_{i})=c_{i}$, $i=1,2$. Obviously, if $f$ is proper (adjacent
vertices receive distinct colours) and $|C|$ is minimum possible (i.e.,
$|C|=\chi(G)$, the chromatic number of $G$), then $f$ is necessarily complete.

The achromatic number of $G$, in symbols $\mathrm{achr}(G)$, is the maximum
number of colours in a proper complete vertex colouring of $G$. This invariant
was introduced by Harary, Hedetniemi, and Prins in [6]. The problem of
determining the achromatic number is NP-complete even for trees, see Cairnie
and Edwards [2]. So, it is not surprising that exact results concerning the
achromatic number are quite rare. A comprehensive bibliography for the
achromatic number is maintained by Edwards [5].

Some attention was paid to the achromatic number of graphs created by graph
operations. Hell and Miller in [7] analysed $\mathrm{achr}(G_{1}\times G_{2})$
where $G_{1}\times G_{2}$ is the categorical product of graphs $G_{1}$ and
$G_{2}$ (in the paper we use the notation taken from the monograph Imrich and
Klavžar [14]).

The Cartesian product $G_{1}\square G_{2}$ of graphs $G_{1}$ and $G_{2}$ is
the graph with $V(G_{1}\square G_{2})=V(G_{1})\times V(G_{2})$, in which
$(x_{1},y_{1})$ is joined by an edge to $(x_{2},y_{2})$ if and only if either
$x_{1}=x_{2}$ and $\\{y_{1},y_{2}\\}\in E(G_{2})$ or $\\{x_{1},x_{2}\\}\in
E(G_{1})$ and $y_{1}=y_{2}$.

A motivation for the study of $\mathrm{achr}(K_{p}\square K_{q})$ comes from
the observation by Chiang and Fu [3] stating that the assumption
$\mathrm{achr}(G_{1})=p$ and $\mathrm{achr}(G_{2})=q$ implies
$\mathrm{achr}(G_{1}\square G_{2})\geq\mathrm{achr}(K_{p}\square K_{q})$.

Evidently, since the graphs $K_{p}\square K_{q}$ and $K_{q}\square K_{p}$ are
isomorphic to each other, when looking for $\mathrm{achr}(K_{p}\square K_{q})$
we may suppose without loss of generality that $p\leq q$.

Let $p,q$ be integers. In the paper we work with integer intervals that are
denoted as follows:

$[p,q]=\\{z\in\mathbb{Z}:p\leq z\leq
q\\},\qquad[p,\infty)=\\{z\in\mathbb{Z}:p\leq z\\}.$

For a finite set $A$ and $k\in[0,|A|]$ the set $\binom{A}{k}$ consists of all
$k$-element subsets of $A$.

The element in the $i$th row and the $j$th column of a matrix $M$ is presented
as $(M)_{i,j}$. The submatrix of $M$ corresponding to the $i$th row of $M$ is
denoted by $R_{i}(M)$.

The value of $\mathrm{achr}(K_{p}\square K_{q})$ is known for each pair
$(p,q)$ satisfying $1\leq p\leq 6$ and $p\leq q$. Besides the trivial case
$p=1$ ($K_{1}\square K_{q}$ is isomorphic to $K_{q}$, hence
$\mathrm{achr}(K_{1}\square K_{q})=q$), the case $p\in\\{2,3,4\\}$ was settled
by Horňák and Puntigán [13] (for $p\in\\{2,3\\}$ the result was rediscovered
in [3]), the case $p=5$ by Horňák and Pčola [11], [12], and the case $p=6$ by
Horňák [8], [9], [10]. The achromatic number of $K_{p}\square K_{q}$, where
$r$ is an odd order of a finite projective plane, was determined in Chiang and
Fu [4] (for $r=3$ see already Bouchet [1]). Some values of
$\mathrm{achr}(K_{p}\square K_{q})$ with $p\leq 6$ will be used in Section 4.
They are summarised here:

######  Theorem 1.

$1.$ If $q\in[3,\infty)$, then $\mathrm{achr}(K_{2}\square K_{q})=q+1$.

$2.$ If $q\in[4,\infty)$, then $\mathrm{achr}(K_{3}\square
K_{q})=\left\lfloor\frac{3q}{2}\right\rfloor$.

$3.$ If $q\in[25,\infty)$, then $\mathrm{achr}(K_{4}\square
K_{q})=\left\lfloor\frac{5q}{3}\right\rfloor$.

$4.$ If $q\in[43,\infty)$, then $\mathrm{achr}(K_{5}\square
K_{q})=\left\lfloor\frac{9q}{5}\right\rfloor$.

$5.$ If $q\in[41,\infty)$ and $q\equiv 1\pmod{2}$, then
$\mathrm{achr}(K_{6}\square K_{q})=2q+3$.

$6.$ If $q\in[42,\infty)$ and $q\equiv 0\pmod{2}$, then
$\mathrm{achr}(K_{6}\square K_{q})=2q+4$.

What follows is (up to the notation) a natural and somehow standard (cf. [13])
approach to dealing with a proper complete vertex colouring of the Cartesian
product of two complete graphs.

Suppose that $p,q\in[1,\infty)$, $V(K_{s})=[1,s]$ for
$s\in\\{p\\}\cup\\{q\\}$, $C$ is a finite set and $f:V(K_{p}\square K_{q})\to
C$ is a proper complete vertex colouring. Let $M(f)$ be the $p\times q$ matrix
with $(M(f))_{i,j}=f(i,j)$. The fact that $f$ is proper means that each row of
$M(f)$ consists of $q$ distinct colours of $C$, and similarly each column of
$M(f)$ consists of $p$ distinct colours of $C$. Because of the completeness of
$f$ for any $\\{c_{1},c_{2}\\}\in\binom{C}{2}$ there is a line (a row or a
column) of $M(f)$ that contains both $c_{1}$ and $c_{2}$. Let
$\mathcal{M}(p,q,C)$ be the set of all $p\times q$ matrices $M$ with elements
from $C$ such that $M$ has all above properties of the matrix $M(f)$.

Conversely, let $M\in\mathcal{M}(p,q,C)$. It is obvious to see that the
colouring $f_{M}:V(K_{p}\square K_{q})\to C$ defined by $f_{M}(i,j)=(M)_{i,j}$
is a proper complete vertex colouring of the graph $K_{p}\square K_{q}$. Thus,
we have just proved

######  Proposition 2.

If $p,q\in[1,\infty)$ and $C$ is a finite set, then the following statements
are equivalent:

$1.$ There is a proper complete vertex colouring of the graph $K_{p}\square
K_{q}$ using as colours elements of $C$.

$2.$ $\mathcal{M}(p,q,C)\neq\emptyset$.

We shall need a subset $\mathcal{M}^{*}(p,q,C)$ of $\mathcal{M}(p,q,C)$
consisting of matrices $M$, which satisfy the additional condition that for
any $\\{c_{1},c_{2}\\}\in\binom{C}{2}$ there is a row (not merely a line) of
$M$ with both $c_{1},c_{2}$.

Let $r\in[2,\infty)$. A finite projective plane of order $r$ is a pair
$(P,\mathcal{L})$, where $P$ is a finite set of elements called points, and
$\mathcal{L}$ is a set of subsets of $P$ called lines, such that the following
axioms are fulfilled:

$A_{1}.$ If $p_{1},p_{2}\in P$, $p_{1}\neq p_{2}$, there is exactly one line
$L(p_{1},p_{2})\in\mathcal{L}$ such that $\\{p_{1},p_{2}\\}\subseteq
L(p_{1},p_{2})$.

$A_{2}.$ If $L_{1},L_{2}\in\mathcal{L}$, $L_{1}\neq L_{2}$, then $P_{1}\cap
P_{2}\neq\emptyset$.

$A_{3}.$ There are four distinct points
$\tilde{p}_{1},\tilde{p}_{2},\tilde{p}_{3},\tilde{p}_{4}\in P$ determining six
distinct lines, i.e.,
$|\bigcup_{\\{i,j\\}\in\binom{[1,4]}{2}}\\{L(\tilde{p}_{i},\tilde{p}_{j})\\}|=6$.

$A_{4}.$ There is $\tilde{L}\in\mathcal{L}$ such that $|\tilde{L}|=r+1$.

It is well known that points and lines of a finite projective plane
$(P,\mathcal{L})$ of order $r$ have the following basic properties:

$B_{1}.$ If $L_{1},L_{2}\in\mathcal{L}$, $L_{1}\neq L_{2}$, then $|L_{1}\cap
L_{2}|=1$.

$B_{2}.$ If $L\in\mathcal{L}$, then $|L|=r+1$.

$B_{3}.$ If $p\in P$, then $|\\{L\in\mathcal{L}:p\in L\\}|=r+1$.

$B_{4}.$ $|P|=r^{2}+r+1$.

$B_{5}.$ $|\mathcal{L}|=r^{2}+r+1$.

Given $r\in[2,\infty)$, to determine whether there exists a finite projective
plane of order $r$ (i.e., whether $r$ is a finite projective plane order), is
in general a notoriously hard problem of finite combinatorics. All positive
results available so far are restricted to $r=q^{e}$, where $q$ is a prime
number and $e\in[1,\infty)$.

##  2 Some auxiliary results

The following lemma is well known, cf. [13]. We include its proof here for a
better readability of the paper.

######  Lemma 3.

If $p\in[1,\infty)$, $q\in[p,\infty)$, $C$ is a set of size
$a=\mathrm{achr}(K_{p}\square K_{q})$, $M\in\mathcal{M}(p,q,C)$ and $l$ is the
smallest of frequencies of elements in $M$, then the following hold:

$1.$ $l\leq p$;

$2.$ $l\leq\left\lfloor\frac{pq}{a}\right\rfloor$;

$3.$ $a\leq l(p+q-l-1)+1$.

###### Proof.

1\. The vertex colouring $f_{M}$ is proper, hence each element of $C$ appears
in any row of $M$ at most once.

2\. The set of colour classes of $f_{M}$ is a partition of the set
$V(K_{p}\square K_{q})$ of cardinality $pq$ so that $pq\leq al$ and
$l\leq\left\lfloor\frac{pq}{a}\right\rfloor$.

3\. Let $\gamma\in C$ be a colour of $f_{M}$ of frequency $l$. A matrix
created from $M$ by permuting the rows and the columns of $M$ evidently
belongs to $\mathcal{M}(p,q,C)$. Therefore, we may suppose without loss of
generality that $(M)_{i,i}=\gamma$ for every $i\in[1,l]$. The completeness of
$f_{M}$ means that the neighbourhood $N$ of the colour class
$\\{(i,i):i\in[1,l]\\}$ corresponding to $\gamma$ contains a vertex of each
colour in $C\setminus\\{\gamma\\}$. Since $|N|=ql+(p-l)l-l\leq|C|-1$, we have
$a=|C|\leq l(p+q-l-1)+1$. ∎

######  Lemma 4.

If $p\in[3,\infty)$, $q\in[2p-1,\infty)$, $a=\mathrm{achr}(K_{p}\square
K_{q})$, $C$ is an $a$-element colour set,
$\mathcal{M}^{*}(p,q,C)\neq\emptyset$, and $d\notin C$ for a colour $d$, then
$\mathcal{M}^{*}(p,q+1,C\cup\\{d\\})\neq\emptyset$ and
$\mathrm{achr}(K_{p}\square K_{q+1})\geq\mathrm{achr}(K_{p}\square K_{q})+1$.

###### Proof.

For $M\in\mathcal{M}(p,q,C)$ we consider the block matrix $M^{+}=(MJ_{p}(d))$,
in which $J_{p}(d)$ is the $p\times 1$ matrix with all elements equal to $d$.

For each $i\in[1,p]$ we define recurrently an $i\times(q+1)$ matrix
$M_{i}^{+}$. First, we put $M_{1}^{+}=M^{+}$. For $i\in[2,p]$, if the matrix
$M_{i-1}^{+}$ is already defined, we construct a matrix $M_{i}^{+}$ from the
block matrix $M_{i}=\begin{pmatrix}M_{i-1}^{+}\\\ R_{i}(M^{+})\end{pmatrix}$
by interchanging elements $(M_{i})_{i,q+1}=d$ and $(M_{i})_{i,j}$ for a
suitable $j\in[1,q]$ in such a way that lines of $M_{i}^{+}$ contain pairwise
distinct elements (so that $f_{M_{i}^{+}}$ is a proper vertex colouring of
$K_{i}\square K_{q+1}$).

To see that this is doable realise that there are two reasons why an integer
from $[1,q]$ cannot be chosen as $j$. The first one is that the $j$th column
of $M_{i-1}^{+}$ contains $d$, and the second one is that $(M_{i})_{i,j}$ is
an element of the $(q+1)$th column of $M_{i-1}^{+}$. Therefore, the total
number of integers from $[1,q]$, which are not a valid choice for $j$, is
$2(i-1)$, and $M_{i}^{+}$ can be created in a required way, since
$q-2(i-1)\geq q-2(p-1)=q+2-2p\geq 1$.

Thus $f_{M_{p}^{+}}$ is a proper vertex colouring of $K_{p}\square K_{q+1}$.
As $M\in\mathcal{M}^{*}(p,q,C)$, having in mind the construction of
$M_{p}^{+}$ and the fact that the colour $d$ is present in all $p$ rows of the
matrix $M_{p}^{+}$, it is clear that the colouring $f_{M_{p}^{+}}$ is
complete, too. Therefore,
$M_{p}^{+}\in\mathcal{M}^{*}(p,q+1,C\cup\\{d\\})\neq\emptyset$ and
$\mathrm{achr}(K_{p}\square
K_{q+1})\geq|C\cup\\{d\\}|=a+1=\mathrm{achr}(K_{p}\square K_{q})+1$. ∎

######  Lemma 5.

If $r$ is a finite projective plane order and $s\in[r+1,\infty)$, then

$1.$ there exists a colour set $C$ of size $(r^{2}+r+1)s$ such that
$\mathcal{M}^{*}(r^{2}+r+1,$ $(r+1)s,C)\neq\emptyset$;

$2.$ $\mathrm{achr}(K_{r^{2}+r+1}\square K_{(r+1)s})\geq(r^{2}+r+1)s$.

###### Proof.

1\. Let $(P,\mathcal{L})$ be a finite projective plane of order $r$ with
$P=\\{p_{k}:k\in[1,r^{2}+r+1]\\}$ and
$\mathcal{L}=\\{L_{k}:k\in[1,r^{2}+r+1]\\}$ (see the properties $B_{4}$,
$B_{5}$). Consider an $(r^{2}+r+1)\times(r+1)$ matrix $M$ with elements from
$P$ such that, for each $i\in[1,r^{2}+r+1]$, $L_{i}$ is equal to the set
$\\{(M)_{i,j}:j\in[1,r+1]\\}$ of elements in the $i$th row of $M$.

Given $k\in[1,r^{2}+r+1]$ and $l\in[1,r+1]$, replace the $l$th copy of $p_{k}$
in $M$ with $p_{k}^{l}$ (by $B_{3}$, $p_{k}$ appears in $r+1$ distinct lines
of $\mathcal{L}$, and so in $r+1$ distinct rows of $M$); we suppose that the
ordering of copies of $p_{k}$ in $M$ is “inherited” from the lexicographical
ordering of pairs $(i,j)\in[1,r^{2}+r+1]\times[1,r+1]$ with $(M)_{i,j}=p_{k}$.
Denote by $M^{\prime}$ the $(r^{2}+r+1)\times(r+1)$ matrix obtained from $M$
if each point of $P$ in $M$ is replaced in the above way with $p_{k}^{l}$,
where $(k,l)\in[1,r^{2}+r+1]\times[1,r+1]$.

For $z\in\mathbb{Z}$ let$(z)_{s}$ be the unique $t\in[1,s]$ satisfying
$t\equiv z\pmod{s}$. Further, let $M_{k}^{s}$ be the $(r+1)\times s$ matrix
with elements from $\\{p_{k}\\}\times[1,s]$ defined by
$(M_{k}^{s})_{i,j}=(p_{k},(i+j-1)_{s})$, i.e.,

$M_{k}^{s}=\begin{pmatrix}(p_{k},1)&(p_{k},2)&\dots&(p_{k},s-1)&(p_{k},s)\\\
(p_{k},2)&(p_{k},3)&\dots&(p_{k},s)&(p_{k},1)\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
(p_{k},r)&(p_{k},r+1)&\dots&(p_{k},r-2)&(p_{k},r-1)\\\
(p_{k},r+1)&(p_{k},r+2)&\dots&(p_{k},r-1)&(p_{k},r)\end{pmatrix}$

Finally, let $M_{s}$ be the $(r^{2}+r+1)\times(r+1)s$ matrix obtained from
$M^{\prime}$ if each $p_{k}^{l}$ with $(k,l)\in[1,r^{2}+r+1]\times[1,r+1]$ is
replaced with the $1\times s$ block matrix equal to the $l$th row submatrix of
$M_{k}^{s}$.

Let us show that $M_{s}\in\mathcal{M}^{*}(r^{2}+r+1,(r+1)s,C)$ where the set
of colours $C=\\{(p_{k},t):k\in[1,r^{2}+r+1],t\in[1,s]\\}$ is of size
$(r^{2}+r+1)s$. First, the $i$th row of $M_{s}$, $i\in[1,r^{2}+r+1]$, consists
of $(r+1)s$ distinct elements of $C$ (corresponding to $r+1$ points of
$L_{i}$, see $B_{2}$). Next, the assumption $s\geq r$ guarantees that each
column of $M_{s}$ consists of $r^{2}+r+1$ distinct elements of $C$ (even if
there is a column of $M^{\prime}$ containing, for some $k\in[1,r^{2}+r+1]$,
all $p_{k}^{l}$ with $l\in[1,r+1]$). So, $M_{s}$ represents a proper vertex
colouring.

If $k,l\in[1,r^{2}+r+1]$, $k\neq l$, by the axiom $A_{1}$ there is a unique
$i\in[1,r^{2}+r+1]$ such that $\\{p_{k},p_{l}\\}\subseteq L_{i}$. Therefore,
for any $t,u\in[1,s]$, both $(p_{k},t)$ and $(p_{l},u)$ belong to the $i$th
row of $M_{s}$. If $k\in[1,r^{2}+r+1]$ and $t,u\in[1,s]$, $t\neq u$, both
$(p_{k},t)$ and $(p_{k},u)$ appear in $r+1$ rows of $M_{s}$ (corresponding to
$r+1$ rows of $M$ containing $p_{k}$). Thus $M_{s}$ represents a complete
vertex colouring, too; moreover,
$M_{s}\in\mathcal{M}^{*}(r^{2}+r+1,(r+1)s,C)\neq\emptyset$.

2\. Since
$\mathcal{M}(r^{2}+r+1,(r+1)s,C)\supseteq\mathcal{M}^{*}(r^{2}+r+1,(r+1)s,C)\neq\emptyset$
(see Lemma 5.1), using Proposition 2 we obtain
$\mathrm{achr}(K_{r^{2}+r+1}\square K_{(r+1)s})\geq|C|=(r^{2}+r+1)s$. ∎

Note that the structure of the matrix $M$ from the proof of Lemma 5 (that
depends on the projective plane order $r$) is “largely” various, but it
determines the structure of matrices $M^{\prime}$ and $M_{s}$ in a unique way.
For example, in the case $r=2$ and $s=3$ we have

$M=\begin{pmatrix}p_{1}&p_{2}&p_{3}\\\ p_{3}&p_{4}&p_{5}\\\
p_{5}&p_{6}&p_{1}\\\ p_{4}&p_{1}&p_{7}\\\ p_{7}&p_{3}&p_{6}\\\
p_{5}&p_{7}&p_{2}\\\ p_{2}&p_{6}&p_{4}\end{pmatrix},\quad
M^{\prime}=\begin{pmatrix}p_{1}^{1}&p_{2}^{1}&p_{3}^{1}\\\
p_{3}^{2}&p_{4}^{1}&p_{5}^{1}\\\ p_{5}^{2}&p_{6}^{1}&p_{1}^{2}\\\
p_{4}^{2}&p_{1}^{3}&p_{7}^{1}\\\ p_{7}^{2}&p_{3}^{3}&p_{6}^{2}\\\
p_{5}^{3}&p_{7}^{3}&p_{2}^{2}\\\ p_{2}^{3}&p_{6}^{3}&p_{4}^{3}\end{pmatrix},$

and then the matrix $M_{3}$ is

$\begin{pmatrix}(p_{1},1)&(p_{1},2)&(p_{1},3)&(p_{2},1)&(p_{2},2)&(p_{2},3)&(p_{3},1)&(p_{3},2)&(p_{3},3)\\\
(p_{3},2)&(p_{3},3)&(p_{3},1)&(p_{4},1)&(p_{4},2)&(p_{4},3)&(p_{5},1)&(p_{5},2)&(p_{5},3)\\\
(p_{5},2)&(p_{5},3)&(p_{5},1)&(p_{6},1)&(p_{6},2)&(p_{6},3)&(p_{1},2)&(p_{1},3)&(p_{1},1)\\\
(p_{4},2)&(p_{4},3)&(p_{4},1)&(p_{1},3)&(p_{1},1)&(p_{1},2)&(p_{7},1)&(p_{7},2)&(p_{7},3)\\\
(p_{7},2)&(p_{7},3)&(p_{7},1)&(p_{3},3)&(p_{3},1)&(p_{3},2)&(p_{6},2)&(p_{6},3)&(p_{6},1)\\\
(p_{5},3)&(p_{5},1)&(p_{5},2)&(p_{7},3)&(p_{7},1)&(p_{7},2)&(p_{2},2)&(p_{2},3)&(p_{2},1)\\\
(p_{2},3)&(p_{2},1)&(p_{2},2)&(p_{6},3)&(p_{6},1)&(p_{6},2)&(p_{4},3)&(p_{4},1)&(p_{4},2)\end{pmatrix}.$

##  3 Main theorem

######  Theorem 6.

If $r$ is a finite projective plane order, $s\in[r^{3}+1,\infty)$ and
$t\in[0,r]$, then

$(r^{2}+r+1)s+t\leq\mathrm{achr}(K_{r^{2}+r+1}\square
K_{(r+1)s+t})\leq(r^{2}+r+1)s+rt.$

###### Proof.

Denote $a_{s,t}=\mathrm{achr}(K_{r^{2}+r+1}\square K_{(r+1)s+t})$ for
$t\in[0,r]$. Since $s\geq r^{3}+1\geq r+1$, from Lemma 5 we know there is a
colour set $C_{s,0}^{*}$ of size $(r^{2}+r+1)s$ such that
$\mathcal{M}^{*}(r^{2}+r+1,(r+1)s,C_{s,0}^{*})\neq\emptyset$ and

$a_{s,0}\geq(r^{2}+r+1)s.$ (1)

If $t\in[0,r-1]$, it is an easy exercise to prove the inequality $(r+1)s+t\geq
2(r^{2}+r+1)-1$. Therefore, using (1) and Lemma 4, by induction on $t$ we see
that for any $t\in[0,r]$ there exists a colour set $C_{s,t}^{*}$ of size
$(r^{2}+r+1)s+t$ with
$\mathcal{M}^{*}(r^{2}+r+1,(r+1)s+t,C_{s,t}^{*})\neq\emptyset$, which implies

$a_{s,t}\geq(r^{2}+r+1)s+t.$ (2)

Now let $C_{s,t}$ be an $a_{s,t}$-element set. By Proposition 2 there exists a
matrix $M_{s,t}\in\mathcal{M}(r^{2}+r+1,(r+1)s+t,C_{s,t})$. If $l_{s,t}$ is
the minimum frequency of an element of $C_{s,t}$ in $M_{s,t}$, from Lemma 3.2
and (2) it follows that

$\displaystyle l_{s,t}$
$\displaystyle\leq\left\lfloor\frac{(r^{2}+r+1)[(r+1)s+t]}{a_{s,t}}\right\rfloor\leq\left\lfloor\frac{(r^{2}+r+1)[(r+1)s+t}{(r^{2}+r+1)s}\right\rfloor$
$\displaystyle=r+1.$ (3)

In the case $l_{s,t}=r+1$ each colour class of the colouring $f_{M_{s,t}}$ is
of cardinality at least $r+1$, hence, by (2),

$|V(K_{r^{2}+r+1}\square
K_{(r+1)s+t})|=(r^{2}+r+1)[(r+1)s+t]\geq(r+1)a_{s,t},$

so that

$a_{s,t}\leq(r^{2}+r+1)s+\left\lfloor\frac{(r^{2}+r+1)t}{r+1}\right\rfloor=(r^{2}+r+1)s+rt.$
(4)

On the other hand, if $l_{s,t}\leq r$ (see (3)), Lemma 3.3 yields

$\displaystyle a_{s,t}$ $\displaystyle\leq
l_{s,t}[r^{2}+r+1+(r+1)s+t-l_{s,t}-1]+1$ $\displaystyle\leq
r[r^{2}+r+1+(r+1)s+t-r-1]+1$ $\displaystyle=r[r^{2}+(r+1)s+t]+1$ (5)

(since $r\geq 2$, the polynomial $x[r^{2}+r+1+(r+1)s+t-x-1]+1$ in variable $x$
is increasing for $x\leq r$), and from (5) we obtain

$a_{s,t}\leq r^{3}+r(r+1)s+rt+1\leq s+r(r+1)s+rt=(r^{2}+r+1)s+rt.$ (6)

From (4) and (6) we see that

$a_{s,t}\leq(r^{2}+r+1)s+rt$ (7)

independently from the value of $l_{s,t}$, and so, by (2) and (7), for any
$t\in[0,r]$ (including $t=k$) we have $(r^{2}+r+1)s+t\leq
a_{s,t}\leq(r^{2}+r+1)s+rt$. ∎

######  Corollary 7.

If $r$ is a finite projective plane order and $s\in[r^{3}+1,\infty)$, then

$\mathrm{achr}(K_{r^{2}+r+1}\square K_{(r+1)s})=(r^{2}+r+1)s.$

###### Proof.

Take $k=0$ in Theorem 6. ∎

##  4 Asymptotic analysis

######  Theorem 8.

If $r$ is a finite projective plane order, then

$\lim_{q\to\infty}\frac{\mathrm{achr}(K_{r^{2}+r+1}\square
K_{q})}{q}=\frac{r^{2}+r+1}{r+1}.$

###### Proof.

Denote for simplicity $a(p,q)=\mathrm{achr}(K_{p}\square K_{q})$. We have
$a(p,q)=a\left(p,(r+1)\left\lfloor\frac{q}{r+1}\right\rfloor)+k\right)$, where
$k=q-(r+1)\left\lfloor\frac{q}{r+1}\right\rfloor\in[0,r]$. If
$s=\left\lfloor\frac{q}{r+1}\right\rfloor\geq r^{3}+1$, then, by Theorem 6,

$\displaystyle\frac{(r^{2}+r+1)\left\lfloor\frac{q}{r+1}\right\rfloor}{q}$
$\displaystyle\leq\frac{(r^{2}+r+1)\left\lfloor\frac{q}{r+1}\right\rfloor+k}{q}$
$\displaystyle\leq\frac{a\left(r^{2}+r+1,(r+1)\left\lfloor\frac{q}{r+1}\right\rfloor+k\right)}{q}$
$\displaystyle=\frac{a(r^{2}+r+1,q)}{q}\leq\frac{(r^{2}+r+1)\left\lfloor\frac{q}{r+1}\right\rfloor+rk}{q}$
$\displaystyle\leq\frac{(r^{2}+r+1)\left\lfloor\frac{q}{r+1}\right\rfloor+r^{2}}{q}.$
(8)

Now, having in mind that
$\lim_{q\to\infty}\frac{\left\lfloor\frac{q}{r+1}\right\rfloor}{q}=\frac{1}{r+1}$
and $\lim_{q\to\infty}\frac{r^{2}}{q}=0$, from (4) we obtain
$\lim_{q\to\infty}\frac{a(r^{2}+r+1,q)}{q}=\frac{r^{2}+r+1}{r+1}$. ∎

From the known results for $\mathrm{achr}(K_{p}\square K_{q})$ with $p\leq 6$,
see [13] ($p\leq 4$), [11] ($p=5$) and [9], [10] ($p=6$), we can easily deduce
the existence and the value of the limit
$l_{p}=\lim_{q\to\infty}\frac{\mathrm{achr}(K_{p}\square K_{q})}{q}$. Namely,
we have $l_{1}=1=l_{2}$, $l_{3}=\frac{3}{2}$, $l_{4}=\frac{5}{3}$,
$l_{5}=\frac{9}{5}$ and $l_{6}=2$. These facts together with Theorem 8
motivate us to formulate

######  Conjecture 1.

If $p\in[1,\infty)$, then $\lim_{q\to\infty}\frac{\mathrm{achr}(K_{p}\square
K_{q})}{q}$ does exist and is a rational number.

Acknowledgement

This work was supported by the Slovak Research and Development Agency under
the contract APVV-19-0153 and by the grant VEGA 1/0574/21.

## References

  * [1] A. Bouchet, Indice achromatique des graphes multiparti complets et réguliers, Cahiers du Centre d’Études de Recherche Opérationelle 20 (1978) 331–340.
  * [2] N. Cairnie, K.J. Edwards, The achromatic number of bounded degree trees, Discrete Math. 188 (1998) 87–97.
  * [3] N.P. Chiang, H.L. Fu, On the achromatic number of the cartesian product $G_{1}\times G_{2}$, Australas. J. Combin. 6 (1992) 111–117.
  * [4] N.P. Chiang, H.L. Fu, The achromatic indices of the regular complete multipartite graphs, Discrete Math. 141 (1995) 61–66.
  * [5] K.J. Edwards, A Bibliography of Harmonious Colourings and Achromatic Number, staff.computing.dundee.ac.uk/kedwards/biblio.html.
  * [6] F. Harary, S. Hedetniemi, G. Prins, An interpolation theorem for graphical homomorphisms, Portug. Math. 26 (1967) 454–462.
  * [7] P. Hell, D.J. Miller, Achromatic numbers and graph operations, Discrete Math. 108 (1992) 297–305.
  * [8] M. Horňák, The achromatic number of $K_{6}\,\square\,K_{7}$ is $18$, Opuscula Math. 41 (2021), 163–185.
  * [9] M. Horňák, The achromatic number of $K_{6}\square K_{q}$ equals $2q+3$ if $q\geq 41$ is odd, Discuss. Math. Graph Theory, https://doi.org/dmgt.2420.
  * [10] M. Horňák, The achromatic number of the Cartesian product of $K_{6}$ and $K_{q}$, Discuss. Math. Graph Theory, https://doi.org/10.1751/dmgt.2451.
  * [11] M. Horňák, Š. Pčola, Achromatic number of $K_{5}\times K_{n}$ for large $n$, Discrete Math. 234 (2001), 159–169.
  * [12] M. Horňák, Š. Pčola, Achromatic number of $K_{5}\times K_{n}$ for small $n$, Czechoslovak Math. J. 53 (128) (2003), 963–988.
  * [13] M. Horňák, J. Puntigán, On the achromatic number of $K_{m}\times K_{n}$, in: M. Fiedler (ed.), Graphs and Other Combinatorial Topics, Teubner, Leipzig, 1983, pp. 118–123.
  * [14] W. Imrich, S. Klavžar, Product Graphs, Wiley-Interscience, New York, 2000.


problemdefinition[2][]

#2
---

# Sharp Noisy Binary Search with Monotonic Probabilities

Lucas Gretta
UC Berkeley111Work partially done while at UT Austin Eric Price
UT Austin

We revisit the noisy binary search model of [KK07], in which we have $n$ coins
with unknown probabilities $p_{i}$ that we can flip. The coins are sorted by
increasing $p_{i}$, and we would like to find where the probability crosses
(to within $\varepsilon$) of a target value $\tau$. This generalized the
fixed-noise model of [BZ74], in which $p_{i}=\frac{1}{2}\pm\varepsilon$, to a
setting where coins near the target may be indistinguishable from it. It was
shown in [KK07] that $\Theta(\frac{1}{\varepsilon^{2}}\log n)$ samples are
necessary and sufficient for this task.

We produce a _practical_ algorithm by solving two theoretical challenges:
high-probability behavior and sharp constants. We give an algorithm that
succeeds with probability $1-\delta$ from

$\frac{1}{C_{\tau,\varepsilon}}\cdot\left(\lg
n+O(\log^{2/3}n\log^{1/3}\frac{1}{\delta}+\log\frac{1}{\delta})\right)$

samples, where $C_{\tau,\varepsilon}$ is the optimal such constant achievable.
For $\delta>n^{-o(1)}$ this is within $1+o(1)$ of optimal, and for $\delta\ll
1$ it is the first bound within constant factors of optimal.

##  1 Introduction

Binary search is one of the most fundamental algorithms in computer science,
finding an index $i^{*}\in[n]$ from $\log_{2}n$ queries asking if a given
index $i$ is larger than $i^{*}$. But what if the queries are noisy?

One model for noisy binary search has each query be incorrect independently
with exactly the same probability $\frac{1}{2}-\varepsilon$. In this model,
which we call FixedNoiseNBS, a line of work [BZ74, BH08, DLU21, GX23] has
found a sharp bound for the required expected sample complexity, with tight
constants. However, in many applications of noisy binary search the error
probability is not fixed, but varies with $i$: comparing $i$ to $i^{*}$ is
much harder when $i$ is close to $i^{*}$.

As one example, consider the problem of estimating the sample complexity of an
algorithm such as for distribution testing or noisy binary search itself.
Proofs in this space are often sloppy with constant factors, so the proven
bound is not reflective of the true performance. If so, we would like to
empirically estimate the sample complexity $i$ at which the success
probability $p_{i}$ is above a given threshold $\tau$ (say, 90%). (In some
cases we even know the worst-case distribution [DGPP18] so the empirical
estimate is of the worst-case performance, not just the distributional
performance.) We can run the algorithm at a given sample complexity $i$ and
check correctness, getting Success with probability $p_{i}$. The success
probability is monotonic in $i$, and we would like to estimate the $i^{*}$
where $p_{i}$ crosses $\tau$. Finding $i^{*}$ exactly may be very hard—the
success probability at 10000 and 10001 samples are likely to be almost
identical—so we would settle for _some_ index with $p_{i}\approx\tau$.

For a non-computer science example, calculating the LD50 for a substance (the
dose needed to kill half of the members of a specific population) is a noisy
binary search problem with error probability that skyrockets close to the true
answer.

Such considerations led to the noisy binary search model of [KK07], which we
call $\textsc{MonotonicNBS}(\tau,\varepsilon)$: we have $n$ coins whose
unknown probabilities $p_{i}\in[0,1]$ are sorted in nondecreasing order. We
can flip coin $i$ to see heads with probability $p_{i}$. The goal is to find
any coin $i$ with nonempty
$[p_{i},p_{i+1}]\cap(\tau-\varepsilon,\tau+\varepsilon)$. This model subsumes
FixedNoiseNBS (where $p_{i}=\frac{1}{2}-\varepsilon$ for $i\leq i^{*}$ and
$\frac{1}{2}+\varepsilon$ otherwise) and of course regular binary search
(where $p_{i}\in\\{0,1\\}$). Throughout this paper we will suppose that $\tau$
is a constant bounded away from $\\{0,1\\}$, $n$ grows to $\infty$, and
$\varepsilon$ and the desired failure probability $\delta$ may be constant or
may approach $0$ as $n\to\infty$.

Figure 1: In FixedNoiseNBS, every coin is $\varepsilon$-far from the true
$i^{*}$ that must be found. We consider MonotonicNBS, where many coins may be
close to the threshold and the goal is to find some good coin (the gray shaded
region).

The naive solution to MonotonicNBS is binary search with repetition: we do
regular binary search, but repeat each query enough times to have
$\frac{\delta}{\log n}$ failure probability if
$p_{i}\notin[\tau-\varepsilon,\tau+\varepsilon]$. This gives sample complexity
$O(\frac{1}{\varepsilon^{2}}\log n\log\frac{\log n}{\delta})$. In [KK07] it
was shown that this extra $\log\log n$ term is unnecessary, giving two
algorithms that each have sample complexity

$O(\frac{1}{\varepsilon^{2}}\log n\log\frac{1}{\delta}).$

In this paper, we show how to improve this bound. We show upper and lower
bounds that achieve the tight constant on $\log n$, and reduce the
$\log\frac{1}{\delta}$ dependence from multiplicative to additive. Figure 2
compares our result to existing methods for MonotonicNBS.

Algorithm | Proven query complexity | Actual constant
---|---|---
Binary Search w/ Repetition | $2\frac{\tau(1-\tau)}{\varepsilon^{2}}\ln n\cdot{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\ln\frac{\lg n}{\delta}}$ |
[KK07] Multiplicative Weights | $4000\frac{\max(\tau,1-\tau)}{\varepsilon^{2}}\ln n\cdot\ln\frac{1}{\delta}$ | $\approx 31$
[KK07] Backtracking | $476909\frac{\max(\tau,1-\tau)}{\varepsilon^{2}}\ln n\cdot\ln\frac{1}{\delta}$ | $\approx 2000$
BayesianScreeningSearch | $2\frac{\tau(1-\tau)}{\varepsilon^{2}}\ln n$ |
Figure 2: Comparison of our result to prior algorithms for MonotonicNBS in the
regime of $\varepsilon\ll\min(\tau,1-\tau)$ and $\delta=1/n^{o(1)}$, ignoring
lower order terms. The analysis in [KK07] is not careful with constants, so we
also include our best estimate of the actual constant after tuning constant
factors in the algorithms.

#### On Studying Constants.

When analyzing sublinear algorithms, and trying to remove $\log\log n$ factors
in query complexity, constant factors really matter. The proofs in [KK07] are
not careful with constants, but the algorithms themselves inherently lose
constants. Our best estimate is that one algorithm “improves” upon naive
repetition by a factor of $\frac{\ln\lg n}{31}$, and the other by
$\frac{\ln\lg n}{2000}$. Neither is an improvement for any $n$ that will ever
be practical—the better algorithm is only an improvement for
$n>2^{e^{31}}\approx 10^{10^{11}}$. By studying constants, we are forced to
design an algorithm that (as we shall see) gives improvements for practical
values of $n$. We give further discussion of the value of studying constants
in Section 1.3.

Noisy binary search is intimately connected to the asymmetric binary channel,
i.e., the binary channel that can choose between sending $1$ with probability
$\tau-\varepsilon$ or with probability $\tau+\varepsilon$. If each
$p_{i}\in\\{\tau\pm\varepsilon\\}$, then noisy binary search needs to reveal
the $\lg n$-bit $i^{*}$ through such a channel; queries below $i^{*}$ are $1$
with probability $\tau-\varepsilon$ and those above $i^{*}$ are $1$ with
probability $\tau+\varepsilon$. The natural target sample complexity is
therefore $\frac{1}{C_{\tau,\varepsilon}}\lg n$, where $C_{\tau,\varepsilon}$
is the _information capacity_ of the asymmetric binary channel:

$\displaystyle
C_{\tau,\varepsilon}:=\max_{q}H((1-q)(\tau-\varepsilon)+q(\tau+\varepsilon))-(1-q)H(\tau-\varepsilon)-qH(\tau+\varepsilon)$
(1)

where $H(p)$ is the binary entropy function. For $\tau=\frac{1}{2}$, the
maximum is at $q=\frac{1}{2}$ and this is just
$C_{\frac{1}{2},\varepsilon}=1-H(\frac{1}{2}-\varepsilon)$, the capacity of
the binary _symmetric_ channel with error probability
$\frac{1}{2}-\varepsilon$. For $\tau\neq\frac{1}{2}$, the information obtained
from $\tau-\varepsilon$ and $\tau+\varepsilon$ probability coins is not the
same, so the capacity is achieved by getting $\tau+\varepsilon$ coins with
some probability $q$ different from $1/2$; it satisfies
$C_{\tau,\varepsilon}\approx\frac{\varepsilon^{2}}{2\tau(1-\tau)\ln 2}$ for
fixed $\tau$ as $\varepsilon\to 0$.

#### Our results.

Our main result is the following:

######  Theorem 1.1 (Upper bound).

Let $0<\tau<1$ be a constant. Consider any parameters
$0<\varepsilon,\delta<1/2$ with $0<\varepsilon<\min(\tau,1-\tau)/2$. On any
$\textsc{MonotonicNBS}(\tau,\varepsilon)$ input, the algorithm
BayesianScreeningSearch uses at most

$\frac{1}{C_{\tau,\varepsilon}}(\lg
n+O(\log^{2/3}n\log^{1/3}\frac{1}{\delta}+\log\frac{1}{\delta}))$

queries and succeeds with probability $1-\delta$.

Unlike [BZ74, BH08, DLU21, WGZW22, GX23], our results apply to MonotonicNBS,
not just FixedNoiseNBS, so they do not restrict the value of $p_{i}$ and
handle $\tau\neq\frac{1}{2}$. Unlike [KK07], we achieve good constant factors,
high-probability results, and a better scaling with the target $\tau$. In
particular, [KK07] scales multiplicatively rather than additively with
$O(\log\frac{1}{\delta})$; and it uses a reduction that incurs a constant-
factor _loss_ for targets $\tau\neq\frac{1}{2}$, while Theorem 1.1 scales with
$\Theta(\tau(1-\tau))$ so _improves_ for $\tau\neq\frac{1}{2}$.

Using Shannon’s strong converse theorem, we show that the dependence on $n$ is
tight: for $\varepsilon\gg n^{-1/4}$, any algorithm must sometimes use
$(1-o(1))\frac{1}{C_{\tau,\varepsilon}}\lg n$ queries; in fact, it must use
this many queries with nearly $1-\delta$ probability.

######  Theorem 1.2 (Strong converse).

Any $\textsc{MonotonicNBS}(\tau,\varepsilon)$ algorithm that succeeds with
$1-\delta$ probability on inputs with all $p_{i}\in\\{\tau\pm\varepsilon\\}$
must have at least a $1-\delta-O(\frac{1}{\gamma^{2}n\varepsilon^{4}})$ chance
of using at least

$(1-\gamma)\frac{1}{C_{\tau,\varepsilon}}\lg n$

queries, for any $\gamma>0$.

For $\tau=\frac{1}{2}$, this is also a lower bound for FixedNoiseNBS. Thus
Theorem 1.2 gives a new _worst-case_ lower bound for FixedNoiseNBS, which is a
$\frac{1}{1-\delta}$ factor larger than the lower bound for _expected_ query
complexity achieved in prior work [BZ74, BH08, DLU21, GX23].

For $\tau\neq\frac{1}{2}$, our results are the first ones connecting noisy
binary search to $C_{\tau,\varepsilon}$, the information capacity of the
binary asymmetric channel.

#### Our results: expected queries.

For constant $\delta$, one can get a better bound for the expected number of
queries in a simple way: only run the algorithm with probability
$1-(1-\frac{1}{\log n})\delta$, and otherwise output the wrong answer from
zero queries. This saves essentially a $1-\delta$ factor in queries, which for
constant $\delta$ is nontrivial:

######  Corollary 1.3 (Upper bound: expected queries).

Under the same conditions as Theorem 1.1 and for any
$\textsc{MonotonicNBS}(\tau,\varepsilon)$ input, algorithm
SillyBayesianScreeningSearch uses

$\frac{1-\delta}{C_{\tau,\varepsilon}}(\lg n+O(\log^{2/3}n\log^{1/3}\frac{\log
n}{\delta}+\log\frac{1}{\delta}))$

queries in expectation and succeeds with probability $1-\delta$.

This $1-\delta$ savings is essentially the best possible. Our strong converse
(Theorem 1.2) already implies this, if $\varepsilon\gg n^{-1/4}$; but using
Fano’s inequality, the optimality is true in general:

######  Theorem 1.4 (Weak converse).

Any $\textsc{MonotonicNBS}(\tau,\varepsilon)$ algorithm that succeeds with
$1-\delta$ probability on inputs with all $p_{i}\in\\{\tau\pm\varepsilon\\}$
must use

$(1-\delta)\frac{\lg(n-2)-1}{C_{\tau,\varepsilon}}$

queries in expectation.

Theorem 1.4 was essentially shown in [BZ74], which proved the
$\tau=\frac{1}{2}$ case (by giving hardness for FixedNoiseNBS).

#### Our results: experiments.

In Section 6 we compare our approach to naive repetition and the [KK07]
algorithms. We find, for $n\geq 10^{3}$ and $\varepsilon=.1$, that our
approach outperforms naive repetition, which outperforms both [KK07]
algorithms. For $n=10^{9}$, our approach uses $2.3\times$ fewer samples than
naive repetition.

###  1.1 Algorithm Overview

We now describe our noisy binary search algorithm in the case of
$\tau=\frac{1}{2}$ and $\delta>1/n^{o(1)}$.

#### Bayesian start.

The natural choice for a “hard” instance is when
$p_{i}\in\\{\tau\pm\varepsilon\\}$, so the algorithm must find the transition
location $i^{*}$, and information theoretic arguments show
$\frac{1}{C_{\tau,\varepsilon}}\lg n$ queries are necessary. To avoid losing a
constant factor in sample complexity, the algorithm essentially must spend
most of its time running the Bayesian algorithm. This algorithm starts with a
uniform prior over which interval crosses $\tau$, makes the maximally
informative query, updates its posterior, and repeats. When
$\tau=\frac{1}{2}$, the maximally informative query is the median under the
posterior, and the Bayesian update is to multiply intervals on one side of the
query by $1+2\varepsilon$ and the other side by $1-2\varepsilon$. This
algorithm, BayesLearn, is given in Algorithm 1; the algorithm for general
$\tau$ is given in Section 3.

As a technical side note, the discrete nature of the problem introduces a bit
of subtlety. Note that MonotonicNBS flips coins $i$ but returns an _interval_
between coins that should be good:

######  Definition 1.5.

We say that an interval $[i,i+1]$ is _$(\tau,\varepsilon)$ -good_ if
$[p_{i},p_{i+1}]\cap(\tau-\varepsilon,\tau+\varepsilon)$ is nonempty.

Precisely, our version of the Bayesian algorithm is as follows: we start with
a uniform prior over intervals. The median of our posterior can be viewed as a
fractional coin, and we flip the nearest actual coin but update our posterior
as if we flipped the fractional coin. So, for example, suppose the median is
$4.7$ ($.7*w(5)+\sum_{i=1}^{4}w(i)=.5$). We flip coin 5, and if it comes out
$0$, that suggests the true threshold is probably above $5$. We then scale up
our posterior on all intervals above $5$ by $1+2\varepsilon$; scale down
intervals below $4$ by $1-2\varepsilon$; and scale the weight on interval
$[4,5]$ by $.3(1+2\varepsilon)+.7(1-2\varepsilon)$. This new posterior is
still a distribution that sums to $1$.

Algorithm 1 Bayesian learner in $\tau=\frac{1}{2}$ case. Flips $M$ coins and
returns $M$ intervals.

Input A set of $n$ queryable coins, update size $\varepsilon$, number of steps
$M$.
Output A list of $M$ intervals queried.

1:procedure BayesLearn($\text{coins},\varepsilon,M$)

2: $n\leftarrow{|\text{coins}|}$

3: $w_{1}\leftarrow\text{uniform}([n-1])$ $\triangleright$ Prior distribution
over intervals

4: $L\leftarrow\\{\\}$

5: for $i\in[M]$ do

6: $j_{i}\leftarrow$ median interval of $w_{i}$

7: $x_{i}\leftarrow$ either $j_{i}$ or $j_{i}+1$, whichever is closer to the
median

8: append $j_{i}$ to $L$

9: $y_{i}\leftarrow$ flip coin $x_{i}$ $\triangleright$ $1$ with probability
$p_{x_{i}}$

10:
$w_{i+1}(x)\leftarrow\begin{cases}w_{i}(x)\cdot(1-2\varepsilon(-1)^{y_{i}})&\mbox{if
}x<j_{i}\\\ w_{i}(x)\cdot(1+2\varepsilon(-1)^{y_{i}})&\mbox{if }x>j_{i}\\\
\text{remainder so $w_{i+1}$ sums to $1$}&\mbox{if }x=j_{i}\end{cases}$

11: return $L$

#### Using the result.

After running the Bayesian algorithm for most of our query budget, we need to
output an answer. The question becomes: how can we take the transcript of the
Bayesian algorithm and extract a useful worst-case frequentist guarantee? We
need the algorithm to work for _all_ monotonic $p$, which can have values very
different than $\tau\pm\varepsilon$.

In the prior work achieving tight constants for FixedNoiseNBS [BZ74, DLU21],
because the $p_{i}$ are guaranteed to be $\frac{1}{2}\pm\varepsilon$, the
analysis can show that the weight of the single “good” interval grows in
expectation at each step. By a Hoeffding bound, after the desired number of
iterations the “good” interval has more weight than every other interval
combined, so it can be easily selected. But that property is not true for the
more general $p_{i}$ of MonotonicNBS: if many $p_{i}$ are $\frac{1}{2}\pm
0.6\varepsilon$, the Bayesian algorithm will wander somewhat too slowly
through these samples without growing any single interval by the desired
amount.

However, in such cases the Bayesian algorithm is spending a lot of time among
good intervals. This holds in general. Our key lemma shows that, if we run
BayesLearn for $1+O(\gamma)$ times the information theoretic bound
$\frac{1}{C_{\tau,\varepsilon}}\lg n$, a $\gamma$ fraction of the intervals it
visits are $(\tau,\varepsilon)$-good:

######  Lemma 1.6 (Bayesian performance).

Consider any $0<\varepsilon,\tau,\delta,\gamma<1$ with
$\gamma\leq\frac{1}{7}$, $\varepsilon<\min(\tau,1-\tau)/2$, and let $L$ be the
list of intervals returned by BayesLearn, when run for

$\frac{1+O(\gamma)}{C_{\tau,\varepsilon}}\cdot\left(\lg n+O(\sqrt{\log
n\log\frac{1}{\delta}}+\log\frac{1}{\delta})\right)$

iterations on an MonotonicNBS instance. With probability $1-\delta$, at least
a $\gamma$ fraction of the intervals in $L$ are $(\tau,\varepsilon)$-good.

By considering the $\gamma$-quantiles of the returned list, we reduce $n$ to
$\frac{1}{\gamma}$. We can now run a less efficient noisy binary search
algorithm on this small subproblem. There are some complications, as the
solution to the new noisy binary search could correspond to a larger interval
than two adjacent coins. To deal with this, we run BayesLearn with
$\varepsilon^{\prime}=(1-o(1))\varepsilon$, which lets us test our candidate
answers.

#### Technical comparison of techniques.

How we leverage the bayesian learner is the main technical difference between
our upper bound and that of prior work [KK07, BZ74, DLU21]. As described
above, the situation is rather simpler for FixedNoiseNBS. For MonotonicNBS,
[KK07] instead used conservative updates in their multiplicative weights
algorithm: rather than the true Bayesian update $1\pm 2\varepsilon$, it
multiplies by about $1\pm\frac{3}{5}\varepsilon$. This necessarily loses a
constant factor, but ensures that either the median interval queried or the
last interval queried is good. This property is not true for the true Bayesian
algorithm with sharp constant.

###  1.2 Related Work

The FixedNoiseNBS version of noisy binary search, where $\tau=\frac{1}{2}$ and
$p_{i}\in\\{\frac{1}{2}\pm\varepsilon\\}$, was posed by Burnashev and
Zigangirov [BZ74], who showed how to achieve

$\frac{1}{C_{\frac{1}{2},\varepsilon}}\left(\lg
n+\lg\frac{1}{\delta}+\lg\frac{1+2\varepsilon}{1-2\varepsilon}\right)$

_expected_ queries (in Russian; see [WGZW22] for an English proof).
Essentially the same [BZ74] algorithm for FixedNoiseNBS was rediscovered in
[BH08]. Some bugs with the [BH08] proof were discovered and fixed in [DLU21],
as well as an analysis of a variant of the algorithm for _worst-case_ sample
complexity

$\frac{1}{C_{\frac{1}{2},\varepsilon}}\left(\lg n+O(\sqrt{\log
n\log\frac{1}{\delta}})+O(\log\frac{1}{\delta})\right).$

For $1\ll\log\frac{1}{\delta}\ll\log n$, Gu and Xu [GX23] showed black-box
improvements for other $\delta$. If $\delta$ is constant, they output $\perp$
with probability $\delta-\frac{1}{\log n}$, and otherwise run the [DLU21]
algorithm with $\delta^{\prime}=\frac{1}{\log n}$. On the other hand, for
$\delta=n^{-\Omega(1)}$, repeatedly running [DLU21] with
$\delta^{\prime}=\frac{1}{\log n}$ and checking the result gives improvements:

$(1+o(1))\left(\frac{1-\delta}{C_{\frac{1}{2},\varepsilon}}\lg
n+\frac{\log\frac{1}{\delta}}{\varepsilon\log\frac{1+2\varepsilon}{1-2\varepsilon}}\right)$

For $\varepsilon\ll 1$, this is a factor 2 improvement on the constant factor
on $\log\frac{1}{\delta}$. Moreover, [GX23] shows that this bound is sharp in
both $n$ and $\delta$.

Our version of noisy binary search, MonotonicNBS, was first posed by Karp and
Kleinberg [KK07]. They gave two algorithms, based on recursive backtracking
and multiplicative weights respectively, that take
$O(\frac{1}{\varepsilon^{2}}\log n)$ queries for constant $\delta$, which they
showed is within constant factors of optimal for constant $\tau,\delta$.
Unfortunately, the constant factors make both algorithms worse than the naive
repetition algorithm for any reasonable $n$ (see Figure 2 and Section 6).

#### Other models.

There are many different variations for noisy binary search (see [Pel02] for a
survey of older work on the subject). Emamjomeh-Zadeh, Kempe, and Singhal
[EKS16] solve an extension of FixedNoiseNBS from the line to graphs. This
result was improved and simplied by Dereniowski, Tiegel, Uznański and Wolleb-
Graf [DGTU18], which was in later improved and simplified by Dereniowski,
Łukasiewicz, and Uznański [DLU21]. Nowak developed a different generalization
of FixedNoiseNBS to general hypothesis classes [Now09]. Waeber, Frazier, and
Henderson [WFH13] investigates a continuous variant of FixedNoiseNBS, where
the target is a point in the real interval $[0,1]$, and show that the Bayesian
algorithm converges geometrically (the ideal convergence up to constant
factors).

To our knowledge, [KK07] is the only previous work that handles a setting like
MonotonicNBS where the “true” coin may be indistinguishable from nearby coins,
and the goal is just to find a sufficiently good answer.

#### Applications.

Noisy binary search is also used as a subroutine in other algorithms. For
instance in [TS22] it is used for group testing, and in Crume [Cru20] as a
replacement for git-bisect under unreliable tests. Both implementations were
based on the multiplicative weights algorithm of Karp and Kleinberg [KK07].

###  1.3 Why constants?

There is a tendency in theoretical computer science to regard constant factors
as unimportant. But theorists care about constants in many situations, such as
approximation ratios or rates of codes, and we believe that the query
complexity of sublinear algorithms is another situation where they should be
considered.

In general, the arguments for ignoring constants in time complexity hold with
much less force for query complexity. The constant for time complexity is
highly dependent on the machine architecture, which changes over time (e.g.,
the relative cost of addition and multiplication). Moreover, these hardware
improvements mitigate the cost of poor constants. But the number of queries is
a mathematical value, and the cost of queries (which may be, e.g., blood tests
or running a giant test suite) does not clearly decrease with time.

The question should be: does theoretical study of constant factors lead to
algorithmic insights necessary for more practical algorithms? Our paper shows
that it does. By considering constants, we are forced to find a more efficient
way of translating the Bayesian algorithm into one with frequentist guarantees
(via Lemma 1.6). The constants lost in the previous attempt at this (in
[KK07]) mean that it is worse than the naive method until $n>10^{10^{11}}$.

It should not be surprising that a simple method that loses an $O(\log\log n)$
factor can beat an algorithm that loses “only” constants, for all practical
values of $n$. The study of leading constants is a lens by which we found a
new algorithm that actually outperforms the naive method for reasonable values
of $n$ (namely $n>1000$).

##  2 Detailed Proof Sketch for Upper Bound

###  2.1 Key Lemma on Bayesian Learner.

For this proof overview, we focus on the case of $\delta>n^{-o(1)}$ and target
$\tau=\frac{1}{2}$, where BayesLearn queries the median of the posterior at
each stage, and

$C_{\tau,\varepsilon}=1-H(\frac{1}{2}+\varepsilon)=(\frac{1}{2}+\varepsilon)\lg(1+2\varepsilon)+(\frac{1}{2}-\varepsilon)\lg(1-2\varepsilon)\approx\frac{2\varepsilon^{2}}{\ln
2}.$

We give an overview of the proof of our key lemma in this case:

See 1.6

Let $a$ be the “best answer”, an interval that straddles the bias
$\frac{1}{2}$.

The algorithm keeps track of a distribution $w$ on $[n-1]$; at each step $i$,
it queries the median of the current distribution $w_{i}$, then multiplies the
density on one side by $1+2\varepsilon$ and the other by $1-2\varepsilon$ to
form $w_{i+1}$. We analyze the algorithm by looking at $\lg w(a)$.

At each step, the interval $j$ we choose is either good (a valid answer) or
bad (invalid). If it is _bad_ , suppose the sampled coin $x$ has probability
$p_{x}\geq\frac{1}{2}+\varepsilon$. Then $x$ is above $a$, so $w(a)$
multiplies by $1+2\varepsilon$ with probability $p_{x}$, and $1-2\varepsilon$
with probability $1-p_{x}$. Hence:

${\mathbb{E}}[\lg w_{i+1}(a)-\lg
w_{i}(a)]=p_{x}\lg(1+2\varepsilon)+(1-p_{x})\lg(1-2\varepsilon)\geq
C_{\tau,\varepsilon}.$

The case of $p_{x}\leq\frac{1}{2}-\varepsilon$ is symmetric, giving the same
bound. So every bad interval we select increases $\lg w(a)$ by
$C_{\tau,\varepsilon}$ in expectation.

On the other hand, if the interval we select is _good_ , $\lg w(a)$ may
decrease in expectation. For example, if we query coin $a$ and
$\sum_{i=1}^{a-1}w(i)=\frac{1}{2}$, we could have

${\mathbb{E}}[\lg w_{i+1}(a)-\lg
w_{i}(a)]=\frac{1}{2}\lg(1-2\varepsilon)+\frac{1}{2}\lg(1+2\varepsilon)\approx-\frac{2\varepsilon^{2}}{\ln
2}\approx-C_{\tau,\varepsilon}$

It turns out this is essentially the worst case, and in general the expected
decrease in $\lg w(a)$ is no more than $5C_{\tau,\varepsilon}$ for any
$\varepsilon<\frac{1}{2}\min(\tau,1-\tau)$. As a result, the potential
function

$\lg w_{i}(a)-\gamma C_{\tau,\varepsilon}\cdot(\text{\\# intervals
chosen})+6C_{\tau,\varepsilon}\cdot(\text{\\# good intervals chosen})$

increases by at least $(1-\gamma)C_{\tau,\varepsilon}$ in expectation in each
step $i$, regardless of where the median is in that step. This potential
function starts at $-\lg(n-1)$, so after
$M=(1+2\gamma)\frac{1}{C_{\tau,\varepsilon}}\lg n$ steps it is at least
$\Theta(\gamma)\lg n$ in expectation. An Azuma-Hoeffding bound shows that the
value concentrates about this expectation, and in particular will be positive
with $1-\delta$ probability. If so, since $\lg w_{i}(a)\leq 0$ always, we have

$6\cdot(\text{\\# good intervals chosen})-\gamma(\text{\\# intervals
chosen})\geq 0,$

and hence a $\frac{\gamma}{6}$ fraction of chosen intervals are good.

This proves the key lemma: after
$(1+O(\gamma))\frac{1}{C_{\tau,\varepsilon}}\log n$ steps of BayesLearn, a
$\gamma$ fraction of coins flipped are good with decent probability.

#### Targets $\tau\neq\frac{1}{2}$.

When $\tau\neq\frac{1}{2}$, the maximum-information query is no longer the
median coin, but a slightly different quantile $\frac{1}{2}\pm
O(\frac{\varepsilon}{\tau(1-\tau)})$, and the Bayesian updates use more
complicated factors. This choice is still capacity-achieving on bad intervals,
i.e., the expected “information gain” is ${\mathbb{E}}[\lg w_{i}(a)-\lg
w_{i+1}(a)]\geq C_{\tau,\varepsilon}$, and on good intervals the expected
information loss is still at most $5C_{\tau,\varepsilon}$, so the proof
structure works unchanged.

###  2.2 Rest of Upper Bound

Recall that in this overview we assume $\log\frac{1}{\delta}\ll\log n$. By
Lemma 1.6, if we take all
$\\{\gamma,2\gamma,\dots,{\lfloor\frac{1}{\gamma}\rfloor}\gamma\\}$ quantiles
of the list returned by BayesLearn, run with parameter
$\varepsilon^{\prime}=\varepsilon(1-\alpha)$ (where $\alpha$ is introduced so
we can later test the bias of each coin), we get a size-$\frac{1}{\gamma}$
list containing at least one $\varepsilon^{\prime}$-good interval. This
$\varepsilon^{\prime}$ has
$C_{\tau,\varepsilon^{\prime}}=(1-O(\alpha))C_{\tau,\varepsilon}$. For any
$\gamma$, we can just flip all of these coins
$O(\frac{1}{\alpha^{2}\varepsilon^{2}}\log\frac{1}{\gamma\delta})$ times to
find an $\varepsilon$-good one. This would give sample complexity

$\displaystyle\underbrace{(1+O(\gamma))(1+O(\alpha))\frac{1}{C_{\tau,\varepsilon}}\left(\lg
n+O(\sqrt{\log n\log\frac{1}{\delta}})\right)}_{\text{{BayesLearn},
Lemma~{}\ref{lem:keylemma}}}+\underbrace{O(\frac{1}{\gamma}\cdot\frac{1}{\alpha^{2}\varepsilon^{2}}\log\frac{1}{\gamma\delta})}_{\text{Testing
quantiles}}$ (2)

which, by setting $\gamma$ and $\alpha$ to $(\frac{\log\frac{1}{\delta}}{\log
n})^{1/4}$, gives sample complexity

$(1+O(\frac{\log\frac{1}{\delta}}{\log
n})^{1/4})\frac{1}{C_{\tau,\varepsilon}}\lg n.$

This is the desired sharp bound, within $(1+o(1))$ of optimal. One can do
slightly better: the second stage is itself a noisy binary search question on
$O(1/\gamma)$ coins, so by applying the algorithm recursively with
$\gamma^{\prime}=O(1)$ we can solve it on the size-$O(1/\gamma)$ list in
$O(\frac{1}{(1-\alpha)C_{\tau,\varepsilon}}\log\frac{1}{\gamma\delta}+\frac{1}{\alpha^{2}\varepsilon^{2}}\log\frac{1}{\gamma\delta})$
queries. As we recurse on a much smaller list, the samples used are all lower
order and we do not need to recurse more than once. However, the answer to the
recursive call might not be a valid answer to the original problem.
Regardless, one of the endpoints of the return call must be a valid answer,
which we can test for. By optimizing the parameters, this improves the sample
complexity to

$(1+O(\frac{\log\frac{1}{\delta}}{\log
n})^{1/3})\frac{1}{C_{\tau,\varepsilon}}\lg n,$

giving Theorem 1.1.

##  3 Proof of Lemma 1.6

###  3.1 Definitions

Let $\\{l,\dots,r\\}$ be the set of good intervals. Let $a$ be the maximum
$i\in[n-1]$ such that $p_{i}\leq\tau$.

Recall that we defined

$\displaystyle C_{\tau,\varepsilon}$
$\displaystyle=\max_{q}H((1-q)(\tau-\varepsilon)+q(\tau+\varepsilon))-(1-q)H(\tau-\varepsilon)-qH(\tau+\varepsilon)$
(3)

We also define the following functions:

$\displaystyle W(x)$ $\displaystyle=\sum_{i\in[x]}w(i)$ (4)
$\displaystyle\Phi(w,L)$ $\displaystyle=\lg
w(a)+6C_{\tau,\varepsilon}(|\\{x\in L|x\in[l,r]\\}|-\gamma|L|)$ (5)

$C_{\tau,\varepsilon}$ is the capacity of a $(\tau,\varepsilon)$-BAC. We let
$q$ satisfy the equation

$q=\operatorname*{arg\,max}_{x}H((1-x)(\tau-\varepsilon)+x(\tau+\varepsilon))-(1-x)H(\tau-\varepsilon)-xH(\tau+\varepsilon),$

which expresses the shared information between a sent and received message
through a $(\tau,\varepsilon)$-BAC. (See 16, 17 for explicit formulas for
$C_{\tau,\varepsilon},q$) If our prior were true—so the coins really were
$\tau\pm\varepsilon$—we would like to flip a $\tau+\varepsilon$ coin with
probability $q$. This is achieved by selecting the $q$-quantile of our
posterior, which is above the true threshold with probability $q$. If
$\tau=\frac{1}{2}$, $q=\frac{1}{2}$ and we query the median; in general, we
query the $q=\frac{1}{2}\pm O(\frac{\varepsilon}{\tau(1-\tau)})$ quantile.

$\Phi$ is a potential function that we will be analyzing.

We also define:

$\displaystyle d_{0,0}$
$\displaystyle=\frac{1-\tau-\varepsilon}{1-\tau-(2q-1)\varepsilon}$ (6)
$\displaystyle d_{0,1}$
$\displaystyle=\frac{1-\tau+\varepsilon}{1-\tau-(2q-1)\varepsilon}$ (7)
$\displaystyle d_{1,0}$
$\displaystyle=\frac{\tau+\varepsilon}{\tau+(2q-1)\varepsilon}$ (8)
$\displaystyle d_{1,1}$
$\displaystyle=\frac{\tau-\varepsilon}{\tau+(2q-1)\varepsilon}$ (9)

for brevity. In terms of BayesLearn we can think of $d_{x,y}$ as “the
multiplicative effect of a flip resulting in $x$
($1=\text{Heads},0=\text{Tails}$) on the density of an interval on side $y$
($1=\text{Right},0=\text{Left}$) of the flipped coin.” When
$\tau=\frac{1}{2}$, $d_{x,y}=1-2\varepsilon(-1)^{x\oplus y}$.

Algorithm 2 Acts as a Bayesian learner for $M$ iterations, returns a list of
all the chosen intervals. Expressions for the $d_{x,y}$ values are given in
(6), (7), (8), (9)

1:procedure getIntervalFromQuantile($w,q$)

2: $i\leftarrow\min{i\in[n]}$ s.t. $W(i)\geq q$

3:procedure roundIntervalToCoin($i,w,q$)

4: return $i$ if $\frac{q-W(i-1)}{w(i)}\leq q$ else $i+1$

5:procedure BayesLearn($\\{c_{i}\\}_{i=1}^{n},n,\tau,\varepsilon,M$)

6: $w_{1}\leftarrow\text{uniform}([n-1])$

7: Define $q$ as in (17) $\triangleright$ The quantile we choose

8: $L\leftarrow\\{\\}$

9: for $i\in[M]$ do

10: $j_{i}\leftarrow\textsc{getIntervalFromQuantile}(w_{i},q)$
$\triangleright$ The chosen interval

11: $x_{i}\leftarrow\textsc{roundIntervalToCoin}(j_{i},w_{i},q)$
$\triangleright$ The index of the coin we are going to flip

12: append $j_{i}$ to $L$

13: $y_{i}\leftarrow\textsc{flip}(c_{x_{i}})$

14: $w_{i+1}\leftarrow\begin{cases}w_{i}(x)d_{y_{i},0}&\mbox{if
}x\in\\{1,\dots,j_{i}-1\\}\\\
d_{y_{i},0}(q-W_{i}(j_{i}-1))+d_{y_{i},1}(W_{i}(j_{i})-q)&\mbox{if }x=j_{i}\\\
w(x)d_{y_{i},1}&\mbox{if }x\in\\{j_{i}+1,\dots,n-1\\}\end{cases}$ return $L$

###  3.2 Analysis

######  Lemma 3.1.

${\mathbb{E}}[\Phi_{t+1}-\Phi_{t}|y_{t},y_{t-1},\dots,y_{1}]\geq(1-O(\gamma))C_{\tau,\varepsilon}$.

###### Proof.

$\Phi$ is given by the sum of equations (10) and (11).

$6C_{\tau,\varepsilon}(|\\{j\in L|j\in[l,r]\\}|-\gamma|L|)$ (10)

$\lg w(a)$ (11)

Recall that in the $t$th round, $j_{t}$ is the interval chosen, and $x_{t}$ is
index of the coin flipped. Let $p$ be the probability $c_{x_{t}}$ lands heads.

#### Bad queries.

Suppose $j_{t}\notin[l,r]$. If $j_{t}>r$, then $p\geq\tau+\varepsilon$ and the
expected change in (11) is

$p\lg d_{1,0}+(1-p)\lg d_{0,0}$

The first $\log$ is positive and the second $\log$ is negative, so this
expression is minimized at $p=\tau+\varepsilon$, at which point some
computation (Lemma A.1) shows that it equals $C_{\tau,\varepsilon}$.
Similarly, if $x_{t}<l$ then $p\leq\tau-\varepsilon$ and the expected change
is

$p\lg d_{1,1}+(1-p)\lg d_{0,1}$

which is also at least $C_{\tau,\varepsilon}$ by Lemma A.1.

As $j_{t}\not\in[l,r]$, the change in (10) is $-\gamma\cdot
6C_{\tau,\varepsilon}$.

Therefore in this case the expected change in $\Phi$ is at least
$(1-6\gamma)C_{\tau,\varepsilon}$.

#### Good queries.

Suppose $j_{t}\in[l,r]$. The change in (10) is now
$6C_{\tau,\varepsilon}(1-\gamma)$. But how much can (11) decrease in
expectation?

Suppose that $j_{t}\neq a$. Then the expected change is either

$p\lg d_{1,0}+(1-p)\lg d_{0,0}$

with $p\geq\tau$, or

$p\lg d_{1,1}+(1-p)\lg d_{0,1}$

with $p\leq\tau$.

As
$d_{1,0}=\frac{\tau+\varepsilon}{\tau+(2q-1)\varepsilon}\geq\frac{1-\tau-\varepsilon}{1-\tau-(2q-1)\varepsilon}=d_{0,0}$
and
$d_{1,1}=\frac{\tau-\varepsilon}{\tau+(2q-1)\varepsilon}\leq\frac{1-\tau+\varepsilon}{1-\tau-(2q-1)\varepsilon}=d_{0,1}$,
both these expressions are minimized when $p=\tau$.

So the expected change in $\eqref{eq:term2}$ is lower bounded by:

$\min\left(\tau\lg d_{1,0}+(1-\tau)\lg d_{0,0},\tau\lg d_{1,1}+(1-\tau)\lg
d_{0,1}\right).$ (12)

We note that

$\displaystyle\tau\lg d_{1,0}+(1-\tau)\lg d_{0,0}$
$\displaystyle=(\tau+\varepsilon)\lg d_{1,0}+(1-\tau-\varepsilon)\lg
d_{0,0}-\varepsilon\lg d_{1,0}+\varepsilon\lg d_{0,0}$
$\displaystyle=C_{\tau,\varepsilon}-\varepsilon\lg d_{1,0}+\varepsilon\lg
d_{0,0}$ $\displaystyle\geq
C_{\tau,\varepsilon}-3\varepsilon(\frac{\varepsilon}{\tau}+\frac{\varepsilon}{1-\tau})$
Lemma A.5
$\displaystyle=C_{\tau,\varepsilon}-\frac{3\varepsilon^{2}}{\tau(1-\tau)}$
$\displaystyle\geq C_{\tau,\varepsilon}-(6\ln 2)C_{\tau,\varepsilon}$ Lemma
A.2 $\displaystyle\geq-5C_{\tau,\varepsilon}$

a symmetric argument for lower bounding $\tau\lg d_{1,1}+(1-\tau)\lg d_{0,1}$
holds. Therefore, the change in (11) is lower bounded by
$-5C_{\tau,\varepsilon}$.

Now suppose that $j_{t}=a$.

Then the expected change in (11) is:

$p\lg(d_{1,0}k+d_{1,1}(1-k))+(1-p)\lg(d_{0,0}k+d_{0,1}(1-k))$

for some $k\in[0,1]$.

If $k\leq q$ then we flip $a$ so $p\leq\tau$. $d_{0,0}k+d_{0,1}(1-k)\geq
d_{0,0}q+d_{0,1}(1-q)=1$. Also $d_{1,0}k+d_{1,1}(1-k)\leq
d_{1,0}q+d_{1,1}(1-q)=1$. Therefore, this expression is minimized when
$p=\tau$. By symmetry, when $k>q$ this expression is also minimized when
$p=\tau$.

So the expected change in $\eqref{eq:term2}$ is lower bounded by

$\tau\lg(d_{1,0}k+d_{1,1}(1-k))+(1-\tau)\lg(d_{0,0}k+d_{0,1}(1-k))$

for some $k\in[0,1]$.

Taking the derivative with respect to $k$, we get

$\tau\frac{d_{1,0}-d_{1,1}}{d_{1,1}+(d_{1,0}-d_{1,1})k}+(1-\tau)\frac{d_{0,0}-d_{0,1}}{d_{0,1}+(d_{0,0}-d_{0,1})k}$

As $d_{1,1}<d_{1,0}$ and $d_{0,1}>d_{0,0}$,
$\tau\frac{d_{1,0}-d_{1,1}}{d_{1,1}+(d_{1,0}-d_{1,1})k}>0>(1-\tau)\frac{d_{0,0}-d_{0,1}}{d_{0,1}+(d_{0,0}-d_{0,1})k}$.
We note that as $k$ increases,
$\tau\frac{d_{1,0}-d_{1,1}}{d_{1,1}+(d_{1,0}-d_{1,1})k}$ decreases in
magnitude, while $(1-\tau)\frac{d_{0,0}-d_{0,1}}{d_{0,1}+(d_{0,0}-d_{0,1})k}$
increases in magnitude. Therefore, the minimum value of the above expression
is achieved when $k=0$ or $k=1$.

So the expected change in $\eqref{eq:term2}$ is lower bounded by

$\min(\tau\lg d_{1,0}+(1-\tau)\lg d_{0,0},\tau\lg d_{1,1}+(1-\tau)\lg
d_{0,1})$

which is the same expression which we lower bounded for the $j_{t}\neq a$
case.

Combining these two cases, when the we are querying a good interval, the
expected change is lower bounded by
$6C_{\tau,\varepsilon}(1-\gamma)-5C_{\tau,\varepsilon}=(1-6\gamma)C_{\tau,\varepsilon}$

Therefore
${\mathbb{E}}[\Phi_{t+1}-\Phi_{t}|y_{t},y_{t-1},\dots,y_{1}]\geq(1-O(\gamma))C_{\tau,\varepsilon}$.

∎

Now we prove our key lemma.

See 1.6

###### Proof.

Recall that $\Phi$ is given by the sum of equations (10) and (11).

$6C_{\tau,\varepsilon}(|\\{j\in L|j\in[l,r]\\}|-\gamma|L|)$ (10)

$\lg w(a)$ (11)

#### Reduction to $\Phi>0$.

First note that $\Phi_{1}=-\lg(n-1)$, as initially $L$ is empty so (10) is
$0$, and we initialize $w$ as uniform so $w(a)=\frac{1}{n-1}$. Next note that
if $\eqref{eq:term1}>0$, then

$\displaystyle 6C_{\tau,\varepsilon}(|\\{x\in L|x\in[l,r]\\}|-\gamma|L|)$
$\displaystyle>0$ $\displaystyle|\\{x\in L|x\in[l,r]\\}|$
$\displaystyle>\gamma|L|$

So there are strictly more than $\gamma|L|$ good intervals in $L$. Next note
that (11) is $\leq 0$ always, so $\Phi>0\implies$(10) $>0$. So it suffices to
show that with $\delta$ failure probability $\Phi_{t+1}>0$, where
$t=\frac{1+O(\gamma)}{C_{\tau,\varepsilon}}(\lg n+O(\sqrt{\log
n\log\frac{1}{\delta}}+\log\frac{1}{\delta}))$

#### Establishing a submartingale.

Note by a stochastic domination argument, we can consider the worst case where
all coins sampled have bias in $[\tau-\varepsilon,\tau+\varepsilon]$.

Let $\sigma_{i}^{2}$ be the variance of the difference random variables
$\Phi_{i+1}-\Phi_{i}$, then we note that $\sigma_{i}^{2}$ is a Bernoulli
random variable with parameter $p\in[\tau-\varepsilon,\tau+\varepsilon]$, that
is scaled by at most a $\max(\lg d_{1,0}-\lg d_{0,0},\lg d_{0,1}-\lg
d_{1,1})\lesssim\frac{\varepsilon}{\tau(1-\tau)}$ factor, therefore

$\displaystyle\sigma_{i}^{2}\lesssim
p(1-p)\left(\frac{\varepsilon}{\tau(1-\tau)}\right)^{2}\lesssim\tau(1-\tau)\left(\frac{\varepsilon}{\tau(1-\tau)}\right)^{2}=\frac{\varepsilon^{2}}{\tau(1-\tau)}\lesssim
C_{\tau,\varepsilon}$

Where we use the fact that
$\varepsilon\leq\frac{\min\left(\tau,1-\tau\right)}{2}$.

Therefore $\sigma_{i}^{2}\lesssim C_{\tau,\varepsilon}$.

#### Freedman’s inequality.

For brevity let $g=(1-O(\gamma))C_{\tau,\varepsilon}$, the lower bound given
in Lemma 3.1.

$\displaystyle\Pr[\Phi_{t+1}\leq 0]$
$\displaystyle=\Pr[\Phi_{t+1}-\Phi_{1}\leq-\Phi_{1}]$
$\displaystyle=\Pr[\Phi_{t+1}-gt-\Phi_{1}\leq-gt-\Phi_{1}]$
$\displaystyle\leq\exp\left(-\frac{2(-gt-\Phi_{1})^{2}}{\sum_{i=1}^{t}\sigma_{i}^{2}+O(\frac{\varepsilon}{\tau(1-\tau)})(gt+\Phi_{1})}\right)$
$\displaystyle\text{Freedman's when }gt\geq-\Phi_{1}$
$\displaystyle\leq\exp(-\frac{O(1)}{tC_{\tau,\varepsilon}}\cdot(-gt-\Phi_{1})^{2})$
$\displaystyle=\exp(-\frac{O(1)}{tC_{\tau,\varepsilon}}\cdot(g^{2}t^{2}+2gt\Phi_{1}+\Phi_{1}^{2}))$

Bounding this expression by $\delta$, we get

$\displaystyle\exp\left(-\frac{O(1)}{tC_{\tau,\varepsilon}}\cdot(g^{2}t^{2}+2gt\Phi_{1}+\Phi_{1}^{2})\right)$
$\displaystyle\leq\delta$ $\displaystyle g^{2}t^{2}+2g\Phi_{1}t+\Phi_{1}^{2}$
$\displaystyle\geq\log_{O(1)}(1/\delta)tC_{\tau,\varepsilon}$ $\displaystyle
g^{2}t^{2}+(2g\Phi_{1}-\log_{O(1)}(1/\delta)C_{\tau,\varepsilon})t+\Phi_{1}^{2}$
$\displaystyle\geq 0$ (13)

(13) is a quadratic with respect to $t$, and has a positive leading
coefficient. Applying the quadratic formula, if we set

$\displaystyle t$
$\displaystyle\geq\frac{-(2g\Phi_{1}-\log_{O(1)}(1/\delta)C_{\tau,\varepsilon})+\sqrt{(2g\Phi_{1}-\log_{O(1)}(1/\delta)C_{\tau,\varepsilon})^{2}-4g^{2}\Phi_{1}^{2}}}{2g^{2}}$
$\displaystyle=\frac{-(2g\Phi_{1}-\log_{O(1)}(1/\delta)C_{\tau,\varepsilon})+\sqrt{(\log_{O(1)}(1/\delta)C_{\tau,\varepsilon})^{2}-4g\Phi_{1}\log_{O(1)}(1/\delta)C_{\tau,\varepsilon}}}{2g^{2}}$
$\displaystyle=\frac{-\Phi_{1}}{g}+\frac{C_{\tau,\varepsilon}\log_{O(1)}(1/\delta)}{2g^{2}}+\frac{\sqrt{(\log_{O(1)}(1/\delta)C_{\tau,\varepsilon})^{2}-4g\Phi_{1}\log_{O(1)}(1/\delta)C_{\tau,\varepsilon}}}{2g^{2}}$
(14)

then $(\ref{eq1})$ holds.

As $\Phi_{1}=-\lg(n-1),g=(1-O(\gamma))C_{\tau,\varepsilon}$ we get that (14)
is

$\frac{1}{1-O(\gamma)}\cdot\frac{1}{C_{\tau,\varepsilon}}(\lg n+O(\sqrt{\log
n\log\frac{1}{\delta}}+\log\frac{1}{\delta}))$

As $\frac{1}{1-O(\gamma)}$ is $1+O(\gamma)$, our lemma holds. ∎

##  4 Algorithm and Analysis

Algorithm 3 Noisy Binary Search. It recurses at most once.

1:procedure
ReductionToGamma($\\{c_{i}\\}_{i=1}^{n},n,\tau,\varepsilon,\delta,\gamma$)

2:
$L\leftarrow\textsc{BayesLearn}(\\{c_{i}\\}_{i=1}^{n},n,\tau,\varepsilon,\frac{1+O(\gamma)}{C_{\tau,\varepsilon}}(\lg
n+O(\sqrt{\log n\log\frac{1}{\delta}}+\log\frac{1}{\delta})))$

3: $R\leftarrow\\{\\}$

4: for $i\in[{\lfloor\frac{|L|}{{\lceil\gamma|L|\rceil}}\rfloor}]$ do

5: append $L_{{\lceil\gamma|L|\rceil}i}$ to $R$ return
$\textsc{removeDuplicates}(R)$

6:procedure
BayesianScreeningSearch($\\{c_{i}\\}_{i=1}^{n},n,\tau,\varepsilon,\delta,\gamma=\frac{1}{7\lg(n)}$)

7:
$\varepsilon^{\prime}=\varepsilon\cdot\max(1-\sqrt[3]{\log_{n}(1/\delta)},\frac{2}{3})$

8:
$R\leftarrow\textsc{ReductionToGamma}(\\{c_{i}\\}_{i=1}^{n},n,\tau,\varepsilon^{\prime},\delta/3,\frac{1}{3\lg(n)})$

9: if $|R|>7$ then

10: $R\leftarrow[1]+R+[n]$ $\triangleright$ Pad $R$ with the extremes of the
initial problem.

11:
$i\leftarrow\textsc{BayesianScreeningSearch}(\\{c_{R_{i}}\\}_{i=1}^{|R|},|R|,\tau,\varepsilon^{\prime},\delta/3,\frac{1}{7})$

12: $\hat{p}_{R_{i}+1}\leftarrow\text{estimate }p_{R_{i}+1}\text{ up to
}\pm\frac{\varepsilon-\varepsilon^{\prime}}{2}\text{ error with
}\delta/3\text{ f.p.}$

13: if
$\hat{p}_{R_{i}+1}>\tau-\varepsilon+\frac{\varepsilon-\varepsilon^{\prime}}{2}$
then

14: return $R_{i}$

15: else

16: return $R_{i+1}-1$

17: else

18: for $x\in R$ do

19: $\hat{p}_{x+1}\leftarrow\text{estimate }p_{x+1}\text{ up to
}\pm\frac{\varepsilon-\varepsilon^{\prime}}{2}\text{ error with
}\delta/18\text{ f.p.}$

20: if
$\hat{p}_{x+1}>\tau-\varepsilon+\frac{\varepsilon-\varepsilon^{\prime}}{2}$
then

21: return $x$

Algorithm 4 Noisy Binary Search that gets the optimal expected queries.

1:procedure
SillyBayesianScreeningSearch($\\{c_{i}\\}_{i=1}^{n},n,\tau,\varepsilon,\delta$)

2: return $\begin{cases}\textsc{Random}([n-1])&\text{w.p. }\delta-\delta/\lg
n\\\
\textsc{BayesianScreeningSearch}(\\{c_{i}\\}_{i=1}^{n},n,\tau,\varepsilon,\frac{\delta}{\ln(n)})&\text{otherwise}\end{cases}$

See 1.1

###### Proof.

#### Correctness.

Suppose that we run BayesianScreeningSearch on a MonotonicNBS instance with
parameters $\\{c_{i}\\}_{i=1}^{n},n,\tau,\varepsilon,\delta$.

Assume that all probabilistic stages succeed, meaning that ReductionToGamma,
BayesianScreeningSearch, and our coin bias estimation all succeed. By a union
bound, this occurs with probability $\geq 1-\delta$.

As we pick every $\gamma|L|$th coin from $L$ and $L$ contains at least
${\lceil\gamma|L|\rceil}$ $\varepsilon^{\prime}$-good intervals, $R$ contains
at least one $\varepsilon^{\prime}$-good interval. Suppose that $|R|\leq 7$
and that $R_{i}$ is the first $\varepsilon^{\prime}$-good interval in $R$.

Then for all $j\in\\{1,\dots,i-1\\}$, either $R_{j}$ is an $\varepsilon$-good
interval or it is not. If it is, then we have nothing to worry about
outputting it. If it is not, then $p_{R_{j}+1}\leq\tau-\varepsilon$ (as if
$p_{R_{j}+1}\geq\tau+\varepsilon$ then $R_{i}$ is not $\varepsilon$-good), so
$\hat{p}_{R_{j}+1}\leq\tau-\varepsilon+\frac{\varepsilon-\varepsilon^{\prime}}{2}$.
So we do not output any not $\varepsilon$-good interval before $R_{i}$.

Once we reach $R_{i}$, $p_{R_{i}+1}>\tau-\varepsilon^{\prime}$, so
$\hat{p}_{R_{i}+1}>\tau-\varepsilon^{\prime}-\frac{\varepsilon-\varepsilon^{\prime}}{2}=\tau-\varepsilon+\frac{\varepsilon-\varepsilon^{\prime}}{2}$
and we output $R_{i}$.

Now suppose that $|R|>7$. As we recursively run BayesianScreeningSearch with
$\gamma=1/7$, we note that for the $R$ in the recursive call $R^{\prime}$,
$|R^{\prime}|={\lfloor\frac{|L|}{{\lceil\gamma|L|\rceil}}\rfloor}\leq{\lfloor\frac{1}{\gamma}\rfloor}=7$,
so $|R^{\prime}|\leq 7$. By our work above, this means that the recursive call
returns $i$ such that
$[p_{R_{i}},p_{R_{i+1}}]\cap(\tau-\varepsilon^{\prime},\tau+\varepsilon^{\prime})\neq\emptyset$.

Either $R_{i}$ or $R_{i+1}-1$ is $\varepsilon^{\prime}$-good, as if
$p_{R_{i}+1}\leq\tau-\varepsilon^{\prime}$ and
$p_{R_{i+1}}-1\geq\tau+\varepsilon^{\prime}$ then $R$ must not contain any
good intervals. The same logic as for the $|R|\leq 7$ case holds, and we have
shown correctness.

#### Number of samples.

Next we analyze the sample budget.

Suppose that we run BayesianScreeningSearch with $\gamma=1/7$.

The ReductionToGamma call takes

$\displaystyle\frac{1+O(\gamma)}{C_{\tau,\varepsilon^{\prime}}}\left(\lg
n+O(\sqrt{\log n\log\frac{1}{\delta}}+\log\frac{1}{\delta})\right)$
$\displaystyle=\frac{1}{C_{\tau,\varepsilon}}O(\log n+\log\frac{1}{\delta})$

samples.

As we have $\gamma=1/7$, $|R|\leq 7$ and we go through the second branch.

Then the bias estimation takes
$O(\frac{\tau(1-\tau)\log\frac{1}{\delta}}{(\varepsilon-(1-\sqrt[3]{\log_{n}\frac{1}{\delta}})\varepsilon)^{2}})=O(\frac{\tau(1-\tau)\log\frac{1}{\delta}}{(\varepsilon\sqrt[3]{\log_{n}\frac{1}{\delta}})^{2}})=O(\frac{\log^{2/3}n\log^{1/3}\frac{1}{\delta}}{C_{\tau,\varepsilon}})$
samples, for overall $\frac{1}{C_{\tau,\varepsilon}}O(\log
n+\log\frac{1}{\delta})$ samples.

Now consider the case $\gamma=\frac{1}{7\lg n}$, and suppose that
$1-\sqrt[3]{\log_{n}(1/\delta)}\geq 2/3$.

ReductionToGamma takes, with
$\gamma=O(1/\log(n)),\varepsilon^{\prime}=\varepsilon*(1-\sqrt[3]{\log_{n}(1/\delta)})$:

$\displaystyle\frac{1+O(\gamma)}{C_{\tau,\varepsilon^{\prime}}}\left(\lg
n+O(\sqrt{\log n\log\frac{1}{\delta}}+\log\frac{1}{\delta})\right)$
$\displaystyle=\frac{1+O(\frac{1}{\log
n})}{C_{\tau,\varepsilon^{\prime}}}\cdot\left(\lg n+O(\sqrt{\log
n\log\frac{1}{\delta}}+\log\frac{1}{\delta})\right)$
$\displaystyle=\frac{1}{C_{\tau,\varepsilon^{\prime}}}\cdot\left(\lg
n+O(\sqrt{\log n\log\frac{1}{\delta}}+\log\frac{1}{\delta})\right)$
$\displaystyle=\frac{1}{(1-O(\sqrt[3]{\log_{n}(1/\delta)})C_{\tau,\varepsilon}}\cdot\left(\lg
n+O(\sqrt{\log n\log\frac{1}{\delta}}+\log\frac{1}{\delta})\right)$ (Lemma
A.4)

samples, which is $\frac{1}{C_{\tau,\varepsilon}}\cdot\left(\lg
n+O(\log^{2/3}n\log^{1/3}\frac{1}{\delta}+\log\frac{1}{\delta})\right)$.

If $|R|\leq 7$ we take the second branch and take
$O(\frac{\log^{2/3}n\log^{1/3}\frac{1}{\delta}}{C_{\tau,\varepsilon}})$ more
samples, which meets our bound.

If $|R|>7$ we take the first branch and recurse with $\gamma=1/7$ and
$n^{\prime}=O(\log n)$, for $\frac{1}{C_{\tau,\varepsilon}}O(\log\log
n+\log\frac{1}{\delta})$ samples.

As established previously, the bias estimation takes
$O(\frac{\log^{2/3}n\log^{1/3}\frac{1}{\delta}}{C_{\tau,\varepsilon}})$
samples.

For overall

$\frac{1}{C_{\tau,\varepsilon}}(\lg
n+O(\log^{2/3}n\log^{1/3}\frac{1}{\delta}+\log\frac{1}{\delta}))$

samples.

In the case $1-\sqrt[3]{\log_{n}(1/\delta)}<2/3$, the
$\frac{O(\log\frac{1}{\delta})}{C_{\tau,\varepsilon}}$ term dominates the
rest, and the bound holds. ∎

See 1.3

###### Proof.

The failure probability of SillyBayesianScreeningSearch is
$\leq\delta-\delta/\lg n+(1-\delta+\delta/\lg n)\delta/\lg
n=\delta-\delta^{2}/\lg n+\delta^{2}/\lg^{2}n\leq\delta$.

We use $0$ samples with probability $\delta-\delta/\lg n$, and the expression
in Theorem 1.1 with $\delta^{\prime}=\delta/\lg n$, with probability
$1-\delta+\delta/\lg n$. ∎

##  5 Lower Bounds

######  Lemma 5.1.

Given any algorithm $\mathcal{A}$ which solves $NBS$ for parameters
$(\tau,\varepsilon)$ with sample budget $m$ and failure probability $\delta$,
there exists a protocol that communicates over a discrete memoryless channel
with capacity $C_{\tau,\varepsilon}$ with rate $R=\frac{\lg(n-1)}{m}$ with
failure probability $\delta$.

###### Proof.

Let channel $\mathcal{C}$ be a $(\tau,\varepsilon)$-BAC with shared randomness
and perfect feedback.
Binary asymmetric channels are discrete memoryless channels, and so neither
feedback nor shared randomness change its channel capacity. [Sha56] Therefore,
the capacity of $\mathcal{C}$ is $C_{\tau,\varepsilon}$.
Suppose we have agents $A$ and $B$, and $A$ wishes to communicate a message
$x^{*}\in[n-1]$ to $B$ over $\mathcal{C}$. Also assume without loss of
generality $\mathcal{A}$ always flips a coin exactly $m$ times.

Both $A$ and $B$ can run an identical copy of $\mathcal{A}$, as we have shared
randomness. When the algorithm flips a coin $x^{*}$, $A$ sends $B$ $1$ if
$x^{*}<x$, and $0$ otherwise. Then if $x^{*}<x$, $B$ receives $1$ with
probability $\tau+\varepsilon$, and $0$ with probability $1-\tau-\varepsilon$.
If $x^{*}\geq x$, then $B$ receives $1$ with probability $\tau-\varepsilon$
and $0$ with probability $1-\tau+\varepsilon$. With perfect feedback we can
have $A$ receive the same value that $B$ received. Note that to $B$ this is
just an NBS problem with parameters $n,\tau,\varepsilon$, and so it
successfully recovers $x^{*}$ with probability $\geq 1-\delta$. The rate of
our simulated code is $R=\frac{\lg(n-1)}{m}$, and so the lemma holds. ∎

Now we can use lower bounds from information theory.

######  Lemma 5.2 (Shannon’s Strong Converse Theorem).

Over any discrete memoryless channel, for $R>C$

$P_{e}\geq 1-\frac{K_{1}}{n(R-C)^{2}}-\exp(-K_{2}n(R-C))$

where $P_{e}$ is the probability of error, $K_{1},K_{2}$ are positive
constants which depend on the channel, $n$ is the input alphabet size, $R$ is
the rate of information, and $C$ is the channel capacity [Gal68]

See 1.2

###### Proof.

Let $\alpha=\frac{1}{1+\frac{K}{C_{\tau,\varepsilon}\sqrt{\beta(n-1)}}}$, for
constant $K$ to be determined later. Suppose that $\mathcal{A}$ uses at most
$\alpha\frac{\lg(n-1)}{C_{\tau,\varepsilon}}$ samples with probability at
least $\delta+\beta$. Let $\mathcal{A}^{\prime}$ be the algorithm that runs
$\mathcal{A}$, but outputs a random answer if $\mathcal{A}$ uses more than
$\alpha\frac{\lg(n-1)}{C_{\tau,\varepsilon}}$ samples. $\mathcal{A}^{\prime}$
fails only whenever $\mathcal{A}$ fails or uses more than
$\alpha\frac{\lg(n-1)}{C_{\tau,\varepsilon}}$ samples, so by a union bound
$\mathcal{A}^{\prime}$ has a failure probability of at most $1-\beta$.

By Lemma 5.1 we can construct a protocol over a discrete memoryless channel
with capacity $C_{\tau,\varepsilon}$ that communicates at rate
$R=\frac{\lg(n-1)}{\frac{\alpha\lg(n-1)}{C_{\tau,\varepsilon}}}=\frac{C_{\tau,\varepsilon}}{\alpha}=\frac{C}{\alpha}$
with a failure probability of at most $1-\beta$.

By Lemma 5.2 we have that

$\displaystyle 1-\beta$ $\displaystyle\geq
1-\frac{K_{1}}{(n-1)(R-C)^{2}}-\exp(-K_{2}(n-1)(R-C))$
$\displaystyle=1-\frac{K_{1}}{(n-1)((1/\alpha-1)C)^{2}}-\exp(-(n-1)K_{2}((1/\alpha-1)C))$
$\displaystyle=1-\frac{K_{1}\beta}{K}-\exp(-\sqrt{\frac{n-1}{\beta}}K_{2}K)$
$\displaystyle\geq 1-\frac{\beta}{2}$ $\displaystyle\text{sufficiently large
}K\text{ and }n$

which is a contradiction. Therefore with probability at least $1-\delta-\beta$
$\mathcal{A}$ uses
$\frac{1}{1+\frac{K}{\sqrt{\beta(n-1)}(C_{\tau,\varepsilon})}}\frac{1}{C_{\tau,\varepsilon}}\lg
n$ samples.

∎

We can also lower bound the expected number of samples.

See 1.4

###### Proof.

Suppose we have algorithm $\mathcal{A}$ which uses $q$ samples in expectation
to solve NBS with $\delta$ failure probability. By Lemma 5.1 and Fano’s
inequality $\lg(n-1)-qC_{\tau,\varepsilon}\leq
1+\delta\lg(n-2)\implies(1-\delta)\lg(n-2)-1\leq
qC_{\tau,\varepsilon}\implies(1-\delta)\frac{\lg(n-2)-1}{C_{\tau,\varepsilon}}\leq
q$. ∎

##  6 Experiments

#### Applying NBS.

To demonstrate the practicality of BayesianScreeningSearch we compare it to
standard binary search with repetition (NaiveNBS) and the two algorithms of
[KK07] (KKBacktracking and KKMultiplicativeWeights).

To fairly compare between these algorithms, we can’t just use the descriptions
given in [KK07], as the constants used in analysis are not optimized. We
leverage BayesianScreeningSearch to address this. We tweak the listed
algorithms so they take a sample budget as input which they allocate among all
their stages. To estimate how large a budget is needed for algorithm
$\mathcal{A}$ to perform well on distribution $\mathcal{D}$, we run
BayesianScreeningSearch where when the $i$th coin is flipped we run
$\mathcal{A}$ on some input drawn from $\mathcal{D}$, and return $1$ if
$\mathcal{A}$ succeeds and $0$ if $\mathcal{A}$ fails. By setting $\tau=.8,.9$
and $\varepsilon=.05$, we get upper and lower bounds for how many samples is
needed to get $\delta=.15$ failure probability.

#### Experiments.

We compare results on 4 different problem distributions: Standard, Biased,
Lopsided, and Wide.

  * Standard

$p_{i}\in\\{\tau-\varepsilon,\tau+\varepsilon\\}$,
$\tau=\frac{1}{2},\varepsilon=.1$, the transition interval chosen uniformly at
random..

  * Biased

$p_{i}\in\\{\tau-\varepsilon,\tau+\varepsilon\\},\tau=\frac{3}{4},\varepsilon=.1$,
the transition interval chosen uniformly at random.

  * Lopsided

$p_{i}\in\\{\tau-.6\varepsilon,\tau+\varepsilon\\}$,
$\tau=\frac{1}{2},\varepsilon=.1$, the transition interval chosen uniformly at
random..

  * Wide

we choose an interval (uniformly at random) of size $10\ln n$ that linearly
interpolates between $\tau-\varepsilon$ and $\tau+\varepsilon$, and set the
rest to be
$p_{i}\in\\{\tau-\varepsilon,\tau+\varepsilon\\},\tau=\frac{1}{2},\varepsilon=.1$.

#### Results.

We remark that KKBacktracking performed markedly worse than the other
algorithms, and so is not included in the figures. For reference, for
$\textsc{Standard},N=1000$ KKBacktracking required $m>2.9\times 10^{6}$
samples, while the other algorithms need $m<6000$ samples (see Figure 3).

Figure 3: Performance of various MonotonicNBS algorithms for listed
distributions.

We find that KKMultiplicativeWeights is outperformed by NaiveNBS on all of
these distributions. In contrast, BayesianScreeningSearch outperforms NaiveNBS
for $n>10^{3}$.

When $\tau\neq\frac{1}{2}$ the difference between BayesianScreeningSearch,
NaiveNBS and the [KK07] algorithms increases. This is in line with our theory,
as the first two perform better when $\tau$ is further from $\frac{1}{2}$,
while the [KK07] algorithms reduce to the case $\tau=\frac{1}{2}$, losing a
constant factor.

####  BayesianScreeningSearch variant.

Since BayesianScreeningSearch has a large set of parameters to tune, we use a
simpler variant. We run BayesianScreeningSearch as normal but we use
$\varepsilon$ to update instead of $\varepsilon^{\prime}$ when running
BayesLearn. This can be shown to satisfy Theorem 1.1 as well.

To see that this gets the same constant, suppose we are trying to run
BayesLearn with parameters $n,\tau,(1-\alpha)\varepsilon$, but in the actual
algorithm we use $\varepsilon$ instead of $(1-\alpha)\varepsilon$. Then the
expected gain in $\Phi$ when the chosen interval is above the good range is

$\displaystyle(\tau+(1-\alpha)\varepsilon)\lg
d_{1,0}+(1-\tau-(1-\alpha)\varepsilon)\lg d_{0,0}$
$\displaystyle=C_{\tau,\varepsilon}-\alpha\varepsilon*\lg\frac{\frac{\tau+\varepsilon}{\tau+(2q-1)\varepsilon}}{\frac{1-\tau-\varepsilon}{1-\tau-(2q-1)\varepsilon}}$
$\displaystyle\geq
C_{\tau,\varepsilon}-\alpha*O(\frac{\varepsilon^{2}}{\tau(1-\tau)})$
$\displaystyle=(1-O(\alpha))C_{\tau,\varepsilon}$

The case when the chosen interval is below the good range of intervals is
symmetric. When the chosen interval is good, we can see that the loss is
-$\Theta(C_{\tau,\varepsilon})$ using the same work as in Lemma 1.6. So
setting $\alpha=\sqrt[3]{\log_{n}\frac{1}{\delta}}$ we get the same constant
as BayesianScreeningSearch.

We set $\gamma=\frac{1}{\ln^{2}n}$, and addition, when we recurse on
$1/\gamma$ elements we run NaiveNBS to find the $2$ coins out of the possible
$7$ to test.

#### Implementation details.

To run noisy binary search on each algorithm we need to modify each algorithm
to “solve NBS with a given sample budget,” instead of “given a NBS instance
solve it with as few samples as possible.” In this section we discuss
implementation decisions made.

To efficiently implement BayesianScreeningSearch we use a lazily initialized
segment tree, to perform any operations on $w$ in $O(\log n)$ time. When
running the algorithm with a sample budget $b$, $\frac{\lg
n}{C_{\tau,\varepsilon}}$ was allocated to the ReductionToGamma call,
$O(\frac{b\log\log n}{C_{\tau,\varepsilon}})$ was allocated to the Recursive
BayesianScreeningSearch call, and $O(\frac{1}{C_{\tau,\varepsilon}})$ was
allocated to the final bias estimation call, and the remaining budget is split
among the three stages evenly.

To efficiently implement KKMultiplicativeWeights we also use a lazily
initialized segment tree. When running the algorithm with a sample budget $b$,
we determine the maximum number of iterations of update step we can do with
this budget and perform this many steps. (In terms of the original paper, we
noisy binary search on $T(n)$).

For NaiveNBS, for a sample budget $b$ we allocate the number of flips evenly
to each of the $\lg n$ steps of the algorithm.

For KKBacktracking we make no modifications, as the algorithm is structured to
eventually output an answer but we do not have limits on the number of samples
for any stage. So when running the algorithm with sample budget $b$ we cause
it to fail if the algorithm uses more than $b$ samples.

##  7 Future Work

One interesting topic of research is _instance-dependent_ noisy binary search.
If an instance is much nicer than the worst case, say every coin has bias
$\frac{1}{2}\pm\alpha$ for $\alpha\gg\varepsilon$, we would hope to get a
$O(\frac{\log n}{\alpha^{2}})$ dependence, which BayesianScreeningSearch does
not get. One could use an adaptive coin bias estimator to get some adaptivity,
but the constants gotten from this will likely not be good.

Another open problem is attenuating the lower order terms in the upper bound
for NBS. For realistic $n$, lower order terms such as $\sqrt{\log n}$, or even
$\log\log n$ are not negligible compared to $\log n$, and influences the
practical application of BayesianScreeningSearch, as seen in the experimental
results where we spent $28\%$ of our samples on the “lower order” recursive
calls.

One conjectural algorithm for noisy binary search would be: run BayesLearn for
$(1+O(\gamma))OPT$ steps, then output the median of the last $\gamma OPT$
intervals chosen. This interpolates between the overall median (which loses a
constant factor) and the final interval (which has a large probability of
failure), and avoids the inefficiency of recursive calls.

## References

  * [Sha56] Claude Shannon  “The zero error capacity of a noisy channel”  In _IRE Transactions on Information Theory_ 2.3 IEEE, 1956, pp. 8–19
  * [Gal68] Robert G Gallager  “Information theory and reliable communication”  Springer, 1968
  * [BZ74] Marat Valievich Burnashev and Kamil’Shamil’evich Zigangirov  “An interval estimation problem for controlled observations”  In _Problemy Peredachi Informatsii_ 10.3 Russian Academy of Sciences, Branch of Informatics, Computer Equipment and …, 1974, pp. 51–61
  * [Pel02] Andrzej Pelc  “Searching games with errors—fifty years of coping with liars”  In _Theoretical Computer Science_ 270.1, 2002, pp. 71–109  DOI: https://doi.org/10.1016/S0304-3975(01)00303-6
  * [KK07] Richard M. Karp and Robert Kleinberg  “Noisy Binary Search and Its Applications”  In _Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’07  New Orleans, Louisiana: Society for IndustrialApplied Mathematics, 2007, pp. 881–890
  * [BH08] Michael Ben-Or and Avinatan 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  DOI: 10.1109/FOCS.2008.58
  * [Now09] Robert Nowak  “Noisy Generalized Binary Search”  In _Advances in Neural Information Processing Systems_ 22 Curran Associates, Inc., 2009  URL: https://proceedings.neurips.cc/paper/2009/file/556f391937dfd4398cbac35e050a2177-Paper.pdf
  * [WFH13] Rolf Waeber, Peter I. Frazier and Shane G. Henderson  “Bisection Search with Noisy Responses”  In _SIAM Journal on Control and Optimization_ 51.3, 2013, pp. 2261–2279  DOI: 10.1137/120861898
  * [EKS16] Ehsan Emamjomeh-Zadeh, David Kempe and Vikrant Singhal  “Deterministic and Probabilistic Binary Search in Graphs”  In _Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’16  Cambridge, MA, USA: Association for Computing Machinery, 2016, pp. 519–532  DOI: 10.1145/2897518.2897656
  * [DGTU18] Dariusz Dereniowski, Daniel Graf, Stefan Tiegel and Przemyslaw Uznanski  “A Framework for Searching in Graphs in the Presence of Errors”  In _CoRR_ abs/1804.02075, 2018  arXiv: http://arxiv.org/abs/1804.02075
  * [DGPP18] Ilias Diakonikolas, Themis Gouleakis, John Peebles and Eric Price  “Sample-optimal identity testing with high probability”  In _45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)_ , 2018  Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
  * [Cru20] Adam Crume  “Robust Binary Search”  In _GitHub repository_ GitHub, https://github.com/adamcrume/robust-binary-search, 2020
  * [DLU21] Dariusz Dereniowski, Aleksander Lukasiewicz and Przemyslaw Uznanski  “Noisy searching: simple, fast and correct”  In _CoRR_ abs/2107.05753, 2021  arXiv: https://arxiv.org/abs/2107.05753
  * [TS22] Bernard Teo and Jonathan Scarlett  “Noisy Adaptive Group Testing via Noisy Binary Search”  In _IEEE Trans. Inf. Theory_ 68.5, 2022, pp. 3340–3353  DOI: 10.1109/TIT.2022.3140604
  * [WGZW22] Ziao Wang, Nadim Ghaddar, Banghua Zhu and Lele Wang  “Noisy sorting capacity”  In _2022 IEEE International Symposium on Information Theory (ISIT)_ , 2022, pp. 2541–2546  IEEE
  * [GX23] Yuzhou Gu and Yinzhan Xu  “Optimal Bounds for Noisy Sorting”  In _STOC_ , 2023  DOI: 10.48550/ARXIV.2302.12440

##  Appendix A Computations

This section gives the proof of some approximations used in the body of the
paper.

We give explicit formulas for some functions used in this paper

$\displaystyle z$
$\displaystyle=2^{\frac{H(\tau-\varepsilon)-H(\tau+\varepsilon)}{2\varepsilon}}$
(15) $\displaystyle C_{\tau,\varepsilon}$
$\displaystyle=\lg(z+1)+\frac{\tau-\epsilon}{2\epsilon}H(\tau+\epsilon)-\frac{\tau+\epsilon}{2\epsilon}H(\tau-\epsilon)$
(16) $\displaystyle q$
$\displaystyle=\frac{\left(1-\tau+\varepsilon\right)-\frac{1}{1+z}}{2\varepsilon}$
(17)

######  Lemma A.1.

$C_{\tau,\varepsilon}=(\tau+\epsilon)\lg(\frac{\tau+\epsilon}{\tau+(2q-1)\varepsilon})+(1-\tau-\epsilon)\lg(\frac{1-\tau-\epsilon}{1-\tau-(2q-1)\varepsilon})$

and

$C_{\tau,\varepsilon}=(\tau-\epsilon)\lg(\frac{\tau-\epsilon}{\tau+(2q-1)\varepsilon})+(1-\tau+\epsilon)\lg(\frac{1-\tau+\epsilon}{1-\tau-(2q-1)\varepsilon})$

###### Proof.

$\tau+(2q-1)\varepsilon=\tau+\varepsilon-\frac{1}{1+z}+(1-\tau-\varepsilon)=1-\frac{1}{1+z}$
and similarly
$1-\tau-(2q-1)\varepsilon=1-\tau-\varepsilon+\frac{1}{1+z}+(1-\tau-\varepsilon)=\frac{1}{1+z}$.
Then the first result is

$\displaystyle\qquad(\tau+\epsilon)\lg(\frac{\tau+\epsilon}{1-\frac{1}{1+z}})+(1-\tau-\epsilon)\lg(\frac{1-\tau-\epsilon}{\frac{1}{1+z}})$
$\displaystyle=-H(\tau+\epsilon)+(\tau+\epsilon)\lg(\frac{z+1}{z})+(1-\tau-\epsilon)\lg(z+1)$
$\displaystyle=-H(\tau+\epsilon)+\lg(z+1)+(\tau+\epsilon)\lg(\frac{1}{z})$
$\displaystyle=-H(\tau+\epsilon)+\lg(z+1)-(\tau+\epsilon)(\frac{H(\tau-\epsilon)-H(\tau+\epsilon)}{2\epsilon})$
$\displaystyle=\lg(z+1)+\frac{\tau-\epsilon}{2\epsilon}H(\tau+\epsilon)-\frac{\tau+\epsilon}{2\epsilon}H(\tau-\epsilon)$
$\displaystyle=C_{\tau,\epsilon}.$

and similarly,

$\displaystyle\qquad(\tau-\epsilon)\lg(\frac{\tau-\epsilon}{1-\frac{1}{1+z}})+(1-\tau+\epsilon)\lg(\frac{1-\tau+\epsilon}{\frac{1}{1+z}})$
$\displaystyle=-H(\tau-\epsilon)+(\tau-\epsilon)\lg(\frac{z+1}{z})+(1-\tau+\epsilon)\lg(z+1)$
$\displaystyle=-H(\tau-\epsilon)+\lg(z+1)+(\tau-\epsilon)\lg(\frac{1}{z})$
$\displaystyle=-H(\tau-\epsilon)+\lg(z+1)-(\tau-\epsilon)(\frac{H(\tau-\epsilon)-H(\tau+\epsilon)}{2\epsilon})$
$\displaystyle=\lg(z+1)+\frac{\tau-\epsilon}{2\epsilon}H(\tau+\epsilon)-\frac{\tau+\epsilon}{2\epsilon}H(\tau-\epsilon)$
$\displaystyle=C_{\tau,\epsilon}.$

∎

######  Lemma A.2.

For $\varepsilon\leq\frac{1}{2}\min(\tau,1-\tau)$,

$\frac{1}{2\ln 2}\frac{\varepsilon^{2}}{\tau(1-\tau)}\leq
C_{\tau,\varepsilon}\leq\frac{1}{\ln 2}\frac{\varepsilon^{2}}{\tau(1-\tau)}.$

###### Proof.

Note that $H^{(2)}(x)=\frac{-1}{(\ln 2)x(1-x)}$ and $H^{(4)}(x)=-\frac{2}{\ln
2}\left(\frac{1}{(1-x)^{3}}+\frac{1}{x^{3}}\right)\leq 0$ for all $x$.

For the lower bound, by the definition of channel capacity,
$C_{\tau,\varepsilon}$ is at least the information gained when choosing the
median, i.e.,

$\displaystyle C_{\tau,\varepsilon}$
$\displaystyle=\max_{q}H(\tau+(2q-1)\varepsilon)-(qH(\tau+\varepsilon)+(1-q)H(\tau-\varepsilon))$
$\displaystyle\geq
H(\tau)-\frac{1}{2}\left(H(\tau+\varepsilon)+H(\tau-\varepsilon)\right).$

If we Taylor expand about $\tau$, the odd powers of $\varepsilon$ cancel,
leaving:

$\frac{1}{2}(H(\tau+\varepsilon)+H(\tau+\varepsilon))=H(\tau)+\frac{\varepsilon^{2}}{2}H^{(2)}(\tau)+\frac{\varepsilon^{4}}{2\cdot
4!}\left(H^{(4)}(\tau+a_{1})+H^{(4)}(\tau-a_{2})\right)$

for some $0\leq a_{i}\leq\varepsilon$. Since $H^{(4)}(x)\leq 0$ for all $x$,
this gives

$C_{\tau,\varepsilon}\geq-\frac{\varepsilon^{2}}{2}H^{(2)}(\tau)=\frac{\varepsilon^{2}}{2\ln
2\tau(1-\tau)}.$

For the upper bound, the condition on $\varepsilon$ implies that
$H^{(2)}(x)\geq-\frac{2}{\ln 2\tau(1-\tau)}$ for all
$x\in[\tau-\varepsilon,\tau+\varepsilon]$. Then Taylor’s theorem gives, for
some values $a,b,c\in[-\varepsilon,\varepsilon]$, that

$\displaystyle C_{\tau,\varepsilon}$
$\displaystyle=H(\tau+(2q-1)\varepsilon)-(qH(\tau+\varepsilon)+(1-q)H(\tau-\varepsilon))$
$\displaystyle=H(\tau)+(2q-1)\varepsilon
H^{\prime}(\tau)+\frac{1}{2}(2q-1)^{2}\varepsilon^{2}H^{(2)}(\tau+a)$
$\displaystyle\quad-\left(H(\tau)+q\varepsilon
H^{\prime}(\tau)-(1-q)\varepsilon
H^{\prime}(\tau)+q\frac{\varepsilon^{2}}{2}H^{(2)}(\tau+b)+(1-q)\frac{\varepsilon^{2}}{2}H^{(2)}(\tau+c)\right)$
$\displaystyle=\frac{\varepsilon^{2}}{2}\left((2q-1)^{2}H^{(2)}(\tau+a)-qH^{(2)}(\tau+b)-(1-q)H^{(2)}(\tau+c)\right)$
$\displaystyle\leq\frac{\varepsilon^{2}}{\ln 2\cdot\tau(1-\tau)}.$

∎

######  Lemma A.3.

For $0<\varepsilon\leq\frac{1}{2}\min(\tau,1-\tau)$,

$|q-\frac{1}{2}|\leq\frac{2\varepsilon}{\tau(1-\tau)}.$

###### Proof.

Recall that $q\in[0,1]$ is chosen to maximize the expected information gain:

$H((1-q)(\tau-\varepsilon)+q(\tau+\varepsilon))-(1-q)H(\tau-\varepsilon)-qH(\tau+\varepsilon).$
(18)

Setting the derivative of this to zero, we get

$\displaystyle 0$ $\displaystyle=2\varepsilon
H^{\prime}(\tau+(2q-1)\varepsilon)+H(\tau-\varepsilon)-H(\tau+\varepsilon)$
$\displaystyle H^{\prime}(\tau+(2q-1)\varepsilon)$
$\displaystyle=\frac{H(\tau+\varepsilon)-H(\tau-\varepsilon)}{2\varepsilon}$
(19)

As $H^{\prime}$ is strictly decreasing, $m$ is the unique solution to (19).

Observe that

$\displaystyle H(\tau+\varepsilon)-H(\tau-\varepsilon)=2\varepsilon
H^{\prime}(\tau)+\frac{1}{3}\varepsilon^{3}(H^{(3)}(\tau+a)+H^{(3)}(\tau+b))$

for some $a,b\in[\tau-\varepsilon,\tau+\varepsilon]$. Since

$H^{(3)}(x)=\frac{1}{\ln 2}(\frac{1}{x^{2}}-\frac{1}{(1-x)^{2}}),$

we have ${|H^{(3)}(\tau+a)|}\leq 4\frac{1}{\ln
2}\max(\frac{1}{\tau^{2}},\frac{1}{(1-\tau)^{2}})$, and similarly for $b$.
Hence

$\displaystyle\frac{1}{2\varepsilon}\left(H(\tau+\varepsilon)-H(\tau-\varepsilon)\right)=H^{\prime}(\tau)+\Delta$
(20)

for ${|\Delta|}\leq\frac{\varepsilon^{2}}{6}\frac{8}{\ln
2}\max(\frac{1}{\tau^{2}},\frac{1}{(1-\tau)^{2}})$. Returning to (19),

$H^{\prime}(\tau+(2q-1)\varepsilon)=H^{\prime}(\tau)+(2q-1)\varepsilon
H^{(2)}(\tau+c)$

for some ${|c|}\leq{|2q-1|}\varepsilon$. Combining with (20),

${|(2q-1)\varepsilon
H^{(2)}(\tau+c)|}={|\Delta|}\leq\varepsilon^{2}\frac{4}{3\ln
2}\max(\frac{1}{\tau^{2}},\frac{1}{(1-\tau)^{2}}).$

Since $H^{(2)}(\tau+c)=\frac{1}{\ln
2(\tau+c)(1-\tau-c)}\geq\frac{2}{3}\frac{1}{\ln 2\cdot\tau(1-\tau)}$,

${|2q-1|}\leq
2\varepsilon\tau(1-\tau)\max(\frac{1}{\tau^{2}},\frac{1}{(1-\tau)^{2}})=2\varepsilon\max(\frac{1-\tau}{\tau},\frac{\tau}{1-\tau})\leq\frac{2\varepsilon}{\tau(1-\tau)}.$

∎

######  Lemma A.4.

$C_{\tau,(1-o(1))\varepsilon}\geq(1-o(1))C_{\tau,\varepsilon}$

###### Proof.

Let
$C^{\prime}(\alpha):=\min((\tau+\alpha\epsilon)\lg(\frac{\tau+\epsilon}{\tau+(2q-1)\varepsilon})+(1-\tau-\alpha\epsilon)\lg(\frac{1-\tau-\epsilon}{1-\tau-(2q-1)\varepsilon}),(\tau-\alpha\epsilon)\lg(\frac{\tau-\epsilon}{\tau+(2q-1)\varepsilon})+(1-\tau+\alpha\epsilon)\lg(\frac{1-\tau+\epsilon}{1-\tau-(2q-1)\varepsilon}))$
for $0<\alpha<1$.

Note that $C^{\prime}(\alpha)\leq C_{\tau,\alpha\varepsilon}$ as otherwise we
can use the analysis of Lemma 1.6 to show that, we can solve NBS when
$\varepsilon^{\prime}=\alpha\epsilon$ with
$\delta=1/n^{\frac{1}{\sqrt{\ln{n}}}}$, in
$(1+o(1))\frac{\lg(n)}{(C^{\prime}(\alpha)+C_{\tau,\varepsilon})/2}$ samples,
which contradicts our lower bound.

Therefore

$\displaystyle C_{\tau,\varepsilon}-C^{\prime}(\alpha)$ $\displaystyle\leq
C^{\prime}(1)-C^{\prime}(\alpha)$ $\displaystyle\leq\begin{aligned}
\max((1-\alpha)\epsilon(\lg(\frac{\tau+\varepsilon}{\tau+(2q-1)\varepsilon})-\lg(\frac{1-\tau-\varepsilon}{1-\tau-(2q-1)\varepsilon})),\\\
(1-\alpha)\epsilon(\lg(\frac{\tau+(2q-1)\varepsilon}{\tau-\varepsilon})-\lg(\frac{1-\tau-(2q-1)\varepsilon}{1-\tau+\varepsilon})))\end{aligned}$
$\displaystyle\leq\begin{aligned}
\max((1-\alpha)\epsilon(\lg(\frac{\tau+\varepsilon}{\tau-\varepsilon})+\lg(\frac{1-\tau+\varepsilon}{1-\tau-\varepsilon})),\\\
(1-\alpha)\epsilon(\lg(\frac{\tau+\varepsilon}{\tau-\varepsilon})+\lg(\frac{1-\tau+\varepsilon}{1-\tau-\varepsilon})))\end{aligned}$
$\displaystyle\leq\begin{aligned}
(1-\alpha)\epsilon(\lg(\frac{\tau+\varepsilon}{\tau-\varepsilon})+\lg(\frac{1-\tau+\varepsilon}{1-\tau-\varepsilon})\end{aligned}$
$\displaystyle\leq(1-\alpha)\varepsilon(O(\frac{\varepsilon}{\tau})+O(\frac{\varepsilon}{1-\tau}))$
$\displaystyle\leq(1-\alpha)O(\frac{\varepsilon^{2}}{\tau(1-\tau)})$
$\displaystyle\leq(1-\alpha)O(C_{\tau,\varepsilon})$

So when $\alpha=1-o(1)$

$\displaystyle C_{\tau,\varepsilon}-C_{\tau,\alpha\varepsilon}$
$\displaystyle\leq(1-\alpha)O(C_{\tau,\varepsilon})$ $\displaystyle\leq
o(1)O(C_{\tau,\varepsilon})$ $\displaystyle
C_{\tau,\varepsilon}-o(1)O(C_{\tau,\varepsilon})$ $\displaystyle\leq
C_{\tau,\alpha\varepsilon}$ $\displaystyle(1-o(1))C_{\tau,\varepsilon}$
$\displaystyle\leq C_{\tau,\alpha\varepsilon}$

∎

######  Lemma A.5.

For $\varepsilon<\frac{1}{2}\min(\tau,1-\tau)$,

  * •

$\lg d_{0,0}\geq-3\frac{\varepsilon}{1-\tau}$

  * •

$\lg\frac{1}{d_{0,1}}\geq-3\frac{\varepsilon}{1-\tau}$

  * •

$\lg\frac{1}{d_{1,0}}\geq-3\frac{\varepsilon}{\tau}$

  * •

$\lg d_{1,1}\geq-3\frac{\varepsilon}{\tau}$

###### Proof.

When $x\in[0,1/4],\lg\frac{1-x}{1+x}\geq
4x\cdot\lg\frac{1-.25}{1+.25}\geq-3x$.

  * •

$\lg
d_{0,0}=\lg\frac{1-\tau-\varepsilon}{1-\tau-(2q-1)\varepsilon}\geq\lg\frac{1-\tau-\varepsilon}{1-\tau+\varepsilon}=\lg\frac{1-\frac{\varepsilon}{1-\tau}}{1+\frac{\varepsilon}{1-\tau}}\geq-3\frac{\varepsilon}{1-\tau}$

  * •

$\lg\frac{1}{d_{0,1}}=\lg\frac{1-\tau-(2q-1)\varepsilon}{1-\tau+\varepsilon}\geq\lg\frac{1-\tau-\varepsilon}{1-\tau+\varepsilon}=\lg\frac{1-\frac{\varepsilon}{1-\tau}}{1+\frac{\varepsilon}{1-\tau}}\geq-3\frac{\varepsilon}{1-\tau}$

  * •

$\lg\frac{1}{d_{1,0}}=\lg\frac{\tau+(2q-1)\varepsilon}{\tau+\varepsilon}\geq\lg\frac{\tau-\varepsilon}{\tau+\varepsilon}=\lg\frac{1-\frac{\varepsilon}{\tau}}{1+\frac{\varepsilon}{\tau}}\geq-3\frac{\varepsilon}{\tau}$

  * •

$\lg
d_{1,1}=\lg\frac{\tau-\varepsilon}{\tau+(2q-1)\varepsilon}\geq\lg\frac{\tau-\varepsilon}{\tau+\varepsilon}=\lg\frac{1-\frac{\varepsilon}{\tau}}{1+\frac{\varepsilon}{\tau}}\geq-3\frac{\varepsilon}{\tau}$

∎