# Expected distance of nearest matching pair in the game of pairs

Recently I was playing several rounds of the game of pairs with my children. I was surprised that almost every time, one matching pair was adjacent (either next to each other in a row, or vertically). This led to the following question.

Let $$n$$ be a positive integer. Consider the set $$C_n = \{1,\ldots, 2n^2\}\times\{0,1\}.$$ We say that $$(k,0)$$ and $$(k,1)$$ for $$k\in \{1,\ldots,2n^2\}$$ is a matching pair in $$C_n$$.

Let $$G_n = \{1,\ldots, 2n\} \times \{1,\ldots,2n\}\subseteq \mathbb{R}^2$$ be thought of the "gaming grid" where we place the numbers. Formally: shuffling and distributing the cards corresponds to a bijection $$\varphi: C_n \to G_n$$. So we can define the minimum distance of a matching pair by $$M_n = \min\big\{||\varphi(k,0), \varphi(k,1)||: k\in \{1,\ldots,2n^2\}\big\}.$$

By $$||\cdot||$$ we denote the Euclidean distance.

$$M_n$$ is a random variable, so we can calculate its expected value $$E(M_n)$$.

Question. In plain English: if we play the game of pairs on an ever growing quadratic play-field, can we expect to find some matching pair in a reasonably close distance? Or more formally: Do we have $$\lim_{n\to\infty} E(M_n) < \infty$$?

