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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 阿米巴虫面试问题: : 一个阿米巴虫,下一步有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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : You are right, it's not correct.
| z*****n 发帖数: 165 | 5 That's convincing, thanks!
【在 a********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I'm sorry,why P(n)
|
|