\section{Introduction}
\label{secIntro}
The idea of \textit{group testing} was introduced by R. Dorfman~\cite{dor43}. It was proposed
to save on blood tests for infection by grouping individuals and testing the mixture.
The group testing scheme suggested by R. Dorfman is constructed in such way that
the successive  groups depend on the results of the previous tests.
Such schemes are called \textit{adaptive}.
There are  \textit{nonadaptive} schemes also. A nonadaptive scheme is a series of $N$
a priori group tests that can be carried out simultaneously. This is
the essential advantage for the most important applications~\cite{dh00,dmr00-2}.
In this paper we focus on nonadaptive group testing schemes.

Let $t$ be the number of elements and $\S$ ($\S \subseteq [t]$, $[t] \eq \{1, 2, \dots, t\}$)
is an unknown subset of defectives. We will use these notations throughout the paper.
The conventional group testing problem assumes
that the number of defectives $|\S|$ is upper bounded by a known fixed constant $s$,
i.e., $|\S| \le s$, where $s$ does not depend on~$t$.
In this regime the main attention is given to disjunctive $s$-codes~\cite{ks64,dh00}
which will be defined in the next section.
However, a more common assumption is that the defectives are rare, with $|\S| = o(t)$ as $t \to \infty$.
So, in the recent works~\cite{ald14,ald-scar17,scar17} the regime $|\S| = \Theta(t^\alpha)$, $0 < \alpha < 1$,
is studied.

The other authors  consider the situation in which the number of defectives is unknown.
Originally it was proposed in Dorfman's paper~\cite{dor43} that each element is defective
with probability $p$, $0 < p < 1$. Exactly the same model is considered in the recent papers~\cite{wad17,jaggi18,ald18},
where the authors focus on nonadaptive schemes and study algorithms for which the error probability
of finding defectives is $o(1)$ as $t \to \infty$.
A more general model in which $p = p(t)$ depends on $t$ is considered in paper~\cite{lev02}.
T. Berger and V. Levenshtein~\cite{lev02} study the use of so called $2$-stage testing schemes
to find all defectives with zero-error probability.
They propose to run a fixed number of nonadaptive tests at the first stage and
to test individually potential candidates after the first stage at the second stage.
For some dependencies $p(t)$, the lower and upper bounds
on asymptotics of the expected number of tests in the described 2-stage scheme are obtained in~\cite{lev02,mezard11}.

 Another approach to nonadaptive group testing schemes for finding the unknown
set of defectives  is proposed by P.~Damaschke and A.S.~Muhammad in~\cite{dam10}.
In the beginning  one obtains
an estimate of the unknown  number of defectives $|\S|$ with the help of $N$  random
group tests, and then it remains to use one of the well-known algorithms to construct
a defective set $\S$ having the randomly estimated size.
\if0
Another approach to finding the defective set of an unknown size is proposed
by P.~Damaschke and A.S.~Muhammad in~\cite{dam10}. In the beginning one should
estimate the number of defectives $|\S|$ with the help of  group tests, and then
it remains to use one of the well-known algorithms for finding the defective set $\S$
of the estimated size.
\fi

The aim of our work is to discuss testing of hypothesis $H_0$: the  random  number of defectives
is upper bounded by a fixed parameter $s$ which does not depend on~$t$. In fact, the considered disjunctive group testing model is a special case of
noiseless symmetric multiple-access channel (MAC)
such that the output of MAC equals the disjunctive sum of the inputs.
The given model represents one described in the recent paper~\cite{pol17},
where the model of MAC has the following key differences from  the   usual information-theoretic
models of MAC: a)~all the users employ the same code of size~$t$; b)~the code size $t$ is independent from
the code length $N$ and $t$ can be arbitrary large; c)~at any  time unit $i$, $i=1,2,\dots,N$,
there is  the  same random collection of active users.

The remainder of this paper is organized as follows.
In Section~\ref{secDefs} we introduce notations and give basic definitions. Section~\ref{secRelatedRes}
starts with the exhaustive proposition in the case of zero-error probability and discusses the related results.
In Section~\ref{secMainResults} we present the main results of this paper: the existence of an algorithm with $O(s^2 \log \frac{1}{\epsilon})$ tests which accepts or rejects $H_0$ with error probability $\le \epsilon$,  and the necessity of $\Omega(s\log \frac{1}{\epsilon})$ tests for any algorithm and sufficiently large number of elements.
Section~\ref{secModul} is devoted to simulations of hypothesis testing problem. Finally,
Section~\ref{secProofs} contains the proofs of the main results.

