14
Note on the regeneration-based bootstrap for atomic Markov chains Bertail, Patrice Laboratoire de Statistiques, CREST Clémençon, Stéphan MODAL’X, Université Paris X Nanterre Laboratoire de Probabilités et Modèles Aléatoires, UMR CNRS 7599 - Universités Paris VI et VII Abstract In this paper, we show how the original Bootstrap method in- troduced by Datta & McCormick (1993), namely the regeneration- based Bootstrap, for approximating the sampling distribution of sam- ple mean statistics in the atomic Markovian setting may be modi…ed, so as to be second order correct. We prove that the drawback of the original construction mainly relies on a wrong estimation of the skew- ness of the sampling distribution and that it is possible to correct it by suitable standardization of the regeneration-based bootstrap statistic and recentering of the bootstrap distribution. An asymptotic result establishing the second order accuracy of this bootstrap estimate up to O( n ¡1 log(n)) (close to the rate obtained in an i.i.d. setting) is also stated under weak moment assumptions. Résumé Dans cet article, nous montrons comment la méthode du bootstrap regénératif introduite par Datta et McCormick (1993) peut être modi- …ée pour obtenir des résultats de validité au second ordre dans le cadre de l’estimation de fonctionnelles linéaires basées sur l’observation d’une chaine de Markov stationnaire, atomique. Nous montrons que la méthode originale ne permet pas d’estimer correctement le coe¢cient d’assymétrie de la distribution mais qu’il est possible de corriger ce problème par une standardisation et un recentrage adéquats. Nous obtenons ainsi la validité au second ordre de cette forme de bootstrap avec une erreur de l’ordre O P (n ¡1 log( n)) ; proche au log ( n) près du cas i.i.d., sous des conditions de moments très faibles.

Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

Embed Size (px)

Citation preview

Page 1: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

Note on the regeneration-based bootstrap foratomic Markov chains

Bertail, PatriceLaboratoire de Statistiques, CREST

Clémençon, StéphanMODAL’X, Université Paris X Nanterre

Laboratoire de Probabilités et Modèles Aléatoires,UMR CNRS 7599 - Universités Paris VI et VII

AbstractIn this paper, we show how the original Bootstrap method in-

troduced by Datta & McCormick (1993), namely the regeneration-based Bootstrap, for approximating the sampling distribution of sam-ple mean statistics in the atomic Markovian setting may be modi…ed,so as to be second order correct. We prove that the drawback of theoriginal construction mainly relies on a wrong estimation of the skew-ness of the sampling distribution and that it is possible to correct it bysuitable standardization of the regeneration-based bootstrap statisticand recentering of the bootstrap distribution. An asymptotic resultestablishing the second order accuracy of this bootstrap estimate upto O(n¡1 log(n)) (close to the rate obtained in an i.i.d. setting) is alsostated under weak moment assumptions.

RésuméDans cet article, nous montrons comment la méthode du bootstrap

regénératif introduite par Datta et McCormick (1993) peut être modi-…ée pour obtenir des résultats de validité au second ordre dans le cadrede l’estimation de fonctionnelles linéaires basées sur l’observation d’unechaine de Markov stationnaire, atomique. Nous montrons que laméthode originale ne permet pas d’estimer correctement le coe¢cientd’assymétrie de la distribution mais qu’il est possible de corriger ceproblème par une standardisation et un recentrage adéquats. Nousobtenons ainsi la validité au second ordre de cette forme de bootstrapavec une erreur de l’ordre OP(n¡1 log(n)); proche au log(n) près ducas i.i.d., sous des conditions de moments très faibles.

Page 2: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

