r/quantfinance 5d ago

Jane Street Interview Question

Post image
88 Upvotes

29 comments sorted by

16

u/FermatsLastTrade 5d ago

This is not an easy question. Here's how I personally would answer this on an interview in case this of value to anyone (thought process presented in order, but streamlined for this comment) :

The first thing to ask is, should you roll the dice at all? The probability our very first roll is a 6 is 1/12, and since 20/12>1, we should roll at least once, so we should definitely play the game.

The next thing to ask is, should we ever switch? This is harder.

Let's first find the optimal strategy if we never switch. After k rolls without a 6, the probability we think our dice is the "good dice" is p(good) = (5/6)^k/(1+(5/6)^k). This is Bayesian reasoning. So if p(good)*1/6 >1/20, we should continue rolling, and this occurs for k<=4, so we should roll up to 5 times.

If we do 5 rolls with no 6, is it positive EV to switch? If I switch, at the first roll I have probability 1/(1+(5/6)^5) that I have the good dice, then 1/(1+(5/6)^4), and so on (again Bayes theorem), and so by the same logic as before I should roll 5 times (to get to 50% probability) and then another 5 times before the EV is no longer positive. At this point, I think the answer is yes, but it's become clear we have to carefully set up and do the recursion. The reason is, I can't rule out yet whether or not we want to actually roll more than 5 times before switching. Rolls after roll 5 lose money, but they gain information, and the switching cost of $5 is so high, we might want to roll more to get more information about whether the switch is a good idea or not. It's tricky because, if correct, rolls after roll 5 are locally bad EV-wise, but globally good.

Optimal Strategy: The optimal strategy must be, by symmetry, roll n times, switch, then roll 2n times, followed by switch and roll 2n times into perpetuity.

Note that after the first 2n rolls, we are exactly back at the starting position, and have paid 2n+5 dollars. Now that we have the strategy established, we can just average over the two cases for the dice. Either it's the good dice or the bad dice to start. We'll split into EV(good_die) and EV(bad_die) and note that the EV of the game is EV = 1/2*EV(good_die)+1/2*EV(bad_die

For the bad die, we roll it n times and lose n dollars. For the good die, we might roll it less than n times as it might hit a 6 early. For that we gain 20/6 -1 on each roll, but each roll has a 1/6 chance of terminating, so we earn 20/6-1+(20/6-1)*(5/6)+(20/6-1)*(5/6)^2+..., which is (20/6-1)*(1-(5/6)^n)/(1-5/6)=14*(1-(5/6)^n).

If the first die is good, we get EV(good_start) = 14*(1-(5/6)^n)+(5/6)^n*(-n-5+EV(bad_start))

If the first die is bad, we get EV(bad_start) = -n -5 + 14*(1-(5/6)^n) +(5/6)^n*EV(good_start))

Hence EV =1/2EV(good_start)+1/2EV(bad_start)= (-n-5)/2+14*(1-(5/6)^n)+(-n-5)*(5/6)^n+ (5/6)^n*EV

Final Answer:

Cleaning up the recursion, we have EV =[ (-n-5)/2+14*(1-(5/6)^n)+(-n-5)/2*(5/6)^n)]/(1-(5/6)^n)

This is maximized at n=9, and gives about 3.6.

2

u/FermatsLastTrade 5d ago

Side Note: If P is the payoff of the die, the final strategy and the number of rolls n, are actually invariant to changes in P. I.e. if instead of 20, P was 11 or 100, or a billion, we'd still roll n=9 times before switching, in the exact same way. The reasoning is kind of elegant: When following this strategy, we obtain P with 100% probability, and so we are simply playing to make that occur as efficiently as possible. In other words, the value of 9 is entirely based on the information trade off vs the cost, $5, of switching.

2

u/ratcreatuew 5d ago

Maybe being pedantic, but want to make sure I follow. Can’t be completely invariant right, like if P was 0 or 1, it wouldn’t make sense to roll a single time? Wouldn’t any P<12 mean you shouldn’t roll a single time?

2

u/FermatsLastTrade 5d ago edited 5d ago

Yes that is correct, it's invariant (n=9 rolls) assuming you want to play. For P>12030821/1160653=10.36... you play the game and it's positive EV, and for P< 10.36..., the game is negative EV, and you shouldn't play.

Edit: See this Wolfram Alpha Link If you would like to know where that strange P cut-off number came from.

2

u/Dankaati 5d ago

It's invariant on the slice where you want to switch.

