资源描述：
《balls bins and randoom graphs》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、CHAPTERFIVEBalls,Bins,andRando01GraphsInthischapter,wefocusononeofthemostbasicofrandomprocesses:mballsarethrownrandomlyintonbins,eachballlandinginabinchosenindependentlyanduniformlyatrandom.Weusethetechniqueswehavedevelopedpreviouslytoanalyzethisprocessanddeve
2、lopanewapproachbasedonwhatisknownasthePoissonapproximation.Wedemonstrateseveralapplicationsofthismodel,includingamoresophisticatedanalysisofthecouponcollector'sproblemandananalysisoftheBloomfilterdatastructure.Afterintroducingacloselyrelatedmodelofrandomgraphs
3、,weshowanefficientalgorithmforfindingaHamiltoniancycleonarandomgraphwithsufficientlymanyedges.EventhoughfindingaHamiltoniancycleisNP-hardingeneral,ourresultshowsthat,forarandomlychosengraph,theproblemissolvableinpolynomialtimewithhighprobability.5.1.Example:Th
4、eBirthdayParadoxSittinginlecture,younoticethatthereare30peopleintheroom.Isitmorelikelythatsometwopeopleintheroomsharethesamebirthdayorthatnotwopeopleintheroomsharethesamebirthday?Wecanmodelthisproblembyassumingthatthebirthdayofeachpersonisarandomdayfroma365-da
5、yyear,chosenindependentlyanduniformlyatrandomforeachperson.Thisisobviouslyasimplification;forexample,weassumethataperson'sbirthdayisequallylikelytobeanydayoftheyear,weavoidtheissueofleapyears,andweignorethepossibilityoftwins�Asamodel,however,ithasthevirtueofbe
6、ingeasytounderstandandanalyze.Onewaytocalculatethisprobabilityistodirectlycounttheconfigurationswheretwopeopledonotshareabirthday.Itiseasiertothinkabouttheconfigurationswherepeopledonotshareabirthdaythanaboutconfigurationswheresometwopeopledo.Thirtydaysmustbec
7、hosenfromthe365;therearee��nwaystodothis.These30dayscanbeassignedtothepeopleinanyofthe30!possibleorders.Hencethereare(���)30!configurationswherenotwopeoplesharethesamebirthday,outofthe36530waysthebirthdayscouldoccur.Thus,theprobabilityis905.1EXAMPLE:THEBIRTHDA
8、YPARADOX(��n3o!(5.1)36530.Wecanalsocalculatethisprobabilitybyconsideringonepersonatatime.Thefirstpersonintheroomhasabirthday.Theprobabilitythatthesecondpersonhasadifferentbirthdayi