1 IntroductionAmong the numerous methods that have been suggested to adapt Efron’sBootstrap to weakly dependent settings, the view underlying the construc-tion proposed in Datta & McCormick (1993) (see also Athreya & Fuh (1989))for bootstrapping sample mean statistics in the atomic Markovian frameworkis one of the most interesting ones. Curiously, the beautiful ideas introducedin this paper, based on the renewal properties of Markov chains with an atom,do not seem to be widely known and used in the statistical and econometricBootstrap literature. This may be partly explained by the fact that theyonly consider the restrictive case of Markov chains possessing a known atomunder rather strong assumptions regarding to ergodicity properties. More-over, because of some inappropriate standardization, the method proposed inDatta & McCormick (1993) is not second order correct and performs poorlyin the applications. The purpose of this paper is to explain why the originalregeneration-based Bootstrap procedure fails to be second order accurate onthe one hand and to show how it is possible to correct it by some speci…cstandardization and recentering on the other hand. It is noteworthy that theregeneration-based bootstrap, modi…ed in this way, allows to get an accuracy,in the case when the chain is stationary, very close to the one obtained in thei.i.d. setting, which is not the case for other Bootstrap methods introducedto deal with the dependent case (see Götze & Künsch (1996) for instance).For the sake of simplicity, we only focus here on the case of the samplemean statistic renormalized by its true asymptotic variance. In section 2,the atomic Markovian framework we consider is set out and some notationsare given for later use. In section 3 a preliminary result is established, whichprovides an explicit expression for the asymptotic skewness coe¢cient of thesample mean statistic in our setting. Our proposal, based on this preliminaryresult, for correcting the original regeneration-based bootstrap is describedin section 4. An asymptotic result proving the second order accuracy with aremainder of order OP (n¡1 log(n)) of this bootstrap procedure is also stated.The proof is given in section 5.

2 Assumptions and notationHere and throughout, X = (Xn)n2N is a time-homogeneous positive recurrentMarkov chain valued in a countably generated state space (E; E) with tran-sition probability ¦(x; dy) and stationary probability distribution ¹(dy) (seeRevuz (1984) for an exhaustive treaty of the basic concepts of the Markovchain theory). For any probability distribution º on (E; E) (respectively, forany x 2 E), let Pº (resp., Px) denote the probability on the underlying spacesuch that X0 » º (resp., X0 = x) and let Eº(:) (resp., Ex(:)) denote the

1

Page 3: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

Pº-expectation (resp., the Px-expectation). In what follows, we will supposethat the underlying probability space is the canonical space of the Markovchain, that is by no means restrictive regarding to our results. Let us assumefurther that the chain possesses a known accessible atom A, i.e. a measur-able set A 2 E such that ¹(A) > 0 and for all x; y in A, ¦(x; :) = ¦(y; :).We will denote by PA (respectively, by EA(:)) the probability measure on theunderlying space such that X0 2 A (resp., the PA-expectation). We denotethe consecutive return times to the atom A by

¿A = ¿A(1) = inf fn > 1; Xn 2 Ag ;¿A(k + 1) = inf fn > ¿A(k); Xn 2 Ag ; for k > 1:

Throughout this paper, I(A) denote the indicator function of the event A. Inthis setting, the stationary distribution ¹ may be represented as an occupa-tion’s measure (see Theorem 17.1.7 in Meyn & Tweedie (1996) for instance):for any B 2 E,

¹(B) = EA(¿A)¡1EA(¿AX

i=1

IfXi 2 Bg):

