Noisy Computing of the Threshold Function

The noisy computation of the $\mathsf{TH}_{k}$ function has primarily been investigated with a focus on the special case of $k=1$, i.e., the $\mathsf{OR}$ function. Early investigations into the noisy computation of the $\mathsf{OR}$ function can be traced back to studies in circuit theory with noisy gates (Dobrushin and Ortyukov, 1977a, ; Dobrushin and Ortyukov, 1977b, ; Von Neumann,, 1956; Pippenger et al.,, 1991; Gács and Gál,, 1994) and noisy decision trees (Evans and Pippenger,, 1998; Reischuk and Schmeltz,, 1991). For the more general case of arbitrary $k$, the noisy computation of the $\mathsf{TH}_{k}$ function was initially explored in the seminal work (Feige et al.,, 1994) on noisy computing. Subsequent investigations extended this study to the context of noisy broadcast networks (Kushilevitz and Mansour,, 2005). In the noise model we consider, the best-known upper and lower bounds for the required number of queries to achieve a desired error probability $\delta$ are attributed to Feige et al., (1994). Their work characterizes the optimal order as $\Theta(n\log(k/\delta))$ for the number of queries required. In this work, we improve the known bounds and provide an asymptotically tight characterization for the required number of queries.

Recently, there have been several notable efforts to precisely characterize the optimal number of queries with tight constant dependencies for various noisy computing tasks. Wang et al., (2024) consider the problem of noisy sorting with pairwise comparisons, and provide upper and lower bounds for the required number of queries with a multiplicative gap of factor $2$. This gap is later closed by Gu and Xu, (2023). In a recent paper (Zhu et al.,, 2024), tight bounds are established for two tasks including computing the $\mathsf{OR}$ function of a binary sequence and $\mathsf{MAX}$ function of a real sequence using pairwise comparisons.

In this paper, we adhere to the following notation conventions. Sets and events are represented using calligraphic letters, random variables using uppercase letters, and specific realizations of random variables using lowercase letters. For example, $\mathcal{X}$ and $\mathcal{Y}$ are two sets, $X$ and $Y$ are random variables, and $x$ and $y$ are their respective realizations. Vectors will be denoted using boldface letters, while scalars will be denoted using regular (non-bold) letters. The probability of an event $\mathcal{A}$ will be expressed as $\operatorname{\mathsf{P}}(\mathcal{A})$, and the expectation of a real-valued random variable $X$ will be denoted as $\operatorname{\mathsf{E}}[X]$. For a finite set $\mathcal{X}$, its cardinality will be denoted by $\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{X}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$. Unless otherwise specified, we use $\log$ to indicate the natural logarithm. We use $[n]$ to denote the set of integers $\{1,\ldots,n\}$. We follow the standard Landau notation: $f(n)=O(g(n))$ if $\lim_{n\to\infty}\frac{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}f(n)\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}{g(n)}<\infty$; $f(n)=\Omega(g(n))$ if $\lim_{n\to\infty}\frac{f(n)}{g(n)}>0$; $f(n)=\Theta(g(n))$ if $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$; $f(n)=o(g(n))$ if $\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$; $f(n)=\omega(g(n))$ if $\lim_{n\to\infty}\frac{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}f(n)\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}{\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}g(n)\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}missing}=\infty$; and $f(n)\sim g(n)$ if $\lim_{n\to\infty}\frac{f(n)}{g(n)}=1$. Unless otherwise specified, limits in all instances of Landau notation are taken with respect to $n$.

In this regime, our lower bound relies on Le Cam’s two-point method. In this method, we view the noisy computing problem as a binary testing problem. We design an input instance ${\mathbf{x}}^{(0)}$ with $\mathsf{TH}_{k}({\mathbf{x}})=0$, and $n-k$ input instances ${\mathbf{x}}^{(1)},\ldots,{\mathbf{x}}^{(n-k)}$ with $\mathsf{TH}_{k}({\mathbf{x}})=1$ for each $i\in[n-k]$. Using Le Cam’s two-point lemma (Yu,, 1997), we show that when the query complexity of the algorithm is below a certain threshold, the algorithm cannot distinguish ${\mathbf{x}}^{(0)}$ and ${\mathbf{x}}^{(i)}$ for some $i\in[n-k]$, leading to an estimation error of the $\mathsf{TH}_{k}$ function. Specifically, this method yields a lower bound of $(1-o(1))\frac{(n-k)\log\frac{1}{\delta}}{{D_{\mathrm{KL}}(p\|1-p)}}$ on the required number of queries, and further implies the desired bound $(1-o(1))\frac{(n-k)\log\frac{k}{\delta}}{{D_{\mathrm{KL}}(p\|1-p)}}$ by the fact that $\log(k/\delta)=(1+o(1))\log\frac{1}{\delta}$ in this regime. We defer the detailed proof in this regime to Appendix A.

