# Expected number of turns to find all pairs in card matching game

Suppose we have a game with $$2n$$ cards labeled $$1,1,2,2,...,n,n$$, such that for every integer $$i$$ where $$1\leq i\leq n$$ we have 2 cards labeled with $$i$$. Initially, all the cards are placed face-down on a table. Every turn, the player flips over 2 cards one at a time. If they match, which is if the two cards share the same number, the two cards are removed from the board. If they do not match, the two cards are flipped back to their face-down position. The game ends when all pairs have been found, and all the cards have been removed from the table. (This game is known as Concentration).

Assume the player has perfect memory, and that even after flipping a card back over, they are able to remember which card has what number on it. My question is: what is the expected number of turns to complete a game given $$n$$ starting pairs?

I have thought about this problem, and have come up with a few observations. Let $$E(N,k)$$ represent the expected number of moves to win from a state with $$2N$$ total face-down cards ($$N$$ unfound pairs) remaining and $$k$$ face-down cards that the player knows the value of.

• No matter what, we have $$k\leq N$$, since by PHP, $$k>N$$ implies that there are at least 2 face-down cards that share a value and where the player knows both their locations. Then the next move would be to flip all these "known" face-down pairs until $$k\leq N$$ again.
• $$E(N,k)=\frac{k}{2N-k}(E(N-1,k-1)+1)+\frac{2N-2k}{2N-k}\cdot\frac{1}{2N-k-1}(E(N-1,k)+1)+\frac{2N-2k}{2N-k}\cdot\frac{2N-2k-2}{2N-k-1}(E(N,k+2)+1)+\frac{2N-2k}{2N-k}\cdot\frac{k}{2N-k-1}(E(N-1,k)+2)$$
• $$E(N,N)=N$$
• $$0\leq aE(N,b)$$
• $$\lim_{N\to\infty} E(N,0)-E(N,k)=\frac{k}{2}$$
• $$\lim_{N\to\infty} E(N,N-k)-E(N,N)=k$$
• There exists some constant $$X$$ such that $$\lim_{N\to\infty} E(N,0)=X\cdot N$$.

If I am not mistaken, the goal to find the expected number of turns to complete a game with $$n$$ starting pairs reduces to finding that constant $$X$$. However, I am stuck here. I know $$\frac{3}{2}, but not much more.

• I wrote some code, and can conclude that most likely, $1.613585<X<1.613705641$. It's more likely closer to the upper bound, as the lower bound was calculated from $E(i,0)/i$ and the upper bound from $E(i,0)-E(i-1,0)$. Jul 6 at 8:29
• Is it true that when $n$ is even best case : n turns , worst case : $n/2 + n$ turns ?
– C.C
Jul 6 at 10:07
• I was about to answer the question, then discovered this. math.stackexchange.com/questions/1876467/…
– YJT
Jul 6 at 10:24
• @C.C I'm fairly certain the worst case is $2n-1$ and the best case is $n$ for all $n$. Jul 7 at 6:13

Wikipedia gives a link to the solution of your question, assuming perfect memorization and an optimal strategy.

$$E(N,0) \approx (3 − 2\ln{2})N + 7/8 − 2\ln{2}$$

therefore:

$$X=3 − 2\ln{2} \approx 1.61370563888$$

A freely accessible previous version of the same work by the same authors, with a different title, can be found at arXiv "Matching expectations".

• For the interested: from the arxiv paper, the error on the quoted formula for $E(N,0)$ is $O(1/\sqrt{N})$ Jul 6 at 14:32
• Wow, didn't see this paper. Now I wonder if some paper exists discussing the win probability of the player that moves first in a 2-player game with $n$ starting pairs. Jul 6 at 19:26
• @TracyMorgan you can take a look at the references at OEIS A299908. I didn't study them, but maybe you can find something useful there. Jul 7 at 5:51