关闭

关闭

封号提示

内容

首页 ballot theorem.pdf

ballot theorem.pdf

ballot theorem.pdf

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

简介:本文档为《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

类似资料

编辑推荐

柏杨版《白话译本资治通鉴》59 甘露事变.pdf

标准园林绿化工程施工组织设计方案范本.doc

燃气分布式能源培训材料.ppt

中国针灸学求真(焦顺发).pdf

民国史料丛刊総目提要 2010.pdf

职业精品

精彩专题

普天同庆,八天长假足够去感受我们的辉煌中国了!

近日,《辉煌中国》在央视热播,广大人民群众反响强烈。国家的飞速发展让我们感到骄傲和自豪,祖国为世界和平作出的巨大贡献让我们深感荣幸。这个国庆长假,焦点不应只放在“八天”。别忘了享受和平年代繁荣昌盛的同时,去看看《辉煌中国》,感受这部让我们热血沸腾的纪录片。

用户评论

0/200
    暂无评论
上传我的资料

精选资料

热门资料排行换一换

  • 历史主义贫困论.pdf

  • 杨铁夫:吴梦窗词笺释,陈邦炎等校…

  • 蒙古逸史·黄成垿·陈箓·商务印书…

  • 砺波护、杉山正明、岸本美绪编《中…

  • 重力式和衡重式挡土墙抗震性能研究…

  • 十二月政治局会议及其引发的党内政…

  • 031全元文(三十一).pdf

  • CJJT 190-2012 透水…

  • (光绪)永嘉县志(一).pdf

  • 资料评价:

    / 4
    所需积分:0 立即下载

    意见
    反馈

    返回
    顶部