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:krebs@mathematik.uni-kl.de 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 (2k+1)N. Thus,fork k therearev,w L withthepropertythatd (v,w) > 2k ≥ 1 | k| ≥ 1 ∈ k ∞,ZN whichimpliesforthesetwonodesthat 2k1. 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 2C2ki (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

ε 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 ε 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 ε 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óre`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ćessairementstationnaires. 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

A Bernstein Inequality For Exponentially Growing Graphs

Similar A Bernstein Inequality For Exponentially Growing Graphs