Recently I was playing several rounds of the game of [pairs](https://en.wikipedia.org/wiki/Concentration_(game)) 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$?



Expected distance of nearest matching pair in the game of pairs
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)$. 


