珍珠湾ART

标题: 醉鬼散步 [打印本页]

作者: constant 时间: 2006-4-20 23:18
标题: 醉鬼散步

难度：++

最近WXC出了好几个醉鬼问题，咱们也出一个。

一个醉鬼在悬崖边散步。开始时背对悬崖（倒退一步就掉下去）。每一步他向前走的概率是2/3，向后是1/3。假设他不转身，也不往旁边走，他掉下悬崖的概率是多少？

更复杂一点，假设他向前走的概率是p，向后是1-p，开始时离悬崖k步，他掉下悬崖的概率是多少？

作者: sean9991 时间: 2006-4-21 02:10
标题: 回复：醉鬼散步

For general problem, let the probability be P(k).

We have the following equations:

P(0) = (1-p) * 1 + p * P(1), ...

P(k) = (1-p) * P(k-1) + p * P(k+1), ...

We can derive the following equations:

p * P(k+1) - (1-p) * P(k) = p * P(k) - (1-p) * P(k-1).

Therefore, p * P(k+1) - (1-p) P(k) = ... = p * P(0) - (1-p) * 1.

When k approaches 0, both P(k) and P(k+1) approach 0.

Hence, P(0) = (1-p) / p, P(1) = P(0)^2, ..., P(k) = P(0)^(k-1).

作者: 大头羊 时间: 2006-4-21 04:21
标题: 回复：回复：醉鬼散步

莫非这就是传说中的马尔可夫公式

作者: constant 时间: 2006-4-21 19:33
标题: 回复：回复：醉鬼散步

A tiny problem: "both P(k) and P(k+1) approach 0", this is true only if p < 1/2.

作者: sean9991 时间: 2006-4-22 00:30
标题: 回复：回复：回复：醉鬼散步

When k approaches infinity, P(k) and P(k+1) will approach 0 as long as p > 0.

作者: constant 时间: 2006-4-22 01:30
标题: 回复：回复：回复：回复：醉鬼散步

They are 1 for any k if p >=1/2. Try your own formula.

作者: sean9991 时间: 2006-4-24 17:53
标题: 回复：回复：回复：回复：回复：醉鬼散步

that is true.

欢迎光临珍珠湾ART (http://66.160.158.134/)