\section{Notation and Definitions}
The conventional symbol $\u \bigvee \v$ will be used to denote the disjunctive (Boolean)
sum of binary columns $\u, \v \in \{0, 1\}^N$.
We say that a column $\u$ \textit{covers} a column $\v$ if $\u \bigvee \v = \u$.
\label{secDefs}
\begin{definition}[\cite{ks64}]
\label{defDis}
A binary $(N \times t)$-matrix $X$ is called a \textit{disjunctive $s$-code},
$s \in [t-1]$, if the disjunctive sum of any $s$-subset
of columns of $X$ covers those and only those
columns of $X$ which are the terms of the given disjunctive sum.
\end{definition}
\begin{remark}
Despite the fact that we do not touch upon a coding in this paper,
we use a more conventional definition for such object in which
columns of matrix $X$ are codewords.
\end{remark}
In the classical problem of non-adaptive group testing, we describe $N$ tests
as a binary $(N \times t)$-matrix $X = \| x_i(j) \|$,
where a column $\x(j)$ corresponds to the $j$-th element, a row $\x_i$ corresponds to the $i$-th test and
$x_i(j) \eq 1$ if and only if the $j$-th element is included into the $i$-th testing group.
Let $\S$, $\S \subseteq [t]$, be an arbitrary fixed set
of defective elements of size~$|\S|$. For a binary matrix $X$ and a set $\S$,
define the binary \textit{response vector} $\x(\S)$ of length $N$, namely:
$$
\x(\S) \eq
\begin{cases}
\bigvee\limits_{j \in \S} \, \x(j) \quad &\text{if} \quad \S \ne\emptyset, \\
(0, 0, \dots, 0)^T \quad &\text{if} \quad \S = \emptyset.
\end{cases}
$$
The result of each test equals $1$ if at least one defective element is included into the testing group
and $0$ otherwise. So, the column of results is exactly equal to the response vector~$\x(\S)$.
Definition~\ref{defDis} of disjunctive $s$-code
gives the important sufficient condition for identification of any unknown
defective set $\S$, namely, one can recover $\S$ based on the response vector if the number of defective elements~$|\S| \le  s$.
In the case of disjunctive $s$-codes, the identification of the unknown $\S$ is equivalent to searching all columns of
matrix~$X$ covered by~$\x(\S)$,
and its complexity is equal to $\Theta(N \cdot t)$.
This conventional algorithm of finding defectives is called \textit{COMP
$($Combinatorial Optimal Matching Pursuit$)$}~\cite{ald14}.
The best detection algorithm is based on enumerating all possible defective sets $\S$,
and one of candidates is called \textit{SSS $($Smallest Satisfying Set$)$}~\cite{ald14}. But this algorithm
is impractical because of the high time complexity which equals $\Theta\(N \cdot {t \choose s}\)$ if $|\S| = s$.
Among other detection algorithms we highlight \textit{DD $($Definite Defectives$)$}~\cite{ald14,scar17} because
it has the same complexity as COMP but the best known non-adaptive random scheme requires
up to $50\%$ fewer tests in the regime $|\S| = \Theta(t^\alpha)$, $0 < \alpha < 1$.
The DD algorithm finds all columns $\S'$ of matrix~$X$ covered by~$\x(\S)$ at the beginning,
but only those elements are considered to be defective
for which the removal from $\S'$ leads to another disjunctive sum, i.e.,
$j$ is defective if $\x(\S' \setminus \{j\}) \neq \x(\S)$.

Let us introduce two hypothesis:
the null hypothesis $\left\{ H_0 \,:\, |\S| \le s \right\}$
and the alternative $\left\{ H_1 \,:\, |\S| \ge s+1 \right\}$.
In this work we consider testing hypothesis $H_0$ versus $H_1$ using group tests
in the reasonable probabilitic model in which
the  random  defective sets of the same size are equiprobable.
More accurately, the probability distribution
of the random defective set $\S$ is defined by vector
$\p \eq (p_0, p_1, \dots, p_t)$, $p_k \ge 0 \; \forall \, k$,
$\sum_{k = 0}^{t} p_k = 1$, as follows:
\begin{equation}
\label{pd}
\Pr\{\S = \S_0\} \eq \frac{p_{|\S_0|}}{{t \choose |\S_0|}} \quad \text{for any}
\quad \S_0 \subseteq [t].
\end{equation}

Let $\D : \{0, 1\}^N \to \{H_0, H_1\}$ be an arbitrary \textit{decision rule}
which associates a response vector with the hypothesis.
So, we will call the adapted for hypothesis testing problem the COMP algorithm by the COMP decision rule
which accepts $H_0$ if the number of columns covered by the response vector is at most $s$.
Introduce the \textit{$($maximal$)$ error probability} for the decision rule~$\D$ and testing matrix~$X$:
\begin{equation}
\label{maxError}
\begin{split}
\e_s(\p, \D, X) \eq \, \max\, \big\{ \Pr\{ \text{accept } H_1 \big| H_0 \} \, ,
\, \Pr\{ \text{accept } H_0 \big| H_1 \} \,\big\},
\end{split}
\end{equation}
where the probability measure in the conditional probabilities is defined by~(\ref{pd}).
If the $\Pr\{H_0\} = 0$ or $\Pr\{H_1\} = 0$ let the error probability be zero.
We use also the notation of \textit{universal error probability}
which does not depend on $\p$ and equals the worst error probability:
\begin{equation}
\label{uniError}
\e_s(\D, X) \eq \, \max\limits_{\p} \, \e_s(\p, \D, X).
\end{equation}

\section{Related Results}
\label{secRelatedRes}
The problem of optimal zero-error nonadaptive hypothesis testing is reduced to
the problem of optimal disjunctive codes in the following way:
\begin{proposition}
\label{propDisj}
Let $X$ be an arbitrary test matrix.
$\forall \, \p: p_s > 0 \text{ and } p_{s + 1} > 0 \; \exists \, \D \; : \; \e_s(\p, \D, X) = 0$
if and only if $X$ is a disjunctive $s$-code.
\end{proposition}
\begin{proof}
If $X$ is a disjunctive $s$-code, then obviously the COMP decision rule allows to check the hypothesis $H_0$ without error.
Converse can be proved by contradiction. Indeed, if matrix $X$ is not a disjunctive $s$-code, then there exists a set $\S \subseteq [t]$, $|\S| = s$,
and a number $j \in [t] \setminus \S$ such that $\x(\S) = \x(\S \cup \{j\})$.
So, for any decision rule we cannot distinguish the set $\S$ of size $s$ from the set $\S \cup \{j\}$ of size $s + 1$.
\end{proof}
The best known practical constructions of disjunctive  $s$-codes are
based on shortened RS-codes. These constructions presented
in~\cite{dmr00-1} essentialy extend  optimal
and suboptimal ones
 suggested in~\cite{ks64}.

Recall some results
for optimal disjunctive $s$-codes. Denote by $t(s, N)$ the maximal number of columns for disjunctive\quad $s$-codes with $N$ rows.
Introduce the \textit{rate} of disjunctive $s$-codes:
$$
R(s) \eq \varlimsup_{N \to \infty} \frac{\log_2 t(s, N)}{N}.
$$
The best known upper and lower bounds on the rate $R(s)$ are presented in~\cite{dr82} and~\cite{drr89}, respectively.
These bounds are written in the complex form, but the asymptotics as $s \to \infty$ are as follows
$$
\frac{\ln 2}{s^2} (1 + o(1)) \le R(s) \le \frac{2 \log_2 s}{s^2} (1 + o(1)), \quad s \to \infty.
$$

Further we will consider the case of positive error probability.
At the beginning let us mention some results for the
problem of estimating the number of defectives
which is the closest one to ours.
In~\cite{dam10} the authors present a randomized algorithm that uses
$G(\epsilon, c) \log_2 t$ nonadaptive tests and produces the statistic $\hat s$
which satisfies the following properties: probability
$\Pr\{\hat s < |\S|\}$ is upper bounded by a small parameter $\epsilon \ll 1$
and the expected value of~$\hat s / |\S|$ is upper bounded by a number~$c > 1$.
Note that this result is \textit{universal}, i.e., it does not depend on the distribution
of the defective set. In~\cite{orl16} the authors construct adaptive randomized algorithm
which uses at most $2 \log_2 \log_2 |\S| + O(\frac{1}{\delta^2} \log_2 \frac{1}{\epsilon})$
adaptive tests and estimates $|\S|$ up to a multiplicative factor of $1 \pm \delta$ with error probability $\le \epsilon$.
Also there is a converse in~\cite{orl16} which states
the necessity of $(1 - \epsilon) \log_2 \log_2 |\S| - 1$ tests on average.

The first thought which comes to mind from Proposition~\ref{propDisj} is that in order to solve the hypothesis testing problem one may use the COMP decision rule.
Note that this rule always accepts $H_1$ if it holds, i.e., $\Pr(H_0|H_1)=0$.
Moreover, it is not difficult to obtain that the maximum of the error probability $\e_s(\p, \text{COMP}, X)$
in (\ref{uniError}) is attained at any vector $\p$ such that $0< p_s < 1$ and $p_k = 0$ for $\forall \, k < s$, e.g., one can take $p_s=p_{s+1}=1/2$.
The reader may refer to Lemma~\ref{lemWorstProb} about a similar statement which
is given in Section~\ref{secMainResults} and proved in Section~\ref{secProofLemWorstProb}.
That is why the universal error probability $\e_s(\text{COMP}, X)$ equals the probability that
an $s$-subset of columns of $X$ covers an external column. But this probability is exactly
the error probability for almost disjunctive $s$-codes~\cite{d15}.
The most important relations between the error probability and matrix sizes are presented below.
\begin{theorem}[{\cite[Theorem $2$]{d15}}]
\label{thCapacityUpper}
Let $X$ be $(N \times t(N))$ testing matrix and $t(N) = \Omega(2^{N / s})$ then
$\e_s(\text{COMP}, X) = \Omega(1)$ as $N \to \infty$.
\end{theorem}
In other words, Theorem~\ref{thCapacityUpper} means that the \textit{rate} of matrix $X$ defined by
$$
R \eq \frac{\log_2 t}{N}
$$
is at most $1 / s$ for reaching an arbitrary small error probability.
Introduce the standard notations
\begin{align*}
h(Q) &\eq -Q \log_2 Q - (1 - Q) \log_2 [1 - Q],\\
[x]^+ &\eq \max\{x, 0\}.
\end{align*}
In~\cite{d15} it was also established a random coding bound.
\begin{theorem}[{\cite[Theorem~$4$]{d15}}
\label{thCapacityLower}
Let $R$, $0<R<1$, be fixed. For any $N$ there exists
$(N \times t)$ testing matrix $X$ with $t = \lfloor 2^{RN} \rfloor$ such that
$\e_s(\text{COMP}, X) \le 2^{- N \Ecomp(s, R) (1 + o(1))}$ as $N \to \infty$,
where
\begin{align}
\notag
\Ecomp(s, R) &\eq \, \max_{0 < Q < 1} \, \min_{Q \le q < \min\{1, sQ\}} \left\{ \A(s, Q, q)
+ \[h(Q) - q h(Q / q) - R\]^+\right\},
\\
\label{exprA}
\A(s, Q, q) &\eq (1-q) \log_2(1-q) + q \log_2 \[ \frac{Qy^s}{1-y} \] + sQ \log_2 \frac{1-y}{y} + sh(Q),
\end{align}
and $y$
is the unique root of the equation
\begin{equation}
\label{qSmall}
q = Q \frac{1 - y^s}{1 - y}, \quad 0 < y < 1.
\end{equation}
In addition, for $s \to \infty$ and $R \le \frac{\ln 2}{s}(1 + o(1))$, the exponent
$\Ecomp(s, R) > 0$.
\end{theorem}

\section{Main Results}
\label{secMainResults}
Note that our hypothesis testing problem is very different from the detection of defectives
because there are only two answers: $H_0$ or $H_1$. However, in the zero-error case hypothesis testing
requires nearly the same number of group tests as a detection of defectives does.
Our main result is devoted to hypothesis group testing in the small-error case. We introduce a decision rule
which is essentially better than COMP and provide an upper bound on the error probability
which does not depend on the number of elements $t$, whereas the result in Theorem~\ref{thCapacityLower} does.

Fix an arbitrary parameter $\tau$, $0 < \tau < 1$, and
introduce a \textit{$\tau$-weight decision rule ($\tau$-WDR)}
\begin{equation}
\label{wdr}
\begin{cases}
\text{accept $\left\{ H_0 \,:\, |\S| \le s \right\}$} & \text{if $|\x(\S)| \le \tau N$}, \\
\text{accept $\left\{ H_1 \,:\, |\S| > s \right\}$} & \text{if $|\x(\S)| > \tau N$}. \\
\end{cases}
\end{equation}

\begin{remark}
In the zero-error case $\tau$-WDR requires a special condition on a disjunctive $s$-code $X$:
for any subset $\S$ of size $|\S| = s$, the weight $|\x(\S)|$ of the response vector is at most $\lfloor \tau N \rfloor$,
and, for any subset $\S'$ of size $|\S'| = s + 1$, the weight $|\x(\S')|$ of the response vector is at least $\lfloor \tau N \rfloor + 1$.
A similar model of specific disjunctive $s$-codes was considered in~\cite{b15},
where a disjunctive $s$-code is supplied with a weaker additional condition:
the weight $|\x(\S)|$ of the response vector for any subset $\S$, $\S \subseteq [t]$, $|\S| \le s$, is at most $T$.
In~\cite{b15} the authors motivate their group testing model
by a risk for the safety of the persons who perform tests, in some contexts,
when the number of positive test results is too large.
\end{remark}

We study only the universal error probability for $\tau$-WDR,
and the following lemma proved in Section~\ref{secProofLemWorstProb} determines
the worst probability distribution.
\begin{lemma}
\label{lemWorstProb}
For any integer $s \ge 1$ and testing matrix $X$, the maximum of the error probability $\e_s(\p, \text{$\tau$-WDR}, X)$
in (\ref{uniError}) is attained at any $\p$ such that $p_s > 0$, $p_{s + 1} > 0$ and $p_s + p_{s + 1} = 1$.
\end{lemma}

The following upper bound on the error probability
for $\tau$-WDR is proved in Section~\ref{secProofThErrorUpper} by the probabilistic method based
on the ensemble of the constant column weight matrices.
A parameter $Q$ in the statement of Theorem~\ref{thErrorUpper}
corresponds to the relative weight of columns in the random matrix.

\begin{theorem}
\label{thErrorUpper}
\textnormal{\textbf{1.}}
For any $N$ and $t$,
there exists an $(N \times t)$ testing matrix $X$ such that
the error probability $\e_s(\text{$\tau$-WDR}, X) \le \overline{\e}_s(\tau, N)$,
where the bound $\overline{\e}_s(\tau, N)$ does not depend
on the number of elements $t$ and has the form:
\begin{align}
\label{upperErr}
\overline{\e}_s(\tau, N) &= 2^{ -N \underline{E}(s, \tau) (1 + o(1)) }, \text{ as }
N \to \infty,
\\
\label{lowerEExpr}
\underline{E}(s, \tau) &\eq \A(s, Q^*(s, \tau), \tau),
\end{align}
where $\A(s, Q, \tau)$ is defined by~(\ref{exprA})-(\ref{qSmall}) and $Q^*(s, \tau)$ is a unique solution of the equation
\begin{equation}
\label{AMinEq}
\A(s, Q, \tau) = \A(s + 1, Q, \tau), \quad \max \left\{ 1 - (1 - \tau)^{1 / (s + 1)}, \frac{\tau}{s} \right\} < Q < 1 - (1 - \tau)^{1 / s}.
\end{equation}
\textnormal{\textbf{2.}}
The optimal value of $\underline{E}(s, \tau)$
satisfies the asymptotic inequality:
\begin{equation}
\label{lowerEAs}
\Ewdr(s) \eq \max_{0 < \tau < 1} \underline{E}(s, \tau) \ge \frac{\log_2 e}{4s^2} (1 + o(1)), \quad s \to \infty,
\end{equation}
where the right-hand side is attained at the parameters that satisfy
$\tau \sim s \cdot Q = o(1)$, and $Q \cdot s^2 \to\infty$.
\end{theorem}

Independence from the number of elements $t$ is crucial in this bound.
It means that one can construct a sequence of $(N \times t(N))$ matrices
with exponentially decreasing error probability for any function $t(N)$.
Recall that by Theorem~\ref{thCapacityUpper} the rate $R = (\log_2 t(N)) / N$ has to be $\le 1/s$ if the error probability for the COMP decision rule vanishes as $N\to\infty$.
That is why the $\tau$-WDR decision rule has a significant advantage
over the COMP decision rule for the large number of elements $t$.

The next converse theorem derives the lower bound on the error probability
for the worst distribution and any decision rule.

\begin{theorem}
\label{thErrorLower}
Let $\p$ be such that $p_s > 0$, $p_{s + 1} > 0$ and $p_s + p_{s + 1} = 1$.
For any decision rule $\D$ and any testing matrix $X$,
the error probability is lower bounded by:
\begin{equation}
\label{lowerErr}
\e_s(\p, \D, X) \ge \frac{1}{2} \( 2^{- N / s} \frac{t}{t - s} - \frac{s}{t - s} \).
\end{equation}
\end{theorem}

The bound~(\ref{lowerErr}) makes sense only for $t\ge s2^{N/s}$.
If so and the rate $R= \log_2 t / N$ is fixed, this bound means
that the decreasing rate of the error probability
cannot be larger than exponential with respect to the number of tests $N$. In particular, it follows that the lower bound~\eqref{lowerEAs} on the error exponent, which is presented in Theorem~\ref{thErrorUpper} and equals the logarithm of the error probability,
is suboptimal by a multiplicative factor $4s \ln 2$.

The numerical values of the optimal lower bound $\Ewdr(s)$ on the error exponent
along with the corresponding optimal weight parameter $\tau = \tau(s)$
and the ensemble parameter $Q = Q(s)$
are presented in~Table~\ref{tabErrExp}. The table also depicts
the values of $\Ecomp(s, 0) \eq \lim\limits_{R \to 0} \Ecomp(s, R)$
(the maximal known lower bound on the error exponent for COMP and positive rate),
$\CapComp(s) \eq \sup\{ R : \Ecomp_s(R) > 0 \}$
(the maximal rate for which the known lower bound on the error exponent for COMP is positive)
and $\Rwdr(s) \eq \sup\{ R : \Ecomp_s(R) > \Ewdr(s) \}$
(the maximal rate for which the known lower bound on the error exponent for COMP is better than for $\tau$-WDR).
Also these relations are presented on Figure~\ref{figErrExp}.

\begin{table}[ht]
\caption{The numerical values of the lower bounds on the error exponents}
\label{tabErrExp}
\begin{center}
\begin{tabular}{|c|ccccc|}
\hline
$s$ & $2$ & $3$ & $4$ & $5$ & $6$ \\%& $7$ & $8$\\
\hline
$\Ewdr(s)$ & $0.1380$ & $0.0570$ & $0.0311$ & $0.0196$ & $0.0135$ \\%& $0.0098$ & $0.0075$\\
\hline
$\tau(s)$ & $0.2065$ & $0.1365$ & $0.1021$ & $0.0816$ & $0.0679$ \\%& $0.0582$ & $0.0509$\\
\hline
$Q(s)$ & $0.1033$ & $0.0455$ & $0.0255$ & $0.0163$ & $0.0113$ \\%& $0.0083$ & $0.0064$\\
\hline
$\Ecomp_s(0)$ & $0.3651$ & $0.2362$ & $0.1754$ & $0.1397$ & $0.1161$ \\%& $0.0994$ & $0.0869$\\
\hline
$\CapComp(s)$ & $0.3832$ & $0.2455$ & $0.1810$ & $0.1434$ & $0.1188$ \\%& $0.1014$ & $0.0884$\\
\hline
$\Rwdr(s)$ & $0.2271$ & $0.1792$ & $0.1443$ & $0.1201$ & $0.1027$ \\%& $0.0896$ & $0.0794$\\
\hline
\end{tabular}
\end{center}
\end{table}

\begin{figure}[ht]
\begin{center}
\caption{The lower bounds on the error exponents}
\label{figErrExp}
\def\svgwidth{.45\textwidth}
\input{graphErrExp.pdf_tex}
\end{center}
\end{figure}

\section{Simulation}
\label{secModul}
For finite $N$ and $t$, we carried out a simulation as follows.
The probability distribution vector $\p$ is defined by
$$
p_s = p_{s+1} = 1/2, \qquad p_k = 0 \quad \forall \, k \in[t]\setminus \{s, s+1\},
$$
i.e., $\p$ is a distribution at which the maximum in the right-hand side of~(\ref{uniError}) is attained
for the COMP and the $\tau$-WDR decision rules.
A matrix $X$ is generated randomly from the ensemble of constant column weight matrices, i.e.,
for some weight parameter $w$, $1\le w\le N$, each column of $X$ is chosen independently and equiprobably
from the set of all ${N \choose w}$ columns of weight $w$. For every weight $w$ and every decision rule,
we repeat the procedure $1000$ times and choose the matrix
with the minimal error probability.
Some results of simulation are presented in Table~\ref{tabSim15}.
The best values of the error probability
for fixed parameters $s$, $t$ and $N$ are given in boldface.

\begin{table}[ht]
\caption{Results of simulation}
\label{tabSim15}
\begin{center}
\begin{tabular}{|c|cccc|cc|}
\hline
& \multicolumn{4}{|c|}{$\tau$-WDR decision rule}
& \multicolumn{2}{|c|}{COMP decision rule}\\
\hline
$N$ & $\Pr\{\text{accept } H_1 | H_0\}$ & $\Pr\{\text{accept } H_0 | H_1\}$ & $w$ & $\lfloor \tau N \rfloor$
& $\Pr\{\text{accept } H_1 | H_0\}$ & $w$\\
\hline
\multicolumn{7}{c}{$s = 2, \quad t = 15$}\\
\hline
$5$ & $0.2571$ & $\mathbf{0.2571}$ & $2$ & $3$ & $0.9333$ & $2$\\
\hline
$8$ & $\mathbf{0.1619}$ & $0.1604$ & $3$ & $5$ & $0.7048$ & $2$\\
\hline
$10$ & $0$ & $\mathbf{0.1429}$ & $1$ & $2$ & $0.4571$ & $3$\\
\hline
$12$ & $0$ & $\mathbf{0.0857}$ & $1$ & $2$ & $0.1810$ & $3$\\
\hline
$14$ & $0$ & $\mathbf{0.0571}$ & $1$ & $2$ & $0.0952$ & $3$\\
\hline
$15$ & $0$ & $0.0462$ & $2$ & $4$ & $\mathbf{0.0286}$ & $3$\\
\hline
\multicolumn{7}{c}{$s = 2, \quad t = 20$}\\
\hline
$5$ & $\mathbf{0.2632}$ & $0.2588$ & $2$ & $3$ & $0.9579$ & $2$\\
\hline
$8$ & $0.1632$ & $\mathbf{0.1649}$ & $3$ & $5$ & $0.8316$ & $2$\\
\hline
$11$ & $0.1053$ & $\mathbf{0.1509}$ & $4$ & $7$ & $0.5158$ & $3$\\
\hline
$12$ & $\mathbf{0.1158}$ & $0.1123$ & $4$ & $7$ & $0.4158$ & $3$\\
\hline
$14$ & $0$ & $\mathbf{0.0842}$ & $2$ & $4$ & $0.2316$ & $3$\\
\hline
$15$ & $0$ & $\mathbf{0.0693}$ & $2$ & $4$ & $0.1526$ & $4$\\
\hline
\multicolumn{7}{c}{$s = 2, \quad t = 100$ \quad (Estimated error probabilities)}\\
\hline
$5$ & $\mathbf{0.2420}$ & $0.2300$ & $2$ & $3$ & $0.9980$ & $2$\\
\hline
$8$ & $0.1830$ & $\mathbf{0.1950}$ & $3$ & $5$ & $0.9940$ & $5$\\
\hline
$11$ & $0.1570$ & $\mathbf{0.1630}$ & $5$ & $8$ & $0.9830$ & $4$\\
\hline
$12$ & $0.1280$ & $\mathbf{0.1350}$ & $4$ & $7$ & $0.9810$ & $4$\\
\hline
$14$ & $0$ & $\mathbf{0.1080}$ & $2$ & $4$ & $0.9600$ & $5$\\
\hline
$15$ & $0$ & $\mathbf{0.0970}$ & $2$ & $4$ & $0.9610$ & $5$\\
\hline
\end{tabular}
\end{center}
\end{table}

For $s=2$, any number of tests $N$ from Table~\ref{tabSim15} and an arbitrary number of columns $t$, $t > N$, it is recommended
to choose the corresponding column weight $w$, $1 < w < N$,
specified in Table~\ref{tabSim15} and generate an
``optimal'' random $(N \times t)$ constant column weight matrix with weight $w$.
So then, for the corresponding threshold $\tau$ depicted in Table~\ref{tabSim15},
an ``optimal'' error probability for the $\tau$-WDR decision rule should be similar
to the corresponding one indicated in Table~\ref{tabSim15}
in boldface. As an example of such comparison, we put in Table~\ref{tabSim15}
the error probabilities for $s = 2$ and $t = 100$ which were estimated by the Monte Carlo method,
namely, subsets $\S$, $\S \subseteq [100]$, of size $|\S| = 2$ and $|\S| = 3$ were chosen randomly $1000$ times.

The results of simulation verify the advantage of the $\tau$-WDR decision rule
over the COMP decision rule and the independence of the error probability for $\tau$-WDR decision rule
from the number of elements $t$.

\section{Proofs of Main Results}
\label{secProofs}

\subsection{Proof of Lemma~\ref{lemWorstProb}}
\label{secProofLemWorstProb}
\begin{proof}
	For a fixed $(N \times t)$-matrix $X$ and parameters $s$ and $T \eq \lfloor \tau N \rfloor$, introduce the sets $B^i_k(T, X)$,
	$i = 1, 2$, $k = 0, 1, \dots, t$, of $k$-subsets of set $[t]$ as follows:
	\begin{equation}
	\label{Bk}
	\begin{split}
	B^1_k(T, X) &\eq \, \left\{ \, \S \,:\, \S \subseteq [t], \; |\S| = k, \; |\x(\S)| \ge T + 1 \right\},\\
	B^2_k(T, X) &\eq \, \left\{ \, \S \,:\, \S \subseteq [t], \; |\S| = k, \; |\x(\S)| \le T \right \}.
	\end{split}
	\end{equation}
	Then the error probability for the $\tau$-WDR decision rule is represented by
	\begin{equation}
	\label{maxerror2}
	\e_s(\p, \text{$\tau$-WDR}, X) \eq \max \Bigg\{ \sum_{k = 0}^{s} \frac{p_k}{\sum\limits_{l = 0}^s p_l} \frac{\card{B^1_k(T, X)}}{{t \choose k}},
	\sum_{k = s+1}^{t} \frac{p_k}{\sum\limits_{l = s+1}^t p_l} \frac{\card{B^2_k(T, X)}}{{t \choose k}} \Bigg\}.
	\end{equation}
	
	For any $k<t$, $\S\in B^1_k(T, X)$, and $j\in[t]\setminus \S$,  one can construct a set $\S'=\S\cup \{j\}$
	belonging to $B^1_{k + 1}(T, X)$. Moreover, there exist at most $k+1$ ways leading to the same set $\S'\in B^1_{k + 1}(T, X)$. This implies the following inequality:
	$$
	|B^1_{k+1}(T, X)| \ge \frac{t-k}{k+1} |B^1_k(T, X)|.
	$$
	Similarly, one can construct set $\S \in B^2_k(T, X)$ by removing from any set $\S' \in B^2_{k + 1}(T, X)$
	any index $j \in \S'$, and at most $(t - k)$ such different pairs $(\S', j)$
	may construct the same $\S \eq \S' \setminus \{j\}$. Therefore
	$$
	|B^2_{k}(T, X)| \ge \frac{k+1}{t-k} |B^2_{k+1}(T, X)|.
	$$
	Definition~(\ref{maxerror2}) and these inequalities yield
	\begin{equation}
	\label{maxerrorUpper}
	\e_s(\p, \text{$\tau$-WDR}, X) \le \max \left\{ \frac{\card{B^1_s(T, X)}}{{t \choose s}}, \frac{\card{B^2_{s+1}(T, X)}}{{t \choose s+1}} \right\},
	\end{equation}
	and the equality~(\ref{maxerrorUpper}) holds for any distribution with the properties:
	$p_s > 0$, $p_{s + 1} > 0$, and $p_j = 0$ for $ j \in [t]\setminus\{s, s+1\}$.
	In particular, it means that for $\tau$-WDR the definition of the universal error probability~(\ref{uniError})
	is equivalent to the right-hand side of~(\ref{maxerrorUpper}).
\end{proof}

\subsection{Proof of Theorem~\ref{thErrorLower}}
\label{secProofThErrorLower}
\begin{proof}
Let an $(N \times t)$-matrix $X$ be any testing matrix,
$\D: \{0, 1\}^N \to \{H_0, H_1\}$ be any decision rule
and $\p$ be a distribution so that $p_s > 0$, $p_{s + 1} > 0$ and $p_j = 0$ for $j \in [t]\setminus\{s, s+1\}$.
First, the maximal error probability~(\ref{maxError}) is bounded below
by the half of the sum:
\begin{equation}
\label{maxErrorSum}
\e_s(\p, \D, X) \ge \frac{1}{2} \( \Pr\{ \text{accept } H_1 \big| H_0 \} + \Pr\{ \text{accept } H_0 \big| H_1 \} \).
\end{equation}
Denote the number of $k$-subsets with the response vector $\y$ by $n_k(\y, X)$, i.e.,
$$
n_k(\y, X) \eq \left| \{ \S : |\S| = k, \; \x(\S) = \y \} \right|.
$$
The considered special type of distribution $\p$ allows to rewrite the error probabilities in a simple form.
The right-hand side of~(\ref{maxErrorSum}) can be represented as follows
\begin{equation}
\label{maxErrorBigSum}
\e_s(\p, \D, X) \ge \frac{1}{2} \sum_{\y \in \{0, 1\}^N} \(
\frac{n_s(\y, X)}{{t \choose s}} \I \{\D(\y) \not= H_0\} +
\frac{n_{s + 1}(\y, X)}{{t \choose s + 1}} \I \{\D(\y) \not= H_1\} \).
\end{equation}
One of the two indicators $\I \{\D(\y) \not= H_0\}$, $\I \{\D(\y) \not= H_1\}$
equals $0$ and the other one equals $1$. It is easy to understand which decision rule $\D$ minimizes the right-hand side of (\ref{maxErrorBigSum}), therefore
\begin{equation}
\label{maxErrorMinSum}
\e_s(\p, \D, X) \ge \frac{1}{2} \sum_{\y \in \{0, 1\}^N}
\min \left\{ \frac{n_s(\y, X)}{{t \choose s}} ,
\frac{n_{s + 1}(\y, X)}{{t \choose s + 1}} \right\}.
\end{equation}
Further we consider only those $\y$ for which $n_s(\y, X) > 0$.
It is obvious that for other $\y$ the minimum in the sum~(\ref{maxErrorMinSum}) equals $0$.
Denote the relative number of $s$-subsets with the response vector $\y$ by $\beta_\y$, i.e.,
$\beta_\y \eq n_s(\y, X) / {t \choose s}$, and note that
$$
n_s(\y, X) = \beta_\y {t \choose s} = \beta_\y \frac{(t - s + 1) \dots t}{s!}
\ge \frac{(\beta_\y^{\frac{1}{s}} t - s + 1) \dots (\beta_\y^{\frac{1}{s}} t)}{s!}
= {\beta_\y^{\frac{1}{s}} t \choose s}
$$
because $0 < \beta_\y \le 1$. By $\S_\y$ denote a set of all column's indexes which are included
into some $s$-subset $\S$ for which the response vector $\x(\S)=\y$, i.e.,
$$
\S_\y = \bigcup_{\S : \x(\S) = \y} \S,
$$
and suppose that $|\S_\y| = s + L$. The previous inequality and this assumption lead to
$$
{\beta_\y^{\frac{1}{s}} t \choose s} \le n_s(\y, X) \le {s + L \choose s}.
$$
It gives $L \ge \beta_\y^{\frac{1}{s}} t - s$ (the right-hand side can be replaced by the ceiling).
Given $\S$, $|\S|=s$, with the response vector $\x(\S) = y$, and index $j\in \S_\y \setminus \S$, one
one can construct an $(s + 1)$-subset $\S'=\S\cup\{j\}$ with the same response vector $\x(\S')=\y$.
Moreover, any $\S'$ can be constructed in at most $(s + 1)$ such ways. Hence
\begin{equation}
\label{nyLowerBound}
n_{s + 1}(\y, X) \ge  n_{s}(\y, X)\frac{L}{s+1}\ge \beta_\y {t \choose s} (\beta_\y^{\frac{1}{s}} t - s) \frac{1}{s + 1} =
\( \beta_\y^{\frac{s + 1}{s}} \frac{t}{t - s} - \beta_\y \frac{s}{t - s} \) {t \choose s + 1}.
\end{equation}
Recall that $0 < \beta_\y \le 1$. Therefore, the following inequality holds:
$$
\beta_\y^{\frac{s + 1}{s}} \frac{t}{t - s} - \beta_\y \frac{s}{t - s} \le \beta_\y.
$$
That is why the lower bound~(\ref{nyLowerBound}) also gives a lower bound
on the minimum in the sum~(\ref{maxErrorMinSum}) and one can derive
$$
\e_s(\p, \D, X) \ge \frac{1}{2} \sum_{\y \in \{0, 1\}^N : \beta_\y > 0}
\( \beta_\y^{\frac{s + 1}{s}} \frac{t}{t - s} - \beta_\y \frac{s}{t - s} \) \ge
\frac{1}{2} \( 2^{-\frac{N}{s}} \frac{t}{t - s} - \frac{s}{t - s} \),
$$
where we use the property of values $\beta_\y$ that their sum equals $1$, i.e.,
$\sum_{\y \in \{0, 1\}^N} \beta_\y = 1$, and Jensen's inequality for a $\cup$-convex function $f(x) = x^{-\frac{1}{s}}$:
$$
\sum_{\y \in \{0, 1\}^N : \beta_\y > 0} \beta_\y f(\beta_\y^{-1}) \ge f\( \sum_{\y \in \{0, 1\}^N : \beta_\y > 0} \beta_\y \cdot \beta_\y^{-1} \).
$$
\end{proof}



\subsection{Proof of Theorem~\ref{thErrorUpper}}
\label{secProofThErrorUpper}
\begin{proof}[Proof of Statement 1]
Fix $s \ge 2$, $t \ge s + 1$, $N \ge 2$, $0 < \tau < 1$ and a parameter $Q, \; \frac{\tau}{s} < Q < \tau$.
The bound~(\ref{upperErr}) is obtained by the probabilistic method.
Define an ensemble of constant column weight matrices~\cite{drr89} as
ensemble $E(N, t, Q)$ of binary matrices $X$ with $N$ rows and $t$ columns,
where the columns are chosen independently and equiprobably from the set
of all ${N \choose \lfloor QN \rfloor}$ columns of a fixed weight $\lfloor QN \rfloor$.

By Lemma~\ref{lemWorstProb} the error probability can be rewritten as
\begin{equation}
\label{maxerrorFinal}
\e_s(\text{$\tau$-WDR}, X) \eq \max \left\{ \frac{\card{B^1_s(\lfloor \tau N \rfloor, X)}}{{t \choose s}}, \frac{\card{B^2_{s+1}(\lfloor \tau N \rfloor, X)}}{{t \choose s+1}} \right\},
\end{equation}
where the sets $B^1_s(\lfloor \tau N \rfloor, X)$ and $B^2_{s+1}(\lfloor \tau N \rfloor, X)$ are defined by~(\ref{Bk}).
For the ensemble $E(N, t, Q)$, denote the expectation of the error probability~(\ref{maxerrorFinal}) by
\begin{equation}
\label{exError}
\ee_s(\tau, Q, N, t) \eq \Ex \Big[ \e_s(\text{$\tau$-WDR}, X) \Big].
\end{equation}
It is obvious that there exists a matrix $X$ with $N$ rows and $t$ columns such that
its error probability~(\ref{maxerrorFinal})
is upper bounded by $\ee_s(\tau, Q, N, t)$ minimized over all admissible $Q$.
Further we show that the logarithmic asymptotics of this value equals~(\ref{lowerEExpr}). Define
\begin{equation}
\label{lowerEGen}
\underline{E}(s, \tau) \eq
\max_{\tau / s < Q < \tau} \, \lim_{N \to \infty} \frac{- \log_2 \ee_s(\tau, Q, N, t)}{N}.
\end{equation}
The cardinality of set $B_s^1(\lfloor \tau N \rfloor, X)$
can be expressed through indicator functions:
$$
\card{B_s^1(\lfloor \tau N \rfloor, X)} = \sum_{\S \subseteq [t], |S| = s} \I\big\{ \S \in B_s^1(\lfloor \tau N \rfloor, X) \big\}.
$$
Therefore, the expectation of the cardinality $\card{B_s^1(\lfloor \tau N \rfloor, X)}$
(and similarly, $\card{B_{s+1}^2(\lfloor \tau N \rfloor, X)}$) equals
\begin{equation}
\label{exBk}
\begin{split}
\Ex \Big[ \card{B_s^1} \Big] &= {t \choose s} \Pr \big\{ \S \in B_s^1 \, \big| \, |\S| = s \big\}\\
\Bigg( \Ex \Big[ \card{B_{s+1}^2} \Big] &= {t \choose s+1} \Pr \big\{ \S \in B_{s+1}^2 \, \big| \, |\S| = s + 1 \big\} \Bigg).
\end{split}
\end{equation}

For the ensemble $E(N, t, Q)$, denote the probabilities $\Pr \big\{ \S \in B_s^1(\lfloor \tau N \rfloor, X) \, \big| \, |\S| = s \big\}$
and $\Pr \big\{ \S \in B_{s+1}^2(\lfloor \tau N \rfloor, X) \, \big| \, |\S| = s+1 \big\}$ by
$P_s^1(\tau, Q, N)$ and $P_{s+1}^2(\tau, Q, N)$, respectively. It is obvious, that these probabilities
depend only on $s$, $\tau$, $Q$, $N$ and do not depend on $t$.
The formulas~(\ref{exBk}) yield that the expectation~(\ref{exError})
satisfies the inequalities:
\begin{align}
\label{exErrorInequal}
\max \left\{ P_s^1(\tau, Q, N), P_{s+1}^2(\tau, Q, N) \right\} \le
\ee_s(\tau, Q, N, t)
\le P_s^1(\tau, Q, N) + P_{s+1}^2(\tau, Q, N).
\end{align}

Given matrix $X$, for a fixed subset $\S \subseteq [t]$, $|\S| = k$, of size $k$ and a fixed integer $w$, consider a probability
\begin{equation}
\label{probForWeight}
P_k^N(Q, w) \eq \Pr \Bigg\{ \Bigg| \bigvee_{j \in \S} \x(j) \Bigg| = w \Bigg\}.
\end{equation}
Note that the probability $P_k^N(Q, w)$ does not depend on the choice of the set $\S$
and depends only on $k$, $w$, $N$ and $Q$.
Probabilities $P_s^1(\tau, Q, N)$ and $P_{s+1}^2(\tau, Q, N)$ can be rewritten as follows:
\begin{equation}
\label{probForm}
\begin{split}
P_s^1(\tau, Q, N) &= \sum_{w = \lfloor \tau N \rfloor + 1}^{\min\{N, s \lfloor QN \rfloor\}}
P_s^N(Q, w), \\
P_{s+1}^2(\tau, Q, N) &= \sum_{w = \lfloor QN \rfloor}^{\lfloor \tau N \rfloor}
P_{s+1}^N(Q, w).
\end{split}
\end{equation}

The logarithmic asymptotics of the probability $P_k^N(Q, w)$ was calculated in~\cite{d15}.
To make the present paper self-contained, we repeat the proof in Section~\ref{secProofsOfLemmas}.
\begin{lemma}
\label{lemProbAs}
If $q$ satisfies $Q < q < \min\{kQ, 1\}$, then
\begin{equation}
\label{probWeightAs}
\lim_{N \to \infty} \frac{- \log_2 P_k^N(Q, \lfloor qN \rfloor) }{N} = \A(k, Q, q),
\end{equation}
where the function $\A(k, Q, q)$ is defined by~(\ref{exprA})-(\ref{qSmall}).
\end{lemma}
In Section~\ref{secProofsOfLemmas} we prove the following analytical properties:
\begin{lemma}
\label{lemAProps}
\textnormal{\textbf{1.}}
Function $\A(k, Q, q)$ as a function of the parameter $q$ decreases in the interval
$q \in (Q, 1 - (1 - Q)^k]$, increases in the interval $q \in [1 - (1 - Q)^k, \min\{1, kQ\})$
and equals $0$ at the point $q = 1 - (1 - Q)^k$.
\newline
\textnormal{\textbf{2.}}
Function $\A(k, Q, q)$ as a function of the parameter $Q$ decreases in the interval
$Q \in (\frac{q}{k}, 1 - (1 - q)^{1 / k}]$, increases in the interval $Q \in [1 - (1 - q)^{1 / k}, q)$
and equals $0$ at the point $Q = 1 - (1 - q)^{1 / k}$.
\end{lemma}

One can obtain the logarithmic asymptotics of the probabilities $P_s^1(\tau, Q, N)$ and $P_{s+1}^2(\tau, Q, N)$
from formulas (\ref{probForm}) and (\ref{probWeightAs}):
\begin{equation}
\label{probAs}
\begin{split}
&\lim_{N \to \infty} \frac{- \log_2 P_s^1(\tau, Q, N)}{N} = \min_{q \in (\text{i}1)} \A(s, Q, q),\\
&\lim_{N \to \infty} \frac{- \log_2 P_{s+1}^2(\tau, Q, N)}{N} = \min_{q \in (\text{i}2)} \A(s+1, Q, q),\\
&(\text{i}1) \eq [ \tau, \min\{1, sQ\} ], \quad
(\text{i}2) \eq [ Q, \tau ].
\end{split}
\end{equation}

Therefore, (\ref{exErrorInequal}) and (\ref{probAs}) yield the existence of the limit
\begin{equation}
\label{lowerEFirst}
\lim_{N \to \infty} \frac{- \log_2 \ee_s^N(\tau, Q, N, t)}{N} =
\min \left\{ \min_{q \in (\text{i}1)} \A(s, Q, q),
\min_{q \in (\text{i}2)} \A(s+1, Q, q) \right\}.
\end{equation}
By Lemma~\ref{lemAProps} the function $\A(k, Q, q)$ equals $0$ at $q = 1 - (1 - Q)^k$. This property yields
\begin{align*}
\min_{q \in (\text{i}1)} \, &\A(s, Q, q) = 0 \; &&\text{ if } \tau \le 1 - (1 - Q)^s,\\
\min_{q \in (\text{i}2)} \, &\A(s+1, Q, q) = 0 \; &&\text{ if } \tau \ge 1 - (1 - Q)^{s + 1}.
\end{align*}
Finally, we exclude from~(\ref{lowerEGen}) values of $Q$
for which the minimum~(\ref{lowerEFirst}) equals $0$,
and from the monotonicity properties given in Lemma~\ref{lemAProps} we derive
\begin{align*}
\underline{E}(s, \tau) =
\max_{Q \in (\text{i}Q)} \, \min \left\{ \A(s, Q, \tau), \A(s+1, Q, \tau) \right\},\\
(\text{i}Q) \eq \(\max \left\{ 1 - (1 - \tau)^{1 / (s + 1)}, \frac{\tau}{s} \right\},
1 - (1 - \tau)^{1 / s} \).
\end{align*}
By applying the monotonicity properties given in the second statement
of Lemma~\ref{lemAProps} we finish the proof of Statement 1 of Theorem~\ref{thErrorUpper}.
\end{proof}

\begin{proof}[Proof of Statement 2]
We shall establish a lower bound on the asymptotic behaviour of the expression
\begin{equation}
\label{fullExpr}
\Ewdr(s) \eq \max_{0 < \tau < 1} \; \max_{Q \in (\text{i}Q)}
\min \left\{ \A(s, Q, \tau), \A(s+1, Q, \tau) \right\}, \quad s \to \infty.
\end{equation}

For any fixed $\tau$, $0 < \tau < 1$, and any fixed $Q$, $Q \in (\text{i}Q)$,
let us denote the solutions of the equation~(\ref{qSmall}) for $\A(s, Q, \tau)$ and $\A(s+1, Q, \tau)$ by
$y_1(Q, \tau)$ and $y_2(Q, \tau)$, respectively. Note that $y_1$ can be greater than $1$.
It follows from~(\ref{qSmall}) that the parameter $\tau$ can be expressed in two forms:
$$
\tau = Q \frac{1 - y_1^s}{1 - y_1} = Q \frac{1 - y_2^{s+1}}{1 - y_2}.
$$
This means that the inequality $1 - (1 - \tau)^{1 / (s + 1)} < Q \Leftrightarrow \tau < 1 - (1 - Q)^{s + 1}$ is equivalent to
$$
\frac{1 - y_2^{s+1}}{1 - y_2} < \frac{1 - (1 - Q)^{s+1}}{1 - (1 - Q)}.
$$
Note that, for any integer $n \ge 2$, the function $f(x) = \frac{1 - x^n}{1 - x}$ is increasing in the interval $x \in (0, +\infty)$.
Hence, we have
\begin{align*}
1 - (1 - \tau)^{1 / (s + 1)} < Q \quad &\Leftrightarrow \quad Q < 1 - y_2,\\
\text{and similarly},\\
Q < 1 - (1 - \tau)^{1 / s} \quad &\Leftrightarrow \quad Q > 1 - y_1.
\end{align*}

In conclusion, a pair of parameters $(y_1, Q)$, $y_1 > 0$, $0 < Q < 1$, uniquely defines the parameters
$\tau$ and $y_2$. Moreover, if the inequalities
\begin{equation}
\label{regionDef}
0 < \tau < 1, \quad
Q < 1 - y_2, \quad
Q > 1 - y_1.
\end{equation}
hold, then the parameters $\tau$ and $Q$ are in the region, in which the maximum~(\ref{fullExpr}) is searched.

Let some constant $c > 0$ be fixed, $s \to \infty$ and $y_1 \eq 1 - c / s^2 + o(1 / s^3)$.
Then, the asymptotic behavior of $\tau / Q$ equals
$$
\frac{1 - y_2^{s+1}}{1 - y_2} = \frac{\tau}{Q} = \frac{1 - y_1^s}{1 - y_1} = s - \frac{c}{2} + o(1),
$$
and, therefore,
$$
y_2 = 1 - \frac{c+2}{(s+1)^2} + o\(\frac{1}{s^3}\) = 1 - \frac{c + 2}{s^2} + \frac{2 (c + 2)}{s^3} + o\(\frac{1}{s^3}\).
$$
To satisfy the inequalities~(\ref{regionDef}) the parameter $Q$ should be in the interval
\begin{align*}
\Bigg( 1 - y_1 = \frac{c}{s^2} + o\(\frac{1}{s^3}\),\,
1 - y_2 = \frac{c+2}{s^2} - \frac{2 (c+2)}{s^3} + o\(\frac{1}{s^3}\) \Bigg).
\end{align*}
Let us define the parameter $Q$ as $Q \eq d / s^2$, where $d$, $c < d < c + 2$, is some constant.
Hence, $Q$ is in that interval.

The full list of the asymptotic behaviors of the parameters is presented below:
\begin{equation}
\label{allAsympt}
\begin{split}
&\tau = \frac{d}{s} - \frac{cd}{2s^2} + o\(\frac{1}{s^2}\), \\
&Q = \frac{d}{s^2}, \\
&y_1 = 1 - \frac{c}{s^2} + o\(\frac{1}{s^2}\),\\
&y_2 = 1 - \frac{c+2}{s^2} + o\(\frac{1}{s^2}\), \quad s \to \infty,
\end{split}
\end{equation}
where $c$ and $d$ are arbitrary constants such that $c > 0$, $c < d < c + 2$.
The parameters defined by~(\ref{allAsympt}) satisfy the inequalities~(\ref{regionDef}), and, therefore,
the substitution of asymptotic behaviors~(\ref{allAsympt}) into~(\ref{fullExpr}) leads to
some lower bound on $\Ewdr(s)$.

Let us calculate the asymptotics of
\begin{align*}
\frac{\A(s, Q, \tau)}{\log_2 e} = (1 - \tau) \ln (1 - \tau)
+ (sQ - \tau) \ln \[\frac{1 - y_1}{Q}\]
+ s (\tau - Q) \ln y_1 - s(1 - Q) \ln (1 - Q).
\end{align*}
The first two terms of the asymptotic expansion of the summands are
\begin{align*}
(1 - \tau) \ln (1 - \tau) &= -\frac{d}{s} + \frac{cd}{2s^2} + \frac{d^2}{2s^2} + o\(\frac{1}{s^2}\),\\
(sQ - \tau) \ln \[\frac{1 - y_1}{Q}\] &= \frac{cd}{2s^2} \ln \[\frac{c}{d}\] + o\(\frac{1}{s^2}\),\\
s (\tau - Q) \ln y_1 &= -\frac{cd}{s^2} + o\(\frac{1}{s^2}\),\\
- s(1 - Q) \ln (1 - Q) &= \frac{d}{s} + o\(\frac{1}{s^2}\).
\end{align*}
Therefore,
$$
\frac{\A(s, Q, \tau)}{\log_2 e} = \frac{d(d - c + c \ln [c / d])}{2s^2} + o\(\frac{1}{s^2}\).
$$

Further, let us calculate the asymptotics of
\begin{align*}
\frac{\A(s + 1, Q, \tau)}{\log_2 e} &= (1 - \tau) \ln (1 - \tau)
+ (sQ - \tau) \ln \[\frac{1 - y_2}{Q}\]
+ s (\tau - Q) \ln y_2 - s(1 - Q) \ln (1 - Q)\\
&+ Q \ln \[\frac{1 - y_2}{Q}\]
+ (\tau - Q) \ln y_2 - (1 - Q) \ln (1 - Q).
\end{align*}
The first two terms of the asymptotic expansion of the new summands equals
\begin{align*}
(sQ - \tau) \ln \[\frac{1 - y_2}{Q}\] &= \frac{cd}{2s^2} \ln \[\frac{c+2}{d}\] + o\(\frac{1}{s^2}\),\\
s (\tau - Q) \ln y_2 &= -\frac{(c+2)d}{s^2} + o\(\frac{1}{s^2}\),\\
Q \ln \[\frac{1 - y_2}{Q}\] &= \frac{d}{s^2} \ln \[\frac{c+2}{d}\] + o\(\frac{1}{s^2}\),\\
(\tau - Q) \ln y_2 &= o\(\frac{1}{s^2}\).
\end{align*}
Therefore,
$$
\frac{\A(s+1, Q, \tau)}{\log_2 e} = \frac{d(d - c - 2 + (c + 2) \ln [(c + 2) / d])}{2s^2}
+ o\(\frac{1}{s^2}\).
$$

Finally, the maximum value
$$
\max_{c > 0} \; \max_{c < d < c + 2} \; \min \bigg\{ d\(d - c + c \ln \[\frac{c}{d}\]\),
d\(d - c - 2 + (c + 2) \ln \[\frac{c + 2}{d}\]\) \bigg\}
$$
is at least $\frac{1}{2}$, that is attained at $c \to \infty$ and $d = c + 1$.
\end{proof}

\subsection{Proofs of Analytical Lemmas}
\label{secProofsOfLemmas}

\begin{proof}[Proof of Lemma~\ref{lemProbAs}]
Let $w \eq \lfloor qN \rfloor$.
We will use the terminology of \textit{types}~\cite{ck81}. Consider an arbitrary set of size $k$
consisting of binary columns of height $N$ and weight $\lfloor QN \rfloor$:
$(\x(1), \dots, \x(k))$, where $\x(i) \in \{0, 1\}^N, ~\forall i \in [k]$.
The set forms $(N \times k)$-matrix $X_k$. Let $\u \eq (u_1, \dots, u_k) \in \{0, 1\}^k$ is a row.
Denote a \textit{type} of the matrix $X_k$ by $\{n(\u)\}$, where $n(\u)$, $0 \le n(\u) \le N$,
is the number of rows $\u$ in the matrix $X_k$. Obviously, for any matrix $X_k$ we have
$
\sum_{\u} n(\u) = N.
$
By $n(\0)$ ($n(\1)$) denote the number of the rows in $X_k$ consisting of all zeros (ones).
It allows to represent the probability~(\ref{probForWeight}) as follows:
\begin{equation}
\label{probByTypes}
P_k^N(Q, w) = {N \choose \lfloor QN \rfloor }^{-k} \cdot
\sum \limits_{(\ref{typesCond})} \frac{N!}{\prod_{\u} n(\u)!},
\end{equation}
where the sum is taken over all types $\{n(\u)\}$ such that
\begin{equation}
\label{typesCond}
\sum_{\u} n(\u) = N, \qquad n(\0) = N - w, \qquad \sum \limits_{\u: \, u_i = 1} n(\u) = \lfloor QN \rfloor \quad \text{for any } i \in [k].
\end{equation}
Denote the logarithmic asymptotics of the probability~(\ref{probByTypes}) by
\begin{equation}
\label{A}
\A(k, Q, q) \eq \lim \limits_{N \to \infty} \frac{-\log_2 P_k^N(Q, \lfloor qN \rfloor)}{N}, \quad Q < q < \min\{1, kQ\}.
\end{equation}
Let $N \to \infty$. For every type $\{n(\u)\}$, consider the corresponding distribution
$\rho: \rho(\u) = \frac{n(\u)}{N}$, $\forall \, \u \in \{0, 1\}^k$.
Applying the Stirling's approximation, we obtain the following logarithmic asymptotic behavior
of the summand in the sum~(\ref{probByTypes}):
$$
-\log_2 \frac{N!}{\prod_{\u} n(\u)!} {N \choose \lfloor QN \rfloor}^{-k} = N F(\rho, Q, q)(1 + o(1)), \quad \text{where}
$$
\begin{equation}
\label{FNeedToMin}
F(\rho, Q, q) = \sum_{\u} \rho(\u) \log_2 \rho(\u) + k \cdot h(Q).
\end{equation}
Thus, to calculate $\A(k, Q, q)$ one needs to find the following minimum:
\begin{equation}
\label{FProblem}
\A(k, Q, q) = \min_{\rho \in (\ref{FRegion}): (\ref{FRestrictions})} F(\rho, Q, q),
\end{equation}
\begin{equation}
\label{FRegion}
\left\{ \rho:~\forall~\u = (u_1,\dots, u_k) \in \{0,1\}^k \quad 0 < \rho(\u) < 1 \right\},
\end{equation}
\begin{equation}
\label{FRestrictions}
\sum_{\u} \rho(\u) = 1, \qquad \rho(\0) = 1 - q, \qquad \sum_{\u: u_i = 1} \rho(\u) = Q \quad \forall~i \in [k],
\end{equation}
where restrictions~(\ref{FRestrictions}) are induced by~(\ref{typesCond}).

To find the extremal distribution $\rho$ we apply the standard Lagrange multipliers method. Consider the Lagrangian:
\begin{align*}
\Lambda &\eq \sum_{\rho(\u)} \rho(\u) \log_2 \rho(\u) + sh(Q) + \lambda_0 \(\rho(\0) + q - 1\) \\
&+ \sum_{i = 1}^k \lambda_i \(\sum_{\u: u_i = 1} \rho(\u) - Q\) + \lambda_{k+1} \(\sum_{\u} \rho(\u) - 1\).
\end{align*}
The necessary conditions for the extremal distribution are
\begin{equation}
\label{FNecConditions}
\begin{cases}
\frac{\partial \Lambda}{\partial \rho(\0)} = \log_2 \rho(\0) + \log_2 e + \lambda_0 + \lambda_{k+1} = 0,\\
\frac{\partial \Lambda}{\partial \rho(\u)} = \log_2 \rho(\u) + \log_2 e + \lambda_{k+1} + \sum_{i = 1}^k u_i \lambda_i = 0 \quad \forall \, \u \neq \0.
\end{cases}
\end{equation}

It is obvious that the matrix of second derivatives of the Lagrangian is diagonal,
so this matrix is positive definite in the domain~(\ref{FRegion}).
Therefore~\cite{opu}, $F(\rho, Q)$ is strictly $\cup$-convex in the domain~(\ref{FRegion})
and any local minimum is also a global minimum.

Recall that the Karush-Kuhn-Tacker theorem~\cite{opu} states
that every solution $\rho \in (\ref{FRegion})$ is a local minimum of $F(\rho, Q)$ if it satisfies the restrictions~(\ref{FRestrictions})
and the system~(\ref{FNecConditions}) and has the positive definite
matrix of second derivatives of the Lagrangian in this point $\rho$.
Hence, if there exists a solution of~(\ref{FRestrictions}) and~(\ref{FNecConditions})
in the domain~(\ref{FRegion}), then this solution is a unique and is a solution
of the minimization problem~(\ref{FProblem})-(\ref{FRestrictions}).

Note that the symmetry of the problem yields equality: $\eta \eq \lambda_1 = \lambda_2 = \dots = \lambda_k$.
To prove this, we need to check that $\lambda_i = \lambda_j$ for $i \neq j$. Let $\bar\u_i \eq (0, \dots, 1, \dots, 0)$
be a row of length $k$, which has $1$ at the $i$-th position and $0$'s at the other positions.
A permutation of indices $i$ and $j$ leads to an equivalent problem. Hence, if $\rho_1$ is a solution,
then $\rho_2$ is also a solution, where $\rho_2(\u) \eq \rho_1(\tilde \u)$ and $\tilde \u$ is a row,
obtained by permutation of indices $i$ and $j$ from the row $\u$. The uniqueness of the solution $\rho$
implies that the distribution $\rho_1$ coincides with the distribution $\rho_2$. In particular,
$\rho_1(\bar \u_i) = \rho_2(\bar \u_i) = \rho_1(\bar \u_j)$.
From the second equation of~(\ref{FNecConditions}),
it follows that $\lambda_i = \lambda_j$.

Introduce parameters $\mu \eq \log_2 e + \lambda_{k+1}$ and $\nu \eq \lambda_0$.
The equations~(\ref{FRestrictions}) and~(\ref{FNecConditions}) can be represented as follows:
\begin{equation}
\label{FFinalSystem}
\begin{cases}
\text{1) } \log_2 \rho(\u) + \mu + \eta \sum_{i = 1}^k u_i = 0 \quad \forall \, \u \neq \0,\\
\text{2) } \log_2 \rho(\0) + \mu + \nu = 0,\\
\text{3) } \rho(\0) = 1 - q,\\
\text{4) } \sum_{\u} \rho(\u) = 1,\\
\text{5) } \sum_{\u: u_i = 1} \rho(\u) = Q \quad \forall \, i \in [k].
\end{cases}
\end{equation}

