Matching Game Perfect Play

I guess it kind of makes sense that it would be linear — this means that for every additional pair, you need an additional 1.61 turns on average. I guess you tend to reach some kind of steady state where the number of cards you know is a certain percentage of the total cards, and the tendencies to decrease the number of cards you know (by picking a match) and increase (by picking a new unknown card) balance each other out. On the other hand, in the real world, I would expect the function to grow faster than linear, since the more cards there are, the harder it is to remember them.

Also, I have no idea what the significance of the number 1.613706… is. It seems kinda close to the golden ratio but I’m pretty sure that’s just a coincidence.

4 Likes

Using @poisson’s recurrence to generate more terms, and taking successive differences, I was able to figure out that the numerators for p+2 follow a 6th-degree polynomial, then use Wolfram Alpha to find it:

P(p+2|p,0) = f(p) / (2p-1)!!

where

\displaystyle f(p) = \frac{(p-2)(p-1) p (p+1)(2p^2-2p-3)}{36} = \binom {p+1} 3 \frac{(p-2)(2p^2-2p-3)}{6}

The numerators for p+3 follow a 9th degree polynomial but I’m having some trouble determining it.

The 2p^2 - 2p - 3 term is unexpected, as it doesn’t factor into linear terms over the integers (the roots are (1 \pm \sqrt 7)/2). I was kinda hoping/expecting that f(p) would be something like a product of two binomial coefficients.

3 Likes

This is so cool! So, so far we have, for p pairs of cards:

turns   probability  
p   \dfrac{p! 2^p}{(2p)!}=\dfrac{1}{(2p-1)!!} maximum luckiness, every turn reveals a match
p+1   \dfrac{2 \binom{p+1}{3}}{(2p-1)!!} one more turn than there are pairs
p+2   \dfrac{\binom {p+1} 3 (p-2)(2p^2-2p-3)/6}{(2p-1)!!} two more turns than pairs
  [general case goes here!]
2p-1   \begin{cases} 1 & \text{if } p=1 \\ \dfrac{2^p-2}{(2p-1)!!} & \text{if } p>1 \end{cases} maximally unlucky

(And just to repeat Brent’s note about double factorial since it’s not what it looks like: n!! = n\cdot(n-2)\cdot(n-4)\cdots down to 2 or 1 depending on whether n is even or odd.)

I double-checked everything above up to 100 pairs of cards. I don’t know what’s up with that ugly special case for the 2p-1 formula but I needed it to make everything match the recurrence relation. (And we can see that it’s true for the p=1 case because that makes 2p-1=1 which is to say, the probability of it taking 1 turn when you have just 1 pair of cards, which is indeed 100%.)

2 Likes

We can get a recurrence relation for the expected value, perhaps similar to poisson’s for the distribution. Can Wolfram solve this into a closed form?

I had somewhat different notation: c is the number of cards, m_u the number of unpaired cards in our memory, and m_p the number of paired cards in our memory (this can only be 0 or 2). E gives the expected number of turns taken as a function of those variables. We have:

\begin{align} E(0,0,0) = 0 \\ E(c,m_u,2) = 1 & + E(c-2,m_u,0)\\ E(2,1,0) = 1 \\ \text{otherwise} \\ E(c,m_u,0) = 1 & + \frac{m_u}{c-m_u}E(c-2,m_u-1,0) \\ & + \frac{c-2m_u}{(c-m_u)(c-m_u-1)}(E(c-2,m_u,0) \hspace{2cm}\\ & + m_uE(c,m_u,2)+c-2(m_u-1)E(c,m_u+2,0)) \end{align}

I wonder if this is correct / gets the same expected value results as Danny computed before.

3 Likes

Ooh! Thanks for this! I’m eager to try but you currently have a mismatched parenthesis and I’m having trouble debugging it. (Also we probably need more base cases to avoid division by zero.)

1 Like

@wantonhalo I’m failing to get your recurrence relation to work! It looks like a really good approach though, so lemme try to understand it…

(Btw, @bee jumped in and helped me figure out the following.)

There are c cards on the table. Of those c cards, there are u that you know and that you don’t know the match of. Also there are p out of the remaining c-u cards that you know and which you do know the match of. (As you @wantonhalo says, if p ever becomes 2 then you know a match which you’ll immediately grab on your next turn.) We’re looking for the expected number of a turns as a function of c, u, and p which we write as E(c,u,p).

