C/C++中伯努力投票定理的应用

在伯努力的原始论文中，他解释了一个依赖于实现递归关系的有利序列数量的通用公式的证明。

示例

假设有5位投票者，其中3位投票给候选人A，2位投票给候选人B（因此p = 3，q = 2）。投票顺序共有十种可能性：

对于AABAB这个顺序，选举过程中投票的统计如下：

候选人	A	A	B	A	B
A	1	2	2	3	3
B	0	0	1	1	2

在每一列中，A的票数始终大于B的票数，因此A始终严格领先于B。对于AABBA这个顺序，选举过程中投票的统计如下：

候选人	A	A	B	B	A
A	1	2	2	2	3
B	0	0	1	2	2

关于这个顺序，在第四票后B与A持平，因此A并不总是严格领先于B。在10种可能的顺序中，只有AAABB和AABAB的情况下A始终领先于B。因此，A始终严格领先的概率为2/10=1/5，这确实等于定理预测的(3-2)/(3+2)。

Arnab Chakraborty

更新于：2020年1月29日

浏览量：139

通过完成课程获得认证