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 的大作中提到】
: 请教一道题：
: 正反两面概率相等硬币，丢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 的大作中提到】
: 请教一道题：
: 正反两面概率相等硬币，丢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 的大作中提到】
: (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 的大作中提到】
: 请教一道题：
: 正反两面概率相等硬币，丢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 的大作中提到】
: 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 的大作中提到】
: 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 | |
|
