1 Introduction↩︎

A central concern in sequential hypothesis testing is the efficient use of observations: one wishes to minimize the number of samples required to accept one of two or more hypotheses with sufficiently small error probabilities. Wald and Wolfowitz Wald1948? showed that for two simple hypotheses the sequential probability ratio test (SPRT) is optimal in the sense that it minimizes the expected sample size simultaneously under both hypotheses. However, the sample efficiency of the SPRT is highly sensitive to model mismatch. In fact, when the true distribution differs from the assumed ones, the expected sample size of an SPRT can significantly exceed that of a fixed-sample-size test (FSST) with identical error probabilities—compare, for example, Tartakovsky2014?.

Prompted by this observation, Jack Kiefer and Lionel Weiss proposed to design a sequential test that, in addition to meeting the targeted error probabilities under both hypotheses, minimizes the maximum expected sample size over a parametric family of distributions Kiefer1957?, Weiss1962?. More formally, Kiefer and Weiss assumed that observations are drawn independently from a parametric distribution \(P_\theta\), with \(\theta = \theta_0\) and \(\theta = \theta_1\) under the respective hypotheses. The Kiefer–Weiss test (KWT) is then defined as the sequential test that admits prescribed Type I and Type II error probabilities and minimizes the maximum expected sample size over \(\theta \in \Theta\), where \(\Theta\) is a set of feasible parameter values. This problem, in various forms, has received considerable attention in the literature Dvoretzky1953?, Anderson1960?, Robbins1972?, Lai1973?, Lorden1976?, Eisenberg1982?, Huffman1983?, Dragalin1988?, Lai1988?, Pavlov1991?, Augustin2001?, Zhitlukhin2013?, Novikov2022?, Novikov2022a?, Novikov2023?.

The general solution of the Kiefer–Weiss problem turned out to be rather elusive, which caused the focus to shift to special cases and approximations. The most well-studied cases are the Kiefer–Weiss test for a shift in the mean parameter of a normal distribution Anderson1960?, Weiss1962?, Lai1973?, Lorden1976? and the closely related problem of testing the drift parameter of a Wiener process Dvoretzky1953?, Zhitlukhin2013?. Asymptotic, approximate and numeric results exist for more general families of distributions Robbins1972?, Eisenberg1982?, Huffman1983?, Dragalin1988?, Pavlov1991?, Augustin2001?, Novikov2022?, Novikov2022a?, Novikov2023?. An up-to-date treatment of the Kiefer–Weiss problem and some of its variations can be found in Tartakovsky2014?.

In this paper, we study a novel variant of the Kiefer–Weiss problem: Our objective is to minimize a weighted sum of the Type I and Type II error probabilities of a binary sequential test subject to a constraint on its maximum expected sample size. However, rather than over a parametric family, this maximum is taken over all possible probability distributions on the given sequence space. We therefore refer to the resulting formulation as the nonparametric Kiefer–Weiss problem¹ and the corresponding optimal test as the nonparametric Kiefer–Weiss test (NPKWT).

The remainder of the paper is organized as follows: In Section 2, we introduce our notation and assumptions. The core sections of the paper are Section 3, in which the nonparametric Kiefer–Weiss problem is formally defined, and Section 4, in which its solution is derived. The results are discussed in Section 5. Two approximations of the optimal stopping policy are proposed in Section 6. Numerical examples and illustrations are presented in Section 7. Section 8 concludes the paper and briefly discusses directions for future research.

2 Notation and Assumptions↩︎

Throughout the paper, \(\mathbb{N}_{\geq n}\) denotes the set of integers greater than or equal to \(n\). Analogously, \(\mathbb{R}_{\geq x}\) denotes the set of real numbers greater than or equal to \(x\). The set of all sequences with values in \([0, 1]\), sometimes referred to as the Hilbert cube Aliprantis2007?, is denoted by \(\mathcal{I}^\infty \coloneq [0,1]^\infty\). The indicator function of a set \(\mathcal{A}\) is denoted by \(\boldsymbol{1}_{\mathcal{A}}\). We write \(x^* = \mathop{\mathrm{arg\,max}}_{x \in \mathcal{X}} f(x)\) to indicate that \(x^*\) is a maximizer of \(f\) over \(\mathcal{X}\). Random variables are denoted by uppercase letters, and their realizations by the corresponding lowercase letters. Since it appears frequently in the sequel, we define the function \(g \colon \mathbb{R}_{\geq 0} \to [0,1]\) as \(g(z) \coloneq \min\{1, z\}\).

Let \(\boldsymbol{X} = (X_1, X_2, \ldots)\) be a sequence of random variables with values in a measurable space \((\mathcal{X}, \mathcal{F})\). The truncated sequence \((X_1, \ldots, X_t)\) is denoted by \(\boldsymbol{X}_t\). The joint distribution of \(\boldsymbol{X}\) is denoted by \(\mathbf{P}\in \mathcal{M}(\mathcal{X}^\infty)\), where \(\mathcal{M}(\mathcal{X}^\infty)\) denotes the set of all probability measures on the sequence space \(\mathcal{X}^\infty\). We assume that two simple hypotheses about \(\mathbf{P}\) are given: \[\begin{align} \mathcal{H}_0 &\colon \boldsymbol{X} \text{ i.i.d.\;according to } P_0, \\ \mathcal{H}_1 &\colon \boldsymbol{X} \text{ i.i.d.\;according to } P_1. \end{align}\] In words, we seek to test whether the elements of \(\boldsymbol{X}\) are independent and identically distributed (i.i.d.) according to \(P_0\) or to \(P_1\). For the sake of exposition, it is further assumed that \(P_1\) is absolutely continuous with respect to \(P_0\) and that the Kullback–Leibler divergence \(D_\text{KL}(P_0 \Vert P_1)\) is non-zero and finite. The densities of \(P_0\) and \(P_1\) with respect to a suitable background measure are denoted by \(p_0\) and \(p_1\), respectively. Possible relaxations of these assumptions are discussed in Section 5.

At every time \(t\), a sequential test needs to make a decision to stop or continue. Let \(\boldsymbol{S} = (S_0, S_1, \ldots)\) denote a sequence of binary random variables corresponding to this decision, that is, the sequential test stops at time \(t\) if \(S_t = 1\) and continues if \(S_t = 0\). The corresponding stopping time is defined as \[T = \min\{\, t \geq 0 : S_t = 1 \,\}.\] Upon stopping, the test outputs a binary decision \(D\), where \(D = 0\) indicates acceptance of \(\mathcal{H}_0\), and \(D = 1\) indicates acceptance of \(\mathcal{H}_1\).

Let \(\mathbb{P}\) be the joint distribution of \((\boldsymbol{X}, \boldsymbol{S}, D)\), and let \(\mathbb{E}\) denote the corresponding expectation operator. We define the conditional expectations: \[\psi_t = \psi_t(\boldsymbol{x}_t) \coloneq \mathbb{E}\bigl[ S_t \,|\, \boldsymbol{X}_t = \boldsymbol{x}_t \bigr] \label{eq:psi95t}\tag{1}\] and \[\delta_t = \delta_t(\boldsymbol{x}_t) \coloneq \mathbb{E}\bigl[ D \,|\, T = t, \boldsymbol{X}_t = \boldsymbol{x}_t \bigr]. \label{eq:delta95t}\tag{2}\] The sequence \(\psi = (\psi_0, \psi_1, \ldots) \in \mathcal{I}^\infty\) is referred to as a stopping policy, and the sequence \(\delta = (\delta_0, \delta_1, \ldots) \in \mathcal{I}^\infty\) as a decision policy. The pair \((\psi, \delta)\) is called a testing policy and completely specifies a sequential test.

For notational convenience, we define the shorthand \[\phi_t = \phi_t(\boldsymbol{x}_t) \coloneq \mathbb{P}\bigl[T = t \mid \boldsymbol{X}_t = \boldsymbol{x}_t \bigr] = \psi_t(\boldsymbol{x}_t)\prod_{n=0}^{t-1} \bigl(1 - \psi_n(\boldsymbol{x}_n)\bigr), \label{eq:phi95t}\tag{3}\] which denotes the probability of stopping at time \(t\) given observations \(\boldsymbol{x}_t\). We further define \[\tau(\boldsymbol{x}) \coloneq T \mid (\boldsymbol{X} = \boldsymbol{x}) \label{eq:tau}\tag{4}\] to represent the stopping time associated with a given observation sequence \(\boldsymbol{x}\). Note that \(\tau(\boldsymbol{x})\) is deterministic for deterministic stopping policies but random in general.

For notational clarity, we make explicit the dependence of \(\mathbb{P}\) on the sample distribution, the stopping policy, and the decision policy. Specifically, we write \(\mathbb{P}= \mathbb{P}_{\mathbf{P}, \psi, \delta}\) and \(\mathbb{E}= \mathbb{E}_{\mathbf{P},\psi,\delta}\) for the probability distribution and expectation, respectively. Under hypothesis \(\mathcal{H}_i\), \(i \in \{0,1\}\), we write \(\mathbb{P}_{i,\psi,\delta}\) and \(\mathbb{E}_{i,\psi,\delta}\). Whenever a probability or expectation does not depend on \(\mathbf{P}\), \(\psi\), or \(\delta\), the corresponding subscripts are omitted. For example, \(\mathbb{P}_{\mathbf{P}, \psi, \delta}\bigl[ T = 0 \bigr] = \mathbb{P}_{\psi}\bigl[ T = 0 \bigr]\).

Finally, the Type I and Type II error probabilities of a sequential test of \(\mathcal{H}_1\) against \(\mathcal{H}_0\) using policy \((\psi,\delta)\) are written as \[\alpha(\psi,\delta) \coloneq \mathbb{E}_{0,\psi,\delta}[D] \quad \text{and} \quad \beta(\psi,\delta) \coloneq \mathbb{E}_{1,\psi,\delta}[1-D].\] We are now ready to formulate the nonparametric Kiefer–Weiss problem.

3 The Nonparametric Kiefer–Weiss Problem↩︎

Let \(\mathcal{I}_c^\infty\) denote the set of stopping policies for which the expected sample size of the underlying sequential test is bounded by some constant \(c \geq 0\) for all possible distributions of \(\boldsymbol{X}\): \[\mathcal{I}_c^\infty \coloneq \bigl\{\psi \in I^\infty \colon \mathbb{E}_{\mathbf{P}, \psi}\bigl[\, T \,\bigr] \leq c \quad \forall \, \mathbf{P}\in \mathcal{M}(\mathcal{X}^\infty) \bigr\}. \label{eq:stopping95policy95prob}\tag{5}\] We define the nonparametric Kiefer–Weiss problem as follows: \[\inf_{\psi \in \mathcal{I}_c^\infty} \; \inf_{\delta \in \mathcal{I}^\infty} \; \alpha(\delta, \psi) + z \, \beta(\delta, \psi), \label{eq:nonpa95kiwei}\tag{6}\] where \(z, c \geq 0\). In words, we seek to design a policy for a sequential test between two simple hypotheses that minimizes the weighted sum of its error probabilities, subject to the constraint that its expected sample size does not exceed \(c\) for all possible distributions of \(\boldsymbol{X}\).

