一个期望问题

话说你看到这幅图是不是感觉很坑爹啊,这不是连分数吗,怎么会跟期望问题有关咧,其实吧,在一些可能会出现无限步骤的求期望的问题中,他们的思想还是有些类似的。

先看这个连分数的求法,略去1+1/的那部分看剩下的,假设剩下的是x那么整个式子是=1+1/x的,那么x=2+1/x,然后解一个一元二次方程,然后这个式子显然是正的啊!所以x=1+sqrt(2),最后求得答案是1+1/x=srqt(2)

下面来看这个期望问题,从A退出的概率是1/2,从A到B的概率是1/2,从B退出的概率是1/2,从B到A的概率是1/2,问从A到退出期望会走几步,也就是说平均走几步才能出去。

标准的做法是用每一个的步数乘以概率然后加起来,就是0*1/2+1*(1/2)*(1/2)+2*(1/2)*(1/2)*(1/2)*(1/2)......然后可以利用生成函数之类的计算出结果是1

方法计算起来还是有些麻烦的,现在我们换个方法,假设E1表示从A开始平均多少步能退出,E2表示从B开始走,多少步能退出,然后有点类似连分数那样的无穷的形式,我们可以得到两个式子

(1)E1=1/2+1/2*E2 
(2)E2=1/2+1/2*E1

就是说从A开始走时,我们有1/2的平均步数退出,剩下的就是1/2的E2的平均步数,这样很顺利的解出E1=1

同样的如果我们想计算从A退出的概率可以利用类似的想法得到式子

P=1/2+1/2*1/2*P

可推得P=2/3,同样的物理上有很多类似的比如求无线网络上两点之间的电阻神马的又都有些类似,总之,灵活运用这种方法会使解决问题变得轻松简单。

您可能喜欢:
我猜您可能还喜欢:
,

《一个期望问题》有 3 条评论

  1. scturtle | #1

    每过段时间总得来看看这篇

Trackbacks/Pingbacks:

  1. md5到md5破解的一些科普 | 吃杂烩
  2. 2-sat问题 | isnowfy

发表评论