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.
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.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.
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!
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.
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.
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 :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.
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.