Convergence rate of the dependent bootstrapped means

THEORY PROBAB. APPL.c 2006 Society for Industrial and Applied Mathematics Vol. 50, No. 2, pp. 337–346 Translated from Russian Journal CONVERGENCE RATE OF THE DEPENDENT BOOTSTRAPPED MEANS∗ A. VOLODIN†,M.ORD ´ O˜ NEZ CABRERA‡,AND T. C. HU§ (Translated by A. Volodin) Abstract. In this paper, a Baum–Katz, Erd¨os, Hsu–Robbins, Spitzer type complete convergence result is obtained for the dependent bootstrapped means. Key words. bootstrapped means, dependent bootstrap, rate of convergence, exponential inequalities, strong law of large numbers DOI. 10.1137/S0040585X97981688 1. Introduction. The main focus of the present investigation is to obtain the convergence rates in the form of a Baum–Katz, Erd¨os, Hsu–Robbins, Spitzer type complete convergence result for the dependent bootstrapped means from a sequence of random variables. The work on the consistency of bootstrap estimators has received much attention in recent years due to a growing demand for the procedure in both theoretical and practical applications. It is important to note that exponential inequalities are of practical use in establishing the strong asymptotic validity of the bootstrapped mean. We begin with a brief discussion of results in the literature pertaining to a sequence of independent and identically distributed (i.i.d.) random variables and classical (independent) bootstrap of the mean. Let {X, Xn,n1}be a sequence of i.i.d. random variables defined on a probability space (Ω,F,P). For ω∈Ω and n1, let Pn(ω)=n−1n i=1 δXi(ω)denote the empirical measure and let { X(ω) n,j ,1jm(n)}be i.i.d. random variables with law Pn(ω), where {m(n),n1}is a sequence of positive integers. In other words, the random variables { X(ω) n,j ,1jm(n)}result by sampling m(n) times with replacement from the nobservations X1(ω),... ,X n(ω) such that for each of the m(n) selections, each Xj(ω) has probability n−1of being chosen. For each n1, { X(ω) n,j ,1jm(n)}is the so-called [7] bootstrap sample from X1,... ,X nwith bootstrap sample size m(n). Let Xn(ω)=n−1n j=1 Xj(ω) denote the sample mean of {Xj(ω), 1 jn},n1. Bickel and Freedman [4] showed that when Xis nondegenerate and EX2<∞, for almost every ω∈Ω the central limit theorem (CLT) n1/21 n n  j=1  X(ω) n,j −Xn(ω)d −→ N(0,σ2) ∗Received by the editors February 14, 2004. This work was supported by National Sciences and Engineering Research Council of Canada grants BFM 2000-0344-C0201, FQM 127, and NSC91-2118M-007-008. http://www.siam.org/journals/tvp/50-2/98168.html †Department of Mathematics and Statistics, University of Regina, Regina, Saskatchewan, S4S 0A2, Canada ([email protected]). ‡Department of Mathematical Analysis, University of Seville, Seville 41080, Spain (cabrera@ us.se). §Department of Mathematics, Tsing Hua University, Hsinchu 30043, Taiwan (tchu@math. nthu.edu.tw). 337 338 A. VOLODIN, M. ORD ´ O˜ NEZ CABRERA, AND T. C. HU is valid. Here and in what follows, σ2=VarX. Note that by the Glivenko–Cantelli theorem, Pn(ω) is close to L(X) for almost every ω∈Ω and all large n, and by the classical L´evy CLT, n1/21 n n  j=1 Xj−EXd →N(0,σ2). It follows that for almost every ω∈Ω, the bootstrap statistic n1/21 n n  j=1  X(ω) n,j −Xn(ω) is close in distribution to that of n1/21 n n  j=1 Xj−EXd −→ N(0,σ2) for all large n. This is the basic idea behind the bootstrap. See the pioneering work of Efron [7], where this nice idea is made explicit and where it is substantiated with several important examples. Strong laws of large numbers were proved by Athreya [2] and Cs¨org˝o [6] for bootstrapped means. Arenal-Guti´errez, Matr´an, and Cuesta-Albertos [1] analyzed the results of [2] and [6]. Then, by taking into account the different growth rates for the resampling size m(n), they gave new and simple proofs of those results. They also provided examples that show that the sizes of resampling required by their results to ensure almost sure (a.s.) convergence are not far from optimal. Another reference which is important to this paper is the work of Mikosch [10]. He established a series of useful exponential inequalities that are an important tool for deriving results on the consistency of the bootstrapped mean. Based on these exponential inequalities, the Baum–Katz, Erd¨os, Hsu–Robbins, Spitzer type complete convergence result for the bootstrapped means and a moment result for the supremum of normed bootstrapped sums were established in [9]. It is important to note that in [9] no assumptions were made concerning either the marginal or the joint distributions of the random variables from which bootstrap resamples are withdrawn. We follow the same approach in this paper. The notion of the dependent bootstrap procedure was introduced in [12], where some important properties were also established. The main goal of the present paper is to extend and generalize the results of [9] on the strong law of large numbers for the case of the dependent bootstrap procedure. The main tools are the extensions and generalizations of the result of [10] (section 4) and [12] (section 2). 2. Dependent bootstrap. The results from this section are modifications, generalizations, and extensions of the results of [12] and [13] for the dependent bootstrap from the sequence of unnecessary i.i.d. random variables. We mention that Smith and Taylor [12], [13] consider only the i.i.d. case. We present this case as a simple reference since it plays a role in the following. Let {Xn,n1}be a sequence of random variables (which are not necessarily independent or identically distributed) defined on a probability space (Ω,F,P). Let {m(n),n1} and {k(n),n1}be two sequences of positive integers such that for all n1, m(n) nk(n).For ω∈Ω and n1, the dependent bootstrap is defined as the sample of size m(n), CONVERGENCE RATE OF THE DEPENDENT BOOTSTRAPPED MEANS 339 denoted { X(ω) n,j ,1jm(n)}, drawn without replacement from the collection of nk(n) items made up of k(n) copies, each of the sample observations X1(ω),... ,X n(ω). This dependent bootstrap procedure is proposed as a procedure to reduce variation of estimators and to obtain better confidence intervals. The dependent bootstrap procedure is proposed as a procedure to reduce variation of estimators and to obtain better confidence intervals. We refer to [13], where this fact is proven and simulated confidence intervals are used to examine possible gains in coverage probabilities and interval lengths. The first proposition gives us the joint distribution of the dependent bootstrap random variables. We need the following notation. For ω∈Ω, n1,and a real number x, denote τ(x)= n  j=1 IXj(ω)x, where I(·) is the indicator function. Hence, τ(x) is the random variable that counts the number of observations less than or equal to x. For a finite sequence {x1,x 2,... ,x m}of real numbers, denote by {x(1),x (2),... ,x (m)} its nondecreasing rearrangement, that is, x(1) x(2) ··· x(m), and for any 1 jm there exists 1 imsuch that xi=x(j). Proposition 1. For ω∈Ω, n1, and a sequence {x1,x 2,... ,x m}of real numbers we have the following: 1) If k(n)τ(x(j))jfor all 1jm(n), then P X(ω) n,1x1,... ,  X(ω) n,m(n)xm(n)= m(n)  j=1 k(n)τ(x(j))−(j−1) k(n)n−(j−1) . 2) If k(n)τ(x(j))<jfor at least one 1jm(n), then the above probability is zero. Proof. Let πbe the reordering of {1,2,... ,m(n)}such that π(j)=ifor xi=x(j). Then P X(ω) n,1x1,... ,  X(ω) n,m(n)xm(n)=P X(ω) n,π(1) x(1),... ,  X(ω) n,π(m(n)) x(m(n)) =P X(ω) n,π(1) x(1)P X(ω) n,π(2) x(2) | X(ω) n,π(1) x(1)×··· ×P X(ω) n,π(m(n)) x(m(n)) | X(ω) n,π(1) x(1),... ,  X(ω) n,π(m(n)−1) x(m(n)−1) = m(n)  j=1 k(n)τ(x(j))−(j−1) k(n)n−(j−1) if k(n)τ(x(j))jfor all 1 jm(n). The second part of the proposition is obvious. Of course, the dependent bootstrap random variables { X(ω) n,j ,1jm(n)}are dependent. They obey the so-called negatively dependent property; this property will be established in Proposition 2. The concept of negatively dependent random variables was introduced by Lehmann [8] as follows. 340 A. VOLODIN, M. ORD ´ O˜ NEZ CABRERA, AND T. C. HU The random variables Y1,Y 2,... are said to be negatively dependent if for each n2 the following two inequalities hold: P{Y1y1,... ,Y nyn} n  i=1 P{Yiyi} and P{Y1>y 1,... ,Y n>y n} n  i=1 P{Yi>y i}, for any sequence {y1,... ,y n}of real numbers. Proposition 2. For ω∈Ωand n1the dependent bootstrap random variables { X(ω) n,j , 1jm(n)}are negatively dependent and exchangeable. Proof. For the negative dependence property we will prove only the first inequality. The proof of the second one is completely the same. Let {x1,x 2,... ,x m(n)}be a sequence of real numbers. It is interesting to consider only the case k(n)τ(x(j))jfor all 1 jm(n). By Proposition 1 P X(ω) n,1x1,... ,  X(ω) n,m(n)xm(n)= m(n)  j=1 k(n)τ(x(j))−(j−1) k(n)n−(j−1)  m(n)  j=1 k(n)τ(x(j)) k(n)n= m(n)  j=1 P X(ω) n,j xj. The exchangeability is obvious by Proposition 1. 3. A few technical lemmas. In this section we present a few technical results that we will use in proofs of the main results of the paper. Some of the lemmas are only generalizations and extensions of well-known results. For expository purposes we outline their proofs. For simplicity, by the log-function in this section we mean the natural logarithm function. The results can be easily generalized on any other logarithm function with base greater than one. The first lemma is well known (cf., for example, [5]) and trivial. So, we omit the proof. Lemma 1. Let {Yn,n1}be a sequence of negatively dependent random variables. 1) If {fn,n1}is a sequence of measurable real functions all of which are monotone increasing (or all monotone decreasing), then {fn(Yn),n1}is a sequence of negatively dependent random variables. 2) For any n1, En 1Yjn 1EYj,provided the expectations are finite. Unfortunately, it is not possible to find the inverse function to the function φ(t)= t1/β/log t,t>0, 0 <β<e, in the closed form. But the following lemma gives a good “approximation” to the inverse function. Lemma 2. Let φ(t)=t1/β/log tand ψ(t)=tβlogβt,te,0<β<e. Then 1 β1−β eβ tψφ(t)1 ββ t. Proof. Note that ψ(φ(t)) = t ββ1−βlog log t log tβ and 1 −β e1−βlog log t log t1 for te, which can be established by differentiation. CONVERGENCE RATE OF THE DEPENDENT BOOTSTRAPPED MEANS 341 The main idea of Lemma 2 is that for a positive random variable Y, the assumptions Eφ−1(Y)<∞and Eψ(Y)<∞are equivalent. The following lemma can be found in [11, Theorem 2]. Note that there is no independence assumption. Lemma 3. Let φ(t), t>0, be a continuous function that is positive,strictly increasing, and satisfying the condition φ(t)→∞as t→∞. Put bn=φ(n), n1. Moreover,let {Yn,n1}be a sequence of identically distributed random variables. If ∞  j=n 1 bj =On bnand Eφ−1(Y1)<∞, where φ−1is the inverse of φ,then 1 bn n  j=1 Yj=0 a.s. In the following lemma it is also important to note that there is no independence condition. Lemma 4. Let {Xn,n1}be a sequence of identically distributed random variables such that E|X1|αlog |X1|α/2<∞ for some 0<α<2. Then log n n2/α n  j=1 X2 j−→ 0a.s. Proof. In order to apply Lemma 3, put Yn=Xn2,bn=n2/α/log n,n1, and β=α/2 (then 0 <β<1). If we consider φ(t)=t1/β/log t,te, then bn=φ(n) and according to Lemma 2 with ψ(t)=tβ(log t)β, the conditions Eφ−1(Y1)<∞and Eψ(Y1)<∞are equivalent. Note that Eψ(Y1)=2 α/2E|X1|αlog |X1|α/2<∞. The last thing we need to prove is that ∞ j=n1/bj=O(n/bn). We have ∞  j=n 1 bj = ∞  j=n log j j1/β = ∞  m=1 n(m+1)−1  k=nm log k k1/β  ∞  m=1 nlog(mn) (nm)1/β . Since the sequence {log k/k1/β ,ke1/β}is strictly decreasing the last sum is not greater than nlog n n1/β ∞  m=1 1 + log m/ log 2 m1/β =Cnlog n n1/β =Cn bn . By Lemma 3, log n n2/α n  j=1 X2 j→0 a.s. Lemma 4 is proved. The following two lemmas deal with the convergence of maximums of random variables. Again, no assumption of independence is made. Lemma 5. Let {Xn,n1}be a sequence of positive random variables and let {bn, n1}be a nondecreasing sequence of positive constants such that bn→∞. Then the assumptions Xn/bn→0a.s. and max1jnXj/bn→0a.s. are equivalent. 342 A. VOLODIN, M. ORD ´ O˜ NEZ CABRERA, AND T. C. HU Proof. Let Xn/bn→0 a.s. For arbitrary nk2, 1 bn max 1jnXj1 bn max 1jk−1Xj+1 bn max kjnXj1 bn max 1jk−1Xj+ max kjn Xj bj . Since {bn,n1}is nondecreasing the last expression is not greater than 1 bn max 1jk−1Xj+ sup jk Xj bj −→ 0, where first n→∞and then k→∞. The reverse implication is obvious. The following lemma in this section is a generalization of the corollary to Theorem 3 of [3]. Lemma 6. Let ψ(t),t0, be a strictly increasing function and let {bn,n1} be a nondecreasing sequence of positive numbers such that ψ(bn)Cn,n1, where the constant Cdoes not depend on n. Moreover,let {Xn,n1}be a sequence of positive identically distributed random variables such that Eψ(X1/ε)<∞for all ε>0. Then 1 bn max 1jnXj→0a.s. Proof. For any ε>0 ∞  n=1 P{Xn>εb n} ∞  n=1 PC−1ψX1 ε>n C−1EψX1 ε<∞. Then by the Borel–Cantelli lemma Xn/bn→0 a.s. By Lemma 5 we obtain that 1 bn max 1jnXj→0 a.s. The next exponential inequality in this section is a key tool used in the proof of the law of large numbers for the dependent bootstrap of the mean presented in the theorem. It is an analogue of the Mikosch exponential inequality [10, Lemma 5.1] for the case of the dependent bootstrap. We need to add two more notations to the notations from section 2. Let {Xn,n1} be a sequence of (not necessarily independent or identically distributed) random variables. For ω∈Ω and n1 denote Mn(ω)= 1 m(n)max 1jnXj(ω)−Xn(ω)and Bn(ω)= 1 nm(n) n  j=1 Xj(ω)−Xn(ω)2, where Xn(ω)= 1 n n  j=1 Xj(ω) denote the sample mean of {Xj(ω), 1 jn},n1. Lemma 7. Let {an,n1}and {hn,n1}be two sequences of positive reals. Then for ω∈Ωand n1such that hnMn(ω)<1and all ε>0, the following inequality holds: P 1 m(n) m(n)  j=1  X(ω) n,j −Xn(ω)εan2 exp −εhnan+h2 nBn(ω) 2(1 −hnMn(ω)). CONVERGENCE RATE OF THE DEPENDENT BOOTSTRAPPED MEANS 343 Proof. By Markov’s inequality P 1 m(n) m(n)  j=1  X(ω) n,j −Xn(ω)εan exp{−εhnan}Eexp hn 1 m(n) m(n)  j=1  X(ω) n,j −Xn(ω) exp{−εhnan}Eexp hn1 m(n) m(n)  j=1  X(ω) n,j −Xn(ω) + exp{−εhnan}Eexp −hn1 m(n) m(n)  j=1  X(ω) n,j −Xn(ω). We will estimate only the expectation in the first item of the last expression; the same bound is valid for the second expectation. Note that by Proposition 2 the dependent bootstrap random variables { X(ω) n,j ,1j m(n)},n1, are negatively dependent and exchangeable. Hence, by Lemma 1(1) the random variables exp hn m(n) X(ω) n,j −Xn(ω),1jm(n) are negatively dependent and identically distributed. Therefore, Eexp hn1 m(n) m(n)  j=1  X(ω) n,j −Xn(ω)=Em(n)  j=1 exp hn m(n) X(ω) n,j −Xn(ω)  m(n)  j=1 Eexp hn m(n) X(ω) n,j −Xn(ω) by Lemma 1(2). By identical distribution this expression is equal to Eexp hn m(n) X(ω) n,1−Xn(ω)m(n) =1 n n  i=1 exp hn m(n)Xi(ω)−Xn(ω)m(n) =1+ 1 n n  i=1 h2 n 2! m(n)2Xi(ω)−Xn(ω)2+h3 n 3! m(n)3Xi(ω)−Xn(ω)3 +h4 n 4! m(n)4Xi(ω)−Xn(ω)4+···m(n) =1+ h2 n m(n) n  i=1 (Xi(ω)−Xn(ω))2 nm(n) ×1 2! +hn 3! Xi(ω)−Xn(ω) m(n)+h2 n 4! Xi(ω)−Xn(ω) m(n)2 +···m(n) 1+ h2 n m(n) Bn(ω) 21+hnMn(ω)+hnMn(ω)2+···m(n) =1+ h2 n 2m(n) Bn(ω) 1−hnMn(ω)m(n) exp h2 n 2m(n) Bn(ω) 1−hnMn(ω)m(n) = exp h2 nBn(ω) 2(1 −hnMn(ω)). 344 A. VOLODIN, M. ORD ´ O˜ NEZ CABRERA, AND T. C. HU Hence, P 1 m(n) m(n)  j=1  X(ω) n,j −Xn(ω)εan2 exp −εhnan+h2 nBn(ω) 2(1 −hnMn(ω)). 4. Complete convergence rates for the dependent bootstrap of the mean. With the preliminaries accounted for, the law of large numbers for the dependent bootstrap of the mean may now be established. The theorem is an analogue of Theorem 2.1 of [9] for the case of the dependent bootstrap. Theorem. Let {Xn,n1}be a sequence of (not necessarily independent or identically distributed)random variables and let {an,n1}be a sequence of positive real numbers. If (i) log n m(n)an max 1in|Xi|−→0a.s. and (ii) log n nm(n)a2 n n  i=1 X2 i−→ 0a.s., then for any real r,every ε>0, and almost every ω∈Ω ∞  n=1 nrP 1 m(n) m(n)  j=1  X(ω) n,j −Xn(ω)εan<∞. We make several remarks concerning the theorem before proving it. Remarks. 1. The conclusion of the theorem is of course stronger the larger ris taken. In contrast with the Baum–Katz, Erd¨os, Hsu–Robbins, Spitzer complete convergence theorem, the constant rdoes not play a role in any condition of the theorem and it can be taken arbitrarily large. 2. Taking r= 0, it follows from the Borel–Cantelli lemma and the conclusion of the theorem that for almost every ω∈Ω 1 an1 m(n) m(n)  j=1  X(ω) n,j −Xn(ω)−→ 0 a.s. 3. According to Lemma 5, if (log n)/(m(n)an)↓0 monotonically, then assumption (i) from the theorem is equivalent to the apparently weaker and strictly simpler condition log n m(n)an Xn→0 a.s. 4. Careful analysis of the proof of the theorem shows that assumptions (i) and (ii) can be slightly weakened: (i)log n m(n)an max 1in|Xi−Xn|−→0 a.s., (ii)log n nm(n)a2 n n  i=1 (Xi−Xn)2−→ 0 a.s. Ignoring the fact that assumptions (i) and (ii) are obviously weaker than assumptions (i) and (ii), it is worth mentioning that they are cumbersome and more difficult to check. Proof of the theorem. The conclusion of the theorem obviously holds for r<−1, so it will be assumed that r−1. Using the notation of Lemma 7 denote Ω0=ω:log n an Mn(ω)−→ 0 and log n a2 n Bn(ω)→0. It is easy to check that conditions (i) and (ii) imply P(Ω0)=1. CONVERGENCE RATE OF THE DEPENDENT BOOTSTRAPPED MEANS 345 For fixed r−1, ε>0, and ω∈Ω0, let hn=3+r εan log n, n 1. Since ω∈Ω0,we have hnMn(ω)=3+r ε log n an Mn(ω)−→ 0 and h2 n log nBn(ω)=3+r ε2log n a2 n Bn(ω)−→ 0. Let nbe sufficiently large such that h2 nBn(ω)log nand hnMn(ω)1 2. Applying Lemma 7 we obtain nrPm(n) j=1  X(ω) n,j m(n)−Xn(ω)εn2nrexp −εhnan+h2 nBn(ω) 2(1 −hnMn(ω)) 2nrexp −(3+r) log n+ log n=2nrexp −(2+r) log n2n−2 since r−1, and the conclusion follows. Corollary. Let {Xn,n1}be a sequence of identically distributed (not necessarily independent)random variables and 0<α<2.IfE|X1|α|log |X1||α<∞,then for every real r,every ε>0, and almost every ω∈Ω ∞  n=1 nrP 1 n1/α n  j=1  X(ω) n,j −Xn(ω)ε<∞. Proof. Consider m(n)=nand an=n(1−α)/α,n1,in the theorem. We need to check that assumptions (i) and (ii) are true. For (i) we denote bn=n1/α/log nand ψ(t)=tα(log t)α,t1. According to Lemma 2, ψ(bn)Cn, where the constant Cdoes not depend on n. Assumption (i) follows from Lemma 6. Assumption (ii) follows from Lemma 4 directly. We should mention that Lemma 4 requires an even slightly weaker moment assumption than we have. REFERENCES [1] E. Arenal-Guti´ errez, C. Matr´ an, and J. A. Cuesta-Albertos,On the unconditional strong law of large numbers for the bootstrap mean, Statist. Probab. Lett., 27 (1996), pp. 49–60. [2] K. B. Athreya,Strong law for the bootstrap, Statist. Probab. Lett., 1 (1983), pp. 147–150. [3] G. R. Barnes and H. G. Tucker,On almost sure convergence of normed maxima of independent random variables, J. London Math. Soc. (2), 16 (1977), pp. 377–383. [4] P. J. Bickel and D. A. Freedman,Some asymptotic theory for the bootstrap, Ann. Statist., 9 (1981), pp. 1196–1217. [5] A. Bozorgnia, R. F. Patterson, and R. L. Taylor,Limit theorems for dependent random variables, in Proceedings of the First World Congress of Nonlinear Analysis (Tampa, 1992), V. Ladshmikantham, ed., de Gruyter, Berlin, 1996, pp. 1639–1650. [6] S. Cs¨ org˝ o,On the law of large numbers for the bootstrap mean, Statist. Probab. Lett., 14 (1992), pp. 1–7. [7] B. Efron,Bootstrap methods:Another look at the jackknife, Ann Statist., 7 (1979), pp. 1–26. [8] E. L. Lehmann,Some concepts of dependence, Ann. Math. Statist., 37 (1966), pp. 1137–1153. [9] D. Li, A. Rosalsky, and S. E. Ahmed,Complete convergence of bootstrapped means and moments of the supremum of normed bootstrapped sums, Stochastic Anal. Appl., 17 (1999), pp. 799–814. [10] T. Mikosch,Almost sure convergence of bootstrapped means and U-statistics, J. Statist. Plann. Inference, 41 (1994), pp. 1–19.