On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds

We present two general lower bounds for stopping times of sequential tests between arbitrary composite nulls mathcal P and alternatives mathcal Q. The first lower bound is for the ``Wald setting'' where the type-1 error level α approaches zero for a fixed alternative Q ∈ mathcal Q, and equals log(1/α) divided by a certain infimum KL divergence between mathcal P and Q, termed operatornameKLinf. The second lower bound applies to the ``Farrell setting'', where α is fixed and operatornameKLinf approaches 0 along a sequence of alternatives such that the required expected sample size along that sequence is of order at least operatornameKL-1inf log log operatornameKL-1inf. Our main contribution is the generality of these bounds, which hold in non-parametric, composite settings, without requiring a dominating reference measure, substantially generalizing the known parametric results. We also provide sufficient conditions for matching upper bounds and show that these are met in several nontrivial non-parametric cases.