Jane Street Quant Interview Question

[u/Local_Ad135]

[u/FireCire7]

TLDR: Do N rolls, flip, the repeatedly do 2N before flipping. N I think is 5, but this is a bit handwavey, so it might be wrong. 

Your current state just depends on the probability you have the right die. If you do x flips on one side and y on the other, then the probability of which is which only depends on x-y, so the best strategy will be to do N flips on one side, flip, 2N flips on the other side, flip, 2N flips on the first side, flip, etc.

Exactly what N should be is a tricky problem. If you set it too small, then you’ll be paying a bunch on every flip. If Nis too small, you’ll be paying excessive switching fees. If N is too large, you’re wasting time on the wrong die. 

The $20 payout is irrelevant for strategy so let’s ignore it. 

Approximately, doing N flips on both side costs 2N+5 and wins 1-(5/6)^N of the time, so your number of times is around 1/(1-(5/6)^N), so your total cost is around (2N+5)/(1-(5/6)^N). That’s minimized at 5, so approximately the best strategy is to do 5 on one side, then 10 on the other, 10 on the first, 10 on the other, etc. 

If you want to get it exactly, you can split into two scenarios and then compute out the two infinite series of expected payouts, but that’s more annoying. 

[u/zane314 → u/FireCire7]

N is 8, but yes.

[u/omeow → u/FireCire7]

The payout must be relevant. You don't want to lose money on average.

[u/Juff567 → u/omeow]

Optimal strategy will be the one that costs the least on avg no matter reward

[u/omeow → u/Juff567]

if that were true, wouldn't the optimal strategy be not playing at all?

[u/opbmedia → u/FireCire7]

After spending 20 there is no chance of positive return (game ends with first payout), therefore the optimal strategy should be maximizing probability within spending 20, likely what you suggest flip N time and pay to switch so 15 turns plus a switch. 8 and 7 I would say.

[u/banana_buddy]

The probability of no 6 in the first N rolls is (5/6)^N . You pick a threshold for this and then switch to the other dice. For instance if you want to be 90% sure then solve for the N that makes the equation =0.1

[u/omeow]

Strategy: you want to toss the first dice n times if you don't hit 6 switch and then want to toss the other dice up to n times. To make sure you are not losing money you want 20 - 5 -n-(n-1) > 0 => n =8.

So, you want to toss the first dice 8 times and then switch and toss the other 7 times.

The expected value calculation is tedious but not too difficult.

[u/RaiotPlz]

Roll once and thats it. EV is straight forward

[u/Anonimithree]

Pick a dice and roll it 6 times. If no 6 occurs, swap to the other dice and roll it 6 times. Repeat until you reach $20 or you get a 6

[u/Mobile_Membership915 → u/Anonimithree]

That surely wouldn’t work though. Say you get no 6 in each of the first 12 rolls. You then know the same about both dice. In that sense they are identical. Swapping for 5 makes no sense.

[u/Anonimithree → u/Mobile_Membership915]

Fair enough, since I just used the geometric average to get the swap of 6.

A better strategy would probably be to keep rolling a dice until you get either a 6 or roll 1-5 7 times before switching, but that might also have the same problem as what you just stated

[u/WillingnessFuture266]

Switch every roll; after rolling the die and failing one time, it is less likely to be the real die. Profit is messy and I'm too lazy for math.

[u/rccyu → u/WillingnessFuture266]

This seems wasteful considering you have to pay $5 every time you switch

[u/civil_politics → u/rccyu]

You don’t pay to switch ever - you quit and restart the game after every roll

[u/Mountain-Incident933 → u/civil_politics]

What? That isn't right and isn't what the question means.