A card game with no decisions

Question

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.

Answer 1

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

Answer 2

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.