Card matching game

Question

The game setup is as follows: there is a bag with 6 matching pairs of cards (two 1s, two 2s, two 3s, two 4s, two 5s, two 6s).

We randomly draw one card at a time, but put matching cards aside as soon as they appear in our hand. The game ends and we lose if we ever hold three cards, no two of which match. What is the probability of winning?

My Approach

Let $State_x$ be the state where we have $x$ cards in our hand and $n$ be the number of remaining cards in the deck.

After some thought I realized that in the 'winning' scenario we will always come back to the state where we have 1 card in our hand.

So for every possible $n$, when we are at $State_1$ (this will only happen when $n$ is odd), I calculated the probability of coming back to $State_1$:

• Either this way: $State_1 \to State_0 \to State_1$

  In this case the probability of coming back to $State_1$ is $\frac{1}{n}$

• Or this way: $State_1 \to State_2 \to State_1$

  In this case the probability of coming back to $State_1$ is $\frac{n-1}{n} \cdot \frac{2}{n-1} = \frac{2}{n}$

Generalizing, for any $n \ge 3$, the probability of coming back to $State_1$ is $\frac{1}{n} + \frac{2}{n} = \frac{3}{n}$

To win, one would need to go through all odd values of $n$ starting from 11 till 3.

Let $C$ be the event of coming back to $State_1$, then

$P(C|n=11) = \frac{3}{11}$

$P(C|n=9) = \frac{3}{9}$

$P(C|n=7) = \frac{3}{7}$

$P(C|n=5) = \frac{3}{5}$

$P(C|n=3) = \frac{3}{3}$

$P( Winning ) =P(C|n=11) \cap P(C|n=9) \cap P(C|n=7) \cap P(C|n=5) \cap P(C|n=3) = \frac{9}{385} $

Am I right in my approach?

Answer 1

Consider a generalization of this game: instead of $6$ pairs in the deck, there are $N$ pairs. As we play, every time we get a pair in our hand, we reduce to a smaller game where $N$ has decreased by $1$! With one small wrinkle: we may start this smaller game with a card already in our hand (e.g. our first 3 draws are $1, 2, 1$, yielding a new game where we start with a $2$ in our hand).

So, we should recursively compute the probability that we win a game with $N$ pairs and $k \in \{0,1\}$ cards already in our hand. However, we can note that having a card already in your hand does not change your probability of winning whatsoever -- if you start with no cards in your hand, the first thing you do is draw a card, and the card you draw doesn't affect your odds of winning in any way. So we really just need to recursively compute the probability that we win a game with $N$ pairs and no cards in our hand. Let's do it!

---

If $N = 1$, the probability that we win is $\boxed{1}$.

If $N = 2$, the probability that we win is $\boxed{1}$.

If $N = 3$, we lose iff we draw $3$ distinct cards in a row. The probability of this occurring is $$\frac{4}{5} \cdot \frac{2}{4} = \frac{2}{5},$$ so the probability that we win is $\boxed{\frac{3}{5}}$.

If $N = 4$, we lose "immediately" if we draw $3$ distinct cards in a row; the probability of this occurring is $$\frac{6}{7} \cdot \frac{4}{6} = \frac{4}{7}.$$ So, the probability that we don't lose "immediately" is $\frac{3}{7}$. If we don't lose immediately, we now have to win a game with $N = 3$, and we will do this with probability $\frac{3}{5}$. Overall, the probability of winning a game with $N = 4$ is $\frac{3}{7} \cdot \frac{3}{5} = \boxed{\frac{9}{35}}$.

Etc!

Answer 2

We have a simple exercise with a concrete small number of pairs, so i will go to solve it without generalization. Let us write down all states that may occur. Below it is a schematic picture, the states $0$, $1$, $2$ appear in different places, are not the same one at the many places, it depends on the "level" at which it is shown. The state "$*$" leads to losing the game. And it occurs also in different levels.

12     0 
         \
       1  \
           \
11           1
          /     \
    1/11 /       \ 10/11
        /         \                8/10
10    0             2 -------------------- (*) GAME OVER
        \         /
       1 \       / 2/10
          \     /
 9           1
          /     \
     1/9 /       \ 8/9
        /         \                 6/8
 8    0             2 -------------------- (*) GAME OVER
        \         /
       1 \       / 2/8
          \     /
 7           1
          /     \
     1/7 /       \ 6/7
        /         \                 4/6
 6    0             2 -------------------- (*) GAME OVER
        \         /
       1 \       / 2/6
          \     /
 5           1
          /     \
     1/5 /       \ 4/5
        /         \                 2/4
 4    0             2 -------------------- (*) GAME OVER
        \         /
       1 \       / 2/4
          \     /
 3           1 (and from here we can only WIN)
          /     \
     1/3 /       \ 2/3
        /         \              0 = 0/2
 2    0             2 -------------------- (*)

        \         /
       1 \       / 2/2 = 1
          \     /
 1           1
          / 
     1/1 /
        / 
 0    0 = WIN 

