Efficient Approximate Solutions to the Kiefer-Weiss Problem Citation Huffman, Michael David (1980) Efficient Approximate Solutions to the Kiefer-Weiss Problem. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/5nn5-n386. https://resolver.caltech.edu/CaltechTHESIS:08112025-214237411 Abstract The problem is to decide on the basis of repeated independent observations whether θ 0 or θ 1 is the true value of the parameter e of a Koopman-Darmois family of densities, where θ less than θ less than θ. The probability of falsely rejecting e0 is to be at most o:0, and that of falsely rejecting θ 1 , at most α 1 . Procedures are studied from the point of view of minimizing the maximum (over θ) expected number of observations required when e is the true value of the parameter. Two types of tests are considered. The first, based on the well-known sequential probability ratio test (SPRT), dictates after each observation whether to stop and ma.ke a decision, or whether to continue sampling. An explicit method is derived for determining a combination of one-sided SPRT's, known as a 2-SPRT, which minimizes the maximum expected number of observations to within o((n(α 0 ,α 1 )) 1/2 ) as α 0 and α 1 go to o, where n(α 0 ,α 1 ) is the minimum of the maximum expected sample size, taken over all procedures with error probabilities at most α 0 and α 1 . The second test uses several stages of observations, deciding whether to stop or continue only at the end of each stage. A procedure designed to "do what a sequential test would do", while using at most three stages, is defined and shown to minimize the maximum expected number of observations to within O((n(α 0 ,α 1 )) 1/4 (log n(α 0 ,α 1 )) 3/2 ) as α 0 and α 1 go to 0. Finally, using backward induction, optimal procedures were developed on the computer for the case where the mean of an exponential density is tested. Then extensive computer calculations comparing the proposed 2-SPRT with these optimal procedures show that the 2-SPRT comes within 1% of minimizing the maximum expected sample size over a broad range of error probability and parameter values. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Lorden, Gary A. Thesis Committee: Unknown, Unknown Defense Date: 28 August 1979 Record Number: CaltechTHESIS:08112025-214237411 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:08112025-214237411 DOI: 10.7907/5nn5-n386 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 17611 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 12 Aug 2025 16:30 Last Modified: 12 Aug 2025 16:31 Thesis Files PDF - Final Version See Usage Policy. 12MB Repository Staff Only: item control page

