Concentration Inequalities for Dependent Random Va

arXiv:math/0609835v1[math.PR]29Sep2006ConcentrationInequalitiesforDependentRandomVariablesviatheMartingaleMethodLeonidKontorovich∗,andKavitaRamanan†CarnegieMellonUniversityL.KontorovichSchoolofComputerScienceCarnegieMellonUniversityPittsburgh,PA15213USAe-mail:[e-mail]maticalSciencesCarnegieMellonUniversityPittsburgh,PA15213USAe-mail:[e-mail]:Weusethemartingalemethodtoestablishconcentrationinequalitiesforaclassofdependentrandomsequencesonacountablestatespace,withtheconstantsintheinequalitiesexpressedintermsofcertainmixingcoefficients.Alongtheway,weobtainboundsoncertainmartingaledifferencesassociatedwiththerandomsequences,whichmaybeofindependentinterest.Asanapplicationofourresult,wealsode-riveaconcentrationinequalityforinhomogeneousMarkovchains,andestablishanextremalpropertyassociatedwiththeirmartingalediffer-encebounds.ThisworkcomplementscertainconcentrationinequalitiesobtainedbyMartonandSamson,whilealsoprovidingadifferentproofofsomeknownresults.AMS2000subjectclassifications:Primary60E15;secondary60J10,60G42.Keywordsandphrases:concentrationinequality,McDiarmid’sbound,boundedmartingaledifferences,Markovchains,contractingMarkovchains,mixingcoefficients.∗PartiallysupportedbyDMS-0323668-0000000965,NSFITRgrantIIS-0205456†PartiallysupportedbyNSFgrantsDMS-0406191,DMI-0323668-0000000965,DMS-04053431imsartver.2006/03/07file:meas10.texdate:February2,2008KontorovichandRamanan/ConcentrationInequalitiesforDependentVariables21.Introduction1.1.BackgroundConcentrationofmeasureisafairlygeneralphenomenonwhich,roughlyspeaking,assertsthatafunctionϕ:Ω→Rwith“suitablysmall”localoscillationsdefinedona“high-dimensional”probabilityspace(Ω,F,P),al-mostalwaystakesvaluesthatare“close”totheaverage(ormedian)valueofϕonΩ.Undervariousassumptionsonthefunctionϕanddifferentchoicesofmetrics,thisphenomenonhasbeenquiteextensivelystudiedinthecasewhenPisaproductmeasureonaproductspace(Ω,F)or,equivalently,whenϕisafunctionofalargenumberofi.i.d.randomvariables(see,forexample,thesurveysofTalagrand[26,27],Ledoux[14],McDiarmid[22]andreferencestherein).Concentrationinequalitieshavefoundnumerousappli-cationsinavarietyoffields(see,forexample,[6,22,25]).Thesituationisnaturallyfarmorecomplexfornon-productmeasures,whereonecantriviallyconstructexampleswheretheconcentrationpropertyfails.Forfunctionsofdependentrandomvariables(Xi)i∈N,thecruxoftheproblemisoftentoquantifyandboundthedependenceamongthevariablesXi,oftenintermsofvarioustypesofmixingcoefficients.Asufficientlystrongdecayofthemixingcoefficientsoftenallowsonetoestablishconcentrationresults[19,20,24].Anumberoftechniqueshavebeenusedtoprovemeasureconcentration.AmongtheseareisoperimetricinequalitiesandtheinductionmethodofTa-lagrand[26,27],log-SobolevinequalitiesdevelopedbyLedouxandothers[5,13,20,24],information-theoretictechniques[1,7,10,16–18,24],mar-tingalemethodsbasedontheAzuma-Hoeffdinginequality[2,9,22]andtransportationinequalities(see,e.g.[8,23]).Theinformation-theoreticap-proachhasprovedparticularlyusefulfordealingwithnon-productmeasures.Inparticular,inaseriesofpapersMarton[16–20]successfullyusedthesetechniquestoestablishconcentrationinequalitiesforcollectionsofdepen-dentrandomvariablesundervariousassumptions.Inthisworkweadoptacompletelydifferentapproach,basedonthemartingalemethod,toestab-lishconcentrationboundsfordependentrandomvariables.Intheprocessweestablishboundsoncertainmartingaledifferences,whichmaybeofin-dependentinterest.Inthenextsubsectionweprovideaprecisedescriptionofourmainresultsanddiscusstheirrelationtopriorwork.Thesubsequentsubsectionsprovideanoutlineofthepaperandcollectsomecommonnotationthatweuse.imsartver.2006/03/07file:meas10.texdate:February2,2008KontorovichandRamanan/ConcentrationInequalitiesforDependentVariables31.2.DescriptionofMainResultsConsideracollectionofrandomvariables(Xi)1≤i≤ntakingvaluesinacount-ablespaceS.LetFbethesetofallsubsetsofSnandletP=L((X1,...,Xn))betheprobabilitydistributioninducedbythefinitesequenceX=(X1,...,Xn)on(Sn,F).Thenwecan(andwill)assumewithoutlossofgeneralitythat(Xi)arethecoordinateprojectionsdefinedontheprobabilityspace(Sn,F,P).Given1≤ij≤n,xjiisusedtodenotethesubsequence(xi,xi+1,...,xj).Similarly,for1≤ij≤n,Xjirepresentstherandomvector(Xi,...,Xj).Forfurthersimplicityofnotation,xj1andXj1willbesometimeswrittensimplyasxjandXj,respectively.LetSnbeequippedwiththeHammingmetricd:Sn×Sn→[0,∞),definedbyd(x,y).=nXi=11{xi6=yi}.Also,let¯d(x,y).=d(x,y)/ndenotethenormalizedHammingmetriconSn.Inaddition,letEdenoteexpectationwithrespecttoP.Givenafunctionϕ:Sn→R,wewillusetheshorthandnotationP{|ϕ−Eϕ|≥t}insteadofP{|ϕ(X)−E[ϕ(X)]|≥t}.Also,giventworandomvariablesYandZ,L(Z|Y=y)denotestheconditionaldistributionofXgivenY=y.Ourmainresultisaconcentrationinequalityonthemetricprobabilityspace(Sn,d,P),whichisexpressedintermsofthefollowingmixingcoeffi-cients.For1≤ij≤n,define¯ηij.=supyi−1∈Si−1,w,ˆw∈Sηij(yi−1,w,ˆw),(1.1)where,foryi−1∈Si−1andw,ˆw∈S,ηij(yi−1,w,ˆw).=LXnj|Xi=yi−1w−LXnj|Xi=yi−1ˆwTV(1.2)andkQ−RkTVdenotes(half)thevariationaldistancebetweenprobabili