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$?
 A: 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)$.  
A: 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%.
A: 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