In the remainder of this section, some useful simplifications of 6 are derived. First, we show that 5 can equivalently be defined via a pointwise constraint on the expected conditional sample size, \(\mathbb{E}_\psi[\tau(\boldsymbol{x})]\).

Theorem 1 is proven in Appendix 9.

Next, it is shown that the optimal testing problem can be reduced to an optimal stopping problem by minimizing out the decision policy. Variations of this result are well-known in sequential analysis. It is stated and proven here for completeness.

Theorem 2 is proven in Appendix 10

The nonparametric Kiefer–Weiss problem can now be written as \[\inf_{\psi \in \mathcal{I}_c^\infty} \; \alpha(\psi) + z \, \beta(\psi), \label{eq:nonpa95kiwei95stopping}\tag{10}\] where, in a slight abuse of notation, we defined \(\alpha(\psi) \coloneq \alpha(\psi, \delta^*)\) and \(\beta(\psi) \coloneq \beta(\psi, \delta^*)\).

We conclude this section by showing existence of an optimal stopping policy.

Lemma 1 is proven in Appendix 11.

4 The Nonparametric Kiefer–Weiss Test↩︎

In this section, we derive the stopping policy that solves 10 . To this end, a recurrence relation is established that leads to a characterization of the optimal stopping policy as the solution of a nonlinear integral equation of the Bellman type. This equation is derived by considering policies that are restricted in terms of how many randomized stopping decision can be made during the test. We refer to this as the limited-randomness case. The solution to the original problem is then obtained by letting the number of allowed randomization uses go to infinity.

4.1 Limited Randomness↩︎

Let \(\mathcal{I}_{c,k}^\infty\) denote the set of policies that are feasible in the sense of 7 , but whose use of randomization is limited to \(k \in \mathbb{N}_{\geq 0}\) instances: \[\mathcal{I}_{c,k}^\infty \coloneq \biggl\{\psi \in \mathcal{I}_c^\infty : \sum_{t = 0}^T \boldsymbol{1}_{(0,1)}(\psi_t) \leq k \biggr\}.\] We define the family of functions \(\rho_k \colon \mathbb{R}_{\geq 0}^2 \to [0,1]\) as \[\rho_k(z, c) \coloneq \inf_{\psi \in \mathcal{I}_{c,k}^\infty} \; \alpha(\psi) + z \, \beta(\psi). \label{eq:rho95k95def}\tag{11}\] Limiting the use of randomized stopping decisions causes the space \(\mathcal{I}_{c,k}^\infty\) to be non-compact in general. Therefore, we cannot assume the existence of an optimal stopping policy. However, the optimal policy can be derived in a constructive manner. Before doing so, some useful properties of \(\rho_k\) that follow directly from the definition in 11 are stated.

Lemma 2 is proven in Appendix 12.

Now, assume that \(k = 0\), meaning that the stopping policy is constrained to be deterministic. In this case, the constraint in 7 becomes \[\tau(\boldsymbol{x}) \leq c \quad \forall \boldsymbol{x} \in \mathcal{X}^\infty,\] that is, the underlying sequential test is truncated after at most \(c\) samples. In the next lemma, it is shown that for deterministic stopping rules the nonparametric Kiefer–Weiss test reduces to a fixed-sample size test.

Next, we provide a recursive expression for \(\rho_k\) when \(k \geq 1\).

Lemma 4 is proven in Appendix 13. It completely specifies the optimal nonparametric Kiefer–Weiss test with at most \(k\) randomized stopping decisions. More specifically, given \(\rho_{k-1}\) for some \(k \geq 0\), \(\rho_k(z, \bullet)\) can be calculated on the interval \([0, 1)\) via the first case in 13 . Given \(\rho_k(z, \bullet)\) on \([0, 1)\), it can be evaluated on \([1, 2)\) via the second case in 13 . Continuing in this manner, \(\rho_k(z, \bullet)\) can be pieced together on \(\mathbb{R}_{\geq 0}\) and can in turn be used to calculate \(\rho_{k+1}\). The corresponding optimal stopping rules can be obtained from the arguments that maximize/minimize the respective terms in 13 . This result is made formal in the next theorem. To simplify its statement, we define the following condition: \[\mathbb{E}_0\Bigl[\rho_k\Bigl( z \frac{p_1(X)}{p_0(X)}, c - 1\Bigr)\Bigr] \leq g(z) - c \, \max_{b \geq c} \, r_{k-1}(z, b). \label{eq:cont95condition}\tag{14}\] This condition is true if the minimum in the case \(c \geq 1\) in 13 is attained by its first argument.

The three quantities tracked by the test statistic in Theorem 3 are the likelihood ratio, \(z_t\), the maximum expected remaining sample size, \(c_t\), and the number of remaining randomization uses, \(k_t\). The underlying idea is that randomized stopping decisions allow the test to increase the number of samples in some runs at the expense of stopping early in others. By carefully choosing when and how to randomize, this policy can achieve lower error probabilities than a truncated SPRT or an FSST. A more detailed discussion of the optimal policy is deferred to Section 5.

Although its optimal stopping policy can be calculated explicitly, the limited-randomness case is somewhat unsatisfying, both from a theoretical and a practical perspective. The constraint on the use of randomization is arguably artificial and unlikely to arise in practice. Moreover, recursive calculation of \(\rho_k\) via 13 is computationally expensive and error prone. In general, \(\rho_k\) is non-convex and discontinuous, making it hard to approximate it numerically and to solve the maximization problems in 13 —numerical examples will be shown in Section 5. Interestingly, these complications disappear as \(k \to \infty\). This limit is investigated in the next section.

4.2 Unlimited Randomness↩︎

The unlimited randomness case can be recovered from the limited randomness case by letting \(k \to \infty\). In the next lemma, we show that \(\rho_k\) converges to the minimum cost of the original problem in 10 .

Next, we characterize \(\rho\) in terms of an integral equation of the Bellman type.

Lemma 6 is proven in Appendix 14.

Comparing 17 to 13 , it appears that \(\rho\) is smoother than \(\rho_k\) in the sense that it requires fewer case-by-case comparisons and is not explicitly derived from the discontinuous function \(\rho_0\). However, given its derivation, one would still expect \(\rho\) to show remnants of discontinuity. This intuition is formalized in the next lemma.

Lemma 7 is proven in Appendix 15. It is key to simplifying the optimal stopping rule and allows us to eliminate most of the complications that occurred in the limited randomness case. First, since a convex and piecewise linear function is completely specified by its breakpoints, we can restrict the domain of the second argument of \(\rho\) to \(\mathbb{N}_{\geq 0}\) without loss of generality.

We can now state the optimal stopping policy of the nonparametric Kiefer–Weiss test. This constitutes the main result of the paper.

Theorem 4 is proven in Appendix 16.

5 Discussion↩︎

By inspection of Theorem 4, the NPKWT uses a two-dimensional test statistic: \(z_t\) tracks the likelihood ratio, and \(c_t\) tracks the expected number of remaining samples. The evolution of \(c_t\), and in turn the stopping policy of the test, is completely specified by the function \(m^*\), which maps a (real-valued) likelihood ratio to an (integer-valued) sample size. At time \(t\), the test stops with certainty if and only if \(c_t = 0\), and it continues with certainty if and only if \(c_t \geq m^*(z_t)\). In all other cases, the stopping decision is randomized and the test continues with probability \(\frac{c_t}{m^*(z_t)}\).

The NPKWT can be interpreted as a conventional SPRT augmented with a “sample budget,” \(c_t\). As long as this budget is sufficiently large, the test continues with certainty and decrements \(c_t\) with every observation. In this regime, the NPKWT effectively behaves like an FSST. However, its behavior changes when \(c_t\) is small enough that the test outcome is effectively determined, meaning the probability of the remaining samples changing the decision is close to zero. In this case, the NPKWT either stops immediately and saves the remaining samples for another run, or continues with a sample budget that is sufficiently large to potentially affect its outcome. The function \(m^*\) makes this notion precise: Given the likelihood ratio \(z_t\), continuing the test is only worthwhile if the available sample budget is at least \(m^*(z_t)\).

The stopping policy of the NPKWT will be illustrated with concrete, numerical examples in Section 7. Before concluding this section, some additional remarks are useful:

• The optimal stopping policy, \(\psi^*\), satisfies \(\mathbb{E}_{\psi^*}[\tau(\boldsymbol{x})] = c\) for all \(\boldsymbol{x} \in \mathcal{X}^\infty\). That is, the NPKWT has a constant expected sample size for all possible sequences \(\boldsymbol{x} \in \mathcal{X}^\infty\). In turn, every distribution is least favorable. This “equalization of cost” is a well-known characteristic of minimiax procedures; see, for example, Lehmann1998?. Interestingly, by construction, the equalization property not only holds for \(m^*\), but for all functions \(\mathbb{R}_{\geq 0} \to \mathbb{N}_{\geq 1}\). Suboptimal choices will increase the error probabilities, but will not violate the sample size constraint. In this sense, the NPKWT is robust against deviations from the optimal policy.

• In contrast to most sequential tests, including the parametric KWT, the stopping rule of the NPKWT is not threshold-based. Loosely speaking, the NPKWT stops because of “insufficient remaining samples,” not because of “sufficient evidence.”

• The NPKWT is untruncated in the sense that its stopping time is generally supported on \(\mathbb{N}_{\geq 0}\). Arguably, this is an unexpected property for at least two reasons: First, given the underlying problem formulation, one might expect the NPKWT to be truncated in order to avoid sequences with unbounded stopping time. This intuition is true for deterministic stopping policies, for which the existence of such a sequence indeed implies an unbounded expected stopping time. For randomized policies, however, each sequence is associated with a stopping time distribution whose expectation can be bounded, despite its support being unbounded. Second, it is well-known that the parametric KWT is typically truncated Tartakovsky2014?. Since the NPKWT is a restriction of the KWT, it seems natural that it should inherit this property. However, the significantly stricter constraint on the expected sample size changes the character of the test. As discussed above, the NPKWT is no longer a threshold-based sequential test, so that intuitions learned from the latter do not necessarily carry over.

• When the NPKWT continues after a randomized stopping decision, its expected remaining sample size becomes integer-valued since \(m^*\) maps to \(\mathbb{N}_{\geq 1}\). In other words, \(c_t\) eventually snaps to the integer grid. Moreover, since \(\rho(z, \bullet)\) is affine between integers, an optimal test for a non-integer-valued \(c\) can be implemented by mixing the optimal policies for \(\lfloor c \rfloor\) and \(\lceil c \rceil\). In this sense, policies for non-integer-valued \(c\) are redundant. This observation also supports the interpretation of the NPKWT as a relaxed FSST.

