1

Jamie is told there are 3 aces and 3 jacks in a pile. Each turn, a card is drawn without replacement; Jamie earns $1 if he guesses the drawn card correctly. Jamie plays 6 turns under the optimal strategy. How much money should Jamie expect to earn. I am having difficulty in approaching this problem. I can find out for the first round to be 0.5. Then onwards I am stuck.

Md Kaif Faiyaz
  • 320
  • 1
    The numbers are so small here...There are only $\binom 63=20$ possible orders. Just write it out if you can't think of anything else. – lulu Oct 06 '23 at 13:26
  • @lulu What if the numbers were big? Even if it was just $5$ Aces and $5$ Jacks, you couldn't brute force it. You'll have to do it recursively. – Devansh Agarwal Oct 07 '23 at 13:20
  • 1
    @DevanshAgarwal Sure, but the backwards induction model for larger numbers is easy and well documented. For a harder problem, see the Black and Red Card problem. This one is much easier since, as far as one can tell from the terse write up, there isn't even a stopping option, which is the source of all the difficulty in the general problem. – lulu Oct 07 '23 at 13:21
  • @lulu Thanks for the link to the problem. Do you happen to have a source for more problems related to the backwards induction approach? – Devansh Agarwal Oct 07 '23 at 13:39
  • 1
    @DevanshAgarwal I first got experience with backwards induction methods through finance, specifically the pricing of American options. ("American" just means that, as in the Red and Black card problem, you can exercise your option whenever you feel like, as opposed to a "European" option which can only be exercised at a specified moment in time). See This for an introduction. Searching for "pricing of American options" will generate lots of references. – lulu Oct 07 '23 at 13:47
  • 1
    @DevanshAgarwal Another sort of problem, best solved by backwards induction, is the World Series Problem. That problem supposes that you want to bet on, say, the winner of a $7$ game series, but the market only allows you to place bets on individual games. How can you structure your bets to perfectly replicate a single bet on the entire series? – lulu Oct 07 '23 at 13:49

2 Answers2

1

Define $f(a,b)$ to be the expected amount of additional money gained when the deck currently contains $a$ aces and $b$ jacks.

$f(0,0)=0,~f(1,0)=1,~f(0,1)=1$ should be obvious. $f(a,b)=f(b,a)$ should also be obvious, as should the strategy of always guessing that the next card is the one which there is more of remaining (doesn't matter if ace or jack if equal amount, so go ahead and always guess ace in those cases)

We have that when $a\geq 1$ that $f(a,0)=a$, since at that point we know the exact contents remaining in the deck and so can say with certainty for each subsequent draw that the card will be an ace. Similarly $f(0,b)=b$.

Lastly, we can note that when $a\geq b\geq 1$ we have that $f(a,b) = \underbrace{\frac{a}{a+b}\left(1+f(a-1,b)\right)}_{\text{guessed right}} + \underbrace{\frac{b}{a+b}\left(0+f(a,b-1)\right)}_{\text{guessed wrong}}$. The other case of when $b>a\geq 1$ is covered by $f(a,b)=f(b,a)$

We have all information we need now to work backwards to find $f(3,3)$

$f(0,0) = 0$

$f(1,0)=1,~~f(0,1)=1$

$f(2,0)=2,~~f(1,1)=1.5,~~f(0,2)=2$

$f(3,0)=3,~~f(2,1)=\frac{7}{3},~~f(1,2)=\frac{7}{3},~~f(0,3)=3$

$f(3,1)=3.25,~~f(2,2)=\frac{17}{6},~~f(1,3)=3.25$

$f(3,2)=3.6,~~f(2,3)=3.6$

$f(3,3)=4.1$

In more detail for example, $f(3,1) = \frac{3}{3+1}(1+f(2,1))+\frac{1}{3+1}(1+f(3,0)) = \frac{3}{4}\cdot (1+\frac{7}{3})+\frac{1}{4}\cdot (0+3) = 3.25$

JMoravitz
  • 79,518
  • Hi, my approach was quite similar. Instead of a bottom up, I used a top down approach. My follow up is: Can you get a general equation having parameters just a and b for E[a Aces and b Jacks]? The problem is, what if there were say 20 Aces and 11 Jacks? How would we go about it then? – Devansh Agarwal Oct 07 '23 at 17:12
1

The concept of symmetry is extremely useful in this problem. For example, the expected earning in the case where $1$ ace and $2$ jacks are left is the same as the expected earning in the case where $2$ aces and $1$ jack are left. i.e. $E[1A, 2J] = E[2A, 1J]$

We can simplify any subproblem by ignoring As and Js. Let $x$ be the number of cards of type $1$ (either As or Js) and let $y$ be the number of cards of the type $2$ (Js if x is As or vice versa).

Hence, we want $E[nxmy]$, where there are n cards of type x and m cards of type y. In your problem, you require $E[3x3y]$. It is easy to define any subproblem recursively. $$E [3x3y] = \frac12 + E[2x3y]$$ $$=> E[2x3y] = \frac35 \cdot \left( 1 + E[2x2y] \right) + \frac25 \cdot E[1x3y]$$ $$=> E[2x2y] = \frac12 \cdot (1 + E[1x2y]) \quad and \quad E[1x3y] = \frac3 4 \cdot(1+E[1x2y]) + \frac14 \cdot E[0x3y] $$ $$=> E[1x2y] = \frac23 \cdot(1 + E[1x1y]) + \frac13 \cdot E[0x2y] \quad$$ Now, the smaller subproblems are pretty obvious: $E[1x1y] = \frac 32, E[0x2y] = 2, E[0x3y] = 3$

Keep substituting back to get $E[3x3y] = \frac{41}{10} = 4.1$

Devansh Agarwal
  • 335