You play the following game. Eleven closed boxes are put in random order in front of you. The boxes $1,\ldots, 10$ contain $a_1,\ldots, a_{10}$ dollars, but box 11 contains a devil's penny. You may open as many boxes as you wish, but they must be opened one by one. You can keep the money from the boxes you have opened as long as you have not opened the box with the devil's penny. Once you open this box, the game is over and you lose all the money gathered so far. What is a good stopping rule?

I can't read well your mail.Do you know the distribution of the money inside good boxes?

The amounts a_1, ... ,a_10 are given amounts. As an example a_i=i as in: A game is played with eleven cards: an ace, two, three, $\ldots$, nine, ten, and a joker. These cards are thoroughly shuffled and laid face down. You can flip over as many cards as you wish, but they must be flipped over one by one. Once you flip over the joker card, the game is over and you lose all the money gathered so far. If you stop before the joker card is flipped over, you win as many dollars as the sum of the values of the cards you have flipped over.

OKCall S the sum of the box value S=55 in your case and N the number of boxes (N=11)If you have collected s by opening n boxes, open another box will give you:* (S-s)/(N-n-1) with a probability (N-n-1)/(N-n)* -s with a probability 1/(N-n) So you continue if (S-s)/(N-n)>s/(N-n) -> s<S/2It doesn't depend on N and n.

Why twice?If it's egal, you can continue.In one case, you lose, in the other case, you double.

QuoteOriginally posted by: Vanubis1OKCall S the sum of the box value S=55 in your case and N the number of boxes (N=11)If you have collected s by opening n boxes, open another box will give you:* (S-s)/(N-n-1) with a probability (N-n-1)/(N-n)* -s with a probability 1/(N-n) So you continue if (S-s)/(N-n)>s/(N-n) -> s<S/2It doesn't depend on N and n.Is this right? The upside seems underestimated, because you also get a chance to keep playing and win more.

I understand what you mean.It's underestimated if you want to price the expected value but not to know when you have to stop.It's because gain-loss is a decreasing function of number of rounds.So if it's positive, you continue and don't care to underestimate.If it's negative, playing more rounds after will decrease the value so it's negative again.

OK, I get the same answer, but just wanted to provide more rigorous reasoning.If s < S/2 after opening n boxes, then the expected gain for (n+1)th box is (S - s) / (N - n) - s / (N - n) = (S - 2s) / (N - n), which is already positive. So one must continue regardless of the option to keep playing after (n+1)th box.This, however, doesn't necessarily imply that one must stop if s > S/2. To show that, use induction.Conjecture: If s > S/2, one must stop.The conjecture is trivially true when there is only one box left.The conjecture is also true when there are two boxes left, because the expected gain is (S - s) / 2 - s / 2 = (S - 2s) / 2 < 0.Now assume the conjecture is true when k boxes are left.When k+1 boxes are left, the expected gain for the next box is (S - s) / (k + 1) - s / (k + 1) = (S - 2s) / (k + 1) < 0. Therefore one must stop, and the conjecture is true. (Notice there is no need to consider the option to keep playing because if s is larger than S/2 with k+1 boxes left, s will be automatically larger than S/2 with k boxes left.)Conclusion: one must continue if s < S/2 and stop if s > S/2. (I find it somewhat surprising that this is the same answer you get without considering the option to keep playing.)

QuoteOriginally posted by: ymousOK, I get the same answer, but just wanted to provide more rigorous reasoning.If s < S/2 after opening n boxes, then the expected gain for (n+1)th box is (S - s) / (N - n) - s / (N - n) = (S - 2s) / (N - n), which is already positive. So one must continue regardless of the option to keep playing after (n+1)th box.This, however, doesn't necessarily imply that one must stop if s > S/2. To show that, use induction.Conjecture: If s > S/2, one must stop.The conjecture is trivially true when there is only one box left.The conjecture is also true when there are two boxes left, because the expected gain is (S - s) / 2 - s / 2 = (S - 2s) / 2 < 0.Now assume the conjecture is true when k boxes are left.When k+1 boxes are left, the expected gain for the next box is (S - s) / (k + 1) - s / (k + 1) = (S - 2s) / (k + 1) < 0. Therefore one must stop, and the conjecture is true. (Notice there is no need to consider the option to keep playing because if s is larger than S/2 with k+1 boxes left, s will be automatically larger than S/2 with k boxes left.)Conclusion: one must continue if s < S/2 and stop if s > S/2. (I find it somewhat surprising that this is the same answer you get without considering the option to keep playing.)For any time t where t <= this stopping time - the process is a sub-martingale, after the stopping time its a super-martingale. I think theres a theorem you can use which verifies this as the optimal stopping time otherwise some elementary probability will show that this strategies expected return dominates any other (potentially random) strategy.

An interesting discussion on the problem and a variant of the problem can be found inhttp://wordplay.blogs.nytimes.com/2014/03/03/devil/?_php=true&_type=blogs&_php=true&_type=blogs&_php=true&_type=blogs&_r=2