Notably, in the opposite regime $\log k>\frac{\log(1/\delta)}{\log\log(1/\delta)}$, the equality $\log(k/\delta)=(1+o(1))\log\frac{1}{\delta}$ does not necessarily hold true, and hence the bound provided by Le Cam’s method does not yield the desired lower bound. For example, when $\delta=\frac{1}{\log n}$ and $k=n/2$, the lower bound provided by Le Cam’s method is given by $(1-o(1))\frac{\frac{n}{2}\log\log n}{{D_{\mathrm{KL}}(p\|1-p)}}$, which does not even match the asymptotic order of the desired lower bound $(1-o(1))\frac{\frac{n}{2}\log\frac{n\log n}{2}}{{D_{\mathrm{KL}}(p\|1-p)}}$.

In this regime with a larger $k$ value, the bound derived from Le Cam’s method falls short in capturing the dependency between the optimal number of queries and the parameter $k$. Therefore, we adopt an alternative approach, where we directly analyze the query-response statistics of an arbitrary algorithm, and bound its error probability. The major difficulty in establishing a converse result for an arbitrary algorithm is that the algorithm may have an arbitrarily correlated query strategy. To tackle this challenge, we introduce a two-phase enhanced version of any given variable-length algorithm. The first phase of the enhanced algorithm is called the non-adaptive phase. It queries each bit for a fixed amount of time. The second phase is called the adaptive phase. It adaptively chooses certain bits to noiselessly reveal their values. This two-phase design of the enhanced algorithm makes the response statistics more tractable and analyzable. We show that the worst-case probability of error of the enhanced algorithm is less than or equal to that of the original algorithm. Therefore, it suffices to show that the enhanced algorithm has error probability at least $\delta$. We sketch the proof in the rest of this section.

To prove the desired bound $(1-o(1))\frac{(n-k)\log\frac{k}{\delta}}{{D_{\mathrm{KL}}(p\|1-p)}}$, we define a vanishing quantity $\epsilon=o(1)$, and prove that any algorithm with at most $\frac{(1-{\epsilon})(n-k-{\epsilon}n)\log\frac{k}{\delta}}{{D_{\mathrm{KL}}}(p-\epsilon\|1-p)}$ queries in expectation has error probability at least $\delta$.

Enhanced algorithm. Consider an arbitrary algorithm $\mathcal{A}$ that makes at most $\frac{(1-\epsilon)(n-k-\epsilon n)\log\frac{k}{\delta}}{{D_{\mathrm{KL}}}(p-\epsilon\|1-p)}$ queries in expectation. We introduce an enhanced version of $\mathcal{A}$, denoted $\mathcal{A}^{\prime}$, and show that the error probability of $\mathcal{A}^{\prime}$ is always less than or equal to the error probability of $\mathcal{A}$. We then lower bound the error probability of $\mathcal{A}^{\prime}$ to complete the proof.

The enhanced algorithm $\mathcal{A}^{\prime}$ includes a two-step procedure:

• $\bullet$

  Non-adaptive phase: query each of the $n$ bits $\alpha\triangleq\frac{(1-\epsilon)\log\frac{k}{\delta}}{{D_{\mathrm{KL}}}(p-\epsilon\|1-p)}$ times.

• $\bullet$

  Adaptive phase: Adaptively choose $N^{\prime}$ bits and noiselessly reveal their value, where the number of revealed bits $N^{\prime}$ satisfies $\operatorname{\mathsf{E}}[N^{\prime}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathbf{x}]=n-k-\epsilon n$ for any $\mathbf{x}$.

