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.

0

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

Interview Candidate on Apr 7, 2011
2

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

William on Apr 7, 2011
1

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

HH on May 25, 2011
8

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

Someone on Jul 9, 2011
3

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.
x=2.585

Interview Candidate #2 on Jul 11, 2011
0

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
0

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:
0=tails

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
4

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.

4

P on Aug 3, 2011
12

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
0

4.5

xeesus on Aug 6, 2012
1

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
0

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

lolz on Mar 13, 2013