2448 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 45, NO. 7, NOVEMBER 1999Multihypothesis Sequential Probability RatioTests—Part I: Asymptotic OptimalityVladimir P. Dragalin, Alexander G. Tartakovsky, and Venugopal V. Veeravalli, Senior Member, IEEEAbstract— The problem of sequential testing of multiple hy-potheses is considered, and two candidate sequential test proce-dures are studied. Both tests are multihypothesis versions of thebinary sequential probability ratio test (SPRT), and are referredto as MSPRT’s. The first test is motivated by Bayesian optimalityarguments, while the second corresponds to a generalized likeli-hood ratio test. It is shown that both MSPRT’s are asymptoticallyoptimal relative not only to the expected sample size but alsoto any positive moment of the stopping time distribution, whenthe error probabilities or, more generally, risks associated withincorrect decisions are small. The results are first derived forthe discrete-time case of independent and identically distributed(i.i.d.) observations and simple hypotheses. They are then ex-tended to general, possibly continuous-time, statistical modelsthat may include correlated and nonhomogeneous observationprocesses. It also demonstrated that the results can be extendedto hypothesis testing problems with nuisance parameters, wherethe composite hypotheses, due to nuisance parameters, can bereduced to simple ones by using the principle of invariance. Theseresults provide a complete generalization of the results givenin [36], where it was shown that the quasi-Bayesian MSPRT isasymptotically efficient with respect to the expected sample sizefor i.i.d. observations. In a companion paper [12], based on thenonlinear renewal theory we find higher order approximations,up to a vanishing term, for the expected sample size that take intoaccount the overshoot over the boundaries of decision statistics.Index Terms— Asymptotic optimality, invariant sequentialtests, multialternative sequential tests, one-sided SPRT, renewaltheory, slippage problems.I. INTRODUCTIONTHE goal of statistical hypothesis testing is to classifya sequence of observations into one ofpossible hypothesis based on some knowledge of statisticaldistributions of the observations under each of the hypotheses.For sequential testing problems, the number of observationsManuscript received April 6, 1998; revised February 2, 1999. This workwas supported in part by the National Science Foundation under Grant NCR-9523967, by the National Institutes of Health under Grant RO1 HL58751, andby the Office of Naval Research under Grant N00014-95-1-0229.V. P. Dragalin is with the Department of Biostatistics, University ofRochester, Rochester, NY 14642 USA (e-mail: [email protected]).A. G. Tartakovsky is with the Center for Applied Mathematical Sciences,University of Southern California, Los Angeles, CA 90089-1113 USA (e-mail:[email protected]).V. V. Veeravalli is with the School of Electrical Engineering and theDepartment of Statistical Science, Cornell University, Ithaca, NY 14853 USA(e-mail: [email protected]).Communicated by M. L. Honig, Assicate Editor for Communications.Publisher Item Identifier S 0018-9448(99)07008-X.used (sample size) is allowed to be variable, i.e., the samplesize is a function of the observations. A sequential test picksa stopping time and a final decision rule to effect a tradeoffbetween sample size and decision accuracy.The majority of research in sequential hypothesis testing hasbeen restricted to two hypotheses. However, there are severalsituations, particularly in engineering applications, where itis natural to consider more than two hypotheses. Examplesinclude, among a multitude of others, target detection inmultiple-resolution radar [26] and infrared systems [13], signalacquisition in direct sequence code-division multiple accesssystems [37], and statistical pattern recognition [16]. It isthus of interest to study sequential testing of more than twohypotheses.It is well known that for binary hypotheses testing,Wald’s sequential probability ratio test (SPRT) is optimal, inthe sense that it simultaneously minimizes both expectations ofthe sample size among all tests (sequential and nonsequential)for which the probabilities of error do not exceed predefinedvalues (see, e.g., Wald and Wolfowitz [40], Chernoff [6], andLehmann [22]). Unfortunately, if, it is not clear ifthere even exists a test that minimizes the expected sample sizefor all hypotheses. Moreover, existing research indicates thateven if such a test exists, it would be very difficult to find itsstructure. For this reason a substantial part of the developmentof sequential multihypothesis testing has been directed towardthe study of practical, suboptimal sequential tests and theevaluation of their asymptotic performance, see [3], [5]–[11],[21], [25], [30]–[38], and many others. A model for studyingsuch asymptotics was first introduced by Chernoff [5], whereinhe studied the independent and identically distributed (i.i.d.)case and assumed a cost per observation that was allowedto go to zero. Generalization to non-i.i.d. cases (where log-likelihood ratios fail to be random walks) have been made byGolubev and Khas’minskii [18], Lai [23], Tartakovsky [31],[32], [34], [35], as well as Verdenskaya and Tartakovskii [38].For the binary SPRT, it is well known that renewal the-ory is useful in obtaining asymptotically exact expressionsfor expected sample sizes and error probabilities (see, e.g.,[29], and [41]). An approach to applying renewal theorytechniques to sequential multihypothesis tests was recentlyelucidated by Baum and Veeravalli [3], wherein they studieda generalization1of the SPRT to more than two hypothesesthat is motivated by a Bayesian setting. This quasi-Bayesian1This generalization also appears in other papers [18], [30]–[32] in variouscontexts.0018–9448/99$10.00  1999 IEEEAuthorized licensed use limited to: University of Houston. Downloaded on October 26, 2009 at 15:23 from IEEE Xplore. Restrictions apply.DRAGALIN et al.: MULTIHYPOTHESIS SEQUENTIAL PROBABILITY RATIO TESTS–PART I 2449multihypothesis SPRT (or MSPRT) was shown to be amenableto an asymptotic analysis using nonlinear renewal theory[41], and asymptotic expressions for the expected sample sizeand error probabilities were obtained in [3]. Furthermore, itwas established in [36] that the quasi-Bayesian MSPRT isasymptotically efficient with respect to expected sample