The purpose of the enhanced algorithm is to transform an intractable adaptive algorithm into a tractable one with analyzable statistics. The idea of algorithm enhancement is first introduced by Feige et al., (1994), where the authors define an enhancement for any fixed-length algorithm. In the above definition of ${\mathcal{A}}^{\prime}$, we extend this notion of algorithm enhancement to accommodate any variable-length algorithm, and analyze the error probability for this enhanced variable-length algorithm. Consequently, the lower bound established in our work applies to the expected query complexity of any variable-length algorithm, while the lower bound by Feige et al., (1994) applies only to the deterministic query complexity of any fixed-length algorithm.

It is an intuitive observation that Algorithm $\mathcal{A}^{\prime}$ works strictly better than $\mathcal{A}$. To see this, we notice that the expected number of bits queried more than $\alpha=\frac{(1-\epsilon)\log\frac{k}{\delta}}{{D_{\mathrm{KL}}}(p-\epsilon\|1-p)}$ times in Algorithm $\mathcal{A}$ is at most $n-k-\epsilon n$, because $\mathcal{A}$ makes at most $\frac{(1-\epsilon)(n-k-\epsilon n)\log\frac{k}{\delta}}{{D_{\mathrm{KL}}}(p-\epsilon\|1-p)}$ queries in expectation. In contrast, Algorithm $\mathcal{A}^{\prime}$ makes $\alpha$ queries to each bit, and adaptively choose $n-k-\epsilon n$ bits in expectation to acquire the values noiselessly. As a result, Algorithm $\mathcal{A}^{\prime}$ obtains more information on every bit than Algorithm $\mathcal{A}$, and hence has a lower error probability. We formally state this result in following lemma, and defer its proof to Appendix A.

Now, it suffices to show that the worst-case error probability of $\mathcal{A}^{\prime}$ is at least $\delta$. To bound the error probability of Algorithm $\mathcal{A}^{\prime}$, we analyze the query responses from the non-adaptive phase using a balls-and-bins model. We view each of the $n$ bits as a ball with an underlying weight. A bit of value one corresponds to a heavy ball, and a bit of value zero corresponds to a light ball. In the non-adaptive phase, each bit $x_{i}$ is queried $\alpha$ times. Let $I_{i}$ denote the number of ones in these $\alpha$ responses. If $I_{i}=j$, we put ball $i$ to bin $j\in\{0,1,\ldots,\alpha\}$. This creates $\alpha+1$ bins ${\mathcal{S}}_{j}\triangleq\{i\in[n]\mathchar 58\relax I_{i}=j\}$ for $j\in\{0,1,\ldots,\alpha\}$.

The statistics of the responses we get from the non-adaptive phase can be characterized by a sequence of $\alpha+1$ sets ${\mathcal{S}}\triangleq({\mathcal{S}}_{0},\ldots,{\mathcal{S}}_{\alpha})$. For $j\in\{0,\ldots,\alpha\}$, we define $\mathcal{H}_{j}\triangleq\{i\in[n]\mathchar 58\relax x_{i}=1,I_{i}=j\}$ and $\mathcal{L}_{j}\triangleq\{i\in[n]\mathchar 58\relax x_{i}=0,I_{i}=j\}$, i.e., $\mathcal{H}_{j}$ (resp. $\mathcal{L}_{j}$) represents the set of heavy (resp. light) balls in the $j$th bin. Let $H_{j}\triangleq\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{H}_{j}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$ and $L_{j}\triangleq\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathcal{L}_{j}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$. Let ${\bf H}_{0}^{\alpha}\triangleq(H_{0},\ldots,H_{\alpha})$ and ${\bf L}_{0}^{\alpha}\triangleq(L_{0},\ldots,L_{\alpha})$.

In the adaptive phase of Algorithm $\mathcal{A}^{\prime}$, we noiselessly reveal the weights of $N^{\prime}$ balls. Using ${\mathcal{S}}$ and the weights of the balls revealed in the adaptive phase, Algorithm $\mathcal{A}^{\prime}$ needs to estimate whether there are at least $k$ heavy balls out of $n$ balls.

