3.1. Formulation

We consider $n+1$ binary random variables $X_1, \ldots, X_{n+1}$ that take values in $\{0,1\}$ and are subject to a joint distribution $P_{X_1, \ldots, X_{n+1}}$ . By randomly drawing n samples $Y_1, \ldots, Y_n$ without replacement from $X_1, \ldots, X_{n+1}$ , we would like to estimate the marginal distribution of the remaining binary variable $Y_{n+1}$ . To characterize this problem, we introduce the set $S_{n+1}$ of permutations on $[n+1]\,:\!=\,\{1, \ldots, n+1\}$ . The joint distribution $P_{Y_1, \ldots, Y_{n+1}}$ of $Y_1, \ldots, Y_{n+1}$ is given as

\begin{align*}P_{Y_1, \ldots, Y_{n+1}}(y_1, \ldots, y_{n+1})=\sum_{\sigma \in S_{n+1}}\frac{1}{(n+1) ! }P_{X_{\sigma(1)}, \ldots, X_{\sigma(n+1)}}(y_1, \ldots, y_{n+1}).\end{align*}

Denote the set of permutation invariant distributions on $[n+1]$ by ${\mathcal Q}_{n+1}$ , then the joint distribution $P_{Y_1, \ldots, Y_{n+1}}$ can be considered as an arbitrary element of ${\mathcal Q}_{n+1}$ .

Our problem setting is formulated as follows. Suppose n observed variables $Y_1, \ldots, Y_n$ are $y_1, \ldots, y_n$ , our task is to estimate the conditional distribution $P_{Y_{n+1}| (Y_1, \ldots, Y_n) =(y_1, \ldots, y_n)}$ . For each observed variable $Y_i$ , the observation outcome $Y_i=0$ is labeled as a ‘success’ and the outcome $Y_i=1$ is labeled as a ‘failure’. Since $P_{Y_1, \ldots, Y_{n+1}}$ is permutation invariant, the above conditional distribution $P_{Y_{n+1}| Y_1, \ldots, Y_n}$ depends only on the random variable K that describes the number of failures among the n observations $Y_1, \ldots, Y_n$ . Hence, we discuss only the conditional distribution $P_{Y_{n+1}|K}$ . Since $Y_{n+1}$ is a binary variable taking values in $\{0,1\}$ , it suffices to estimate the conditional probability $\textrm{P}(Y_{n+1}=1|K \le k)$ for each realization k.

Now, we discuss this problem in the framework of one-sided hypothesis testing with significance level $\delta$ . The problem setting is formulated as follows. We are interested in the probability of $Y_{n+1}=1$ under the condition that our test is passed. That is, we focus on the conditional distribution $\textrm{P}(Y_{n+1}=1| \operatorname{Pass} )$ , where ‘ $\operatorname{Pass}$ ’ means the case that our test is passed. The aim of our test is to guarantee that the conditional probability $\textrm{P}(Y_{n+1}=1| \operatorname{Pass} )$ is not greater than a threshold $\epsilon$ with significance level $\delta$ . Hence, when its upper bound $\epsilon$ is given, the null hypothesis $H_0$ and the alternative hypothesis $H_1$ are given as

\begin{align*}H_0\,:\, &\quad \textrm{P}(Y_{n+1}=1| \operatorname{Pass} ) > \epsilon, \\H_1\,:\, &\quad \textrm{P}(Y_{n+1}=1| \operatorname{Pass} ) \le \epsilon.\end{align*}

In this problem setting, it is needed to set the event ‘Pass’ as follows: when the test is passed, the null hypothesis $H_0$ is rejected. This is because we are required to guarantee the alternative hypothesis $H_1$ under the event ‘Pass’. Due to the above requirement and the correlation between $Y_{n+1}$ and $Y_1, \ldots, Y_n$ , the forms of our hypotheses depend on our decision.

In other words, the expectation $\textrm{E}[Y_{n+1}]$ does not equal $\textrm{P} (Y_{n+1} =1|\operatorname{Pass})$ . This point is the difficulty of our problem. Given a test T, the maximum of the conditional probability $\textrm{P}(Y_{n+1}=1| \operatorname{Pass} T)$ with significance level $\delta$ is given as

\begin{align*}\overline{\epsilon}(T,n,\delta)\,:\!=\,\max_{Q \in {\mathcal Q}_{n+1}}\{Q(Y_{n+1}=1| \operatorname{Pass} T)|Q(\operatorname{Pass} T) \ge \delta \}.\end{align*}

Since we can guarantee that the conditional probability $\textrm{P}(Y_{n+1}=1| \operatorname{Pass} T)$ is not greater than the maximum, the above maximum is simply called the upper confidence limit at significance level $\delta$ . In this case, we can say that $\delta$ is the p-value of the upper bound $\overline{\epsilon}(T,n,\delta)$ of the conditional probability $\textrm{P}(Y_{n+1}=1| \operatorname{Pass} T)$ .

The most natural choice for the rejection region of the null hypothesis $H_0$ is the set $\{K| K \leq k\}$ , i.e. the test is passed when $K \le k$ . This rejection region is determined by the threshold value k. We denote this deterministic test by $T_k$ . Under this choice of the rejection region, the upper confidence limit is given as

\begin{align*}\overline{\epsilon}(T_k,n,\delta)=\max_{Q \in {\mathcal Q}_{n+1}}\{Q(Y_{n+1}=1|K \le k)\,|\, Q(K \le k) \ge \delta \}.\end{align*}

That is, we can guarantee that the conditional probability $\textrm{P}(Y_{n+1}=1 |K \le k)$ is not greater than the upper confidence limit $\overline{\epsilon}(T_k,n,\delta)$ at significance level $\delta$ . Here the threshold k denotes the number of allowed failures.

As we show in Section 4.1, the upper confidence limit $\overline{\epsilon}(T_k,n,\delta)$ reads