• In practice, it is typically easier to work with logarithmic instead of linear likelihood ratios. In this case, instead of solving 18 , one can directly solve \[\frac{g(a^\lambda) - \varrho(\lambda, n)}{n} = \sup_{m \geq n} \frac{g(a^\lambda) - \mathbb{E}_0\bigl[\varrho\bigl(\lambda + \ell_a(X), m - 1\bigr)\bigr]}{m} \label{eq:rho95bellman95discrete95llr}\tag{21}\] with boundary condition \(\varrho(\lambda, 0) = g(a^\lambda)\) on \(\mathbb{R}\times \mathbb{N}_{\geq 0}\), where \(a\) denotes the base of the logarithm and \[\ell_a(X) \coloneq \log_a \frac{p_1(X)}{p_0(X)}. \label{eq:llr}\tag{22}\] To obtain the counterpart of \(m^*\) in the log-domain, \(\varrho\) can be substituted for \(\rho\) in 19 .

• In 6 , we formulate the nonparametric Kiefer–Weiss problem as an error probability minimization under a constraint on the maximum expected sample size. An alternative formulation, which is arguably more in the spirit of sequential analysis, is to minimize the maximum expected sample size under constraints on the error probabilities: \[\inf_{\psi, \delta \in \mathcal{I}^\infty} \; \sup_{\mathbf{P}\in \mathcal{M}(\mathcal{X}^\infty)} \; \mathbb{E}_{\mathbf{P}, \psi}\bigl[ T \bigr] \quad \text{s.t.} \quad \alpha(\delta, \psi) \leq \overline{\alpha}, \quad \beta(\delta, \psi) \leq \overline{\beta}. \label{eq:nonpa95kiwei95alternative}\tag{23}\] Using Lagrange duality, it is not hard to show that 23 can be solved by finding a pair \((z, c)\) such that the corresponding optimal policy, \((\delta^*, \psi^*)\), saturates the error probability constraints. In other words, \((\delta^*, \psi^*)\) solves 23 if \(\alpha(\delta^*, \psi^*) = \overline{\alpha}\) and \(\beta(\delta^*, \psi^*) = \overline{\beta}\). However, while any decision rule of the form 8 solves 6 , the solution of 23 can require a particular randomization.

• The assumptions that \(P_1\) is absolutely continuous with respect to \(P_0\) and that \(D_\text{KL}(P_0 \lVert P_1)\) is finite can be relaxed. In fact, the latter assumption is not needed for the derivation of the main result but is required for the approximations proposed in the next section. The first assumption can be relaxed by defining \(\frac{p_1}{p_0} \coloneq \infty\) on \(\{ x \in \mathcal{X}\colon p_0(x) = 0, p_1(x) > 0\}\) and \(\rho(\infty, c) \coloneq 1\).

6 Approximate Stopping Policies↩︎

In this section, we propose two approximations of the function \(m^*\) in 19 . Both are obtained by considering the single-randomization case, \(k = 1\). In this case, the optimal remaining sample size after a randomized stopping decision is characterized by \(\rho_0\), which is the cost of a fixed-sample size test and can be closely approximated using standard techniques.

It follows from Theorem 2 and Lemma 3 that for a given pair \(z, c \geq 0\) the optimal test with deterministic stopping policy is a likelihood ratio test of size \(\lfloor c \rfloor\) with decision threshold \(z^{-1}\). Using a normal approximation for the log-likelihood ratio distribution one obtains \[\begin{align} \rho_0(z, c) &= \mathbf{P}_0\Biggl[ \prod_{t=1}^{\lfloor c \rfloor} \frac{p_1(X_t)}{p_0(X_t)} > \frac{1}{z} \Biggr] + z \, \mathbf{P}_1\Biggl[ \prod_{t=1}^{\lfloor c \rfloor} \frac{p_1(X_t)}{p_0(X_t)} \leq \frac{1}{z} \Biggr] \tag{24} \\ &= \mathbf{P}_0\Biggl[ \sum_{t=1}^{\lfloor c \rfloor} \log \frac{p_1(X_t)}{p_0(X_t)} > -\log z \Biggr] + z \, \mathbf{P}_1\Biggl[ \sum_{t=1}^{\lfloor c \rfloor} \log \frac{p_1(X_t)}{p_0(X_t)} \leq - \log z \Biggr] \notag \\ &\approx 1 - \Phi\biggl( -\frac{\log z + \mu_0 \lfloor c \rfloor}{\sigma_0 \sqrt{\lfloor c \rfloor}} \biggr) + z \, \Phi\biggl( -\frac{\log z + \mu_1 \lfloor c \rfloor}{\sigma_1 \sqrt{\lfloor c \rfloor}} \biggr) \notag \\ &\approx \Phi\biggl(\frac{\log z + \mu_0 c}{\sigma_0 \sqrt{c}} \biggr) + z \, \Phi\biggl( -\frac{\log z + \mu_1 c}{\sigma_1 \sqrt{c}} \biggr), \tag{25} \end{align}\] where \(\Phi\) denotes the cumulative distribution function (CDF) of the standard normal distribution, and \(\mu_i, \sigma_i^2\), \(i \in \{0,1\}\), denote the mean and variance of the log-likelihood ratio in 22 under \(\mathcal{H}_i\), respectively. For brevity, we omit the dependence on the base \(a\) in this section. Note that in 24 the underlying test decides for \(\mathcal{H}_0\) if the test statistic hits the threshold exactly. This assignment is arbitrary and without loss of optimality—compare Theorem 2. Finally, in the last step, the flooring operation is dropped to simplify the expression.

Substituting the right-hand side of 25 for \(\rho_0\) in 12 yields an approximation of \(r_0\) and in turn of \(b_1^*\). This is our fist approximation of \(m^*\).

The claim that the right-hand side of 26 is an approximate upper bound on \(m^*\) is based on the following rationale: for \(k = 1\), the NPKWT reduces to a fixed-sample size test after the first randomized stopping decision. That is, given that the test continues, it will take exactly \(\lfloor b_1^* \rfloor\) additional samples. Consequently, \(b_1^*\) needs to be sufficiently large for the additional samples to be useful with high probability. For \(k \gg 1\), in contrast, the sample size remains variable after a randomized stopping decision and can be adjusted again after the next one and so on. This leads to a more conservative increase in the remaining sample size at any particular time. Therefore, \(b_1^*\) is typically larger than \(m^*\). However, in the next section, it will be shown via a numerical counterexample that \(b_1^*\), and in turn its approximation in 29 , is not an upper bound on \(m^*\) in general.

For the second approximation, assume that \(z \to \infty\). In this case, the second term in 25 goes to zero and the right-hand side of 26 reduces to \[\frac{1}{b}\left( g(z) - \Phi\biggl( \frac{\log z + \mu_0 b}{\sigma_0 \sqrt{b}} \biggr)\right) = \frac{1}{b} \Phi\biggl( -\frac{\log z + \mu_0 b}{\sigma_0 \sqrt{b}} \biggr),\] where we used the fact that \(g(z) = 1\) for \(z \geq 1\). In Appendix 17, it is shown that \[\mathop{\mathrm{arg\,max}}_{b \geq 1} \, \frac{1}{b} \Phi\biggl( -\frac{\log z + \mu_0 b}{\sigma_0 \sqrt{b}} \biggr) \geq -\frac{\log z}{\mu_0} - \frac{\sigma_0^2}{\mu_0^2}. \label{EQ:BOPT95LB0}\tag{27}\] Note that the first term on the right-hand side is positive for \(\log z > 0\) since \(\mu_0 < 0\). The same line of arguments can be applied in the case \(z \to 0\) to obtain the bound \[\mathop{\mathrm{arg\,max}}_{b \geq 1} \, \frac{1}{b} \Phi\biggl( \frac{\log z + \mu_1 b}{\sigma_1 \sqrt{b}} \biggr) \geq -\frac{\log z}{\mu_1} - \frac{\sigma_1^2}{\mu_1^2}, \label{eq:bopt95lb1}\tag{28}\] where the first term is positive for \(\log z < 0\) since \(\mu_1 > 0\). These bounds, together with the trivial bound \(m^* \geq 1\), yield our second approximation.

The claim that the right-hand side of 29 is an approximate lower bound is based on two observations: first, by construction, the approximation lower bounds \(b_1^*\) for \(z \to \infty\) and \(z \to 0\), respectively. Second, it follows from Wald’s identity Wald1947? that it also provides a lower bound on the expected number of samples required for an SPRT to reverse a wrong preference, that is, to either lower the log-likelihood ratio from \(\log z > 0\) to \(0\) under \(\mathcal{H}_0\), or to increase it from \(\log z < 0\) to \(0\) under \(\mathcal{H}_1\). More specifically, the \(\log z\)-terms in 27 and 28 correspond to the expected sample sizes when the log-likelihood ratio is assumed to hit \(0\) exactly, and the constant terms are second-order corrections. Interestingly, in sequential detection the correction terms are typically positive and correct for the expected overshoot. Here, the correction terms are negative, suggesting that \(m^*(z)\) can be smaller than Wald’s uncorrected approximation. The numerical examples in the next section show that this is indeed the case.

Finally, we would like to remark that the presented approximations can be improved in various ways. For example, depending on the available compute, one can tighten the approximate upper bound by using 25 as a basis to recursively obtain approximations of \(\rho_k\), \(k \geq 1\), and in turn \(b_k^*\). Alternatively, one can obtain a good approximation of \(m^*\) by dropping or modifying the correction terms in 29 ; see, for example, Siegmund1985? for various higher-order corrections. In general, we believe that interpreting \(m^*(z)\) as the expected number of samples required for an SPRT to return from an excursion to the wrong side of the decision threshold is a good starting point for the derivation of approximate stopping policies for the NPKWT.

7 Numerical Examples↩︎

In this section, we present and discuss two concrete numerical examples of the NPKWT. In the first example, we test for a shift in the success probability of a Bernoulli distribution: \[\begin{align} \mathcal{H}_0 &\colon \boldsymbol{X} \text{ i.i.d.\;according to } \text{Bernoulli}(\frac{1}{3}), \\ \mathcal{H}_1 &\colon \boldsymbol{X} \text{ i.i.d.\;according to } \text{Bernoulli}(\frac{2}{3}). \\ \end{align} \label{eq:bernoulli95example}\tag{30}\] In the second example, we test for a shift in the mean of a normal distribution: \[\begin{align} \mathcal{H}_0 &\colon \boldsymbol{X} \text{ i.i.d.\;according to } \mathcal{N}(0, 1), \\ \mathcal{H}_1 &\colon \boldsymbol{X} \text{ i.i.d.\;according to } \mathcal{N}(1, 1). \\ \end{align} \label{eq:normal95example}\tag{31}\] Both examples are simple, but well-suited to illustrate the NPKWT. For the unlimited randomness case, \(k \to \infty\), the results presented in this section were obtained by numerically solving 21 and in turn 19 . For the two examples above, 21 simplifies to \[\frac{g(2^\lambda) - \varrho(\lambda, n)}{n} = \sup_{m \geq n} \frac{g(2^\lambda) - \frac{2}{3} \varrho\bigl(\lambda - 1 , m - 1\bigr) - \frac{1}{3} \varrho\bigl(\lambda + 1, m - 1\bigr)}{m} \label{eq:rho95bernoulli}\tag{32}\] and \[\frac{g(e^\lambda) - \varrho(\lambda, n)}{n} = \sup_{m \geq n} \frac{g(e^\lambda) - \mathbb{E}_{\mathcal{N}(0, 1)}\bigl[\varrho\bigl(\lambda + X - \frac{1}{2}, m - 1\bigr)\bigr]}{m}, \label{eq:rho95gauss}\tag{33}\] respectively. Note that we used the binary logarithm in 32 and the natural logarithm in 33 .

