A Bernstein Inequality For Exponentially Growing Graphs ∗ JohannesT.N. Krebs† January17, 2017 7 1 0 2 n a J Abstract 6 1 In this article we present a Bernstein inequality for sums of random variables which are defined on a graphical ] networkwhosenodesgrowatanexponential rate. Theinequalitycanbeusedtoderiveconcentrationinequalitiesin T highly-connectednetworks.Itcanbeusefultoobtainconsistencypropertiesfornonparametricestimatorsofconditional S . expectationfunctionswhicharederivedfromsuchnetworks. h t a Keywords: Asymptotic inference; asymptotic inequalities; Bernstein inequality; Concentration inequality; Graphs; m Highly-connectedgraphicalnetworks;Mixing;Nonparametricstatistics;Randomfields;Stochasticprocesses [ MSC2010: Primary:62G20,62M40,90B15;Secondary:62G07,62G08,91D30 1 v 8 8 1 InequalitiesoftheBernsteintypeareanimportanttoolfortheasymptoticanalysisinprobabilitytheoryandstatistics. 4 TheoriginalinequalityderivedbyBernstein(1927)givesboundson (S > ε),whereS = n Z forbounded 0 P | n| n k=1 n random variables Z ,...,Z which are i.i.d. and have expectation zero. There are various versions of Bernstein’s . 1 n P 1 inequality,e.g., Hoeffding(1963). Inparticular, generalizationsto differentkindsof stochastic processeshave gained 0 importance: Carbon(1983), Collomb(1984), BrycandDembo(1996) andMerleve`deetal. (2009) provideextensions 7 1 to times series Z : t which are weakly dependent. Valenzuela-Dom´ınguezandFranke (2005) give a further t v: generalization t{o strong∈miZxi}ng random fields Zs : s N which are defined on the regular lattice N for some { ∈ Z } Z i lattice dimensionN . Thecorrespondingdefinitionsofdependenceandtheirinteractionpropertiesaregivenin X ∈ N+ Doukhan(1994)andinBradley(2005). r a Bernsteininequalitiesinparticularfindtheirapplicationswhenderivinglargedeviationresultsor(uniform)consistency statementsinnonparametricregressionanddensityestimation,compareGyo¨rfietal.(1989)andGyo¨rfietal.(2002). InthisarticlewederiveaBernsteininequalitywhichadaptstohighly-connectednetworkswherethenumberofnodes growsatan exponentialrate. A well-knownexampleforsucha graphis theinternetmapwhichtries to representthe internetwithvisualgraphics. Anotherapplicationmaybenestedsimulationswhichareusedininsurancemathematics to simulate the outcomeof an insurancecontract. We deriveanotherconcentrationinequalitybased on thisBernstein inequality.Itturnsoutthatweneedasomewhatstricterdecayintheα-mixingcoefficientsthanitisusuallyassumedin thecasefortimeseries. Thispaperisorganizedasfollows: wegivethemotivationandthedefinitionsinSection1. Section2containsthenew Bernsteininequalityandconcentrationinequalitiesforexponentiallygrowinggraphs,itisthemainpartofthisarticle. TheAppendixAcontainsausefulpropositionofDavydov(1973). ∗ThisresearchwassupportedbytheFraunhoferITWM,67663Kaiserslautern,GermanywhichispartoftheFraunhoferGesellschaftzurFo¨rderung derangewandtenForschunge.V.TheauthorthanksHannesChristiansenforproofreadingpartsofthearticle. †DepartmentofMathematics,UniversityofKaiserslautern,67653Kaiserslautern,Germany,email:[email protected] 1 1 Introduction InthissectionweconsiderageneralgraphG=(V,E)withacountablesetofnodesV andasetofedgesE. Wedefine thenaturalmetriconGastheminimalnumberofedgesbetweentwonodes d :V V , G × →N (v,w) inf l suchthatthereare(v ,v ),...,(v ,v ) E with v =v,v =w . 0 1 l−1 l 0 l 7→ ∈N ∈ (cid:8) (cid:9) Themetricd isextendedtosetsI,J V intheusualway: d (I,J) = inf d (v,w) : v I,w J . Wedenote G G G ⊆ { ∈ ∈ } byN(v) the setofneighborsofv w.r.t.Gfora nodev ofa graphG = (V,E). Furthermore,we assumethatthereis aprobabilityspace(Ω,A, )whichisendowedwithareal-valuedrandomfieldZ. Thelatterisindexedbythesetof P nodesV, i.e., Z isafamilyofrandomvariables Z : v V suchthatZ : Ω S ismeasurableforeachv V. v v { ∈ } → ∈ Wedenotetheindicatorfunctionby andwedefinetheα-mixingcoefficientoftherandomfield Z : v V onthe v 1 { ∈ } graphG=(V,E)by α (n):= sup sup (A B) (A) (B), n . G I,J⊆V, A∈F(I),|P ∩ −P P | ∈N dG(I,J)≥nB∈F(J) Therandomfieldisstrongmixingw.r.t.Gifandonlyifα (n) 0forn . Inthesequel,weinvestigaterandom G → →∞ fieldswhicharedefinedonthefollowingclassofgraphs: Definition1.1(TreesgrowingatanexponentialrateA). LetA . AtreeT =(V,E)isgrowingatanexponential + ∈N rate Aif T is a rootedtreeandeach nodev V hasexactlyA children. Thenodesin the tree arelabeledaccording ∈ tothefollowingscheme: thedistinguishedroot(whichhasnoparent)islabeledby(0,0)andthechildrenofthenode (j,k)arelabeledby(j+1,A(k 1)+1),...,(j+1,Ak). Hence,thesetofnodesandthesetofedgesaregivenby − V = (j,k):j , 1 k Aj andE = ((j,k),(j+1,k′)): (j,k) V andA(k 1)+1 k′ Ak . ∈N ≤ ≤ { ∈ − ≤ ≤ } (cid:8) (cid:9) ArootedgraphG=(V,E)isgrowingatanexponentialrateAiftheedgesEcanbedecomposedintotwodisjointsets asE = E′ E˜ suchthat(V,E′)is atree growingatan exponentialrateAandthesetE˜ of additionaledgeshasthe ∪ propertythatitdoesnotconnectnodesofarbitrarylengthinT,i.e., sup d (v,w) (v,w) E˜ < . T { | ∈ } ∞ We come to the definition of an embeddable graph. Here it is worthy to mention that especially in the context of − graphtheory therearedifferentdefinitionsofgraphembeddings:thecommondefinitionofanembeddingofagraph − G requires, loosely speaking, that the edges of the embedded graph may only intersect at their endpoints, i.e., at the nodes. Itiswellknownthatanygraphwithcountablymanynodescanbeembeddedinto 3 viaplacingthei-thnode Z atthepoint(i,i2,i3) 3,compareCohenetal.(1994). Furthermore,onecancharacterizethefinitegraphswhichare ∈Z embeddableintotheplane(theplanargraphs)withthehelpofthetheoremsofKuratowski(1930)andofWagner(1937). Here,weslightlychangethisgraphtheoreticdefinitionsuchthatitistailoredtoourneeds: wecanomittherestriction thatedgesmaynotintersectataninteriorpoint.However,sinceweshallusuallybedealingwithinfinitegraphs,wehave toaddarequirementthatisessentialwheniscomestomixingrandomfieldswhicharedefinedonthegraphwhichisto beembedded.Weneedthisdefinitiontoshowwhatisintuitivelyclear:theBernsteininequalitiesforregularlatticesare notapplicableinthecontextofgraphswhichgrowatanexponentialrate. Wegivethedefinition Definition1.2(EmbeddableGraphs). LetG=(V,E)beagraphwithcountablymanynodesV anddenotebyd the p, N Euclideanp-normontheN-dimensionallattice N,forp 1.Gisembeddablein N ifthereisadimensionNZ + Z ≥ Z ∈N suchthatGisisomorphictoagraphG′ =(V′,E′)withV′ N andforeachsequence((v ,w ) : i ) V V i i ⊆Z ∈N ⊆ × withimage((v′,w′):i ) V′ V′itistruethat i i ∈N ⊆ × sup d (v ,w ):i < = sup d (v′,w′):i < . { G i i ∈N} ∞ ⇒ { ∞,ZN i i ∈N} ∞ 2 Inthefollowing,whenspeakingofthelattice N asa graph,we shallalwaysunderstandthe graphG = (V,E)with Z nodesV = N andedgesE = (v,v+b ):v V, i=1,...,N whereb isthei-thstandardbasisvectorwhichisone i i Z { ∈ } inthei-thcoordinateandzerootherwise.Notethatinthiscase,wehaved d andd d Nd . G ≡ 1,ZN ∞,ZN ≤ 1,ZN ≤ ∞,ZN Wehaveapracticallemmawhichgivesequivalentformulationsofthisdefinition Lemma1.3. LetGbeagraph.Thenthefollowingareequivalent 1. Gisembeddablein N Z 2. GisisomorphictoagraphG′ =(V′,E′)withnodesV′ N andthereisaconstant0<C < suchthatfor ⊆Z ∞ any(v,w) V V withimage(v′,w′) V′ V′itistruethatd (v′,w′) Cd (v,w). ∈ × ∈ × ∞,ZN ≤ G 3. GisisomorphictoagraphG′ =(V′,E′)withnodesV′ N and ⊆Z sup d (v′,w′): v V,w N(v),v(resp. w)isisomorphictov′ (resp.w′) < . { ∞,ZN ∈ ∈ } ∞ Inparticular,let Z :v V bearandomfieldonG,denoteby Z :s V′ thesamerandomfieldunderthegraph v s { ∈ } { ∈ } isomorphism. Thenthemixingcoefficientssatisfyasymptoticallyα ( C ) α whichmeansthatstrongmixing mixingisinheritedwhenswitchingbetweenGandG′. ∞,ZN ⌈ ·⌉ ≤ G Proof. (1) (2)and(3):letGbeembeddablein N,thenobviouslyV iscountable,thus,thenumber ⇒ Z C :=sup d (v,w):d (v,w)=1,v,w V { ∞,ZN G ∈ } ismeaningfulandfinitebyassumption.Consequently,wehavefortwoconnectednodesvandwinV thatd (v,w) ∞,ZN ≤ Cd (v,w). Ifvandwarenotconnectedthend (v,w)= . Hence,Cistheproperconstant.Theconverseinclusions G G ∞ (2)(resp.(3)) (1)areimmediate. ⇒ We come to the amendment of the lemma. Let n be given and consider a random field on G and its graph- ∈ N isomorphiccounterpartonG′. WeinferfortwosetsI′,J′ V′ withpreimageI,J V andd (I′,J′) nthat Cd (I,J) d (I′,J′) n,i.e.,wehaveusingthegr⊆aphisomorphismforn ⊆C ∞,ZN ≥ G ≥ ∞,ZN ≥ ≥ (I′,J′): I′,J′ V′andd (I′,J′) n (I,J): I,J V andd (I,J) C−1n . { ⊆ ∞,ZN ≥ }⊆{ ⊆ G ≥ } Thus, α (n) α C−1n for n C. This means that asymptotically α α C−1 or rather ∞,ZN ≤ G ≥ ∞,ZN ≤ G · α ( C ) α . ∞,ZN ⌈ ·⌉ ≤ G (cid:0)(cid:4) (cid:5)(cid:1) (cid:0)(cid:4) (cid:5)(cid:1) Thefollowingclassofgraphscannotbeembeddedin N Z Proposition1.4(Exponentiallygrowinggraphsarenotembeddable). LetG=(V,E)beagraphwithrootv V. Put 0 ∈ L := v andrecursively 0 0 { } L := v V k−1L w L withw N(v) k ∈ \∪i=0 i |∃ ∈ k−1 ∈ (cid:8) (cid:9) fork . Ifthemap k L growsfasterthananypolynomialfunctionofdegreeN definedon ,Gisnot + k ∈ N N ∋ 7→ | | N embeddablein N. Z Proof. Letthemap k L growfasterthananypolynomialofdegreeN andassumethatGcanbeembedded k N ∋ 7→ | | into N with0 <C < whichsatisfiesd (v,w) Cd (v,w)asstatedinLemma1.3. First,observethatforv Z ∞ ∞,ZN ≤ G andwbothinL thedistanceinthegraphisatmostd (v,w) 2k. Byassumptionthereisak suchthatforall k G 1 ≤ ∈N k k wehave L > (2k+1)N. Thus,fork k therearev,w L withthepropertythatd (v,w) > 2k ≥ 1 | k| ≥ 1 ∈ k ∞,ZN whichimpliesforthesetwonodesthat 2k<d (v,w) Cd (v,w) 2Ck. ∞,ZN ≤ G ≤ 3 Hence,C >1. Inthesameway,thereisak suchthatforallk k ,wehave L >(2C2k+1)N. Inparticular, 2 2 k ∈N ≥ | | thereare(v,w) L ,k k withthepropertythatd (v,w)>2C2kwhichimpliesfork max(k ,k ) ∈ k ≥ 2 ∞,ZN ≥ 1 2 2C2k<d (v,w) Cd (v,w) 2Ck; ∞,ZN ≤ G ≤ whichinturnimpliesC <1. ThiscontradictstheassumptionthatGisembeddablein N. Z ThisimpliesthatwecannotusetheabovementionedBernsteininequalitiesfordatawhichisdefinedonalatticetoderive concentrationinequalitiesforrandomfieldsthataredefinedongraphswhichgrowatanexponentialrateA. Insteadwe giveanewBernsteininequalitywhichcandealwiththisclassofrandomfieldsinthenextsection. 2 A Bernstein inequality for exponentially growing graphs In this section we derive inequalities of the Bernstein type for random fields which are highly-connectedand whose indexsetgrowsatanexponentialrate. Weneedthefollowingimportantlemma: Lemma2.1. LetT =(V,E)beatreegrowingatanexponentialrateA. Denoteby V(j,k,P):= (j′,k′) V j j′ j+P 1, Aj′−j(k 1)+1 k′ Aj′−jk (2.1) ∈ | ≤ ≤ − − ≤ ≤ n o thesetofnodesofthesubtreeofT whichhasitsrootatthenode(j,k)andconsistsofP generations. Consider + ∈ N the graph which is induced by the set of nodes V(j,k,P). Then the number of pairs (v,w) in this graph which are separatedbyexactlyLedgesfor1 L 2(P 1)isgivenby ≤ ≤ − ⌊P−1−L/2⌋ L∧(P−1−h) N(P,L):= Ah Ai 2 1 +(A 1)AL−i−1 L>i (2.2) {L=i} · − 1{ } h=0 i=1∨(L−(P−1−h)) X X (cid:0) (cid:1) AP AL =2 − 1 +(L 1) AP AL−1 L P A 1 {L≤P−1} − − 1{ ≤ } − + 2(P 1) L+1 AP−1+⌊L(cid:0)/2⌋ AL−1∨(cid:1)P L 4 − − − · 1{ ≥ } (cid:0) (A 1)(P 1 (cid:1)(cid:16)L/2 ) 1 AP−1+⌊L/2(cid:17)⌋+AL 2 − − −⌈ ⌉ − L 4 − A 1 · 1{ ≥ } (cid:8) − (cid:9) (A 1)(P L) 1 AP +AL +2{ − − − } 4 L<P A 1 1{ ≤ } − CP AP+L/2, ≤ forasuitableconstant0<C < whichdoesnotdependonP,LandA. ∞ ProofofLemma2.1. Theminimaldistanceinthissubtreeclearlyis1,whereasthemaximaldistanceis2(P 1). Let − nowalengthLbefixed,1 L 2(P 1). Wedistinguishtwocasesforapair(v,w)whichisseparatedbyLedges: ≤ ≤ − inthefirstcasew(resp. v)isadescendantofv(resp. w). Inthesecondcasevandwhaveacommonparentwhichwe callrand,plainly,v =r =w. 6 6 The first case is onlypossible for 1 L P 1, for such an L thereare exactly 2(AP AL)/(A 1)such pairs ≤ ≤ − − − (v,w)inthissubtree.Thesecondcaseispossiblefor2 L 2(P 1).DependingonLtheparentislocatedbetween ≤ ≤ − generationzeroandgeneration P 1 L/2 ,denoteitsgenerationbyh. Havingfixedaparentringenerationhthe ⌈ − − ⌉ distancefromrtothefirstnodevisatleast1 (l (P 1 h))andatmostL (P 1 h),denotethisdistanceby ∨ − − − ∧ − − i. Hence,thereareexactlyAi nodesinquestionforv. Inthiscasethati<LthenodewisseparatedL igenerations − fromr. Sincev =wandtheirgraphdistanceisL,thisyields(A 1)AL−i−1possibilitiesforw. Allinall,wegivethe 6 − numberofpairswiththeformulafromequation(2.2). It followsthe Bernstein inequality. Here we do not considerthe full set of nodesV instead we focuson a strip of V whichisdefinedwiththehelpoftheV(j,k,P)fromthepreviousLemma2.1. 4 Theorem2.2(Bernsteininequality). LetT =(V,E)beatreegrowingatanexponentialrateA.LetZ beareal-valued v randomvariable for eachv V with [Z ] = 0, Z C andVar(Z ) σ2, for some 0 < σ,C < . Let ∈ E v k vk∞ ≤ v ≤ ∞ L ,P andconsiderthesubtreeinducedbythesetofnodes + ∈N ∈N V′ :=V(L,1,P) ... V(L,AL,P) (2.3) ∪ ∪ withV(L,i,P)asinthedefinitiongivenin(2.1). Then Z >ε 2e−βεexp 10√eα (f)(P2+Q2)/(2P2+2Q2+AL) AL v T P (cid:12)(cid:12)(cid:12)vX∈V′ (cid:12)(cid:12)(cid:12) !≤ (cid:26) P2+Q2(cid:27) (2.4) (cid:12)(cid:12) (cid:12)(cid:12) exp 4β2e(P )2 AP −1σ2+4C22(P−1)α (k)N(P,k) AL +1 ·  2  A 1 T  P +Q   − Xk=1 (cid:18) 2 2 (cid:19)   whereQ ,P suchthatQ P andP +Q <AL aswellas  2 2 + 2 2 2 2 ∈N ≤ A 1 logQ β − andf :=2 2 . ≤ 4eCP (AP 1) logA 2 − (cid:24) (cid:25) ProofofTheorem2.2. We have to partition V′ suitably. We use the abbreviations V( ) := V(L, ,P) and T := · · AL/(P +Q ) aswellas, 2 2 e (cid:6) (cid:7) A(i):=V (i 1)(P +Q )+1 ... V (i 1)Q +iP 2 2 2 2 − ∪ ∪ − B(i):=V(cid:0)(i 1)Q2+iP2+1 (cid:1) ... V (cid:0)i(P2+Q2) , (cid:1) e − ∪ ∪ e (cid:0) (cid:1) (cid:0) (cid:1) fori=1,...,T.NotethattheA(i)eandB(i)aretheunionofthedisjoeintsetsV( )andthatsomeA(i)andB(i)might · beempty.Furthermore,wedefine V′ := T A(i)andV′ := T B(i).e 1 ∪i=1 2 ∪i=1 Then,wehavewithChebychev’sinequalityandthewell-knownAM-GMinequalitythat e−βε Zv >ε e2βPv∈V1′Zv + e2βPv∈V2′Zv forβ >0. P vX∈V′ !≤ 2 nEh i Eh io Hence,itsufficestoconsiderthesum Z closer. Wewrite v∈V1′ v P S(i):= Z andJ(i):= Z fori=1,...,T. v v v∈∪Xii=1A(i) v∈XA(i) We computetheexpectationsoftherandomvariableseδS(i), forδ > 0sufficientlysmall. Notethatthedistancew.r.t. d betweenv A(i)andv′ A(i′),i=i′,isatleast2 logQ /logA . SinceS(i)=S(i 1)+J(i),weinferfrom G 2 ∈ ∈ 6 ⌈ ⌉ − Davydov’sinequalitygiveninPropositionA.1that eδS(i) =Cov(eδS(i−1),eδJ(i))+ eδS(i−1) eδJ(i) E E E h i h i h i 10α (f)1/a exp(δS(i 1)) exp(δJ(i)) + eδS(i−1) eδJ(i) (2.5) ≤ T k − kbk k∞ E E h i h i forHo¨lderconjugatea,b 1andf :=2 logQ /logA . Furthermore,wehaveif δJ(i) 1/(2e)that 2 ≥ ⌈ ⌉ | |≤ expδJ(i) 1+δJ(i)+δ2J(i)2. ≤ NowtherandomvariablesZ areessentiallyboundedbyC. Letβ (A 1)/(4eCP (AP 1))anddefineδ := 2β. v 2 ≤ − − 5 Then,wehave AP 1 1 δJ(i) δCP − , hence, [δJ(i)] exp δ2 J(i)2 . 2 | |≤ A 1 ≤ 2e E ≤ E − (cid:0) (cid:2) (cid:3)(cid:1) Note that in the subgraphinduced by the A(i) there are exactly N(P,k) pairsof nodes(v,w) with d (v,w) = k G 1,...,2(P 1) ,whereN(P,k)isgiveninLemma2.1. Forthenexttwolinesweusetheinequality( n a )2 ∈ { − } i=1 i ≤ n2 n a2forrealnumbersa ,i=1,...,n,n . Consequently,weget i=1 i i ∈N P P J(i)2 = Z2 + [Z Z ] E E v E v w (cid:2) (cid:3) v∈XA(i) (cid:2) (cid:3) v,wX∈A(i), v6=w AP 1 2(P−1) (P )2 − σ2+4C2 α (k)N(P,k) =:K ≤ 2  A 1 T   − Xk=1  withDavydov’sinequalityfromPropositionA.1.  Furthermore,we find with the Ho¨lder inequalitythat exp(δS(i 1)) exp(δS(i 1)) . Thus, equation(2.5) k − k1 ≤ k − kb canbeboundedby [exp(δS(i))] 10α (f)1/a exp(δJ(i) +exp(δ2K) exp(δS(i 1)) . (2.6) E ≤ T k k∞ k − kb n o Especially, for the case i = T successive iteration of (2.6) yieldsfor the choicea := T +1 and b = 1+1/T (as in Valenzuela-Dom´ınguezandFranke(2005)) [exp(δS(T))] exp 10√eα (f)1/(T+1)(T 1)+δ2eKT . T E ≤ { − } Next,sinceα (f) 1and1/(1+T) P2+Q2 ,wearriveat T ≤ ≥ 2(P2+Q2)+AL AL exp 2β Z exp 10√eα (f)(P2+Q2)/(2(P2+Q2)+AL) v T E  ≤ P +Q vX∈V1′ (cid:26) 2 2(cid:27)    AP 1 2(P−1) AL exp 4β2e(P )2 − σ2+4C2 α (k)N(P,k) +1 . ·  2  A 1 T  P +Q   − kX=1 (cid:18) 2 2 (cid:19)     The computations for exp 2β Z are similar and one achieves the same bounds for this term. This E v∈V2′ v finishestheproof. h (cid:16) (cid:17)i P Wearenowinpositiontoderiveaconcentrationinequality. Weconsideraninfinitetreewhichgrowsatanexponential rateAandwhichisendowedwitharandomfieldZ. WeassumethattherandomfieldZ onthetreeT isstrongmixing suchthat α (k)N(P,k) O PAP , (2.7) T ∈ k∈ XN (cid:0) (cid:1) where N(P,k) is defined in Lemma 2.1. We say that the mixingcoefficientsdecayat a super-exponential(orhyper- exponential)rateifthereisapositiveincreasingfunctiongwithlim g(n)= suchthat n→∞ ∞ α (n) exp( ng(n)). (2.8) T ≤ − In this case, equation (2.7) follows from Lemma 2.1 with the bound N(P,k) O PAP+k/2 and the following ∈ concentrationinequalityistrue (cid:0) (cid:1) Theorem 2.3 (Concentration inequality for exponentially growing trees). Let T = (V,E) be a tree growing at an 6 exponentialrateAandletZ bearandomfieldonT asinTheorem2.2. Lettherandomfieldbestrongmixingw.r.t.the graphmetricwithα-mixingcoefficientswhichfulfill(2.7),e.g.,themixingcoefficientsdecayatasuper-exponentialrate asin(2.8). ConsiderthesubgraphwhichconsistsofthefirstLgenerationsofT forL ∈N V = (j,k) V :0 j L 1, 1 k AL−1 . L ∈ ≤ ≤ − ≤ ≤ (cid:8) (cid:9) Thenthereareconstantsc ,c suchthatforallL andε>0 1 2 + ∈R ∈N 1 L Z >ε c exp c ε . v 1 2 P |VL|(cid:12)(cid:12)vX∈VL (cid:12)(cid:12) !≤ (cid:26)− logL(cid:27) (cid:12) (cid:12) (cid:12) (cid:12) Thismeanstheprobabilitydecaysasymptot(cid:12)icallyat(cid:12)aratewhichisapproximatelylinearinthesizeofthesampleVL. ProofofTheorem2.3. LetP := Lη forsomeη (0,1). WepartitionV inthefollowingway: firstwedefinethe 1 L ⌊ ⌋ ∈ wedgewhichconsistofthefirstL P generations 1 − W := (j,k) V : 0 j <L P . L L 1 { ∈ ≤ − } TheremainingP generationsarecollectedin 1 U := (j,k) V : L P j <L . L L 1 { ∈ − ≤ } The sums which correspond to these partitioning are S := Z and S := Z . Then we split the L v∈WL v L v∈UL v probabilityasfollows, P P e ε ε Z >ε V S > V + S > V (2.9) v L L L L L P (cid:12) (cid:12) | |!≤P | | 2| | P | | 2| | (cid:12)vX∈VL (cid:12) (cid:16) (cid:17) (cid:16) (cid:17) (cid:12) (cid:12) e (cid:12) (cid:12) Thefirstprobabilityin(2.9)i(cid:12)snegligib(cid:12)lebecausewefind ε AL−P1 1 εAL 1 S > V 2C − > − . L L P | | 2| | ≤ 1 A 1 2 A 1 (cid:16) (cid:17) (cid:26) − − (cid:27) e Thus,wecanfocusonthesecondprobabilityin(2.9). WeuseTheorem2.2. Wemakethefollowingdefinitions AL−P1 P :=Q := D logL , forasufficientlylargeconstantD 2 2 + L P ∈R (cid:22) − 1 (cid:23) A 1 logP β := − andf :=2 2 . 4eCP (AP1 1) logA 2 − (cid:24) (cid:25) Consider the exponentof the first factor given in (2.4): one findsthat there is a constantc which doesneither + ∈ R dependonLnoronεnorontheZ suchthat v ε L exp β V exp cε . (2.10) L −2 | | ≤ − logL n o (cid:26) (cid:27) Thesecondfactorin(2.4)isgivenby exp B√eα (f)2P2/(4P2+AL−P1)AL−P1 . (2.11) T 2P (cid:26) 2 (cid:27) Wecanderivethefollowingboundforthemixingcoefficientandtheexponentinsidetheexp-functionin(2.11) α (f)2P2/(4P2+AL−P1) exp D logL 1+ log(DlogL/(L−P1)) . T ≤ −5 (L P )logA (cid:26) (cid:18) − 1 (cid:19)(cid:27) 7 Consider the second factor inside the exp-function in (2.11), it is AL−P1/P (L P )/logL. In particular, the 2 1 ≤ − secondfactorin(2.11)isuniformlyboundedforallL ifDissufficientlylarge.Considerthethirdfactorin(2.4). + ∈N Sincethemixingcoefficientsdecaysufficientlyfast,wecanderivethefollowinginequality AP1 1 2(P1−1) AL−P1 P (L P ) exp 4eβ2(P )2 − σ2+4C2 N(P ,k)α (k) +1 exp c 1 − 1 ,  2  A 1 1 T  2P ≤ AP1logL  − Xk=1 (cid:18) 2 (cid:19) (cid:26) (cid:27)   forasuitableconstantc . Inparticular,thisexpressionisuniformlyboundedoverallL . Allinall, we have ∈ R ∈ N shownthatthereareconstantsc ,c suchthatforthesecondprobabilityin(2.9)isboundedas 1 2 + ∈R ε L S > V c c ε , L L 1 2 P | | 2| | ≤ P − logL (cid:16) (cid:17) (cid:18) (cid:19) where,theasymptoticspeedisdeterminedby(2.10). Thiscompletestheproof. Theprevioustheoremcanbeappliedtoexponentiallygrowinggraphsaswell,wehavetheusefulcorollary: Corollary2.4(Concentrationinequalityforexponentiallygrowinggraphs). LetG = (V,E′ E˜)beagraphgrowing ∪ atanexponentialrateAendowedwitharandomfieldZ asinTheorem2.3. Thenthereareconstantsc ,c such 1 2 + ∈R thatforallL andε>0 ∈N 1 L Z >ε c exp c ε . v 1 2 P |VL|(cid:12)(cid:12)vX∈VL (cid:12)(cid:12) !≤ (cid:26)− logL(cid:27) (cid:12) (cid:12) (cid:12) (cid:12) ProofofCorollary2.4. We only need to sh(cid:12)ow that(cid:12)the mixing conditions for the tree T = (V,E′) are fulfilled. The conditionthatS :=sup d (v,w) (v,w) E˜ < impliesthat T { | ∈ } ∞ d (v,w) T 1 d (v,w) d (v,w). G T ∨ S ≤ ≤ Inparticular,themixingratesw.r.t.thetreeandthewholegraphstructuresatisfyasymptoticallytheinequalityrelations α ( S ) α α . Thus,wecanconcludethestatementfromTheorem2.3. T G T ⌈ ·⌉ ≤ ≤ A Appendix PropositionA.1(Davydov(1973)). Let(Ω,A, )beaprobabilityspaceandletG,H Abesub-σ-algebras.Denote P ⊆ byα:=sup (A B) (A) (B) : A G,B G theα-mixingcoefficientbetweenGandH. Letp,q,r 1be {|P ∩ −P P | ∈ ∈ } ≥ Ho¨lderconjugate.Letξ(resp. η)beinLp( )andG-measurable(resp. inLq( )andH-measurable).Then P P Cov(ξ,η) 10α1/r ξ η | |≤ k kLp( )k kLq( ) P P References SergeBernstein. Surl’extensionduthe´ore`melimite ducalculdesprobabilite´sauxsommesdequantite´sde´pendantes. MathematischeAnnalen,97(1):1–59,1927. Richard C. Bradley. Basic properties of strong mixing conditions. a survey and some open questions. Probability surveys,2(2):107–144,2005. WłodzimierzBrycandAmirDembo. Largedeviationsandstrongmixing. InAnnalesdel’IHPProbabilite´setstatis- tiques,volume32,pages549–569,1996. 8 M. Carbon. Ine´galite´ de Bernstein pour les processus fortementme´langeantsnon ne´cessairementstationnaires. C.R. Acad.Sc.ParisI,297:303–306,1983. RobertF.Cohen,PeterEades,TaoLin,andFrankRuskey. Three-dimensionalgraphdrawing. InInternationalSympo- siumonGraphDrawing,pages1–11.Springer,1994. Ge´rardCollomb. Proprie´te´sdeconvergencepresquecomple`tedupre´dicteura`noyau. Zeitschriftfu¨rWahrscheinlichkeit- stheorieundverwandteGebiete,66(3):441–460,1984. YuriiA.Davydov.MixingconditionsforMarkovchains. TeoriyaVeroyatnosteiieePrimeneniya,18(2):321–338,1973. PaulDoukhan. Mixing,volume85ofLectureNotesinStatistics. Springer-Verlag,NewYork,1994. La´szlo´Gyo¨rfi,MichaelKohler,AdamKrz˙yzak,andHarroWalk.Adistribution-freetheoryofnonparametricregression. SpringerBerlin,NewYork,Heidelberg,2002. La´zlo´ Gyo¨rfi, Wolfgang Ha¨rdle, Pascal Sarda, and Philippe Vieu. Nonparametric curve estimation from time series, volume60. Springer,1989. WassilyHoeffding. Probabilityinequalitiesforsumsofboundedrandomvariables. JournaloftheAmericanstatistical association,58(301):13–30,1963. Casimir Kuratowski. Sur le problemedescourbesgauchesen topologie. Fundamentamathematicae,15(1):271–283, 1930. FlorenceMerleve`de,MagdaPeligrad,andEmmanuelRio. Bernsteininequalityandmoderatedeviationsunderstrong mixingconditions,volumeVolume5ofCollections,pages273–292.InstituteofMathematicalStatistics,Beachwood, Ohio,USA,2009. Eduardo Valenzuela-Dom´ınguezand Ju¨rgen Franke. A Bernstein inequality for strongly mixing spatial random pro- cesses. Technicalreport, Preprintseries of the DFG priority program1114 “Mathematicalmethodsfor time series analysisanddigitalimageprocessing”,January2005. KlausWagner. U¨bereineEigenschaftderebenenKomplexe. MathematischeAnnalen,114(1):570–590,1937. 9