A small deck of cards has cards of three types, Reshuffle, One and Zero.
- Drawing a Reshuffle card scores 0. Then all drawn cards are replaced back into the deck, and the deck is shuffled.
- Drawing a One card scores 1 point. Drawn One cards are retained in hand until the next Reshuffle is drawn.
- Drawing a Zero card scores 0. Drawn Zero cards are retained in hand until the next Reshuffle is drawn.
Questions:
- A. The deck contains 1 One and 2 Reshuffle cards. Draw 100 times. What is the expected score? (25, scoring 1 per 4 draws from 3 cards)
- B. The deck contains 1 One, 10 Zero and 2 Reshuffle cards. Draw 100 times. What is the expected score? (7.1, i.e scoring 1 per 14 draws from 13 cards)
- C. The deck contains i One, j Zero and k Reshuffle cards. What's the formula for the expected score? (No idea)
I've run a Monte-Carlo simulation of this, and am reasonably sure of the answers to A and B. My maths isn't up to rigorously defining C.
This is a representation of the attack deck in the board game Gloomhaven. The deck always contains two cards which cause a reshuffle, plus some variable number of other cards. The Monte-Carlo simulation was intended to work out how often a particular single special card would be drawn, here represented by the One. I found the conclusion was interesting and surprising. I'm asking here to confirm that result.
I can see that the answer to A (1 in 4 draws are the One, total average score for 100 thus being 25) comes from there being four different draw possibilities – the obvious initial three, and the fourth when the One is already in hand and the next draw must be an unscoring reshuffle. But I don't know how to represent or derive that, and I would like an answer to C that I can grasp as a none-mathematician.
Best Answer
You don't specify an initial state. From your result for $A$, I infer that you're interested in the expected score in equilibrium (which is $\frac14$ per draw in $A$), not starting from a full deck (which would be slightly different).
In the general case, in a shuffled deck the $i+j$ non-reshuffle cards are equidistributed over the $k+1$ intervals formed by the $k$ reshuffle cards. Thus, on average we draw $\frac{i+j}{k+1}$ non-reshuffle cards before drawing a reshuffle card, and the expected score from these is $\frac i{k+1}$. Thus the expected score per draw is
$$ \frac{\frac i{k+1}}{\frac{i+j}{k+1}+1}=\frac i{i+j+k+1} $$
(where $+1$ counts the reshuffle card). In your two specific cases, this yields
$$ \frac1{1+0+2+1}=\frac14 $$
and
$$ \frac1{1+10+2+1}=\frac1{14}\;, $$
respectively.
Note that interestingly it doesn't matter how many of the non-scoring cards are zeros or reshuffles. As long as there's at least one reshuffle card, the expected score per draw is simply $\frac i{n+1}$, where $n$ is the total number of cards, compared to $\frac in$ if you loop through a deck without reshuffle cards.
Edit in response to a comment:
The ratio $\frac{\frac i{k+1}}{\frac{i+j}{k+1}+1}$ comes about as follows: Each time we draw from a full, shuffled deck up to and including a reshuffle card, the expected score is $\frac i{k+1}$ and the expected number of draws is $\frac{i+j}{k+1}+1$. For one such run, the expectation of the score per draw is hard to determine; it isn't simply the ratio of the two expectations. For instance, in your first example, we score $0/1$ with probability $\frac23$ and $1/2$ with probability $\frac13$, so the expectation of the score per draw is $\frac23\cdot0+\frac13\cdot\frac12=\frac16\ne\frac14$. However, if we perform a very large number $m$ of such runs, the number of draws will be close to $m$ times the expected number of draws per run, and the score will be close to $m$ times the expected score per run, so for all the runs together, the expectation of the score per draw is simply the ratio between the expected score per run and the expected number of draws per run.