一道趣味概率题

一个盲人骑马站在悬崖边，如果他向前一步就掉落深渊，已知马向前一步的概率为$\frac{1}{2}$，向后一步的概率为$\frac{1}{2}$，马在悬崖上徘徊，求盲人最后掉落深渊的概率。

必死无颖？

2# kuing

0101010101……

倒也不是必死无疑的

很著名的问题，嗯，相关的
http://bbs.pep.com.cn/viewthread ... d=976841#pid6873706

不过问题编成这样也太生硬了，马向后走和向前走概率一样，这是什么马啊，而且马又不是瞎子，看见悬崖还会往前走……

在一个QQ群里面看到的一个问题
有人给出了答案为1
而且给出了一个简单的解释，
用楼上给出的公式求解，需要求一个数列和的极限，昨天就试过了，没算出来…

想知道这个答案是不是就等于1
你们怎么做的？

3# ①②③④⑤⑥⑦

唔，有空慢慢研究。。。
嘿，那个题设的确是搞笑的……

http://oeis.org/A001405

看好久才把链接的文章看完了
没看出那个链接对这道题有什么帮助
谢谢楼上的

一个重要结论就是，如果悬崖在马身后，设马走了 m 步向后，n步向前，也即共走了 n+m 步，则不会落下悬崖的走法共有 \[\left( {\begin{array}{*{20}{c}}
  {m + n} \\
  m
\end{array}} \right) - \left( {\begin{array}{*{20}{c}}
  {m + n} \\
  {m - 1}
\end{array}} \right)\]

一个重要结论就是，设马走了 m 步向后，n步向前，也即共走了 n+m 步，则不会落下悬崖的走法共有 \[\left( {\begin{array}{*{20}{c}}
  {m + n} \\
  m
\end{array}} \right) - \left( {\begin{array}{*{20}{c}} ...
icesheep 发表于 2011-11-17 02:45

只在 m=n 时成立，就是 Catalan 数

前面给出的那个序列，与Dyck paths有关,  去搜索一下就知道是同一个问题，这个序列则是相应的扩展，不要求必须回来，其实相当于楼主的走n步没死

Number of left factors of Dyck paths, consisting of n steps. Example: a(4)=6 because we have UDUD, UDUU, UUDD, UUDU, UUUD and UUUU, where U=(1,1) and D=(1,-1).

9# ①②③④⑤⑥⑦


m不等于n也成立的，你看你的例子中，UUUD，向前走了三步，向后只走了一步，即 n=3,m=1

对应的走法数为 C(4,1)-C(4,0)=3

也即你列出的 UUUD,UUDU,UDUU 这三种

9# ①②③④⑤⑥⑦


m不等于n也成立的。
icesheep 发表于 2011-11-17 12:55

$m=2, n=1$

$C_{2+1}^2-C_{2+1}^{2-1}=C_3^2-C_3^1=0$

确实是零啊，说明 “向后走两步，向前走一步，不管怎么走都会掉下去”。

12# icesheep

向后走是活啊，我看反了？

13# ①②③④⑤⑥⑦


我看反了。。。原来是头面向悬崖。。。那就是 n,m 表示的意义反一下。。。

14# icesheep

嗯，这样应该是对的，最好加上 Max{...,0}

约定 C(k,-1)=0 即可。我仍然采用m为后退，n为前进的描述方法，

用上述结论分成总步数 k=n+m 为奇数和偶数的情况分开讨论，对 m 从1到 ceil(k/2) 将不会掉落悬崖的路线求和，

最后可以得出结果是 f(k)=C(k,ceil(k/2))

或者用递推的办法也可以，不过通项就要靠 ”猜测+数归“ 了。

f(1)=1
f(2k)=2f(2k-1)
f(2k+1)=2f(2k)-h(2k)

其中 h(2k)=C(2k,k)-C(2k,k-1) ，也就是 Catanlan 数

16# icesheep


“约定 C(k,-1)=0 即可。”你原来的表达式是减法，不是这个约定能直接解决的。或者你限定一下 m<=n 倒是很容易

17# ①②③④⑤⑥⑦


m>n 时一定掉下去，所以对活着的路线计数时，只需对 m 从 1 到 ceil[k/2] 求和，这个取整其实就这么来的。

我在想这个要怎么说明： \[\mathop {\lim }\limits_{k \to \infty } \frac{{f\left( k \right)}}{{{2^k}}} = 0\]

18# icesheep


你都搞定通项了，这个极限不是很easy嘛……

19# ①②③④⑤⑥⑦


我不想用斯特灵公式。。。