z*****n
发帖数: 165 | 1 阿米巴虫面试问题：
一个阿米巴虫，下一步有1/4的概率分别变成0（消失），1（不变），2，3，问最终消
失的概率
通常的做法：设最终消失的概率为x，则条件概率方法：x=1/4*(1+x+x^2+x^3)，得出x=
sqrt(2)-
1, -sqrt(2)-1,1，我们取sqrt(2)-1为解；但是为什么x=1不行呢？
用Generating Function的技巧重访此题：
定义Fa(s)=Sum(fa_n)s^n,n=1,2,... fa_n是从一个阿米巴虫开始，到第n个时间点消失
的概率；
定义Fb(s)=Sum(fb_n)s^n,n=1,2,... fb_n是从两个阿米巴虫开始，到第n个时间点消失
的概率；
定义Fc(s)=Sum(fc_n)s^n,n=1,2,... fc_n是从三个阿米巴虫开始，到第n个时间点消失
的概率；
不难发现：Fb=Fa^2, Fc=Fa^3 和 Fa=s/4*(1+Fa+Fb+Fc)
通过一元三次方程通解（http://en.wikipedia.org/wiki/Cubic_polynomial）得Fa的三个
解。
注意边界条件：阿米巴虫不可能在第0步消失，即Fa(s=0)=0，可排除其中两个解，对于
剩下的唯一
解，Fa(s=1)即所求概率: sqrt(2)-1 | a********e
发帖数: 508 | 2 it's an interesting point
however, I think your equation Fb=Fa^2 might not be right
x=
【在 z*****n 的大作中提到】
: 阿米巴虫面试问题：
: 一个阿米巴虫，下一步有1/4的概率分别变成0（消失），1（不变），2，3，问最终消
: 失的概率
: 通常的做法：设最终消失的概率为x，则条件概率方法：x=1/4*(1+x+x^2+x^3)，得出x=
: sqrt(2)-
: 1, -sqrt(2)-1,1，我们取sqrt(2)-1为解；但是为什么x=1不行呢？
: 用Generating Function的技巧重访此题：
: 定义Fa(s)=Sum(fa_n)s^n,n=1,2,... fa_n是从一个阿米巴虫开始，到第n个时间点消失
: 的概率；
: 定义Fb(s)=Sum(fb_n)s^n,n=1,2,... fb_n是从两个阿米巴虫开始，到第n个时间点消失
| z*****n
发帖数: 165 | 3 You are right, it's not correct.
【在 a********e 的大作中提到】
: it's an interesting point
: however, I think your equation Fb=Fa^2 might not be right
:
: x=
| a********e
发帖数: 508 | 4 I have the following approach for your point:
let P(n) be the prob that it vanishes at or before time n, then
P(n)=1/4*(1+P(n-1)+P(n-1)^2+P(n-1)^3)
lim_{n->inf} P(n)=1 or sqrt(2)-1
but if P(n-1) is around 1 for large n, P(n)
【在 z*****n 的大作中提到】
: You are right, it's not correct.
| z*****n
发帖数: 165 | 5 That's convincing, thanks!
【在 a********e 的大作中提到】
: I have the following approach for your point:
: let P(n) be the prob that it vanishes at or before time n, then
: P(n)=1/4*(1+P(n-1)+P(n-1)^2+P(n-1)^3)
: lim_{n->inf} P(n)=1 or sqrt(2)-1
: but if P(n-1) is around 1 for large n, P(n)
| s********r
发帖数: 529 | 6 I'm sorry,why P(n)
【在 a********e 的大作中提到】
: I have the following approach for your point:
: let P(n) be the prob that it vanishes at or before time n, then
: P(n)=1/4*(1+P(n-1)+P(n-1)^2+P(n-1)^3)
: lim_{n->inf} P(n)=1 or sqrt(2)-1
: but if P(n-1) is around 1 for large n, P(n)
| x******a
发帖数: 6336 | 7 If it vanishes in n-1 steps then it vanishes in n steps,
Hence P(n-1)<=P(n).
【在 s********r 的大作中提到】
: I'm sorry,why P(n)
|
|
