7.7 Jane Street Capital Second Round Interview

[DieterD]

Why bother with infinite sums when you can just write a simple finite sum?

 

[Advait]

E=(100*101-(E-1)*(E-2))/200 + (E-2)/100((100*101-(E-1)*(E-2))/200 -1 + (E-2)/100((100*101-(E-1)*(E-2))/200 -1 +…
E = [(100*101-(E-1)*(E-2))/200 - (E-2)/100]/(1-(E-2)/100)

 

[Advait]

B'coz I dont see how you can have a finite sum since the number of tries are unlimited and even the nth try (if required) has a finite probability and a payoff.

 

[DieterD]

You can use the fact that if you decide to roll again, it's basically just the same as the original game, with the only difference being that you have now paid $1. This then allows you to write a recursion formula for the expectation of this game.

 

[Advait]

But if you decide to roll a second time, its the same game but with a lower Pr and so and so forth...Ultimately, I too have tried getting a recursive formula via an infinite series....

 

[pruse]

I think that is incorrect. The interviewer told me that the expected value should be above 80. He then asked me to calculate the expected value of the game if the player adopted a strategy of opting to roll again only if he/she rolls <=84 which I then worked out to be 87.5 according to the following calculation.

E(game) = (Pr(>84) x (92.5)) + (Pr(<=84) * (E(game) - 1))

Using the above recurrence relation, E(game) works out to be $87.50. So after he asked me this, I learnt that the expected value of the game is at least $87.50. However, I am confused on how to find the maximum expected value(which I think is what the interviewer wanted) systematically.

Isn't the solution to that equation 87.25?

The recursion we get for (E) if we want to maximize the e.v. is

1) (E = \frac{\lfloor E-1 \rfloor}{100}\cdot (E-1) + \large(1- \frac{\lfloor E-1 \rfloor}{100}\right)\cdot \frac{\lfloor E \rfloor +100}{2}), if ( E ) is not integral. The solution to this equation is (\frac{1223}{14}\approx 87.36).

2) (E = \frac{E-2}{100}\cdot (E-1) + \large(1- \frac{E-2}{100}\right)\cdot \frac{E-1+100}{2}), if ( E ) is integral. But this does not have an integral solution.

So it appears the best e.v. we can do is 87.36.

 

[HarishKumar]

^I prob got 87.50 using approximations, it was during the interview after all

 

[koupparis]

Isn't the solution to that equation 87.25?

The recursion we get for (E) if we want to maximize the e.v. is

1) (E = \frac{\lfloor E-1 \rfloor}{100}\cdot (E-1) + \large(1- \frac{\lfloor E-1 \rfloor}{100}\right)\cdot \frac{\lfloor E \rfloor +100}{2}), if ( E ) is not integral. The solution to this equation is (\frac{1223}{14}\approx 87.36).

2) (E = \frac{E-2}{100}\cdot (E-1) + \large(1- \frac{E-2}{100}\right)\cdot \frac{E-1+100}{2}), if ( E ) is integral. But this does not have an integral solution.

So it appears the best e.v. we can do is 87.36.

I think I'm missing a couple pieces from your logic. I assume we stop when we roll > E if E is non-integer, so I think your floors should be ceils. Also for (\frac{\lfloor E \rfloor +100}{2}), shouldn't this represent (E(winnings - rolls | roll > E))? I think you've only got a piece of that expectation there.

 

[DieterD]

You should stop if you roll > E-1. Since it'll cost you $1 to roll again, you can only expect E-1 if you roll again.

 

[pruse]

I think I'm missing a couple pieces from your logic. I assume we stop when we roll > E if E is non-integer, so I think your floors should be ceils. Also for (\frac{\lfloor E \rfloor +100}{2}), shouldn't this represent (E(winnings - rolls | roll > E))? I think you've only got a piece of that expectation there.

Nope. This recursion comes from conditioning on what happens on the first roll. If on the first roll you roll more than (E-1) then your expectation is really (\frac{\lfloor E \rfloor +100}{2}) (you walk away after the first roll, and you haven't paid anything).

 

[Advait]

I'm not sure if 87.5 is the right answer. I did a 50,000 event sample MC Simulation with a maximum of 25 re-tries at the cost of 1 $ (yes, I know that this is not exactly the question that is being discussed but let's be honest, the probability one would try >25 times is several orders of magnitude lower than single digit tries so I assumed their effect to be close to zero) in MS Excel and the entire game yielded a decent profit!

 

[pruse]

I'm not sure if 87.5 is the right answer. I did a 50,000 event sample MC Simulation with a maximum of 25 re-tries at the cost of 1 $ (yes, I know that this is not exactly the question that is being discussed but let's be honest, the probability one would try >25 times is several orders of magnitude lower than single digit tries so I assumed their effect to be close to zero) in MS Excel and the entire game yielded a decent profit!

