I've been going through a problem solving book, and I'm a little stumped on the following question:
At each round, draw a number 1-100 out of a hat (and replace the number after you draw). You can play as many rounds as you want, and the last number you draw is the number of dollars you win, but each round costs an extra $1. What is a fair value to charge for entering this game?
One thought I had was to suppose I only have N rounds, instead of an unlimited number. (I'd then let N approach infinity.) Then my expected payoff at the Nth round is (Expected number I draw – N) = 50.5 – N. So if I draw a number d at the (N-1)th round, my current payoff would be d – (N-1), so I should redraw if d – (N-1) < 50.5 – N, i.e., if d < 49.5. So my expected payoff at the (N-1)th round is 49(50.5-N) + 1/100*[(50 – (N-1)) + (51 – (N-1)) + … + (100 – (N-1))] = 62.995 – N (if I did my calculations correctly), and so on.
The problem is that this gets messy, so I think I'm doing something wrong. Any hints/suggestions to the right approach?
Best Answer
Consider what happens in the first stage. You get a number out of the hat, and either stop or go on. And you do it in some "optimal" way (maximizes expectation). If you do go on, the rule that will ensure you the maximal expectation is the same rule you used before - your original optimal rule.
This shows that your stopping rule can be characterized by some threshold $X$, which is the minimal number for which you'd stop (alternatively we could have chosen $X-1$, which is the maximal number for which you'd go on). Denote the expected gain by $E$. We have $$ E = -1 + \frac{X-1}{100}E + \frac{\sum_{t=X}^{100} t}{100} = -1 + \frac{X-1}{100} + \frac{(100-X+1)(100+X)}{200}. $$ Multiplying by $200$ and rearranging, we get $$ 2(101-X)E = (101-X)(100+X) - 200. $$ Therefore $$ E = \frac{(101-X)(100+X) - 200}{2(101-X)}. $$ This is maximized by $101 - 10\sqrt{2} \approx 86.86$. Thus the best value for $X$ is either $86$ or $87$. These values give $E \approx 86.33$ and $E \approx 86.37$, so $X = 87$ is better, and the value of the game is $1209/14$.
My calculations don't agree with Ross's, so there's probably a mistake somewhere; this doesn't invalidate the method.