All results presented in this section were obtained by iteratively calculating \(\rho_{k+1}\) from \(\rho_k\). The basis for the iteration was \(\rho_0\), which can be calculated explicitly for both examples. Both \(\log z\) and \(c\) were discretized on a regular grid. For a given value of \(c\), \(\varrho_k(\bullet, c)\) was evaluated on the given log-likelihood grid, and then approximated using cubic splines. The maximization over \(b_k\) was performed by an exhaustive search over the \(c\)-grid. For the unlimited-randomness case, the iteration was considered converged when \(\lVert \rho_k - \rho_{k-1} \rVert_\infty < 10^{-6}\) on the given grid, where \(\lVert \bullet \rVert_\infty\) denotes the maximum norm. Given its stronger properties, the iteration steps can be slightly simplified if one is only interested in the limit \(\rho\). We will not go into more details of the numerical solution here. Python code to reproduce the results and figures in this section has been made publicly available github?.

7.1 Optimal Cost↩︎

First, we focus on the optimal cost function, \(\rho\), and its limited randomness counterpart, \(\rho_k\). In Fig. 1, the costs of the NPKWTs for the hypotheses in 30 and 31 are plotted as functions of \(z\) for a fixed value of \(c\). Here, we used \(c = 20\) for the Bernoulli example and \(c = 10\) for the Gaussian example. By inspection, the biggest reduction in cost happens when going from \(k = 0\) to \(k = 1\). In light of the discussion in Section 5, this indicates that a single randomization is sufficient to overcome the bottleneck of the test statistic “getting stuck” on the wrong side of the decision threshold. Allowing for an unlimited number of randomization uses, \(k \to \infty\), further reduces the cost, but the effects are less significant.

In Fig. 2, the optimal costs of the same NPKWTs are plotted as functions of \(c\) for a fixed value of \(z\). In both examples, we set \(z = 1\), so that the cost is the sum error probability. For \(k = 0\), the optimal test is an FSST, and \(\rho_0(z, \bullet)\) is a step function with discontinuities contained in the positive integers—compare Lemma 3. Note that in case of the Bernoulli example, increasing the sample size from an odd number to the next even number can affect the individual error probabilities, depending on the randomization of the decision rule, but cannot reduce their sum. Accordingly, the discontinuities of the cost function are located at the odd integers in the plot on the left-hand side of Fig. 2. For \(k = 1\), the cost function becomes smooth, but still admits small bumps at the discontinuities of \(\rho_0(z, \bullet)\), making it non-convex and nonlinear on the intervals between the discontinuities. For \(k \to \infty\), the bumps are ironed-out and the cost function becomes convex and piecewise linear—compare Lemma 7. By inspection, the reduction in cost is again most significant when going from \(k = 0\) to \(k = 1\). However, it takes some iterations for \(\rho_k(z, \bullet)\) to become convex and piecewise linear, which are critical properties for Theorem 4 to hold. Finally, note that the reduction in cost when increasing \(k\) is larger for larger values of \(z\)—compare Fig. 1. We chose \(z = 1\) since it allows for a clear interpretation of the cost function.

7.2 Optimal Expected Remaining Sample Size↩︎

In Fig. 3, the function \(m^*\) in 19 is plotted. Since the log-likelihood increment distributions are symmetric in both examples, \(m^*\) is symmetric about zero. Therefore, we only plot \(m^*\) for \(\log z \geq 0\). Moreover, in the Bernoulli example, the log-likelihood ratio only takes integer values, so we only plot \(m^*\) at these.

By inspection, \(m^*\) is approximately linear in \(\log z\) in both cases. This is expected in light of the discussion in the previous sections. For comparison, we also show the optimal single-randomization sample size, \(b_1^*(z, 1)\), and the two approximations proposed in Section 6. Since the approximation in 25 is exact in the Gaussian example, the approximate upper bound coincides with \(b_1^*(z, 1)\) in the plot on the right. In the Bernoulli example, the approximation is no longer exact but slightly differs from \(b_1^*(z, 1)\). In general, the approximations are useful in the two examples considered here. Especially for larger \(\log z\), the optimal \(m^*\) is located well within the cone spanned by the two approximate bounds. In fact, the mid-point between the two bounds provides a good approximation of \(m^*\) for a large range of log-likelihood ratio values.

Interestingly, it can be seen in the magnified inset on the right that there is a small interval around \(\ln z = 1.5\) on which \(m^*\) exceeds both \(b_1^*(z, 1)\) and the corresponding approximation. However, at this point, we cannot say with certainty if this is really a counterexample or merely a numerical artifact. In general, the question of whether \(b_k^*(z, c)\) is monotonic in \(k\) arguably warrants closer inspection.

7.3 Properties of the NPKWT↩︎

In this section, we study selected properties of the NPKWT in more detail. First, the sum error probability of an NPKWT for the hypotheses in 30 and 31 is plotted as a function of the number of allowed randomization uses in Fig. 4. Again, we used \(c = 20\) for the Bernoulli example and \(c = 10\) for the Gaussian example. For the Bernoulli example, it can be seen that the sum error probability decreases from approximately \(0.13\) for \(k = 0\) to approximately \(0.11\) for \(k = 10\). This is a non-negligible reduction of approximately 15.4 % and highlights the potential usefulness of the NPKWT in practice. In the Gaussian example, the sum error probability decreases from approximately \(0.114\) for \(k = 0\) to approximately \(0.106\) for \(k = 10\). This is a reduction of approximately 12.3 %, which is less significant, but still noteworthy.

For reference, the sum error probabilities of two FSSTs are plotted for sample sizes \(c\) and \(c + 1\). For \(k = 0\), the NPKWT reduces to the FSST and its error probabilities match. Interestingly, while the FSST with a sample size of \(c + 1\) achieves a lower sum error probability than the NPKWT in the Gaussian example, this is not the case in the Bernoulli example. This disproves a conjecture we had at an early stage of this work, namely, that \(\rho_0(z, c) \leq \rho(z,c) \leq \rho_0(z, c+1)\). Clearly, the second bound does not hold in general. However, some insights could be gained from investigating conditions under which it does.

Fig.5 shows (right-truncated) histograms of the stopping times of the two NPKWTs with \(z = 1\) under the respective null hypotheses. Again, we used \(c = 20\) for the Bernoulli example and \(c = 10\) for the Gaussian example. The depicted results are based on \(10^5\) Monte Carlo simulations. Both stopping time distributions are approximately of the same shape, with a single mode just below the targeted expected sample size and a pronounced right tail. Interestingly, while the NPKWT in the Gaussian example can stop at any time, its counterpart in the Bernoulli example has a minimum sample size of six. This is a consequence of the bounded log-likelihood ratio increments under the Bernoulli hypotheses. It takes at least six samples to reach a log-likelihood ratio value that is large in comparison to the remaining number of samples.

Selected summary statistics of the two stopping time histograms in Fig. 5 are given in Table 1. Arguably, the one statistic that stands out is the maximum stopping time observed over \(10^5\) Monte Carlo runs, which is well over 2000 samples in both cases. On the one hand, this illustrates the fact that, despite having a bounded expected sample size, the NPKWT is untruncated in general and can, in principle, use arbitrarily many samples for any individual run. On the other hand, for sample sizes of this order the magnitude of the log-likelihood ratio becomes extremely large and numerical issues can arise when evaluating \(\rho\) and \(m^*\). Therefore, we urge the reader to take the exact numbers with a grain of salt.

Histograms of the number of randomization uses by the NPKWT are shown in Fig. 6. Selected summary statistics of these histograms are given in Table 2. By inspection, most instances of the NPKWT stop after at most three randomization uses in the Bernoulli case and two randomization uses in the Gaussian case. This observation confirms that in most instances a small number of randomized stopping decisions are sufficient to implement the NPKWT. However, the histograms also show large variances and significant right tails, again highlighting the untruncated nature of the NPKWT. As before, the maxima given in Table 2, especially in the Gaussian case, should be interpreted with caution as they could be affected by numerical noise.

We conclude this section with an illustration of the stopping policy of the NPKWT for two specific sequences of observations. First, consider the NPKWT for the hypotheses in 31 , and assume that \(z = 1\) and \(c = 20\). If \(x_t = \frac{1}{2}\) for all \(t \geq 1\), the observations do not provide any information about the true hypothesis, and the likelihood ratio remains constant, namely, \(z_t = z = 1\) for all \(t \geq 1\). In turn, \(m^*(z_t) = m^*(1) = 1\) for all \(t \geq 1\). Using the update rules in Theorem 4, the test simply decrements \(c_t\) after each sample and stops when \(c_t = 0\). That is, the NPKWT reduces to an FSST with \(c = 20\) samples. This is an example of how the NPKWT avoids large stopping times in scenarios where a conventional SPRT breaks down because the observations do not provide sufficient evidence to cross a decision threshold.

Next, consider the NPKWT for the hypotheses in 30 , and assume that \(z = 1\) and \(c = 10\). If \(x_t = 1\) for all \(t \geq 1\), the observations all point toward the alternative hypothesis, and the likelihood ratio is monotonically increasing, namely, \(z_t = 2^t\). The resulting sequence of continuation probabilities is shown in Table 3. In this example, randomization starts after three samples, and the structure of the randomization rule in 20 is reflected in these probabilities: for \(t \geq 3\), the continuation probabilities are of the form \(\tfrac{m^*(2^{t-1}) - 1}{m^*(2^t)}\). Interestingly, the continuation probability approaches \(1\) as the evidence for \(\mathcal{H}_1\) increases. This might seem counterintuitive, but is in line with the discussion in the previous section: since \(m^*\) is approximately linear in \(\log z\), the absolute increment in expected remaining sample size after each likelihood ratio update, \(c_t - c_{t-1}\), is approximately constant. However, relative to \(c_t\), this increment, and in turn the stopping probability, tends to zero. This illustrates how the NPKWT can delay stopping in cases where the observations are highly informative, and helps to understand the extremely large sample sizes observed in our experiments.

8 Conclusion and Outlook↩︎

In this paper, we have formulated and solved the nonparametric Kiefer–Weiss problem. The corresponding sequential test has been shown to rely heavily on randomized stopping rules, and the optimal randomization to be defined by a function that maps the current likelihood ratio to a minimal number of expected remaining samples. The properties of the optimal test have been further explored and illustrated with numerical examples.