• The probability that the two copies of $k$, formally $(k, 0)$ and $(k, 1)$, are adjacent is about $1/n^2$. Once $(k, 0)$ is placed there are four possible places to put $(k, 1)$, out of $4n^2$. (I'm ignoring edge effects.) There are $2n^2$ different pairs so we should expect about 2 adjacent matching pairs, and these sorts of distributions are "usually" Poisson, so I'd expect $P(M_n = 1) \to 1 - e^{-2}$ as $n \to \infty$. But this sort of reasoning doesn't directly give your desired result since $M_n$ could be very large with non-negligible probability. Nov 28 '18 at 16:09

The goal here is to show that Michael's "usually Poisson" reasoning can be made rigorous. For $$d>0$$, let $$c_d$$ denote the number of other lattice points in $$\mathbb{Z}^2$$ within distance $$d$$ of the point $$(n,n)$$. My claim will be that for fixed $$d$$ the number of matching pairs of distance at most $$d$$ is asymptotically Poisson with mean $$c_d/2$$, and in particular that the probability there is at least one pair within distance $$d$$ converges to $$1-e^{-c_d/2}$$.

As pointed out by Michael in his comment, this doesn't directly extend to a guarantee of bounded expectation without some further argument showing there isn't a part of the tail that has probability tending to $$0$$ but expectation tending to infinity.

Call an unordered pair $$\{ (x_1, y_1), (x_2, y_2) \}$$ of points in our grid close if the points are within distance $$d$$ from each other. The number of close pairs is equal to $$2n^2 c_d + O(n)$$, where here (and throughout) the constant in the $$O$$ notation may depend on $$d$$ and $$m$$. (Equivalently, there's $$4n^2 c_d+O(n)$$ ordered pairs of close points. The idea is that each of the $$4n^2-O(n)$$ points $$(x_1, y_1)$$ not within distance $$d$$ of the boundary of the grid is the first point in $$c_d$$ pairs).

For each close pair $$p$$ of points, let $$X_p$$ be equal to $$1$$ if the pair matches, and $$0$$ otherwise. Then we have $$E(X_p) = \frac{1}{4n^2-1}$$ and the number of matching pairs is $$X= \sum_{p} X_p,$$ Let $$\{Z_p\}$$ be a family of independent random variables each equal to $$1$$ with probability $$\frac{1}{4n^2-1}$$, and let $$Z=\sum Z_p$$. Then $$Z$$ converges to the Poisson distribution as $$n$$ goes to infinity. To show that $$X$$ also converges to Poisson, it is enough to show that the moments of $$X$$ are asymptotically equal to the moments of $$Z$$, i.e. that $$E(X^m-Z^m) \rightarrow 0$$ for each $$m$$.

We have $$\begin{eqnarray*} E(X^m) &=& E\left((\sum_p X_p)^m\right) \\ &=& E \left( \sum_{(p_1, \dots, p_m)} X_{p_1} X_{p_2} \dots X_{p_m}\right) \\ &=& \sum_{(p_1, \dots, p_m)} E(X_{p_1} \dots X_{p_m}) \end{eqnarray*}$$ and similarly for $$Z$$.

We now divide up our $$m-$$tuples into two classes:

Class 1: For each $$i \neq j$$ we either have $$p_i=p_j$$ or $$p_i \cap p_j = \emptyset$$ (i.e. no two pairs overlap in exactly one point).

Class 2: There is at least one pair $$(i,j)$$ for which $$p_i$$ and $$p_j$$ intersect exactly in one point.

Notice that in class $$2$$ it's impossible for both $$p_i$$ and $$p_j$$ to be matching pairs (If $$(x_1, y_1)$$ and $$(x_2, y_2)$$ match, it's impossible for $$(x_1, y_1)$$ and $$(x_3, y_3)$$ to match). So the contribution of Class $$2$$ to the expectation of $$X$$ is $$0$$. The bound we want on the expectation would follow from the following two claims:

Claim 1: For any tuple in class $$1$$ we have $$E(X_{p_1} X_{p_2} \dots X_{p_n}) = E(Z_{p_1} Z_{p_2} \dots Z_{p_n}) (1+o(1))$$. (So the total contribution of Class $$1$$ to $$E(X)$$ and $$E(Z)$$ is roughly the same).

Claim 2: The total contribution of class $$2$$ to $$E(Z)$$ is $$o(1)$$.

The intuition here is that because $$m$$ is fixed and the size of the grid tends to infinity, most collections of points won't overlap at all, so class $$2$$ isn't that significant.

For claim $$1$$: If $$r$$ is the number of distinct pairs in $$(p_1, p_2, \dots, p_m)$$, then we have $$\begin{eqnarray*} E(Z_{p_1} Z_{p_2} \dots Z_{p_m}) &=& \left(\frac{1}{4n^2-1}\right)^r \\ E(X_{p_1} X_{p_2} \dots X_{p_m}) &=& \left(\frac{1}{4n^2-1}\right)\left(\frac{1}{4n^2-3}\right) \dots \left(\frac{1}{4n^2-(2r-1)}\right)\end{eqnarray*}$$ (Knowing certain pairs match makes it slightly more likely that other pairs match too).
In particular, we have $$E(Z_{p_1} Z_{p_2} \dots Z_{p_m}) \leq E(X_{p_1} X_{p_2} \dots X_{p_m}) \leq E(Z_{p_1} Z_{p_2} \dots Z_{p_m})\left(\frac{4n^2-1}{4n^2-2m}\right)^m$$

A sketchier argument for Claim $$2$$: Let $$r$$ be as in claim $$1$$. If we consider all $$m$$-tuples containing $$r$$ distinct pairs, then only an $$O(\frac{1}{2n^2c_d})$$ of them have any overlap between the $$r$$ pairs. (the denominator here coming from how there's $$2n^2c_d$$ close pairs to choose from. Again the constant in the $$O$$ notation can depend on $$m$$ or $$d$$). All tuples with $$r$$ pairs have the same contribution to $$E(Z)$$, so the contribution from pairs with overlap is only $$O(\frac{1}{n^2})$$ the contribution from all pairs. The claim follows since $$E(Z)=O(1)$$.

I wrote a program that repeatedly generates a random grid and counts the number of adjacent pairs, and finally outputs the distribution of this number. Here are some results:

10*10 grid, 50 pairs, 1000000 games

     0      1      2      3      4      5      6      7     8    9   10  11  12
158437 295726 272342 164827  73472  25585   7400   1784   350   67    8   2   0


100*100 grid, 5000 pairs, 10000 games

   0      1      2      3      4      5      6      7      8      9     10
1361   2794   2729   1725    891    335    117     37      9      2      0


1000*1000 grid, 500000 pairs, 100 games

 0      1      2      3      4      5      6      7      8      9     10
13     25     23     25     10      3      1      0      0      0      0


So these results confirm Kevin's post. The probability that there is no adjacent pair converges to $$e^{-2}$$ = 13.53%.

• Hi Mark - thanks for the program and the results -- and welcome to MathOverflow! Dec 4 '18 at 10:10

I think the exact expected number of adjacent pairs is $$\dfrac{4n}{2n+1}$$, which is $$\frac43$$ when $$n=1$$, while it is $$\frac85$$ when $$n=2$$ and converges to $$2$$ as $$n$$ increases, consistent with Michael Lugo's almost Poisson comment. When $$n=1$$ the probability of at least one (in this case exactly two) adjacent pairs is $$\frac23$$, and it seems likely to increase from there

I suspect that the $$1-e^{-2}$$ asymptotic probability of a minimum distance of $$1$$ can also be extended to $$e^{-2}-e^{-4}$$ of minimum distance $$\sqrt{2}$$, then $$e^{-4}-e^{-6}$$ of minimum distance $$2$$, and $$e^{-6}-e^{-10}$$ of minimum distance $$\sqrt{5}$$ [note the jump in the exponent as a chess knight can move to up to $$8$$ squares], etc.

Adding these up, and a couple more, suggest a limit for $$E(M_n)$$ of approximately $$1.06727$$. The worst case is again when $$n=1$$ with $$E(M_1)=\frac{2+\sqrt{2}}{3} \approx 1.138$$ while simulation suggests $$E(M_2) \approx 1.088$$

Like Mark Dettinger, I attempted a simulation, mine of $$100000$$ games with a $$200\times200$$ grid, i.e. with $$n=100$$. I got the simulated proportion of games with a minimum distance of $$1$$ to be $$0.86322$$ which is indeed close to $$1-e^{-2}\approx 0.86466$$. I also got a sample average minimum distance of about $$1.0683$$, and the full list of frequencies of minimum distances compared with the predicted asymptotic probabilities was

mindist   sample frequency   prediction
1          86322           0.8646647
sqrt(2)      11798           0.1170196
2           1626           0.0158369
sqrt(5)        247           0.0024334
sqrt(8)          6           0.0000393
3              1           0.0000053
>=sqrt(10)        0           0.0000008


which also looks reasonably close to me