4
$\begingroup$

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$?

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Michael Lugo Nov 28 '18 at 16:09
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hi Mark - thanks for the program and the results -- and welcome to MathOverflow! $\endgroup$ – Dominic van der Zypen Dec 4 '18 at 10:10
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.