Questions left open in the paper include:

• Can the gain of the NPKWT over the FSST be bounded? For example, is there a constant \(\Delta\), possibly dependent on \(P_0\) and \(P_1\), such that \(\rho(z,c) \leq \rho_0(z, c + \Delta)\)?

• What can be said about the stopping time distribution of the NPKWT under a given sample distribution \(\mathbf{P}\)?

• Is the optimal sample size \(b_k^*(z, c)\) in 15 monotonic in \(k\)?

Another possible research direction is to investigate the properties of the NPKWT for vanishing error probabilities, or, equivalently, for \(c \to \infty\). Although this topic has not been addressed in this paper, we conjecture that in this asymptotic regime the optimal stopping rules simplify significantly, possibly to a variation of Approximation 6. However, we expect a formal proof to be non-trivial, as it needs to take the dynamics of \(c_t\) into account. Even for large initial values \(c_0\), the NPKWT can, in principle, re-enter a non-asymptotic regime as the test progresses.

Finally, we would like to emphasize that the NPKWT is not only of theoretical interest, but can be an attractive choice in practice as well. In contrast to conventional KWTs, which often have time-dependent or two-dimensional thresholds and require substantial computation, the NPKWT is essentially an augmented SPRT. Moreover, as discussed before, it is robust against deviations from the optimal mapping \(m^*\), so that, in practice, approximate stopping policies such as the ones proposed in Section 6 can be used with minimal computational overhead. Therefore, we encourage interested researchers and practitioners to identify and investigate potential applications.

9 Proof of Theorem 1↩︎

Assume that \(\psi\) satisfies the condition in 7 . It then holds that \[\mathbb{E}_{\mathbf{P}, \psi}\bigl[ T \bigr] = \mathbb{E}_{\mathbf{P}}\bigl[ \mathbb{E}_\psi[ T \,|\, \boldsymbol{X}] \bigr] = \mathbb{E}_{\mathbf{P}}\bigl[ \tau(\boldsymbol{X}) \bigr] \leq \mathbb{E}_{\mathbf{P}}[\, c \,] = c,\] so that \(\psi\) also satisfies the condition in 5 . Now assume that \(\psi\) violates the condition in 7 . In this case, there exists at least one sequence \(\tilde{\boldsymbol{x}}\) for which \[\mathbb{E}_\psi\bigl[ \tau(\tilde{\boldsymbol{x}}) \bigr] > c.\] This implies that \[\mathbb{E}_{\boldsymbol{1}_{\tilde{\boldsymbol{x}}}, \psi}\bigl[\, T \,\bigr] = \mathbb{E}_{\psi}\bigl[\, T \,|\, \boldsymbol{X} = \tilde{\boldsymbol{x}} \,\bigr] = \mathbb{E}_{\psi}\bigl[\, \tau(\tilde{\boldsymbol{x}}) \,\bigr] > c,\] where \(\boldsymbol{1}_{\boldsymbol{x}} \in \mathcal{M}(\mathcal{X}^\infty)\) denotes a unit point mass on \(\boldsymbol{x}\). Therefore, \(\psi\) also violates the condition in 5 . This completes the proof.

10 Proof of Theorem 2↩︎

By conditioning on the stopping time we obtain \[\begin{align} \alpha(\psi, \delta) + & z \, \beta(\psi, \delta) \notag \\ &= \mathbb{E}_{0, \psi, \delta}\bigl[ D \bigr] + z \, \mathbb{E}_{1, \psi, \delta}\bigl[ 1 - D \bigr] \notag \\ &= \sum_{t=0}^\infty \Bigl( \mathbb{E}_{0, \delta}\bigl[ D \,|\, T = t \bigr] \mathbb{P}_{0, \psi}\bigl[ T = t \bigr] + z \, \mathbb{E}_{1, \delta}\bigl[ 1 - D \,|\, T = t \bigr] \mathbb{P}_{1, \psi}\bigl[ T = t \bigr] \Bigr). \label{eq:err95t} \end{align}\tag{34}\] Additionally conditioning on the observed sequence yields \[\begin{align} \mathbb{E}_{0, \delta}\bigl[ D \,|\, T = t \bigr] & \mathbb{P}_{0, \psi}\bigl[ T = t \bigr] \notag \\ &= \int_{\mathcal{X}^t} \mathbb{E}_{0, \delta}\bigl[ D \,|\, T = t, \boldsymbol{X}_t = \boldsymbol{x}_t \bigr] \mathbb{P}_{0, \psi}\bigl[ T = t \,|\, \boldsymbol{X}_t = \boldsymbol{x}_t \bigr] \prod_{n=1}^t p_0(x_n) \, \mathrm{d}\boldsymbol{x}_t \notag \\ &= \int_{\mathcal{X}^t} \delta_t(\boldsymbol{x}_t) \phi_t(\boldsymbol{x}_t) \prod_{n=1}^t p_0(x_n) \, \mathrm{d}\boldsymbol{x}_t \label{eq:err95t950} \end{align}\tag{35}\] and \[\begin{align} \mathbb{E}_{1,\delta}\bigl[ 1 &- D \,|\, T = t \bigr] \mathbb{P}_{1, \psi}\bigl[ T = t \bigr] \notag \\ &= \int_{\mathcal{X}^t} \mathbb{E}_{1,\delta}\bigl[ 1 - D \,|\, T = t, \boldsymbol{X}_t = \boldsymbol{x}_t \bigr] \mathbb{P}_{1,\psi}\bigl[ T = t \,|\, \boldsymbol{X}_t = \boldsymbol{x}_t \bigr] \prod_{n=1}^t p_1(x_n) \, \mathrm{d}\boldsymbol{x}_t \notag \\ &= \int_{\mathcal{X}^t} (1 - \delta_t(\boldsymbol{x}_t)) \phi_t(\boldsymbol{x}_t) \prod_{n=1}^t p_1(x_n) \, \mathrm{d}\boldsymbol{x}_t, \label{eq:err95t951} \end{align}\tag{36}\] with \(\phi_t\) and \(\delta_t\) defined in 3 and 2 , respectively. Substituting 35 and 36 back into 34 yields the following lower bound: \[\begin{align} \alpha(\psi, \delta) + &z \, \beta(\psi, \delta) \\ &= \sum_{t=0}^\infty \int_{\mathcal{X}^t} \delta_t(\boldsymbol{x}_t) \phi_t(\boldsymbol{x}_t) \prod_{n=1}^t p_0(x_n) + z (1 - \delta_t(\boldsymbol{x}_t)) \phi_t(\boldsymbol{x}_t) \prod_{n=1}^t p_1(x_n) \, \mathrm{d}\boldsymbol{x}_t \\ &\geq \sum_{t=0}^\infty \int_{\mathcal{X}^t} \min\biggl\{ \prod_{n=1}^t p_0(x_n) \,,\, z \prod_{n=1}^t p_1(x_n) \biggr\} \phi_t(\boldsymbol{x}_t) \, \mathrm{d}\boldsymbol{x}_t \\ &= \sum_{t=0}^\infty \int_{\mathcal{X}^t} \min\biggl\{ 1 \,,\, z \prod_{n=1}^t \frac{p_1(x_n)}{p_0(x_n)} \biggr\} \phi_t(\boldsymbol{x}_t) \, \prod_{s=1}^t p_0(x_s) \mathrm{d}\boldsymbol{x}_t \\ &= \sum_{t=0}^\infty \mathbb{E}_{0, \psi}\biggl[ g\biggl(z \prod_{n=1}^t \frac{p_1(X_n)}{p_0(X_n)} \biggr) \phi_t(\boldsymbol{X}_t) \biggr] \\ &= \mathbb{E}_{0, \psi}\Biggl[ \sum_{t=0}^\infty g\biggl(z \prod_{n=1}^t \frac{p_1(X_n)}{p_0(X_n)} \biggr) \phi_t(\boldsymbol{X}_t) \Biggr] \\ &= \mathbb{E}_{0, \psi}\Biggl[ g\biggl(z \prod_{t=1}^T \frac{p_1(X_t)}{p_0(X_t)} \biggr) \Biggr], \end{align}\] where in the second-to-last step summation and expectation can be interchanged since all summands are non-negative Folland1999?. The lower bound is attained if and only if \(\delta_t\) is of the form 8 in Theorem 2. This completes the proof.

11 Proof of Lemma 1↩︎

The problem in 10 can be reparametrized in terms of the conditional distribution of the stopping time: \[\inf_{\phi \in \mathcal{S}} \, \mathbb{E}_0\Biggl[\sum_{t=0}^\infty Y_t(\boldsymbol{X}_t) \phi_t(\boldsymbol{X}_t) \Biggr] \quad \text{s.t.} \quad \sum_{t=0}^\infty t \, \phi_t(\boldsymbol{x}_t) \leq c \quad \forall \boldsymbol{x} \in \mathcal{X}^\infty, \label{eq:constrained95optimal95stopping}\tag{37}\] where \(\mathcal{S}\) denotes the space of stopping time distributions and \[Y_t(\boldsymbol{X}_t) \coloneq g\biggl( z \prod_{n=1}^t \frac{p_1(X_n)}{p_0(X_n)} \biggr).\] In a nutshell, the existence of a minimizer follows from the fact that 37 is a well-defined optimal stopping problem: The cost, \(Y_t\), is non-negative and bounded for all \(t \geq 0\), and both the objective and the constraints are linear in \(\phi\).

More formally, we need to show that the set of feasible stopping time distributions is compact and that the objective function is lower-semiconscious. Existence of a minimizer then follows from the extreme value theorem Aliprantis2007?.

The seminal work on compactness of stopping times is due to Baxter and Chacon who identified the appropriate topology Baxter1977?. All statements made in what follows hold in the Baxter-Chacon (BC) topology.

A formal proof proceeds as follows:

1. The space of discrete-time stopping time distributions, \(\mathcal{S}\), is sequentially compact Edgar1982?.

2. Define the sequence of functions \((f_n)_{n \geq 0}\) as \[f_n(\phi) \coloneq \sum_{t=0}^n t \, \phi_t(\boldsymbol{x}_t).\] For all \(n \geq 0\), the function \(f_n\) is linear and bounded and, therefore Conway1994?, continuous in \(\phi\). Moreover, since \(t \, \phi_t \geq 0\) for all \(t \geq 0\), the sequence \((f_n)_{n \geq 0}\) is non-decreasing so that \[\sum_{t=0}^\infty t \, \phi_t(\boldsymbol{x}_t) = \sup_{n \geq 0} f_n(\phi).\] Since the supremum of continuous functions is lower semicontinuous Aliprantis2007?, this implies that the constraint function in 37 is lower semicontinuous.

3. By Rudin1987?, sublevel sets of lower semicontinuous functions are closed. Moreover, arbitrary intersections of closed sets are closed Munkres1974?, and closed subsets of compact sets are compact Rudin1976?. It follows that the subset of \(\mathcal{S}\) defined by the constraints in 37 is compact.

