In this game, you have an infinite deck of cards. Each time you draw a card it's value is a uniformly distributed integer on the interval [0,C].
The game lasts for R rounds.
You start the game by drawing a card and adding its value to your running total.
At each round you have two choices:
1) draw another card from the deck and add its value to your total
2) add the value of the highest card previously drawn to your total
What strategy, based on the constraints R and C, gives you the optimal total at
the end of the R rounds?
(In reply to
a hint by Daniel)
Well yes, that's a pretty good hint, and it does apply to this situation, and does simplify things.
If the high card is H and there are r rounds remaining after this one, then the expected gain (or loss) from stopping drawing on this round as opposed to stopping drawing on next round:
Expected gain/loss in this round + expected gain in future rounds = (C/2 - H) + r(expected increase in high card).
There is
probability (1/(C+1)) of increasing high card by 1
+ probability (1/(C+1)) of increasing high card by 2
+ ...
+ probability (1/(C+1)) of increasing high card by (C-H)
Expected increase in high card =
(1 + 2 + .... (C-H))/(C+1) =
(C-H+1)*(C-H)/2(C+1)=
So, the total expected gain / loss =
(C/2 - H) + r(C-H+1)*(C-H)/2(C+1)
We should draw if this expected gain/loss >= 0, and stop otherwise
Solving for r (number of rounds remaining AFTER THIS ONE), we should draw if
r >= (2H - C)(C+1)/((C-H+1)*(C-H))
Adding 1 and simplifying, we get the rule that we should draw if the number of rounds INCLUDING THE CURRENT ONE is >=
H(H+1)/((C-H+1)*(C-H))
If H <= C/2 then this expression is less <= 1. In other words, always draw if H <= C/2.
If H = C, this expression is infinite, and we should never draw.
If C = 3 and H = 2, draw if r (number of rounds remaining including this one) > (2)(3)/(2*1) = 3
In other words, as previously stated, when C = 3, the optimal action table is as follows:
H action
-- ------
< 2 draw
2 draw if 3 or more rounds remaining
3 don't draw
Let's look at a more interesting case
If C = 10 (applying the formula, and rounding fractions up)
H action
-- ------
< 6 draw
6 draw if 3 or more rounds remaining
7 draw if 5 or more rounds remaining
8 draw if 12 or more rounds remaining
9 draw if 45 or more rounds remaining
10 don't draw
So, I was wrong and there is a nice closed decision expression, although I still doubt that there is a nice closed expression for the value of the game.
Nice problem, Daniel, and thanks for the hint!
re: a hint