(1) \begin{align}\overline{\epsilon}(T_k,n,\delta)=\left\{\begin{array}{l@{\quad}c}\dfrac{(k+1) (n+1-k) -\delta(n+1)}{\delta(n-k)(n+1)} &\hbox{ when } \delta \ge \dfrac{k+1}{n+1}, \\[6pt]1&\hbox{ when }\delta < \dfrac{k+1}{n+1} .\end{array}\right.\end{align}

Equation (1) shows that when the significance level $\delta$ is smaller than $1/(n+1)= \min_{k \ge 0} ((k+1)/(n+1))$ , we cannot make any non-trivial upper confidence limit for the conditional probability $\textrm{P}(Y_{n+1}=1|K \le k)$ for any integer $k=0,1,\ldots, n$ . Therefore, it is impossible to realize an exponentially small significance level with respect to n for any non-trivial upper confidence limit. In other words, when we set the significance level $\delta$ to be an exponentially small value with respect to n, the upper confidence limit becomes 1.

Fortunately, this problem can be resolved by introducing a randomized test. Our randomized test is not a trivial idea. To see the strength of our method, we first see a usual randomized test as follows. When we consider a randomized test, usually we make the randomization only on the threshold. Consider the following test. When $K \le k-1$ , we reject the null hypothesis $H_0$ . When $K \ge k+1$ , we adopt the null hypothesis $H_0$ . When $K = k$ , we reject the null hypothesis $H_0$ with probability $1-\lambda$ , and adopt $H_0$ with probability $\lambda$ . This test can be considered as a probabilistic mixture of the test $T_k$ and $T_{k-1}$ with probabilities $1-\lambda $ and $\lambda$ . We denote this test by $\tilde{T}_k(\lambda)$ . Since $\tilde{T}_k(0)=T_k$ , this method is a generalization of the above method. As we show in Section 4.2, the upper confidence limit $\overline{\epsilon}(\tilde{T}_k(\lambda),n,\delta)$ reads

(2) \begin{align}\overline{\epsilon}(\tilde{T}_k(\lambda),n,\delta)&=\left\{\begin{array}{l@{\quad}l}\xi_1(n,k,\lambda,\delta) &\hbox{ when }\delta\ge (1-\lambda) +\lambda \dfrac{k}{n+1}, \\[3pt]\xi_2(n,k,\lambda,\delta) &\hbox{ when }(1-\lambda) +\lambda \dfrac{k}{n+1} > \delta\ge (1-\lambda) \dfrac{k+1}{n+1}, \\[3pt]1&\hbox{ when }(1-\lambda) \dfrac{k+1}{n+1}> \delta ,\end{array}\right.\end{align}

where

\begin{align*}\xi_1(n,k,\lambda,\delta) &\,:\!=\, \frac{(k-1)\lambda(n+1-k)+(n+1)(1-\delta)}{\delta(n+1)\lambda(n+1-k)},\\[3pt]\xi_2(n,k,\lambda,\delta) &\,:\!=\, \frac{\delta(n+1) (k-(1-\lambda)(k+1))+(1-\lambda)^2 (k+1) (n+1-k)}{\delta(n+1)(k+(1-\lambda) (n-2k))}.\end{align*}

Consequently, with this type of randomized test, when we set the significance level $\delta$ to be an exponentially small value with respect to n, the upper confidence limit $\overline{\epsilon}(\tilde{T}_k(\lambda),n,\delta)$ becomes 1. To see this, we examine two cases depending the behavior of $\lambda$ . First, if $(1-\lambda) (k+1)/(n+1)> \delta$ then the above observation holds immediately. Second, if $(1-\lambda) +\lambda {k}/{(n+1)} > \delta\ge (1-\lambda) (k+1)/(n+1)$ then $(1-\lambda)$ is also an exponentially small value with respect to n, leading to that $\overline{\epsilon}(\tilde{T}_k(\lambda),n,\delta)=\xi_2(n,k,\lambda,\delta)$ converges to 1. This discussion shows that a more advanced randomization is needed for further improvement.

The above randomized test makes a randomized decision only when the observation is the threshold value. In contrast, our method makes this kind of randomized decision for all observations, and the probability of this randomization depends on our observation. To introduce our randomized test, which is different from the above randomized test, we consider the following artificial noise before our data processing. Instead of $Y_1, \ldots, Y_{n}$ , we focus on n variables $U_1, \ldots, U_{n}$ with the following conditional distribution $P_{U_i|Y_i}$ :

(3) \begin{align}P_{U_i|Y_i}(0|0)=1, \quad P_{U_i|Y_i}(1|0)=0 ,\quad P_{U_i|Y_i}(0|1)=\lambda, \quad P_{U_i|Y_i}(1|1)=1-\lambda ,\end{align}

where $0 \leq \lambda < 1$ is a randomization parameter. For convenience, we define $\nu\,:\!=\,1-\lambda$ . The outcome $U_i=0$ is labeled as a ‘success’ and the outcome $U_i=1$ is labeled as a ‘failure’. Denote the number of failures among $U_1, \ldots, U_{n}$ by the random variable L, which satisfies the following conditional distribution $P_{L|K}$ :

\begin{align*}P_{L|K}(l|k)=\left\{\begin{array}{l@{\quad}l}0 & {\rm when}\,\, l > k, \\\left(\begin{smallmatrix} k \\ l \end{smallmatrix}\right) \lambda^{k-l} (1-\lambda)^{l}& {\rm when}\,\, l \le k,\end{array}\right. \end{align*}

which implies that $L \le K$ . Then, we define the following test by using the random variable L instead of K. When $L \le l$ , we reject the null hypothesis $H_0$ . When $L \ge l+1$ , we adopt the null hypothesis $H_0$ . We denote this test by $T_l(\lambda)$ , in which the threshold l denotes the number of allowed failures.

Then, the upper confidence limit $\overline{\epsilon}(T_l(\lambda),n,\delta)$ is calculated as

\begin{align*}\overline{\epsilon}(T_l(\lambda),n,\delta)=\max_{Q \in {\mathcal Q}_{n+1}}\{Q(Y_{n+1}=1|L \le l)\,|\, Q(L \le l) \ge \delta \}.\end{align*}

When $K \le l$ , the relation $L\le K$ guarantees that the probability $\textrm{P}(Y_{n+1}=1)$ under the observed condition is not greater than the upper limit. Otherwise, we make a randomized decision. Note that $\overline{\epsilon}(T_l,n,\delta)$ is the special case of $\overline{\epsilon}(T_l(\lambda),n,\delta)$ with $\lambda=0$ . This method guarantees that the conditional probability $\textrm{P}(Y_{n+1}=1|L \le l)$ is not greater than $\overline{\epsilon}(T_l(\lambda),n,\delta)$ at significance level $\delta$ .

The one-sided hypothesis testing introduced above plays a crucial role in the task of verifying quantum states in the adversarial scenario (QSVadv) [Reference Zhu and Hayashi46, Reference Zhu and Hayashi47]. In QSVadv, one aims to ensure that the quantum state on one system has sufficiently high fidelity with the target state by performing n measurements on other systems. So far, only the verification protocol with $l=0$ has been studied in the literature. The performance with general $l>0$ is still not clear.

To see how our new method with $\lambda>0$ can achieve exponentially small significance level, we set $l=0$ . For $z\in\{0,1,\dots,n+1\}$ , let $\delta=\delta_z\,:\!=\,({(n+1-z)\lambda^z+ z \lambda^{z-1}})/({n+1})$ , then we have

(4) \begin{align}\overline{\epsilon}(T_0(\lambda),n,\delta_z)=\frac{z}{z+(n-z+1)\lambda}. \end{align}

Equation (4) follows from (57) in Ref. [Reference Zhu and Hayashi47], and a simple proof is also given in Section 4.3. Since $\delta_z$ has a similar behavior as $\lambda^z$ , this equation shows that the above randomized test can realize a non-trivial statement even with an exponentially small significance level. So randomized tests can significantly outperform deterministic tests.

By contrast, randomized tests are not necessary to achieve an exponentially small significance level for i.i.d. variables. To see this, we define the upper confidence limit for the i.i.d. case and a test T as

\begin{align*}\overline{\epsilon}_{\textrm{i.i.d.}}(T,n,\delta)\,:\!=\,\max_{Q \in {\mathcal Q}_{\operatorname{i.i.d.},n+1}}\{Q(Y_{n+1}=1| \operatorname{Pass} T) \,|\, Q(\operatorname{Pass} T) \ge \delta \},\end{align*}

where ${\mathcal Q}_{\textrm{i.i.d.},n+1} $ is the set of independent and identical distributions on $[n+1]$ . Then, for the deterministic test $T_k$ , we have

(5) \begin{align}\overline{\epsilon}_{\textrm{i.i.d.}}(T_k,n,\delta)=&\max_{Q \in {\mathcal Q}_{\operatorname{i.i.d.},n+1}}\{Q(Y_{n+1}=1|K \le k)\,|\, Q(K\le k) \ge \delta \} .\end{align}

We denote by $P_{\theta}^{n+1}$ the independent and identical distribution on $[n+1]$ where the probability of the event $Y_i=1$ is $\theta$ . Hence, ${\mathcal Q}_{\textrm{i.i.d.},n+1} $ can be written as $\{P_{\theta}^{n+1}\}_{\theta \in [0,1]}$ , which implies that

(6) \begin{align}\overline{\epsilon}_{\textrm{i.i.d.}}(T_k,n,\delta)=&\max_{\theta \in [0,1]} \{\theta \,|\, P_{\theta}^{n+1}(K\le k) \ge \delta \} .\end{align}

As we show in Sections 5 and 7, $\overline{\epsilon}_{\textrm{i.i.d.}}(T_k,n,\delta)$ has a non-trivial value even when the significance level $\delta$ is exponentially small with respect to n.

3.2. Frequently used notation

In preparation for further discussions, here we introduce further notation, which will be frequently used throughout the paper.

Let $\mathbb{Z}^{\geq j}$ be the set of integers larger than or equal to j. For $0 \leq p \leq 1$ and $z,l,j\in\mathbb{Z}^{\geq 0}$ , let

(7) \begin{align} b_{z,j}(p)\,:\!=\, \binom{z}{j} p^j (1-p)^{z-j},\qquad B_{z,l}(p)\,:\!=\, \sum_{j=0}^l b_{z,j}(p)= \sum_{j=0}^l \binom{z}{j} p^j (1-p)^{z-j}.\end{align}

Here it is understood that $b_{z,j}(p)=0$ whenever $j\geq z+1$ , and $x^0=1$ even if $x=0$ . When there is no danger of confusion, we shall use $b_{z,l}$ and $B_{z,l}$ as shorthand for $b_{z,l}(\nu)$ and $B_{z,l}(\nu)$ , respectively. Define

(8) \begin{align} \Delta_{z,l}\,:\!=\,B_{z,l}-B_{z+1,l},\quad z,l=0,1,2,\ldots.\end{align}

For $0 < \delta\leq 1$ , define

(9) \begin{align} z^*(l,\delta,\lambda)\,:\!=\,\min\{z\in\mathbb{Z}^{\geq l}|B_{z,l}\leq \delta\},\quad z_*(l,\delta,\lambda)\,:\!=\,z^*(l,\delta,\lambda)-1.\end{align}

Here $z^*(l,\delta,\lambda)$ and $z_*(l,\delta,\lambda)$ are well defined because $B_{l,l}(\nu)=1$ , $\lim_{z\to\infty} B_{z,l}(\nu)=0$ , and that $B_{z,l}(\nu)$ is non-increasing in z for $z\geq l$ according to Lemma 7. In this paper we shall frequently use $z^*$ and $z_*$ as shorthand for $z^*(l,\delta,\lambda)$ and $z_*(l,\delta,\lambda)$ , respectively.

The standard normal density function and its distribution function read

(10) \begin{align} \phi(x)\,:\!=\,\frac{1}{\sqrt{2\pi}}\mathrm{e}^{-x^2/2},\quad \Phi(x)\,:\!=\,\int_{-\infty}^x \phi(t) \,\textrm{d} t.\end{align}

The function $\Phi^{-1}(x)$ is defined as the inverse function of $\Phi(x)$ .

For $0< p,q<1$ , the relative entropy between two binary non-negative vectors $(p,1-p)$ and $(q,1-q)$ reads

(11) \begin{align} D(p\|q)\,:\!=\,p\ln\frac{p}{q}+(1-p)\ln\frac{1-p}{1-q}.\end{align}

For $\gamma\geq0$ and $0<x<1$ , define $t_\mathrm{D}(\gamma,x)$ as the unique solution of t to the equation

(12) \begin{align} t D\!\left( \frac{\gamma}{t}\Big\|x\right) =1, \quad t\geq \frac{\gamma}{x}.\end{align}

Note that $t_\mathrm{D}(\gamma,x)$ is well defined because $D(x\|x)=0$ , $D(0\|x)=-\ln(1-x)$ , and that $D( \gamma/t\|x)$ is non-decreasing in t for $t\geq \gamma/x$ thanks to Lemma 12 in Appendix A.2. For $0 \leq s < 1$ and $r>0$ , define $\epsilon_D(s,r)$ as the unique solution of $\epsilon$ to the equation

(13) \begin{align} r=D(s\|\epsilon ), \quad 0 \leq s \leq \epsilon < 1 .\end{align}

Similarly, for $0 < \epsilon<1$ and $0 < r \leq- \ln(1-\epsilon)$ , define $s_D(\epsilon,r)$ as the unique solution of s to (13). Both $\epsilon_D(s,r)$ and $s_D(\epsilon,r)$ are well defined according to Lemma 12 in Appendix A.2.

For $x\geq 0$ and $k\in\mathbb{Z}^{\geq 0}$ , the Poisson cumulative distribution function reads

(14) \begin{align} \mathrm{Pois}(k,x)\,:\!=\,\mathrm{e}^{-x} \sum_{j=0}^k \frac{x^j}{j!}.\end{align}

For $0 < \delta < 1$ and $k\in\mathbb{Z}^{\geq 0}$ , define $t_\mathrm{P}(k,\delta)$ as the unique solution of t to the equation

(15) \begin{align}\mathrm{Pois}(k,t) = \delta \quad \hbox{for } \ t\geq 0.\end{align}

Note that $t_\mathrm{P}(k,\delta)$ is well defined because $\mathrm{Pois}(k,0)=1$ , $\lim_{t\to\infty}\mathrm{Pois}(k,t)=0$ , and that $\mathrm{Pois}(k,t)$ is monotonically decreasing in t for $t\geq0$ according to Lemma 13 in Appendix A.3.

3.3. Properties of the upper confidence limit

Here we summarize some basic properties of the upper confidence limit. In particular, Proposition 1 clarifies the monotonicities of $\overline{\epsilon}_{\operatorname{i.i.d.}}(T_k,n,\delta)$ , and Lemma 1 provides useful bounds for $\overline{\epsilon}(T_k,n,\delta)$ , $\overline{\epsilon}(T_l(\lambda),n,\delta)$ , and $\overline{\epsilon}_{\textrm{i.i.d.}}(T_k,n,\delta)$ . The monotonicities of $\overline{\epsilon}(T_l(\lambda),n,\delta)$ will be clarified later in Proposition 6 after several preparations. Proposition 1 and Lemma 1 are proved in Appendices C and D, respectively.

Lemma 1. Suppose $0 < \delta \leq \tfrac12$ , $k,l,n\in \mathbb{Z}^{\geq 0}$ , $n>k$ , $n>l$ . In the i.i.d. case, we have

(16) \begin{align}\overline{\epsilon}_{\textrm{i.i.d.}}(T_k,n,\delta) \ge\overline{\epsilon}_{\textrm{i.i.d.}}\left(T_k,n,\frac12\right) > \frac{k}{n}.\end{align}

As a generalization, for $0 \leq \lambda < 1$ we have

(17) \begin{align}\overline{\epsilon}(T_l(\lambda),n,\delta)\ge\overline{\epsilon}\left(T_l(\lambda),n,\frac12\right)\left\{\begin{array}{l@{\quad}l} =1 &\quad when \,\, l\geq \nu n ,\\ > \frac{l}{\nu n}&\quad when\,\, l<\nu n.\end{array}\right.\end{align}

For $\lambda=0$ and $k/n<\delta\leq \tfrac12$ , we have

(18) \begin{align}\overline{\epsilon}(T_k,n,\delta) > \frac{k}{n\delta}.\end{align}

4.1. Proof of (1)

Let $Q_{j}$ be the permutation invariant distribution of variables $Y_1, Y_2,\ldots, Y_{n+1}\in\{0,1\}$ that satisfy $\sum_{i=1}^{n+1}Y_i=j$ . Then any element of $ {\mathcal Q}_{n+1}$ can be written in the form $Q[\vec{p}]\,:\!=\,\sum_{j=0}^{n+1}p_j Q_j$ , where $\vec{p}\,:\!=\,(p_j)_{j=0}^{n+1}$ . In addition, we have

\begin{align*}Q_j(K=k)=\left\{\begin{array}{l@{\quad}l}\dfrac{n+1-j}{n+1}& \hbox{ when } k=j, \\[6pt]\dfrac{j}{n+1} & \hbox{ when } k=j-1, \\[6pt]0 & \hbox{ otherwise} .\end{array}\right.\end{align*}

It follows that

(19) \begin{align}Q[\vec{p}](K \le k)&=\sum_{j=0}^k p_j + \frac{k+1}{n+1}p_{k+1}\end{align}

(20) \begin{align} Q[\vec{p}](Y_{n+1}=1,K \le k)&=\sum_{j=0}^k \frac{j}{n+1}p_j+ \frac{k+1}{n+1}p_{k+1},\end{align}

and

(21) \begin{align}\overline{\epsilon}(T_k,n,\delta)=&\max_{(p_j)_{j=0}^{n+1}}\bigg\{\dfrac{Q[\vec{p}](Y_{n+1}=1,K \le k)}{Q[\vec{p}](K \le k)}\,\bigg|\,Q[\vec{p}](K \le k)\ge \delta\bigg\}\nonumber\\[6pt]\stackrel{(a)}{=}&\max_{0 \le p_k \le 1 }\bigg\{\frac{p_k\dfrac{k}{n+1} +\dfrac{k+1}{n+1}(1- p_{k})}{p_k + \dfrac{k+1}{n+1}(1-p_{k})}\,\bigg|\, p_k + \dfrac{k+1}{n+1}(1-p_{k}) \ge \delta\bigg\}\nonumber\\[6pt]=&\max_{0 \le p_k \le 1 }\bigg\{\dfrac{ k+1 -p_k}{(k+1)+ p_k(n-k)}\,\bigg|\, \dfrac{(k+1)+ p_k(n-k)}{n+1}\ge \delta\bigg\}.\end{align}

To derive (a) above, we use (19), (20), and choose $p_1, \ldots, p_{k-1}$ to be zero. When $(k+1)/(n+1)> \delta$ , the maximum in (21) is realized with $p_k=0$ , i.e. the maximum is 1. When $(k+1)/(n+1)\le \delta$ , the maximum is realized with $p_k=((n+1)\delta-(k+1))/(n-k)$ , i.e. the maximum is $((k+1)(n-k+1)-\delta(n+1))/[\delta(n+1)(n-k)]$ . Then, we have (1).

4.2. Proof of (2)

The test $\tilde{T}_k(\lambda)$ satisfies that

\begin{align*}Q[\vec{p}](\operatorname{Pass} \tilde{T}_j(\lambda))&=(1-\lambda) \left( \sum_{j=0}^k p_j + \frac{k+1}{n+1}p_{k+1} \right)+\lambda\left( \sum_{j=0}^{k-1} p_j + \frac{k}{n+1}p_{k} \right) \nonumber\\&= \sum_{j=0}^{k-1} p_j+\left( 1-\lambda + \frac{k}{n+1}\lambda\right) p_k+ \frac{k+1}{n+1} (1-\lambda) p_{k+1}=\sum_{j=0}^{k+1} a_j p_j ,\\Q[\vec{p}](Y_{n+1}=1,\operatorname{Pass} \tilde{T}_j(\lambda))&=(1-\lambda) \sum_{j=0}^{k+1} \frac{j}{n+1}p_j+\lambda \sum_{j=0}^k \frac{j}{n+1} p_j \nonumber\\&=\sum_{j=0}^k \frac{j}{n+1}p_j+ \frac{k+1}{n+1}(1-\lambda)p_{k+1}=\sum_{j=0}^{k+1} b_j p_j ,\end{align*}

where we choose the parameters $a_{j}$ and $b_{j}$ as follows:

\begin{align*}&a_{k+1}\,:\!=\,(1-\lambda) \frac{k+1}{n+1} , \quad a_{k}\,:\!=\,(1-\lambda) +\lambda \frac{k}{n+1}, \quad a_{j}\,:\!=\,1 \quad \hbox{for } j=0, \ldots, k-1, \\&b_{k+1}\,:\!=\,(1-\lambda) \frac{k+1}{n+1} , \quad b_{j}\,:\!=\,\frac{j}{n+1} \quad \hbox{for } j=0, \ldots, k .\end{align*}

Then, we have

(22) \begin{align}\frac{b_{k-1}-b_{k}}{a_{k-1}-a_{k}}=-\frac{1}{\lambda(n+1-k)}\le\frac{(k+1)\lambda-1}{(n-k)+\lambda(2k-n)}=\frac{b_{k}-b_{k+1}}{a_{k}-a_{k+1}}.\end{align}

Hence, the positional relation among the points $(a_0,b_0),(a_1,b_1),\ldots,(a_{k+1},b_{k+1})$ are illustrated as Figure 1. The upper confidence limit $\overline{\epsilon}(\tilde{T}_k(\lambda),n,\delta)$ can be written as

(23) \begin{align}\overline{\epsilon}(\tilde{T}_k(\lambda),n,\delta)=&\max_{(p_j)_{j=0}^{n+1}}\left\{\frac{Q[\vec{p}](Y_{n+1}=1,\operatorname{Pass} \tilde{T}_j(\lambda))}{Q[\vec{p}](\operatorname{Pass} \tilde{T}_j(\lambda))}\,\bigg| \,Q[\vec{p}](\operatorname{Pass} \tilde{T}_j(\lambda))\ge \delta\right\}\nonumber\\=&\max_{(p_j)_{j=0}^{n+1} \in {\mathcal P}_{k,n}}\left\{\frac{Q[\vec{p}](Y_{n+1}=1,\operatorname{Pass} \tilde{T}_j(\lambda))}{Q[\vec{p}](\operatorname{Pass} \tilde{T}_j(\lambda))}\,\bigg|\,Q[\vec{p}](\operatorname{Pass} \tilde{T}_j(\lambda))\ge \delta\right\},\end{align}

where ${\mathcal P}_{k,n}$ is the set of distributions on $\{0,1, \ldots, n,n+1\}$ such that $p_0=p_1=\cdots =p_{k-2}=p_{k+2}=\cdots =p_n=p_{n+1}=0$ .

Figure 1.

Positional relation among the points $(a_0,b_0),(a_1,b_1),\ldots, (a_{k},b_{k}),(a_{k+1},b_{k+1})$ . Due to (22), the point $(a_{k},b_{k})$ is located above the line segment between the points $(a_{k-1},b_{k-1})$ and $(a_{k+1},b_{k+1})$ . This positional relation shows that the maximum in (23) is achieved by a probabilistic mixture among the three points $(a_{k-1},b_{k-1}),(a_{k},b_{k}),(a_{k+1},b_{k+1})$ .

Figure 1 Long description

A scatter plot displays the positional relationship among the points (a0, b0), (a1, b1), ..., (ak, bk), (ak+1, bk+1). The point (ak, bk) is located above the line segment connecting the points (ak-1, bk-1) and (ak+1, bk+1). This positional relationship indicates that the maximum in the given equation is achieved by a probabilistic mixture among the three points (ak-1, bk-1), (ak, bk), and (ak+1, bk+1). The x-axis represents the variable 'a' and the y-axis represents the variable 'b'. The plot includes several labeled data points and a line segment connecting two of them. All values are approximated.

When $a_{k+1} > \delta$ , the maximum in (23) is realized with $p_{k-1}=p_k=0$ and $p_{k+1}=1$ , and the maximum is 1. When $a_{k} > \delta\ge a_{k+1} $ , the maximum is realized with $p_{k-1}=0,p_k=(\delta(n+1)-(1-\lambda)(k+1))/(k+(1-\lambda)(n-2k))$ and $p_{k+1}=1-(\delta(n+1)-(1-\lambda)(k+1))/((k+(1-\lambda)(n-2k))$ , and the maximum is $(\delta(n+1) (k-(1-\lambda)(k+1))+(1-\lambda)^2 (k+1) (n+1-k))/(\delta(n+1)(k+(1-\lambda) (n-2k)))$ . When $1=a_{k-1} \ge \delta\ge a_{k} $ , the maximum is realized with $p_{k-1}=1-(1-\delta)(n+1-k)/(\lambda(n+1)),p_k=(1-\delta)(n+1-k)/[\lambda(n+1)]$ , and $p_{k+1}=0$ , i.e. the maximum is $((k-1)\lambda(n+1-k)+(n+1)(1-\delta))/[\delta(n+1)\lambda(n+1-k)]$ . Thus, we obtain (2).

4.3. Proof of (4)

In preparation for proving (4), we define the new quantity $\overline{\epsilon}^\textrm{c}(T_0(\lambda),n,\delta)\,:\!=\, 1-\overline{\epsilon}(T_0(\lambda),n,\delta)$ . In the following, we shall show (4) by proving that

(24) \begin{align} \overline{\epsilon}^\textrm{c}(T_0(\lambda),n,\delta_z) =\frac{(n-z+1)\lambda}{z+(n-z+1)\lambda} \quad \mbox{for all }z\in\{0,1,\dots,n+1\}. \end{align}

Let $Q_{z}\in {\mathcal Q}_{n+1}$ be the permutation invariant distribution of variables $Y_1, \ldots, Y_{n+1}\in\{0,1\}$ that satisfy $\sum_{i=1}^{n+1}Y_i=z$ . Then by a simple calculation we have

\begin{align*} Q_z(L=0)&= \left\{ \begin{array}{l@{\quad}l} \lambda^{n} & \hbox{ when } z =n+1, \\[4pt] \frac{(n+1-z)\lambda^z+ z \lambda^{z-1}}{n+1} =\delta_z & \hbox{ when } 1\le z \le n, \\[4pt] 1 & \hbox{ when } z =0, \end{array} \right.\\[4pt] Q_z(L=0,Y_{n+1}=0)&= \left\{ \begin{array}{ll} 0 & \hbox{ when } z =n+1, \\[4pt] \frac{(n+1-z)\lambda^z}{n+1} & \hbox{ when } 1\le z \le n, \\[4pt] 1 & \hbox{ when } z =0, \end{array} \right.\end{align*}

and, thus,

(25) \begin{align}\dfrac{Q_z(L=0,Y_{n+1}=0)}{Q_z(L=0)}&=\left\{\begin{array}{l@{\quad}l} 0 & z =n+1 \\[5pt] \dfrac{(n+1-z)\lambda}{(n+1-z)\lambda+ z }\quad & 1\le z \le n \\[7pt] 1 & z =0\end{array} \right\}=\dfrac{(n-z+1)\lambda}{z+(n-z+1)\lambda} .\end{align}

In addition, we have

\begin{equation*} \overline{\epsilon}(T_0(\lambda),n,\delta) = \min_{ \{p_j\}_{j=0}^{n+1}} \left\{ \frac{\sum_{j=0}^{n+1} p_j Q_j(L=0,Y_{n+1}=0) }{\sum_{j=0}^{n+1} p_j Q_j(L=0)} \,\Bigg|\, \sum_{j=0}^{n+1} p_j Q_j(L=0) \ge \delta \right\},\end{equation*}

where $p_j$ form a probability distribution on $[n+1]$ .

Note that $Q_z(L=0)$ , $Q_z(L=0,Y_{n+1}=0)$ , and $Q_z(L=0,Y_{n+1}=0)/Q_z(L=0)$ all strictly decrease with z for $z\in\{0,1,\ldots,n+1\}$ . Therefore, when $\delta=\delta_z$ , the above minimum is realized with

\begin{align*} p_j= \left\{ \begin{array}{ll} 1 & \hbox{ when } j=z, \\ 0 & \hbox{ otherwise. } \end{array} \right.\end{align*}

This fact together with (25) confirms (24) and completes the proof of (4).

5.1. Preparations

To discuss the linear regime, we prepare the function $\psi(\delta)$ as

\begin{align*}\psi(\delta)\,:\!=\, \frac{\phi(\Phi^{-1}(\delta)) }{\delta \Phi^{-1}(\delta)},\end{align*}

which takes a central role in our analysis on $\overline{\epsilon}(T_{\lceil s \nu n\rceil}(\lambda),n,\delta)$ . This quantity can be approximated as

\begin{align*}\psi(\delta)\cong -B\!\left( 1-\mathrm{e}^{c \Phi^{-1}(\delta)}\right) ^{-1},\end{align*}

where $B=1.135$ and $c={1.98}/{\sqrt{2}}$ [Reference Karagiannidis and Lioumpas26, Reference Tanash and Riihonen44].

When $x\ge 0$ , the function $\eta(x)\,:\!=\,{x \Phi(x)}/{\phi(x)}$ satisfies the condition ${{\textrm{d}} \eta(x)}/{{\textrm{d}} x}> 0$ . Hence, $\psi(\delta)$ is strictly decreasing in $\delta > \tfrac12$ . Since $ \lim_{\delta\to (\tfrac{1}{2})^+}\psi(\delta)=+\infty$ and $ \lim_{\delta\to 1^-}\psi(\delta)=0^+$ , we can define $\psi^{-1}$ on $\mathbb{R}^+$ with the range $(\tfrac{1}{2},1) $ . Then, we define the function

(26) \begin{align}C(\lambda,s,\delta)\,:\!=\,&\, \frac{\sqrt{(1-\lambda)s}(1-s)}{\sqrt{\lambda}}\Phi^{-1}(\delta)\bigg[\psi(\delta)-\frac{\lambda}{(1-\lambda)(1-s)} \bigg] \nonumber\\=&\,\sqrt{s}(1-s)\Phi^{-1}(\delta)\bigg[\sqrt{\frac{1-\lambda}{\lambda}}\psi(\delta)-\sqrt{\frac{\lambda}{1-\lambda}} \frac{1}{1-s}\bigg] ,\end{align}

where $\Phi(x)$ and $\phi(x)$ are defined in (10). When $s \le 1$ , the value $C(\lambda,s,\delta)$ is non-negative for $ \delta \le\psi^{-1}\left({\lambda}/[{(1-\lambda)(1-s)}]\right)$ . Its minimization over $\lambda$ is given as

(27) \begin{align}\underline{C}(s,\delta)\,:\!=\,\inf_{\lambda \in (0, 1)}C(\lambda,s,\delta)=\left\{\begin{array}{l@{\quad}l}2\sqrt{\frac{-s (1-s)\Phi^{-1}(\delta)\phi(\Phi^{-1}(\delta))}{\delta}}&\hbox{ when } \delta \le \frac{1}{2}, \\[6pt]-\infty &\hbox{ otherwise. }\end{array}\right.\end{align}

When $\delta \le \tfrac{1}{2}$ , due to the relation of the arithmetic–geometric means, the above minimum value is attained when $\sqrt{({1-\lambda})/{\lambda}}\psi(\delta)=-\sqrt{{\lambda}/({1-\lambda})} ({1}/({1-s})) $ , i.e. $\lambda={(1-s)\psi(\delta)}/({(1-s)\psi(\delta)-1 })$ because the minimum is calculated as

\begin{align*}& \min_{\lambda \in (0, 1)}\sqrt{s}(1-s)\Phi^{-1}(\delta)\bigg[\sqrt{\frac{1-\lambda}{\lambda}}\psi(\delta)-\sqrt{\frac{\lambda}{1-\lambda}} \frac{1}{1-s}\bigg] \\&= -2\sqrt{s}(1-s)\Phi^{-1}(\delta)\sqrt{\bigg[-\sqrt{\frac{1-\lambda}{\lambda}}\psi(\delta)\cdot\sqrt{\frac{\lambda}{1-\lambda}} \frac{1}{1-s}\bigg]} \\&=-2\sqrt{s(1-s)}\Phi^{-1}(\delta)\sqrt{-\psi(\delta)}=2\sqrt{\frac{-s(1-s) \Phi^{-1}(\delta)\phi(\Phi^{-1}(\delta))}{\delta}}.\end{align*}

When $\delta >\frac{1}{2}$ , the minimum is realized when $\lambda \to 1$ .

5.2. Upper confidence limit

In the linear regime, according to (17) of Lemma1, when $0 < \delta\leq \tfrac12$ and $0 \leq s < 1$ , we have the following relation:

\begin{equation*} \overline{\epsilon}(T_{\lceil s\nu n\rceil}(\lambda),n,\delta) > s.\end{equation*}

Hence, our interest is the difference between $\overline{\epsilon}(T_{\lceil s\nu n\rceil}(\lambda),n,\delta)$ and s.

The comparison between (30) and (28) leads to an advantage of our randomized test. Equation (30) shows that the upper confidence limit attains s for $\delta >0$ and $\lambda> 0$ while (28) shows that it is impossible for $\delta >0$ and $\lambda= 0$ . That is, to achieve the upper confidence limit s, we need to choose non-zero $\lambda$ .

Equations (29) and (31) are shown by the substitution of sn into k at (1) with the asymptotic expansion for n. The derivation of (28) is slightly complicated. Let $ s_n= \lceil s n\rceil/n$ ; then $0 \le s_n - s=\upsilon_n/n \le 1/n$ . The substitution of sn into k at (1) with the asymptotic expansion for n implies that

(33) \begin{align}&\overline{\epsilon}(T_{\lceil s n\rceil}(0),n,\delta)=\frac{s_n}{\delta}+\frac{1-s_n+s_n^2-\delta}{\delta(1-s_n)}\frac{1}{n}+O\left(\frac{1}{n^2}\right), \end{align}

Substituting $s_n=s +\upsilon_n/n $ in (33), we obtain (28). Equations (30) and (32) are shown in Section 9 after several preparations.

Equation (30) shows that the term $C(\lambda,s,\delta)n^{-1/2}$ is an extra value to guarantee the significance level $\delta$ . Hence, a smaller coefficient $C(\lambda,s,\delta)$ is better. That is, the minimizer

\begin{align*}\lambda_{s,\delta}\,:\!=\, \mathop{\textrm{argmin}}_{\lambda}C(\lambda,s,\delta)=\frac{(1-s)\psi(\delta)}{(1-s)\psi(\delta)-1 }\end{align*}

gives the asymptotically minimum upper confidence limit when s and $\delta\in(0, \tfrac12)$ are fixed. To see this characterization, we consider the minimum upper confidence limit:

\begin{align*}\overline{\epsilon}_{\min}(s ,n,\delta)\,:\!=\,\min_{\lambda \in [0,1)}\overline{\epsilon}(T_{\lceil s\nu n\rceil}(\lambda),n,\delta).\end{align*}

Lemma 1 implies that

(34) \begin{align}\overline{\epsilon}_{\min}(s ,n,\delta)\ge \frac{\lceil \nu s n\rceil}{\nu n}\ge s \quad \mbox{for all } 0< \delta \le \frac{1}{2}.\end{align}

Equation (30) yields the following corollary for the minimum upper confidence limit.

Corollary 1. We fix $0 \leq s < 1$ , $0 < \delta< \tfrac12$ , and $0 < \lambda < 1$ . When n goes to infinity, we have

(35) \begin{align}\overline{\epsilon}_{\min}(s ,n,\delta)=s +\underline{C}(s,\delta)\sqrt{\frac{1}{n}}+O\left(\frac{1}{n}\right).\end{align}

Due to (31), when the significance level $\delta$ is exponentially small and $\lambda=0$ , the upper confidence limit takes the trivial value 1. That is, to achieve an exponentially small significance level $\delta$ , we need to choose non-zero $\lambda$ , which is an advantage of our randomized test. Indeed, when the significance level $\delta$ is exponentially small value $\mathrm{e}^{-nr}$ and $\lambda>0$ , (32) shows the upper confidence limit. Hence, when s and r are fixed, the asymptotically minimum upper confidence limit equals the minimum $\min_{\lambda}\min\{1,E_{\lambda, s}(r)\}$ , because the condition $E_{\lambda, s}(r)\geq 1$ is equivalent to the condition $r \geq D(s\nu\|\nu)$ . Since we have $D(s\nu\|\nu)\to\infty$ when $\lambda\to 0^+$ , this value is a non-trivial value.

In fact, when r approaches $0^+$ , $r t_\mathrm{D}({\nu s}.{r},\nu)$ approaches $s^+$ , and $E_{\lambda, s}(r)$ approaches $s^+$ . In addition, when r approaches $+\infty$ , we have $E_{\lambda, s}(r)\geq 1$ . This fact shows that the quantity $\overline{\epsilon}(T_{\lceil \nu s n\rceil}(\lambda),n,\delta=\mathrm{e}^{-r n})$ takes values in (s,1].

In contrast, we have the following proposition under the i.i.d. case. Under this case with the linear regime, we set k to be $\lceil s n\rceil$ with $0 \leq s < 1$ . According to Lemma 1, when $0 < \delta \leq \tfrac12$ we have

(36) \begin{align}\overline{\epsilon}_{\textrm{i.i.d.}}(T_{\lceil s n\rceil},n,\delta)>s.\end{align}

Cases (a) and (b) immediately follow from the central limit theorem and large deviation principle, respectively. For the reader’s convenience, Appendix E gives their proofs. A numerical comparison among (30), (35), and (37) is presented in Figure 2(b).

Figure 2.

(a) Variations of upper confidence limits in the constant regime. Here $k_0=100$ and $\delta=0.1$ . The symbols ‘ $\times$ ’ represent $\overline{\epsilon}_{\textrm{i.i.d.}}(T_{k_0},n,\delta)$ , ‘ $*$ ’ represent $\overline{\epsilon}(T_{k_0}(0),n,\delta)$ , whereas other symbols represent $\overline{\epsilon}(T_{\lceil\nu k_0\rceil}(\lambda) ,n,\delta)$ . The five curves from left to right represent the approximate formula in (66), (63), (63), (63), and (62), respectively (the terms $O(n^{-1})$ are ignored). (b) Variations of upper confidence limits in the linear regime. Here $s=0.1$ and $\delta=0.1$ . The symbols ‘ $\times$ ’ represent $\overline{\epsilon}_{\textrm{i.i.d.}}(T_{\lceil s n\rceil},n,\delta)$ , and other symbols represent $\overline{\epsilon}(T_{\lceil s\nu n\rceil}(\lambda),n,\delta)$ . The four curves from left to right represent the approximate formula in (37), (35), (30), and (30), respectively (the terms $O(n^{-1})$ are ignored); $\overline{\epsilon}(T_{\lceil s n\rceil}(0),n,\delta)$ is not shown because its value is too large.

Figure 2 Long description

Two line graphs compare variations of upper confidence limits in constant and linear regimes. The left graph shows five curves representing different formulas for the constant regime with symbols indicating specific data points. The right graph displays four curves for the linear regime with symbols marking certain data points. Each graph plots the variable epsilon against the variable n, illustrating how confidence limits change across different conditions and formulas.

5.3. Minimum number of required observations n

Next, under the linear regime, we consider the minimum number of observations n required to guarantee the upper confidence limit $\epsilon$ at significance level $\delta$ . To this end, for $0 \leq \lambda < 1$ , $0 < \epsilon,\delta < 1$ , and $0 \leq s < 1$ , we define the following values,

(39) \begin{align}N_{\lambda,\textrm{l}}(s,\epsilon, \delta)\,:\!=\,&\min \{n \ge \lceil \nu s n\rceil+1 \,|\,\overline{\epsilon}(T_{\lceil s\nu n\rceil}(\lambda),n,\delta) \le \epsilon \} ,\\\nonumber\underline{N}_{\textrm{l}}(s,\epsilon, \delta)\,:\!=\,&\min_{\lambda \in [0,1)} N_{\lambda,\textrm{l}}(s,\epsilon, \delta),\\N_{\textrm{i.i.d.},\textrm{l}}(s,\epsilon, \delta)\,:\!=\,&\min \{n \ge \lceil s n\rceil+1 \,|\,\overline{\epsilon}_{\textrm{i.i.d.}}(T_{\lceil s n\rceil},n,\delta) \le \epsilon \} .\end{align}

In the above notation, the subscript l expresses the linear regime. To make a fair comparison of the required number n, we need to choose the number of allowed failures l or k depending on $\lambda$ and s in the above way.

For the asymptotic evaluation of the above values, we have the following corollary.

Proof. The condition $0 < \delta \leq \tfrac12$ guarantees $ C(\lambda,s,\delta)\geq 0$ and $\overline{\epsilon}(T_{\lceil s\nu n\rceil}(\lambda),n,\delta)>s$ . The definition in (39) guarantees that $N_{\lambda,\textrm{l}}(s,\epsilon, \delta)$ is non-increasing in $\epsilon$ . Due to (30) and $ C(\lambda,s,\delta)\geq0$ , the equation $\epsilon= \overline{\epsilon}(T_{\lceil s\nu n\rceil}(\lambda),n,\delta)$ guarantees $C(\lambda,s,\delta)\sqrt{\frac{1}{n}}=\epsilon -s +O(n^{-1})$ , which implies that $n={C(\lambda,s,\delta)^2}/{(\epsilon-s)^2} +O\big((\epsilon -s)^{-1}\big)$ . Hence, there exists an integer $n_0 > 0$ and some constant $C_0>0$ such that

\begin{align*}\left|n-\frac{C(\lambda,s,\delta)^2}{(\epsilon -s)^2}\right|\le\frac{ C_0}{\epsilon -s}\quad \mbox{for all } n \ge n_0.\end{align*}

On the other hand, due to Lemma 1, there exits an $s<\epsilon_0<1 $ such that

\begin{align*}\overline{\epsilon}(T_{\lceil s\nu n\rceil}(\lambda),n,\delta) \ge \epsilon_0 \quad \mbox{for all }n \le n_0.\end{align*}

Therefore, for $\epsilon \in (s,\epsilon_0)$ , we have

\begin{align*}N_{\lambda,\textrm{l}}(s,\epsilon, \delta)=\frac{C(\lambda,s,\delta)^2}{(\epsilon -s)^2} + O\left( \frac{1}{\epsilon - s}\right) .\end{align*}

Hence, we obtain (40). In the same way, we can show (41) from (34) and (35), and show (42) from (36) and (37). In addition, (43) follows from (18) and (28) of Lemma 1 in the same way because of $1-s+s^2\ge \tfrac12$ . By solving the equation $E_{\lambda, s}(r)=\epsilon$ for r, we obtain (44) from (32). Similarly, by solving $\epsilon_D(s,r)=\epsilon$ for r, we obtain (45) from (38).

5.4. Maximum number of allowed failures l

In addition, we may consider the following quantities:

(46) \begin{equation}\begin{aligned}l_{\lambda}(n,\epsilon, \delta)&\,:\!=\,\max \{l \ge 0 \,|\, \overline{\epsilon}(T_l(\lambda),n,\delta) \le \epsilon \}, \\l_{\textrm{i.i.d.}}(n,\epsilon, \delta)&\,:\!=\,\max \{l \ge 0 \,|\, \overline{\epsilon}_{\textrm{i.i.d.}}(T_l,n,\delta) \le \epsilon \},\end{aligned}\end{equation}

which denote the maximum numbers of failures l allowed to guarantee the upper confidence limit $\epsilon$ at significance level $\delta$ .

Proof. First, we prove (47). The condition $\overline{\epsilon}(T_l,n,\delta) \le \epsilon$ is equivalent to the conditions

(52) \begin{align}l^2 -[ (1+\epsilon\delta) n + \epsilon\delta]l-(n+1) (1-\delta -\epsilon \delta n )\ge 0\end{align}

and $l \le \delta (n+1)-1$ . The condition in (52) is equivalent to

(53) \begin{align}l \le \delta \epsilon n -\frac{1-\delta-\delta\epsilon+\delta^2\epsilon^2}{1-\delta\epsilon}+O\left(\frac{1}{n}\right) \quad \text{or} \quad l \ge n +\frac{1-\delta}{1-\delta\epsilon}+O\left(\frac{1}{n}\right) .\end{align}

However, the second case in (53) is not allowed due to the condition $l \le \delta (n+1)-1$ . Hence, we have only the first case in (53). Since $l_{0}(n,\epsilon, \delta)$ is the maximum integer that satisfies the first inequality in (53), we have (47).

Next, we prove (48). When l is proportional to n, (30) implies that

(54) \begin{align}&\overline{\epsilon}(T_l(\lambda),n,\delta)=\frac{l}{\nu n} +C\left( \lambda,\frac{l}{\nu n},\delta\right) \sqrt{\frac{1}{n}}+O\left(\frac{1}{n}\right).\end{align}

To determine $l_{\lambda}(n,\epsilon, \delta)$ , we set the right-hand side of (54) to be $\epsilon$ , that is,

(55) \begin{align}\frac{l}{\nu n} +C\left( \lambda,\frac{l}{\nu n},\delta\right) \sqrt{\frac{1}{n}}+O\left(\frac{1}{n}\right)=\epsilon. \end{align}

This implies that $l= \nu n\epsilon+x$ , where $x=o(n)$ is some small quantity. By plugging $l= \nu n\epsilon+x$ into (55), we get

\begin{align*}\frac{x}{\nu} +C(\lambda,\epsilon+o(1),\delta)\sqrt{n}+O(1)=0.\end{align*}

Hence, we have $x=-C(\lambda,\epsilon,\delta)\nu\sqrt{n}+o(\sqrt{n})$ and $l= \nu n\epsilon-C(\lambda,\epsilon,\delta)\nu\sqrt{n}+y$ , where $y=o(\sqrt{n})$ . By plugging this relation into (55) again, we can deduce that $y=O(1)$ . This confirms (48). Equation (49) can be derived in a similar way.

Finally, we prove (50). Solving the equation $\bar{E}_{\lambda, r}(s)=E_{\lambda, s}(r)=\epsilon$ for s, we obtain ${l}/[{(1-\lambda)n}]=\bar{E}_{\lambda, r}^{-1}(\epsilon)$ from (32). Note that $E_{\lambda,s}(r)$ is increasing in s and this equation has a solution for $s\geq0$ when the constraint $E_{\lambda,0}(r)\leq\epsilon$ , i.e. $r \leq {-\lambda\epsilon\ln\lambda}/({1-\nu\epsilon})$ holds. Hence, we obtain (50) under the condition $r \leq {-\lambda\epsilon\ln\lambda}/({1-\nu\epsilon})$ . In the same way, we obtain (51) from (38).

7.1. Upper confidence limit

For the asymptotic evaluation of $\overline{\epsilon}(T_{l}(\lambda),n,\delta)$ , we define the coefficient

\begin{align*}G(l,\delta,\lambda)\,:\!=\,\frac{(B_{z_*,l}-\delta)z^*B_{z_*,l}+(\delta-B_{z^*,l})z_*B_{z_*-1,l}}{ \delta\Delta_{z_*,l}},\end{align*}

where $z^*$ and $z_*$ are shorthand for $z^*(l,\delta,\lambda)$ and $z_*(l,\delta,\lambda)$ , respectively, which are defined in (9). Then, we have the following theorem.

Equations (62) and (64) follow from (1) with the limit $n \to \infty$ . Other equations will be shown in Appendix N after several preparations.

In contrast, we have the following proposition under the i.i.d. case.

Cases (a) and (b) immediately follow from the law of small numbers and the large deviation principle, respectively. For the reader’s convenience, we give their proofs in Appendix G. A numerical comparison among (62), (63), and (66) is presented as Figure 2(a).

7.2. Minimum number of required observations n

Next, we consider the minimum number of observations n required to guarantee the upper confidence limit $\epsilon$ at significance level $\delta$ . For $0 \leq \lambda < 1$ , $0 < \epsilon,\delta < 1$ , and $k,l\in\mathbb{Z}^{\geq 0}$ , we define the following values:

\begin{align*}N_{\lambda,\textrm{c}}(l,\epsilon, \delta)\,:\!=\,&\min \{n \in\mathbb{Z}^{\geq l+1}\,|\, \overline{\epsilon}(T_l(\lambda), n,\delta) \le \epsilon \}, \\N_{\textrm{i.i.d.},\textrm{c}}(k,\epsilon, \delta)\,:\!=\,&\min \{n \in\mathbb{Z}^{\geq k+1}\,|\, \overline{\epsilon}_{\textrm{i.i.d.}}(T_k,n,\delta) \le \epsilon \} .\end{align*}

In the above notation, the subscript c expresses the constant regime.

For the asymptotic evaluation of $N_{\lambda,\textrm{c}}(l,\epsilon, \delta)$ , we have the following result.

In case (b), choosing non-zero $\lambda$ improves the required number $N_{\lambda,\textrm{c}}(k_0,\epsilon,\delta)$ exponentially.

Proof. Equations (68), (69), and (70) follow from (62), (63), and (66), respectively. When $\delta^{-1}$ and n go to infinity, (71) follows from (1).

Equation (72) can be shown from (65) as follows. We consider the following equation for r:

\begin{align*}\lim_{n\to \infty}\overline{\epsilon}(T_{\lceil\nu k_0\rceil}(\lambda),n,\delta=\mathrm{e}^{-r n})=\frac{r}{r +\lambda(\ln\lambda^{-1}-r)}=\epsilon.\end{align*}

The solution is $ r= {\lambda\epsilon\ln\lambda^{-1}}/({1-\nu\epsilon})$ . Since $\delta=\mathrm{e}^{-nr}$ , we obtain (72). In the same way, solving the equation $1-\mathrm{e}^{-r}=\epsilon$ for r, we obtain (73) from (67).

As shown in Appendix H after several preparations, we have the following lemma.

Lemma 3. Suppose $0 < \lambda,\epsilon,\delta< 1$ and $k_0\in\mathbb{Z}^{\geq 0}$ . Then

\begin{align*}\lim_{\delta,\epsilon\to 0} \frac{\epsilon N_{\lambda,\textrm{c}}(\lceil\nu k_0\rceil,\epsilon,\delta)}{\ln \delta^{-1}}=\frac{1}{\lambda \ln \lambda^{-1}},\end{align*}

where the order of the two limits $\epsilon\to 0$ and $\delta\to 0$ does not matter.

The function ${1}/({\lambda \ln \lambda^{-1}})$ takes the minimum value e when $\lambda= 1/\mathrm{e}$ . Hence, the choice $\lambda= 1/\mathrm{e}$ is optimal under the constant regime.

8.1. Region approach

We extend the idea based on the region used in Section 4.2 to the case with the test $T_l(\lambda)$ . In order to determine the upper confidence limit $\overline{\epsilon}(T_l(\lambda),n,\delta)$ , we introduce the quantities $p_l (Q)$ and $f_l(Q)$ for $0 \leq \lambda < 1$ , $l\in\mathbb{Z}^{\geq 0}$ , $n\in\mathbb{Z}^{\geq l+1}$ , and $Q \in {\mathcal Q}_{n+1}$ as

\begin{align*}p_l (Q)\,:\!=\,Q(L \le l), \quad f_l (Q)\,:\!=\,Q(Y_{n+1}=0, L \le l).\end{align*}

Then, instead of $\overline{\epsilon}(T_l(\lambda),n,\delta)$ , we discuss $\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)\,:\!=\,1-\overline{\epsilon}(T_l(\lambda),n,\delta)$ . Define the two-dimensional region ${\mathcal R}_{l,n,\lambda}$ as

(74) \begin{align}{\mathcal R}_{l,n,\lambda}\,:\!=\,\big\{\big(p_l (Q),f_l (Q)\big)\in \mathbb{R}_+^2\,\big|\,Q \in {\mathcal Q}_{n+1}\big\}.\end{align}

This region ${\mathcal R}_{l,n,\lambda}$ is convex because $p_l (Q)$ and $f_l (Q)$ are both linear in Q, and the set ${\mathcal Q}_{n+1}$ is convex. The geometric picture of ${\mathcal R}_{l,n,\lambda}$ is helpful to understanding and calculating $\overline{\epsilon}(T_l(\lambda),n,\delta)$ . In particular, $\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)$ can be determined for all $0 < \delta\leq 1$ once the lower boundary of ${\mathcal R}_{l,n,\lambda}$ is known, because it has the following form

(75) \begin{align}\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)&=\min_{Q \in {\mathcal Q}_{n+1}}\{Q(Y_{n+1}=0\,|\, L \le l)\,|\, Q(L \le l) \ge \delta \}\nonumber\\&=\min_{Q \in {\mathcal Q}_{n+1}} \bigg\{\frac{f_l (Q)}{p_l (Q)}\,\bigg|\, p_l (Q) \ge \delta \bigg\}.\end{align}

To characterize ${\mathcal R}_{l,n,\lambda}$ , we define the random variable $Z\,:\!=\,\sum_{i=1}^{n+1}Y_i$ . Then any $Q \in {\mathcal Q}_{n+1}$ is completely determined by the $n+1$ probabilities $\{Q(Z=z)\}_{z=0}^n$ , and the joint distribution $P_{Y_1, \ldots, Y_{n+1}}$ of $Y_1, \ldots, Y_{n+1}$ is given as

\begin{align*} P_{Y_1, \ldots, Y_{n+1}}(y_1, \ldots, y_{n+1})= {\left(\begin{smallmatrix} n+1 \\ \sum_{i=1}^{n+1}y_i \end{smallmatrix}\right)}^{-1} Q\bigg(Z=\sum_{i=1}^{n+1}y_i \bigg) .\end{align*}

For integer $0 \leq z \leq n+1$ , we define

(76) \begin{align}h_z(l,n,\lambda)&\,:\!=\,Q(L \le l\,|\, Z=z)=\begin{cases}1 & 0 \leq z \le l, \\[6pt]\dfrac{(n-z+1) B_{z,l} +z B_{z-1,l} }{n+1} & l+1 \leq z \leq n+1,\end{cases} \end{align}

(77) \begin{align}g_z(l,n,\lambda)&\,:\!=\,Q(Y_{n+1}=0, L \le l\,|\, Z=z)=\begin{cases}\dfrac{n-z+1}{n+1} & 0 \leq z \le l, \\[6pt]\dfrac{(n-z+1)B_{z,l}}{n+1} & l+1 \leq z \leq n+1,\end{cases}\end{align}

where $B_{z,l}$ is shorthand for $B_{z,l}(\nu)$ as defined in (7), and $B_{z,l}(\nu)=1$ for $l\geq z$ . The second equality of (76) and the second equality of (77) are proved in Appendix 1. Then, we have

\begin{align*}Q(L \le l)&=\sum_{z=0}^{n+1}Q(Z=z)Q(L \le l \,|\, Z=z)=\sum_{z=0}^{n+1}Q(Z=z)h_z(l,n,\lambda) ,\\Q(Y_{n+1}=0,L \le l)&=\sum_{z=0}^{n+1}Q(Z=z)Q(Y_{n+1}=0,L \le l \,|\, Z=z)\\&=\sum_{z=0}^{n+1}Q(Z=z)g_z(l,n,\lambda) .\end{align*}

Therefore, any element of the region ${\mathcal R}_{l,n,\lambda}$ can be written as a convex combination of the $n+2$ points $\left\{ (h_z(l,n,\lambda),g_z(l,n,\lambda))\right\}_{z=0}^{n+1}$ . That is, we obtain the following proposition.

Proposition 5. The two-dimensional region ${\mathcal R}_{l,n,\lambda}$ (see Figure 4) is the convex hull of the following set of points

(78) \begin{align}\left\{\big(h_z(l,n,\lambda),g_z(l,n,\lambda)\big)\right\}_{z=0}^{n+1}.\end{align}

Figure 4.

The region ${\mathcal R}_{l,n,\lambda}$ composed of points $(p_l (Q),f_l (Q))$ as defined in (74). The region is the convex hull of the points in (78), which are highlighted as dots. Here we choose $l=3$ for all plots.

Figure 4 Long description

The image contains four scatter plots arranged in a 2x2 grid. Each plot compares points in regions defined by the parameters lambda and n. The x-axis represents p_l(Q) and the y-axis represents f_l(Q). The top-left plot shows data for lambda equals 0 and n equals 10, with a convex hull and highlighted dots. The top-right plot shows data for lambda equals 1/3 and n equals 10, with a convex hull and highlighted dots. The bottom-left plot shows data for lambda equals 0 and n equals 50, with a convex hull and highlighted dots. The bottom-right plot shows data for lambda equals 1/3 and n equals 50, with a convex hull and highlighted dots. The convex hulls are shaded in cyan, and the highlighted dots are red. The plots illustrate the relationship between p_l(Q) and f_l(Q) under different conditions.

According to this proposition, ${\mathcal R}_{l,n,\lambda}$ is a polygon, as illustrated in Figure 4. Now, the original complicated problem of determining the region ${\mathcal R}_{l,n,\lambda}$ has been transformed into the intuitive task of studying the geometric relation between the $n+2$ points given in (78).

8.2. Case with $\lambda>0$

In this subsection we discuss $\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)$ in the case $0 < \lambda < 1$ .

As the first step, we clarify that the lower boundary of the region ${\mathcal R}_{l,n,\lambda}$ defined in (74) consists of $n-l+1$ line segments, as shown in the following lemmas (see Appendix J for proofs).

Next, we shall determine the exact value of $\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)$ . By Lemma 4, we have $B_{n,l}=h_{n+1}(l,n,\lambda)\leq h_z(l,n,\lambda)\leq 1$ for $z\in\{0,\dots,n+1\}$ . For $B_{n,l}<\delta\leq 1$ , let $\hat{z}$ be the largest integer z such that $h_z(l,n,\lambda)\geq\delta$ . For $z\in\{l,l+1,\dots,n\}$ , define

(79) \begin{align}\kappa_z(l,n,\delta,\lambda) \,:\!=\,\;& \frac{\delta-h_{z+1}(l,n,\lambda)}{h_z(l,n,\lambda)-h_{z+1}(l,n,\lambda)}, \end{align}

(80) \begin{align}\tilde{\zeta}_\lambda(l,n,\delta,z) \,:\!=\,\;& [1-\kappa_z(l,n,\delta,\lambda)]g_{z+1}(l,n,\lambda) +\kappa_z(l,n,\delta,\lambda)g_z(l,n,\lambda). \end{align}

The following theorem provides the analytical expression of $\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)$ .

Theorem 3. Suppose $0 < \lambda < 1$ , $0 < \delta \leq 1$ , $l\in\mathbb{Z}^{\geq 0}$ , and $n\in\mathbb{Z}^{\geq l+1}$ . Then we have

\begin{align*}&\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)=\begin{cases}0 & \delta \leq B_{n,l}, \\\delta^{-1}\, \tilde{\zeta}_\lambda(l,n,\delta,\hat{z}) >0 & \delta > B_{n,l}.\end{cases}\end{align*}

Proof. According to (75), to determine the value of $\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)$ , we need to find the best point $\big(p_l (Q),f_l (Q)\big)$ in the region ${\mathcal R}_{l,n,\lambda}$ such that $p_l (Q) \ge \delta$ and ${f_l (Q)}/{p_l (Q)}$ is minimum. Note that this best point must be on the lower boundary of ${\mathcal R}_{l,n,\lambda}$ .

First, we consider the case $0 < \delta \leq B_{n,l}$ . According to Proposition 5, the point $\big(h_{n+1}(l,n,\lambda),g_{n+1}(l,n,\lambda)\big)=(B_{n,l},0)$ is in the region ${\mathcal R}_{l,n,\lambda}$ . Hence, there exists a $Q\in {\mathcal Q}_{n+1}$ such that $p_l (Q) \ge \delta$ and ${f_l (Q)}/{p_l (Q)}=0$ . This implies that $\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)=0$ .

Second, we consider the case $B_{n,l}<\delta\leq 1$ . Let $\big(p_l (Q_A),f_l (Q_A)\big)$ be the point on the lower boundary of ${\mathcal R}_{l,n,\lambda}$ that satisfies $p_l (Q_A)=\delta$ . According to Proposition 5 and Lemmas 4 and 5, if $\big(p_l (Q_B),f_l (Q_B)\big)$ is a point on the lower boundary of ${\mathcal R}_{l,n,\lambda}$ that satisfies $p_l (Q_B)>\delta$ , then we must have ${f_l (Q_B)}/{p_l (Q_B)}>{f_l (Q_A)}/{p_l (Q_A)}$ . Therefore, $\big(p_l (Q_A),f_l (Q_A)\big)$ is the best point $\big(p_l (Q),f_l (Q)\big)$ in the region ${\mathcal R}_{l,n,\lambda}$ such that $p_l (Q) \ge \delta$ and ${f_l (Q)}/{p_l (Q)}$ is minimum. This implies that

(81) \begin{align}\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)= \frac{f_l (Q_A)}{p_l (Q_A)}= \frac{f_l (Q_A)}{\delta}.\end{align}