Moreover the study of the asymptotic properties of such a Markov chainis made much easier by applying the so-called regenerative method. Thisconsists in dividing its trajectories into ”blocks” corresponding to pieces ofthe sample path between successive visits to the atom A, Bk = (X¿A(k)+1; :::;X¿A(k+1)); k > 1, and in exploiting the fact that, by virtue of the strongMarkov property, the Bk’s are i.i.d. random variables valued in the torusT = [1n=1En: In the sequel, we shall denote by l(Bk) = ¿A(k +1)¡ ¿A(k) thelength of the block Bk; k > 1: And for any measurable function f : E ! <,we will set

SA(f ) =¿AX

i=1

f (Xi);

f(Bj) =¿A(j+1)X

i=1+¿A(j)

f (Xi); for j > 1:

We point out that the atomic setting includes the whole class of Harrisrecurrent Markov chains with a countable state space (for which, any recur-rent state is an accessible atom), as well as many other speci…c Markovianmodels, widely used for modeling storage and queuing systems for instance(refer to Asmussen (1987) for an overview).

3 Preliminary resultLet f be a real valued function de…ned on the state space (E; E) and setSn(f ) =

Pni=1 f (Xi). Under the assumption that the expectationEA(SA(jfj))

2

Page 4: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

is …nite, the function f is clearly ¹-integrable (note that ¹(f ) = E¹(f(X1)) =¹(A)EA(SA(f)) by the representation of ¹ using the atom A) and with theadditional assumption that the initial probability distribution º is such thatPº(¿A < 1) = 1, the regenerative method mentioned above allows to showstraightforwardly that ¹n(f) = Sn(f )=n is a strongly consistent estimator ofthe parameter ¹(f) under Pº: Sn(f )=n ! ¹(f) Pº a.s., as n ! 1. More-over, under the further assumptions that the expectations EA(¿ 2A); Eº(¿A);EA(SA(jf j2)) and Eº(SA(jfj)) are …nite, the CLT holds too under Pº:

n1=2(Sn(f)=n¡ ¹(f )) d¡! N (0; ¾2f), as n! 1;

with a limiting variance ¾2f = ¹(A)EA(SA(f ¡ ¹(f ))2) (see Theorems 17.2.1and 17.2.2 in Meyn & Tweedie (1996) for instance).

Even if it entails to replace f by f ¡ ¹(f), we assume that ¹(f ) = 0in the remainder of this section. The following theorem gives two di¤erentforms for the asymptotic skewness of n1=2(Sn(f)=n); which determines themain term in its Edgeworth expansion (see Datta & McCormick (1993b)).

Theorem 1 If the seriesPi>1fE¹(f 2(X1)f (Xi+1)) + E¹(f(X1)f 2(Xi+1))g

andPi; j>1E¹(f (X1)f (Xi+1)f(Xi+j+1)) converge absolutely, then we have:

limn!1

n¡1E¹((Sn(f))3) = E¹(f(X1)3)

+ 31X

i=1

fE¹(f2(X1)f(Xi+1)) + E¹(f(X1)f 2(Xi+1))g

+61X

i; j=1

E¹(f(X1)f(Xi+1)f (Xi+j+1)): (1)

Moreover, if the expectations EA(¿4A) and EA (SA(jf j)4) are …nite, ¾2f > 0

and limjtj!1jEA(exp(itSA(f)))j < 1, then we have also:

limn!1

n¡1E¹((Sn(f ))3) = EA(¿A)¡1fEA(SA(f )3) ¡ 3¾2fEA(¿ASA(f ))g: (2)

3

Page 5: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

Proof. For all n> 1 we have by stationarity

n¡1E¹(Sn(f)3) = E¹(f(X1)3)

+ 3n¡1n¡1X

i=1

nX

j=i+1

E¹(f (X1)2f(Xj¡i+1)) +E¹(f (X1)f (Xj¡i+1)2)

+ 6n¡1n¡2X

i=1

n¡1X

j=i+1

nX

k=j+1

E¹(f(X1)f (Xj¡i+1)f(Xk¡j+1))

= E¹(f(X1)3)+

3n¡ 1n

nX

l=1

E¹(f(X1)2f(Xl+1)) +E¹(f (X1)f(Xl+1)2)+

6n¡ 2n

n¡1X

l=1

nX

m=1

E¹(f(X1)f(Xl+1)f(Xm+l+1))

and thus one clearly gets (1) from the convergence of the right hand side asn! 1. Besides, under the assumption that the ”block” moment conditions

EA(¿4A) < 1; EA¡SA(jfj)4

¢<1

are ful…lled; as well as the Cramer condition limjtj!1jEA(exp(itSA(f)))j < 1,(2) straightforwardly results from Theorem 3 in Malinovskii (1987) (see alsoTheorem 3 in Malinovskii (1985)). As a matter of fact, according to thisresult, for any initial probability º such that Eº(¿2A) < 1 and Eº(SA(jf j)2) <1; we have as n! 1n¡1Eº(Sn(f))3) = ®¡1fEA(SA(f )3) ¡ 3¾2f(2¯(f) ¡ ®´º(f)g +O(n¡1=2);

with ® = EA(¿A); ´º(f) = Eº(SA(f)) + ®¡1EA(P¿Ai=1(¿A ¡ i)f (Xi)) and

¯(f) = EA(¿ASA(f)): The assumptions EA(¿ 4A) < 1 and EA (SA(jfj)4) <1ensure thus that E¹(¿ 2A) < 1 and E¹(SA(jf j)2) < 1. As a matter of fact,by the representation of the stationary probability measure using the atomA (i.e. ¹(B) = ®¡1EA(

P¿Ai=1 IfXi 2 Bg), for all B 2 E , and E¹(H(X)) =R

¹(dx)Ex(H(X)) for any measurable function H de…ned on the canonicalspace), the following stronger bounds hold. We have

E¹(¿ 3A) = ®¡1EA(

¿AX

i=1

EXi(¿A)3):

Therefore, on the event fi 6 ¿Ag; we have µi ± ¿A = ¿A ¡ i; denoting by µthe shift operator on the canonical space. Hence we deduce from the Markovproperty that

E¹(¿3A) = ®¡1EA(

¿AX

i=1

E((¿A¡ i)3 j FXi ));

4

Page 6: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

where FXi denotes the ¾-…eld generated by the Xj’s; for j 6 i: Finally, wehave

E¹(¿ 3A) < ®¡1EA(

¿AX

i=1

(¿A ¡ i)3) < ®¡1EA(¿ 4A) < 1:

In a similar fashion, we have

E¹(SA(jf j)3) = ®¡1EA(¿AX

i=1

(¿AX

j=i

jf(Xi)j)3) 6 ®¡1EA(¿ASA(f )3)

6 ®¡1(EA(¿4A))1=4EA(SA(f)4)3=4 < 1

by using Hölder inequality. Moreover, we have ®´¹(f) = ¯(f). By therepresentation of the stationary distribution ¹ using the atom A again, wehave

®E¹(¿AX

i=1

f (Xi)) = EA(¿AX

i=1

EXi(¿AX

k=1

f (Xk))) = EA(X

16i<k6¿Af (Xk))

= EA(¿AX

k=1

(k ¡ 1)f (Xk)) = EA(¿AX

k=1

kf(Xk));

since we assumed ¹(f ) = ®¡1EA(P¿Ak=1 f (Xk)) = 0. This allows to deduce

straightforwardly that ®´¹ = ¯ and so to prove (2) :We point out that it is possible to take advantage of the identity (2)

for constructing an empirical estimate of the asymptotic skewness basedon the regenerative blocks (refer to Bertail & Clémençon (2003) and theproof of the main theorem below). Besides, it is noteworthy that the asymp-totic skewness, namely k3;f = ¾¡3f limn!1n¡1E¹(Sn(f )3); generally di¤ersfrom ®¡1¾¡3f EA((SA(f)3). Under the assumptions of Theorem 1, whereasPk>1ff 2(Xk) ¡ E¹(f2(Xk))g converges absolutely under P¹; we have thatP1k=1 f2(Xk) = 1 , P¹ a.s. (note that f2(Xk) is not centered under P¹).

Thus, this crucial observation shows that exchanging the expectation andthe summation in

P1i=1E¹(f(X1)f 2(Xi+1)); as done in Datta & McCormick

(1993a), is not possible. Observe further that such an illicit operation wouldallow to derive the false identity claiming that the sumE¹(f(X1)3) + 3

P1i=1fE¹(f 2(X1)f (Xi+1)) + E¹(f (X1)f2(Xi+1))g+

6P1i; j=1E¹(f(X1)f (Xi+1)f(Xi+j+1)) equals to the term®¡1EA((SA(f )3),

(or equivalently that k3;f equals to ®¡1¾¡3f EA((SA(f )3)); on which the argu-

ment of Datta & McCormick (1993a), for studying the second order prop-erties of the regeneration-based bootstrap methodology they introduced, isbased. As will be shown precisely in the next section, this particularly entailsthat the regeneration-based bootstrap estimate of the sampling distributionof the sample mean statistic ¹n(f ) = Sn(f)=n, originally proposed by Datta& McCormick (1993a) has an Edgeworth expansion, that does not match

5

Page 7: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

with the expansion of ¹n(f ) (which is due to the skewness term), and conse-quently is not second order accurate.

4 The stationary regenerative block-bootstrapThe preliminary result of section 3 clearly advocates for the following modi-…cation of the regeneration-based bootstrap procedure introduced by Datta& McCormick (1993a) to deal with atomic Markov chains, which we callthe stationary regenerative block-bootstrap (SRBB). For estimating the sam-pling distribution H¹(x) = P¹(n1=2¾¡1f (¹n(f)¡¹(f)) 6 x) of the studentizedsample mean statistic (see below the de…nition of the asymptotic varianceestimator ¾2n(f)) computed from observations X1; :::; Xn drawn from a sta-tionary version of the chain X, it is performed in four steps as follows.

1. Count the number of visits ln =Pni=1 IfXi 2 Ag to the atom A up to

time n. And divide the observed sample path X (n) = (X1; ::::;Xn) intoln + 1 blocks, valued in the torus T = [1n=1En; corresponding to thepieces of the sample path between consecutive visits to the atom A:

B0 = (X1; :::; X¿A(1)); B1 = (X¿A(1)+1; :::; X¿A(2)); :::;

Bln¡1 = (X¿A(ln¡1)+1; :::; X¿A(ln)); B(n)ln = (X¿A(ln)+1; :::; Xn):

2. Draw an array of ln ¡ 1 bootstrap data blocks (B¤1;n; :::; B¤ln¡1;n) inde-pendently from the empirical distribution Fn = (ln ¡ 1)¡1

Pln¡1i=1 ±Bi of

the blocks B1; :::; Bln¡1, conditioned on X(n): Practically the bootstrapblocks are taken with replacement from the primary blocks.

3. From the bootstrap data blocks generated at step 2, reconstruct apseudo-trajectory by binding the blocks together, getting the recon-structed SRBB sample path

X¤(n) = (B¤0;n; B¤1;n; :::;B¤ln¡1;n; B¤ln;n):with

B¤0;n = B0 and B¤ln;n = B(n)ln :

Whereas the number of blocks ln¡ 1 is …xed (conditionally to the datasample), the length of the reconstructed segment (B¤1;n; :::;B¤ln¡1;n) ofthe pseudo-trajectory is random. We denote by n¤ =

Pln¡1i=1 l(B¤1;n) the

length of this segment.

4. Compute the SRBB statistic, with the usual convention regarding toempty summation,

S¤n¤(f ) =lnX

j=0

f (B¤j;n);

6

Page 8: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

and the following estimate of ¾2f ,

¾2n(f) = (¿A(ln) ¡ ¿A)¡1ln¡1X

j=1

(f (Bj) ¡ e¹n(f)l(Bj))2;

with e¹n(f) = (¿A(ln)¡ ¿A)¡1Pln¡1j=1 f (Bj): Then, the recentered distri-

bution oft¤n = n

¤¡1=2S¤n¤ (f) ¡ Sn(f)¾n(f)

;

conditioned on X(n), is the SRBB distribution

HSRBB(x) = P ¤(t¤n ¡ E¤(t¤njX(n)) · x j X(n))

where P ¤(: j X(n)) (respectively, E¤(: j X(n))) denotes the conditionalprobability (resp., the conditional expectation) given X(n).

² We point out that the bootstrap estimator HSRBB(x) of H¹(x) di¤ersfrom the bootstrap estimator originally proposed by Datta & McCormick(1993a) in two ways. First, the standardization of the bootstrap statistic de-pends on the random length n¤ of the reconstructed bootstrap data segment,whereas the standardization n¡1=2(S¤n¤(f )¡Sn(f))=¾n(f) is used in Datta &McCormick (1993a). Secondly, the bootstrap distribution is recentered so asto be unbiased. As will be shown below, this random standardization actu-ally allows to recover the correct skewness coe¢cient k3;f at the price of anadditional bias, that may be recti…ed by recentering suitably the statistic t¤nof interest (observe that, because of the random standardization by n¤¡1=2,recentering the distribution does not amount to recenter the SRBB statisticS¤n¤(f )).

² The construction of the estimator ¾2n(f ) naturally relies on the ex-pression ¾2f = ¹(A)EA((SA(f) ¡ ¹(f)¿A)2) for the asymptotic variance, itsproperties are studied in Bertail & Clémençon (2003). Besides, we have notused the …rst and last (non regenerative) data blocks B0 and B(n)

ln in thecomputation of our estimate ¾2n(f ), because this would make its study muchmore tricky, while being all the same from the estimation point of view inthe stationary framework considered here.

² We also emphasize that one may naturally compute a Monte-Carloapproximation to HSRBB(x) by the following scheme: repeat independentlythe procedure above Q times, so as to generate t¤n;1; :::; t¤n;Q, and compute

H(Q)SRBB(x) = Q

¡1QX

q=1

Ift¤n;q ¡Q¡1QX

p=1

t¤n;p 6 xg:

The following theorem establish the second order validity of the SRBBestimator up to order OP(n¡1 log(n)); which is close to the rate OP(n¡1) thatcan be obtained in the i.i.d case.

7

Page 9: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

Theorem 2 Assume that the chain X ful…lls the following conditions.

(i) Conditional Cramer condition:

limt!1EAjEA(exp(itSA(f))j¿A)j < 1:

(ii) Non degenerate asymptotic variance: ¾2f > 0:

(iii) ”Block” moment conditions:

EA(¿ 4A) < 1; EA(SA(jfj)6) < 1:

(iv) Non trivial regeneration set: EA(¿A) > 1:

Then, the following Edgeworth expansion is valid uniformly over R;

¢n = supx2R

jH¹ (x)¡ E (2)n (x)j = O(n¡1); as n! 1; (3)

with

E(2)n (x) = ©(x) ¡ n¡1=2k3;f

6(x2 ¡ 1)Á(x);

k3;f = EA(¿A)¡1fEA(SA(f )3) ¡ 3¾2fEA(¿ASA(f ))g=¾3f :

And the SRBB estimator is second order accurate in the following sense

¢Sn = supx2R

jHSRBB(x) ¡H¹(x)j = OP¹(n¡1 log(n)) (4)

uniformly over R, as n! 1:² The proof essentially relies on the Edgeworth expansion (E.E. in abbre-

viated form) obtained in Malinovskii (1987). And dealing with the Bootstrappart mainly reduces to study the E.E. of a bootstrapped V -statistic of degree2 based on i.i.d. r.v.’s (the bootstrap blocks). The validity of E.E. for V -statistics has been proved in Götze (1979), Bickel, Götze & van Zwet (1986)for instance. The accuracy of the Bootstrap for U-statistics of degree 2 iseasy to obtain up to oP (n¡1=2): But further conditional Cramer conditionsare generally assumed to check the validity up to OP(n¡1). Here we use theresults of Lai & Wang (1993), proving the validity of the Bootstrap of U-Vstatistics up to OP(n¡1); under conditions which reduce to the conditionalCramer condition (i) in our case. The validity of the SRBB under weakerCramer conditions will be investigated elsewhere.

² When f is bounded, (iii) reduces to the condition EA(¿6A) < 1, whichtypically holds as soon as the strong mixing coe¢cients sequence decreasesat a polynomial rate n¡½ for some ½ > 5 (see Bolthausen (1982)).

8

Page 10: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

5 Proof of the main resultThe proof of the E.E. (3) for the non studentized sample mean may be foundin Malinovskii (1987) (see Theorem 1, refer also to Bertail & Clémençon(2003)). Notice that the conditional Cramer condition implies the usualCramer condition limjtj!1jEA(exp(itSA(f)))j< 1 and that the bias vanishesin the stationary case. Consider the recentered variables for j > 1;

F (Bj) = f(Bj) ¡ ¹(f )l(Bj);F (B¤j;n) = f(B¤j;n)¡ e¹n(f )l(B¤j;n):

Notice that the mean length of the bootstrap data blocks B¤j;n; j > 1; forgiven X(n) is

lB =defE¤(l(B¤j;n) j X(n)) = (ln ¡ 1)¡1

ln¡1X

k=1

l(Bk);

and observe further that E¤(F (B¤j;n) j X(n)) = 0 and

V ¤(F (B¤j;n) j X(n)) =1

ln ¡ 1

ln¡1X

k=1

F (Bk)2 = lB¾2n(f) =def b¾2F ;

denoting by V ¤(: j X(n)) the conditional variance for given X (n). Note thatthe empirical estimator ¾2n(f) of the asymptotic variance is essentially a boot-strap estimator of the variance of the recentered blocks, rescaled by an esti-mator of EA(¿A); namely lB: The following technical results will be useful inthe proof. Lemma 3 is a standard result due to Chibisov (1972).

Lemma 3 Assume that Wn admits an E.E. on the normal distribution up

to O(n¡1 log(n)±); ± > 0; as n ! 1: Assume further that Rn is such that,

for some ´ > 0; P (njRnj > ´ log(n)±) = O(n¡1 log(n)±) or O(n¡1) as n!1; then Wn + Rn has the same E.E. as Wn up to O(n¡1 log(n)±).

Lemma 4 Under the hypotheses of Theorem 2, we have for some constant

´ > 0;

P¹(n1=2¯̄nl¡1n ¡ ®

¯̄> ´(log(n))1=2) = O

¡n¡1

¢, as n! 1: (5)

Proof. Following the argument given in Clémençon (2001) based on theFuk & Nagaev’s inequality for sums of independent unbounded r.v.’s (see alsoTheorem 6.1 in Rio (2000) for a proof based on block mixing techniques),

9

Page 11: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

there exists constants c0 and c1 such that the following probability inequalityholds for all n;

P¹(¯̄ln=n¡ ®¡1

¯̄> x) 6 c0fexp(¡

nx2

c1 + xy)+

nPA(¿A > y) +PA(¿A > n=2) + P¹(¿A > n=2)g:

On the one hand, choosing y = n1=2 and bounding the last three terms atthe right hand side by Chebyshev’s inequality (given that the expectationsEA(¿2A) and E¹(¿A) are …nite), one gets that, for a constant ³ > 0 largeenough

P¹(¯̄ln=n¡ ®¡1

¯̄> ³) = O(n¡1), as n! 1; (6)

and on the other hand with the choice x = ´(logn=n)1=2 and y = (n= logn)1=2and using Chebyshev’s inequality again (given that the expectations EA(¿ 4A)and E¹(¿A) are …nite), one obtains that

P¹(n1=2¯̄ln=n¡ ®¡1

¯̄> ´(logn)1=2) = O(n¡1), as n! 1: (7)

Now, by combining bounds (6) and (7) ; the proof is …nished by straightfor-ward calculations.

Notice …rst that, because of the recentering of S¤n¤(f) by the originalstatistic Sn(f); the data of the …rst and last (non regenerative) blocks B0

and B(n)ln disappear in the numerator. Hence, we may rewrite the bootstrap

version of the studentized sample mean the following way

t¤n =Pln¡1j=1 F (B¤j;n)

(Pln¡1j=1 l(B¤j;n))1=2¾n(f)

(8)

=Pln¡1j=1 ff (B¤j;n) ¡ e¹n(f)l(B¤j;n)g(ln ¡ 1)1=2 (1 +L¤n)

1=2 b¾Fwith

L¤n = lB¡1f(ln ¡ 1)¡1

ln¡1X

j=1

l(B¤j;n) ¡ lBg

Using standard bootstrap results in the i.i.d. case (see Singh (1981) for thelattice case), we have for a constant ´ > 0 large enough,

P ¤((ln ¡ 1)L¤2n > ´ log(ln) jX (n)) = O(l¡1n ); as n! 1:

It follows from lemma (3) with ± = 1 that up to O(l¡1n log(ln)); we canlinearize (8) and the problem reduces to …nd the E.E. of

et¤n = (ln ¡ 1)¡1=2b¾¡1F

(ln¡1X

j=1

F (B¤j;n)f1¡ 12(ln ¡ 1)¡1

ln¡1X

k=1

(l(B¤k;n)¡ lB)=lB)g)

10

Page 12: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

This may be seen as a bootstrapped V -statistic of degree 2 based on thei.i.d. blocks B¤j;n, j > 1 or . The main (linear) part of the correspondingU -statistic is F (B¤j;n)=b¾¡1F ; the (degenerate) quadratic term is given by

¯n(B¤j;n;B¤k;n) =12b¾¡1F

(F (B¤j;n)

l(B¤k;n) ¡ lBlB

) + F (B¤k;n)l(B¤j;n) ¡ lB

lB

):

The validity of the Bootstrap for general U or V statistics is proved in Lai& Wang (1993), up to OP(n¡1) under assumptions on the second gradient ofthe U -statistics, which are easier to check than the usual conditional Cramerconditions or conditions on the eigenvalues of the second order gradient ofthe U -statistic (see also Bickel, Götze & van Zwet (1986)). The conditionalCramer condition used here implies their Cramer type condition (see p 521 oftheir paper, as well as related results in Bai & Rao (1991) for the validity ofE.E. under conditional Cramer type conditions). Using the arguments in Lai& Wang (1993), one may thus check that, conditionally to X(n), et¤n admitsup to O(l¡1n log(ln)) an E.E. of the form (see also Barbe & Bertail (1995) forthe form of the E.E. up to oP(n¡1=2)),

P ¤¡t¤n · x j X(n)

¢= ©(x) ¡ ©(3)(x)

6pln ¡ 1

f 1ln ¡ 1

ln¡1X

j=1

ff(Bj) ¡ e¹n(f)l(Bj)gb¾3F

3

g

¡ x©(2)(x)

2pln ¡ 1

f 1ln ¡ 1

ln¡1X

j=1

ff(Bj)¡ e¹n(f )l(Bj)g(l(Bj) ¡ lB

b¾F lB)g

+O(l¡1n log(ln)): (9)

Now from lemma 4, we obtain (unconditionally) as n! 1;

1(ln ¡ 1)1=2

=EA(¿A)1=2

n1=2+ OP¹(n¡1 log(n)1=2), (10)

and similarlyl¡1n log(ln) = OP¹(n¡1 log(n)): (11)

Now under assumption (iii); by the SLLN and the CLT for the i.i.d.blocks we have as n! 1 (see also Bertail & Clémençon (2003))

1ln ¡ 1

ln¡1X

j=1

ff(Bj) ¡ e¹n(f)l(Bj)g3b¾3F

= EA(SA(f)3)EA(¿A)3=2¾f3

+ OP¹(n¡1=2) (12)

and

1ln ¡ 1

ln¡1X

j=1

(f(Bj) ¡ e¹n(f)l(Bj))(l(Bj) ¡ lB

b¾F lB) = E¿¡3=2A ¾f¡1¯ + OP¹ (n¡1=2);

(13)

11

Page 13: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

as n ! 1, provided that the denominator is de…ned, which is the case assoon as ln > 1. Therefore we have P¹(ln · 1) = O(n¡1) as n ! 1 (seelemma 4 for instance) and combining the conditional E.E. (9) with the ap-proximations (10), (11), (12), (13), it follows that the Bootstrap distributionhas in P¹ probability an E.E. of the form

P ¤¡t¤n · x jX (n)

¢= ©(x) ¡ n¡1=2k3;f(x2 ¡ 1)Á(x)

+ n¡1=2EA(¿A)¡1¾f¡1¯=2 Á(x) +OP¹(n¡1 log(n)):

Notice the bias n¡1=2EA(¿A)¡1¾(f)¡1¯=2 which appears because of the ran-dom standardization. Recentering by the conditional expectation of t¤n givenX(n) immediately leads to the asymptotic result (4) of Theorem 2.

References[1] Asmussen, S. (1987). Applied Probability and Queues. John Wiley & Sons,

NY.

[2] Athreya, K.B., Fuh, C.D. (1989). Bootstrapping Markov chain: countablecase. Tech Rep. 89-7, Institute of Statistical Science, Academia Sinica,Taiwan.

[3] Bai, Z.D., Rao, C.R. (1991). Edgeworth expansion of a function of samplemeans. Ann. Statist., 19, 1295-1315.

[4] Barbe, Ph., Bertail, P. (1995). The Weighted Bootstrap. Lecture Notes inStatistics, 98, Springer Verlag, New-York.

[5] Bertail, P., Clémençon, S. (2003). Edgeworth expansions for suitably nor-malized sample mean statistics for atomic Markov chains. Submitted forpublication.

[6] Bickel, P.J., Götze, F. , van Zwet , W. R. (1986). The Edgeworth expan-sion for U-statistics of degree 2. Ann. Statist. , 14, 1463-1484.

[7] Bolthausen, E. (1982). The Berry-Esseen Theorem for strongly mixingHarris recurrent Markov Chains. Z. Wahrsch. Verw. Gebiete, 60, 283-289.

[8] Chibisov, D. M. (1972). An asymptotic expansion for the distribution ofa statistic admitting an asymptotic expansion. Theory Probab. Appl., 17,620-630.

[9] Clémençon, S. (2001). Moment and probability inequalities for sums ofbounded additive functionals of regular Markov chains via the Nummelinsplitting technique. Stat. Prob. Letters, 55, 227-238.

12

Page 14: Note onthe regeneration-basedbootstrapfor atomic Markov chains · Note onthe regeneration-basedbootstrapfor atomic Markov chains Bertail, ... chaine de Markov stationnaire, ... Markov

[10] Datta, S., McCormick W.P., (1993a). Regeneration-based bootstrap forMarkov chains. The Canadian Journal of Statistics, 21, No.2, 181-193.

[11] Datta, S., McCormick W.P., (1993b). On the …rst-Order EdgeworthExpansion for a Markov Chain. J. Mult. Anal. , 44, 345-359.

[12] Götze, F. (1979). Asymptotic expansions for von-Mises functionals. Zeit.Warsh. Verw. Gebiete, 50, 333-355.

[13] Götze, F., Künsch, H.R. (1996), Second order correctness of the block-wise bootstrap for stationary observations, Ann. Statist., 24, 1914-1933.

[14] Malinovskii, V. K. (1985). On some asymptotic relations and identitiesfor Harris recurrent Markov Chains. Statistics and Control of StochasticProcesses, 317-336.

[15] Malinovskii, V. K. (1987). Limit theorems for Harris Markov chains I.Theory Prob. Appl., 31, 269-285.

[16] Meyn, S.P., Tweedie, R.L., (1996). Markov chains and stochastic stabil-ity. Springer, Berlin.

[17] Lai, T. L. , Wang, J. Q. (1993). Edgeworth expansions for symetricstatistics with applications to bootstrap methods. Statistica Sinica, 3,517-542.

[18] Revuz, D (1984). Markov chains. North-Holland, 2nd edition.

[19] Rio, E. (2000). Théorie asymptotique des processus aléatoires faiblementdépendantes. Springer Verlag.

[20] Singh, K. (1981). On the asymptotic accuracy of Efron’s Bootstrap.Ann. Statist. , 9, 1187-1195.

13