You sit down with a well mixed deck containing A cards marked "+" and B cards marked "—". You may draw cards from this deck as long as you want, i.e., you can stop playing at any point. Each time you draw a + card you are given $1 and each time you draw a — card you have to pay $1. Cards are not replaced after having been drawn.

What would be a fair amount to pay for the right to play (i.e., what is the expected payoff) and under what circumstance should a player cease drawing?

(In reply to re: .. what went wrong .. by Steve Herman)

The recursion relation itself:

W(A,B) = [1 + W(A-1,B)]A/[A+B] + [-1 + W(A,B-1)]B/[A+B]

is not defined for (0,1), as W(-1,1) is not defined.

However, it does need to be modified to never have negative values:

W(A,B) = Max(0,  [1 + W(A-1,B)]A/[A+B] + [-1 + W(A,B-1)]B/[A+B])

The fault lies in the boundary conditions.  The boundary has to start at defining W(0,x) as 0 for all x, and W(y,0) = y for all y.

The major fault is arbitrarily not using the recurrence relation when the - cards exceed in number the + cards, rather than using the Max in the above redefinition. This is the same recurrence relation used by Leming, myself and Eigenray.

Applied to (2,3), the first place the official solution's arbitrary restriction yields a wrong answer, the continuance of the recurrence relation gives:

W(2,3) = [1 + W(1,3)]2/[2+3] + [-1 + W(2,2)]3/[2+3]

   = [1 + 0] * 2/5 + [-1 + (4/3)]*3/5

   = 2/5 + [1/3] * 3/5

   = 1/5

rather than the zero of arbitrarily giving that answer when B exceeds A. 

Posted by Charlie on 2008-03-25 11:36:53