Sequential fixed width confidence intervals Citation Asparouhov, Tihomir Zlatev (2000) Sequential fixed width confidence intervals. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/0DZR-RK42. https://resolver.caltech.edu/CaltechTHESIS:01272012-142906804 Abstract We consider the problem of constructing confidence intervals of fixed width d and confidence level γ for the success probability p in Bernoulli trials. Algorithms are given for calculating numerical lower bounds on the average expected sample size required and an asymptotic lower bound is obtained as d -> 0. Sequential and two-stage procedures are proposed that attain the asymptotic lower bounds and nearly attain the numerical lower bounds. Asymptotically optimal sequential and two-stage confidence intervals of fixed width and confidence level are proposed for the mean in a general (non-Bernoulli) context. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: Mathematics Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Lorden, Gary A. Thesis Committee: Unknown, Unknown Defense Date: 13 March 2000 Record Number: CaltechTHESIS:01272012-142906804 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:01272012-142906804 DOI: 10.7907/0DZR-RK42 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 6787 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 30 Jan 2012 16:54 Last Modified: 09 Nov 2022 19:19 Thesis Files Preview PDF - Final Version See Usage Policy. 16MB Repository Staff Only: item control page

Sequential Fixed Width Confidence Intervals Thesis by Tihomir Zlatev Asparouhov In P artial Fulfillment of t he Requirements for the Degree of Doctor of Philosophy California Institute of Technology P asadena, California 2000 (Submitted March 13, 2000) 11 © 2000 Tihomir Zlatev Asparouhov All Rights Reserved III Acknowledgements I would like to express my deepest gratitude to my advisor, Professor Gary Lorden, whose support and supervision made this research possible. It has been a great pleasure to work under his guidance. The Mathematics Department of the California Institute of Technology was a great place for conducting the research, and for that I would like to thank all the members and staff of the department. I would like to thank my wife Elena and my son Delian for their constant support and encouragement. IV Abstract We consider the problem of constructing confidence intervals of fixed width d and confidence level 'Y for the success probability p in Bernoulli trials. Algorithms are given for calculating numerical lower bounds on the average expected sample size required and an asymptotic lower bound is obtained as d -> O. Sequential and twostage procedures are proposed that attain the asymptotic lower bounds and nearly attain the numerical lower bounds. Asymptotically optimal sequential and two-stage confidence intervals of fixed width and confidence level are proposed for the mean in a general (non-Bernoulli) context. v Contents Acknowledgements III Abstract iv 1 Introduction 1 2 Lower Bound on Average Expected Sample Size 6 2.1 Bayes Auxiliary Problem . . . . . . . . . . . . . . 6 2.2 Lower Bound on the Posterior Expected Loss with Uniform Prior 9 2.3 Lower Bound on the Integrated Risk with Beta Prior . . . . . . . 17 2.4 Asymptotic Lower Bound on the Sample Size of a Fixed Width Confidence Interval . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 3 4 19 Asymptotically Efficient Fixed Width Confidence Intervals of Exact Coverage for the Mean of a Population 23 3.1 Asymptotic Efficiency . .. . 27 3.2 Exact Coverage Probability 32 3.3 Two Stage Confidence Intervals 41 3.4 Related Literature ..... . . 43 Exact Lower Bounds and Nearly Optimal Procedures 45 VI 4.1 Backward Induction 45 4.2 Asymptotically Efficient Stopping Times 48 4.3 Lorden's Push Algorithm . 49 4.4 Numerical Examples . . . 56 Bibliography 65 1 Chapter 1 Introduction Let Xl, X 2 , ... be independent Bernoulli random variables with unknown parameter o :::; p :::; 1, i.e., for each i = 1,2 ... , P(Xi = 1) = p = 1 - P(Xi = 0). Let [L, R] be a confidence interval for the parameter p , where Land R are functions of the observed X/so The confidence interval [L, R] has confidence level , if its coverage probability is at least " i.e., infp Pp(L :::; p :::; R) :::: ,. It has width d if Pp(R - L :::; d) = 1 for all p. We are interested in finding level , width d confidence intervals that require a minimal amount of sampling. There are two ways to approach this problem: by a fixed sample size method, or by a sequential method. A fixed sample size method consists of (n , L, R), where n is the number of observations needed, and [L, R] is the confidence interval based on the observations. In contrast, a sequential method consists of (N, L , R) where N is a stopping time (also called a stopping rule) denoting the number of observations taken, which is a random variable based on the observations. Our results concern sequential methods, which require less sampling than fixed sample size methods. Throughout this work, and d are given numbers, 0 < , < 1, d > 0 and we denote by h = d/ 2 the length of the half interval. There are two classical fixed sample size methods to obtain confidence intervals for p. 2 SAM (Standard Approximate Method) By the Central Limit Theorem and Slutsky's ([10]) theorem the confidence interval has coverage probability approximately equal to "'I, where c is the (1+"'1)/2 quantile of the standard normal distribution, i.e., c = <I>-1((1+"'I)/2) > 0 where <I> is the standard normal distribution function. However, for p close to 0 and 1 this approximation breaks down and the coverage probability approaches O. SAM (Standard Exact Method) This method is based on constructing the two uniformly most accurate (1 +"'1) /2 one-sided confidence intervals, described in Chapter 3.5 of [11]. Given that Sn = 2:~= 1 Xi = k the confidence interval [L, R] is obtained by solving these two equations for Land R : Pp=L ( Sn ~ k ) = Pp=R ( Sn:S; k ) 1-"'1 -2- 1-"'1 = -2- Neither of these methods yields fixed width confidence intervals. There are two improvements of the classical methods up to now, both designed to give confidence intervals of fixed width. 3 Classical Sequential Method (Chow-Robbins [4]) The idea of this method is to use the confidence interval based on the Central Limit Theorem approximation but to sample until the width of this interval becomes less than d. Hence the method uses the following stopping rule: N is the smallest n for which 2cJ Xn(l;X n ) < d. This method also has only approximate coverage probability , and the approximation breaks down when p is close to 0 and 1. Pushed Confidence Intervals (Lorden [12]) Lorden has obtained the best fixed sample size method for giving confidence intervals of exact coverage probability , and fixed width d. It is the best in the sense that it uses the smallest possible sample size n. Chapter 4 includes a discussion of this method and our application of it in the sequential case. Let ),.(p) b e a probability density function defined on [0 , 1]. Define J 1 B(r, d,),.) = inf EpN ),.(p) dp, o where the infimum is taken over all confidence intervals (N , L , R) of level, and width d. The quantity B(r, d, ),.) represents the minimal amount of sampling needed to obtain a level , width d confidence interval, in the sense of minimizing the average over p (using),. as a weight function) of the expectation, when p is true , of the sample size. 4 With few exceptions, problems in sequential analysis about b est possible performance, such as the one defined by Bb, d, A), lead to theorems proved only in asymptotic form, as the sample size b ecomes large. In the present problem, asymptotic theory is most naturally developed by letting d -+ 0 with" held fixed. In Chapter 2 we use a Bayes technique to obtain an asymptotic lower bound on Bb, d, >.) as d -+ O. In Chapter 3 we modify an idea of Chow and Robbins [4] to construct level " width d confidence intervals that achieve the asymptotic lower bound. Combining these two results yields the following theorem. Theorem 1. For any positive continuous function>. defined on [0, 1] The method proposed in Chapter 3 is developed as a solution to the problem of constructing a confidence interval for the unknown mean of a distribution belonging to a general class of distributions . Under some mild moment conditions, we construct fixed width d level " confidence intervals, that are asymptotically efficient in a certain sense. We also consider an appealing special class of sequential methods called twostage procedures. These rely on a preliminary (first-stage) sample of a fixed size, m, followed if necessary by a second stage of variable size. We construct two-stage confidence interval procedures that are asymptotically efficient and in the Bernoulli case attain Bb, d, >.) in the limit as d -+ O. Another goal of this investigation is to determine algorithms for constructing "nearly optimal" sequential confidence intervals , along with methods for calculating 5 how close they come to attaining Bb, d, >') . Such constructions have two parts: the stopping rule N and the so called terminal decision rule that calculates the interval [L, R] based on Nand XN . It turns out that rather than center the interval at X N and use probability estimates to guarantee coverage probability I, which suffices for the asymptotic theory of Chapter 3, it is much more effective for small sample sizes to apply Lorden's "push" algorithm [12] to optimize the construction of [L, R] for a given stopping rule N. These considerations reduce the problem to one of finding the best (or nearly best) stopping rules N. In Chapter 4 we give a method for computing explicit lower bounds on Bb, d, >.) and describe two new methods for constructing nearly optimal stopping rules. The first method is based on the auxiliary Bayes problem of Chapter 2 and uses a Backward Induction scheme to compute the stopping rule. The second method is based on selecting a member of the asymptotically optimal family of solutions proposed in Chapter 3. For both methods we use as a terminal decision the confidence intervals obtained by Lorden's push algorithm. We also give a method for obtaining nearly optimal two-stage confidence interval procedures. As the numerical results in Table 1 of Chapter 4 illustrate, the algorithms for b oth the sequential and two-stage rules come very close to solving the problem of attaining B (')', d , >.) in practice. 6 Chapter 2 Lower Bound on Average Expected Sample Size 2.1 Bayes Auxiliary Problem Given a probability density function 1f (p) defined on the interval [0, 1J and c> 0, we consider the problem of minimizing J{h2~ 1 (c) EpN - p (1 - p) Pp (L ~ p ~ R)} 1f (p) dp (2.1) o over all width d = 2h confidence intervals (N, L, R) for p, assuming without loss of generality that R = L + d. There is no restriction on the confidence level of the intervals. Our goal is to find a lower bound on the quantity (2.1), useful for constructing lower bounds on Bb, d, -X). A standard way to solve this problem is to use the following Bayes technique. Let p be a random variable, p E [0 ,1] with density function 1f, also called the prior density of p. Define the loss function for (N, L, R) as a function of p by I: (N, L , R) = h2¢(C) c N - P (1 - p) l{L::;p::;R} 7 Then (2.1) can be interpreted in the form J{h2~ 1 E (£ (N, L, R)) = (c) EpN - p (1 - p) Pp (L <:S p <:S R) } 7r (p) dp , o where the expectation on the left-hand side is taken with respect to the sequence of Bernoulli random variables {Xi} with probability of success p , where p is a random variable having probability density function 7r. In this form the problem is known as a Bayes problem and E (£ (N, L , R)) is called the integrated risk of the procedure (N, L, R). We are interested in a lower bound on the integrated risk in terms of h, "f and 7r. A standard way to study the integrated risk is to express it in terms of a conditional expectation, i.e., E(£(N,L , R)) = E{E(£(N, L,R) IN,SN)} and to obtain bounds on E (£ (N, L, R) IN, SN), which is called the posterior expected loss. Define s = SN as the number of "successes" at termination, i.e., the number of observed l 's, and f = N - s as the number of "failures" at termination, i.e. , the number of observed O's. We use the following notation for the conditional expectation given Nand SN : E ('Is , j) = E CIN = s + j, SN = s). Then the posterior expected loss is E (£Is, j) = h2~ (c) (s + j) - J L+d p (1 - p) 7r (pis, j) dp L (2.2) 8 where 7r (pI8, f) is the conditional density of p given N = 8 + f and SN = 8, which is also known as the posterior density of p The posterior expected loss will be minimal when L is chosen to maximize the integral on the right-hand side of equation (2.2), and since the integrand depends only on 8 and f, the optimal value for L will depend only on 8 and f. Such an optimal value is called a Bayes terminal decision, which we denote by L (8, f). Without loss of generality we assume that L = L (8, f) , which reduces the problem to choosing N optimally. We depict the random walk generated by Xl, X 2 , ... in the following way: it starts at the origin of the two-dimensional coordinate system, where the 8 axis is horizontal and the faxis is vertical. For each success it moves to the right, i.e., it increases the 8 coordinate by 1 and for each failure it increases the f coordinate by 1. Thus (8, f) is the position of the random walk after observing s + f data points. A stopping rule N determines a partition of the integer lattice points - each (s, f) is either a stopping point or a continuation point. First we will find a lower bound on the integrated risk in the case when the prior distribution of p is Beta(a, b) , a, b > 0, i.e., the prior density function of p is the 9 Beta(a, b) density fun ction pa- l (1 _ p /-1 fa ,dp) = B (a, b) , 1 where B (a, b) = Jpa-l (1 - p)b- l dp, is the Beta function. o 2.2 Lower Bound on the Posterior Expected Loss with Uniform Prior In this section we assume that p has a uniform distribution on [0,1]' i.e., a Beta(l, 1) distribution. Lemma 1. There exists a constant C such that E (£Is, f) 2 (c¢ (c) - 'I) E (p (1 - p) Is, f) - Ch. (2.3) Proof. If p has uniform prior density, then the posterior density of p at (s, f) is the Beta(s + 1, f + 1) density (see page 193 of [16]). If the confidence interval associated with the stopping point (s, f) is [z, z + 2h] , then the posterior expected loss is z+2h J h2¢ ( ) p (1 - p) pS (1 - p)f dp E (£Is , f) = c (s + f) _ _ z_ _: - -_ _--,--_ _ B (s + 1, f + 1) C z+2h J pS+l (1 - P )f+l dp 2 = h ¢ (c) (s + f) _ B (s + 2, f + 2) _ z_ ......,....-_--:--:---_ c B (s + 1, f + 1) B (s + 2,f + 2) 10 z+2h = 2 h ¢ (c) (3 + 1) _ (3 + 1) (f + 1) C (3 + 1 + 2) (3 + 1 + 3) J ps+1 (1 - p )f+l dp z (2.4) B (3 + 2, 1 + 2) where we used Euler's formula for the Beta function, B (3, 1) = ri(~:W, to evaluate B (3 + 2, 1 + 2) /B (3 + 1, 1 + 1). Also, since the posterior distribution of p is Beta( 3 + 1, 1 + 1) , the posterior expect ation of p (1 - p) is E 1- (p( 3 p)I , 1) =B(3+2,1+ 2 )= (3+1)(f+1) B(3+1,1+1) (3+1+2)(3+1+3)' (2.5) From now on, we will assume that 3 :::; j. By symmetry all the claims need only be proved in the case 3 2:: j. Case 1. Suppose that 3 =f. 1 and (3 + 1) (f + 1) <h 2(f-3)(3+1+2) - Then (2.3) is satisfied. Proof of Case 1. We have z+2h J ps+1 (1 - p )f+1 dp 2 E (£13 1) = h ¢ (c) (3 + 1) _ (3 + 1) (f + 1) -"z':--_ _ _ __ , c (3 + f + 2) (3 + f + 3) ps+1 (1 _ p)f+l dp o J 2 > h ¢ (c) (3 + 1) _ - C (3 + 1) (f + 1) > -E (p (1 - p) 13 1) (3 + 1 + 2)(3 + 1 + 3) , 11 Therefore E (£, 18, 1) - (c¢ (C) - ,) E (p (1 - p) 18, 1) 2 - (1 - , + c¢ (c)) (8 +(; : ~~ ~ ~ : Y+ 3) 2h (f - 8) 2-(1-,+C¢(C)) 8+1+3 2-(1-,+c¢(c))2h, which proves (2.3) Case 2. Suppose that (8 + 1) (f + 1) > h (f _ 8) 2(8+1+2) - (2.6) Then (2.3) is satisfied. Proof of Case 2. Let a = 8 + 1 and b = 1 + 1. Our goal is to find an upper bound on J z+2h g(z)= pa (1_p)b dp . z Define gl (p) = pa (1 - p)b . Suppose 9 achieves its maximum at zo, then o = g' (zo) = gl (zo + 2h) - gl (zo) . However, gl (p) is an increasing function in the interval [0, aj (a + b)] and decreasing on [aj (a + b), 1], which implies Zo < aj (a + b) < Zo + 2h. For a change of variable in 9 (z) set a p=--+x. a+b 12 The above inequalities imply that for all p E [zo, Zo + 2h], Ixl < 2h . The inequality log (1 + x) ::; x - x2 x3 2 +3 (2.7) is valid for all x > -1. Now log = (pa (1 - p)b) = alog (a: b+ x) + blog (a ~ b- x) alog (a : b) + blog (a ~ b) + alog ( 1+ x (aa+ b)) + blog (1 - x (a b+ b) ) ~ log Ca :":;"+b) + (a log (1 + x(aa+b») +blog (1 _ x(ab+b») ) By assumption b 2: a. We use Ixl < 2h and (2.7) to get where (J" is defined by the last equation, i. e., (J"= ab 13 Notice now that (2.6) can be restated as Now we combine the above inequalities zo+2h J pa (1 - p)b dp zo zo+2h-a/ (a+b) (a + b + I)! aabb alb! (a + bt+b J zo-a/ (a+b) zo+2h-a/(a+b) < (a + b + I)! aabb alb! (a + bt+b J zo-a/(a+b) since the highest probability density interval for the normal distribution is the symmetric interval around zero. Using Stirling's formula in the form found in [6J page 52, and we obtain 14 Finally we obtain (2.8) By the mean value theorem <I> (x) -1 / 2 ,./, ( ) __1_ smax'l-'x-~, y2n x so for all positive x, 2x 2<I> (x) - 1 < - . - V2if An upper bound for the last term in (2.8) can be obtained from the inequality 1 1 a + b /1 _ 4h(b L a 2 ) V By (2.6) 3ab f2 /a+b 2h -;;;;-h ::; .,fo. ( (~h) ) V;V 2<1) - 1 ::; 15 For any 0 < x :::; 2/3 1 yT=X = I- x x 1+ l-yT=X yT=X < 1+ yT=X < 1+ J3x. I- x - l-x- Now we deal with the first term in (2.8) VI - 1 (!!.) _1) : :; 2<1> (!!.) _1+ J34h (b3ab a (2<1> (!!.) _1) 2 4h(b L a 2 ) 3ab (2<1> CT ) CT < 2<1> (h' ~ _ 1 - 2 - V~) CT 2 2 '3'4h (b - a ) +V0 3ab . Finally Now we substitute this inequality in (2.4) b f) ~ h¢ (c) (a + b - 2) - (a + b) (aab+ b + 1) (2iF. (hV Ca +ab ) 3 2 E (£Is, c '±' ) - 1) _ ab J34h (b 2 - a2 ) _ ab 2h (a + b) (a + b + 1) 3ab (a + b) (a + b + 1) viii 2 > h ¢ (c) (a + b _ 2) _ - c ab (2<1> (a + b) (a + b + 1) (hJ<a +abb)3) _1) _4V3h _~ 3 2viii 16 For all x ?: 0 define the function K(x) = <}(c)x c (2<1> (Vx) -1). Its derivative is an increasing function and has a unique root x = c2 . In fact, K' (x) < 0 when 0 < x < c2 and K' (x) > 0 for x > c2. Therefore, K (x) ?: K (c 2 ) = c<} (c) - , . Using this inequality we complete the proof. b) ab E (£1 s, f) ?: h2<}c (c) (a+ - (a+b)(a+b+1) - 2 . (2;t;. (hla +abb)3) - 1) _ '±' h 2 <} (c) 4V3h h ab - - - - - - > -:---:--:-----:c 3 2y17T- (a+b)(a+b+1) (h2~(C)(a +b)2~+b+l) _ (2<1> (h (a+b)2~~+b+l)) -1)) -Csh > ab K (h2 (a + b)2 (a + b + - (a + b) (a + b + 1) ab 1)) _ C h ?: E (p (1 - p) Is,1) (c<} (c) - ,) - C3 h, where C 3 depends only on , . This completes the proof of Lemma 1. 3 17 The above argument suggests as a solution of the Bayes problem the stopping boundary (S+1+2)2(S+1+3) (S + 1) (J + 1) C 2 h2 ' This stopping boundary is a special case of the Chow-Robbins stopping rules. 2.3 Lower Bound on the Integrated Risk with Beta Prior In this section we assume that p is a Beta( a, b) random variable, where a and bare positive numbers. Denote by Ea,b the expectation, when the prior distribution of p is Beta(a, b) . Lemma 2. There is a constant C1 depending only on a and b such that Ea,b (£Is, 1) 2': (c¢ (c) -,) Ea,b (p (1 - p) Is, 1) - e 1 h Proof. By (2.2) Ea,b (£Is, 1) = h 2 ¢ (c) c (s + j) - Ea,b (p (1 - p) lL::O;p::O;Rls, j) 18 where the second expectation depends only on the posterior distribution of p , which is Beta( a + s, b + 1). Therefore, Ea,b (£Is, 1) = E 1 ,1 (£ Is + (a - 1), f + (b - 1)) - (a + b - 2) h2 ¢ ~c) (2.9) By Lemma 1 E 1 ,1 (£Is + (a - 1) , f + (b - 1)) 2 E 1 ,1 (p (1 - p) Is + (a - 1), f + (b - 1)) - Ch = Ea,dp (1- p) Is , 1) - Ch, again because the conditional distribution of p is the same. Combine these two results and the fact that h < 1 to complete the proof of the lemma. The optimal boundary suggested by the above argument when the prior is Beta(a, b) is given by (s + f + a + b)2 (s + f + a + b + 1) (s + a) (j + b) c2 h2 · Lemma 3. There is a constant C1 depending only on a and b such that Ea,b (£) 2 (c¢ (c) - ,) E a,b (p (1 - p)) - C 1 h. Proof. Integrate the inequality in Lemma 2 with respect to the distribution of (s, f) . 19 2.4 Asymptotic Lower Bound on the Sample Size of a Fixed Width Confidence Interval Now we apply the result from the previous section to obtain a lower bound on the average expected sample size of any sequential confidence interval (N, L, R) of width 2h and confidence level T We can of course assume that the width is exactly 2h. Recall that !a,b (p) is the Beta( a, b) density function. Lemma 4. For any positive numbers a and b and any confidence interval (N, L , R) of width 2h and confidence level" a lower bound on the expected sample size averaged with respect to !a,b (p) as h -+ 0 is given by 1 h 2 J Ep (N) !a,b (p) dp 2:: c o 1 2 J 2 p (1 - p) !a,b (p) dp+O (h) = c (a + b) (:b+ b + 1) +0 (h) . 0 Proof. Fix p and integrate with respect to Xl , X 2 , ... to get 20 Now we integrate with respect to p and get J 1 2 Ea,b (£) :::; h ¢c (c) Ep (N) fa,b (p) dp -,Ea,bP (1 - p) . o By Lemma 3, therefore, J 1 2 c¢(c)Ea,b(p(l - p)) + O(h) :::; h ¢(c) c Ep (N) f a,b (p) dp o and the conclusion of the lemma follows , using the fact that E ((1 _ )) _ ab a,b P P - (a + b) (a + b + 1) by (2.5). Now we extend this result to a general class of priors. Theorem 2. Let f (p) be a positive continuous function defined on the interval [0,1]. If {( N (h) , L (h) , R (h))} is a family of confidence intervals of width 2h and confidence level " then J Jp (1 - p) f (p) dp. o 0 1 liminf h 2 h--....O Proof. Choose <5 > 1 Ep (N) f (p) dp ;:::: c 2 °such that f (p) ;:::: for all p [0 , 1] . is well known that <5 E It 21 the Bernstein polynomials converge uniformly to any continuous function. Therefore, for a fixed c there exist n and some positive numbers lk such that n If (p) - L lkfk ,n-k (p) I < c. k=O Now J n 1 liminf h 2 h~O Ep (N) (J (p) + c) dp 2: o 2: L lk C2 k=O L l k liminf h h~O k=O J n I J 1 2 Ep (N) fk ,n - k (p) dp 0 J l p (1 - p) ik ,n - k (p) dp 2: c2 0 p (1 - p) U (p) - c) dp 0 On the other hand J 1 lim inf h2 h~O Ep (N) (J (p) + c) dp o 1 ::; (1 + J)li~-1~f h JEp (N) f (p) dp. 2 o 22 Therefore, 1 (1 + J) li~jrf J h 2 Ep (N) f (p) dp ? c 1 2 o J p (1 - p) f (p) dp - ~ c. 0 Letting c go to zero, we obtain the desired result. Remark. If we consider only stopping rules N (h) for which E (N) = 0 (h- 2 ) in the above theorem, we can drop the assumption f (p) > O. Note that all reasonable stopping rules are of this type. In fact the optimal fixed size stopping rule needs no more than 0 (h- 2 ) observations. 23 Chapter 3 Asymptotically Efficient Fixed W"idth Confidence Intervals of Exact Coverage for the Mean of a Population A method for constructing width 2h confidence intervals (N , L , R) for the mean f-l of independent identically distributed random variables Xl, X 2 , ' " with finite variance is described by Chow and Robbins in [4] . The stopping rule considered is where limn->oo Cn = C = q,-1((1 + "Y)/2), and "y is the desired coverage level. Here defining a sequence of estimators of the unknown variance. Upon stopping the confidence interval is [L, R] = [XN(h) - h, XN(h) + h]. Theorem 3 (Chow-Robbins). Let cr 2 be the variance of the Xi'S. If 0 < cr < 00 , 24 then lim P(XN(h) - h :::; jJ, :::; XN(h) + h) = ,. (3.1) h -+0 The coverage probability of these confidence intervals is asymptotically" i.e., the probability of their containing the true jJ, will be arbitrarily close to , when h is sufficiently small. However, in a parametric problem like the Bernoulli case, the definition of a confidence interval requires more than just asymptotic coverage. At a minimum what is needed is the so-called strong asymptotic coverage, which specifies that the convergence of the coverage probability in (3.1) is uniform in p. Then for h sufficiently small the coverage probability will be arbitrarily close to , simultaneously for all p. This is critical since p is unknown. Theorem 4 below resolves these issues; in fact , our procedures guarantee coverage probability" once h is suffuciently small. Moreover, that theorem and its Corollary at the end of Section 3.2 are used along with the lower bound proved in Theorem 2 in Chapter 2 to prove Theorem 1. We consider the general problem of constructing width 2h level , confidence intervals for the mean of a population in a parametric context. Let Xl, X 2 , ... be independent and identically distributed random variables with unknown distribution F which belongs to a known class of distributions F . Let jJ,F and oJ. be the mean and the variance of F. A level, confidence interval (N, L, R) for the mean jJ, = jJ,F 25 is a procedure satisfying ?F(L :'S J-LF :'S R) 2':, for all F E F. Fix 0 < , < 1 and C = <;[>-1((1 + , )/ 2) . In this chapter, but only in this chapter, we will be interested in width 2h confidence intervals for J-L that are centered at the point estimate XN(h), i.e., [XN(h) - h, XN(h) + h). Therefore, we identify the confidence interval (N(h), L = XN(h) - h , R = XN(h) + h) with the stopping time N(h) , and will refer to this confidence interval by referring only to the stopping time N(h). The stopping time we propose is defined by N(h) = min {n 2': K 2 C } n-K>V:~ - nh 2 where K = K(h) and Ch are parameters to be chosen. We will find conditions on K and Ch sufficient for coverage probability " which also yield asymptotically efficient N(h) in the sense of Theorem 4. Throughout this chapter we assume that: Also, without loss of generality assume that Ch is bounded between fixed numbers c' 26 and C", i.e., 0 < c' < Ch < C", for all h. Theorem 4 describes a method for constructing width 2h level, confidence intervals for the mean. Assume that all F E F have finite fourth moment. Let We will omit the subscript F when there is no ambiguity. Theorem 4. Suppose that for all F E F, min {W F, W F / oJ} < B for some positive constant B. Th en for K = h-1.85 and Ch = C + h O. 13 the confidence intervals defined by N (h) achieve confidence level " i. e. , (3.2) In addition N(h) is asymptotically effi cient for all F E F , in the sense that (3.3) Moreover, N is asymptotically efficient with respect to any probability measure 1r defined on F for which f01 oJ. d1r < 00, i.e., (3.4) The meaning of " asymptotically efficient" in the above theorem, also sometimes called Chow-Robbins asymptotic efficiency, is based on the following observation. If 27 (J' were known, then by the Central Limit Theorem we would need to take approxi- mately c2 (J'2 / h 2 observations to achieve coverage probability r using fixed sample size symmetric confidence intervals. Thus, (3.3) shows that for unknown (J' a sequential stopping rule can use the sequence {Vn } estimating (J'2 to achieve on the average the same sample size as would be required if (J'2 were known. Note that this definition of asymptotic efficiency does not necessarily guarantee best possible performance among sequential rules. However, Theorem 2 shows that in the case when F is the family of Bernoulli distributions and 7r is a probability distribution with positive continuous "-- density, asymptotic efficiency with respect to 7r in the sense of (3.4) does guarantee b est possible performance among sequential procedures. A discussion of related papers in the literature is given at the end of this chapter. Remark 1. The choice of K and Ch is not the optimal choice we can make. To make such a choice one needs to look at the eight terms that provide a lower bound on the coverage probability in Lemma 9, for each term deduce a linear inequality that needs to be satisfied by logh (K), logh (Ch) and the other functions involved, and solve these strict linear inequalities. The actual optimal choice is close to the one we made. 3.1 ASYIIlptotic Efficiency This is Lemma 2 from [15]. Lemma 5. For any a> 0, and m 2:: 1, 28 The following direct consequence of Lemma 5 is of use later. Lemma 6. Esup IXnl < 1f.L1 + 160'2 + 1. n Proof. Esup IXnl :::; Esup IXn - f.L1 + 1f.L1· n n By Lemma 5 and the result follows. Define L n 2 = -1 ( X · - X) 2 = T7 - 1 sn J n Vn . n J= . 1 n Next we derive a lemma similar to Lemma 5. Lemma 7. For any a > 0, and m ~ 1, P ( sup 1s~ - 0'21 ~ a n ~m ) 16( :::; m 2 2 w -0'4 a 2 + -0'2) , a 29 Proof. by the preceding lemma. Lemma 8 (Asymptotically Efficient Sample Size). Suppose that lim h 2 K(h) = 0 and h~O lim Ch = c. h~O Then (i) for every F E F , (3.3) holds, (ii) for any probability measure 7r on F satisfying J a} d7r < 00, (3.4) holds. Proof. (i) We use N as a shorthand for N(h). First we establish a lower bound on N. Since Vn ;:::: n- 1 and 30 taking square roots shows that (3.5) Thus N -+ 00 as h -+ O. Since also limn-+oo Vn = a 2 a.s. , The stopping rule also satisfies (3.6) As h -+ 0 therefore lim Nh2 = (ac)2 a.s. h-+O To prove (3.3), i.e., that lim E(N)h 2 = (ac? h-+O it suffices to show that {Nh2h>o are bounded by an integrable function for h in a neighborhood of O. From inequality (3.6) we deduce that for h sufficiently small Nh2 :::; (c"? sup Vn + 1 n 31 It suffices to show that E sUPn Vn < 00, which follows from ,\"",n V.n < _ ui=l (X. _ t n f.l )2 +1 by Lemm a 6 and the fact that X i has a finit e fourth moment. (ii) In order to establish (3.4), we need to show that {h 2 E(N)} are uniformly integrable with respect to 7r for all h in a neighborhood of O. From (3.6) we get N-l N(N - 1)h2 :::; (e")2 + (N - l)(K + 1)h2 + (e")2 L(Xi i=l N-l :::; (e")2 + N(K + 1)h2 + (e")2 L(Xi - f.l) 2 i=l N :::; (e")2 + N(K + 1)h2 + (e"? L(Xi - f.l) 2. i =l Therefore, N N 2h 2 :::; (e")2 + N(K + 2)h 2 + (e")2 L(Xi - f.l? i=l Using Wald's equation ([7]) and hence XN_d 2 32 Therefore, Since (J2 is integrable with respect to 7[", we get the uniform integrability of h2 E(N) with respect to 7[", which completes the proof of Lemma 8. 3.2 Exact Coverage Probability Our choice for the parameters Ch and K will be based on the following technical lemma. Define nmin = max{K, c' /h} -1. Since N(h) 2: K, (3.5) ensures that N(h) 1 2: nmin. Use N as a shorthand for N(h). Lemma 9. Suppose that E and E l are such that 1 2 2 n m in(J2 -> E> - - - (3.7) (3.8) Then for h sufficiently small and for all F E F, a lower bound on the coverage 33 probability of the confidence intervals defin ed by N(h) is given by (3 .9) where the Ci's are positive and depend on r, but not on h. Let Now p(l~ -11 >c) =P(IN-Nol >cNo) 34 2 :::; 2P ( sup n:::::nmin 1) ISn2 - 0" 21 > cO" 2 - -h-2 - - - . (c') nm.n Notice that for h sufficiently small nmin :::; (c/)2 / h 2, since limh->o K h 2 = O. So for h sufficiently small l /n m in ~ h 2/(c/)2 and we get that P (I;' - 11 > o c) :::; 2P ( sup Is'; - 0"21 > cO"2 - _2_ . ) . n:::::nmin nm~n (3.10) By (3.7) we can apply Lemma 7 to the right-hand side of (3. 10) (3.11) Let Sn = 2:~ Xi' Now estimate the probability that f-L is not covered. P(f-L is not covered) '- P (I;; - f-LI > h) = P(ISN - N f-LI > hN) :::; P (/ :::; P ~ - 1/ > c) + P (/ ~ - 1/ : :; c and IS (I ~ - c) + 11 > N - N f-LI > hN ) P (ISNO- Nof-LI > hNo - chNo - c10"VNa) 35 At this point we need to estimate the last two terms in (3.12). We begin with the last term. Let n' = min{N, No}. By Kolmogorov's ([6]) inequality we get The middle term in (3.12) will be estimated by normal approximation. Let Fn(x) be the distribution function of From the Berry-Esseen ([6]) theorem we know that for all x. Now 36 Finally we need a lower bound for this term (3.14) By (3.7) Therefore, ~ (h(1- VNo) E)-(]"- - El ~ ~(c - () . Notice that for h sufficiently small ( is less than 1. Also by (3.8) ( > O. Denote the minimum of ¢ on the interval (c, c + 1) by M. By the mean value theorem, for some ~ E (c,c+() ~(c + () = ~(c) + (¢ (~) ~ ~(c) + (M. 37 Finally We now combine this inequality with inequality (3.13) to get the desired estimate of the middle term in (3.12), and the proof of the lemma is complete. Lemma 10. Suppose that there are positive (}o and b such that for all F E F , (}5 :s: (}J. and Wp / (}J. < b. If Ch 2 c+hO. 13 and K 2 0, then for h sufficiently small the confidence intervals defined by N ( h) achieve confidence level,. Proof. Choose c = hO. 42 and Cl = hO. 14 . It is easy to see that for h sufficiently small (3.7) and (3.8) are satisfied. We also see that Also Finally for h sufficiently small < 1 2 nmin C :s: h h84 = O(Ch - c). O. 38 By Lemma 9 for h sufficiently small the dominating nonconstant term in (3.9) is Ch-C and therefore P (p is not covered) < 1 - ry. Lemma 11. Suppose that for some positive constant wo, w~ :::; w6, for all F E F. Then if K 2:: h-l. S5 and Ch 2:: c) for h sufficiently small the confidence intervals defined by N (h) achieve confidence level ry. Proof. From Lemma 5 we see that if the variance is small (depending on h), the desired coverage is easy to establish: So if (J2 < Kh 2 (1-ry)/8 there is nothing to prove. Assume that (J2 2:: Kh 2 (1-ry)/8 2:: (1- ry)hO. 15 /8. Again in (3.9) choose c = h°.4S and Cl = hO. 16 . It's easy to see that for h sufficiently small, (3.7) and (3.8) are satisfied. Also Notice that nrnin = K, for h sufficiently small. Since w is uniformly bounded, so are (J and p, i.e., (J :::; (Jo and P :::; Po. For h sufficiently small 39 Also for h sufficiently small Finally, for h sufficiently small From (3.9) we get that for h sufficiently small P(p is not covered) < 1 - 'Y. Remark 2. The minimal possible order of magnitude for K in the above proof is actually h -1.8 in the following sense. There is a constant, say C , depending only on the confidence level 'Y, such that if K = C h -1.8, the symmetric confidence intervals will achieve precise coverage for h sufficiently small. To see this we need to repeat the above proof with c = hO. 6 , Cl = hO. 2 . The magnitudes of the terms in (3.9) are as follows: The role of the constant C is to ensure that the coefficient in front of Kh2 is larger than all the coefficients in front of the terms of the same magnitude hO. 2 , which will make Kh2 again the dominating term in (3.9). 40 Proof of Theorem 4. If WF < B then Lemma 11 applies. If WF > B, then B / a} < wF/a} < B, which implies that aF > 1 and Lemma 10 applies. Remark 3. The condition that min{ w, W / a 2 } is uniformly bounded can be restated as . W 11m 2 a w---t(X) < 00 and it is satisfied for most common family of distributions. Examples are the Normal, Exponential, Chi-Square , Extreme Value, Poisson and Geometric families of distributions. This condition will fail only for classes of distributions with very heavy tails. The next corollary says that if the random variables X i are bounded , we can make a simple choice for Ch, namely c. In particular this applies to the family of Bernoulli distri butions. Corollary 1. Let Xi be bounded iid random variables, z.e., IXil < B for some con- stant B independent of F. Let N be the stopping rule N=min{n2:K For K = h- 1. 85 this stopping rule is asymptotically efficient for any F in the sense of (3.3) and for any probability measure 7r on:F in the sense of (3.4), and the confidence intervals defined by N achieve confidence level 'Y . Proof. By Lemma 11 confidence level 'Y is achieved , and the asymptotic efficiency follows from Lemma 8. Notice that since the Xi's are bounded, so is a and therefore 41 f (J2 d7r < 00, for any 7r. Application of this corollary together with Theorem 2 completes the proof of Theorem 1. 3.3 Two Stage Confidence Intervals Here we discuss the two stage procedures associated with our stopping rules. Theorem 5 shows that the advantage of taking the observations fully sequentially will not appear in the first order term of E(N). Theorem 5. If min {w, w / (J2} is uniformly bounded for F E F , then for K - rh-1. 851 and Ch = C + hO. 13 the two stage procedure 1. Take K observations. 2. If K < rVK~ l then take rVK~l- K more observations; otherwise stop. 3. [L, R) = [XN(h) - h, XN(h) + h). achieves confid ence level , and is asymptotically efficient for any F E F in the sense of (3.3). In addition if7r(F) is a probability measure on F such that f (J 2 d 7r(F) < 00, this two stage procedure is asymptotically efficient with respect to 7r in the sense of (3·4)· Proof: The proof is based on the same ideas we used in the proof of Theorem 4. Take N = rmax { K, V ~~ K } l 42 It is easy to see that 2 IN - No l ::s; ~~10-2 - VKI + 1. Define nmin = K - 1. Inequalities (3.10), (3.11) and (3.12) are obtained the same way. The analogues of (3.13) and (3 .14) are [ VNa) ] + 6p..JK ( ::s; 2 1 - <P h( 1 - c) ~ - Cl 0- 3 and As before we obtain ( VNa) 2': <P ( <P h( 1 - c) - 0 - - - Cl ( VNa) 2': <P h(l - c)~ - Cl Ch2 - C - Cl ) . C - Cc + - - C - Cl )<P ' (c + 1), <p(c) + (-Cc +h - 2- and as in (3.9) we get Now we take K = h-1. 85 , C = h°.42 , Cl = hO. 14 and Ch = C+ hO. 13 . As in Lemma 11 we 43 can deduce that (T2 2': C4ho.15 where C4 is independent of h. The only new term we have in the non-coverage probability is 6p 6w 3 / 2 (T3yIK :s; (T3y1K' Suppose that min{w,w/(T2} :s; B. Then for all w > B, W/(T2:s; Band 6p 6B 3 / 2 -(J3-ylK-=K= :s; -ylK-K- = o( Ch - c) Ifw:S;B 6p 6B 3 / 2 6B 3 / 2 (T3yIK :s; (T3yIK :s; (C hO.15 )3/2yIK = O(Ch - c) . 4 This establishes P(p is not covered) :s; 1 - r for h sufficiently small. The remaining claims are proved as in Theorem 4. Remark 4. When the random variables Xi are bounded, then as in the sequential case we can choose Ch = c. However , to guarantee coverage probability r the second stage has to be modified to "take 3.4 IV ~~ l K more observations. " Related Literature A parametric problem was first considered by Anscombe in [1] in the case of the normal distribution. This problem is quite different from the Bernoulli problem considered in this thesis, since the sample mean and the sample variance are independent in the case of the normal distribution. Other notable results for normal populations 44 include those of Simons [17], who showed that a modified Chow-Robbins procedure achieves exact coverage, Starr [18], who investigates numerically the errors in the coverage probability approximation for a Chow-Robbins type boundary, and Woodroofe [20] , who finds an asymptotic lower bound on expected sample size under the condition of uniform convergence of the coverage probability. Also in the normal population case, second order results are obtained by Simons [17] and Woodroofe [20]. There are, however , no results in the literature establishing for non-normal distributions asymptotic optimality in the sense of Theorem 1, where confidence level ry is guaranteed. While there is considerable research which studies specific sampling plans and compares them to the hypothetical fixed sample size plan if the variance were known, there is no research which seeks to find optimal sequential procedures and lower bounds on their expected sample sizes, except [20] in the normal case. We conjecture that a lower bound on the average expected sample size, similar to Theorem 2 in the Bernoulli case, is true also for a general class of distributions, under suitable conditions. The first important theorem about a two-stage interval estimation procedure was established by Stein [19] in the case of the normal distribution. There have been other modifications and improvements of this procedure, for example [9] and [13]. However, the literature contains no optimality results , like those in Theorem 5, for non-normal distributions, except in [8] , where the exponential distribution is considered. For a comprehensive and up-to-date review in the area of fixed-width sequential and multistage confidence intervals , one can refer to [7] and [14] . 45 Chapter 4 Exact Lower Bounds and Nearly Optimal Procedures 4.1 Backward Induction Here we describe a method for computing explicit lower bounds on B(ry, d, A). We define a Bayes problem similar to the problem defined in Chapter 2. Let p be a random variable with density function A and let Xl, X 2 , ... be Bernoulli random variables with parameter p. Define the loss function of a sequential procedure (N, L, R), R = L + d to be where e and l are parameters to be specified later. We are interested in finding procedures that minimize the integrated risk I = E(£). There is a nice interpretation of this problem. An unknown p is selected from a known distribution A. A statistician can sample from Bernoulli(p) and each observation costs e. The statistician decides how much to sample and after stopping announces an interval of width d. The statistician receives (p(1 - p))l if p belongs to that interval and otherwise receives O. We are interested in the strategy that maximizes the earnings. The solution of this problem is given by Optimal Stopping Theory in the form of an algorithm called Backward Induction ([3], [5]). By Theorem 46 3, Chapter 7, in [3] there exists a t such that for the optimal strategy Pp(N :s: t) = 1 for all p. Therefore, we can restrict the search for the optimal strategy to the class of strategies with uniformly bounded sample size. The smallest possible posterior loss for (N, L , R), after observing s successes and j failures and stopping is J L+d E(£lj, s) = E(£IN = s + j, SN = s) = e(s + 1) - mF (p(l - p))I),(pls, 1) dp. L Let l(s, j) denote the smallest possible posterior loss of an optimal strategy, given that the point (s, 1) is reached. Then l(s,1) = min{E(£ls, j), P(Xs+f+l = lis, 1)1(s + 1,1) + P(Xs+f+1 = Ols, 1)1(s, j + I)} (4.1) This equation expresses the fact that the smallest possible conditional expected loss, given that the point (s, 1) is reached, is the minimum of the smallest loss if one stops and the smallest loss if one continues. The latter is evaluated by considering the probabilities of the cases Xs+f+1 = 1 and Xs+f+l = 0 and multiplying by the best possible conditional expected losses in those cases. Now we wish to compute 1= 1(0,0). To begin, we compute l(s, 1) for (s,1) = (0, t), (1, t - 1), ... , (t, 0) using l(s, j) = E(£lj, s). Then for each k = t - 1, t - 2, ... ,0 in succession, the "backward induction" proceeds by computing l(s, 1) for (s , 1) = (0, k), (1 , k - 1) , ... , (k, 0) using (4.1). The optimal 47 stopping time is defined by: stop at the first n such that i.e., the stopping points are those (s, 1) for which I(s , 1) = E(£ls, f), and each point which is not a stopping point is a continuation point. Denote I by Ie,l and the optimal stopping time by N* (e, l) to indicate the dependence on the parameters e and l. The stopping rule N *, with parameters chosen properly, is the stopping rule which we want to calculate. Also, the value of Ie,l leads to a lower bound on BCr, d,),) in the following way. If (N, L, R) is a width d level , confidence interval, then 1 1 Ie,l ::; E(£(N, L , R)) = e j EpN),(p) dp - j Pp(L ::; p::; R)(p(l - p))l),(p) dp o 0 1 1 ::; e j EpN),(p)dp-, j(P(l-P))I)'(P)dP, o 0 which implies the lower bound 1 Ie,l +, J(p(l - p))l ),(p) dp BCr, d,),) ~ ___O~_ _ _ __ e (4.2) Relation (4.2) is used to obtain a numerical lower bounds on BCr, d,),) by choosing pairs of values of e and l, computing Ie,l by backward induction, and using the largest value of the right-hand side of (4.2) obtained in this way. 48 Remark 5. For other families of distributions the factor (p(l- p))1 should be replaced Remark 6. We can obtain analytically a value of t that can be used in the algorithm but such a t would be unnecessarily large. Instead we guess a value of t, start the algorithm, and if there are continuation points on the line s + f = t, we increase t, repeating the procedure until there are no continuation points on that line. As an initial guess of t we take c2 / d2 , which is the asymptotic result for p = 0.5 . 4.2 Asymptotically Efficient Stopping Times Here we describe explicitly the stopping rules suggested by the asymptotic theory. Suppose that we are interested in finding a width 2h level 'Y confidence interval 1 (N, L, R) for p that minimizes J Ep(N)fa,b(P) dp, where fa,b(P) is the Beta(a , b) deno sity function. The stopping rule N'(K) suggested by the asymptotic theory is N'(K) = min {n 2 n _ K > c (s + a)(J + b)} - h 2n 2 ' where c = 11>-1 ((1 + 'Y)/2) and s = Sn , f = n - Sn. The stopping rule depends on a parameter K which is restricted to integer values, for simplicity. The two stage procedure, NI/(Ch' K), depending on the parameters Ch and K, is defined by: the sample size for the first stage is K and the sample size for the second stage is max {a r c~(s + a)(J + b)l- K} , h 2 K2 ' 49 where s = SK is the number of observed successes during the first stage and f - K - SK is the number of observed failures during the first stage. When the second stage sample size is 0, the sampling terminates after the first stage. The parameters Ch and K will be determined numerically as described in Section 4.4. R emark 7. It was suggested by the asymptotic theory that for the fully sequential procedures only the parameter K needs to be selected and Ch can b e taken to be c. For the two-stage procedure both parameters Ch and K need to be selected numerically. Our numerical investigation shows that if we restrict Ch to C in the two-stage procedure, t he performance suffers. This was also suggested by the asymptotic theory. 4.3 Lorden's Push Algorithm In this section we will discuss Lorden's method for constructing confidence intervals that improve upon the p erformance of [Xn - h, Xn + h]. Lorden shows ([12]) that in the fixed sample size case one can improve the minimum coverage probability obtained by fixed width d confidence intervals by letting [L , R] increase as a function of Xn as rapidly as possible, i.e., the intervals [L, R] are pushed to the right as much as possible. This push algorithm can also b e applied in the sequential setting for any given stopping rule, N (see Theorem 7), and the algorithm constructs the socalled pushed confidence intervals. The pushed confidence intervals applied to the stopping rules N* (e , l) , N' (K) and Nil (Ch' K) described in the previous sections form the confidence interval procedures that we propose for use. Fix a stopping rule N. In order to apply the push algorithm we need to define 50 an ordering of the stopping points (s, 1) = (SN, N - S N)' The push algorithm uses this ordering to set confidence intervals covering smaller p values for smaller points, i.e., if (s, 1) precedes (s', II) then L(s , 1) ~ L(s',1') and R(s , i) ~ R(s', I'). In the fixed sample size case the optimal (see [12]) ordering of the stopping points is defined by their maximum likelihood estimate of p, i.e., by the number of successes. In the sequential case such an optimality property is not known, i.e., there is no reasonable conjecture that determines the optimal ordering of the stopping points. In the hope of achieving near-optimality, we propose to use the maximum likelihood estimate of p, i.e., if (8,1) and (8',1') are two stopping points, we say that (8,1) precedes (8',1') if 8/ (s + i) < s' / (s' + i')· If s / (s + 1) = s' / (s' + 1'), we say that (8, 1) precedes (s', 1') if s < s'. Index the stopping points as (Si' Ii) for i = 1, ... ,]. Let J be the index of the actual stopping point (SN , N - SN ). Now we have to define the confidence interval [L , RJ for all the possible values of J, 1, ... ,], so that Land R increase as a function of J as rapidly as possible. There is another consideration that plays an important role. The sample space of J is finite, and if the confidence intervals are based only on J, then the coverage probability as a function of p will have relatively large jumps at the endpoints of the confidence intervals. Greater efficiency, i.e. , larger 1', is achievable by reducing the size of the jumps through a technique called randomization. Let U be a uniformly distributed random variable on the interval [-0.5,0.5]' independent of the XIs . Let Y = SN + U. The randomized pushed confidence intervals for p are based on the value of Y, i.e., L = L(Y) and R = L + d increase in Y as rapidly as possible. 51 The optimality property that determines the construction of Lorden's pushed intervals, even in the fixed sample size case, requires that the endpoints Land R of the confidence intervals be restricted to a finite grid {O, !, ~, ..., rn~l, 1} in order to make a numerical algorithm possible. As explained in [12], the construction of optimal [L , R] that are not limited to a grid requires taking monotonic majorants, which are not computable. In our numerical investigations we use m = 105 , so that little is lost by this restriction. Theorem 8 shows that ~ is an upper bound on the difference between the unrestricted shortest-width intervals and shortest-width intervals that are grid limited, i.e., that have end points in {O, !, ... ,1}. Let Pk = ! for k = 0, .. . ,m. Definition 1. A confidence interval [L , R] has grid coverage level '"Y if for k = 1, ... , m (4.3) for P = Pk- l and P = Pk · Choose m and r so that .I.... = d. rn Theorem 6 (Lorden). Grid-limited level '"Y confidence intervals have grid coverage level '"Y. Proof. Let [L , R] be a grid-limited level '"Y confidence interval. Let Yk = inf{yIL(y) > Pk} for k = 0, ... , m and Yk = -0.5 for k = -r, ... , -1. Note t hat 52 {ydk=-r is a nondecreasing sequence. Suppose Pk- l < P < Pk. Then { ::; Pp(L(Y) ::; P ::; R(Y)) = Pp(L(Y) ::; Pk-l < Pk ::; R(Y)) (4.4) Now L(y) ::; Pk- l if and only if y < Yk or Y = Yk and L(Yk) ::; Pk- l' Also R(y) 2:: Pk if and only if L(y) :2: Pk- r if and only if Y > Yk-r or Y = Yk - r and L(Yk- r) = Pk-r. Since Y is a continuous random variable, for all P Since Pp(Yk- r ::; Y ::; Yk) is a continuous function of p, we obtain that Pp(L(Y) ::; Pk-l < Pk ::; R(Y)) is a continuous function of p, and since inequality (4.4) is valid for P E (Pk - l,Pk) we conclude that for P = Pk- l and P = Pk· In the fixed sample size case, the converse of the above theorem is also true, as shown in [12]. However, in the sequential case it is not true in general for all stopping rules, but it is true for some classes of stopping rules. Discussion of this will appear in [2]. When m is large the coverage level of a confidence interval is well approximated by its grid-coverage level and the procedures that we propose achieve grid-coverage level {. 53 Denote by Fk the distribution function of Y when Pk is true, i.e., Fk(y) = Pp=Pk (Y ::; y). Since Y is a continuous random variable, the inverse functions Fk- 1 (ex) , k = 0, ... , m, defining the ex quantiles are well-defined and are strictly increasing for °< ex < 1. It is convenient to define for all k Fk- l(ex) = ° -.5 if ex = j + .5, if ex = 1 +00, if a > 1, which preserves the strictly increasing property. We are interested in finding the smallest integer r such that there exist grid-limited width rim level '"Y confidence intervals for p that are nondecreasing functions of Y. Theorem 7 (Lorden). Suppose a stopping time N is given and also an ordering {(Si ' fi) , i = 1, .. }} of the stopping points. Fix m and require that L, R E {a, 11m, 21m, ... , 1}. Suppos e that there exists a width rim confidence interval [L , R] with grid coverage level '"Y such that L(Y) and R(Y) are nondecreasing in Y. Then there exists a nondecreasing sequence {ydk=-r such that if Yk < Y < Yk+l then [L(y), R(y)] = [Pk,Pk+r]' (4.5) The sequence {Yk}k= - r satisfies (4.6) 54 As a consequence, Yk 2:: Xk for all k, where {xdk=-r is defined by Xk = -0.5 if k < 0 and if k 2:: 0 Then ( 4.8) defines grid-limited width rim confidence intervals with grid coverage level ,",(, and L*(y) 2:: L(y) and R*(y) 2:: R(y) for all y. Proof. Let Yk = inf{yIL(y) 2:: Pk} Then (4.5) is clearly satisfied. We have and The two inequalities yield 55 and which proves (4.6), since {yd is nondecreasing. Now it is straightforward to prove by induction on k that Yk 2: Xk· The induction step uses the fact that Yk-r 2: Xk-r implies Fj(Yk-r) 2: Fj(Xk-r) for j = k - 1, k and the fact that F j- 1 is nondecreasing. The confidence interval [L *, R*] has grid confidence level '"Y since (4.7) implies that (4.9) and (4.10) hold with Xk in place of Yk. Note that the sequence {Xk} is well-defined whether or not width rim confidence intervals of grid coverage level '"Y exist. The terms Xk are all finite if and ony if Fk-1(Xk-r) :::; 1 - '"Y for all k. This is how we numerically check whether grid level '"Y width d confidence intervals exist: we compute the sequence {xd using equation (4.7), and if Xm is finite the algorithm succeeds and equation (4.8) defines the pushed confidence intervals. Otherwise, Theorem 7 says that width rim intervals with grid coverage level '"Y do not exist. Thus, given Nand m, we can use the push algorithm to find the smallest r (by trial and error) for which width rim confidence intervals of grid coverage level '"Y exist as a nondecreasing function of Y. The following theorem shows that grid-limited confidence intervals are not much longer than non-grid-limited ones. Theorem 8 (Lorden). Suppose that r is the smallest integer such that grid limited width rim level '"Y confidence intervals nondecreasing in Y exist. If there exists a level '"Y width d confidence interval procedure that is nondecreasing in Y, then d > (r-2)/m. Proof. Suppose that d :::; (r - 2)/m. If Pj :::; L(y) < pj+l then R(y) < Pj+r-l· 56 Define [L*(y), R*(y)] = [pj,Pj+r-l] for such y. Then clearly [L*(y), R*(y) ] defines a nondecreasing grid-limited width (r-1)/m confidence interval with coverage probability 'Y, contrary to t he assumption that rim is the smallest possible level 'Y monotonic grid limited confidence interval. Remark 8. The pushed confidence intervals are not symmetric with respect to the symmetry on the interval [0,1] : P --+ 1 - p. However , Lorden has shown in [12] that the pushed confidence intervals, once they are constructed , can b e easily modified to be symmetric and all the optimalities continue to hold. 4.4 Numerical Examples In this section we report numerical results obtained for specific sets of parameters. We use inequality (4.2) to produce explicit lower bounds on B("( , d, '\). The maximization with respect to the parameters land e is done on a grid. Given 'Y, d, and ,\ we wish to determine the set of parameters defining N*, N' and Nil for which the push algorithm succeeds, i.e. , such that the push algorithm constructs width d level 'Y confidence intervals for P and (4.11) is minimal. For N* this is done in the following way. For a fixed l, Ep (N* (e, l)) is a decreasing function of e. Therefore, for l on a grid we determine the largest e for which the push 57 algorithm succeeds. Then we minimize (4.11) with respect to l. The values of l we used are all in the interval [0,2]. The value of K that specifies N' is selected to be the smallest K for which the push confidence intervals succeed, the reason being again that Ep(N'(K)) in increasing in K. Since K is an integer this computation is very fast . In fact the biggest advantage of N' is that it requires much less computation when compared to N* and Nil. The search for K is initiated at K = O. The search for the optimal parameters Ch and K for the two stage procedure N"(Ch, K) is done in the following way. Since Ep(N"(Ch, K)) is increasing in Ch, for a fixed K we determine the smallest Ch for which the push algorithm succeeds and then we minimize (4.11) with respect to K. Tables 1 and 2 show that all three procedures that we propose come very close to being optimal. Another conclusion that we can draw (something we already suspect from the asymptotic theory) is that the advantage of a fully sequential procedure when compared to a two-stage procedure is relatively small, and the two-stage procedures are very effective in the Bernoulli problem. Table 2 also shows that occasionally the two-stage procedure Nil performs better than the sequential, but this is due to the fact that the two stage procedure is optimized with respect to two parameters and the sequential is optimized only with respect to one parameter, which we artificially restricted to the integer values for simplicity. Also in Table 2 in one instance the Bayesian procedure performed worse than the sequential and the two-stage procedure, which we think is due to the discrete nature of E(N). Table 3 shows maxp Ep(N*) 58 and max N*, which occurs for p = 0.5. The results show that our procedures always perform better than the Classical Extreme Tails method. However, they perform worse than Lorden's best fixed sample size method for some values of p. Table 4 shows the optimal choice for the parameters defining the stopping rules. Figures 4.1 and 4.2 show the stopping boundaries N* and N ' , which are very close. Figures 4.3 and 4.4 show the stopping boundaries for the two-stage rule. The meaning of the graph is the following: the straight line represents the first stage sample size and to get the second stage sample size one needs to find the intersection point of the second boundary and the line connecting the origin of the coordinate system and the position of the random walk after the first stage. The sum of the two coordinates of that intersection point represents the total number of observations. Figures 4.5 and 4.6 show Ep(N*) as a function of p when the prior function is Beta(l, 1) and Beta(3,3) compared to the classical fixed sample method and Lorden's best fixed sample method. Figures 4.7 and 4.8 show the curves defining the pushed confidence intervals and, for comparison, the straight lines defining the centered confidence intervals. 59 Table 1. Average Expected Sample Size with Uniform Prior, ,"(=0.95 h Classical Extreme Tails Lorden Fixed-Sample Size Two-Stage Proced ure( N") Sequential Procedure(N') Bayesian Procedure(N*) Lower Bound 0.1 104 78 65.1 63.1 62.6 61.1 0.065 240 199 154.3 152.5 151.3 149.0 0.05 402 347 261.4 256.9 256.0 253.7 0.03 1096 1004 722.2 714.2 712.3 709.3 Table 2. Average Expected Sample Size with Beta(3,3) Prior, '"(=0.95 0.1 104 78 76.3 76.7 76.1 74.6 h Classical Extreme Tails Lorden Fixed-Sample Size Two-Stage Procedure(N") Sequential Procedure(N') Bayesian Procedure(N*) Lower Bound 0.065 240 199 188.9 189.2 188.2 187.0 0.05 402 347 323.3 323.3 323. 1 321.3 0.03 1096 1004 909.4 908.5 909.7 906.6 Table 3. maxpEp(N*) and maxN* with Uniform Prior, ,"(=0.95 h maxpEp(N*) maxN* 0.1 90.9 92 0.065 222.1 225 0.05 376.8 378 0.03 1065.8 1068 Table 4. Parameter Specification with Uniform Prior, ,"(=0.95 h (Ch , K) for N" (K) for N' (e10 - 0, l) for N* Lower Bound 0.1 (1.8,36) -7 (1.69,0.81) (1.8,1.2) 0.065 (1.87,52) -5 (0.7283,0.87) (0.76,1.17) 0.05 (1.908,95) -5 (0.4368,0.87) (0.45,1.1 ) 0.03 (1.938 ,190) -3 (0.1594,1) (0.16,1.05) 60 Figure 4.1: N * and N'(dotted line) , Uniform Prior, h = 0.1, '"Y = 0.95 50 40 30 20 10 10 20 30 40 50 61 Figure 4.2: N* and N'(dotted line), Uniform Prior, h = 0.03, 'Y = 0.95 600 500 400 300 200 100 100 200 300 400 500 600 62 Figure 4.3: Nil, Uniform Prior, h = 0.1, 1=0.95 50 40 30 20 10 10 20 30 40 50 Figure 4.4: Nil , Uniform Prior, h = 0.03, 1=0.95 600 500 400 100 100 200 300 400 500 600 63 Figure 4.5: Ep(N*), Uniform Prior (the more p eaked graph) and Beta(3,3) Prior, Classical Fixed Sample and Best Fixed Sample, h = 0.1, "y = 0.95 100 B0r--------7r---------~~-------- 0.2 0.4 0.6 O.B 1 Figure 4.6: Ep(N*), Uniform Prior (the more p eaked graph) and Beta(3,3) Prior, Classical Fixed Sample and Best Fixed Sample, h = 0.03, "y = 0.95 1000 ~--------~~----~----------- BOO 600 0.2 0.4 0.6 O.B 1 64 Figure 4.7: Pushed Confidence Intervals for N* and centered intervals, Uniform Prior, h = 0.1, "( = 0.95 1 0.2 0.4 0.6 0.8 1 Figure 4.8: Pushed Confidence Intervals for N* and centered intervals, Uniform Prior, h = 0.03, "( = 0.95 1 0.8 0.6 0.4 0.4 0.6 0.8 1 65 Bibliography [1] Anscombe, F.J. Sequential Estimation, J .R. Statist. Soc., Ser. B, 15(1953) 1- 21 [2] Asparouhov, T. On the Unimodality of some Binomial Probabilities (in preparation) [3] Berger, J. O. Statistical decision theory and Bayesian analysis. Springer Series in Statistics. Springer-Verlag, New York-Berlin, 1985 [4] Chow, Y. S.; Robbins, H. On the asymptotic theory of fixed-width sequential confidence intervals for the mean. Ann. Math. Statist. 36 1965 457-462 [5] Chow, Y. S.; Robbins, H.; Siegmund, D. Great expectations: the theory of optimal stopping. Houghton Mifflin Co., Boston, Mass. , 1971 [6] Feller, W . An Introduction to Probability Theory and its Applications , Vol. I, 1957, second edition. John Wiley & Sons, New York [7] Ghosh, M. ; Mukhopadhyay, Nitis; Sen, Pranab K. Sequential estimation. Wiley Series in Probability and Statistics: Probability and 66 Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997 [8] Ghurye, S. G. Note on sufficient statistics and two-stage procedures. Ann. Math. Statist.(1958) 29 155-166 [9] Hall, P. Asymptotic theory of triple sampling for sequential estimation of the mean, Ann. Statist. 9(1981) 1229- 1238 [10] Karr, A. Probability, Springer-Verlag New York, Inc., 1993 [11] Lehmann, E. L. Testing statistical hypotheses. John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1959 [12] Lorden, G. Shortest Fixed Width Confidence Intervals for the Bernoulli parameter p (to appear) [13] Mukhopadhyay, N. A consistent and asymptotically efficient twostage procedure to construct fixed-width confidence intervals for the mean. Metrika, 27, 281- 284 [14] Mukhopadhyay, N.; Solanky, T. K. S. Multistage selection and ranking procedures. Second-order asymptotics. Statistics: Textbooks and Monographs, 142. Marcel Dekker, Inc., New York, 1994 [15] Robbins, H.; Siegmund, D.; Wendel, J. The limiting distribution of the last time Sn 2': nc. Proc. Nat. Acad. Sci. U.S.A. 61, 1968 1228-1230 67 [16] Ross, Sheldon M. Introduction to Probability and Statistics for Engineers and Scientists. Wiley Series in Probability and Mathematical Statistics 1987 John Wiley & Sons, Inc., New York [17] Simons, G. On the cost of not knowing the variance when making a fixed width confidence interval for the mean, Ann. Math. Statist. 39 (1968), 1946-1952 [18] Starr, N. The performance of a sequential procedure for fixed width confidence interval estimation of a mean, Ann. Math. Statist. 37(1966), 1215- 1218 [19] Stein, C. A two-sample test for a linear hypothesis whose power is independent of the variance, Ann. Math. Statist. 5(1977), 984- 995 [20] Woodroofe, M. Asymptotic optimality in sequential interval estimation. Adv. in Appl. Math. 7 (1986), no. 1, 70-79