大二下学期时，在徐老师的提议下，负责创建了校内的数学系论坛。因讨论数学的人本不多，更何况是在线讨论，所以论坛的人气一直很低。后来因一些老师的宣传和参与，及一些热心同学的加入，论坛也讨论气氛有所提升，十分感谢他们的支持！现在自己能呆在学校的时间不多了，又没找到可以接班的人，同时校内新创建了一个 quot学习网 ，提议合并数学论坛，数学系论坛就此关闭。快三年了吧，兴奋、失落、感动、遗憾，还有回忆~
最近在准备面试，遇到了一些概率题，所以重新思考bbs上的一道概率题。
题目
两个人甲和乙竞选，统计结果是甲p票，乙q票（p q）。问在计票过程中甲的得票数始终大于乙的得票数的概率是多少？（由原校内数学系bbs的ZXY同学分享）
两个回帖
第一个没看明白，先记录着，第二个解答比较巧妙易懂，第三个是网友google到的
ZXY：
结果是(p-q)/(p+q)
由这道题可以引申出一个比较深刻的问题，具体我也说不清楚，反正就是这种题在历史上的意义比较的大。
我想了一种解法，不知是否重复了前人的。
显然这个概率是p,q的函数，不妨设为P(p,q),容易知道p<=q时,P(p,q)=0
易知这是古典概型，所以P(p,q)=r(p,q)/C(p+q,p)（我用C(p+q,p)表示组合数，p+q是下标）
下面考虑r(p,q).显然p<=q时r(p,q)=0.
可以证明r(p,q)=r(p-1,q)+r(p,q-1)
由此可以得出P(p,q)与P(p-1,q)和P(p,q-1)的关系。
下面对p,q使用跷跷板数学归纳法，就可以得出上述结论。
席Andy：
这个是典型的xxx折线问题啊（忘了叫啥了）。。我记得在高中老师的组合分析里面看过
那个题是卖5块钱的票2n张有n个有10块的和n个有5块的人要买 问卖的过程中不缺零钱的概率
一个坐标系，开始计票，如果甲得票，就画一条(0，0)到(1，1)的折线如果然后乙的票再画下来斜率是-1到(2，0)
以此类推。所有的情况就是从(0，0)到(p+q，p-q)的折线。所求情况是这条折线始终在y=0之上。
所求情况的补集就是折线会碰到y=0的情况。先假定第一张票就是甲的，而第一张票是甲的的概率是p/(p+q)
然后这个方法的精髓就在这里，把所有这种会碰到y=0的折线都在第一次碰到y=0之后的部分关于直线y=0对称过来，
就唯一对应于一种从(1,1)到 (p+q,q-p)的折线。
这种情况共有 C(p+q-1,p)。总情况有 C(p+q-1,p-1)
所求概率就是 p=[1-C(p+q-1,p) * C(p+q-1,p-1) ] * p / (p+q) = (p-q)/(p+q)
注：这里C(x,y)表示组合数，从x中取y的组合。
就是说首先必然到(1,1)点这个概率是 p/(p+q)
然后事件总数是从(1,1)到(p+q,p-q)
所有满足接触y=0的折线都是不满足题设情况的
将这些折线第一次接触y=0后面的部分 关于y=0对称
则终点就变成了(p+q,q-p)然后计算从(1,1)到(p+q,q-p)的走法数 需要总共走p+q-1次 向上走的-向下走的=q-p-1
得到向下走了p步 于是C(p+q-1,p)
同理总数是 C(p+q-1,p-1)
因为票都是无差别的，取票过程也是随机的，所以这个问题也就是甲得票一直领先的概率，但是一个一个列举出来确实会累出人命的。我们不妨来简化一下，假设有6个人投票，甲4票，丙2票。甲的票我们记做A，乙的票我们记做C，现在我们看其中的一种排列，AAAACC，按这个顺序出票的话，甲是一直领先的，那如果我们把这个直线顺序弯起来，做成一个环形顺时针走，1号是第一个A，那么从一号开始出票就是AAAACC，从2号开始到1号结束就是AAACCA，接下来还有AACCAA，ACCAAA，CCAAAA，CAAAAC，一共六种不同的出票顺序，这其中只有AAAACC，AAACCA两种情形，也就是从1号和2号票开始，甲才能一直保持领先。这个数据有没有通过计算得到呢，我们不妨在这个圈子中把相连的AC划掉，因为这其中第一个A不起作用，刚加上就被C又超过，对甲一直保持领先没有贡献，同样第二个C也是没意义的，因为如果在此之前甲领先，那么与他同时出现且在前面的A也抵消了C的作用，C对甲无法一直领先也没有贡献，所以同时消除不影响结果，于是这个圈子里（AAAACC）的4号和5号两张票消失了，圈子简化成AAAXXC，XX代表原来那个AC的空位，这时候3号票和6号票也相连了，于是再次消除3号，6号，于是圈子变成AAXXXX，那么从1号和2号开始的两种顺序就是甲的得票一直领先，也就是A的总数一直大于C的总数的情况，不难得知这个可能的情况总是A-C那么多。
不过很可惜，AAAACC以及衍生出的另外5种情况并不是全部的可能情况，我们还可以排出AAACAC这样一个圈子，并且可以分别从2号，3号一直到 6号票开始顺时针转，找到另外不同的五种排列情况：AACACA，ACACAA，CACAAA，ACAAAC，CAAACA，不过采用第一个圈子里的消除法，我们同样可以找到仍然是只有两种情况，也就是从1号和2号开始的两种情况能够保证A一直大于C，甲一直领先乙。这两个圈子里所有可能的情况都是6，也就是总的票数，所有甲领先的可能情形都是2种，也就是A-C的差。
当然，也许会注意到另外一种情况，就是AACAAC，这样的圈子实际上只有三种不同情况，从1号开始和从4号开始是一样的，从2号和从5号也是，3号和6号也是，这个先放一边，我们还是用消除法，变成了AXXAXX，也就是说能够保证甲一直领先的开票方式是从1号票开始，或者从4号票，但是实际上1号票和4号票的顺序是一样的，是同一种情况AACAAC，所以这个圈子里保证A C的情况只有一种，那么这个圈子里甲领先的概率就是1/3，其实跟2 /6是一样的。现在实际上我们已经枚举了所有的情况，三种圈子，6+6+3种排列方式，其中有，2+2+1种甲领先的情况，不管这个圈子变得多么的大，也不管会出现多少不同的圈子，情况都和这6个人构成的三个圈子类似，可能的概率就是(A-C)/(A+C)。