b*****w
发帖数: 79 | 1 Somehow I got interviews from Jane Street and DE Shaw research and people
told me they are very famous. I am never prepared for finance so I guess I
am not going to pass the second rounds.
Here are some questions that I still don't know how to solve.
1. You throw a coin until you see 20 consecutive heads in a row. What is the
probability that you see 10 consecutive tails in a row before you stop?
2. Two people, X and Y, throw coins. X stops until he sees 2 consecutive
heads in a row and Y stops until he sees 3 consecutive heads in a row. Let
the number of tosses before X stops be M, the number of tosses before Y
stops to be N. Find the probability P(M>N). Forgot whether it is P(M>N) or P
(M>=N)..
Can some one give me a hint?
Thanks |
i***y
发帖数: 285 | 2 ding!
the
P
【在 b*****w 的大作中提到】
: Somehow I got interviews from Jane Street and DE Shaw research and people
: told me they are very famous. I am never prepared for finance so I guess I
: am not going to pass the second rounds.
: Here are some questions that I still don't know how to solve.
: 1. You throw a coin until you see 20 consecutive heads in a row. What is the
: probability that you see 10 consecutive tails in a row before you stop?
: 2. Two people, X and Y, throw coins. X stops until he sees 2 consecutive
: heads in a row and Y stops until he sees 3 consecutive heads in a row. Let
: the number of tosses before X stops be M, the number of tosses before Y
: stops to be N. Find the probability P(M>N). Forgot whether it is P(M>N) or P
|
m*********g
发帖数: 646 | 3 1 = (2^11+1)/(2^11+2)
2应该有个TRICK把问题简化，大概就是利用3个T还是3个H是一样的事情，还是其他大牛
来吧。。。 |
p******e
发帖数: 756 | 4 第一个怎么做？
构造一个markov chain然后算absorbing prob？感觉非常地复杂。。。
thx
【在 m*********g 的大作中提到】
: 1 = (2^11+1)/(2^11+2)
: 2应该有个TRICK把问题简化，大概就是利用3个T还是3个H是一样的事情，还是其他大牛
: 来吧。。。
|
w*****e
发帖数: 197 | 5 The first one is very simple because 10 T and 20 H
can't overlap. So essentially speaking, it is like
asking two events, one occurs with 1/2^10 and the other
with 1/2^20, what is the chance of one occurs before
the other.
The second one can be modeled as a markov process.
But it indeed seems to be a bit tedious by hand,
not so much on computer.
the
P
【在 b*****w 的大作中提到】
: Somehow I got interviews from Jane Street and DE Shaw research and people
: told me they are very famous. I am never prepared for finance so I guess I
: am not going to pass the second rounds.
: Here are some questions that I still don't know how to solve.
: 1. You throw a coin until you see 20 consecutive heads in a row. What is the
: probability that you see 10 consecutive tails in a row before you stop?
: 2. Two people, X and Y, throw coins. X stops until he sees 2 consecutive
: heads in a row and Y stops until he sees 3 consecutive heads in a row. Let
: the number of tosses before X stops be M, the number of tosses before Y
: stops to be N. Find the probability P(M>N). Forgot whether it is P(M>N) or P
|
i***y
发帖数: 285 | 6 一题没有你说的那么简单吧。
【在 w*****e 的大作中提到】
: The first one is very simple because 10 T and 20 H
: can't overlap. So essentially speaking, it is like
: asking two events, one occurs with 1/2^10 and the other
: with 1/2^20, what is the chance of one occurs before
: the other.
: The second one can be modeled as a markov process.
: But it indeed seems to be a bit tedious by hand,
: not so much on computer.
:
: the
|
i***y
发帖数: 285 | 7 Why (2^11+1)/(2^11+2)?
【在 m*********g 的大作中提到】
: 1 = (2^11+1)/(2^11+2)
: 2应该有个TRICK把问题简化，大概就是利用3个T还是3个H是一样的事情，还是其他大牛
: 来吧。。。
|
w*****e
发帖数: 197 | 8 能否详细说说？ 我觉得即便用标准的赌局
martingale来做，答案也是我说的那样。
【在 i***y 的大作中提到】
: 一题没有你说的那么简单吧。
|
i***y
发帖数: 285 | 9 １０个T 和２０个H之间是什么，你是没有CARE的啊
如果中间包括２０H了，就是。。。１０T。。。２０H。。。２０H。。。这样计算不是
有重复么？martingale能没说说么？
【在 w*****e 的大作中提到】
: 能否详细说说？ 我觉得即便用标准的赌局
: martingale来做，答案也是我说的那样。
|
m*********g
发帖数: 646 | 10 用MARKOV CHAIN， 捆绑事件， 10H 一个， 10T一个，其他乱七八糟的permutation一
个。
你看几个用MARKOV CHAIN解硬币题就明白了。
【在 i***y 的大作中提到】
: Why (2^11+1)/(2^11+2)?
|
|
|
w*****e
发帖数: 197 | 11 A MARTINGALE APPROACH TO THE STUDY OF OCCURRENCE OF SEQUENCE ...
Google this one. And you shall be enlightened. :)
【在 w*****e 的大作中提到】
: 能否详细说说？ 我觉得即便用标准的赌局
: martingale来做，答案也是我说的那样。
|
c********d
发帖数: 173 | 12 这个。。。
可问的是两个都要occur的概率啊
【在 w*****e 的大作中提到】
: The first one is very simple because 10 T and 20 H
: can't overlap. So essentially speaking, it is like
: asking two events, one occurs with 1/2^10 and the other
: with 1/2^20, what is the chance of one occurs before
: the other.
: The second one can be modeled as a markov process.
: But it indeed seems to be a bit tedious by hand,
: not so much on computer.
:
: the
|
p******e
发帖数: 756 | 13 如果其他的都捆绑到一起，那转移概率怎么算，另外至少要一个20H吧。
【在 m*********g 的大作中提到】
: 用MARKOV CHAIN， 捆绑事件， 10H 一个， 10T一个，其他乱七八糟的permutation一
: 个。
: 你看几个用MARKOV CHAIN解硬币题就明白了。
|
w*****e
发帖数: 197 | 14 Yeah, my bad. Please refer to the martingale approach I referred above.
This is misleading.
【在 w*****e 的大作中提到】
: The first one is very simple because 10 T and 20 H
: can't overlap. So essentially speaking, it is like
: asking two events, one occurs with 1/2^10 and the other
: with 1/2^20, what is the chance of one occurs before
: the other.
: The second one can be modeled as a markov process.
: But it indeed seems to be a bit tedious by hand,
: not so much on computer.
:
: the
|
m*********g
发帖数: 646 | 15 。。。。。
某个事件可以连续发生两次
【在 p******e 的大作中提到】
: 如果其他的都捆绑到一起，那转移概率怎么算，另外至少要一个20H吧。
|
p******e
发帖数: 756 | 16 可以是可以，最传统的办法是算absorbing prob吧，如果你把20H看成10H连续发生两次
，那么10T在连续2次10H之前发生的概率怎么算。另外，如果把其他的都捆绑到一起，转
移概率应该不能认为是简单的叠加吧？
麻烦能给详细点的解法么，多谢
【在 m*********g 的大作中提到】
: 。。。。。
: 某个事件可以连续发生两次
|
c********d
发帖数: 173 | 17 数值地算了一下1
结果是0.0084979
收敛似乎挺慢的，所以不确实误差是多少
the
P
【在 b*****w 的大作中提到】
: Somehow I got interviews from Jane Street and DE Shaw research and people
: told me they are very famous. I am never prepared for finance so I guess I
: am not going to pass the second rounds.
: Here are some questions that I still don't know how to solve.
: 1. You throw a coin until you see 20 consecutive heads in a row. What is the
: probability that you see 10 consecutive tails in a row before you stop?
: 2. Two people, X and Y, throw coins. X stops until he sees 2 consecutive
: heads in a row and Y stops until he sees 3 consecutive heads in a row. Let
: the number of tosses before X stops be M, the number of tosses before Y
: stops to be N. Find the probability P(M>N). Forgot whether it is P(M>N) or P
|
s*****c
发帖数: 753 | 18 For the first question, can I use some "elementry" ways to get some estimate?
So 20 consecutive heads probability is 1/2^20. 10 consecutive tail
probability is 1/2^10.
If I try 2^40 times, on average, I will see 2^20 times 20 consecutive heads,
Lets label it event A, and I will see 2^30 times 10 consecutive tails,
lets label it event B.
So basically it is for 2^40 positions, you have 2^20 A and 2^30 B randomly
position, what is probability the first B is before first A.
calculate the limit and we will get the answer.
the
P
【在 b*****w 的大作中提到】
: Somehow I got interviews from Jane Street and DE Shaw research and people
: told me they are very famous. I am never prepared for finance so I guess I
: am not going to pass the second rounds.
: Here are some questions that I still don't know how to solve.
: 1. You throw a coin until you see 20 consecutive heads in a row. What is the
: probability that you see 10 consecutive tails in a row before you stop?
: 2. Two people, X and Y, throw coins. X stops until he sees 2 consecutive
: heads in a row and Y stops until he sees 3 consecutive heads in a row. Let
: the number of tosses before X stops be M, the number of tosses before Y
: stops to be N. Find the probability P(M>N). Forgot whether it is P(M>N) or P
|
x******a
发帖数: 6336 | 19 the first one I get is
(1-1/2^20)/(1+1/2^10-1/2^19)
the general form i get for n consecutive tails before heads is
(1-1/2^m)/(1+1/2^(m-n)-1/2^(m-1)).
estimate?
consecutive
heads,
tails,
randomly
【在 s*****c 的大作中提到】
: For the first question, can I use some "elementry" ways to get some estimate?
: So 20 consecutive heads probability is 1/2^20. 10 consecutive tail
: probability is 1/2^10.
: If I try 2^40 times, on average, I will see 2^20 times 20 consecutive heads,
: Lets label it event A, and I will see 2^30 times 10 consecutive tails,
: lets label it event B.
: So basically it is for 2^40 positions, you have 2^20 A and 2^30 B randomly
: position, what is probability the first B is before first A.
: calculate the limit and we will get the answer.
:
|
u****g
发帖数: 402 | 20 This is exactly same as what I get.
【在 x******a 的大作中提到】
: the first one I get is
: (1-1/2^20)/(1+1/2^10-1/2^19)
: the general form i get for n consecutive tails before heads is
: (1-1/2^m)/(1+1/2^(m-n)-1/2^(m-1)).
:
: estimate?
: consecutive
: heads,
: tails,
: randomly
|
|
|
f**x
发帖数: 4325 | 21 用markov chain做出来，也是这个结果
你是用哪种方法做的？
【在 x******a 的大作中提到】
: the first one I get is
: (1-1/2^20)/(1+1/2^10-1/2^19)
: the general form i get for n consecutive tails before heads is
: (1-1/2^m)/(1+1/2^(m-n)-1/2^(m-1)).
:
: estimate?
: consecutive
: heads,
: tails,
: randomly
|
x******a
发帖数: 6336 | |
c********d
发帖数: 173 | 23 What is your numerical value, hard to read the expression (1-1/2^20)/(1+2^10
-1/2^19).
Is it 0.000975609?
Doesn't seem correct. When we have a very long sequence which ends with 20H,
it is for sure to have 10T occurred before. So the probability in question
should be almost 1, if not exactly 1.
previous answer (2^11+1)/(2^11+2) seems more reasonable.
【在 x******a 的大作中提到】
: the first one I get is
: (1-1/2^20)/(1+1/2^10-1/2^19)
: the general form i get for n consecutive tails before heads is
: (1-1/2^m)/(1+1/2^(m-n)-1/2^(m-1)).
:
: estimate?
: consecutive
: heads,
: tails,
: randomly
|
c********d
发帖数: 173 | 24 能否仔细说说怎么做的
感觉结果并不对啊
【在 f**x 的大作中提到】
: 用markov chain做出来，也是这个结果
: 你是用哪种方法做的？
|
x******a
发帖数: 6336 | 25 it is
(1-1/2^20)/(1+1/2^10-1/2^19).
thank you for pointing out.
1/2^20)/(1+2^10
with 20H,
question
【在 c********d 的大作中提到】
: What is your numerical value, hard to read the expression (1-1/2^20)/(1+2^10
: -1/2^19).
: Is it 0.000975609?
: Doesn't seem correct. When we have a very long sequence which ends with 20H,
: it is for sure to have 10T occurred before. So the probability in question
: should be almost 1, if not exactly 1.
: previous answer (2^11+1)/(2^11+2) seems more reasonable.
|
f**x
发帖数: 4325 | 26 Markov chain，列出28个方程，解之
具体做法见绿皮书
【在 c********d 的大作中提到】
: 能否仔细说说怎么做的
: 感觉结果并不对啊
|
m*********g
发帖数: 646 | 27 前面我提到的捆绑做法简化的太过了，忽略了“其他乱七八糟的permutation”里面实
际包含了一个opposite的toss结果 （H or T）。
重新捆绑这样
最近一次结果是一个T，最近一次结果是一个H，连出19H，连出9T。四个中间状态，一
共需要三个方程，解出来结果:(1-0.5^20)/(1+0.5^10-0.5^19) 跟前面的兄弟们一样。
具体的转移矩阵：(j-i means: j to i)
0-T p=0.5 ; 0-H p=0.5;
T-H p=1-0.5^9 ; T-9T p=0.5^9
H-T p=1-0.5^19 ; H-19H p=0.5^19
这个做法列出三个方程，（其实只要解后两个，代入第一个就可以了）.该方法可以轻易推广到M,N问题。不知道还有没
有更简便的方法
【在 f**x 的大作中提到】
: Markov chain，列出28个方程，解之
: 具体做法见绿皮书
|
m*********g
发帖数: 646 | 28 另外第二题，我的答案 p(M>=N)=0.26
类似第一题方法，只不过A的结果和B的结果是独立事件。
下面求的是P（M>=N）的概率
note, pij 表示 P( desired |A有i个H in a row,B有j个H in a row)
列出来如下方程：
3/4p00=1/4p10+1/4p11+1/4p01
p10=1/4p00+1/4p01+1/2p_A
p11=1/2p2+1/4p02+1/4p00
p01=1/4p10+1/4p02+1/4p12+1/4p00
p02=1/2p_B+1/4p10+1/4p00
p12=1/2p_B+1/4p00+1/4p2
boundary 是p_A=0; p_B=1
6个方程有点多，解系统方程AX=B,得 0.26
还是等大牛们来指正吧。或者有更简便的方法。 |
a********e
发帖数: 508 | 29 这个转移矩阵怎么来的呢？
为什么从T只可能到H,9T两种？比如连续出现3个T，属于哪种情况？
轻易推广到M,N问题。不知道还有没
【在 m*********g 的大作中提到】
: 前面我提到的捆绑做法简化的太过了，忽略了“其他乱七八糟的permutation”里面实
: 际包含了一个opposite的toss结果 （H or T）。
: 重新捆绑这样
: 最近一次结果是一个T，最近一次结果是一个H，连出19H，连出9T。四个中间状态，一
: 共需要三个方程，解出来结果:(1-0.5^20)/(1+0.5^10-0.5^19) 跟前面的兄弟们一样。
: 具体的转移矩阵：(j-i means: j to i)
: 0-T p=0.5 ; 0-H p=0.5;
: T-H p=1-0.5^9 ; T-9T p=0.5^9
: H-T p=1-0.5^19 ; H-19H p=0.5^19
: 这个做法列出三个方程，（其实只要解后两个，代入第一个就可以了）.该方法可以轻易推广到M,N问题。不知道还有没
|
o****g
发帖数: 314 | 30 random walker模型。令 f(m) 表示从m点出发先到达N2而不是-N1的概率
f(N2) = 1;
f(-N1) = 0;
m >= 1:
f(m) = 0.5*f(m+1) + 0.5*f(-1)
m <= -1:
f(m) = 0.5*f(m-1) + 0.5*f(1)
m == 0:
f(0) = 0.5 * f(1) + 0.5 * f(-1)
要求的也是 f(0)
【在 a********e 的大作中提到】
: 这个转移矩阵怎么来的呢？
: 为什么从T只可能到H,9T两种？比如连续出现3个T，属于哪种情况？
:
: 轻易推广到M,N问题。不知道还有没
|
|
|
a********e
发帖数: 508 | 31 这个不是random walk模型，这个问题是连续N1次向上的stopping time
【在 o****g 的大作中提到】
: random walker模型。令 f(m) 表示从m点出发先到达N2而不是-N1的概率
: f(N2) = 1;
: f(-N1) = 0;
: m >= 1:
: f(m) = 0.5*f(m+1) + 0.5*f(-1)
: m <= -1:
: f(m) = 0.5*f(m-1) + 0.5*f(1)
: m == 0:
: f(0) = 0.5 * f(1) + 0.5 * f(-1)
: 要求的也是 f(0)
|