EFFICIENT APPROXIMA~ SOLUTIONS TO THE KIEFER-WEISS PROBLEM Thesis by Michael David Huffman In Partial FulfilJJnent of the Requirements for the Degree of Doctor of Hrl.1.osopby Ca1ifornia. Institute of Technology Pasadena, California 1980 (SUbmitted August 28, 1979) ii Acknowledgments I am grateful. to the California Institute of Technology and its Mathematics Department for the fellowships and research and teaching assistantships which supported me financially and provided valuable teaching experience. To all my friends and relatives in Albuquerque, Pasadena and around the country, I give maey thanks for genuine concern and interest in both my work and my well-being. My pa.rents and my brother Cary deserve special appreciation. The love and encouragement they have given me for 25 yea.rs has certainly provided an important foundation for the completion of my graduate studies. I wish to express heartfelt gratitude to my thesis advisor, Dr. Gary Lorden, whose incredibly patient guidance and careful tutoring enabled me to do this research. My deepest appreciation goes to my wife, Margo, who was never- failing in her support and belief in me. No matter how frustrated I became, she was always ready with cheerful. and encouraging words. I also thank her for the skillful tyJ)ing and editing which she provided. With much love I dedicate this thesis to her. iii Abstract The problem is to decide on the basis of repeated independent observations whether 00 or e1 is the true value of the para.meter e of a Koopman-Da.rmois family of densities, where i < e < i. The probability of falsely rejecting e0 is to be at most o: 0 , and that of falsely rejecting e1, at most a 1 . Procedures are studied from the point of view of minimizing the maximum (over a) expected number of observations required when e is the true value of the parameter. Two types of tests are considered. The first, based on the well-lmown sequential probability ratio test (SPRT), dictates after each observation whether to stop and ma.ke a decision, or whether to continue sampling. An explicit method is derived for determining a combination of one-sided SPRT's, lmown as a 2-SPRT, which minimizes the maximum expected number of observations to within o((n(a0 ,o: )) 1/ 2 ) 1 as o: 0 and a 1 go to o, where n(a 0 ,a 1 ) is the minim.um of the ma.x:imum expected sample size, taken over all procedures with error probabilities at most o:0 and o: . The second test uses several stages of observations, 1 deciding whether to stop or continue only at the end of each stage. A procedure designed to "do what a sequential test would do", while using at most three stages, is defined and shown to minimize the maximum expected number of observations to within O(~(a ,o: 1 )y/4(log n(a ,a )?/2 ) 0 0 1 as o: 0 go to o. 1 Finally, using backward induction, optimal procedures were and a develOJ?ed on the computer for the case where the mean of an exponential density is tested. Then extensive computer calculations comparing iv ·the proposed 2-SPRT with these optimal procedures show that the 2- SPRT comes within 1i of minimizing the maximum expected sample size over a broad range of error probability and para.meter va.lues. V Table of Contents ~ Acknowledgments ii Abstract iii 1. Background and Definition of the Problem 1 2. 2-SPRT's and the Kiefer-Weiss Problem 11 2.1 Introduction and Summary of Resu1ts 11 2.2 Proof of (2.10) 16 2.3 Proof of (2.8) 18 2.4 Proof of (2.9) 22 2. 5 Refinement 26 Three-stage Tests and the Kiefer-Weiss Problem 28 4. Comparison of 2-SPRT's with Kiefer-Weiss Solutions 38 3. 4.1 Summary of Results 4.2 Method for Computing Kiefer-Weiss Solutions References 38 42 47 - 1- 1. Background and Definition of the Problem Hypothesis testing has long been one of the .most studied statistical areas. As the name implies, two (or perhaps :more) hypotheses, H0 and H1, are formula.ted, and then one of these must be chosen as correct. 'Ibis decision will be based upon the observed values of random variables x1, ~, ... which are assumed to be independent and identically distributed with density r (x) for sane 8 value of e. In this and the following chapters, the testing problem under consideration will be to determine which probability density, t or f 80 (x) (x), is true, where e0 < e1 . 81 When performing a test there are two errors which can be committed: rejecting a0 when it is true (called a type I error), or accepting e0 when the alternative e1 is true (called a type II error). The probabilities of these errors will be denoted by a 0 and a 1, respectively, so that and a 1 = P (reject e1 ). 81 Of course, the most desirable test is one which will keep to a m1n1mum the probability of these two types of error. Unfortunately, when the number of observations is given, both probabilities of error cannot be controlled simultaneously. It is customary to assign a bound to the probability of incorrectly rejecting e0 when it is true, -2- and to attempt to minimize the other error probability subject to this condition. Neyman and. Pearson, who were the first to introduce the distinction between the two types of error, proposed the following "likelihood ratio test", and established a fundamental lemma bearing their names [13 ] . Fork= 1,2, ... , the likelihood function of the observations x 1,~,··• is defined by Assume that a fixed number n of observations will be taken, and. choose a constant c > o. If then e0 is rejected; otherwise e0 is accepted. Once n has been established, the value of c controls the value of the type I error of the test. The Neyman-Pearson lemma states that among all tests using n observations and satisfying P (reject e0 ) ~a 0 , the likelihood 80 ratio test (with error probability a 0 ) minimizes cx 1 . Hence if the sample size is fixed, the likelihood ratio test provides the best procedure. Significant improvement in the likelihood ratio test is possible, however, if the number of observations is not fixed in advance but is allowed to depend on the observations themselves. Procedures which take samples one at a time until enough information has been accumulated to make a decision are called sequential tests. These tests based on sequential sampling will be written as the pair T = (N,D). N is called a stopping rule -- it states when the -3- sampling should end, based on the observations taken up to that point. Dis the decision rule, indicating which of the hypotheses should be accepted once sampling has stopped. The earliest of these tests, called a. sequential probability ratio test (SPRT), is due to Abraham Wald [15]. Given AO and A1 in (o, 1) the stopping rule N is the first n (or~ if there is non) such that the inequa.lity ( 1. 1 ) does not hold. The decision rule D rejects e0 if the inequa.lity is violated to the right, and rejects e1 if it tails to hold on the left. N is a random variable which depends on the observations, that is, on the true distribution of the Xi's. If the true value of 8 is less than 00, then the test will quickly violate the left inequa.lity, resulting in a small N. Similarly, if the true value of 9 is greater than e1, the right-hand inequality will tail after relatively few observations. Should 8 lie between 00 and e1, the SPRT will require more observations in order to make a choice. E N will denote the expectation of N when 8 is the true parameter 8 value, and represents the average or expected number of observations which will be needed to complete the SPRT if e is true. The performance of any sequential test is judged on the basis of its error probabilities and its expected sample sizes. Wald and Wolfowitz [ 17] established the remarkable property that among all tests-sequential or not--with equal or smaJJ.er error probabilities, the SPRT -4minimizes both E N and E N. 81 80 In practice the values of A0 and A 1 in (1.1) must be chosen so that the resulting SPRT has prescribed error probabilities a 0 and a 1 . WaJ.d [ 15] showed that if a 0 ' and a 1 ' are the actual error probabilities of the SPRT using A0 and A1, then Hence choosing A0 = a 0 and A 1 = a 1 in ( 1 • 1 ) guarantees that the SPRT will have error probabilities at most a 0 and a 1 . WaJ.d aJ.so provided approximations for E N and E N. 81 80 Define for n = 1,2, ... and Yn = z1 + .•• + zn . By taking logs, (1.1) is equivalent to the inequality Since N is a stopping rule, (1.3) where the first equality is known as WaJ.d's equation and I(e 1,e0 ) is the Kullback-Leibler information number defined by -1 If the SPRT rejects e0, then~ is ap:proximately log A0 , while if it rejects e1, ~ is near log A1 . Hence -5(1.4) _, where ~ indicates that the terms YN - log A1 and YN - log A0 , call.ed excess over the boundary, have been neglected. a.re chosen equaJ. to o: 0 If A 0 and A 1 and o: , then (1.3) and (1.4) combine to yield 1 log o: E N~---- 81 for smaJ.l values of o: -1 0 I(a 1,a0 ) and o: . , In fact, if var z , the variance of 8 1 z1 under e1, is finite, then E8 N is within 0(1) of the right-hand side as o: and o: tend too, with a similar expression holding for e • 0 1 0 0 1 , Even though the SPRT minimizes E N and E N among all tests with 81 80 prescribed error probabilities, its performance is unsatisfactory for values of e between e and e . 0 1 In sane cases E N is larger than the 8 number of observations required by a fixed sample size test with the same error probabilities. Mu.ch of the development of sequential analysis has been directed toward finding procedures which improve the performance of the SPRT for these parameter va.lues. Let ,1(o: ,o: ) denote the class of all tests (N, D) which have error 0 1 probabilities at most o: 0 and o: , and define 1 The problem of finding a procedure (N' ,D') which minimizes the maximum expected sample size subject to the error probability constraints o: and o: 1 -- that is, so that s f E8N' = n(o:0 ,o: 1 ) -- is known as the Kiefer-Weiss problem. No optimal results (in the sense of the optima.lity property of the SPRT) have been found for this problem. 0 -6Kiefer and Weiss [ 5] proved structure theorems about tests which minimize E N for a fixed 8 = e (this is called the modified Kiefer2 92 Weiss problem). Weiss (18] showed that the Kiefer-Weiss problem reduces to the modified problem in symmetric cases involving normal and binomial distributions . Lai [ 7] investigated the Wiener process case. A test (N,D) is customarily judged by its efficiency, which in this context is n(a ,a 1 ) 0 ( 1 • 5) s~p E9N A procedure is said to be asymptotica.l.ly efficient if (1.5) tends to 1 as a 0 and a 1 go too, and for such tests the rate of approach of (1.5) to 1 is of interest. Thus, finding fairly simple procedures which are not only asymptotica.l.ly efficient, but have efficiencies close to 1 for practical values of a 0 and a 1, is important. Anderson [ 1] studied a class of easily constructable procedures for the symmetric case of testing the mean drift of a Wiener process. In a general context Lorden [8] studied a subclass of Anderson's procedures, related to SPRT's and caJ.led 2-SPRT's. Given e0 < 8 < e1, and O < A ,A 1 ~ 1, the stopping rule M( 8,A 0,A 1 ) is the smallest n ( or 00 0 if there is non) such that f ~.n J. - f - < A. en for either i = 0 or 1. - J. ( 1. 6) The decision rule D rejects 80 if (1.6) does not hold for i = 1, and rejects e1 if it does not hold for i = 0. If (1.6) is true for both values of i, then any fixed rule can be used -7- for deciding between e0 and e1 . A useful alternate way to write the stopping rule is M(a,AO,A1 ) = min(Mo(e,AO),M,(e,Ai)) where Mi(e,Ai) is the smallest n such that ( 1. 6) holds. As Lorden pointed out, the method which Wald used to derive (1.2) is applicable to the 2-SPRT and yields a.< A. P (reject e ), l. - l. 0 1 i = 0,1 (1. 7) so that setting Ai= ai in (1.6) insures error probabilities of at most a 0 and a 1 . The main theorem in [ 8] states that if a 0 and a 1 are the true error probabilities of the 2-SPRT (M(e,AO,A1 ),D), then as a ,a 1 ➔ o where e is fixed. Thus, for any fixed a, the 2-SPRT O provides an asymptotic solution to the modified Kiefer-Weiss problem. In the symmetric normal. case, where e is the mean and a 0 = a 1 = a, say, the Kiefer-Weiss problem reduces to the modified problem for cp = (e 0 + e1 )/2 [18], where only procedures symmetric about q, need be considered. So in this case, the 2-SPRT gives an approximate solution to the Kiefer-Weiss problem. values of a, Lorden showed that over a wide range of e0 and e1, the 2-SPRT has an efficiency of more than 99.2i. Hence, setting Ai= ai so the 2-SPRT's are in .r(aO,a 1 ), if 9 can be found so that E M(e,a O,a 1 ) is nearly maximized at 8 = 8 e, then the resulting 2-SPRT will be an approximate solution to the Kiefer-Weiss problem. Chapter 2 derives an explicit method for determining 1!' as a function of a 0 and a 1, in the context of the Koopman-Darmois family of densities (defined in the next paragraph). Theorem 1 shows -81 - 1/2 that the efficiency of the 2-SPRT so obtained is 1 - o((log a 0 - ) as a 0 and a 1 go too, subject to the condition that O < c < log a /log a < c < oo 0 1 1 2 for fixed but arbitrary constants c1 and c2 • In Chapters 2 and 3 it is assumed that x 1, ~, ••• have one of the Koopman-Darmois densities given by with respect to a non-degenerate a-finite measureµ.. (Common members of this family include the normal, eJQ?OnentiaJ.., binomial. and Poisson densities.) The function b(8) is necessarily convex and infinitely differentiable on (~ 9), and its first two derivatives satisfy b' (e) = E x and bn(a) = va:r x = cl(e) 0 8 ([ 6] a.nd [15]). A simple calculation shows that I(8,r.p) = (a - q,)b'(e) - (b(e) - b(cp)). For n = 1,2, ... , let S = x1 + ... + X, and define the logn n likelihood ratios f = log fen ein = (e - e.)s 1 n - n(b(e) - b(ei)), i = 0,1. Then (1.6) is equival.ent to ,t,i(e,n) ~ log Ai-l. The 2-SPRT can be described graphically in the plane of n a.nd Sn. There are two 1 converging lines given by (e - ei)Sn - n(b(e) - b(8 1 )) = log A - . 1 Sampling is stopped as soon as the sequence (1,s1 ), (2,s2 ), ... leaves the triangular region bounded by the lines, and the decision depends on which line is crossed . ) -9In practice it is sometimes easier to collect and use data in sets rather than one at a time. In this case it is preferable to use a testing procedure which is based on taking observations in several stages. Typically the maximum number of stages is fixed in advance, and a:f'ter each set of observations is taken, a decision is ma.de whether to stop or to continue to the next stage. The number of observations in each stage _is based on the observations taken up to that point . To design such a multistac;e test, it is natural to try to imitate the performance of a sequential test by setting up each stage to 11 do what the best sequential test would do 11 based on the previous stages. Chapter 3 is concerned with defining a three-stage test, based on the sequential likelihood ratio test (SLRT) [9], in such a way as to achieve good asymptotic performance. Theorem 2 shows that the procedure defined in the third chapter 1 has an efficiency of 1 - O(y- 3/ 4 (log y) 3/ 2 ), where y = log a - + 0 1 log a - , indicating that the performance of the three-stage test would 1 be very good for sma.11 enough a 0 and a 1 . Unfortunately, the test and theory are not refined enough to indicate what should be done to achieve high efficiencies in practical use. In particular, since there is no analog of Lorden's o(1) result for the 2-SPRT, it seems unlikely that at this level of refinement the three - stage procedure would attain efficiencies as high as those of the 2-SPRT. Chapter 4 describes the results of computer calculations comparing the test proposed in Chapter 2 with actual Kiefer-Weiss solutions in the case of the exponential density. A method of computing the latter was developed, incorporating the well-known backward induction method -10- for computing modified Kiefer-Weiss solutions. It is shown that the 2-SPRT comes within 1% of minimizing the maximum expected sample size over a fairly broad range of error probability and parameter values. In addition, the expected sample sizes under e0 and e1 are compared with those of the SPRT having the same error probabilities, indicating a relatively insignificant increase in the number of observations required by the 2-SPRT. -11- 2. 2. 1 2-SPRT's and the Kiefer-Weiss Problem Introduction and Sumtl\8ry of Results For the results in this chapter it suffices to choose Ai= ai for i = O, 1, which insures that all the 2-SPRT's under consideration are in .r(a ,a 1 ). 0 It will also be assumed that there are fixed but arbitrary constants c1 and c such that 2 log a o < c1 < 1og a 0 < c2 < oo. (2.,) 1 Let S = x + ... + X for n = 1,2, . . . . n n 1 In the {n,S) plane the n boundarie s of M( e,a ,o: 1 ), defi ned by equa.li ty in ( 1. 6), are lines 0 given by Defining Ii(e) = I(e,e1 ) and a 1 (e) = ( e - e.1 ) /r.1 ( e), these lines intersect at (n(e),v(e)) where -1 = (log a 1 n ( e) , I ( e) (2.3) v(o) (2.4) 1 and By virtue of the fact that b( e) is convex, I ( fl) is strictly increasing, 0 I (A) is strictly decreasing, and both are positive on (e0 ,e1 ). 1 Thus for any e in (0 ,A ), a (e) < O < a0 (e), which implies that n(e) is 0 1 1 positive. Hence the 2-SPRT is truncated and can take at most [n(e)] + 1 observations. -12Let ai., Ii, a and n denote the values of ai(e), Ii(e), a(8) and Also let ii = min(M0,i1 ) represent M(e,a0,a1 ) . n( 8) tor 8 = 'J. F.quations (2.11), (2.14), (2.15) and (2 . 16) given below define 'J and r so that the following theorem holds. If (2.1) is satisfied then as a 0,a1 ➔ O Theorem 1. sup E/ = n - a{a0 8 a1 )cp(r)n1/ 2 + o(n1/ 2 ) (2. 5) and where c;p(•) is the standard normal. density function. Thus • -1/2 1 - o( (log a - ) )• 0 (2. 7) The proof of Theorem. 1 consists of establishing relations (2.8) (2. 1O) below. (2. 5) follows immediately from °¥ ~ n - a(aO - al )cp(r)n1/2 - o(nl/2) (2.8) 1 sup E/<3_n -aCa0 -a1 )cp(r)n / 2 + o(n1/ 2 ), (2.9) and e while (2.6) follows from these relations together with inf .r(a0 ,a 1 ) Ef ~ Y (2.10) - 0(1 ). (2.7) is an immediate consequence of (2.5) aoo (2.6). The key to the argument is to choose '8' so that the supremum over 8 of E9't. is attained at 8, at least to within (n1/ 2 ). 0 -13- To determine how to choose l', first define 9* so that (2. 11 ) and let n* be the canon value of the two aides (which by (2.3) equals n ( 8*) ) . The monotonicity of the information numbers implies that 8* is uniquely determined, and (2.1) implies that 8* lies in a fixed closed subinterval of (e0,e 1 ), say [q,0,q, 1 ]. As above for 1iof, let M* = M(8*,cx0,a 1 ) = min(Mc,*,M, *) and define a1 *, Ii* and a* accordingly. In the {n,Sn) plane, relation {2.Ji) shows that the line determined by the points (n,E *sn) = (n,nb' (8*)) for n = 1,2, ... passes through 8 the vertex (n*,v(8*)). So under 8* the points (n,s) will tend to n drift toward the vertex. at 8 = 8*. In general, however, E M* is not maximized 9 This is because for n < n* one of the boundaries will be closer to the line (n,nb' (e*)) so that the nuctuations ins will n cause the 2-SPRT to end too early by going over the closer boundary. More precisely, essentiaJ.ly the same argument that will be used to show (2.5) can be extended to show that for 8.,. 8* + c(n*)- 1/ 2 (where c is restricted to any bounded interval) where the expectation on the right-hand side is with respect to the standard normal variable z. Choosing e to ma:dm1 -ze E M* to within 8 1 2 o{{n*) / ) is then equivalent to finding c to minimize the expectation on the right-hand side. This expectation can be written -1400 j0 P(max(ai*(Z +a-Mc))> t) dt i=0,1 (2. 13) = oo Jo t t (P(Z > ;-,,: - O'-IEc) + P(Z < --:.: - O'-tfc)) dt. ao a, Using xt(x) + q,(x) as a primitive for the standard normal distribution t(x), straightforward integration shows that the integral equals a-Mca 1*+ (a0 * - a 1*)(a-1Ect(O'i!-c) + ,,(O'-lfc)). Differentiating with respect to c shows that the minimum value of (2.13) occurs at c = r*/a* where (2. 14) In addition, the value ot (2.13) at c = r*/a* is given by (a0 * - a 1*)~(r*). In general, define r ( e) by the relation a1 (e) t(r(e)) = a {8) - a (9) 1 0 ' so that r* = r(e*). In Theorem 1 l and r are given by l = e* + r* 1/2 cr*(n*) (2. 15) and r = r(l). (2. 16) With this choice of 1', it turns out that the analog of (2.12) using 1r in place of M* is extremized by the same choice of c. 1 maximized to within o(n. / 2 ) by e = l. Thus, E YI. is 8 It will be assumed in the remainder of the chapter that a 0 and a 1 are small enough so that 9* and 1' are in [q:,01 q, 1 ]. Thia assures that ai*, a1, and the information numbers are bounded away f'rcm O and oo. -15Before continuing to the proofs of (2.8) - (2.10), given in the following sections, several relationships concerning the boundaries of i{ will be established. Let Tn = Sn - nb' (e) for n = 1,2, ... and lets= v(l) - nb' (e). Then in the (n,T ) plane, (n,s) is the vertex of i{ and from (2.2) n the boundaries are given by the equations log cx1 -1 ui (n) = ;:n + - - ai l - ei for i = 0,1. (Sampling is stopped as soon as either Tn ~ u0 (n) or Tn ~ u1 (n), the decision depending on which inequality holds.) These are lines with slope -ai -l passing through (n,s) so the above is equivalent to (2. 17) Solving for log cxi -1 using the last two equations yields log (Xi - l = (n + ais)Ii (2. 18} The final relationship is given by ~ ~ sl/2 = -"; + o(l ). (2.19) o-{n) To show (2.19) it suffices to establish ~ s 1/2 = -r* +0(1), (2.20) O'*(~) since r* is bounded by virtue of (2.1) and 8 - 9* ➔ 0 ensures n ~ n*, r ~ r* and a~ cr*. (2.4) a.nd the definitions of sand n* give -16- 2 It is easily seen that I ' (e) = (8 - e )a (e), so that expanding 1 1 I (1n in a Taylor series about 8* yields 1 where the ~i are numbers between 8* and l. Substituting into the 1 2 above expression for sand dividing by cr*(n*) / gives s* {(02(~,)(~, - e,) cr2(~0)<~0 - 80)) -11 _ _..,.....,,.. = - - . , . . - - - - - _ _..,..._ _ _ (a (l) - a (1')) r* cr*(n*) 1/2 (cr*)2I1 (l) (cr*/Io(l') O 1 2 2 Noting that cr (~i)(c*)- = 1 + o(1) and (~ 1 - e )/I (l') = a (l) + 0(1) As pointed out after (2. 16), ai' 'Ii and a are bounded awey- from 0 1 1 1 completes the demonstration of (2.20). 2.2 Proof of (2.10) and oo, so that tbe following lemma yields (2.10) . (2 .21 ) Proof. Let Mand Mi denote M(e,a0 ,cx 1 ) a.nd M1 (e,ai) respectively. Let (N, D) be any test in ..1(a0 ,cx 1 ) , a.nd let [D = i 1 be the event that -178 is rejected by that test. 1 define As in the proof of Theorem 1 in [ 9] where N( D = i} = N if D = 1 and 00 otherwise. M - N < t - i::O By Wald's equation Clearly for all e, (M - N. ) . 1 1 (2.22) -1 log cxi + o E(11 = I (8) i 1 where o = E (t1 (e,M1 ) - log cx0 - ) is the expected excess over the 8 boundary log ex _, . By '.theorem 1 of [ 11 ] , 1 var ti( e, 1) 8 -- = o < -~ - ri(e) (e - e /a-2 ( 8) i I 1 (8 ) (2.23) which yields (2.24) To estimate E N1, the inequality 8 canbined with Wald's lower bound on the expected sample size of a one-sided SPRT [15] shows (2.25) Ta.king expectations in (2.22) and using (2.24) and (2.25) shows that (2 .21 ) is true, (N, D) being an arbitrary member of .r(cx0,cx 1 ) . -182.3 Proof of (2.8) Let m = [~n - ~1/2 n log ~1 n. The derivation of (2.8) relies mainly on two facts, the first being that with overwhelming probability under 1' the test requires at least m observations, and the second being that once them observations are taken, the behavior of the remainder of the test is sufficiently predictable by the value of T. m More specifically, the first claim is given by ~ 1 P (M ~ m) ~ O(n ) 8 (2.26) and is proven in Lemma 2.4 at the end of this section, while the second is given by the following lemma. Lemma 2. 2. On the event E,.,.e~IT ) > m - Proof. {M > m} 12 n - i=0,1 max (e;i(T - s)) - o(n / ). m (2.27) At time m the log-likelihood ratios have values ti (1,m) = (a1 Tm + m)l'i for i = O, 1. If' M > m then based on observations Y1, Y2 , ... , where Yk = x.+k' let Ni be the first n such that 1 ti (l,n) ~ Ki = log a 1 - - (a1Tm + m)l'i. Substituting for log ai-l according to (2.18) shows Ki• (n - ai(Tm - s) - m)l'i. (2.28) On {M>m}, (2.29) By Lemma 2.3 below there is a constant D such that (2. 30) -19By (2.28), K 1 min ) = m - max (ai (Tm - s) ), (2.31) i=0,1 Ii i=0,1 12 which is at most / log Using (2.30) and (2.31) in (2.29) yields (~ n n- n. relation (2.27). The following lemma. establishes (2.30) by giving a general lower bound on E M(8rA0,A1 ). 8 • Lemma 2.3. 1 Let D = 2 max [cpo, q,1 l ((a0 (a) - a. 1 (e) ) 1fe a(e)). EeM(e,A0,A1 ) ~ K - DK l/2, (2.32) -1 . (log Ai ~ where K = nun I {e) )" i=0,1 i Proof. As in the proof of inequality ( 1 • 4) in [ 4 ] , define for n = 1,2, ... , i = o, 1 and yn = Yo ,n - Y, ,n • Clearly K :S max(Y0 M'Yl , M). , , Therefore, writing max(Y0,M'Y1 M) = } (Y0,M + Y1,M) +} l\il and noting that E8Yi,M = E8M by Wald's equation (since E Yi,l = 1), 8 (2.33) Also, (2.34) Since E Y1 = o, Wald's second moment equation yields 8 2 Ee(~)~ (EeM)Va.reY,. (2 . 35) -20- 2 A simple computation shows that the variance equals (a0 (8)-a 1 (e))cr (e). Combining (2.33) - (2.35) with the definition of D leads to 12 K ~ E8M + D(E~) / from which (2 .32) follows easily, proving the lemma. Lemma 2.2 and the estimate of 1l'(j.'f ~ m) in (2.26 ) give ~ ~n - ~ _max(a1 (Tm - s)) + o(n1/ 2 ) . 1=0, 1 The expectation on the right-hand side can be written ~ 1/2 r (Tm - 8\ om .I~( ms.x(ai~ 172 -) ) >t) dt. o i=0,1 om 00 As in the evaluation of (2.13), the integrand is the sum of the probabilities of the inequality holding for i = 0 and for i = 1 . In the case i = o, for example, this equals s \ 1 s ) + 0 (m-1 /2 ) , n.. . ( Tm > t + -rf t -'a ~ 72 =- ~ 72") C • \ z > =- + ~ 1/2 am a0 om a0 om 1 where Z is standard normal, by virtue of the Berry-Esseen theorem [3] and the fa.ct that v~1 and~(IT1 13 ) are bounded awey from O and 00 , respectively. ~~ ~ the first ~ i Snee a1 a ~1/2 n --and hence ~/'!t s1 a m1/2 -- tends to -r, term on the right-hand side converges to P{a0 (z+r) > t). Together with a ~irn1Jar result for 1 = 1, this shows that the integrand in (2.36) converges pointwise to P( max (a1 ( z + r) ) > t). Using Chebyshev' s 1::0, 1 inequality and the boundedness of ~ a 1 -1 and ~ a 1~ s,nt ~ m1/2 , the integrands - 2 1 - in (2.36) are seen to be bounded above by a :f'unction that goes to 0 -2 like t as t ➔ 00 • Therefore, by the dominated convergence theorem = ~ ~a ~1 /2 E max:,ai r,:, ( Z + ~)) + (~1 /2) n - n r o n . (2.37) i=O, 1 The evaluation of (2.13) given in section 2.1 shows that (2.37) is equivalent to (2 . 8). To prove (2.8) it remains only to establish (2.26), which is contained in the followinr5 lemma. (also to be used in the next section). Lemma 2. 4. Let B be a positive constant. Then 1 P (M ~ m) ~ o(n ) 8 uniformly for I Proof. 0 - el < B n 1 2 / • It suffices to show Pa(Tk ~ Uo(k)) = o(rt2 ), uniformly in k and I 0 el ~ - B n 1 2 / , k = 1, ... ,m (2 . 39) with a similar bound for Tk ~ u1(k), since (2.38) follows by summing over k = 1, ... ,m. The boundedness of a0 together with (2.17) and (2.19) imply there is a positive constant c such that u (k ) ~ c ~1/2 n log ~ n =y 0 for all k < m. For a:rry t > o, Applying Chebyshev 's inequality to the right-hand side yields -22- Pe(Tk ~ ~) ~ exp(-yt)(Ee(exp(tT,)))k = exp(-yt + k(b(t + e) - b(8) - tb' (l'))). Using a Taylor expansion of b(t + 8) about e, the continuity and boundedness of bn(e) imply Expanding b' (e) about l s1m1Ja.rly yields a constant for some q > o. q' > O such that ~1/2 2 Pe ( Tk ~ y) ~ exp(-yt + ktq'.i,n + qkt ). 1 Replacing k by non the right-hand side and setting t = 2/(c n. / 2 ) shows P (T 8 > U(k)) < n 2 exp(~ + 2 4' B) k- - 2 C c for any k ~ m, which yields (2.39). 2.4 Proof of (2.9) The proof of (2.9) is divided into two parts, the first being to show that there is a B >Osuch that Only the case e >l will be considered, as the case e <l is similar. For B' > O (to be chosen below), there is a B >Osuch that 0 > l + B 1/ 2 implies n Eeto(e, 1) ~ Io + B' n 1/ 2 • (2.41) -23~e same analysis which established (2.23) in Lemma 2.1 shows that the expected excess of ~ M0 over log a0 -1 is at most 2 (e - e0 ) a2(e) (2.42) E t (e, 1) 8 0 For 8 > ')tti + B ~n 1/2 , (2. 42 ) is bounded, so that by (2. 4 1 ) and Wald's equation EJA- ~ E0ttiO ~ 1' log a 0 -1 ,~-i/2 + 0(1 ). 0 +Bn Replacing log a O- 1 according to (2.18) and using the fact thats is of order ~1/2 n yields ~n + ~~ ~ aOs E M < -----,,--..::,----,,+ 0 (1 ) 8 ,~-1/2-:::!. -1 1 + B n r0 1 2 Since s ~ -r o n / by virtue of (2. 19), this last impl.ies ~ < ,,.,,, -1 + ~S.c:f~ ~'0'1/2 c~1/2) • E "l,J m ~ n - B i a1n +on 0 8 (2.43) Choose B' sufficiently large so that (2.40) follows from (2.43). For the remainder of this section, J(B) will denote the interval of 9 values given by le - al < B r 1 2 / • ~e next lemma parallels Lemma 2.2 by establishing a bound on the conditional. expectation of Mgiven Tm. On the event (M > m} Lemma 2.5. E 8 (l!IT ) <n m - uniformly fore in J(B). 1 2 max (ai(Tm - s)) + o(n. 1 ) i=O, 1 {2.44) -24Proof. N and 0 Assume T > m- s, the proof for Tm < s being similar . Ko as in the proof of Lemma 2 . 2. Define Under e the expected excess of N over K0 is boun:led above by (2.42 ), and is thus bounded 0 uniformly on J(B) (since E t (l', 1 ), being continuous and positive at 8 0 ~ is eventua.lly bounded below by a positive number for 8 in J(B) ) . e, Hence E (MjT) < m + E N < m + 8 m 80 - uniformly for 8 in J(B) . (n - a 0 (T m • - s) - m)I 0 (1) + 0(1) (2 .45) E t (e, 1 ) 0 0 Si nce the ratio of I (e) to E t (e,1) is 0 8 0 1 2 1 + o(n / ) uniformJ.y for 8 in J(B), and n - a (Tm - s) - m :Sn - m :S 0 1 2 O(n / log n), (2. 45) implies Ee(MIT) m -<n - ao(Tm - s) + O(log n) uniformly for e in ~ (B), which yields (2. 44) for the case T > s, m- proving the lemma. From (2.44) Eji. ~ ~ n -a n 1 2 1 2 / Ee( max Ca1(~m~~/2) )l[M > m}) + o(n / ), i=O, 1 a n where l{.} denotes the indicator :f'unction and the inequality holds uniformly for 8 in J(B). To complete the proof of (2.9) it will suffice to show (2 . 46 ) ~ inf E( max (a (z + r))) r i=0, 1 1 - o(1) uniformJ.y for 8 inJ(B), since the right-hand side is at least -25(a0 ·• a1 ),:p(r) + o(1) by the argument eval.ua.ting (2.13). To prove (2.46), note that by arguing as in the proof of Lemma 2.2, fort> 0 T - ,..~ Pe( max (ai(~m~1/~) > t) i=O, 1 er n uniformly for a in J (B). Since P ('M ~ m) ➔ 0 uniformly by Lemma 2.4, the last relation 8 yields for fixed L > O (2.4 7) uniformly for e in J(B). Because + m1/2;;-l/2E T = + m1/2cr- 1/ 2 (b' (e) - b' (l')) 8 1 is bounded for 8 in J(B), the.re is a Q such that the integre.l on the r r right-hand side of (2.47) is at least inf lrl~ f o P( max (a (Z + r)) 1 > t) dt 1=0,1 (2.48) J max (a (z + r)) > t) dt - JL g (t) - Ir!~ O i=0,1 00 > inf' 00 P( 1 dt where g( •) is an integrable f'unction which can be chosen to dominate the integrands (since the range of r is bounded). (2.47) and (2.48) establiflh (2.46) to within the last term in (2.48), which can be :ma.de arbitrarily small by choosing L large. -26Thus, (2.46) follows and the proof of (2.9) and, hence, Theorem 1 is COIDJ?lete. 2. 5 Refinement The actu.aJ. error probabilities of the 2-SPRT M can be evaluated asymptotically using the relat ions P 9• l i = 0,1. (reject a.)= . l Using (2 .1 9) and the limit distribution of Tm' 1l(reject e0 ) is asymptotically P(Z > -r) =a,/(a, -ao). Since to(e,M) - logao_, is the excess over the boundary when e0 is rejected, Theorem 5 of [10] then shows for the nonlattice case that where 1(1!', e0 ) is defined in [ 5]. A similar expression holds for the other error probability. In practice it seems advisable to use this information in defining the test, so that the actu.aJ. error probabilities attained will be close to those desired. The following formulation, used for the calculations in Chapter 4, is recommended for practical use. and Define -27Choose~* to satisfy log (A 0 (cp*)) - 1 =------ , IO(cp*) and let n(tp*) be the common value of the two sides. m= cp* + Let r(5e*) a((?*)(n(t9*)) 1/2 N = M(~,A0 (tp),A1 (cp')). Theorem 1 now holds for N, with a 0 and a 1 replaced by A0 c;') and and use the 2-SPRT A1 {;), and n, a, ai and r determined by ~- The proof of Theorem 1 goes through nearly unchanged, it being necessary only to modify the derivation of (2 .19 ), using the fact that the ratios log A (~* )/log Ai(cp) 1 tend to 1. -28- 3. Three-Stage Tests and the Kiefer-Weiss Problem In this chapter a three-stage test designed to imitate a sequential likelihood ratio test (SLRT) is defined so that it 1 1 minimizes the maxim.um expected sample size to within O(y / 4 log y- ) where y is defined as log a 0 -1 + log a 1 - 1 . It is assumed that condition (2 . 1) holds as in Chapter 2. For any (n,S ), n = 1,2, ... , define i to be the solution to n n b' (8) = sn/n if b' (8 0 ) < sn/n < b' (8 1 ). If sn/n ~ b' (a 0 ) define "0n = e0, and if SnI n -> b '( 8 1 ) define "8n = e1 . "en is well-defined since b' (8) is strictly increasing, and it maximizes the likelihood function 8Sn - nb' (e) on [e0 ,a 1 ]. Note that (3. 1 ) in which case en is the maximum likel:ihood estimate of e. A ,. Given A0 and A1 in (0,1) the SLRT consists of the stopping time N = smallest n (or~ if there is non) such that for i = O or 1, (3.2) and the decision rule D , which r ejects e0 if (3.2) holds only for i = o, and rejects e1 if (3.2) holds only for i = 1. In the case that both inequalities hold, any fixed rule can be used to decide between 80 and 01 . SLRT' s have been studied by Schwarz [ 14], Wong [ 19] and Lorden [ 9 ]. Lorden gives a concise SUIIIID8XY of the results of Schwarz and Wong in his paper, where he extends Wong's results and shows that -29the SLRT with error probabilities o: , o: 1 has expected. sample sizes 0 1 exceeding n(o:0 ,o: 1 ) by at most M lo~og q- uniformly in e, where q = min(o: 0 ,o: 1 ) . To insure that the SLRT has error probabilities at most o: 0 and o: 1, define r(e) = min I.(e) and choose 1 i=0,1 Ai = ai / D log ai -1 i ,., o, 1 (3.3) 1 where Dis chosen to satisfy D/log D ~ 6(1 + (min(I(8))- ) as in Theorem 1 of [ 9 ). In this chapter 8* is defined by the relation (3 .4 ) a.nd n* is the common value of the two sides. Let m* = [n*] + 1. Then the SLRT can take at most m* observations. To see this, note that if, sa:y, em*~ 8*, then ;. ~ m* I 0 (em*) ~ n* r (8*) 0 = log A -1 0 , ;. and the case em*< 9* is similar. Final.ly, under condition (2.1), the ratio y/n* is bounded awa:y from O and 00 • -30The three-stage test (N(A0 ,A 1 ), D) is defined as follows: (i) Take (3. 5) observations and stop if (3.2) holds, deciding as D prescribes. (ii) otherwise, continue to time (3.6) ,- = . min ( m*, 1 l.=0,1 ,. If (3.2) holds, stop and use D. (iii) otherwise, continue to time m* e.nd follow D. Note that case (iii) arises only if,-< m*. By (3.4) and the monotonicity of the information numbers, ,. if em~ 8* then the term inside the greatest integer function in (3.6) is minimized by i = o, and if\_< 8* it is minimized by 1 m 1. ,. ,. Assume e1 > 0m -> 8*. If 8n stays close toem for n = m+1,m+2, ... , then .. so when n reaches ,- (3.2) should be satisfied. The extra term of 1 (n*) / 4(1og n*) 3/ 2 in the definition of Tis designed to insure that the three-stage test will end with high probability at time,-. Let A routine calculation shows that there exists an A small enough so that -31- for aJ.l 8 in J(A), i = 0, 1. Fixing this A, note that if 8m E J(A) n (80,8 1) then (3 . 1) and (3.4) imply A -1 A t 1 (8m,m) = mI.(8) < log Ai , 1. m i = 0,1, so that N(Ao,A,) > m. For the Ai given by (3.3), (N(A0,A 1 ), D) is in In addition, if (2.1) is satisfied, then Theorem 2. ~T(a0,a1 ). sup E N(A0,A1 ) = n(a0,a ) + o(y 114 (1og y) 3/ 2 ) 1 8 (3.7) 8 (3.8) Proof. To show that the three-stage procedure is in J"(a0 ,a 1 ) , note that in the proof of Theorem 1 of [ 9 ] , Lorden shows that for the SLRT, P8i (reject ei) ~ P8i (ti(~n,n) ~ log Ai-l ~ ai for some n ~ m*) for i = o, 1 • Since (N(A0 ,A 1 ), D) can reject e1 only if ti(; ,n) ~ log Ai-l for 0 some n ~ m*, its error probabilities are likewise at most a 0 and a 1 . Using Theorem 1, (3 . 8) follows immediately from ( 3. 7). The proof' of (3.7) consists of establishing the following three relations. uniformly for 8 E J(A/2). -3214 2 EeN(AO,A1) - E8M(8,Ao,A,) ~ O(y / (1og y)3/ ) (3.10) uniformly for 8 € J(A/2). (3. 11) (3 .9) and (3.10) show that E N(A0 ,A ) ~ n(a ,a ) + o(y1/ 4(1og y) 3/ 2 ) 1 0 1 8 uniformly for 8 € J(A/2), and this combines with (3.11) to give (3.7). To verify ( 3. 9), note that the method of proof in Lemma 2. 1 still applies when M(e,a0,a1 ) is replaced by M(8,A0,A1 ), so in fact the left-hand side of the inequal.ity in (3 .9) is at most 1 2 2 L (ai ( 8 )o- ( 8) + log ( 1 + Dilog ai -1 ) bO I ( ) i 8 ) , which establishes (3. 9). For the proofs of (3.10) and (3.11), first note that the proof of Lemma. 2.4 shows that for any 8 € (e 0 ,e 1 ) and for all k ~ n*, 1 2 2 P (l3it - kb' (e)I ~ c (n*) / log n*) ~ (n*)8 exp(~), (3.12) C where q is a constant independent of 8 (since it depends only on b 0 (8) being continuous and bounded on (e0 ,e 1 )). The same proof also establishes for all k with m < k < m* that - - 12 P (1sk - Sm - (k - m)b' ( 8)1 ~ c(n* - m) / 1og n*) 8 2 = 0( (n*)- ) uniformly in 8 on (8 0,8 1 ). (3. 13) -33Let and where Q1 and'½ are constants to be determined. It will next be established that for sutticiently small'½, Also, (3.15) uniformly in 8. It follows that (3. 16) uniformly in e. To see (3.14) note that if N(A0,A1 ) > m and ~m ~ 8*, then either T = m* (so that (3.14) is trivial) or else + (n*) 1/4 (log n*) 3/2 log Ao -1 > --- , I (e,.) 0 (3.17) - the last inequ.e.lity holding provided'½ is chosen sufficiently small. Arguing as in the verification following (3.4) that the SLRT takes at A -1 most m* observations, (3.17 implies that t 0 eT,T) ~ log A0 , which ) yields (3.14). The case where ( 8m < 8* is similar. To establish (3.15), first assume 8 € [e0' ,e 1'] where!< 80' < e0, and e1 < e1' < i are fixed, and note that for m ~ n ~ m* s s m n-1( S -S - (n - m)b' (e)) + m - n(s - mb' (e)). -n- - = n m n m mn m -34Since b"(8) is bounded on [e 0' ,e 1' ], (3.13) and (3.12) extend to show that therefore max lsn - sml = o((n*)-3/4{1og n*)3/2) + O((n*)-l(log n*)2) m<n<ln* n m = O((n*)-3/4(1og n*)3/2) (3.18) with probability at least 1 - O((n*) Now, -1 )uniformly for 8 in [00' ,9 1' ]. e,n which is a function of Sn/n, has bounded derivative on · (e0 ,e 1 ) since b*(e) is bounded away from o, and is constant for sn/n ~ e0 or sn/n::: e1 . Hence (3.18) implies that (3.15) holds uniformly fore E [e 0' ,e 1' ]. To show (3.15) holds uniformly for all e, note that if, say, 8 > e1' then <e = .•. = 8m* = 8 m A p ::: P8 ,(Sn - nb' (8 1')::: 0 n for n = m, ... ,m*) 1 where p = b' (e 1') - b'(e 1 ) > o. By (3.12) this last probability is 1 at lea.st 1 - o{(n*)- ). A similar argument for e < e0' shows that (3.15) is uniform for all e. The derivation of (3.11) can now be completed. The basic idea is that the second stage when 8* is true will with high probability be at least as large as the second stage when any 8 outside of J(A/2) is true. Let e-(c) and e+(c) denote the left-hand and right-hand endpoints of J(c), respectively. Choose B small enough so that -35- (3.19) Suppose e > e+(A/2). Then by (3.12), the last part of the argument for (3.15), and (3.16), the probability is at least 1 - O((n*)- 1 ) that both "em> e+ (A/4) and N(A 0 ,A 1 ) ~ T· In this case, N(A0,A ) ~ min(m*, LHS + (n*) 1/ 4(1og n*)3/2 ), 1 (3.20) Now if e* is true, (3.12) implies that with probability at least 1 - O((n*)-2 ), € J(B), where LHS stands for the left-hand side of (3.19). e m in which case (3.21) where Rl:IS stands for the right-hand side of (3.19). (3.11) follows from ( 3. 19) - (3 .21 ) and a similar argument for e < e- (A/2). To complete the proof of Theorem 2 it remains only to show (3.10). Fore E J(A/2) and k ~ n*, 18k_ - kb' (e*)I ~ lsk - kb' (e)I + 12 1 o((n*) / log n·*), so that by (3.12), P (E 1 ) :::: 1 - o((n*)- ) 8 uniformly for e € J(A/2). With (3. 15) this shows (3.22) uniformly for e E J(A/2). It will be shown that for a Q1 chosen sufficiently small, (3.23) -36on E1 n ~, uniformly for 8 € J(A/2). Since N(A0 ,A1 ) ~ m*, relations (3.22) and (3.23) yield (3.10). It will first be established. that for 8 € J(A/2) If 8 € J(A/2 ), then for sufficiently small a 0 ,a 1 , 8 is sufficiently close to 9* so that in the relation Hence on E1, tor k < m the bracketed expression is positive. 12 t 0 (e,k) ~ (e-e 0 )Q1 (n*) / 1og n* (3.24) + m{<e-e0 )b' (e*) - (b(e) - b(e 0 ))}. The right-hand side of (3 .24) is the value of t 0 (e,m) when Sm= mb'(e*) + Q (n*) 1 1 2 1 10g n*. By the argument following the definition of J(A), it follows that for sufficient1y smal.l Q1 this t 0 (e,m) is less than log A0 - 1 . Thus on E1 n ~ and for 9 E J(A/2), M(e,A0,A1 ) does not reject e by time m and, similarly, does not reject e1 by time m. 0 In ad.di tion, for sufficiently smal.l Q1, ISm - mb' (8*) I ~ Q1 ( n*) 1/2log n* implies 8m E J(A), so that N(A0,A1 ) > m also. Let M denote M(8,A0 ,A 1 ). If M > m* then (3.23) holds trivially. Otherwise, for sufficiently small a 0 ,a1, on the event E1 n ~ "'9i~ E (e ,e ) and hence either MI ( 8) -1 or MI ("'8M ) ~ log A - 1 • 0 1 0 "'M ~ log A0 1 1 Therefore, for all 8 € J(A/2), on E1 n ~ -1 log Ai ) _, M > min ( - - - > min - i=0,1' I 1 (~) - 1=0,1 (log Ai ) Ii(em) -37Using the definition of T and the fact that M ~T - 1 O{y / 4(1og v) 3/ 2 ) ~ 0 ,A1 ) ~Ton~ gives N(A 1 N(Ao,A,) - O(y / 4(1og y) 3/ 2 ). Since the lower bounds on M do not depend on 8, this proves (3.23) and concludes the proof of Theorem 2. -384. 4.1 Comparison of 2-SPRT' s with Kiefer-Weiss Solutions Summary of Resul.ts Calcul.ations were carried out comparing the 2-SPRT as described in section 2.5 with Kiefer-Weiss solutions, in the case of testing the parameter 8 of the exponential density. f 8 (x) = e exp(-ex), e > o, x > o. In testing 8 = e0 against 8 = e1, it can be assumed that e0 = 1, since that can always be achieved by scaling the X's . Desired values of a0 and a 1 were used to define the 2-SPRT 'if and 7,;. E;}i, sf E8N and the actual error probabilities a 0' and a 1' of the 2-SPRT were ccmputed. nien, as described in section 4.2, the boundaries of the Kiefer-Weiss solution with error probabilities a 0' and a ' were calcul.ated, along with its operating characteristics. 1 This proviided the values of n(a 0' ,a 1') used to compute the efficiency n(a0' ,a 1' )/sf E i of the 2-SPRT. 8 In Figure 1 are the boundaries attained by this process for testing e0 = 1 against e1 = 1.5 with desired error probabilities of a 0 = a 1 = .05. The straight line bounda.ries are those of the 2-SPRT, which had actual error probabilities of a 0 ' = .045 and a 1' = . 044. The curved boundaries are those of the corresponding Kiefer-Weiss solution. For col'IV'enience these were drawn in the (n,T) plane where n Tn = Sn - .8n, Sn = x1 + ••• + X. n To conduct the 2-SPRT, observations are taken and the points (1,T 1 ), (2,T2 ), ... plotted until one of the 2-SPRT boundaries is crossed. The Kiefer-Weiss test is conducted -8 -4 -2 oI 2 4 6 50 FIGURE 1. 4 ... 4 ,..,.. a 0' = 4.~ and a 1 ' = 4.~. 2-SPRT and Kiefer-Weiss boundaries for testing 0 = 1 against e = 1.5 with error probabilities 0 1 Reject 8 0 Reject e 1 n = x1 + ... + xn - .8n T ,... 1 200 n I w I \0 -40similarly. In both cases, if the top boundary is crossed, then e1 = 1.5 is rejected, while if the lower boundary is crossed, e0 = 1 is rejected. For this test sup E 11 = 51.72, whereas n(a 0' ,a 1') = 51.39, 8 8 resulting in an efficiency,of 99.3%. A typical feature is that the maximum possible number of observations with the 2-SPRT is much smaller than that of the Kiefer-Weiss solution. The truncation point of the 2-SPRT is at 113 observations, while that of the Kiefer-Weiss solution is at 194 observations. The most extensive calculations were carried out for the case e1 = 2 and are recorded in Table 1. The 2-SPRT is seen to have an efficiency of over 9% over a broad range of desired error probabilities, with both the efficiency and the closeness of the actual error probabilities to the desired ones decreasing as the ratio of a 0 to a 1 becomes extreme. of The last column records the values F.f, which are in general within~ of sr EeN' indicating that ~ indeed nearly lllBJ[imizes E 'ii1. 8 Lorden indicates in [8] that in the symmetric normal case the observed efficiencies depended on the desired error probabilities, but that over a broad range they depended hardly at all on the parameter values. To confirm this for the exponential density, two cases were computed for e1 = 1.5. As stated earlier, the a = a 1 = .05 0 = .1, a 1 = .05 obtained case resulted in 99.3% efficiency. The case a 0 a ' = .11 and a ' = .035 with an efficiency of 99.2%. Both of these 0 1 efficiencies agree exactly with the corresponding cases for e1 = 2. In addition to the characteristics aJ.ready mentioned, E N and 80 E Nwere computed. For the exponential case Lorden and Eisenberger [12) 81 -41- TABLE 1 Error probabilities and efficiencies, e0 = 1, e1 = 2. a ~ ~ % E..N ef:f'icienci fl) 14.95 99.2 14.88 18.96 19.08 99.3 19.00 .6 25.65 25.83 99.3 25.76 .7 5.8 26.98 27.24 99. 1 27. 11 .06 8.2 37.02 37.60 98.4 37. 35 ao a1 a' 10 5 9.5 5 5 5 n(a 0' ,a1' ) sr E8N 3.3 14.84 4. t 4. 1 1 5. 1 1 5 .1 5 0 1 I ai = desired error probabilities (in~). a.'= actual error probabilities attained by 2-SPRT (in%). 1 n(ao' ,a, I ) = inf{ sr EeN} where the inf is taken over all tests with error probabilities at most a 0 ' ,a 1 ' • efficiency= n(a0 ' ,a 1' )/s~p E N. 8 N, q;' = 2-SPRT and 'q, as defined in section 2.5. -42give an accurate approximation to the expected sample sizes of the SPRT with error probabilities a ' and a 1' . 0 Typical results are recorded in Table 2, and indicate that the loss in performance of the 2-SPRT is fairly mild. 4.2 Method for Computing Kiefer-Weiss Solutions Given a 0' ,a 1', it is desired to find a procedure which attains n(a ' ,a ' ), i.e. to solve the Kiefer-Weiss problem, which i s related 0 1 to the modified Kiefer-Weiss problem in the following way. If (N,D) solves the modified problem for a 0 ' ,a ' and e = e , say, and if 1 2 in addition sup E N = E N, then (N,D) solves the Kiefer -Weiss problem. 82 8 8 To see this, note that for any (N' ,D') in :r(a 0' ,a 1' ), s~p EeN' ~ E82lf ~ E 82 N = sup E N. e 8 For any test T = (N,D), let a 0 (T) and a 1 (T) denote the error probabilities of T. Kiefer and Weiss [5] showed that finding all solutions to the modified problems of minimizing E N is equivalent 82 to finding all procedures which, for some positive constants p0 , o1, o stumning to 1, minimize 2 P~o(T) + p,a,(T) + P2Ee N 2 over all tests T. This is known as a Bayes problem and p = (p 0 ,o 1,o 2 ) is called the prior distribution of e. If n observations have been taken and Sn= s, the vector p(n,s) = (p 0 (n,s),p 1 (n,s), 02 (n,s)) where -43- TABLE 2 Comparison of expected sample sizes of 2-SPRT and SPRT N, e0 = 1, e1 = 2. 0 0: ' 1 Ee ~ N 0 Ee N 0 Ee ~ N 1 E N 81 9.5 3.3 10.60 9.93 12.33 11. 15 4. 1 4. 1 11.47 10.36 16.27 15.08 5. 1 .6 17.30 16.08 18.21 15.22 .7 5.8 12.33 10.07 24.38 23. 13 0: ' -44r:,.ein exp(-e.s) •1 1 p. (n, s) = 1 -=-------r. p .e.nexp(-ejs) j=O J J is called the posterior distribution of e. The Bayes problem is characterized by the following "stationarity" property [16]: Given that n observations have been taken and S n = s, the optimaJ. test proceeds so as to minimize pO(n,sp O(T) + p1 (n,sp 1 (T) + p2 (n,s)E N', 8 (4. 1 ) 2 where N' denotes the number of observations taken from now on. Another way to state this property is that at each (n,s), the optimal procedure either stops or it takes one observation x and then proceeds from (n + 1, s + x) according to the optimal procedure from that point. Let R(n,s) be the infimum of (4.1) over a.11 tests, R1 (n,s) the infimum of (4.1) over all tests which take at least one observation, and define RO(n,s) = min(p O(n,s),p 1 (n,s)). R is known as the Bayes risk, R1 is called the continuation risk, and RO is the stopping risk. As a result of the stationarity property the following relations hold [ 16]: (4.2) and 2 JO R(n+1,s+x)f 0i(x) dx. 00 R1 (n,s) = p2 (n,s) +i~O 0 i(n,s) The second relation is particularly important. If it is assumed that at least one observation will be taken from (n,s), then 2 ~. i=O 0 .(n,s) 1 f 9i (x) (4 .3) -45is called the posterior distribution of the next observation Xn+ 1 . (4 .3) sa~rs the continuation risk is the risk (or "cost") incurred by taking the next observation, plus the expectation of the Bayes risk R(n + l,s + x) under the posterior distribution (4.4). (l+.3) also forms the basis for caJ.culating solutions by "backward" induction [2]. For a given p0 ,p 1,p , there is an n0 such that 2 p (n ,s) > min(p 0 (n ,s),p 1 (n0 ,s)) for alls, so that R1 (n ,s) > R0 (n0,s) 2 0 0 0 for alls. Hence the solutions to the Bayes problem can take at most n0 observations. R(n 0,s) = R0 (n0,s) is easily caJ.culable for alls, so that numerical integration and (4.3) can be used to compute R (n0 - 1, s) for any s, and (4 .2) provides the value of R(n 0 - 1, s) . 1 After calculating R(n0 - 1, s) on a suitable grid of s-values, the induction proceeds backwards to n - 2, and so on. For each n, the 0 upper boundary of the test is calculated by finding the s where R1 (n,s) - 01 (n,s) changes sign, and the lower boundary by finding the s where R1 (n,s) - o0 (n,s) changes sign. Once these boundaries have been located, further numerical integration yields the operating characteristics. In fact, every set of operating characteristics so obtained provides the error probabilities and expected sample size of some solution to the modified Kiefer-Weiss problem. To see this, assume that from (n, s) the calculations yield a 0*,a,* and m* for the values of the error probabilities and the expected sample size. minimize (4.1), so that for any T = (N, D), These values -46p 0 (n,s):x 0 (T) + p 1 (n,s):x 1 (T) + p2 (n,s)E 8 N 2 2: p 0 (n,s):x 0* + p 1 (n,s):x 1 (T) + p2 (n,s)m*. *, then m*::: E8 N. Hence if a 0 (T) ::: a 0* and a 1 (T) ::: a 1 2 For each n in the range of the computations, a Kiefer-Weiss solution is found by obtaining an s 1 between the lower and upper boundaries so that the optimal test starting from (n,s 1 ) has its maximum expected sample size at 8 = e2 . If a 0 * and a 1* are the computed error probabilities, then the expected sample size equals n(a 0*,a,*). (It seems reasonable that such an s 1 can be found, because one expects that for s near one boundary, the maximizing 8 should be smaller than e2 , while for s near the other boundary, it should be larger.) Unfortunately, this routine requires large amounts of computer time and, because the relationship between p ,o 1,o 0 2 and the attained error probabilities is unknown, the procedure must be iterated in order to obtain the solution with the desired error probabilities a 0' and a 1'. Not only is the program. laborious to write, but it is dependent upon the family of distributions being tested. Thus, caJ.culation of Kiefer-Weiss solutions by this method proves impracticaJ. for standard use. The much simpler 2-SPRT appears to provide a mare convenient, yet efficient procedure. -47References [1] Anderson, T. w. (19€,o). A modification of the sequential probability ratio test to reduce the sample size. Ann. Math. Statist. l!_,, 165-1 97. [2] Chow, Y. S., Robbins, H. and Siegmund, D. (1971). Great Expectations: The Theory o:f' Optimal. stopping. Houghton Mif:t'lin, Boston. (3] Feller, W. (1971 ). An Introduction to Probability Theory and its Applications, Vol. 2. [4] Hoeffding, w. (19€,o). Wiley, New York. Lower bounds :for the expected sample size and the average risk of a. sequential procedure. Ann. Ma.th. Statist. l!_,, 352-368. [5] Kiefer, J. and Weiss, L. (1957). Some properties of generalized sequential probability ratio tests. Ann. Ma.th. statist. g§_, 57-75. [6] Koopman, B. o. (1936). statistic. [7] Lai, T. L. (1973). On distributions admitting a sufficient Trans. Amero Math. Soc. J2, 399-409. Optimal stopping and sequential tests which minimize the maxmum expected sample size. Ann. statist. !, 659-673. [8] Lorden, G. (1976). 2-SPRT's and the modified Kiefer-Weiss problem of minimizing an expected sallij?le size. Ann. Sta.tist. ~ 281-291. -48[9] Lorden, G. (1972). Likelihood ratio tests for sequential k-decision prob1ems. [10] Lorden, G. (1977). Nearly-optimal. sequential tests for finitely many parameter values. [1 1 ] Ann. Math. statist. ~ 1412-1427. Lorden, G. (1970) . Ann. Statist . .2,, 1-21. On excess over the boundary. Ann. Math. statist. !!-1, 520-527. [12] Lorden, G. and Eisenberger, I. (1973). Technometrics .!2., 167-175. rate increases. (13] Detection of failure Neyman, J. and Pearson, E. s. (1933). On the prob1em of the most efficient tests of statistical hypotheses. Hlil. Trans. Roy. Soc., Ser. A, 231, 289-337. (14] Schwarz, G. (19€:e). Asymptotic shapes of Bayes sequentiaJ. testing regions. [15 ] WaJ.d, A. (1947). Ann. Ma.th. statist. 33, 224-236. Sequential Analysis. [16] Wa.ld, A. and Wo1fowitz, J. (1950). sequentia.l problems. [17] Wiley, New York. Bayes solutions of Ann. Math. Statist. ~ 82-99. Wa.ld, A. and Wolfowitz, J. (1948). Optimum character of the sequential probability ratio test . Ann. Ma.th. statist . .!2, 326-339. [ 18] Weiss, L. (19€:e). On sequentiaJ. tests which miniJnize the ma.xi.mum expected s8llU)1e size. 551-566. J. Amer. statist. Assoc. 57, -49[19] Wong, S. P. (1968) . Asymptotically optimum properties of certain sequential tests . 1244-1263. Ann. Ma.th. statist . .J.2_,