一个与排列组合有关的概率问题

Question

开始时令点M位于一维坐标系的0点，每一步向左或向右移动1，向左或向右的概率均为0.5。当M位于-1时停止，并记总移动步数为m。
用含n的代数式表示P(m=n) （n为正奇数）

Answer 1

设n=2k+1，则P(m=n) = C(2k,k) * (1/2)^(2k+1) * 1/(k+1)，其中C(n,m)代表n个数里取m个的不同组合个数。

求出C(2k,k) * (1/2)^(2k+1)是错误的，因为这个求解只是套了个二项式公式，而没有考虑到M直到最后一步前，向来位于x轴右侧这个重要的限制条件。

这是概率论里的一个著名问题，叫做Bertrand票选问题（英文专业名词为Bertrand's Ballot Theorem），大意是说：两个候选人A和B，最终分别获得p张和q张选票（设p>=q），则在唱票过程中A票数一直不落后于B的概率会是多少。网上有些资料可以参考，尤其是英文相关资料很多。

楼主的问题相当于Bertrand票选问题。就是说：在随机游走的过程中，是向右走的步数一直不小于向左走的步数，直到最后一步金身告破。

在2k步时位于原点的走法是C(2k,k)，而我们要求的一直>=0的走法数目。大致的思路是翻折，如上图所示，如果之前已经金身不保，把后面的走法统统对调，向左走变向右走，向右走变向左走。。。则走法为C(2k,k-1)种，则金身不破的走法有C(2k,k)-C(2k,k-1)=C(2k,k)*(1-k/(k+1))=C(2k,k)*(1/(k+1))种。

Answer 2

M从O出发，移动N步，到达-1点；移动步数N=n，n必为奇数，设n=2k-1，k为正整数，向右总移动步数为k-1，向左总移动步数为k；P｛N=n｝=[(1/2)^(k-1)][(1/2)^k]，所以P｛N=n｝=1/2^n。

Answer 3

C_(n-1)^((n-1)/2)*（1/2)^(n+1)