伯特兰投票问题

✍ dations ◷ 2025-06-30 14:37:04 #投票理论,包含证明的条目,组合计数

在组合数学中,伯特兰投票问题是指,在一场选举中候选人A得到了p张选票,而候选人得到了q张选票(p>q),那么在整个点票过程中A的票数都严格大于B的概率是多少。这个问题的答案是

这个结果首次由W. A. Whitworth于1878年发布,但最终以在1887年重新发现这个问题的约瑟·伯特兰的名字命名。

假设有5名选民,其中3名候选人投票给,2名候选人投票给(即 = 3, = 2), 则投票顺序有以下十种可能性:

假设投票顺序为 ,则点票过程中点完每一票的结果为:

对于每一列(即点完每一票后), 的票数始终大于的票数,因此的票数始终严格领先于而对于的顺序,随着选举的进行,选票总数为:

对于这个投票顺序, 在第四次投票后与并列,因此并不总是严格地领先于在10个可能的顺序中,只有和两个顺序满足总是领先于 因此,始终严格领先的概率为

这与定理得出的 3 2 3 + 2 {\displaystyle {\frac {3-2}{3+2}}} 个整数上的随机游走数量,从坐标原点开始到 点终止,且不到达负数的范围。假设 和 具有相同的奇偶性,且 n m 0 {\displaystyle n\geq m\geq 0} 为投票问题中的较大数 , 为两候选人票数之差 ,即可得到该问题的结果。当 且 为偶数时,可以通过卡塔兰数 1 n 2 + 1 ( n n 2 ) {\displaystyle {\frac {1}{{\tfrac {n}{2}}+1}}{\binom {n}{\tfrac {n}{2}}}} 确定结果。

相关

  • 鲸是海洋哺乳动物鲸下目中部分生物的通称。鲸下目又分为须鲸小目(Mystacoceti)和齿鲸小目(Odontoceti)。在日常语言中,常将鲸和海豚(以及淡水豚)分开,但在动物学中它们同属于一个系
  • 本·金斯利本·金斯利爵士,CBE(英语:Sir Ben Kingsley,CBE,1943年12月31日-),著名英国男演员,生涯首次主演电影《甘地》即以片中甘地一角,获得第55届奥斯卡金像奖最佳男主角奖、金球奖最佳戏剧类
  • 韩式茶汤饭馔朝鲜传统茶,或称韩国传统茶,是朝鲜半岛的传统茶类饮料,除了茶叶冲泡的茶之外,还有以其他材料制作的代用茶,如草本茶、果茶等。人参茶是用高丽参作的一种茶。所使用的高丽参
  • 奋武将军奋武将军是杂号将军之一 ,是高级将军名号,实际权利是各路军队中的总监军。东汉末年,各路诸侯讨伐董卓时,任命曹操担任奋武将军一职;沮授也曾在袁绍军中任奋武将军的官职。吕布也
  • 吉拉斯魏尔湖坐标:47°50′29″N 9°46′02″E / 47.8413°N 9.76723°E / 47.8413; 9.76723吉拉斯魏尔湖(德语:Girasweiher),是德国的湖泊,位于该国西南部,由巴登-符腾堡州负责管辖,处于贝加特
  • 槙阳子槙阳子(1981年7月11日-)。是日本女漫画家。绰号:小槙。血型A型,身高164公分,日本鹿儿岛出身。
  • 朝潮太郎 (3代)第三代朝潮太郎(1929年11月13日-1988年10月23日),本名米川文敏,身高1.88米,重135公斤,日本鹿儿岛县德之岛出身(出生地兵库县神户市)的大相扑力士,第46代横纲,高砂部屋所属。1948年10月,
  • 假神在亚伯拉罕诸教的信条中,假神指的是信徒们认为能力不合理或不奏效的神或崇拜物。这个词贯穿在圣经中与他们的神YHWH相对,YHWH被解释为真神、无穷无尽、无形态的并且至高无上的
  • 山度士唱片山度士唱片(Chandos Records),是总部位于英国科尔切斯特市的独立古典音乐唱片公司,1979年由Brian Couzens所创建。致力于出版推广英国古典作曲家的作品。Chandos的出版目录包
  • 可计算数 N ⊆ Z ⊆ Q ⊆ R ⊆