Card game Puzzle

Question

---

You have a special deck with 11 cards, with 10 red cards and 1 joker. starting with $1 we play a game:

1. shuffle the deck
2. we can choose to draw the top card. if it's red, we double our money, but if it's the joker, our money is multiplied by 1/2048. the card we drew is then discarded.
3. repeat step 2 until you want to walk away: at any time, you can choose to stop drawing cards and take home however much you have.

a) how would you play this game? what's the minimum amount of money you are guaranteed to take home?

b) let's say you employ a strategy where you always draw n cards then stop. What value of n should you pick? how much money would you on average then have?

c) what strategy maximizes the expected value, and what is this value?

We now modify the game so that before drawing a card, you can bet any number between 0 and how much money you currently have. then, the bet is either doubled or multiplied by 1/2048 depending on whether you draw a red card or the joker.

d) does your strategy change? how should you now play, and what are the associated expectations?

e) what is the most amount of money you are guaranteed to win?

---

My approach:

Part a) If you ever draw a Joker, you continue to draw all the other cards. Hence minimum amount of money guaranteed is \$ 1/2 or 50 cents.

b) We will stop drawing after n cards when

$ E[n+1] <= E[n]:$ $$ \frac {10-n} {11-n} * 2^{n+1} <= \frac {10-n + 1} {11-n +1} * 2^{n} $$

This gives us $ n^2 -22n + 119 = 0 $ as our equation giving $ n <= 9.59 $

Hence we should stop after drawing 9 Red cards. However, if we get a Joker we obviously draw all cards then.

c) Assuming same strategy as above $$ E[x] = \frac {2}{11} * 2^9 + \frac {9} {11} * \frac {1} {2} = 93.5 $$

Not sure if this strategy is correct/optimal that maximizes EV.

Also no idea on the next part where we can bet any amount of the money we currently have

Answer 1

Let $S_0=1$ and $S_n$ denote a random variable modeling the cumulated winnings after the $n$-th card is revealed. Let $N$ denote the rank of the joker in the shuffled deck. Note that $N$ is a random variable.

The dynamic of the game is quite simple: $$S_1=2, S_2=2^2, \ldots, S_{N-1} = 2^{N-1}, S_{N} = \frac{2^{N-1}}{2^{11}},S_{N+1} = \frac{2^{N}}{2^{11}}\ldots, S_{11} = \frac 12.$$

We can find a good strategy via dynamic programming. We encode the current game state by $(r,j)$. The integer $r$ is the number of red cards left in the deck and $j$ is the number of joker ($j\in \{0,1\}$). Initially we are at the state $(10,1)$.

Let $W(r,j)$ denote the cumulated winnings for the state $(r,j)$. If you decide to stop at this state, by the dynamic your winnings are $$g(r,j) :=\begin{cases} 2^{10-r} &\text{if } j=1 \\ \frac{1}{2^{r+1}} &\text{if } j=0. \end{cases}$$ If you continue, your expected winnings are $\frac r{r+j} E[W(r-1,j)] + \frac j{r+j} E[W(r,j-1)]$.

Thus you continue playing iff $$g(r,j) < \frac r{r+j} E[W(r-1,j)] + \frac j{r+j} E[W(r,j-1)]$$ and $$E[W(r,j)] = \max\Big (g(r,j), \frac r{r+j} E[W(r-1,j)] + \frac j{r+j} E[W(r,j-1)] \Big).$$

Note the boundary condition $W(0,0) = \frac 12$. Consider the following Python implementation.

arr = np.zeros((11,2))
arr2 = np.zeros((11,2))

def g(r,j):
    if j == 1:
        return 2**(10-r)
    elif j == 0:
        return 2**(-1-r)
    
arr[0,0] = 1/2
arr[0,1] = 2**10
arr2[0,1] = 0
for r in range(1,11):
    for j in range(2):
        payoff_curr = g(r,j)
        if j == 0:
            payoff_next = r/(r+j) * arr[r-1,j]
        else:
            payoff_next = r/(r+j) * arr[r-1,j] + j/(r+j) * arr[r,j-1]
        arr[r,j] = max(payoff_curr, payoff_next)   
        arr2[r,j] = payoff_curr < payoff_next

It computes the following matrix of earnings arr, hence $E[W(10,1)] \approx 93.545454$, the exact value of which is most likely $\frac{1029}{11}$.

[[   0.5      1024.      ]
 [   0.5       512.25    ]
 [   0.5       341.666667]
 [   0.5       256.375   ]
 [   0.5       205.2     ]
 [   0.5       171.083333]
 [   0.5       146.714286]
 [   0.5       128.4375  ]
 [   0.5       114.222222]
 [   0.5       102.85    ]
 [   0.5        93.545455]]

The corresponding strategy is given by the matrix of moves arr2.

[[0. 0.]
 [1. 1.]
 [1. 1.]
 [1. 1.]
 [1. 1.]
 [1. 1.]
 [1. 1.]
 [1. 1.]
 [1. 1.]
 [1. 1.]
 [1. 1.]]

Answer 2

For the original game, let's suppose we have some amount $x\geq 1$, there is at least one card left, and we are considering whether to draw one more card or not.

• If all remaining cards are red, we clearly should take the next card.
• If the joker is the only card left, we clearly shouldn't take it.
• Otherwise there are $k\geq 2$ cards left, and one of them is the joker. So if we take exactly one more card, we expect to have $\frac{k-1}{k}\cdot 2x+\frac{1}{k}\cdot \frac x{2048}\geq x+\frac14$. So stopping now can never be the optimal strategy (for maximising expectation), since it is always better to take one more card and then stop.

Therefore the strategy is to always take the first $10$ cards, and take the last one unless it's known to be the joker. This has expectation $93.\overline{54}$, slightly better than your suggested strategy.

---

In the amended game, you can describe any plausible strategy as follows: in round $i$, if you have not yet seen the joker and currently have $x$, you bet $p_ix$, where $p_1,\ldots,p_{11}$ are fixed values; if you have seen the joker, you bet $x$. (Clearly the right strategy scales, so $p_i$ will be independent of what you currently have.)

Now suppose $0<p_i<1$. Then it is not hard to show that betting $p_ix$ has the same expected outcome as betting $x$ with probability $p_i$, and $0$ otherwise. And so it is clearly better to choose whichever of betting $x$ or betting $0$ gives the greater expectation (unless they are equal, in case it doesn't matter what you do). Thus there is an optimal strategy where $p_i\in\{0,1\}$ for each $i$.

Clearly $p_{11}=0$. Suppose $p_j=0$ for all $j>i$, and you are at round $i$ with $x$, not having seen the joker.

If you bet $0$, your possible payoffs are $2^0x,2^1x,\ldots 2^{11-i}x$, depending on the position of the joker, all equally likely. (If it's next, you get the maximum.)

If you bet $x$, you get $2^{11-i}x/2048=2^{-i}x$ if the joker comes next. Otherwise you double your winnings in all other cases. But your winnings in the other cases were $2^0x,\ldots,2^{10-i}x$, so they become $2^1x,\ldots,2^{11-i}x$.

Thus your possible outcomes in the two cases are almost exactly the same (although they come in a different order). The only real difference is that $2^0x$ (for $p_i=0$) has been replaced by $2^{-i}x$ (for $p_i=1$). Therefore, by backwards induction, the optimal choice is $p_i=0$ for all $i$.