Steins-method-for-concentration-inequalities

arXiv:math/0604352v2[math.PR]15Sep2006STEIN’SMETHODFORCONCENTRATIONINEQUALITIESSOURAVCHATTERJEEAbstract.WeintroduceaversionofStein’smethodforprovingcon-centrationandmomentinequalitiesinproblemswithdependence.Sim-pleillustrativeexamplesfromcombinatorics,physics,andmathematicalstatisticsareprovided.1.IntroductionandresultsStein’smethodwasintroducedbyCharlesStein[38]inthecontextofnor-malapproximationforsumsofdependentrandomvariables.Stein’sversionofhismethod,bestknownasthe“methodofexchangeablepairs”,attainedmaturityinhislaterwork[39].Areasonablylargeliteraturehasdevelopedaroundthesubject,butithasalmostexclusivelydevelopedasamethodofprovingdistributionalconvergencewitherrorbounds.Stein’sattemptsatgettinglargedeviationsin[39]didnot,unfortunately,provefruitful.SomeprogressforsumsofdependentrandomvariableswasmadebyRaiˇc[33].AgeneralversionofStein’smethodforconcentrationinequalitieswasintro-ducedforthefirsttimeinthePh.D.thesis[11]ofthepresentauthor.Thepurposeofthispaperistoexplainthetheorydevelopedin[11]viaexamples.Anotherapplicationisin[12].Thissectionisorganizedasfollows:First,wegivethreeexamples,fol-lowedbythemainabstracttheorem;finally,towardstheendofthesection,wepresentverycondensedoverviewsofStein’smethod,concentrationofmeasure,andtherelatedliterature.Proofsareinsection2.1.1.Ageneralizedmatchingproblem.Let{aij}beann×narrayofrealnumbers.Letπbechosenuniformlyatrandomfromthesetofallpermutationsof{1,...,n},andletX=Pni=1aiπ(i).ThisclassofrandomvariableswasfirststudiedbyHoeffding[24],whoprovedthattheyareap-proximatelynormallydistributedundercertainconditions.Itiseasytoseethatvariouswell-studiedfunctionsofrandompermutations,likethenum-beroffixedpoints,thesumofarandomsamplepickedwithoutreplacementfromafinitepopulation,andthefunctionPi|i−π(i)|(knownasSpearman’sfootrule[16]),areallinstancesofHoeffding’sstatistic.2000MathematicsSubjectClassification.60E15;60C05;60K35;82C22.Keywordsandphrases.Concentrationinequalities,randompermutations,Gibbsmea-sures,Stein’smethod,Curie-Weissmodel,Isingmodel.12SOURAVCHATTERJEEHoeffding’sstatistichasalonghistoryofassociationwithStein’smethod.Infact,inanunpublishedworkSteinintroducedhismethodtotreatthenormalapproximationproblemforthisobject.Bolthausen[7]usedStein’smethodtogiveaBerry-Esseenbound.BolthausenandG¨otze[8]gavemul-tivariatecentrallimittheoremsunderafurthergeneralizedsetup.However,wehavenotseenlargedeviationsorconcentrationboundsusinganymethod.OurversionofStein’smethodenablesustoeasilyderivethefollowingnicetailbound.Proposition1.1.Let{aij}1≤i,j≤nbeacollectionofnumbersfrom[0,1].LetX=Pni=1aiπ(i),whereπisdrawnfromtheuniformdistributionoverthesetofallpermutationsof{1,...,n}.ThenP{|X−E(X)|≥t}≤2exp−t24E(X)+2tforanyt≥0.Notethatthebounddoesnothaveanexplicitdependenceonn.NotealsotheautomatictransitionfromPoissoniantogaussiantailsasE(X)becomeslarge(whenE(X)issmalltheboundislikeexp(−Ct),whereaswhenE(X)islarge,itisessentiallyagaussiantailwithstandarddeviationpE(X).).Thesetwopropertiescharacterizeitasaso-called“Bernsteintypeinequality”,namedaftertheclassicalBernsteininequality(see[37],page855)forsumsofboundedindependentrandomvariables.TheclassicalresultofMaurey[30]canonlyimplytheweakerinequalityP(XE(X)+t)≤e−t2/4n.However,itispossibletoderiveaBernsteinboundsimilartoProposition1.1(albeitwithasignificantlyworseconstantintheexponent)usingMichelTalagrand’sdeeptheoremaboutconcentra-tionofrandompermutations(Theorem5.1inSection5of[40];seealsoMcDiarmid[31]andLuczak&McDiarmid[29]).Foraconcreteapplication,letXbethenumberoffixedpointsofarandompermutationπ.ThenX=Pni=1aiπ(i),whereaij=I{i=j}.SinceE(X)=1,Proposition1.1givesP{|X−1|≥t}≤2exp(−t2/(4+2t)).Ofcourse,wedonotexpectthistobethebestpossibleboundinthisverywell-understoodproblem;thisisjustmeanttobeanillustration.Infact,theexactdistributionofthethenumberoffixedpointsisknown(seeFeller[19],sectionIV.4),whichgivesatailboundlikeexp(−Ctlogt).Finally,wealsohavea“Burkholder-Davis-Gundy”typeinequalityforHoeffding’sstatisticwhichdoesnotrequireaboundontheaij’s.Proposition1.2.Let{aij}1≤i,j≤nbeanarbitrarycollectionofrealnum-bers.Letπbeauniformrandompermutation,andletX=Pni=1aiπ(i).DefineΔ=14nXi,j(aiπ(i)+ajπ(j)−aiπ(j)−ajπ(i))2.Thenforeverypositiveintegerk,wehaveE(X−E(X))2k≤(2k−1)kEΔk.STEIN’SMETHODFORCONCENTRATIONINEQUALITIES3ForageneralexpositionaboutthefamousBurkholder-Davis-Gundymar-tingaleinequalitieswerefertothearticlebyBurkholder[10].1.2.MagnetizationintheCurie-Weissmodel.Fixanyβ≥0,h∈R,andconsidertheprobabilitymassfunction(theGibbsmeasure)on{−1,1}ngivenby(1)P({σ}):=Z−1expβnXijσiσj+βhXiσi,whereσ=(σ1,...,σn)isatypicalelementof{−1,1}nandZisthenor-malizingconstant(dependsonβandh).Thisisknownasthe‘Curie-Weissmodelofferromagneticinteraction’atinversetemperatureβandexternalfieldh.Theσi’sstandforthespinsofnparticles,eachhavingaspinof+1or−1.Theferromagneticinteractionbetweentheparticlesiscapturedinaverysimplisticmannerbythefirstterminthehamiltonian.Themagnetizationofthesystem,asafunctionoftheconfigurationσ,isdefinedasm(σ):=1nPni=1σi.IfnislargeandσisdrawnfromtheGibbsmeasure,thenthemagne