Probability – 100-Sided Die Probability

dicegamblingprobabilitypuzzle

The question is as follows: You are given a 100-sided die. After you roll once, you can choose to either get paid the dollar amount of that roll OR pay one dollar for one more roll. What is the expected value of the game? There is no limit on number of rolls.

The EV for a 100-sided die roll is 50.5, but the fact that you can pay a dollar for an extra roll complicates things. Not quite sure how to proceed.

Best Answer

If the expected value of this game is $a$, then at a die roll of $X$ you have the choice of either collecting $X$ or paying a dollar and restart, which gives you an expected value of $a-1$. To maximize the expected value, you should take $X$ if $X> a-1$ and start over if $X\le a-1$ (it does not really matter what we do when $X=a-1$). We obtain therefore $$ a = \frac1{100}\left(\lfloor a-1\rfloor\cdot a+\sum_{k=\lfloor a-1\rfloor+1}^{100}k\right) =\frac1{100}\left(\lfloor a-1\rfloor\cdot a+\frac{100\cdot101}{2}-\frac{\lfloor a-1\rfloor \cdot\lfloor a\rfloor}{2}\right). $$ I find numerically (didn't do much code checking, but the results are somewhat plausible) $$a\approx87.3571 $$ which seems to be exactly (and of course the true result must be rational) $$a=87\frac{5}{14}.$$ But I'm sure you can do the justification after the fact, i.e. show that the strategy that consists in continuing until you roll at least $87$ gives you $87\frac{5}{14}$ as expected value.

For your convenience, here is the PARI one-liner:

solve(a=1,100,sum(k=1,100,max(a-1,k))/100-a)


If an extra roll costs two dollars instead of one, the result would be $$a=82\frac12$$ instead, and with a cost of only $0.1$ dollars it would be $$a=96\frac1{10}.$$