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

H Value

-- -------

0-9 9.5

10 10

11 11

12 12

13 13

14 14

15 15

16 16

17 17

18 18

19 19

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

H Value

-- -------

0-9 21.5

10 21.75

11 22.3

12 24

13 26

14 28

15 30

16 32

17 34

18 36

19 38

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**