Since $p_l (Q_A)=\delta$ and $\hat{z}$ is the largest integer z such that $h_z(l,n,\lambda)\geq\delta$ , the point $\big(p_l (Q_A),f_l (Q_A)\big)$ is on the line segment connecting the following two points,

\begin{align*}\big(h_{\hat{z}+1}(l,n,\lambda), g_{\hat{z}+1}(l,n,\lambda)\big), \quad\big(h_{\hat{z}}(l,n,\lambda), g_{\hat{z}}(l,n,\lambda)\big).\end{align*}

Using this fact, one can easily verify that $f_l (Q_A)=\tilde{\zeta}_\lambda(l,n,\delta,\hat{z})$ . This together with (81) completes the proof of Theorem 3.

In particular, when $\delta=h_z(l,n,\lambda)$ for $z\in\{l,l+1,\dots,n+1\}$ , Theorem 3 implies that

(82) \begin{align}\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta=h_z(l,n,\lambda))= \frac{g_z(l,n,\lambda)}{h_z(l,n,\lambda)},\end{align}

which is non-increasing in z. This is because $h_z(l,n,\lambda)$ decreases monotonically with z by Lemma 4, and $\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)$ is non-decreasing in $\delta$ for $0 < \delta\leq1$ by Proposition 6.

