在SCB面试的一道概率题当时虽然给了答案...但是比较慢,谁有更快的解答?
toss a fair coin, what is the expected number of tosses to
get 2 consecutive heads?
[tensor (6-13 22:50, Long long ago)]
[ 传统版 |
sForum ][登录后回复]1楼
is it 4?What's the correct ans?[delay (6-14 12:06, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼
我靠，难啊，解得是6设expect number = E，
扔两次正好如果正好是都是正面那么就赢了，之后不再需要扔了。
设扔两次后第二次硬币是反面的情况下再需要扔的expect number = a, 这种情况的几率是50%
设扔两次后在第一次是反面第二次是正面的情况下再需要扔的expect number = b，这种情况的几率是25%
那么E = 25%x2 + 50%(2+a) + 25%(2+b)
显然a = E （重头再来）
而b = 50%x1 + 50%x(E+1) 注：50%x1就是一般机会一扔是正面，成功；50%x(E+1)就是另一半机会一扔是反面白白增加了一个扔硬币(+1)次数后重新回到起点E
所以：E=25%x2 + 50%(2+E) + 25%[2+50%x1+50%(E+1)]
解得：E=6
这种题如果是填空题的话根本快不了。[卷心菜 (6-14 15:51, Long long ago)]
[ 传统版 |
sForum ][登录后回复]3楼
答案是好多？？[StefinieSun (6-14 22:58, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼
(引用 StefinieSun:答案是好多？？)8次？[StefinieSun (6-14 23:00, Long long ago)] [ 传统版 | sForum ][登录后回复]5楼
是5？[bbx (6-14 23:25, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼
(引用 卷心菜:我靠，难啊，解得是6设expect number = E，
扔两次正好如果正好是都是正面那么就赢了，之后不再需要扔了。
设扔两次后第二次硬币是反面的...)我这儿都解出正确答案了怎么还有朋友跟帖5和8？？很显然，答案必然在5到8之间，
25%的概率需要expect四次“独立”的实验
当前一次一次扔硬币搞的里面关系复杂，不独立，中间都correlate在一起。
所以答案肯定是大于5次(1,2)(2,3)(3,4)(4,5)但这四次并不完全独立
而小于8次(1,2)(3,4)(5,6)(7,8)这样四次独立但完全忽略了(2,3)(4,5)(6,7)
所以很显然，答案必然大于5而小于8。[卷心菜 (6-15 0:31, Long long ago)]
[ 传统版 |
sForum ][登录后回复]7楼
(引用 卷心菜:我这儿都解出正确答案了怎么还有朋友跟帖5和8？？很显然，答案必然在5到8之间， 25%的概率需要expect四次“独立”的实验 当前一次一次扔...)楼上的概率学的很不错！同意你的算法[周星驰 (6-15 10:07, Long long ago)] [ 传统版 | sForum ][登录后回复]8楼
(引用 卷心菜:我靠，难啊，解得是6设expect number = E，
扔两次正好如果正好是都是正面那么就赢了，之后不再需要扔了。
设扔两次后第二次硬币是反面的...)哇，职场版惊见数学题 :D有没有人公布答案？
我觉得卷心菜是对的。[parrot (6-15 10:24, Long long ago)]
[ 传统版 |
sForum ][登录后回复]9楼
(引用 卷心菜:我靠，难啊，解得是6设expect number = E，
扔两次正好如果正好是都是正面那么就赢了，之后不再需要扔了。
设扔两次后第二次硬币是反面的...)菜兄高见!Expected Tosses for Consecutive Heads with a Fair Coin
Date: 06/29/2004 at 23:35:35
From: Adrian
Subject: Coin Toss
What is the expected number of times a person must toss a fair coin
to get 2 consecutive heads? I'm having difficulty in finding the
probabilty when the number of tosses gets bigger.
Here's my thinking:
1) You will only stop when the last two tosses are heads.
2) The random variable should be # of tosses
# of tosses 1 2 3 4 5
Prob 0 P(HH) P(THH) P(TTHH)+P(HTHH) and so on....
However I get 2(1/4)+ 3(1/8) + 4(2/16) + 5(4/32) + ....
Am I doing something wrong here?
--------------------------------------------------------------------------------
Date: 07/01/2004 at 19:23:53
From: Doctor Mitteldorf
Subject: Re: Coin Toss
Hi Adrian -
Your thinking is very good and clear. But the calculation you have
set up is potentially infinite. Sometimes that's ok, and you can get
very close with just the first few terms; in this case, you'll have to
go out past 20, taking 2^20 possibilities into account in order to get
a reasonably accurate number. So we might look for a trick or
shortcut.
In this case, the standard trick is "recursion". Try to write the
probability after a certain number of flips in terms of itself. Let's
let X = the expected count (the thing we're looking for). Start the
way you started:
X = [2(1/4) for HH] + [something for HT] + [something for TT]
+ [something for TH]
Here's how we can evaluate the "something" for HT. There's a 1/4
probability of getting there. And once you've gotten there, you're
exactly where you were when you started, except you've wasted 2
flips. So for that "something" I'm going to write (1/4)(X + 2). The
1/4 says that you have a 1/4 chance of flipping HT. The (X + 2) says
that we have the same expectation now as we did when we started (X)
except that we've wasted two flips.
Similarly, the [something for TT] becomes another (1/4)(X + 2), just
the same as HT.
The last term, TH, is a little trickier, because we're NOT in the same
position we started in, because we've got one H "in the bank". We
have a 1/2 chance of getting another head on the 3rd flip, so that
gives a contribution of (1/4)(1/2)(3). We also have a 1/2 chance of
getting a tail on the 3d flip, leaving us in the same position we
started, except that we've wasted 3 flips now. So that is
represented by (1/4)(1/2)(X + 3).
Put all this together now to make an equation for X:
X = 2(1/4) + (1/4)(X+2) + (1/4)(X+2) + (1/4)(1/2)3 + (1/4)(1/2)(X+3)
What I would do at this point is first to solve for X, and see if I
got a reasonable answer. A reasonable answer is something bigger than
4 and smaller than 10. Next, I wouldn't trust my abstract reasoning -
I'd go write a computer program to check the value that I got from the
algebra.
Will you let me know if this works out?
--------------------------------------------------------------------------------
Date: 07/01/2004 at 20:22:46
From: Doctor Anthony
Subject: Re: Coin Toss
Hi Adrian -
A difference equation is often useful here.
Let a = expected number of throws to first head.
We must make 1 throw at least and we have probability 1/2 of a head
and probability 1/2 of returning to a, so
a = (1/2)1 + (1/2)(1 + a)
(1/2)a = 1
a = 2.
Let E = expected number of throws to 2 consecutive heads.
Consider that we have just thrown a head and what happens on the next
throw. We are dealing with the (a + 1)th throw, with probability 1/2
this is not a head and we return to E.
So E = (1/2)(a + 1) + (1/2)(a + 1 + E)
(1/2)E = a + 1
E = 2(a + 1)
and now putting in the value a = 2 we get E = 2(3) = 6
Expected throws to 2 consecutive heads is 6.
--------------------------------------------------------------------------------
Date: 07/03/2004 at 01:20:24
From: Adrian
Subject: Thank you (Coin Toss)
Thanks. The answer is indeed 6. I've got a simple C++ program to
show this...
//------------------------------------
#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;
int flips();
void main()
{ int result = 0;
int i;
srand(time(NULL));
for (i = 1; i < 999999; i++)
result += flips();
cout << "Expected value = "<< result / i << endl;
}
int flips()
{ int i, j, counter;
i = 0;
j = rand() % 2;
counter = 1;
while ((i+j) != 2)
{ i = j;
j = rand() % 2;
counter++;
}
return counter;
}
//---------------------------
http://mathforum.org/library/drmath/view/65495.html[● (6-15 12:42, Long long ago)]
[ 传统版 |
sForum ][登录后回复]10楼
答案看来是6darkart@darkart-laptop:~/workspace$ java tt 10
5.3
darkart@darkart-laptop:~/workspace$ java tt 100
5.12
darkart@darkart-laptop:~/workspace$ java tt 1000
5.977
darkart@darkart-laptop:~/workspace$ java tt 10000
6.0389
darkart@darkart-laptop:~/workspace$ java tt 100000
6.01165
darkart@darkart-laptop:~/workspace$ java tt 1000000
5.997272
darkart@darkart-laptop:~/workspace$ java tt 10000000
6.0009894[darkart (6-15 17:56, Long long ago)]
[ 传统版 |
sForum ][登录后回复]11楼
(引用 parrot:哇，职场版惊见数学题 :D有没有人公布答案？ 我觉得卷心菜是对的。)大家都在show off呢：D[darkart (6-15 17:59, Long long ago)] [ 传统版 | sForum ][登录后回复]12楼
scb是哪里？什么职位要问这个问题？歇菜。[威尔的身份 (6-15 22:02, Long long ago)] [ 传统版 | sForum ][登录后回复]13楼
这个题其实很简单的。。思路快的话2分钟就做出来了。。比较难一点的版本。。toss a fair coin, what is the expected number of tosses to get m consecutive heads?
继续更难一些（这个没遇到过的估计要翻资料才能做出来了）
toss a fair coin n times, what is the probability to get at least m (m<=n) consecutive heads?
[hula (6-16 13:55, Long long ago)]
[ 传统版 |
sForum ][登录后回复]14楼
(引用 威尔的身份:scb是哪里？什么职位要问这个问题？歇菜。)这个问题很好，谁来回答一下？ｐｓ，数学高手太多，怕怕。。。。。。[parrot (6-16 14:30, Long long ago)] [ 传统版 | sForum ][登录后回复]15楼
(引用 卷心菜:我靠，难啊，解得是6设expect number = E， 扔两次正好如果正好是都是正面那么就赢了，之后不再需要扔了。 设扔两次后第二次硬币是反面的...)答案是6, 你这是我看见的最快的办法了. 是一个QUANTS 的POSITION[tensor (6-16 18:47, Long long ago)] [ 传统版 | sForum ][登录后回复]16楼
(引用 hula:这个题其实很简单的。。思路快的话2分钟就做出来了。。比较难一点的版本。。toss a fair coin, what is the expected number of tosses t...)引用下卷心菜兄弟的解法-* 1/2
+-* 1/4
++-* 1/8
.....
+++++...+- (total m) 1/(2^m)
+++++...++ (total m) 1/(2^m)
x= (1/2)(x+1) + (1/4)(x+2) +... +(1/(2^m))(x+m)+(1/(2^m))*m
=> x = 2^(m+1) - 2
[冷色蓝天 (6-16 21:13, Long long ago)]
[ 传统版 |
sForum ][登录后回复]17楼
(引用 parrot:这个问题很好，谁来回答一下？ｐｓ，数学高手太多，怕怕。。。。。。)SCB = standard chartered bank. position only LZ knows[黑夹克 (6-16 22:29, Long long ago)] [ 传统版 | sForum ][登录后回复]18楼
(引用 冷色蓝天:引用下卷心菜兄弟的解法-* 1/2
+-* 1/4
++-* 1/8
.....
+++++...+- (total m) 1/(2^m)
+++++...++ (total m) 1/(2^m)
x= (1/2)(x+1) + (...)另一种解法令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[大树下 (6-19 15:23, Long long ago)]
[ 传统版 |
sForum ][登录后回复]19楼