# Efficient Robbins-Monro Procedure for Binary Data

**View the full content.**View Full Document

0 0 9 views

**Unformatted text preview:**

Efficient Robbins Monro Procedure for Binary Data V Roshan Joseph School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta GA 30332 0205 USA roshan isye gatech edu SUMMARY The Robbins Monro procedure does not perform well in the estimation of extreme quantiles because the procedure is implemented using asymptotic results which are not suitable for binary data Here we propose a modification of the Robbins Monro procedure and derive the optimal procedure for binary data under some reasonable approximations The improvement obtained by using the optimal procedure for the estimation of extreme quantiles is substantial Some key words Quantile estimation Sequential design Stochastic approximation 1 1 INTRODUCTION In many applications interest centres on finding the threshold of a variable that will cause certain amount of successes or failures in the output For example an explosive designer may be interested in finding the level of shock necessary to make 99 99 of the explosives fire Neyer 1994 see Joseph and Wu 2002 for another application The problem can be formally 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 by assuming 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 to the experimenter but the experimenter can observe Y at different values of x in order to find 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 be performed by using a sequential design in which the x s are chosen sequentially and are allowed 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 procedure xn 1 xn an yn 1 where yn is the binary response observed at xn and an is a pre specified sequence of positive constants Robbins Monro showed that xn in probability if X an and n 1 X n 1 2 a2n 2 Robbins Monro recommended the simple but non optimal choice an c n for some constant c Based on the results of Chung 1954 Hodges Lehmann 1956 and Sacks 1958 the procedure is fully asymptotically efficient with an nM 1 under certain conditions where M denotes the first derivative of M for use in practical implementations see for example Wetherill and Glazebrook 1986 The optimal choice of an in small samples has not been investigated although in most experiments this is the most interesting case Wetherill 1963 showed through simulation that the Robbins Monro procedure works quite well for 0 5 corresponding to LD50 but performs very poorly for extreme quantiles 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 data possess two properties that can be exploited to improve the procedure the variance of Y is a function of x given by M x 1 M x and M x is a distribution function In this article we make use of these properties to produce optimal Robbins Monro procedures for binary data We also propose a slight modification to the Robbins Monro procedure to get better convergence properties Several methods for quantile estimation based on binary data are proposed in the literature see for example Wu 1985 McLeish Tosh 1990 Kalish 1990 Neyer 1994 and Sitter Wu 1999 among many others The objective of this study is to find the optimal sequential procedure within the class of the Robbins Monro type procedures not to find the best overall method 3 2 OPTIMAL ROBBINS MONRO PROCEDURE In most applications the distribution function M x is from a location family with location 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 experiment 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 x1 and var 12 where 1 represents the initial uncertainty of with respect to x1 Let Zn xn Note that although x1 is a fixed quantity x2 xn are random because of their dependence on past data Consider a modified Robbins Monro process given by xn 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 bn different from the performance of the Robbins Monro procedure can be greatly improved Thus our model is yn Zn Ber M Zn Zn 1 Zn an yn bn E Z1 0 and E Z12 12 The objective is to find sequences an and bn such that Zn 0 in probability at the fastest rate First we investigate the conditions under which the desired convergence can be obtained 4 Suppose the sequence bn satisfies the condition X an bn n 2 n 1 X aj 3 j 1 Then we have the following convergence result whose proof closely follows that of Robbins Monro 1951 The above condition together with 2 ensures that bn converges to Moreover because Pn 1 j 1 aj increases with n the convergence of bn to should be fast enough 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 the Theorem 1 We are seeking the particular sequence that gives the best convergence prop2 erties We propose to choose an and bn such that E Zn 1 is a minimum subject to the condition that E Zn 1 0 Similar ideas of choosing two sequences to minimise the conditional mean squared error in sequential designs was employed by Hu 1997 1998 in a Bayesian framework We have that E Zn 1 E Zn an E M Zn bn 0 Since the sequences a1 an 1 and b1 bn 1 are obtained such that E Z2 E Zn 0 we obtain bn E M Zn 4 Let n2 E Zn2 From A1 we have 2 n2 2an E Zn M Zn bn a2n E M Zn bn 2 E M Zn 1 E M Zn n 1 5 5 2 Minimising n 1 with respect to an and using 4 we obtain an E Zn M Zn E M Zn 1 E M Zn 6 Unfortunately the optimal sequences depend on the function M which is unknown to the experimenter Therefore the best we can do is to choose a function G that can closely approximate the true function M and derive the sequences …