So we have the following cases:

  1. With zero cards on the table, you’re done in zero turns. E(0,u,p)=0.
  2. With 2 cards on the table, you’re done in 1 turn. E(2,u,p)=1.
  3. If you know a matching pair then the number of turns is 1 more then if that pair wasn’t there at all. (This is the parenthetical above). E(c,u,2) = 1 + E(c-2,u,0).
  4. Your first flip matches one of the u cards you know. Each of the u cards you know has its match on the table as one of the c-u unknown cards. So there’s a \frac{u}{c-u} probability that you’ll pick one of those. If you do then you remove 2 cards from the table, one of which is one of your known cards. So E(c-2,u-1,0).
  5. Dumb luck! Your first flip doesn’t match anything but your second flip matches the first flip. This happens iff the first flip is not a match of any of the u cards – probability \left(1-\frac{u}{c-u}\right) – and then the second flip is the exact needed card – probability \frac{1}{c-u-1}. Multiply those probabilities for the probability of lucking out on a greenfield match. If that happens, we grab the match and have E(c-2,u,0).
  6. We flip over two new cards that don’t match each other but the second flip reveals a new match. So again we have probability \left(1-\frac{u}{c-u}\right) for the first flip not matching anything, and then with probability \frac{u}{c-u-1} the second flip matches one of the u already-known cards. In this case, we have E(c,u,2) or 1+E(c-2,u,0).
  7. We memorize two new cards with no new matches learned. Like case 5, this means first flipping over a non-match – probability \left(1-\frac{u}{c-u}\right) – and then not hitting any of the u+1 cards known after the first flip, so probability 1-\frac{u+1}{c-u-1}. If this happens then we have the same number of cards on the table but 2 more known unpaired cards, E(c,u+2,0).

Putting all that together, we’re getting the following for the general case:

\begin{align} E(c,u,0) = 1+ &\dfrac{u}{c-u}E(c-2,u-1,0) & \text{ (find match)} \\ + & \left(1-\dfrac{u}{c-u}\right)\dfrac{1}{c-u-1}E(c-2,u,0) & \text{ (dumb luck)} \\ + & \left(1-\dfrac{u}{c-u}\right)\dfrac{u}{c-u-1}E(c,u,2) & \text{ (learn match)} \\ + & \left(1-\dfrac{u}{c-u}\right)\left(1-\dfrac{u+1}{c-u-1}\right)E(c,u+2,0) & \text{ (bupkis)} \end{align}

But I think it must still have a bug somewhere because when I put that in Mathematica and ask for E(2,0,0) it complains about division by zero.

1 Like

Does Mathematica carry out multiplication lazily or strictly in the second argument? e.g. if you define f(x) = (x - x) * f(x+1) will it evaluate to 0, or will it go into infinite recursion? This is relevant because of the last “bupkis” case. When evaluating E(2,0,0) the probability of this case is zero (intuitively it is obvious that this case can’t happen when there are only 2 cards left, and algebraically 1 - (u+1)/(c-u-1) = 1 - 1/(2-0-1) = 1-1 = 0), but if the recursive call happens anyway, it will be to E(2,2,0) which makes no sense, and leads to evaluating things like u/(c - u) = 2/(2 - 2).

I had to deal with this very carefully when defining my Haskell version of @poisson 's recurrence.

2 Likes

Also, it should be possible to get rid of the last parameter, since it is only ever 0 or 2. Just substitute 1 + E(c-2,u,0) in for E(c,u,2) in the “learn match” case; then all the calls to E have zero as the last argument so you can just get rid of it.

2 Likes

Ah, smart, yes, it turns out that Mathematica is hard-working! I.e., it is too dumb to optimize away the recursive call in such cases.

Also smart. I came to the same conclusion when debugging my Wolframaic.

Which, update! The following gives the correct results for expected number of turns:

e[c_, u_] := e[c, u] = Which[
  c == 0, 0,
  c == 2, 1,
  u == c, c/2,
  c-u-1 == 0, 0,
  True, 1 +
    u/(c-u) e[c-2, u-1] + (* first flip matches one of the u cards *)
    (1-u/(c-u)) 1/(c-u-1) e[c-2, u] + (* dumb luck *)
    (1-u/(c-u)) u/(c-u-1) (1+e[c-2, u]) + (* 2nd flip matches 1 of the u cards *)
    (1-u/(c-u)) (1-(u+1)/(c-u-1)) e[c, u+2] (* 2 greenfield flips match bupkis *)
   ]

(Thanks again to @bee for fixing errors here.)

Unfortunately, I’m failing to get Mathematica to make any progress on solving the recurrence relation in closed form, though it’s entirely possible I’m doing it wrong…

3 Likes