Because of the simple structure of the graph with the states, it is easy to write down the probability to reach the one or the other $(*)$ state. We will denote by $(*)_k$ the state $(*)$ in level $k\in\{10,8,6,4\}$. (In level $2$ we have probability zero to get there.) We also denote similarly by $0_k$, $1_k$, $2_k$ the corresponding states in a level $k$ between $12$ and $0$, if there is such a state in that level.

Let $p$ be the probability to win. Then as OP observed, we must go through $1_{11}$, $1_9$, $1_7$, $1_5$, $1_3$, (and $1_1$,) to win the game. In fact, reaching $1_3$ wins the game. So $$ \begin{aligned} p &= \left( \frac {1}{11} \cdot1 + \frac {10}{11} \cdot\frac 2{10} \right) \left( \frac 19 \cdot1 + \frac 89 \cdot\frac 28 \right) \left( \frac 17 \cdot1 + \frac 67 \cdot\frac 26 \right) \left( \frac 15 \cdot1 + \frac 45 \cdot\frac 24 \right) \left( \frac 13 \cdot1 + \frac 23 \cdot\frac 22 \right) \\ &= \left( \frac {1}{11} + \frac 2{11} \right) \left( \frac 19 + \frac 29 \right) \left( \frac 17 + \frac 27 \right) \left( \frac 15 + \frac 25 \right) \left( \frac 13 + \frac 23 \right) \\ &= \frac 3{11}\cdot \frac 39\cdot \frac 37\cdot \frac 35\cdot \frac 33 \\ &=\frac {3^5}{3\cdot5\cdot7\cdot9\cdot 11} =\frac {3^2}{5\cdot7\cdot 11} =\frac 9{385}\ . \end{aligned} $$ $\square$

---

This is exactly the OP idea and the OP computation and the OP result. (It is of course now easy to generalize to more pairs, but not so easy when the $3$ cards of different values are replaced by more.)

---

Computer aided solution / check, here using sage. (This is not so easy to implement, as to get the solution, from my point of view. But from other point of view... It is also a nice modeling and programming task.) Let $1,1',2,2',3,3',4,4',5,5',6,6'$ be the cards in the bag. We model first by using the probability space of all permutations of the $12$ cards, each one having the same probability. This space has $12!$ elements, too big for the computer. But we observe that the group $G$ with $2^6$ elements generates by the transpositions $(k,k')$ acts on these permutations, an maps winning to winning permutation, losing to losing ones. So we may "factor" / identify permutations that can be brought in each other by the action of this group. This means, we can drop the prime, and use as a set of cards $1,1,2,2,3,3,4,4,5,5,6,6$. (As we may have done from the start.) This "list" (of identified permutations) has $12!/2^6$ elements, still too big. But we observe, that the group of permutations of $\{1,2,3,4,5,6\}$ acting on the "list" elements in a natural manner also preserves losing and winning. So we may and do assume, that the cards show up in this order. So there is a first $1$. Then the next card which is not $1$ can be and is assumed to be a $2$. Then the next card which is not $1,2$ can be and is assumed to be a $3$. And so on. We obtain $12!/(2^6\cdot 6!)$ elements. And this should be simple for the computer to cover in some seconds. But not so simple to implement. Let's see. We start with $123456$, written as a word, implemented as a list. We insert an $1$ after the first $1$, getting the words $1123456$, $1213456$, $1231456$, $1234156$, $1234516$, $1234561$. This is a new list, now we insert a $2$ after the place where we already have this entry, and so on. We get a new list of words. And do the same with $3,4,5,6$. At the end we have our $12!/(2^6\cdot 6!)=10395$ elements. We implement a check routine. And count the winning probability.

R = [1, 2, 3, 4, 5, 6]
L = [R]
for k in R:
    LL = []
    for lis in L:
        # find the position of k in this lis
        # then generate all possible lisk obtained by inserting k
        # after the k present in the lis
        ind = lis.index(k)
        for pos in range(ind + 1, len(lis) + 1):
            lisk = lis[:pos] + [k] + lis[pos:]
            LL.append(lisk)
    L = LL[:]

print(f"Collected {len(L)} events...")

def wins(lis):
    for k in [3, 4, 5, 6]:
        # truncate lis at first k, including it
        lisk = lis[:lis.index(k) + 1]
        odds = [j for j in lisk if lisk.count(j) == 1]
        if len(odds) > 2:
            return False
    return True

WINS = [lis for lis in L if wins(lis)]
print(f"There are {len(WINS)} winning events.")
print(f"The WIN probability is {len(WINS)} / {len(L)}"
      f" = {ZZ(len(WINS)) / ZZ(len(L))} ."
      f" ~ {len(WINS) / len(L)} .")

And we get the confirmation:

Collected 10395 events...
There are 243 winning events.
The WIN probability is 243 / 10395 = 9/385 . ~ 0.023376623376623377 .