4. Since \(Y_t \geq 0\) for all \(t \geq 0\), it follows from Fatou’s lemma Rudin1976? that the objective function in 37 is lower semicontinuous.

This concludes the proof.

12 Proof of Lemma 2↩︎

To show the first statement, let \(\gamma \in [0, 1]\) and \(z_1, z_2 \geq 0\). For all \(k \geq 0\) it holds that \[\begin{align} \rho_k(\gamma z_1 + (1 - \gamma) z_2, c) &= \inf_{\psi \in \mathcal{I}_{c,k}^\infty} \alpha(\psi) + (\gamma z_1 + (1 - \gamma) z_2) \beta(\psi) \\ &= \inf_{\psi \in \mathcal{I}_{c,k}^\infty} \gamma \bigl( \alpha(\psi) + z_1 \beta(\psi) \bigr) + (1 - \gamma) \bigl( \alpha(\psi) + z_2 \beta(\psi) \bigr) \\ &\geq \gamma \inf_{\psi \in \mathcal{I}_{c,k}^\infty} \alpha(\psi) + z_1 \beta(\psi) + (1 - \gamma) \inf_{\psi \in \mathcal{I}_{c,k}^\infty} \alpha(\psi) + z_2 \beta(\psi) \\ &= \gamma \rho_k(z_1, c) + (1 - \gamma) \rho_k(z_2, c). \end{align}\] This proves that \(\rho_k\) is concave in \(z\). Now, assume that \(z_2 > z_1\). Since \(\alpha\) and \(\beta\) are non-negative \[\alpha(\psi) + z_2 \, \beta(\psi) \geq \alpha(\psi) + z_1 \, \beta(\psi)\] for any stopping policy \(\psi\). Taking the infimum over \(\mathcal{I}_{c,k}^\infty\) on both sides yields \[\begin{align} \inf_{\psi \in \mathcal{I}_{c,k}^\infty} \alpha(\psi) + z_2 \, \beta(\psi) &\geq \inf_{\psi \in \mathcal{I}_{c,k}^\infty} \alpha(\psi) + z_2 \, \beta(\psi) \\ \rho_k(z_2, c) &\geq \rho_k(z_1, c). \end{align}\]

Finally, since \(\rho_k(z, c)\) is non-increasing in \(c\), it holds that \[\rho_k(z, c) \leq \rho_k(z, 0) = \mathbb{E}_0\biggl[ g\biggl(z \prod_{n=1}^0 \frac{p_1(X_n)}{p_0(X_n)} \biggr) \biggr] = g(z).\] This completes the proof.

13 Proof of Lemma 4↩︎

Consider the problem of choosing the initial stopping probability, \(\psi_0\), of a test with stopping policy \(\psi \in \mathcal{I}_{c,k}^\infty\). Conceptually speaking, we can distinguish between three cases:

1. Stop with certainty and make a decision (\(\psi_0 = 1\)).

2. Continue with certainty and save all \(k\) randomization uses for later (\(\psi_0 = 0\)).

3. Use a randomized stopping rule and either stop, or continue with a policy that allows for at most \(k-1\) randomization uses (\(0 < \psi_0 < 1\)).

The optimal choice is then the one that minimizes the expected cost. In order to formalize this argument, we define \[\rho_k(z, c \,|\, \psi_0 = \eta) \coloneq \inf_{(\eta, \psi_{1:\infty}) \in \mathcal{I}_{c,k}^\infty} \; \mathbb{E}_{0, \psi}\Biggl[ g\biggl( z \prod_{n=1}^T \frac{p_1(X_n)}{p_0(X_n)} \biggr) \,\bigg|\, \psi_0 = \eta \Biggr],\] where \(\psi_{1:\infty}\) is shorthand for the sequence \((\psi_1, \psi_2, \ldots)\). First, assume that \(\psi_0 = 1\), that is, the test stops with certainty before taking the first sample. In this case, \(\phi_0 = 1\) and \[\rho_k(z, c \,|\, \psi_0 = 1) = \mathbb{E}_0\Biggl[ g\biggl( z \prod_{n=1}^0 \frac{p_1(X_n)}{p_0(X_n)} \biggr) \Biggr] = g(z). \label{eq:rho95k951}\tag{38}\] Next, assume that \(\psi_0 = 0\), that is, the test takes the first sample with certainty. Note that this choice is only feasible if \(c \geq 1\). In this case \[\begin{align} \rho_k(z, c \,|\, \psi_0 = 0) &= \inf_{(0, \psi_{1:\infty}) \in \mathcal{I}_{c,k}^\infty} \; \mathbb{E}_{0, \psi}\Biggl[ g\biggl(z \prod_{n=1}^T \frac{p_1(X_n)}{p_0(X_n)} \biggr) \,\bigg|\, \psi_0 = 0 \Biggr] \notag \\ &= \inf_{(0, \psi_{1:\infty}) \in \mathcal{I}_{c,k}^\infty} \; \mathbb{E}_0\Biggl[ \mathbb{E}_{0, \psi}\Biggl[ \sum_{t=1}^\infty g\biggl(z \prod_{n=1}^T \frac{p_1(X_n)}{p_0(X_n)} \biggr) \,\bigg|\, \psi_0 = 0, X_1 \Biggr] \Biggr] \notag \\ &= \mathbb{E}_0\Biggl[ \inf_{(0, \psi_{1:\infty}) \in \mathcal{I}_{c,k}^\infty} \; \mathbb{E}_{0, \psi}\Biggl[ \sum_{t=1}^\infty g\biggl( z\frac{p_1(X_1)}{p_0(X_1)} \prod_{n=2}^T \frac{p_1(X_n)}{p_0(X_n)} \biggr) \,\bigg|\, \psi_0 = 0, X_1 \Biggr] \Biggr], \label{eq:rho95k95095intermediate} \end{align}\tag{39}\] where in the last step expectation and minimization can be interchanged since all \(\psi_t\), \(t \geq 1\) are measurable functions of \(X_1\), that is, the infimum can be taken pointwise—compare Rockafellar2009?. Now, let \(\boldsymbol{X}'\) and \(\psi'\) denote shifted versions of \(\boldsymbol{X}\) and \(\psi\), respectively. More specifically, we define \(X'_t \coloneq X_{t+1}\) and \(\psi'_t \coloneq \psi_{t+1}\) for all \(t \geq 0\). By construction, it holds that \(\psi' \in \mathcal{I}_{c-1,k}^\infty\). This follows since \(\psi \in \mathcal{I}_{c,k}^\infty\) and \[\begin{align} \mathbb{E}_{(0, \psi_{1:\infty})}[\tau(\boldsymbol{x})] &= \sum_{t=1}^\infty t \, \phi_t(\boldsymbol{x}_t) \\ &= \sum_{t=0}^\infty (t + 1) \, \phi'_t(\boldsymbol{x}'_t) \\ &= \sum_{t=0}^\infty t \, \phi'_t(\boldsymbol{x}'_t) + \sum_{t=0}^\infty \phi'_t(\boldsymbol{x}'_t) \\ &= \mathbb{E}_{\psi'}[\tau(\boldsymbol{x})] + 1, \end{align}\] where \(\phi'_t\) is shorthand for \(\phi_t\) in 3 evaluated at \(\psi = \psi'\). The inner minimization in 39 can now be written as \[\begin{align} \inf_{(0, \psi_{1:\infty}) \in \mathcal{I}_{c,k}^\infty} & \mathbb{E}_{0, \psi}\Biggl[ \sum_{t=1}^\infty g\biggl( z\frac{p_1(X_1)}{p_0(X_1)} \prod_{n=2}^T \frac{p_1(X_n)}{p_0(X_n)} \biggr) \,\Big|\, \psi_0 = 0, X_1 \Biggr] \notag \\ &= \inf_{(0, \psi_{1:\infty}) \in \mathcal{I}_{c,k}^\infty} \mathbb{E}_{0, \psi}\Biggl[ \sum_{t=1}^\infty g\biggl( z\frac{p_1(X_1)}{p_0(X_1)} \prod_{n=2}^{t} \frac{p_1(X_n)}{p_0(X_n)} \biggr) \phi_t(\boldsymbol{X}_t) \,\Big|\, \psi_0 = 0, X_1 \biggr] \notag \\ &= \inf_{\psi' \in \mathcal{I}_{c-1, k}^\infty} \mathbb{E}_{0, \psi'}\Biggl[ \sum_{t=0}^\infty g\biggl( z\frac{p_1(X'_0)}{p_0(X'_0)} \prod_{n=1}^t \frac{p_1(X'_n)}{p_0(X'_n)} \biggr) \phi'_t(\boldsymbol{X}'_t) \,\Big|\, X'_0 \Biggr] \notag \\ &= \inf_{\psi' \in \mathcal{I}_{c-1, k}^\infty} \mathbb{E}_{0, \psi'}\Biggl[ g\biggl( z\frac{p_1(X'_0)}{p_0(X'_0)} \prod_{n=1}^T \frac{p_1(X'_n)}{p_0(X'_n)} \biggr) \,\Big|\, X'_0 \Biggr] \notag \\ &= \rho_k\biggl( z \frac{p_1(X'_0)}{p_0(X'_0)}, c - 1\biggr) \notag \\ &= \rho_k\biggl( z \frac{p_1(X_1)}{p_0(X_1)}, c - 1\biggr). \label{eq:rho95k95095conditioned} \end{align}\tag{40}\] Substituting 40 back into 39 and making the restriction to \(c \geq 1\) explicit yields \[\rho_k(z, c \,|\, \psi_0 = 0) = \begin{dcases} \mathbb{E}_0\biggl[\rho_k\biggl( z \frac{p_1(X)}{p_0(X)}, c - 1\biggr)\biggr], & c \geq 1, \\[2pt] \text{undefined}, & c < 1, \end{dcases} \label{eq:rho95k950}\tag{41}\] where we dropped the index of \(X\) since all \(X_t\) are i.i.d.

Finally, assume that \(\eta \in (0,1)\), that is, the test stops with probability \(\eta\) and continues with probability \(1 - \eta\). In this case, the conditional cost is a mixture of the form \[\eta \, g(z) + (1 - \eta) \, \mathbb{E}_0\biggl[\rho_{k-1}\biggl(z \frac{p_1(X)}{p_0(X)}, b - 1 \biggr)\biggr], \label{eq:rho95k95eta95b}\tag{42}\] with \(b \geq 1\). To see this, consider the following. If the test stops, 38 holds and the resulting cost is \(g(z)\). If the test continues, the arguments leading to 41 apply, but with two key differences: first, the expected sample size of the test conditioned on \(S_0 = 0\) can exceed \(c\), as long as the unconditional expected sample size is bounded by \(c\); second, the number of remaining randomization uses for \(t \geq 1\) reduces to \(k - 1\). In combination, this means that \(\psi' \in \mathcal{I}_{b-1, k-1}\), where \(b\) is a free variable. Substituting \(\psi' \in \mathcal{I}_{b-1, k-1}\) for \(\psi' \in \mathcal{I}_{c-1, k}\) in the steps leading to 40 yields the expected cost of continuing in 42 .

We now establish the feasible region for \(\eta\) and \(b\). First, it trivially needs to hold that \(b \geq 1\) since continuing the test implies taking at least one more sample. Moreover, in order for \((\eta, \psi_{1:\infty}) \in \mathcal{I}_{c,k}^\infty\), it needs to hold that \[\begin{align} \mathbb{E}_{(\eta, \psi_{1:\infty})}\bigl[\tau(\boldsymbol{x})\bigr] &\leq c \\ \eta \, \mathbb{E}_{\psi_{1:\infty}}\bigl[\tau(\boldsymbol{x}) \,|\, S_0 = 1 \bigr] + (1 - \eta) \, \mathbb{E}_{\psi_{1:\infty}}\bigl[\tau(\boldsymbol{x}) \,|\, S_0 = 0 \bigr] &\leq c \\ \eta \, 0 + (1 - \eta) \, \bigl(1 + \mathbb{E}_{\psi'}\bigl[\tau(\boldsymbol{x}')\bigr] \bigr) &\leq c\\ \mathbb{E}_{\psi'}\bigl[\tau(\boldsymbol{x}')\bigr] &\leq \frac{c}{1 - \eta} - 1 \end{align}\] for all \(\boldsymbol{x} \in \mathcal{X}^\infty\), where \(\boldsymbol{x}'\) and \(\psi'\) are as defined above. Since \(\psi' \in \mathcal{I}_{b-1, k-1}^\infty\), this implies \[b \leq \frac{c}{1 - \eta}. \label{eq:b95of95eta}\tag{43}\] In order to determine the optimal \(b\), it is useful to treat the cases \(c < 1\) and \(c \geq 1\) separately. First, assume that \(c \geq 1\). In this case, minimizing the expression in 42 over \(b\) yields \[\begin{align} \rho_k(z, c \,|\, \psi_0 = \eta) &= \inf_{1 \leq b \leq \frac{c}{1 - \eta}} \, \eta \, g(z) + (1 - \eta) \, \mathbb{E}_0\biggl[\rho_{k-1}\biggl(z \frac{p_1(X)}{p_0(X)}, b - 1 \biggr)\biggr] \notag \\ &= \eta \, g(z) + (1 - \eta) \, \mathbb{E}_0\biggl[\rho_{k-1}\biggl(z \frac{p_1(X)}{p_0(X)}, \frac{c}{1 - \eta} - 1 \biggr)\biggr] \label{eq:rho95k95eta95min95c95large} \end{align}\tag{44}\] where the second equality holds since \(\rho_{k-1}(z, c)\) is non-increasing in \(c\)—see Lemma 2.

Now assume that \(c < 1\). In this case, the right-hand side of 43 needs to be larger than or equal to one in order for any feasible \(b\) to exist: \[\rho_k(z, c \,|\, \psi_0 = \eta) = \begin{dcases} \eta \, g(z) + (1 - \eta) \, \mathbb{E}_0\biggl[\rho_{k-1}\biggl(z \frac{p_1(X)}{p_0(X)}, \frac{c}{1 - \eta} - 1 \biggr)\biggr], & \frac{c}{1-\eta} \geq 1 \\ \text{undefined}, & \frac{c}{1-\eta} < 1 \end{dcases} \label{eq:rho95k95eta95min95c95small}\tag{45}\] The expressions in 44 and 45 can be combined by parametrizing them as follows: \[\begin{align} \rho_k\Bigl(z, c \,\Big|\, \psi_0 = 1 - \frac{c}{b}\Bigr) &= \Bigl(1 - \frac{c}{b} \Bigr) \, g(z) + \frac{c}{b} \, \mathbb{E}_0\biggl[\rho_{k-1}\biggl(z \frac{p_1(X)}{p_0(X)}, b - 1 \biggr)\biggr] \notag \\ &= g(z) - c \, \frac{g(z) - \mathbb{E}_0\Bigl[\rho_{k-1}\Bigl(z \frac{p_1(X)}{p_0(X)}, b - 1 \Bigr)\Bigr]}{b}, \label{eq:rho95k95eta} \end{align}\tag{46}\] where \(b \geq 1\) if \(c < 1\) and \(b > c\) if \(c \geq 1\).

The result in the lemma can now be obtained by combining 38 , 41 and 46 . First, assume that \(c < 1\). In this case, it holds that \[\begin{align} \rho_k(z, c) &= \inf_{\eta \in (0,1]} \rho_k(z, c \,|, \psi_0 = \eta) \\ &= \min\Bigl\{ \, \inf_{b \geq 1} \rho_k\Bigl(z, n \,|\, \psi_0 = 1 - \frac{c}{b}\Big) \,,\, \rho_k(z, n \,|\, \psi_0 = 1) \Bigr\} \\ &= \min\biggl\{\, \inf_{b \geq 1} g(z) - c \, \frac{g(z) - \mathbb{E}_0\bigl[\rho_{k-1}\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1 \bigr)\bigr]}{b} \,,\, g(z) \biggr\} \\ &= g(z) - c \, \sup_{b \geq 1} \frac{g(z) - \mathbb{E}_0\bigl[\rho_{k-1}\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1 \bigr)\bigr]}{b}, \end{align}\] where we used the fact that \(\lim_{b \to \infty} \rho_k\bigl(z, c \,\big|\, \psi_0 = 1 - \frac{c}{b}\bigr) = \rho_k(z, c \,|\, \psi_0 = 1) = g(z)\) so that the case \(\psi_0 = 1\) does not need to be treated separately. For \(c \geq 1\) it holds that \[\begin{align} \rho_k(z, c) &= \inf_{\eta \in [0,1]} \rho_k(z, c \,|, \psi_0 = \eta) \notag \\ &= \min\Bigl\{ \rho_k(z, n \,|\, \psi_0 = 0) \,,\, \inf_{b > c} \rho_k\Bigl(z, n \,|\, \psi_0 = 1 - \frac{c}{b}\Big) \,,\, \rho_k(z, n \,|\, \psi_0 = 1) \Bigr\} \notag \\ &= \min\biggl\{ \mathbb{E}_0\biggl[\rho_k\biggl( z \frac{p_1(X)}{p_0(X)}, c - 1\biggr)\biggr] \,,\, \notag \\ &\inf_{b > c} g(z) - c \, \frac{g(z) - \mathbb{E}_0\bigl[\rho_{k-1}\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1 \bigr)\bigr]}{b} \,,\, g(z) \biggr\} \notag \\ &= \min\biggl\{\mathbb{E}_0\biggl[\rho_k\biggl( z \frac{p_1(X)}{p_0(X)}, c - 1\biggr)\biggr] \,,\, \notag \\ &g(z) - c \, \sup_{b > c} \frac{g(z) - \mathbb{E}_0\bigl[\rho_{k-1}\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1 \bigr)\bigr]}{b} \biggr\}, \label{eq:rho95k95195inf} \end{align}\tag{47}\] where again the case \(\psi_0 = 1\) is included via the limit \(b \to \infty\).