I don't think anyone is saying it's 87.5. What I was saying above is that it's (\frac{1223}{14} \approx 87.36).

What did you get using MC?

Note that the recursion we've been discussing assumes that an e.v. optimizing strategy is followed, but it does not tell us what strategy (or strategies) to follow. Is it, 'keep rolling as long as you roll less than (E-1 = 86.36)'? The recursion for this strategy is (E = \frac{86}{100} (E-1) + \frac{14}{100}\cdot \frac{87+100}{2}), whose solution is (\frac{1223}{14}) -- the answer the above a priori (before our strategy is known) recursion gave us, whew! Did we just get lucky?

 

[Advait]

No. Your answer of 87.36 (or for that matter 87.5 which is not significantly greater) is significantly of from the results I got in my MC simulation. On refreshing the simulation multiple times, I observed a profit of 3.82-3.93 per simulation event path based on 87.5 as the ex-ante asking price for the game with a maximum of 25 re-tries with each progressive re-try costing 1.

 

[DieterD]

What strategy does your player employ in the MC simulation?

 

[Advait]

If the player gets 87 or above, take the money and quit. If not keep trying. If he ends up not quitting until the 25th re-try, that sample event simulation is discarded.

 

[pruse]

No. Your answer of 87.36 (or for that matter 87.5 which is not significantly greater) is significantly of from the results I got in my MC simulation. On refreshing the simulation multiple times, I observed a profit of 3.82-3.93 per simulation event path based on 87.5 as the ex-ante asking price for the game with a maximum of 25 re-tries with each progressive re-try costing 1.

It's the correct strategy, but you must be implementing it wrong. I wrote a quick Matlab script with 1e6 MC simulations and got an e.v. of 87.352, confirming my result above.

 

[pruse]

If the player gets 87 or above, take the money and quit. If not keep trying. If he ends up not quitting until the 25th re-try, that sample event simulation is discarded.

You can't just discard these, as they are plausible outcomes that need to factor into the e.v.

 

[Wayne Gan]

I think that is incorrect. The interviewer told me that the expected value should be above 80. He then asked me to calculate the expected value of the game if the player adopted a strategy of opting to roll again only if he/she rolls <=84 which I then worked out to be 87.5 according to the following calculation.

E(game) = (Pr(>84) x (92.5)) + (Pr(<=84) * (E(game) - 1))

Using the above recurrence relation, E(game) works out to be $87.50. So after he asked me this, I learnt that the expected value of the game is at least $87.50. However, I am confused on how to find the maximum expected value(which I think is what the interviewer wanted) systematically.

The idea is correct. But the only trick you can use is to set up a variable c, and your strategy is that if you roll the die, and if it is smaller or equal than c, you will drop it and roll again, otherwise, you will take the amount of money. Then you will get the equality that :

E=(c+101)/2 * (100-c)/100 +c/100 * (E-1)

Solving this equation, you can get E=101.5-[ (100-c)/2 + 100/(100-c) ]. Now E is a function depending on c. So you hope to set up c to maximize E. After calculate the derivative of E with respect to c, you can find out that E is maximized when c=86. Then E~ 87.4. Besides, according to the formula you provided, the expected value of the game should be 87.25, but not 87.5. So the maximum expected value should be 87.4.

 

[Saajan]

Keith, you need to take into account the fact that you can roll again.

If we let E be the expected value of the game, then the optimal strategy is to roll again if we roll any number less than E-1. The probability of rolling less than E-1 is approximately (E-1)/100 (need to round E down to an integer for this to be exact). If we roll greater than E-1, we stop and take the money. Our expectation, assuming we roll greater than E-1 is 0.5*(100+E-1) (again E needs to be rounded off to be exact). We have 1-(E-1)/100 probability of rolling a number greater than E-1.

Putting it all together then gives us that

E=0.01*(E-1)*(E-1) + 0.5*(100+E-1)*(1-0.01(E-1)) . Solving for E gives us E=86.85 (or E=115 which we can rule out as E needs to be between 0 and 100).

So this would give a strategy where you'd roll again any time you throw 86 or less. Given the rounding errors above, it's probably best to check if a strategy where you roll again if you throw less than 87 would be better, or a strategy where you roll again if you throw less than 85.

I agree except for how you got the first 0.01*(E-1)*(E-1) term in your formula. Assuming this is the term for if you dont roll again, surely we have
Expectation if you dont roll again = (1+E-1)/2 = E/2
P(dont roll again) = (E-1)/100

So it should be E=0.01*(E-1)*0.5*E + 0.5*(100+E-1)*(1-0.01(E-1))
I may be wrong, but can you explain how you got the formula?

 

[RRodriguez]

It seems like it is asking if you know how to think about perpetual American Options. Try to do an expiration of five rolls. Get some intuition and move forward. You will probably get a lower bound of 87.5 after doing some tricks.