o********n 发帖数: 100 | 1 请教一道题:
正反两面概率相等硬币,丢100次,问连续4次正面的概率是多少?
Flipping 100 fair coins, how to calculate the probability that at least
one set of
continuous four heads happen in the 100 flipping sequence?
谢谢! | s*******s 发帖数: 1568 | 2 induction?
Pn=1/16+1/2Pn-1+1/4Pn-2+1/8Pn-3+1/16Pn-4
【在 o********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请教一道题: : 正反两面概率相等硬币,丢100次,问连续4次正面的概率是多少? : Flipping 100 fair coins, how to calculate the probability that at least : one set of : continuous four heads happen in the 100 flipping sequence? : 谢谢!
| A*******u 发帖数: 66 | 3 (1/97)*(1/16)=1/1552
【在 o********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请教一道题: : 正反两面概率相等硬币,丢100次,问连续4次正面的概率是多少? : Flipping 100 fair coins, how to calculate the probability that at least : one set of : continuous four heads happen in the 100 flipping sequence? : 谢谢!
| j******n 发帖数: 271 | 4 Are you kidding? Law of large number (or maybe some other name?) says it
is close to 1. I think swordmans got it right. Just some 体力活 is needed
to work out a closed-form from the induction.
【在 A*******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : (1/97)*(1/16)=1/1552
| h**6 发帖数: 4160 | 5 P(0) = P(1) = P(2) = P(3) = 0, P(4) = 1/16
P(n) = P(n-1) + 1/32 * [1-P(n-5)], n>=5 | o****b 发帖数: 31 | 6 swordsman's solution is correct | c*****w 发帖数: 50 | 7 Brutal force solution
0.972715
/*** mathematica code ***/
F[s_, p_, r_] := (p*s)^r*(1 - p*s)/(1 - s + (1 - p)*p^r*s^(r + 1))
Plus@@CoefficientList[Series[F[s, 0.5, 4], {s, 0, 100}], s]
【在 o********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请教一道题: : 正反两面概率相等硬币,丢100次,问连续4次正面的概率是多少? : Flipping 100 fair coins, how to calculate the probability that at least : one set of : continuous four heads happen in the 100 flipping sequence? : 谢谢!
| x*a 发帖数: 48 | 8 1. Recursion: C(n) = C(n-1)+C(n-2)+C(n-3), n>=4, C(1)=2,C(2)=2,C(3)=4
2. P(n) = 1-C(n+1)/2^n
3. for n=100, Pn = 0.9997
4. Sanity check: C(4)=8 -> P(3)=0, C(5)=14 -> P(4)=1/8, C(6)=26 -> P(5)=3/16
5. Closed solution: solve cubic equation: x^3-x^2-x-1=0 | m******2 发帖数: 252 | 9 能解释下么?谢谢
【在 s*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : induction? : Pn=1/16+1/2Pn-1+1/4Pn-2+1/8Pn-3+1/16Pn-4
| b******n 发帖数: 637 | 10 这种数列归纳,然后用特征值求解的方法完全丧失了数学味道……至少在数学里边这也
算是非主流的知识,去问数学系的人我打赌10个里边9个不知道1个要查书,只有CS做算
法的人可能比较熟。我想的方法是把他建成Markov Chain,然后把转移矩阵对角化,再
来个100次方就可以了。然而对角化这个过程相当不trivial,只有一个特征根是有理数。
Anyway也可能是我境界不够,还是希望谁能给出个初等解法。这种面试题要真逼到用高
等解法,只能说明面试官想把你做了。 | p*****k 发帖数: 318 | 11
as Xia indicated, it's easier to work with the prob that "HHHH"
does not appear. but seems one term is missing in the solution above.
it should be:
1. Recursion: C(n) = C(n-1)+C(n-2)+C(n-3)+C(n-4), with
C(1)=2,C(2)=4,C(3)=8,C(4)=16
2. P(n) = 1-C(n)/2^n
3. for n=100, Pn = 0.97
the exact solution is to solve x^4-x^3-x^2-x-1=0, but a good
approximation when n is large enough is given by the root of the
eq. above with the largest norm: 1-c*r^n, where c~1.09166, r~0.963781
one could also use the ge
【在 x*a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1. Recursion: C(n) = C(n-1)+C(n-2)+C(n-3), n>=4, C(1)=2,C(2)=2,C(3)=4 : 2. P(n) = 1-C(n+1)/2^n : 3. for n=100, Pn = 0.9997 : 4. Sanity check: C(4)=8 -> P(3)=0, C(5)=14 -> P(4)=1/8, C(6)=26 -> P(5)=3/16 : 5. Closed solution: solve cubic equation: x^3-x^2-x-1=0
| s******1 发帖数: 157 | |
|