All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Optimal Card Drawing Strategy 2 (Posted on 2010-10-02)
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.

 No Solution Yet Submitted by Daniel No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 I have my doubts ... | Comment 1 of 5
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
 Posted by Steve Herman on 2010-10-03 01:21:28

 Search: Search body:
Forums (0)