It remains to show that the supremum is attained at a finite maximizer, and that \(c\) can be included in the maximization domain in 47 . To see that a finite maximizer exists, note that \[g(z) - \mathbb{E}_0\biggl[\rho_{k-1}\biggl(z \frac{p_1(X)}{p_0(X)}, b - 1 \biggr)\biggr] \geq \rho_{k-1}(z, 0) - \rho_{k-1}(z, b - 1 \bigr) \geq 0\] for all \(b \geq 1\). Here, the first inequality follows from Jensen’s inequality together with the fact that \(\rho_k(\bullet , c)\) is concave, and the second holds since \(\rho_k(z , \bullet)\) is non-increasing. However, \[\lim_{b \to \infty} \, \frac{g(z) - \mathbb{E}_0\bigl[\rho_{k-1}\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1 \bigr)\bigr]}{b} \leq \lim_{b \to \infty} \, \frac{g(z)}{b} = 0.\] To see that \(c\) can be included in the maximization domain in 47 , note that \[\begin{align} g(z) - c \, \frac{g(z) - \mathbb{E}_0\bigl[\rho_{k-1}\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1 \bigr)\bigr]}{b} \bigg\rvert_{b = c} &= \mathbb{E}_0\biggl[\rho_{k-1}\biggl(z \frac{p_1(X)}{p_0(X)}, c - 1 \biggr)\biggr] \\ &\geq \mathbb{E}_0\biggl[\rho_k\biggl(z \frac{p_1(X)}{p_0(X)}, c - 1 \biggr)\biggr], \end{align}\] where the last inequality holds since \(\rho_k\) is non-increasing in \(k\). This completes the proof.

14 Proof of Lemma 6↩︎

Taking the limit \(k \to \infty\) on both sides of 13 yields \[\medmuskip=-1mu \thickmuskip=0mu \rho(z, c) = \begin{dcases} g(z) - c \, \max_{b \geq 1} \, \frac{g(z) - \mathbb{E}_0\bigl[\rho\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1\bigr) \bigr]}{b}, & c < 1, \\ \min\biggl\{\mathbb{E}_0\biggl[\rho\biggl( z \frac{p_1(X)}{p_0(X)}, c - 1\biggr)\biggr] \,,\, g(z) - c \, \max_{b \geq c} \frac{g(z) - \mathbb{E}_0\bigl[\rho\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1\bigr) \bigr]}{b} \biggr\}, & c \geq 1. \end{dcases} \label{eq:rho95limit95recursive}\tag{48}\] Since \[g(z) - c \, \frac{g(z) - \mathbb{E}_0\bigl[\rho\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1\bigr) \bigr]}{b} \biggr|_{b=c} = \mathbb{E}_0\biggl[\rho\biggl(z \frac{p_1(X)}{p_0(X)}, c - 1\biggr) \biggr],\] the outer minimum in the case \(c \geq 1\) can be omitted and \(\rho\) can be written as \[\rho(z, c) = \begin{dcases} g(z) - c \, \max_{b \geq 1} \, \frac{g(z) - \mathbb{E}_0\bigl[\rho\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1\bigr) \bigr]}{b}, & c < 1, \\ g(z) - c \, \max_{b \geq c} \frac{g(z) - \mathbb{E}_0\bigl[\rho\bigl(z \frac{p_1(X)}{p_0(X)}, b - 1\bigr) \bigr]}{b}, & c \geq 1. \end{dcases}\] Combining both cases and rearranging the terms yields 17 . This completes the proof.

15 Proof of Lemma 7↩︎