Restricting input sequence weights. To facilitate the analysis of Algorithm $\mathcal{A}^{\prime}$, we restrict the input instance space. We assume that the input sequence $\mathbf{x}$ satisfies either $w(\mathbf{x})=k-1$ or $w(\mathbf{x})=k$, i.e., there are either $k$ or $k-1$ heavy balls. The error for the restricted inputs is a lower bound on the original worst-case error

where $\widehat{\mathsf{TH}}_{k}$ denote the output estimate of Algorithm ${\mathcal{A}}^{\prime}$. Later we will show the error on the restricted input space is at least $\delta$.

Genie-aided information. We assume that a genie provides Algorithm $\mathcal{A}^{\prime}$ with additional information after the non-adaptive phase to assist the estimation. Specifically, the genie reveals two sequences of sets $\bar{\mathcal{H}}_{0}^{\alpha}=(\bar{\mathcal{H}}_{0},\ldots,\bar{\mathcal{H}}_{\alpha})$ and $\bar{\mathcal{L}}_{0}^{\alpha}=(\bar{\mathcal{L}}_{0},\ldots,\bar{\mathcal{L}}_{\alpha})$, which are defined under two hypotheses $w(\mathbf{x})=k-1$ and $w(\mathbf{x})=k$ respectively as follows.

• $\bullet$

  When $w(\mathbf{x})=k-1$, there are in total $k-1$ heavy balls in the bins, and the genie reveals the indices of all of them, i.e., $(\bar{\mathcal{H}}_{0},\ldots,\bar{\mathcal{H}}_{\alpha})=(\mathcal{H}_{0},\ldots,\mathcal{H}_{\alpha})\;\;\text{and}\;\;(\bar{\mathcal{L}}_{0},\ldots,\bar{\mathcal{L}}_{\alpha})=(\mathcal{L}_{0},\ldots,\mathcal{L}_{\alpha}).$

• $\bullet$

  When $w(\mathbf{x})=k$, the genie decides to either reveal the indices of $k-1$ heavy balls or the indices of all $k$ heavy balls through a random process. Let ${\mathcal{T}}\triangleq\{j\in\{0,1,\ldots,\alpha\}\mathchar 58\relax\alpha(p-{\epsilon})\leq j\leq\alpha(p+{\epsilon})\}$ be the set of typical bin indices for light balls. The genie picks a random bin $J\in{\mathcal{T}}$ from distribution $\operatorname{\mathsf{P}}(J=j)=\frac{L_{j}}{\sum_{i\in{\mathcal{T}}}L_{i}}$. If the chosen bin $J$ contains no heavy balls, i.e., $H_{J}=0$, then the genie reveals the indices of all $k$ heavy balls by setting $(\bar{\mathcal{H}}_{0},\ldots,\bar{\mathcal{H}}_{\alpha})=(\mathcal{H}_{0},\ldots,\mathcal{H}_{\alpha})\;\;\text{and}\;\;(\bar{\mathcal{L}}_{0},\ldots,\bar{\mathcal{L}}_{\alpha})=(\mathcal{L}_{0},\ldots,\mathcal{L}_{\alpha}).$ On the other hand, if $H_{J}\geq 1$, then the genie chooses a heavy ball $i$ in bin $J$ uniformly at random to be hidden, and reveals the indices of all other heavy balls. This is done by setting $(\bar{\mathcal{H}}_{0},\ldots,\bar{\mathcal{H}}_{\alpha})=(\mathcal{H}_{0},\ldots,\mathcal{H}_{J-1},\mathcal{H}_{J}\setminus\{i\},\mathcal{H}_{J+1},\ldots,\mathcal{H}_{\alpha})$ and $(\bar{\mathcal{L}}_{0},\ldots,\bar{\mathcal{L}}_{\alpha})=(\mathcal{L}_{0},\ldots,\mathcal{L}_{J-1},\mathcal{L}_{J}\cup\{i\},\mathcal{L}_{J+1},\ldots,\mathcal{L}_{\alpha}).$