After replacement of $\eta$ by $y \eq \frac{1}{1+2^{-\eta}}$ the $1$st equation of~(\ref{FFinalSystem}) becomes
\begin{equation}
\label{FTauANotLast}
\rho(\u) = \frac{1}{2^\mu y^k} (1-y)^{\sum u_j} y^{k - \sum u_j} \quad \forall \, \u \neq \0.
\end{equation}
Substitution of~(\ref{FTauANotLast}) into $5$th equation of~(\ref{FFinalSystem}) gives
$$
\sum_{\u : u_i = 1} \frac{1}{2^\mu y^k} (1-y)^{\sum u_j} y^{k - \sum u_j} = \frac{1-y}{2^\mu y^k}.
$$
Therefore, one can derive
\begin{equation}
\label{FVarU}
\mu = \log_2 \frac{1 - y}{Qy^k}.
\end{equation}
Substitution of (\ref{FTauANotLast}), (\ref{FVarU}) and $3$rd equation of (\ref{FFinalSystem})
into 4th equation of (\ref{FFinalSystem}) leads to
$$
q(y) = \sum_{\u \neq 0} \rho(\u) = \frac{Q(1 - y^k)}{1 - y},
$$
i.e., the equation~(\ref{qSmall}). Thus, restrictions (\ref{FRestrictions})
and conditions (\ref{FNecConditions}) give a unique solution $\rho$ in the domain (\ref{FRegion}):
\begin{equation}
\label{FTauSolution}
\rho(\0) = 1 - q, \qquad \rho(\u) = \frac{Q}{1 - y} (1-y)^{\sum u_j} y^{k - \sum u_j} \quad \forall \, \u \neq \0,
\end{equation}
where parameters $q$ and $y$ are related by (\ref{qSmall}).
To obtain formula (\ref{exprA}) it is sufficient to substitute (\ref{FTauSolution}) into (\ref{FNeedToMin}).
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lemAProps}]
First, note that the function $q(y)$ defined by~(\ref{qSmall})
is increasing in the interval $y \in (0, 1)$,
and $q(0) =Q$ and $\lim q(y) = sQ$ as $y\to 1^-$.
Therefore, it suffices to prove that there is only one local minimum of the function
$\TT(k, Q, y) = \A(k, Q, q(y))$ of parameter $y$ on the interval $y \in (0, y_1)$,
where $q(y_1) = \min\{1, sQ\}$. The derivative of $\TT(k, Q, y)$ with respect to $y$ equals
\begin{equation*}
\label{dAbyY}
\frac{\partial \TT(k, Q, y)}{\partial y} = q'(y) \log_2\left[\frac{Qy^k}{1 - Q - y + Qy^k}\right].
\end{equation*}
Therefore, the function $\TT(k, Q, y)$ decreases in $y \in (0, 1 - Q)$,
increases in $y \in (1 - Q, y_1)$ and attains its minimum $0$ at the point $y_0 = 1 - Q$.
Note that $y < 1 - Q$ is equivalent to $q < 1 - (1 - Q)^k$ because
$q(y)$ is an increasing function.
The first statement is proved.
To prove the second statement it is sufficient to calculate the derivative of $\A(k, Q, y)$ with respect to $Q$:
\begin{equation*}
\label{dAbyQ}
\frac{\partial \A(k, Q, y)}{\partial Q} = k \log_2\left[\frac{(1 - y)(1 - Q)}{yQ}\right].
\end{equation*}
This derivative is positive if and only if $Q < 1 - y$ which is equivalent to $Q > 1 - (1 - q)^{1 / k}$.
So, the second statement holds.
\end{proof}

\bibliographystyle{ieeetran}