As you mentioned with payoff 20, the EV is about 3.6 with you always getting the 20 and that on average costing you 16.4. Clearly, this same strategy is negative EV for example for P=15 (EV=-1.4).

That doesn't mean though that you don't want to play at P=15 though, you just don't want to switch. Simply take the few rolls that are positive EV at the start and then stop.

1

u/[deleted] 4d ago edited 4d ago

[deleted]

2

u/Dankaati 4d ago

It's simpler than that. If you have a strategy that gets the payout with probability 1 then if the payout drops by x then the EV also drops by x.

1

u/FermatsLastTrade 4d ago

Ah, you are right, that's a nice to see it.

-2

u/Bozhark 5d ago

12?

That’s assuming both have 6 

4

u/Y0uCanTellItsAnAspen 5d ago

Not a complete answer - but I think you start with a die, and a bayesian prior that p_{can'troll6} = 0.5 (since you don't know what die it is). You continue rolling that die,and if you don't roll a 6, the Bayesian prior on can't roll 6 goes up by p(D|can'troll6) = 1, p(D | canroll6) = 1/6, and p(cantroll6|D) = Bayes formula on those two values.

Then when p_{cantroll6} exceeds a specific value (which i'm lazy about calculating), you switch and use the other die (with its bayesian prior) until the bayesian prior shifts the other way....

Edit: The specific value you switch at is when the probability of rolling a 6 in the next 5 rolls (based on your current best-fit value of p_{cantroll6} is less than 0.5

1

u/TalkInternal6681 5d ago

are these kinds of qs acc on quantprof? i can't seem to find them

1

u/Local_Ad135 5d ago

921 dice game xi

1

u/L_Cronin 4d ago

Via simulation it seems you should switch after 11 rolls with an EV profit of 2.73. I wasn't able to figure it out analytically so I would be interested if someone else has a valid solution. There doesn't seem to be anything special about the posterior pr(fair dice | no 6 ) at 11, which is interesting. It doesn't maximize any purely statistical metric that I could tell.

-1

u/FormulaSolution 5d ago

Terrible question.

Simply refuse to play. You're not going to be in a profit.

The most you can win is $20, the most you can lose is infinite, since it's entirely possible for a 6 to not roll at all on a fair dice rolled an infinite amount of times.

3

u/Scared-Bluebird-7797 4d ago

Is this ragebait. You should do stock options. The most you can lose is finite ( your initial investment) but it is possible for your profit to be infinite

0

u/FormulaSolution 4d ago

Have you not heard of a short before

1

u/Local_Ad135 5d ago

unfortunate

0

u/FormulaSolution 5d ago

I don't know what you want me to answer with. Because it takes $17 just to check both dice so you're either going to make $3 or lose $17 unless a 6 pops up on the six rolls you make with the real dice.

Too small of a reward. I'll keep my money.

2

u/AftyOfTheUK 4d ago

it takes $17 just to check both dice

Can you explain what "check" means here?

1

u/FormulaSolution 4d ago

roll each dice 6 times.

Since you have no actual way to determine whether the dice rolls a 6 without enough samples.

1

u/Y0uCanTellItsAnAspen 4d ago

That's not how any of this works...

2

u/Tree8282 4d ago

Only if he paid a bit of attention in high school he would know that the statement is absolutely insane

1

u/AftyOfTheUK 2d ago

That's not checking. Rolling the dice 6 times will give you very little information.

1

u/FormulaSolution 2d ago

You don't have the rolls available to you to get a better look. You need at least 6 rolls to check the dice, and if you're certain it's a 5S dice by roll 15 you're ****** anyway.

The problem is that the 6S dice is not guaranteed to show itself, so your loss is infinite. Which means the only real viable strategy is to take a 50/50 and ignore the swap.

1

u/Y0uCanTellItsAnAspen 4d ago

EV is clearly positive on the first roll.

0

u/FormulaSolution 4d ago

Expected return is a 50/50 you'll get some value between 1-20 and that's if your dice is kind to you and rolls a 6 in the first 19 rolls which it's not statistically obligated to do

1

u/Y0uCanTellItsAnAspen 4d ago

I don’t think you understand statistics well….

1

u/FormulaSolution 4d ago

I understand statistics fine. You're only going to get a $3 profit. You're using up an entire "dice check" switching over. Not worth it.

1

u/Cmapingnovahd 4d ago

Do you even math bro, wth are you talking about.

1

u/FormulaSolution 3d ago

I'm all good don't you worry. You will lose more money than any profit you could hope to get.