关闭

关闭

关闭

封号提示

内容

首页 ballot theorem.pdf

ballot theorem.pdf

ballot theorem.pdf

上传者: evenwz 2014-03-11 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《ballot theorempdf》,可适用于高等教育领域,主题内容包含BallotproblemThevotesarecountedinrandomorderTheproblemstatesthattherearenv符等。

BallotproblemThevotesarecountedinrandomorderTheproblemstatesthattherearenvotesforAandmvotesforBAparticularorderingofthevotesisthenasequenceoflengthnmconsistingofnA’sandmB’s,egAAAA︸︷︷︸nBBBB︸︷︷︸mThereare(nmn)suchsequences(EachsequencecorrespondstochoosingnoutofthenmlocationsfortheA’s)Supposeforagivenvotingsequence,youkeeparunningtallyofthedifferenceofthevotesforAandvotesforBYoucanrepresentthistallygraphicallyasfollows:drawapathwhereeachtimeavoteforAiscounted,thepathmovesup,andeachtimeavoteforBiscounted,thepathmovesdownForexample,thesequenceAABABAwouldcorrespondtothefollowingpath:AAABA#A#BVotescountedBThentocomputetheprobabilitythatAisalwaysinthelead,weneedtocountthenumberofsuchpathswhichstartat,endatnm,andnevertouchthehorizontalaxisWedothisinafewexamplesIfn=andm=,therearetwosuchpaths:AAABAABAAB#A#BVotescountedAABAThereare()=totalpathsendingat=,soP,==Ifn=andm=,thereareagaintwosuchpaths:AAABBAABAAB#A#BVotescountedAABABBThusP,=()=Thereare()=totalpathsendingat=,soP,==Ifn=andm=,therearefivesuchpaths:AABABAAABAAB#A#BVotescountedBBAABAAAAABBAAABABAAABBAAABAABThusP,=()=TheotherspecificexamplescanbefoundsimilarlyNow,supposenisarbitraryandm=ThefirsttwocountsmustbeforAAfterthat,thesinglevoteforBcanappearanywhereintheremaining(n)=nplacesThustherearengoodsequencesinwhichAalwaysleads,andPn,=n(n)=nn()Supposenisarbitraryandm=Therearetwopossibleinitialsegments:AAAorAABInthefirstcase,AAA,thetwoB’scanappearanywhereintheremainingn=nremainingspotsThereare(n)=(n)(n)suchsequencesIntheothercase,thesequencemustcontinuetoformAABA(otherwise,ifitstartsAABB,thenAisnotalwaysinthelead)ThentheremainingsingleBcanappearanywhereintheremainingn=nspotsTherearensuchsequencesThetotalnumberofsequenceswhereAalwaysleadsisthen(n)(n)(n)=(n)(n)(n)=(n)(n)WeconcludethatPn,=(n)(n)(n)=nn()Lookingatequations()and(),wemightbeledtoconjecturethatPn,m=nmnm()CheckoutthatallthecasesP,,P,,P,satisfy()Now,letusconditiononthelastvotecounted:Pn,m=P(Aalwaysleads|Alast)P(Alast)P(Balwaysleads|Blast)P(Blast)=Pn,mnnmPn,mmnm()Wenowprovetheformula()byinductionLetPropNbethepropositionthat()holdsforalln,msothatnmandnm=NStepBasecaseCheckthatPropisvalidThisistrueasP,==StepInductionstepNowassumethatPropNistrueLetn,mbesuchthatnmandnm=NThenby()andtheinductionhypothesis,Pn,m=nmnmnnmnmnmmnm=nmnmThisverifiesthatPropNisalsotrueWeconcludethatPropNistrueforallN,whichimpliesthat()isvalidforalln,m

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/4
0下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部