It is not hard to see that with the additional noiseless information revealed by the genie, the performance of Algorithm $\mathcal{A}^{\prime}$ does not deteriorate. Moreover, because in all cases the sets $\bar{\mathcal{H}}_{0}^{\alpha}$ only contain heavy balls, and the sets $\{\bar{\mathcal{L}_{j}}\mathchar 58\relax j\notin\mathcal{T}\}$ only contain light balls, we assume without loss of generality that the adaptive phase of $\mathcal{A}^{\prime}$ only reveals the weights of the balls in {$\bar{\mathcal{L}_{j}}\mathchar 58\relax j\in\mathcal{T}\}$. In the remaining proof, we analyze the error probability of $\mathcal{A}^{\prime}$ in the presence of genie-aided information.

Why can we establish a tighter lower bound? Before sketching the proof of our lower bound with the genie-aided information, we first clarify the key distinctions between our analysis and that in Feige et al., (1994). We also highlight the main reason why our approach provides a tighter lower bound for the optimal query complexity.

In the proof by Feige et al., (1994), the error bound for $\mathcal{A}^{\prime}$ is also established through a genie-aided analysis, where the genie picks the bin $J$ to hide a heavy ball from all possible bins $\{0,\ldots,\alpha\}$ instead of choosing it from the set ${\mathcal{T}}$. It is then shown that when $\alpha$ is small enough, every bin in $\{0,\ldots,\alpha\}$ contains at least one heavy ball with high probability, ensuring the genie hides a heavy ball in the chosen bin. Furthermore, it is shown that the noiseless queries in the adaptive phase would fail to find the hidden heavy ball with a constant probability, resulting in the scenario where the algorithm observes the $k-1$ heavy balls revealed by the genie, but cannot distinguish whether there is a $k$th hidden heavy ball. This leads to an overall error probability of at least $\delta$ for the algorithm.

In our analysis, we realize that having a heavy ball in every bin with high probability is not a necessary condition for establishing the desired error bound for Algorithm $\mathcal{A}^{\prime}$. In our proof, the genie instead picks the bin $J$ from ${\mathcal{T}}$ to hide a heavy ball, where ${\mathcal{T}}$ is a typical set of bins for the light balls. We then focus on analyzing the statistical behavior of these bins in ${\mathcal{T}}$. We show that for each $i\in{\mathcal{T}}$, the probability that bin $i$ contains at least one heavy ball is $\omega(\delta)$. Moreover, conditioned on the event that a heavy ball is hidden by the genie, we further show that the information revealed by the genie and the noiseless queries in the adaptive phase are not informative enough for the algorithm to distinguish whether there is a $k$th heavy ball that is hidden. This leads to the desired error bound. Notably, requiring each bin $i\in{\mathcal{T}}$ to contain at least one heavy ball with probability $\omega(\delta)$ imposes a much less stringent condition on the choice of $\alpha$ comparing to requiring all the bins to contain at least one heavy ball with high probability. Consequently, the choice of $\alpha=\frac{(1-\epsilon)\log\frac{k}{\delta}}{{D_{\mathrm{KL}}}(p-\epsilon\|1-p)}$ in our analysis is much higher than the choice of $\alpha$ in Feige et al., (1994). Therefore, we can show that the error lower bound $\delta$ applies to an algorithm with higher query complexity. This leads to a tighter lower bound for the optimal query complexity.

Error analysis for the optimal estimator. Towards a contradiction, we assume that the worst-case error is at most $\delta$, i.e.,

This implies

However, in the rest of the proof, we show (2) implies

which contradicts with (1).

