Sequential analysis

A branch of mathematical statistics. Its characteristic feature is that the number of observations to be performed (the moment of termination of the observations) is not fixed in advance but is chosen in the course of the experiment depending upon the results that are obtained. The intensive development and application of sequential methods in statistics was due to the work of A. Wald. He established that in the problem of decision (based on the results of independent observations) between two simple hypotheses the so-called sequential probability ratio test gives a considerable improvement in terms of the average number of observations required in comparison with the most-powerful test for deciding between two hypotheses (determined by the Neyman–Pearson lemma) for a fixed sample size and the same error probabilities.

The basic principles of sequential analysis consist of the following. Let be a sequence of independent identically-distributed random variables with distribution function which depends on an unknown parameter belonging to some parameter set . The problem consists of making a certain decision as to the true value of the unknown parameter , based on the results of observations.

A space of terminal final decisions (for the values of the parameter ) and a termination rule which determines the time when the observations are stopped and the terminal decision is taken, lie at the basis of any statistical decision problem. In classical methods the time is non-random and is fixed in advance; in sequential methods is a random variable independent of the "future" (a Markovian time, a stopping time). Formally, let be the -algebra generated by the random variables . A random variable assuming the values is called a Markovian time if the event for any (). Let be the family of all measurable sets such that for any (cf. also Markov moment). If is interpreted as the set of events observed up to some random time (inclusive), then can be interpreted as the set of events observed up to the time (inclusive). A terminal decision is an -measurable function with values in . A pair of such functions is called a (sequential) decision rule.

In order to choose the "optimal" decision rule among all decision rules one usually defines a risk function and considers the mathematical expectation . There are different approaches to defining the optimal decision rule . One of them, the Bayesian approach, is based on the assumption that the parameter is a random variable with a priori distribution . Then one can speak of the -risk

and one calls a rule the optimal Bayesian (or -optimal) solution if for any other (admissible) rule. The most widely used form of the risk function is , where the constant is interpreted as the cost of a unit observation and is a loss function resulting from the terminal decision.

In Bayesian problems it is usually not difficult to find the terminal solution ; thus the main efforts are concentrated on finding the optimal termination time . Moreover, the majority of problems of sequential analysis fall into the following pattern of "optimal termination rules" .

Let , , , be a Markov chain in the state space , where is the state of the chain at the time , the -algebra is interpreted as the set of events observed up to the time (inclusive), and is a probability distribution corresponding to the initial state . It is assumed that by stopping the observation at the time one obtains the gain . Then the average gain resulting from termination at time is , where is the initial state. The function , where the supremum is taken over all (finite) termination times , is called the cost, and the time for which for all is called the -optimal stopping time. -optimal times are called optimal. The main problems in the theory of "optimal stopping rules" are the following: What is the structure of the cost , how to find it, when do -optimal and optimal times exist, and what is their structure? One of the typical results concerning these questions is discussed below.

Let the function be bounded: . Then the cost is the least excessive majorant of , i.e. the smallest of the functions satisfying the two following conditions:

where . Moreover,

is the -optimal time for any , the cost satisfies the Wald–Bellman equation

and can be obtained by the formula

where

In the case when the set is finite, the time

is optimal. In the general case the time is optimal if , .

Let

By definition,

In other words, one should stop the observations upon hitting the set for the first time. Accordingly, the set is called the set of continuation of observations and the set is called the set of termination of observations.

These results can be illustrated by the problem of deciding between two simple hypotheses, for which Wald has demonstrated the advantage of sequential methods as compared to classical ones. Let the parameter take two values 1 and 0 with a priori probabilities and , respectively, and let the set of termination decisions consist of two points as well: (accept hypothesis : ) and (accept hypothesis : ). If the function is chosen in the form

and one puts

then the expression

is obtained for , where

are the error probabilities of the first and second kinds, and denotes the probability distribution in the space of observations corresponding to the a priori distribution . If is the a posteriori probability of the hypothesis : with respect to the -algebra , then

where

From the general theory of optimal stopping rules applied to it follows that the function satisfies the equation

Hence, by virtue of concavity of the functions , , , it follows that there are two numbers such that the domain of continuation of observations is , and the domain of termination of observations is . Here, the termination time

is optimal .

If and are the densities of the distributions and (with respect to the measure ), and

is the likelihood ratio, then the domain of continuation of observations (see Fig. a) can be written in the form

and . : domain of continuation of observations : domain of termination of observations

Figure: s084600a

In addition, if , then the decision is taken, i.e. the hypothesis : is accepted. If, however, , then the hypothesis : is accepted. The structure of this optimal decision rule is the same also for the problem of decision between two hypotheses formulated in terms of a conditional extremum in the following way. For each decision rule one introduces the error probabilities , and fixes two numbers and ; let, further, be the set of all decision rules when , , and , . The following fundamental result was obtained by Wald. If and if among all criteria based on the likelihood ratio and of the form

there are and such that the error probabilities of the first and second kinds are exactly and , then the decision rule with and is optimal in the class in the sense that

for all .

The advantage of the sequential decision rule as compared to the classical one is easier to illustrate by the example of decision between two hypotheses : and : with respect to the local average value of a Wiener process with unit diffusion. The optimal sequential decision rule providing the given probabilities and of errors of the first and second kinds, respectively, is described as follows:

where and the likelihood ratio (the density of the measure corresponding to with respect to the measure corresponding to ) equals , and , (see Fig. b). : domain of continuation of observations : domain of termination of observations

Figure: s084600b

The optimal classical rule (using the Neyman–Pearson lemma) is described in the following way:

where

and is the solution of the equation

Since , , where

one has

Numerical calculations show that for ,

In other words, for the values of errors of the first and the second kinds considered, the optimal sequential method of decision between two hypotheses needs approximately half the observations of the optimal method with a fixed number of observations. Moreover, if , then

References

[1]	A. Wald, "Sequential analysis" , Wiley (1947) MR0020764 Zbl 0041.26303 Zbl 0029.15805
[2]	A.N. Shiryaev, "Statistical sequential analysis" , Amer. Math. Soc. (1973) (Translated from Russian) MR0445744 MR0293789 Zbl 0267.62039
[3]	A.N. Shiryaev, "Optimal stopping rules" , Springer (1978) (Translated from Russian) MR2374974 MR1317981 MR0445744 MR0293789 MR0283922 Zbl 0391.60002

References

[a1]	D. Siegmund, "Sequential analysis" , Springer (1985) MR0799155 Zbl 0573.62071
[a2]	R. Lerche, "Boundary crossing of Brownian motion: its relation to the law of the iterated logarithm and to sequential analysis" , Springer (1986) Zbl 0604.62075