伯特兰投票问题

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

: \frac{p-q}{p+q}

这个结果首次由威廉·亚伦·维特沃斯（W·A·Whitworth）于1878年发布，但最终以在1887年重新发现这个问题的约瑟·伯特兰的名字命名。

举例
假设有5名选民，其中3名候选人投票给A，2名候选人投票给B（即p = 3，q = 2）， 则投票顺序有以下十种可能性：

• AAABB
• AABAB
• ABAAB
• BAAAB
• AABBA
• ABABA
• BAABA
• ABBAA
• BABAA
• BBAAA

假设投票顺序为AABAB，则点票过程中点完每一票的结果为：

对于每一列（即点完每一票后）， A的票数始终大于B的票数，因此A的票数始终严格领先于B。而对于AABBA的顺序，随着选举的进行，选票总数为：

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

: \frac{2}{10}=\frac{1}{5},

这与定理得出的\frac{3-2}{3+2}结果相符。

问题的等价
计算符合要求的选票顺序出现的概率可以通过使用满足要求的选票顺序数量除以可能的顺序总数来得到（这正是伯特兰锁使用的方法）。顺序的总数由二项式系数 \tbinom{p+q}{p} 决定，伯特兰的证明显示，符合要求的选票顺序为\tbinom{p+q-1}{p-1}-\tbinom{p+q-1}{p} （尽管他没有明确给出这个数字）。 作除法后可以得到问题的答案： \tfrac{p}{p+q}-\tfrac{q}{p+q}=\tfrac{p-q}{p+q} 。

另一个等价的问题是计算 n 个整数上的随机游走数量，从坐标原点开始到 m 点终止，且不到达负数的范围。假设 n 和 m 具有相同的奇偶性，且n\ge m \ge 0，则这个结果为

: \binom{n}{\tfrac{n+m}2}-\binom{n}{\tfrac{n+m}2+1} = \frac{m+1}{\tfrac{n+m}2+1}\binom{n}{\tfrac{n+m}2}.

令 n 为投票问题中的较大数 p ，m 为两候选人票数之差 p-q，即可得到该问题的结果。当m = 0 且 n 为偶数时，可以通过卡塔兰数\frac1{\tfrac{n}2+1}\binom{n}{\tfrac{n}2} 确定结果。

使用数学归纳法证明

• 我们将条件p > q放缩至p \ge q，很明显，当p=q时这个定理是正确的，因为当所有票点完时候选人A将不再领先，此时这个问题的概率为0。
• 当p>0且q=0时这个概率为1，因为候选人A收到了全部的选票，自然一直领先。
• 假设当p=a-1且q=b \; (a>b>0)，或者当p=a且q=b-1 \; (a>b>0)时这个定理均成立，则考虑p=a, q=b的情形，最后一票投给候选人A的概率为\frac{a}{a+b}，投给候选人B的概率为\frac{b}{a+b}，所以这种情形下A一直领先B的概率为

:: {a \over (a+b)}{(a-1)-b \over (a+b-1)}+{b \over (a+b)}{a-(b-1) \over (a+b-1)}={a-b \over a+b}.

• 因此，对于所有p>q>0，这个定理均成立。

参考资料