# Card draws from a deck with randomly reshuffles

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.

• The answer to $A$ is not always $\frac N4$, with $N$ draws. Clearly $E[1]=\frac 13$, for instance, and $E[2]=0\times \left(\frac 23 \right)^2+1\times \left (\frac 23\times\frac 13+\frac 13\times 1\right)=\frac 59$ After that there is a simple recursion...since you either start with $R$ or $1R$ we have $E[N]=\frac 23\times E[N-1]+\frac 13\times (1+E[N-2])$ A quick implementation of that gives me $E[100]=25.0625$ but I might have botched the code in my haste. – lulu Sep 11 '18 at 18:55

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.

• $\frac i{n+1}$ was my conclusion from the Monte-Carlo, though I'd have assumed the number of reshuffle cards affected that. It looks like the (n+1) just falls out from the numbers because there are sometime reshuffles and sometimes not, without any "meaning". It'd be (n) if you never reshuffled or always reshuffled, right? – Slow Dog Sep 12 '18 at 10:06
• Also, for clarity, could you please add an english explanation for that first equation $$\frac{\frac i{k+1}}{\frac{i+j}{k+1}+1}$$ – Slow Dog Sep 12 '18 at 10:10
• @SlowDog: About 'without any "meaning"': I do feel it's the sort of result that cries out for a combinatorial interpretation, where one adds another card to the deck and proves that this is somehow equivalent to your deck, but I haven't been able to come up with something like that yet. – joriki Sep 12 '18 at 10:13
• @SlowDog: About "because there are sometime reshuffles and sometimes not": I wouldn't put it that way. If the reshuffles were triggered by some external mechanism independent of the cards, the expected score per card would still be $\frac in$, not $\frac i{n+1}$. The reason for the slightly lower score is that the reshuffles are triggered by cards that don't contribute to the score; these cards get drawn more often than the other cards, because the other cards can't be drawn for a while after they're drawn, whereas the reshuffle cards can be drawn again right away. – joriki Sep 12 '18 at 10:29
• That's great, thanks. Your comment "the other cards can't be drawn for a while after they're drawn, whereas the reshuffle cards can be drawn again right away" is the key – Slow Dog Sep 12 '18 at 11:06