What is the expected length of a memory game when neither player (you may as well play against yourself) remembers any of the cards being uncovered in previous rounds?

Initially and until the first match (because players do not remember), when playing with $N$ pairs, there is a probability of $p=1/(2N-1)$ of a match, as there are $2N-1$ remaining cards which could be a match for the first card you draw.

The game is over when all $N$ pairs are matched, and in principle the game could last forever. Hence, a negative binomial distribution would seem like a good starting point, as we aim to model the probability of $N$ successes in a sequence of Bernoulli experiments.

However, once a match has been found, the success probability increases to $1/(2N-3)$, as the two matches are removed from the game. Hence, the success probability in the trials is not constant. Once there are only two cards left, you are bound to have a match.

I found a paper here that discusses the case in which the players play optimally, i.e., forget nothing.

  • 3
    $\begingroup$ A recursive solution is attractive here and easy to work out: the expected length is the expected time to obtain the first match plus the expected length of a game with $N-1$ pairs. The resulting sum simplifies considerably :-). $\endgroup$ – whuber Aug 2 '16 at 15:19
  • $\begingroup$ @whuber, oh, right, I could have seen that, thanks@ $\endgroup$ – Christoph Hanck Aug 2 '16 at 16:25

So, by @whuber's suggestion:

$$E(\text{number of attempts for }N\text{ pairs})=\sum_{j=1}^NE(\text{number of attempts for }j\text{th pair})$$ The first pair has, as mentioned in the question, a success probability of $p=1/(2N-1)$ in any given attempt, and follows a geometric distribution. The expectation therefore is $$E(\text{number of attempts for }1\text{st pair})=2N-1$$ Likewise, $$E(\text{number of attempts for }2\text{nd pair})=2N-2-1$$ and in general $$\sum_{j=1}^NE(\text{number of attempts for }j\text{th pair})=\sum_{j=1}^N2N-2(j-1)-1$$ which indeed simplifies very nicely to $$\sum_{j=1}^N2N-2(j-1)-1=2N^2+N-2N(N+1)/2=N^2$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.