As a counterpart of Proposition 1 in Section 3.3, the following proposition clarifies the monotonicities of $\overline{\epsilon}(T_l(\lambda),n,\delta)$ . See Appendix K for a proof.

In the following, in order to show the remaining unproved results of Theorems 1 and 2, we prepare two useful statements, which provide several tight bounds for $\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)$ . Corollary 4 follows from (82), Theorem 3, Lemma 4, and the fact that $\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta) $ is non-decreasing in $\delta$ by Proposition 6. Lemma 6 is proved in Appendix L.

Corollary 4. Suppose $0 < \lambda < 1$ , $0 < \delta < 1$ , $l\in\mathbb{Z}^{\geq 0}$ , and $n\in\mathbb{Z}^{\geq l+1}$ , then we have

\begin{align*}\frac{g_{z^*+1}(l,n,\lambda)}{h_{z^*+1}(l,n,\lambda)}\leq \overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)\leq \max \left\{0, \frac{g_{z_*}(l,n,\lambda)}{h_{z_*}(l,n,\lambda)}\right\},\end{align*}

where $z^*$ and $z_*$ are shorthand for $z^*(l,\delta,\lambda)$ and $z_*(l,\delta,\lambda)$ defined in (9), respectively.

Lemma 6. Suppose $0 < \lambda < 1$ , $0 < \delta < 1$ , $l\in\mathbb{Z}^{\geq 0}$ , and $n\in\mathbb{Z}^{\geq l+1}$ . Then

(83) \begin{align}\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)&\leq \max \left\{0, \frac{\lambda(n-z_*+1)}{\lambda(n-z_*+1)+z_*-l }\right\}, \end{align}

(84) \begin{align}\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)&\geq \frac{\lambda(n-z^*)}{\lambda(n-z^*)+z^*+1 }. \end{align}

If in addition $\delta\leq \tfrac12$ then

(85) \begin{align}\overline{\epsilon}^\textrm{c}(T_l(\lambda),n,\delta)&\geq \frac{\lambda(n-z^*)}{\lambda(n-z^*)+z^*-l+1+\sqrt{\lambda l} }\geq 1-\frac{z^*-l+1+\sqrt{\lambda l}}{\lambda n }.\end{align}