Matching Game Perfect Play

[byorgey]

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.

[byorgey]

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.

[dreev]

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%.)

[wantonhalo]

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.

[dreev]

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.)

[dreev]

@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 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.

[byorgey]

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.

[byorgey]

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.

[dreev]

@byorgey

Does Mathematica carry out multiplication lazily or strictly in the second argument?

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.

@byorgey

Also, it should be possible to get rid of the last parameter

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…

[hiibb]

I have approached the problem in a bit of a different way, by imagining the cards lying in a 1-dimensional array, and working on the cards from left to right. If we have perfect memory, every card gets drawn either one time or two times.

We’re going to calculate for every index of the array the expected number of times this card is drawn. The expected number of draws of a card at a certain index is dependent on two things:

1. Whether the card is left card (L) of the pair or the right card (R) of the pair.
2. Whether the card is opened as the first card (F) in a turn or the second card (S) in a turn.

This means that the card at every index is one of the four possible types of cards: LF, LS, RF, RS

We can calculate the expected number of turns by summing the probabilities of the four types of cards. We know that a RF card is only drawn once, as we can match it immediately with its corresponding left card.

We know that a LS card is always drawn twice, once to observe it and once to match it with its corresponding right card.

For a LF card and a RS card, it depends on whether it is a “lucky draw” or not. If it is a lucky draw, both cards are drawn once, otherwise they are drawn twice. Therefore, we’ll further divide the LF and RS cards into two groups:

1. Lucky left first cards (LLF) and lucky right second cards (LRS)
2. Unlucky left first cards (ULF) and unlucky right second cards (URS)

This means that we now have six different types of cards: LLF, ULF, LS, RF, LRS, URS

If we know for every index of the array of cards the probability of being of a certain card type, we can calculate the expected number of draws of the card at a certain index. By summing the expected number of draws of all cards, and dividing by 2, we can estimate the expected number of turns. I have implemented this here: Google Colab

I get the same results as the other approach for the expected values. Two interesting plots:

[byorgey]

I note that the probability in your graphs of getting a “lucky draw” is basically zero, which makes sense, and the probability goes to zero as n goes to infinity. How close are the results if we simply pretend those types of cards don’t exist?

[hiibb]

Although the number of lucky draws per draw goes to zero as c goes to infinity, the number of lucky turns per game seems to stabilize around a value of about 0.70 lucky turns per game…

[byorgey]

Interesting!

[hiibb]

If we separate the even and uneven indices, we get much smoother curves.

[poisson]

Let’s try to explain the linear relationship @dreev saw for a large number of cards. We will not be too rigorous.

Let T{\left(c, u\right)} be the expected number of turns remaining, given that there are c cards remaining of which we know u. Consider the aforementioned recurrence relation for the expectation of the number of turns remaining

\begin{align}T{\left(c,u\right)} &= 1 + \frac{u}{c-u} T(c-2, u-1) + \left(1 - \frac{u}{c-u}\right) \frac{1}{c-u-1}T(c-2, u) \\&+ \left(1 - \frac{u}{c-u}\right) \frac{u}{c-u-1}\left(1+T(c-2, u) \right) \\&+ \left(1 - \frac{u}{c-u}\right) \left( 1 - \frac{u+1}{c-u-1}\right)T(c, u+2) \end{align}

We seek an approximate scaling solution T{\left(c, u\right)} \approx c \tau{\left(u/c\right)} \equiv c \tau{\left(f\right)}. Here now \tau is a continuous function of a real-valued argument. Our solution will only be valid in the limit c\to\infty at fixed f.

The idea is to expand both sides of the equation in powers of 1/c and solve it at the lowest nontrivial order. The terms at different values of c, u on the right-hand side, in this continuum limit, are approximated as derivatives.

So we just put the right hand side of the recurrence relation in mathematica, in terms of our scaling function \tau, and ask it to expand everything in powers of 1/c.

The lowest order term is just c \tau{(f)} = c \tau{(f)}, which is automatically satisfied.

The first nontrivial order is order one (c^0), which gives the differential equation

1 - f - f^2 +2 f ( 3 f - 2) \tau{(f)}+ (2 - 9 f + 13 f^2 - 6 f^3) \tau'{(f)} = 0

The general solution to this equation (per Mathematica, persumably by pulling all the \tau to one side and integrating) is:

\tau{(f)} = \frac{1 + 2 (1 - f)^2\left( \phi + \log((2 - 3 f)/(1-f))\right)}{4 f - 2}

for any constant \phi.

The boundary condition is \tau{\left(1/2\right)} = 1/2. We may easily verify that this BC is satisfied by \phi=-2, by plugging that in and then taking the limit f \to 1/2.

Our desired limiting time to finish the game is then c \tau{\left(0\right)}. This evaluates to

\lim_{c\to\infty} \frac{T}{c}= \left(\frac{3}{2} - \log{2}\right) \approx 0.80685.

Since the number of cards is twice the number of pairs, this seems to agree with @dreev’s numerical 1.6137-ish

[dreev]

Holy cow, yeah, here’s @poisson’s exact value compared to my numerical estimate:

1.6137056388801093812\ldots = 3-\log 4
1.6137058119738408985

Nice work! Now what about that 0.51154898513237434532?

PS: I replaced that 1.6137… number with the closest that Mathematica running on my laptop can get, namely the slope of the function (expected number of turns of perfect play with p pairs of cards) at p=476. There’s no doubt that @poisson is right that it’s converging to 3-\log 4 in the limit.

[poisson]

Hahaha I suspect that’s impossible to get an exact answer for. For any finite number of cards, of course the true function is not linear. The intercept you get by fitting has to be vaguely in the neighbourhood of 0-1 because you need to get the answer 1 for one pair, but beyond that the specific number you get is kind of just some weird result of the best fit of a line to a non-linear function sampled on some particular discrete set of points.

The actual “future work” I want to do is to estimate the shape of the tails of the distribution for a large number of cards…