The first statement in the lemma follows directly from the definition of \(\rho\). In order to show convexity, let \(c_1, c_2 \geq 0\) with \(c_2 > c_1\), and let \(\psi_1^* \in \mathcal{I}_{c_1}^\infty\) and \(\psi_2^* \in \mathcal{I}_{c_2}^\infty\) be optimal in the sense of 10 for \(c = c _1\) and \(c = c_2\), respectively. Now, consider the mixed stopping policy \[\psi^{**} = \gamma \psi_1^* + (1-\gamma) \psi_2^*, \label{eq:mixed95policy}\tag{49}\] where \(\gamma \in [0,1]\). 49 has to be read in the sense that a test under \(\psi^{**}\) uses policy \(\psi_1^*\) with probability \(\gamma\) and policy \(\psi_2^*\) with probability \((1 - \gamma)\). By construction, it holds that \[\mathbb{E}_{\psi^{**}}\bigl[ \tau(\boldsymbol{x}) \bigr] = \gamma \mathbb{E}_{\psi_1^*}\bigl[ \tau(\boldsymbol{x}) \bigr] + (1 - \gamma) \mathbb{E}_{\psi_2^*}\bigl[ \tau(\boldsymbol{x}) \bigr] \leq \gamma c_1 + (1-\gamma) c_2\] for all \(\boldsymbol{x} \in \mathcal{X}^\mathbb{N}\) so that \(\psi^{**} \in \mathcal{I}_{\gamma c_1 + (1-\gamma) c_2}^\infty\). The error probabilities of the corresponding test are given by \[\begin{align} \alpha(\psi^{**}) &= \gamma \alpha(\psi_1^*) + (1-\gamma) \alpha(\psi_2^*), \tag{50} \\ \beta(\psi^{**}) &= \gamma \beta(\psi_1^*) + (1-\gamma) \beta(\psi_2^*). \tag{51} \end{align}\] It follows that \[\begin{align} \gamma \rho_k(z, c_1) + & (1 - \gamma) \rho_k(z, c_2) \notag \\ &= \gamma \min_{\psi \in \mathcal{I}_{c_1}^\infty} \left( \alpha(\psi) + z \, \beta(\psi) \right) + (1 - \gamma) \min_{\psi \in \mathcal{I}_{c_2}^\infty} \left( \alpha(\psi) + z \, \beta(\psi) \right) \notag \\ &= \gamma \left( \alpha(\psi_1^*) + z \, \beta(\psi_1^*) \right) + (1 - \gamma) \left( \alpha(\psi_2^*) + z \, \beta(\psi_2^*) \right) \tag{52}\\ &= \gamma \alpha(\psi_1^*) + (1-\gamma) \alpha(\psi_2^*) + z \left( \gamma \beta(\psi_1^*) + (1-\gamma) \beta(\psi_2^*) \right) \notag \\ &= \alpha(\psi^{**}) + z \, \beta(\psi^{**}) \tag{53}\\ &\geq \min_{\psi \in \mathcal{I}_{\gamma c_1 + (1-\gamma) c_2}^\infty} \alpha(\psi) + z \, \beta(\psi,)\tag{54} \\ &\;= \rho(z, \gamma c_1 + (1-\gamma) c_2), \notag \end{align}\] where 52 holds since \(\psi_1^*\) and \(\psi_2^*\) are optimal, 53 follows from 50 and 51 , and 54 holds since \(\psi^{**} \in \mathcal{I}_{\gamma c_1 + (1-\gamma) c_2}^\infty\).

In order to show that \(\rho(z, \bullet)\) is piecewise linear, we define the following recursion: \[\tilde{\rho}_k(z, c) \coloneq g(z) - c \, \sup_{b \geq \max\{1,c\}} \frac{g(z) - \mathbb{E}_0\bigl[\tilde{\rho}_{k-1}\bigl(z\frac{p_1(X)}{p_0(X)}, b - 1\bigr)\bigr]}{b}, \label{eq:rho95tilde95k95recursion}\tag{55}\] with \(\tilde{\rho}_0 \coloneq \rho_0\). It is not hard to show that for all \(z,c \geq 0\) the sequence \(\bigl( \tilde{\rho}_k(z, c) \bigr)_{k \geq 0}\) is non-increasing and converges to the same limit as \(\rho_k(z, c)\), that is, \[\lim_{k \to \infty} \tilde{\rho}_k(z, c) = \lim_{k \to \infty} \rho_k(z, c) = \rho(z, c).\] The statement in the lemma can now be proven by induction. Assume that for some integer \(k \geq 0\) the function \(\tilde{\rho}_k(z, \bullet)\) is piecewise linear with breakpoints in \(\mathbb{N}_{\geq 0}\). In turn, the function \[\mathbb{E}_0\biggl[\tilde{\rho}_{k-1}\biggl(z\frac{p_1(X)}{p_0(X)}, \bullet \biggr)\biggr]\] is piecewise linear with breakpoints in \(\mathbb{N}_{\geq 0}\). Since the ratio of two positive affine functions is monotonic, the argument of the supremum in 55 is monotonic on all intervals \([n, n+1)\) with \(n \in \mathbb{N}_{\geq 0}\). Consequently, the maximum on the right-hand side of 55 is either attained at \(b_k^* = c\) or at some breakpoint \(m \in \mathbb{N}_{\geq 0}\).

For \(b_k^* = c\) it holds that \[\tilde{\rho}_k(z, c) = \mathbb{E}_0\biggl[\tilde{\rho}_{k-1}\biggl(z\frac{p_1(X)}{p_0(X)}, c - 1\biggr)\biggr],\] which is piecewise linear with breakpoints in \(\mathbb{N}_{\geq 0}\) by assumption. For \(b_k^* = m\) it holds that \[\tilde{\rho}_k(z, c) = g(z) - c \, \frac{g(z) - \mathbb{E}_0\bigl[\tilde{\rho}_{k-1}\bigl(z\frac{p_1(X)}{p_0(X)}, m - 1\bigr)\bigr]}{m},\] which is affine in \(c\). This completes the induction step. The induction hypothesis holds true by Lemma 3. The statement in the lemma now follows from the fact that pointwise limits of affine functions are affine² and that \(\tilde{\rho}_k(z, \bullet)\) is affine on all intervals \([n, n+1]\), \(n \in \mathbb{N}_{\geq 0}\). This completes the proof.

16 Proof of Theorem 4↩︎

To prove the theorem, it suffices to show that \[\max\{ m^*(z) \,,\, c\} = \mathop{\mathrm{arg\,max}}_{b \geq \max\{1,c\}} \frac{g(z) - \mathbb{E}_0\bigl[\rho\bigl(z\frac{p_1(X)}{p_0(X)}, b - 1\bigr)\bigr]}{b}. \label{eq:b95opt}\tag{56}\] For \(c < 1\), it follows from the convexity and piecewise linearity of \(\rho(z, \bullet)\) that the maximum in 56 is attained at a positive integer, that is, \[\begin{align} \mathop{\mathrm{arg\,max}}_{b \geq 1} \frac{g(z) - \mathbb{E}_0\bigl[\rho\bigl(z\frac{p_1(X)}{p_0(X)}, b - 1\bigr)\bigr]}{b} &= \mathop{\mathrm{arg\,max}}_{m \in \mathbb{N}_{\geq 1}} \frac{g(z) - \mathbb{E}_0\bigl[\rho\bigl(z\frac{p_1(X)}{p_0(X)}, m - 1\bigr)\bigr]}{m} \\ &= m^*(z) = \max\{ m^*(z) \,,\, c\}. \end{align}\] For \(c \geq 1\), we distinguish two cases. First, assume that \(c \leq m^*(z)\). In this case \[\mathop{\mathrm{arg\,max}}_{b \geq c} \frac{g(z) - \mathbb{E}_0\bigl[\rho\bigl(z\frac{p_1(X)}{p_0(X)}, b - 1\bigr)\bigr]}{b} = m^*(z) = \max\{ m^*(z) \,,\, c\}.\] Now, assume that \(c > m^*(z)\). Since \(\rho(z, \bullet)\) is convex, it is non-decreasing on \(\mathbb{R}_{\geq m^*(z)}\). Thus, \[\mathop{\mathrm{arg\,max}}_{b \geq c} \frac{g(z) - \mathbb{E}_0\bigl[\rho\bigl(z\frac{p_1(X)}{p_0(X)}, b - 1\bigr)\bigr]}{b} = c = \max\{ m^*(z) \,,\, c\} .\] This completes the proof.

17 Proof of 27↩︎

Let \[u(b) \coloneq -\frac{\log z + \mu_0 b}{\sigma_0\sqrt{b}}.\] Differentiating the objective function in 27 with respect to \(b\) gives the first-order optimality condition \[\frac{\phi(u(b))}{\Phi(u(b))} = \frac{2\sigma_0\sqrt{b}}{\log z - \mu_0 b}, \label{eq:foc}\tag{57}\] where \(\phi\) denotes the probability density function (PDF) of the standard normal distribution. Let the smallest solution of 57 be denoted by \(b'\), so that \(b'\) is a lower bound on the maximizer. First, assume that \(b' > 1\). In this case, it holds that \[\frac{\phi(u(1))}{\Phi(u(1))} > \frac{2\sigma_0}{\log z - \mu_0}.\] Since the left-hand side of 57 is decreasing in \(b\), this implies that it crosses the right-hand side from above at \(b = b'\). We now further bound \(b'\) from below by introducing two successive under-approximations.

The Mills ratio bound Feller1968? gives \[\frac{\phi(u)}{\Phi(u)} > -u. \label{eq:mills95bound}\tag{58}\] Substituting 58 back into 57 and cross-multiplying yields the quadratic equation \[\mu_0^2 b^2 + 2\sigma_0^2 b - (\log z)^2 = 0 \label{eq:foc95mod}\tag{59}\] with unique positive root \[b'' = \frac{-\sigma_0^2+\sqrt{\sigma_0^4+\mu_0^2(\log z)^2}}{\mu_0^2}.\] Since 58 is a lower bound on the left-hand side of 57 and the latter crosses the right-hand side from above, it holds that \(b'' < b'\). Finally, since \(\sigma_0^4 > 0\) and \(\mu_0 < 0\) we have \(\sqrt{\sigma_0^4+\mu_0^2(\log z)^2} > -\mu_0\log z\), so that \[b'' > b''' = \frac{-\sigma_0^2-\mu_0\log z}{\mu_0^2} = -\frac{\log z}{\mu_0}-\frac{\sigma_0^2}{\mu_0^2}.\] Chaining the inequalities yields \(b' \geq b'' \geq b'''\) for \(b' > 1\). Finally, using the Mills ratio bound, it is not hard to show that \(b' = 1\) implies \(b''' < 1\). This completes the proof.

---

1. We first introduced and investigated this problem in an unpublished preprint Fauss2020?. The approach used in this paper is fundamentally different and the presented results are significantly stronger and more general. We do not use any results from Fauss2020?, and do not expect the reader to be familiar with it. However, for the interested reader, Fauss2020? provides a more detailed discussion and motivation of the Kiefer–Weiss problem.↩︎

2. A function is affine if and only if it is convex and concave. Since pointwise limits of finite convex/concave functions are convex/concave Rockafellar1970?, pointwise limits of affine functions are affine.↩︎