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

独立评论

所跟帖: 旁观者昏 这道题有些名气。   2011-12-01 05:01:17  


作者: 鸡头肉   旁兄说得没错 2011-12-01 07:32:08  [点击:4167]
这是个标准的古典概率问题,由法国数学家 Joseph Bertrand 于 1887 年提出,组
合论书籍中常称其为 Bertrand's ballot problem。有一种解法是计算反转的概率,
但直接计算也是可行的。

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

Cm,n=(m+n)!/m!n!

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

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

Am+1,n+1 = Am+1,n + Am,n+1

为了求解递推方程,必须了解几个“边值”。当候选者 M 一张选票也没捞到时,每种
可能的投票方式都显示 N 毫无悬念地获胜,故 A0,n = C0,n = 1。另一个极端是两个
候选人的得票总数相等,m = n,此时 N 并未获胜,故 An,n = 0。

首先将 m = 0 塞入递推方程,俺们有

A1,n+1 = A1,n + A0,n+1 = A1,n + 1



A1,2 - A1,1 = 1, A1,3 - A1,2 = 1, ..., A1,n+1 - A1,n = 1

把这 n 个方程加在一起,注意到合并时方程左边之项的抵消,得

A1,n+1 - A1,1 = n

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

P1,n = A1,n/C1,n =(n-1)/(n+1)

利用数学归纳法可证 Pm,n = (n-m)/(n+m)。

Bertrand 给出了答案之后,曾征求一个“直接”的解法。Andre 给出了直接的求解,
他的方法本质上的随机游走的计算,也是初等的考虑。

加跟贴

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