In the problem Optimal Card Drawing Strategy
, an optimal strategy was determined for a card game.
Give a closed expression for the expected score when using the optimal strategy.
Well, as I said in my solution to the prior problem, I have doubts that a closed expression for the value of the game exists. But I was wrong about the previous problem, so maybe I'm wrong here too.
Working backwards from the last round, and using notation from the last problem:
IF YOUR HIGH CARD GOING INTO THE LAST ROUND IS H, then the strategy is to draw if H <C/2, and just count your high card otherwise.
Incremental gain in the last round =
if H < C/2, then C/2
if H >= C/2, then H
Or (don't know if it will be helpful), greater(H, C/2)
What about if there are two rounds remaining?
Well, we will only draw if
2>= H(H+1)/((C-H+1)*(C-H)) (see previous solution)
And already I'm having trouble figuring it out.
Let's pick a specific case which demonstrates my problem.
C = 19, 3 rounds
At last round, strategy is to draw if high card = 9 or less. Expected value of last round, based on high card, is
average of the above values = 12
At next to last round, strategy is to draw if H card = 11 or less.
If H is between 0 and 9, then the expected value of the last two rounds = C/2 (random card this round) + 12 = 21.5.
If H is between 12 and 19, then we will not be drawing, and the value of the last two rounds = 2H.
But if H = 10 or 11 going in to last to next round, then things are complicated. The expected value is not 21.5. If H = 10 and we draw anything lower than a 10, then the value of the last round is 10, not 9.5. So, expected value of last two rounds =
9.5 + .05*(11*10 + 11 + 12 + ...+19) = 21.75
Similarly, if H = 11 and we draw anything lower than a 11, then the value of the last round is 11, not 9.5 or 10. So, expected value of last two rounds =
9.5 + .05*(12*11 + 12 + ...+19) = 22.3
Expected value of last two rounds, based on high card going into the next to last round, is
average of the above values = 25.2535
So, if the game is only three rounds long, then the first round is always a random draw, expected value = 9.5. Total value of the game = 9.5 + 25.3525 = 34.8525, when C = 19 and R = 3. (While it is always possible that I have made a mistake, I will test any proposed solution using this case.)
If the game is more than 3 rounds, then the situation with 3 rounds to go is even more complicated. While I can see how to calculated the game value easily enough for any given C and R, using a spreadsheet or computer program, I remain doubtful that there is a neat closed expression that doesn't involve multiple minimums and summations.
Over to you, Daniel
Edited on October 3, 2010, 1:44 am