[文集] [专题] [检索] [独立评论] [海阔天空] [矛盾江湖] [全版论坛]

独立评论

所跟帖: 鸡头肉 旁兄说得没错   2011-12-01 07:32:08  


作者: 云儿   try 2011-12-01 11:32:28  [点击:4230]
这是个标准的古典概率问题,由法国数学家 Joseph Bertrand 于 1887 年提出,组
合论书籍中常称其为 Bertrand's ballot problem。有一种解法是计算反转的概率,
但直接计算也是可行的。

首先注意到,当全体 m+n 个选民投完票,其中有 m 张选票投给候选人 M(因而另外
的 n 张选票投给了候选人 N)的不同投法共有



种。该数就是蝎子兄所说的组合数,描述的是把 m+n 人中的 m 个划为同一组(即M
的支持者)的所有可能的方式。在所有这些可能出现的投票记录中,假设有 Am,n
记录对应于候选人 N 毫无悬念地胜出,那么题目所求的概率即为

这个问题最初是通过递归的办法得到解决的(尽管 Bertrand 在其原始论述中省略了
若干关键的步骤)。如果俺们把选民的总数扩充成 m+n+2 个,并假定候选人 M 及 N
各多得一票,则选举结果并未改变。发生变化的是投票记录:如果新加入的两个选民
中的第一个投票给 M,那么使 N 无悬念胜出的可能的投票方式共有 Am+1,n 种;反之,
若新选民的第一个投票给 N,则 N 无悬念胜出的可能方式计为 Am,n+1。于是有递推
关系

....

由 A1,1 = 0 可知 A1,n = n - 1,故



利用数学归纳法可证

Bertrand 给出了答案之后,曾征求一个“直接”的解法。Andre 给出了直接的求解,
他的方法本质上的随机游走的计算,也是初等的考虑。
最后编辑时间: 2011-12-01 11:41:30

加跟贴

笔名:     新网友请先注册笔名 密码:
主题: 进文集
内容: