A card game with no decisions

A friend showed me a mindless card game he plays, in which the initial state of the deck completely determines whether he wins or loses. The game is played as follows:

1. Shuffle a standard $52$ card deck
2. Lay the top $8$ cards face up
3. If any two cards show the same value, lay on top of them the top two cards from the remaining deck, face up.
4. Repeat step $3$ until no two cards showing have the same value, in which case you lose, or until all cards have been played, in which case you win.

What is the probability of a win? Just as a simple observation, if there are no pairs in the first $8$ cards, the game is lost immediately after step $2$.

Of course, we could generalize by varying the number of total cards, the number of different possible values, and the number of cards with a particular value. We could also change the number of cards we are allowed to lay face up to begin with, and as noted in the comments, we could require that all cards of the same value be covered up at step $3$, and not just pairs.

-
What if three or more cards visible have the same value? It seems most reasonable to cover all of them. –  A Walker May 9 '13 at 5:56
@AWalker: We are only allowed to cover cards in pairs. Although your variant would be interesting to study as well. –  Jared May 9 '13 at 5:57
Just started to work this out and then ran into this issue as well. I think keeping track of the possibility of multiple matches and 3-4 of a kind will make this a bit tougher. –  CommonerG May 9 '13 at 6:03
Define $N(x)$ to be the number of disjoint pairs in the top $x$ cards. (Note that this is well-defined: three-of-a-kind contains a single pair, and four-of-a-kind contains two pairs.) You lose immediately unless $N(8)>0$. If it is, you reveal two more cards and remove a pair. You then lose unless $N(10)>1$. And so on; in general, a shuffled deck is "winning" if $N(8+2x)>x$ for all $x < 22$. –  mjqxxxx May 9 '13 at 22:26

The game is trivially equivalent to take the 52 cards from the deck, one (or two) at a time, and group the same valued cards in respective 13 piles. You loose if at some moment you have 8 or more piles with an odd number of cards.

My simulation ($5 \times 10^7$ tries) gave me a winning probability estimate of $p=0.054207$ and the amount of cards taken from the deck (minimum=8, maximum=52=win) has the following distribution. Most of the time, we loose in the first trials, as noted in the other answer.

Update: a computer calcutation (not a simulation; exact, and quick, though not elegant ) gives me: $$p=\frac{23655404966027488102313337962261}{436763610067824320055367170703125}=0.0541606590401477$$

I just consider a 5-elements "state" (number of values that have appeared k-times) and compute iteratively the probabilities transitions (1806 valid states). Java runnable code, in case you are interested (with floating point instead of exact fractions, for clarity), here.

Edited: Let $t \in 0 \dots 52$ be the "time" (iteration) of the game, equal (in my formulation above) to the total number of drawn cards. Let ${\bf n}(t)$ be a 5-dimensional state vector such that $n_k(t)\in 0 \dots 13$ (with $k \in 0 \dots 4$) counts how many values (card ranks) have appeared $k$ times, after having drawn $t$ cards. It follows that

$$\sum_{k=0}^4 n_k(t)=13$$

$$\sum_{k=0}^4 k \, n_k(t)=t$$

(BTW, the total set of states, correspond to the weak-compositions of 13 in 5 parts. And the state value determines univocally the time $t$, through the second equation).

The legal state transitions correspond to selecting a index value $j\in 0\cdots 3$, decrementing that index value and incrementing the next one: $n_j(t+1)=n_j(t)-1$, $n_{j+1}(t+1)=n_{j+1}(t)+1$, with the restriction $n_j(t) >0$. Each transition probability can be computed as

$$p_j = \frac{n_j(t) \, (4-j)}{52-t}$$

Further, the additional game rule corresponds to having less than $M=8$ odd valued numbers, i.e. $n_1(t) + n_3(t) < 8$

Then, given the probability of all legal states at time $t$, we can compute the probability of all legal states at time $t+1$. And the probability of reaching ("legally", without losing the game) state $t$ is the sum of those probabilities. This is just what my program computes.

An example. This states corresponds to 28 cards already played, 3 values (12 cards) not having yet appeared, 5 values have appeared twice (10 cards), 2 values have appeared three times).

k  n  nk    p
----------------
0  3   0  12/24
1  0   0   0/24
2  5  10  10/24
3  2   6   2/24
4  3  12   0/24
----------------
13  28    1

-
I'm not sure I understand your update. Are you saying this horrible fraction is an exact answer? If so, can you be a little more clear about how you found it? I'm not a programmer. –  Jared May 13 '13 at 4:08
Yes, that's an exact answer, unless I've messed up something. I've added more detail. –  leonbloy May 13 '13 at 15:02

Let's set some variables:

PairChoices = Select[Subsets[Range[8], {2}], #[[1]] < #[[2]] &];


(This is a list of all possible (ordered) subsets of $\{1,\ldots,8\}$ of size two. We'll use it to scan for pairs.)

What follows is the bulk of our code. It iterates a while loop until we win or lose, then prints the number of cards remaining in the deck:

Deck = RandomSample[Flatten@ Table[Range[13], {i, 1, 4}], 52];
Hand = Take[Deck, 8]; Deck = Drop[Deck, 8];
While[Length[Union[Hand]] < 8 && Length[Deck] > 1,
Paired = First[Select[PairChoices, Hand[[#[[1]]]] == Hand[[#[[2]]]] &]];
Hand = Join[Drop[Drop[Hand, {Paired[[2]]}], {Paired[[1]]}],Take[Deck, 2]];
Deck = Drop[Deck, 2]];
Print[{Length[Deck], Hand}]


This outputs $0$ if and only if we've won; in general, it outputs the number of cards left in the deck when the game ends. It's not hard to turn this into a function, mapping decks to the number of cards left when the game ends. Then we can run this function as many times as we like. What follows is a histogram of this data, for 100000 games:

Notice that it appears to be impossible to come close to winning without actually winning. After running this game 250000 times, I've had a win-percentage of $0.053816$, i.e. a win about every 18 or 19 games. I'll run more games; hopefully a statistician will be able to say when the result is significant.

-
This is very nice. Thanks! I am hoping to find an exact answer, so I won't accept for now, but I will later if nobody else posts anything constructive. Thanks again! –  Jared May 9 '13 at 16:01
This is fine, of course. Perhaps with more simulation a candidate probability will appear (which, after all, must be rational with denominator dividing the number of distinct games modulo symmetries). –  A Walker May 9 '13 at 17:00
You won't get enough accuracy to distinguish $\frac n{52!}$ from $\frac {n+1}{52!}$. The SD is now $\sqrt{250,000\cdot 0.053816 \cdot (1-0.053816)}\approx 113$ so your win percentage is about $\pm 0.00045$ –  Ross Millikan May 9 '13 at 17:06
At worst, you'd have have to distinguish rational numbers with denominator $44!/(13!/(24^{13}) \approx 10^{26}$ (I believe). This is because a game is determined by the $44$ cards in the deck at start, and independent of color and permutations of the numerals. This doesn't even take into account the fact that the symmetry introduced by the fact that we draw cards in pairs. –  A Walker May 9 '13 at 17:38
For random simulation, you would have to do about the square of that many trials to get that accuracy. Easier to do them all, but that is still out of reach. Your result is already significant (with the stated error). I suspect we won't do better unless somebody can get the exact number somehow. –  Ross Millikan May 10 '13 at 14:54