另一种解法
所在版块:创业求职 发贴时间:2008-06-19 15:23

用户信息
复制本帖HTML代码
高亮: 今天贴 X 昨天贴 X 前天贴 X 
令random number X为number of tosses to get m consecutive heads。令random number Y为number of tosses to get m-1 consecutive heads。

下面求解 E(X|Y=y)

x=y+1时, P(X=y+1|Y=y) = 1/2
x>y+1时, P(X=x|Y=y) = 1/2 * (x-y-1)

所以 E(X|Y=y) = 1/2 * (y+1) + 1/2 * ((y+1) + E(X)) = y + 1 + E(X)/2

所以 E(E(X|Y=y)) = E(y + 1 + E(X)) = E(Y) + 1 + E(X)/2

我们知道 E(X) = E(E(X|Y=y)), 即 E(X) = E(Y) + 1 + E(X)/2 => E(X) = 2 (E(Y) + 1)

所以 E(X) = 2^(m-1) * (E(Y_m=1) + 2) - 2

其中 random number Y_m=1 为 number of tosses to get 1 consecutive head, E(Y_m=1) = 1/p = 2

所以 E(X) = 2^(m+1) - 2


至于第二题,思路上并不难,只是结果不好解也不好表达。

-*
+-*
...
+++++++-*
++++++++*

P(n) = P(n-1)/2 + P(n-2)/4 + ... + P(n-m)/2^m + 1/2^m

令 f(n) = 2^n * (P(n) - 1)

f(n) = f(n-1) + f(n-2) + ... + f(n-m) 当k<m时, f(k) = -2^k

m=1时 f(n)是常数数列

m=2时 f(n)是斐波那契数列

...

一般的f(n)可以用矩阵表示

令 G = (m*m matrix)

0 1 0 0 ... 0
0 0 1 0 ... 0
0 0 0 1 ... 0
...
0 0 0 0 ... 1
1 1 1 1 ... 1


令 L = (1*m vector)

0 0 0 ... 0 1

令 V = (m*1 vector)


1
2
4
...
2^(m-1)

当k>=m时,f(n)可以表示为: f(n) = -L * G^(n-m+1) * V

P(n) = f(n) * 2^(-n) + 1
.
欢迎来到华新中文网,踊跃发帖是支持我们的最好方法!

 相关帖子 我要回复↙ ↗回到正文
在SCB面试的一道概率题 tensor   (134 bytes , 2134reads )
这个题其实很简单的。。思路快的话2分钟就做出来了。。比较难一点的版本。。 hula   (237 bytes , 731reads )
引用下卷心菜兄弟的解法 冷色蓝天   (169 bytes , 581reads )
另一种解法 大树下   (1145 bytes , 513reads )
scb是哪里?什么职位要问这个问题? 威尔的身份   (6 bytes , 383reads )
这个问题很好,谁来回答一下? parrot   (36 bytes , 347reads )
SCB = standard chartered bank. position only LZ knows 黑夹克   (0 bytes , 407reads )
答案看来是6 darkart   (398 bytes , 494reads )
是5? bbx   (0 bytes , 278reads )
答案是好多?? StefinieSun   (0 bytes , 234reads )
8次? StefinieSun   (0 bytes , 225reads )
我靠,难啊,解得是6 卷心菜   (552 bytes , 898reads )
答案是6, 你这是我看见的最快的办法了. 是一个QUANTS 的POSITION tensor   (0 bytes , 352reads )
菜兄高见!   (4575 bytes , 538reads )
哇,职场版惊见数学题 :D parrot   (41 bytes , 385reads )
大家都在show off呢:D darkart   (0 bytes , 239reads )
我这儿都解出正确答案了怎么还有朋友跟帖5和8?? 卷心菜   (301 bytes , 517reads )
楼上的概率学的很不错!同意你的算法 周星驰   (0 bytes , 360reads )
is it 4? delay   (23 bytes , 404reads )