Sufficient statistic for estimation. We claim a sufficient statistic for the optimal estimator $\widehat{\mathsf{TH}}_{k}$. When algorithm $\mathcal{A}^{\prime}$ decides its output, it has access to information including $\bar{\mathcal{H}}_{0}^{\alpha}$, $\bar{\mathcal{L}}_{0}^{\alpha}$ and the weights of the balls revealed in the adaptive phase. By the symmetry of the balls in the same bin, it suffices for $\mathcal{A}^{\prime}$ to consider the cardinality of the sets $\bar{\mathcal{H}}_{0}^{\alpha}$ and $\bar{\mathcal{L}}_{0}^{\alpha}$, denoted by $\bar{\bf H}_{0}^{\alpha}\triangleq(\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\bar{\mathcal{H}}_{0}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|},\ldots,\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\bar{\mathcal{H}}_{\alpha}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|})$ and $\bar{\bf L}_{0}^{\alpha}\triangleq(\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\bar{\mathcal{L}}_{0}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|},\ldots,\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\bar{\mathcal{L}}_{\alpha}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|})$. Moreover, notice that the unrevealed balls include at most $1$ heavy ball. The adaptive phase of the algorithm either finds one heavy ball or no heavy ball. By the symmetry of the balls in the same bin, it suffices for $\mathcal{A}^{\prime}$ to consider whether the adaptive phase finds any heavy ball. Let ${\mathcal{E}}_{1}$ denote the event that the adaptive phase does not find any heavy ball. Thus, the optimal estimator $\widehat{\mathsf{TH}}_{k}$ of $\mathcal{A}^{\prime}$ can be written as a function $\widehat{\mathsf{TH}}_{k}(\bar{\bf H}_{0}^{\alpha},\bar{\bf L}_{0}^{\alpha},\mathbbm{1}_{\{{\mathcal{E}}_{1}\}})$.

Next, we argue that certain realizations of the sufficient statistic yield the correct answer to the true threshold $\mathsf{TH}_{k}(\mathbf{x})$ (and thus no error for the optimal estimator). Notice that if $\sum_{i=0}^{\alpha}\bar{H}_{i}=k$, then we know that $w(\mathbf{x})=k$. This is because $\bar{\mathcal{H}}_{0}^{\alpha}$ only contain indices of heavy balls. Moreover, if $\mathbbm{1}_{\{{\mathcal{E}}_{1}\}}=0$, we know that a heavy ball is found in the adaptive phase, and it follows that $w(\mathbf{x})=k$. Therefore, we assume without loss of generality that the optimal estimator $\widehat{\mathsf{TH}}_{k}(\bar{\bf H}_{0}^{\alpha},\bar{\bf L}_{0}^{\alpha},\mathbbm{1}_{\{{\mathcal{E}}_{1}\}})=1$ if $\sum_{i=0}^{\alpha}\bar{H}_{i}=k$ or $\mathbbm{1}_{\{{\mathcal{E}}_{1}\}}=0$.

Now the only ambiguous case that might lead to error is when $\sum_{i=1}^{\alpha}\bar{H}_{i}=k-1$ and $\mathbbm{1}_{\{{\mathcal{E}}_{1}\}}=1$. This corresponds to the case where the genie reveals the indices of $k-1$ heavy balls, and the adaptive phase does not find any heavy balls. Among the remaining realizations of the sufficient statistic, we further divide them into two sets according to whether the estimator $\widehat{\mathsf{TH}}_{k}({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha},1)$ is 0 or 1. We define $\mathcal{N}$ as the collection of realizations $({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha})$ such that $\widehat{\mathsf{TH}}_{k}({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha},1)=0$. In other words, we have

Ideally, if we can prove that this sufficient statistic $(\bar{\bf H}_{0}^{\alpha},\bar{\bf L}_{0}^{\alpha},\mathbbm{1}_{\{{\mathcal{E}}_{1}\}})$ is similarly distributed under the two different hypotheses $w({\mathbf{x}})=k-1$ and $w({\mathbf{x}})=k$, then we can lower bound the ratio $\frac{\operatorname{\mathsf{P}}(\widehat{\mathsf{TH}}_{k}=0\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}w({\mathbf{x}})=k)}{\operatorname{\mathsf{P}}(\widehat{\mathsf{TH}}_{k}=0\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}w({\mathbf{x}})=k-1)}$, and hence show that (2) implies (3). More specifically, if we can show that

for any $({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha})\in\mathcal{N}$, then we would have

which completes the proof. However, it turns out that the desired property (5) does not hold for all realizations $({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha})\in\mathcal{N}$. Instead, we slightly adjust this approach, and identify a family $\mathcal{C}$ of realizations $({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha})$ satisfying

1. 1.

   Typicality: $\sum_{({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha})\in\mathcal{C}}\operatorname{\mathsf{P}}(\{(\bar{\bf H}_{0}^{\alpha},\bar{\bf L}_{0}^{\alpha})=({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha})\}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}w(\mathbf{x})=k-1)\geq 1-o(1).$

