Efficient Robbins-Monro Procedure for Binary DataV. Roshan JosephSchool of Industrial and Systems EngineeringGeorgia Institute of TechnologyAtlanta, GA 30332-0205, [email protected] Robbins-Monro procedure does not perform well in the estimation of extreme quan-tiles, because the procedure is implemented using asymptotic results, which are not suitablefor binary data. Here we propose a modification of the Robbins-Monro procedure and derivethe optimal procedure for binary data under some reasonable approximations. The improve-ment obtained by using the optimal procedure for the estimation of extreme quantiles issubstantial.Some key words: Quantile estimation; Sequential design; Stochastic approximation.11. INTRODUCTIONIn many applications, interest centres on finding the threshold of a variable that will causecertain amount of successes, or failures, in the output. For example, an explosive designermay be interested in finding the level of shock necessary to make 99.99% of the explosivesfire (Neyer, 1994); see Joseph and Wu (2002) for another application. The problem can beformally stated as follows. Let Y be a binary response with probability of success M(x),where x is the variable whose threshold is of interest. The objective is to find the value θof x for which M(θ) = α, for given α. Usually M(x) is a distribution function obtained byassuming some distribution for a latent variable underlying the binary response, so that θcan be regarded as the α-quantile of this distribution. The function M(x) is unknown tothe experimenter, but the experimenter can observe Y at different values of x in order tofind θ. The objective is to devise an experimental strategy that will help one to estimateθ with minimum number of observations and with great accuracy. The experiment can beperformed by using a sequential design in which the x’s are chosen sequentially and areallowed to depend on the data already observed .One sequential design strategy known as stochastic approximation is to choose x1, x2, ···such that xn→ θ in probability. Robbins & Monro(1951) proposed the procedurexn+1= xn− an(yn− α), (1)where ynis the binary response observed at xnand {an} is a pre-specified sequence of positiveconstants. Robbins & Monro showed that xn→ θ in probability if∞Xn=1an= ∞, and∞Xn=1a2n< ∞. (2)2Robbins & Monro recommended the simple but non-optimal choice an= c/n for someconstant c. Based on the results of Chung (1954), Hodges & Lehmann (1956) and Sacks(1958), the procedure is fully asymptotically efficient with an= {n˙M(θ)}−1under certainconditions, where˙M denotes the first derivative of M; for use in practical implementationssee for example Wetherill and Glazebrook (1986). The optimal choice of anin small sampleshas not been investigated, although in most experiments this is the most interesting case.Wetherill (1963) showed through simulation that the Robbins-Monro procedure worksquite well for α = 0.5, corresponding to LD50, but performs very poorly for extreme quan-tiles, even with a number of modifications. Cochran & Davis (1965) and Young & Easterling(1994) obtained similar conclusions based on extensive simulation results.Although the Robbins-Monro procedure is not restricted to binary data, binary datapossess two properties that can be exploited to improve the procedure: the variance of Yis a function of x given by M(x){1 − M(x)}, and M(x) is a distribution function. In thisarticle we make use of these properties to produce optimal Robbins-Monro procedures forbinary data. We also propose a slight modification to the Robbins-Monro procedure to getbetter convergence properties.Several methods for quantile estimation based on binary data are proposed in the liter-ature; see for example Wu (1985), McLeish & Tosh (1990), Kalish (1990), Neyer (1994) andSitter & Wu (1999) among many others. The objective of this study is to find the optimalsequential procedure within the class of the Robbins-Monro type procedures, not to find thebest overall method.32. OPTIMAL ROBBINS-MONRO PROCEDUREIn most applications, the distribution function M(x) is from a location family with loca-tion parameter θ. Therefore hereafter we denote M(x) by M(x−θ). Thus M(0) = α ∈ (0, 1)is specified. We also assume that˙M(0) > 0 is known. The experimenter starts the exper-iment at some value x1, which is believed to be close to θ based on some prior knowledge.Therefore we may choose a prior distribution for θ with E(Θ) = x1and var(Θ) = τ21< ∞,where τ1represents the initial uncertainty of θ with respect to x1. Let Zn= xn− Θ. Notethat, although x1is a fixed quantity, x2, ···, xnare random because of their dependence onpast data. Consider a modified Robbins-Monro process given byxn+1= xn− an(yn− bn).For binary data, {bn} is a sequence of constants in (0, 1). They need not be equal to α, but{bn} is expected to get close to α as n gets larger. We will see that, if we use a bndifferentfrom α, the performance of the Robbins-Monro procedure can be greatly improved. Thusour model isyn|Zn∼ Ber{M(Zn)},Zn+1= Zn− an(yn− bn),E(Z1) = 0 and E(Z21) = τ21.The objective is to find sequences {an} and {bn} such that Zn→ 0 in probability at thefastest rate. First we investigate the conditions under which the desired convergence can b eobtained.4Suppose the sequence {bn} satisfies the condition∞Xn=2an|bn− α|n−1Xj=1aj< ∞. (3)Then we have the following convergence result whose proof closely follows that of Robbins& Monro (1951). The above condition together with (2) ensures that bnconverges to α.Moreover, becausePn−1j=1ajincreases with n, the convergence of bnto α should be fastenough for (3) to hold. All proofs are given in the Appendix.Theorem 1. If (2) and (3) hold, then Zn→ 0, in probability, as n → ∞ .There are infinitely many sequences for {an} and {bn} satisfying the conditions of theTheorem 1. We are seeking the particular sequence that gives the best convergence prop-erties. We propose to choose anand bnsuch that E(Z2n+1) is a minimum subject to thecondition that E(Zn+1) = 0. Similar ideas of choosing two sequences to minimise the con-ditional mean squared error in sequential designs was employed by Hu (1997, 1998) in aBayesian framework.We have thatE(Zn+1) = E(Zn) −an[E{M(Zn)} − bn] = 0.Since the sequences a1, ···, an−1and b1, ···, bn−1are obtained such that E(Z2) = ··· =E(Zn) = 0, we obtainbn= E{M(Zn)}. (4)Let τ2n=