A sample of samplers - a computational perspective

ASampleofSamplers:AComputationalPerspectiveonSamplingOdedGoldreichDepartmentofComputerScienceandAppliedMathematicsWeizmannInstituteofScience,Rehovot,Israel.Email:[e-mail]26,1997AbstractWeconsidertheproblemofestimatingtheaverageofahugesetofvalues.Thatis,givenoracleaccesstoanarbitraryfunctionf:f0;1gn7![0;1],weneedtoestimate2nPx2f0;1gnf(x)uptoanadditiveerrorof.Weareallowedtoemployarandomizedalgorithmwhichmayerrwithprobabilityatmost.Wesurveyknownalgorithmsforthisproblemandfocusontheideasunderlyingtheircon-struction.Inparticular,wepresentanalgorithmwhichmakesO(2log(1=))queriesandusesn+O(log(1=))+O(log(1=))cointosses,bothcomplexitiesbeingveryclosetothecorrespondinglowerbounds.Keywords:Sampling,randomnesscomplexity,savingrandomness,pairwiseindependentrandomvariables,Expandergraphs,randomwalksongraphs,lowerbounds.01IntroductionInmanysettingsrepeatedsamplingisusedtoestimatetheaveragevalueofahugesetofvalues.Namely,thereisavaluefunctiondenedoverahugespace,say:f0;1gn7![0;1],andonewishestoapproximatedef=12nPx2f0;1gn(x)withouthavingtoinspectthevalueofontheentiredomain.Wecommentthatitisessentialtohavetherangeofbebounded(orelsenoreasonableapproximationmaybepossible).Ourconventionofhaving[0;1]betherangeofisadoptedforsimplicity,andtheproblemforother(predetermined)rangescanbetreatedanalogously.1.1FormalSettingOurnotionofapproximationdependsontwoparameters:accuracy(denoted)anderrorprobability(denoted).Wewishtohaveanalgorithmwhichwithprobabilityatleast1,getswithinofthecorrectvalue.Thisleadstothefollowingdenition.Denition1.1(sampler):Asamplerisarandomizedalgorithmthatoninputparametersn(length),(accuracy)and(error),andoracleaccesstoanyfunction:f0;1gn7![0;1],outputs,withprob-abilityatleast1,avaluethatisatmostawayfromdef=12nPx2f0;1gn(x).Namely,Pr(jsampler(n;;)j)wheretheprobabilityistakenovertheinternalcointossesofthesampler.Weareinterestedin\thecomplexityofsamplingquantiedasafunctionoftheparametersn,and.Specically,wewillconsiderthreecomplexitymeasures1.SampleComplexity:thenumberoforaclequeriesmadebythesampler.2.RandomnessComplexity:thenumberof(unbiased)cointossesperformedbythesampler.3.ComputationalComplexity:therunning-timeofthesampler.Wesaythatasampleisecientifitsrunning-timeispolynomialinthetotallengthofitsqueries(i.e.,polynomialinbothitssamplecomplexityandinn).Wewillfocusonecientsamplers.Furthermore,wewillfocusonecientsamplerswhichhaveoptimal(uptoaconstantfactor)samplecomplexity,andwillbeinterestedinhavingtherandomnesscomplexitybeaslowaspossible.1.2OverviewThestraightforwardmethod(orthenaivesampler)consistsofuniformlyandindependentlyselectingsucientlymanysamplepoints(queries),andoutputtingtheaveragevalueofthefunctiononthesepoints.UsingChernoBoundoneeasilydeterminesthatO(log(1=)2)samplepointssuce.Thenaivesamplerisoptimal(uptoaconstantfactor)initssamplecomplexity,butisquitewastefulinrandomness.InSection2,wediscussthenaivesamplerandpresentlower(andupper)boundsonthesampleandrandomnesscomplexitiesofsamplers.Thesewillguideourquestforimprovements.Pairwise-independentsamplingyieldsagreatsavingintherandomnesscomplexity.InSec-tion3wepresentthePairwise-IndependentSampler,anddiscussitsadvantagesanddisadvantages.Specically,forconstant0,thePairwise-IndependentSamplerisoptimaluptoaconstantfactor1inbothitssampleandrandomnesscomplexities.However,forsmall(i.e.,=o(1)),itssamplecomplexityiswasteful.Anewideaisrequiredforgoingfurther,andarelevanttool{randomwalksonexpandergraphs(seeAppendixA){isneededtoo.InSection4,wecombinethePairwise-IndependentSamplerwiththeExpanderRandomWalkTechniquetoobtainanewsampler.Looselyspeaking,thenewsamplerusesarandomwalkonanexpandertogenerateasequenceof‘def=O(log(1=))(related)randompadsfor‘invocationsofthePairwise-IndependentSampler.Eachoftheseinvocationsreturnsan-closeapproximationwithprobabilityatleast0:9.Theexpanderwalktechniqueyieldsthat,withprobabilityatleast1exp(‘)=1,mostofthese‘invocationsreturnan-closeapproximation.Thus,themedianvalueisan(;)-approximationtothecorrectvalue.Theresultingsampler,calledtheMedian-of-AveragesSampler,hassamplecomplexityO(log(1=)2)andrandomnesscomplexity2n+O(log(1=)).InSection5,wepresentanalternativesamplerwhichimprovesoverthepairwise-independentsampler.Maintainingthesamplecomplexityofthelatter(i.e.,O(1=2)),thenewsamplerhasrandomnesscomplexityn+O(log(1=))(ratherthan2n).CombiningthisnewsamplerwiththeExpanderRandomWalkTechnique,weobtainsamplecomplexityO(log(1=)2)andrandomnesscomplexityn+O(log(1=))+O(log(1=)).Betterboundsareobtainedforthecaseof\Booleansamplers(i.e.,algorithmswhichmustonlywell-approximateBooleanfunctions).Inaddition,inSection5wepresenttwogeneraltechniquesforreningsamplers.Weconcludewithsomeopenproblems.Inparticular,wediscussthenotionof\oblivious(or\averaging)samplers.TheHittingProblemisconsideredinAppendixC.Here,givenanoracletoafunctionhavingatleastanfractionof1’s,oneisrequiredtondaninputwhichevaluatesto1.Clearly,eachsamplercanbeusedforthispurpose,butthisisanover-kill.Neve