2. 2.

   Bounded ratio property²²2For simplicity, the bounded ratio property presented here is a simplified version of what we actually prove, and it holds only in the special case when ${\mathcal{A}}^{\prime}$ makes a fixed number of queries in the adaptive phase. We refer the readers to Propositions 2 and 4 for the properties in the general case.: $\frac{\operatorname{\mathsf{P}}\left(\{(\bar{\bf H}_{0}^{\alpha},\bar{\bf L}_{0}^{\alpha})=({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha})\}\cap{\mathcal{E}}_{1}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}w(\mathbf{x})=k\right)}{\operatorname{\mathsf{P}}\left(\{(\bar{\bf H}_{0}^{\alpha},\bar{\bf L}_{0}^{\alpha})=({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha})\}\cap{\mathcal{E}}_{1}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}w(\mathbf{x})=k-1\right)}=\omega(\delta),$ $\forall({\bf h}_{0}^{\alpha},{\bf l}_{0}^{\alpha})\in\mathcal{C}$.

With the two properties for the family $\mathcal{C}$, we have

which completes the proof. In the detailed proof presented in Appendix A, we further separate the regime $\log k>\frac{\log(1/\delta)}{\log\log(1/\delta)}$ into two sub-regimes $\frac{\log(1/\delta)}{\log\log(1/\delta)}<\log k\leq\log(1/\delta)\log\log(1/\delta)$ and $\log k>\log(1/\delta)\log\log(1/\delta)$. We present the detailed construction of the family $\mathcal{C}$ in these two sub-regimes in Appendix A.

To estimate a function of a binary sequence ${\mathbf{x}}$, one natural idea is first to estimate each bit in ${\mathbf{x}}$ and then to compute the function with the estimates. In this regime, the proposed algorithm exactly follows this idea.

The proposed algorithm estimates the bits in the sequence by employing an existing algorithm ChechBit as a subroutine. CheckBit (Algorithm 1 in Gu and Xu, (2023)) takes as input a single bit and a desired error probability $\delta$, and returns an estimate of the bit through repeated queries. A detailed description of the CheckBit algorithm is provided in Algorithm 3 in Appendix B. Lemma 13 in Gu and Xu, (2023) shows that the algorithm makes at most $\frac{1}{1-2p}\left\lceil\frac{\log\frac{1-\delta}{\delta}}{\log\frac{1-p}{p}}\right\rceil$ queries in expectation and returns the correct value of the input bit with probability at least $1-\delta$.

In the proposed algorithm, we call the CheckBit function to estimate $x_{i}$ for each $i\in[n]$ with error probability set to $\delta/n$, and obtain an estimate $\hat{x}_{i}$. The algorithm then outputs $\widehat{\mathsf{TH}}_{k}(x)=\mathbbm{1}_{\{\sum_{i=1}^{n}\hat{x}_{i}\geq k\}}$ as the estimate. The pseudo-code of this algorithm is given in Algorithm 1.

By the union bound, we have $\operatorname{\mathsf{P}}(\exists i\in[n]\mathchar 58\relax\hat{x}_{i}\neq x_{i})\leq\delta$. Consequently, we get $\operatorname{\mathsf{P}}(\widehat{\mathsf{TH}}_{k}(x)\neq\mathsf{TH}_{k}(x))\leq\delta$, i.e., the error probability of Algorithm 1 is at most $\delta$. The expected number of queries used by these $n$ calls of the CheckBit function is at most

In the regime $k>\frac{n}{\log n}$, it follows that $\log\frac{n}{\delta}=(1+o(1))\log\frac{k}{\delta}$. Therefore, Algorithm 1 uses at most $(1+o(1))\frac{n\log\frac{n}{\delta}}{{D_{\mathrm{KL}}(p\|1-p)}}$ queries in expectation. This proves Theorem 2 in the regime $k>\frac{n}{\log n}$.

