Optimal inequalities in probability theory A conve

SIAMJ.OPTIM.c2005SocietyforIndustrialandAppliedMathematicsVol.15,No.3,pp.780–804OPTIMALINEQUALITIESINPROBABILITYTHEORY:ACONVEXOPTIMIZATIONAPPROACH∗DIMITRISBERTSIMAS†ANDIOANAPOPESCU‡Abstract.WeproposeasemidefiniteoptimizationapproachtotheproblemofderivingtightmomentinequalitiesforP(X∈S),forasetSdefinedbypolynomialinequalitiesandarandomvectorXdefinedonΩ⊆Rnthathasagivencollectionofuptokth-ordermoments.Intheunivariatecase,weprovideoptimalboundsonP(X∈S),whenthefirstkmomentsofXaregiven,asthesolutionofasemidefiniteoptimizationproblemink+1dimensions.Inthemultivariatecase,ifthesetsSandΩaregivenbypolynomialinequalities,weobtainanimprovingsequenceofboundsbysolvingsemidefiniteoptimizationproblemsofpolynomialsizeinn,forfixedk.Wecharacterizethecomplexityoftheproblemofderivingtightmomentinequalities.WeshowthatitisNP-hardtofindtightboundsfork≥4andΩ=Rnandfork≥2andΩ=Rn+,whenthedataintheproblemisrational.Fork=1andΩ=Rn+weshowthatwecanfindtightupperboundsbysolvingnconvexoptimizationproblemswhenthesetSisconvex,andweprovideapolynomialtimealgorithmwhenSandΩareunionsofconvexsets,overwhichlinearfunctionscanbeoptimizedefficiently.Forthecasek=2andΩ=Rn,wepresentanefficientalgorithmforfindingtightboundswhenSisaunionofconvexsets,overwhichconvexquadraticfunctionscanbeoptimizedefficiently.Keywords.probabilitybounds,Chebyshevinequalities,semidefiniteoptimization,convexoptimizationAMSsubjectclassifications.60E15,90C22,90C25DOI.10.1137/S10526234013999031.Introduction.Theproblemofderivingboundsontheprobabilitythatacertainrandomvariablebelongsinagivenset,giveninformationonsomeofitsmoments,hasaveryrichandinterestinghistory,whichisverymuchconnectedwiththedevelopmentofprobabilitytheoryinthetwentiethcentury.TheinequalitiesduetoMarkov,Chebyshev,andChernoffaresomeoftheclassicalandwidelyusedresultsofmodernprobabilitytheory.Naturalquestions,however,thatarisearethefollowing:1.Aresuchbounds“bestpossible”;i.e.,dothereexistdistributionsthatmatchthem?2.Cansuchboundsbegeneralizedinmultivariatesettings,andinwhatcircum-stancescantheybeexplicitlyand/oralgorithmicallycomputed?3.Isthereageneraltheorybasedonoptimizationmethodstoaddressinaunifiedmannermoment-inequalityproblemsinprobabilitytheory?Inthispaper,weformulatetheproblemofobtainingbestpossibleboundsasanoptimizationproblemandusemodernoptimizationtheory,inparticularconvexandsemidefiniteprogramming,togiveconcreteanswerstothequestionsabove.Wefirstintroducesomenotation.Letκ=(k1,...,kn)withkj∈Z+nonnegativeintegers.Weusethenotationσκ=σk1,...,knandJk={κ=(k1,...,kn)|k1+···+kn≤k,kj∈Z+,j=1,...,n}.Wenextintroducethenotionofafeasiblemomentsequence.∗ReceivedbytheeditorsDecember18,2001;acceptedforpublication(inrevisedform)June29,2004;publishedelectronicallyApril8,2005.†SloanSchoolofManagement,Rm.E53-363,MassachusettsInstituteofTechnology,Cambridge,MA02139([e-mail]).TheresearchofthisauthorwaspartiallysupportedbyNSFgrantDMI-9610486andtheMIT-SingaporeAlliance.‡INSEAD,FontainebleauCedex77305,France([e-mail]).780OPTIMALPROBABILITYBOUNDS781Definition1.1.Asequenceσ=(σκ,κ∈Jk)isafeasible(n,k,Ω)-momentvector(orsequence),ifthereisarandomvectorX=(X1,...,Xn)definedonΩ⊆RnendowedwithitsBorelsigmaalgebraofevents,whosemomentsaregivenbyσ,thatis,σκ=σk1,...,kn=EXk11···Xknnforallκ∈Jk.WesaythatanysuchrandomvariableXhasaσ-feasibledistributionanddenotethisasX∼σ.Throughoutthepaper,theunderlyingprobabilityspaceisimplicitlyassumedtobeΩ⊆RnendowedwithitsBorelsigmaalgebraofevents.WedenotebyM=M(n,k,Ω)thesetoffeasible(n,k,Ω)-momentvectors.Fortheunivariatecase(n=1),theproblemofdecidingifσ=(M1,M2,...,Mk)isafeasible(1,k,Ω)-momentvectoristheclassicalmomentproblem.ThisproblemhasbeencompletelycharacterizedbynecessaryandsufficientconditionsbyStieltjes[43],[44]in1894-95,whoadoptsthe“moment”terminologyfrommechanics(seealsoKarlinandShapley[18],Akhiezer[1],Siu,Sengupta,andLind[38],andKemperman[21]).Forunivariate,nonnegativerandomvariables(Ω=R+),theseconditionscanbewrittenasRk0andRk−10,whereforanyintegerl≥0wedefineR2l=⎛⎜⎜⎜⎝1M1...MlM1M2...Ml+1............MlMl+1...M2l⎞⎟⎟⎟⎠,R2l+1=⎛⎜⎜⎜⎝M1M2...Ml+1M2M3...Ml+2............Ml+1Ml+2...M2l+1⎞⎟⎟⎟⎠.ForunivariaterandomvariableswithΩ=R,thenecessaryandsufficientcondi-tion(givenbyHamburger[12],[13]in1920-21)foravectorσ=(M1,M2,...,Mk)tobeafeasible(1,k,R)-momentsequenceisthatR2k20.Inthemultivariatecase,theformulationoftheproblemcanbetracedbacktoHaviland[14],[15]in1935-36(seealsoGodwin[10]).Todate,thesufficiencypartofthemomentproblemhasnotbeencompletelyresolvedinthemultivariatecase,althoughsubstantialprogresshasbeenmadeinthelastdecadebySchmudgen[37]andPutinar[34].SupposethatσisafeasiblemomentsequenceandXhasaσ-feasibledistribution.Wenowdefinethecentralproblemthatthispaperaddresses.The(n,k,Ω)-boundproblem.Givenasequenceσκ,κ=(k1,k2,...,kn)∈Jkofuptokth-ordermomentsσκ=EXk11Xk22···Xknn,κ∈JkofarandomvectorX=(X1,X2,...,Xn)onΩ⊆RnendowedwithitsBorelsigmaalgebra,findthe“bestpossible”or“tight”upperandlowerboundsonP(X∈S),formeasurableeventsS⊆Ω.Theterm“bestpossible”or“tight”upper(andbyanal