醉鬼散步

constant · 发表于 2006-4-20 23:18:11

难度：++

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

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

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

sean9991 · 发表于 2006-4-21 02:10:38

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:10

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

constant · 发表于 2006-4-21 19:33: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:48

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

constant · 发表于 2006-4-22 01:30:44

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

sean9991 · 发表于 2006-4-24 17:53:38

that is true.

		自动登录	找回密码
密码			立即注册

动态微博

醉鬼散步

回复：醉鬼散步

回复：回复：醉鬼散步

回复：回复：醉鬼散步

回复：回复：回复：醉鬼散步

回复：回复：回复：回复：醉鬼散步

回复：回复：回复：回复：回复：醉鬼散步