Card Games: Concentration

Let $E_{n,k}$ be the expected number of moves to end the game with $n$ pairs ( $2n$ cards in the deck) and $k$ $\textit{known}$ cards, where $0 \leq k \leq n$ . By $\textit{known}$ I mean that if you flip card $i$ and $j$ , $i \neq j$ , this two cards become known, meaning that the player will remember their position.

It's trivial that $E_{0,1}=E_{1,1}=1$ and that $E_{n,n}=n$ . We can write a recursive equation for $E_{n,k}$ :

$\displaystyle E_{n,k}=1+p_1 E_{n-1,k}+p_2 E_{n-1,k-1}+p_3(E_{n-1,k}+1)+p_4E_{n,k+2}$

where $p_i$ is the probability of end up in the respective state. In particular

• State $E_{n-1,k}$ represent the case in which the player removes a pair of cards, not among the already known ones
• State $E_{n-1,k-1}$ represent the case in which the player removes a pair of cards, among the already known ones
• State $E_{n-1,k}+1$ represent the case in which the player flips an unknown card and than one of the known ones. The subsequent move is to remove the known pair.
• State $E_{n,k+2}$ represent the case in which the player flips two unknown cards.

With a bit of patience, it can be found that

$p_1=\frac{2(n-k)}{(2n-k)(2n-k-1)} \\ p_2=\frac{k}{2n-k} \\ p_3=\frac{2(n-k)k}{(2n-k)(2n-k-1)} \\ \\ p_4=\frac{4(n-k)(n-k-1)}{(2n-k)(2n-k-1)}$

You can check that $\displaystyle \sum_{i=1}^{4} p_i=1$ . Hence, the final form of the equation is

$\displaystyle E_{n,k}=\begin{cases} 1+\frac{2(n-k)}{(2n-k)(2n-k-1)}[(k+1)E_{n-1,k}+k]+\frac{k}{2n-k}E_{n-1,k-1}+\frac{4(n-k)(n-k-1)}{(2n-k)(2n-k-1)}E_{n,k+2}, & \ \text{for} \ n>1, \\ 1, & \ \text{for} \ n=1, k=\{0,1\} \end{cases}$

For a given $n$ , the expected number of moves to end the game is $E_{n,0}$ . When $n=1729$ it can be computed (I used MATLAB) that

$\displaystyle E_{1729,0}=\frac{33475}{12} \approx \boxed{2789.586}$

We have the following theorem:

The expected length of a game of Memory with $2n$ cards is:

$(3 - 2 \ln 2$ ) $n$ + $\frac{7}{8}$ - $2 \ln 2$ + $E_n$ , where $E_n$ is an error term that approaches zero as n approaches infinity.

The statement of the theorem and its proof can be found here .

So we simply apply this theorem to obtain our answer.

The expected length of a game of Memory with 1729 pairs of cards is:

$(3 - 2 \ln 2$ ) $1729$ + $\frac{7}{8}$ - $2 \ln 2$ $\approx$ 2789.586