Dynamic programming of some sequential sampling design

AbstractLet {xn} be independent random variables with a common distribution function F(x). We observe the xn sequentially and can stop at any time; if we stop with xn we receive the payoff fn(x1,…, xn). Problem: What stopping rule maximizes the expected payoff? It is shown that for fn(x1,…, xn) = xn − cn, where c > 0 is the cost per unit observation, the optimum stopping rule when the first moment of the xn exists is: Stop with the first xn > α where α is the root of the equation ∫γ∞(x−γ)dF(x) = c; the expected payoff is then α. This result is proved in Section II.Two directions of generalization of the problem will be given and discussed in the succeeding two sections.A more realistic version of the problem deals with the situation where the population from which random variables are drawn has an unknown distribution function. We shall treat in Section III the case in which the distribution is normal with known variance and unknown mean.Section IV is concerned with the problem of two populations. Here the problem is that of maximizing the expected payoff in, at most, N1 and N2 drawings from the populations Π1and Π2, respectively, when at each drawing we are free to choose between Π1and Π2. The results obtained in Section II are applied in this section to derive the optimal design of sampling.In this paper, we shall consider all these problems by means of discussions of the functional equations derived from the corresponding decision processes. Using techniques in the theory of dynamic programming [1] we shall determine the structures of the optimal rules for the problems