伯特兰投票问题

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

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

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

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

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

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

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