Jane Street Interview Question: what is the expected number o... | Glassdoor

Interview Question

Assistant Trader Interview(Student Candidate) New York, NY

what is the expected number of flips of a coin to simulate

  a 6 sided die.

Interview Answer

12 Answers


E(x) = .75*3 + .25*E(X+1). From there it simplifies to E(X) = 10/3

Interview Candidate on Apr 7, 2011

E(x)=3+0.25E(x), so E(x)=4.

William on Apr 7, 2011

Hi Can you please explain this in detail ? I dont seem to follow how did u guys do this ?

HH on May 25, 2011

E(x) = .75*3 + .25*E(X+2).

Someone on Jul 9, 2011

The probability of a six sided die is 1/6, while the probability of a coin flip is 1/2, thus, in order to simulate a six sided die the coin must have the same probability, so 1/2 has to become 1/6. From there, you can write the equation1/2^x=1/6, or to make it simpler, 2^x=6. Without using guess and check, you can rewrite the equation to log base 2 6=x (or log2(6)=x), and from there solve: log(6)/log(2), which comes out to 2.58496, or 2.585 (2^2.585=6.000).
So, to answer your question, the coin would have to flip 2.585 in order to simulate the flip of a coin.

Interview Candidate #2 on Jul 11, 2011

3 flips. The coin gives 1 out of 2 possibilities per flip. 3 flips will give you 6 possible combinations like the 6 sided die (1 heads, 2 tails, 2 heads, 1 tail, etc.).

Casey M on Jul 11, 2011

It is easier to look at it as almost 3 flips set up as a binary number. It would be perfect if you were representing an 8 sided die, but since you want only 6 possible results and 2 flips is too little and 3 flips is too big you have to adjust your fomula as such:

000 = Null this means you scratch these results and flip again three more times.

001 = 1
010 = 2
011 = 3
100 =4
101 = 5
110 = 6
111 = is another Null result

Of course the Nulls can be made to be anything as are the numbers it is all relative. This give you a 1 in 6 chance everytime.

Wsc on Jul 12, 2011

Wsc is on the right track. You have to flip 3 coins at least, but the probability of a null result is 1/4 every time, so you would need to flip 3 more coins. This is a geometric sequence 3+3*1/4+3*(1/4)^2 etc, so the answer is 3/(1-1/4) = 4 expected coin flips.


P on Aug 3, 2011

The correct answer is 11/3, as written by "Someone" on July 9, 2011. Both William's and P's answers are close, but not quite accurate, because they assumed that it takes 3 flips to discard a null result. Instead, it only takes two flips to discard a null result (HHT or HHH) since we don't have to flip the third coin if the first two are already heads (HH). That's why the answer is slightly less than 4.

Indeed, note that we have a 3/4 chance of being able to get one of the 6 good results (HTH, HTT, THH, THT, TTH, TTT) that yields a random number from 1 to 6, and a 1/4 chance of having to reflip the coins (HHH or HHT). The key is that for those two results to be discarded, we only needed to flip 2 coins to determine that! There's no need to flip a 3rd coin if the first two were already HH (it'd be a waste of a throw!). Hence, 3/4 of the time, the number of flips required is three and 1/4 of the time, the expected number of flips required is 2+E[X]:
E[X] = 3/4*3 + 1/4*(2+E[X]).
Alternatively, we can flip the coin twice, and then note that 3/4 of the time (for HT,TH,or TT), we only flip one more coin, and 1/4 of the time (for HH), we have to re-flip, so
E[X] = 2 + (3/4*1+1/4*E[X])
Either way, we have E[X] = 11/4 + 1/4*E[X], which yields the desired result,
E(x) = 11/3.

Ed on Oct 24, 2011


xeesus on Aug 6, 2012

It's 11/3. Say you want HHH and TTT to be your rolls to start over so that the last roll is 50-50 to be H or T and you'll only have to roll twice more since there will be no bias. Roll your first roll, it's H or T. After that there is a probability of 1/4 that you'll have to 2 times again. So there a 3/4 chance you won't have to roll again. So using the equation 1/p to find EN we get 1+2(4/3)=1+8/3=11/3

KG on Jan 22, 2013

You can't flip a die because you only have a coin. DUH

lolz on Mar 13, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.