1
$\begingroup$

Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red card drawn, we get 1 dollar and lose 1 dollar for every black card drawn. The problem consists in finding an algorithm which returns the expected value of the game. If we denote by $b$ and $r$, respectively, the number of black and red cards left in the deck at any time, the expected value of the game $E(b,r)$ satisfies:

$$E(b,r)=\max\left\{b-r,\frac{b}{b+r}\,E(b-1,r)+\frac{r}{b+r}\,E(b,r-1)\right\}\,,$$

with boundary conditions $E(0,r)=0$ and $E(b,0)=b$. The expected value of the game is therefore given by $E(26,26)$.

My question is, if we implement the recursive algorithm associated with the above formula, how can we determine its complexity? Using the trivial cases of $E(1,1)$ and $E(2,2)$, it would appear that we are dealing with exponential complexity, but is there a way to prove this properly, and if so, what is the number of necessary operations to compute $E(n,n)$ for an arbitrarily large integer $n$? Any ideas or references to literature would be greatly appreciated.

$\endgroup$
  • $\begingroup$ Is "For every red ... black card drawn." when the red card is drawn or when we ask him to stop? ​ ​ $\endgroup$ – user12859 Feb 4 '16 at 5:43
  • 3
    $\begingroup$ Hint: use memoization. $\endgroup$ – Raphael Feb 4 '16 at 7:48
  • 1
    $\begingroup$ Your recurrence is wrong. Even your boundary conditions are wrong (switch black and red). Start with fixing your recurrence. $\endgroup$ – Yuval Filmus Feb 4 '16 at 8:27
  • $\begingroup$ The answer I get is 41984711742427/15997372030584. $\endgroup$ – Yuval Filmus Feb 4 '16 at 8:28
  • $\begingroup$ @G.Bach When there's only black left you want to stop, so $E(b,0) = 0$. When there's only red left you want to take all of them, so $E(0,r) = r$. I am measuring payoff; what are you measuring? $\endgroup$ – Yuval Filmus Feb 4 '16 at 9:15
2
$\begingroup$

As pointed out in the comments, your recurrence is wrong (though equivalent for $b=r$; it's a recurrence for $E(b,r)+b-r$). Also, you can solve this efficiently using memoization or its more principled cousin, dynamic programming. The dynamic programming solution calculates iteratively $E(i,j)$ for $i+j=0,1,\ldots,52$.

Finally, to answer your question, if you implement you original solution, you get a running time satisfying the recurrence $$ T(b,r) = C + T(b-1,r) + T(b,r-1), $$ with initial conditions $T(b,0) = O(1)$, $T(0,r) = O(1)$. If $T'(b,r) = T(b,r)-C$ then $$ T'(b,r) = T'(b-1,r) + T'(b,r-1), $$ a recurrence solved by $\alpha \binom{b+r}{r}$. Taking the initial conditions into account, we get that $$ T(b,r) = \Theta\left(\binom{b+r}{r}\right). $$ In particular, $$ T(n,n) = \Theta\left(\binom{2n}{n}\right) = \Theta\left(\frac{4^n}{\sqrt{n}}\right). $$ (This assumes all arithmetic is $O(1)$. The running time is actually somewhat larger since the relevant numbers grow fast, but this is a (multiplicative) lower-order factor.)

$\endgroup$
  • $\begingroup$ My recurrence and boundary conditions are perfectly correct. If there are no black cards left, it means we've already turned every black card. So the best we can do is turn over every red card to get our expected payoff to 0. If there are no red cards left, there are no remaining cards which can improve our score, which is equal to the number of outstanding black cards. $\endgroup$ – user223935 Feb 4 '16 at 14:01
  • $\begingroup$ @user223935 I made the same thinko, but that's not how to go about this. $E(b,r)$ is independent of the values $E(b+c, r+d)$ for any $c,d>0$, or in words: the expected payoff for the remaining(!) game doesn't change, whether you already played a couple of rounds before it or not. At every step, you just optimize the expected payoff of the remaining game, not the overall game. That's why Yuval correctly says $E(0,r) = r$ and $E(b,0) = 0$ in a comment to your question. $\endgroup$ – G. Bach Feb 4 '16 at 14:49
  • $\begingroup$ @G.Bach With my boundary conditions and recurrence I find a value of 2.62 for E(26,26), which is perfectly consistent with known results about this game (see for example datagenetics.com/blog/october42014/index.html) $\endgroup$ – user223935 Feb 4 '16 at 15:00
  • $\begingroup$ @G.Bach Also in the reference I mention, you just have to switch the red/black convention $\endgroup$ – user223935 Feb 4 '16 at 15:01
  • 1
    $\begingroup$ @YuvalFilmus Having a second look, $E(b,r) + b - r$ is right. $\endgroup$ – G. Bach Feb 4 '16 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.