Notably, in the opposite regime $k\leq\frac{n}{\log n}$, the equation $\log\frac{n}{\delta}=(1+o(1))\log\frac{k}{\delta}$ does not necessarily hold true, and hence the desired upper bound in Theorem 2 cannot be obtained through Algorithm 1. For example, suppose $k=\log n$ and $\delta=1/\log n$. The upper bound provided by Algorithm 1 is $\frac{(1+o(1))n\log n}{D_{\mathsf{KL}}(p\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}1-p)}$, while the desired upper bound in Theorem 2 is given by $\frac{(1+o(1))2n\log\log n}{D_{\mathsf{KL}}(p\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}1-p)}$.

In this regime, we propose the NoisyThreshold algorithm, given in Algorithm 2, that computes the $\mathsf{TH}_{k}$ function with the desired number of queries and error probability. In addition to CheckBit, Algorithm 2 also utilizes the existing MaxHeapThreshold algorithm as a subroutine.

MaxHeapThreshold is the algorithm proposed by Feige et al., (1994) for estimating the $\mathsf{TH}_{k}$ function. Its main idea is to use heapsort to find the $k$-th largest element in ${\mathbf{x}}$, and then repeatedly query this element to decide $\mathsf{TH}_{k}(x)$. To cope with the observation noise, each query in heapsort is repeated for a certain amount of times. Detailed descriptions of the MaxHeapThreshold algorithm and its subroutines are given in Algorithms 4, 5 and 6 in Appendix B. Theorem 3.3 in Feige et al., (1994) shows that the function uses at most $O(n\log\frac{k}{\delta})$ queries. Although the query complexity of MaxHeapThreshold achieves the correct asymptotic order, there remains a constant multiplicative gap between its query complexity and the optimal value, as demonstrated in the numerical examples provided in Section I.

The main idea in Algorithm 2 is first reducing the problem size to the order of $o(n)$ through a filtering process for the bits in ${\mathbf{x}}$, and then applying MaxHeapThreshold on the reduced problem. In the first step, we call the CheckBit function on each bit to estimate its value with tolerated error probability $\delta/k$. The bits estimated to be $1$ are added to the set $\mathcal{S}$. This step can be viewed as a filtering process that provides a set of bits believed to be $1$ with high confidence. Notice that with an error probability $\delta/k$ for each bit estimation, we cannot guarantee that all bits are correctly estimated with probability at least $1-\delta$ as in the case of Algorithm 1. Instead, we show that with probability at least $1-2\delta$, $\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\mathcal{S}}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}$ is below a certain threshold $\tau$ if $\mathsf{TH}_{k}(x)=0$, and ${\mathcal{S}}$ contains at least $k$ bits of true value 1 if $\mathsf{TH}_{k}(x)=1$. From here, we can output $\mathsf{TH}_{k}(x)=1$ if $\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\mathcal{S}}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\geq\tau$ (Line 10 of Algorithm 2), and output $\mathsf{TH}_{k}(x)=0$ if $\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}{\mathcal{S}}\mathchoice{\mspace{1.0mu}|\mspace{1.0mu}}{|}{|}{|}\leq k-1$ (Line 8 of Algorithm 2). When none of these two cases holds, the problem of estimating $\mathsf{TH}_{k}({\mathbf{x}})$ reduces to deciding whether ${\mathcal{S}}$ contains at least $k$ bits of value $1$. For this reduced problem, we perform the second step by calling the MaxHeapThreshold function on the set ${\mathcal{S}}$ (Line 12 of Algorithm 2) to decide the final output.

By applying the union bound over the two steps, the overall error probability of Algorithm 2 is at most $\delta^{\prime}$ when the input parameter $\delta$ is set to $\delta/3$. Notably, $\tau$ is chosen to be $o(n)$. So in the event that the MaxHeapThreshold function is executed, its input size is $o(n)$. Although running MaxHeapThreshold induces a suboptimality of a constant factor, running it on an input size of $o(n)$ does not affect the dominating term in the query complexity of Algorithm 2. Therefore, the dominating term of the query complexity solely depends on the query complexity in the first step, which is upper bounded by $(1+o(1))\frac{n\log\frac{k}{\delta^{\prime}}}{{D_{\mathrm{KL}}(p\|1-p)}}$. This proves Theorem 2 in the regime of $k\leq\frac{n}{\log n}$. The detailed proof for this regime is presented in Appendix B.