Memory game inspired problem

Question

Motivation. As I was playing the pairs-matching game "Memory" (known as "Concentration" in some parts of the world) with my children, I was surprised that even thorough shuffling could not prevent quite a few pairs of cards lying next to each other. This inspired the following problem.

Formalization. If $X,Y$ are nonempty sets, let $\pi_0:(X\times Y)\to X$ be the map defined by $(x,y)\mapsto x$ for all $(x,y)\in X\times Y$. We formalize the "Memory" game by letting $n\in\mathbb{N}$ be a positive integer and looking at bijections $\varphi:\{1,\ldots, 2n\} \to \big(\{1,\dots,n\}\times\{0,1\}\big)$, and we think of $(i, 0), (i,1)$ as a "matching pair of cards" as in the "Memory" game. We denote the collection of such bijections by ${\cal M}_n$. We say $k\in \{1,\ldots, 2n-1\}$ is an adjacent index if $$\pi_0(\varphi(k)) = \pi_0(\varphi(k+1)),$$ and let $\text{Adj}(\varphi)$ be the collection of adjacent indices of the bijection $\varphi\in{\cal M}_n$. The expected value of the number of adjacent indexes in any such bijection $\varphi$ is given by $$E_n=\frac{1}{(2n)!}\sum_{\varphi\in{\cal M}_n} \text{Adj}(\varphi).$$

Question. What is the value of $\lim\sup_{n\to\infty} E_n$?

Answer 1

First, a simple answer (evocated in the comments) : since expectation is linear (even without independence), when we express $\text{Adj}$ as the sum of each index being adjacent, we can sum their expectation. Each index $i \in \{1, \dots, 2n-1\}$ is connected to exactly one of the other indexes in $\{1, \dots, 2n\} \setminus\{i\}$ with equal probability, so has a probability $\frac 1 {2n-1}$ to be $i+1$. So the expectancy of $i$ being an adjacent index is $\frac 1 {2n-1}$, and there are $(2n-1)$ of those, so the expectation is exactly $1$.

Let us look at the law of $\text{Adj}_n$:

The first tile $\varphi(0)$ is matched to $\varphi(m)$. If we remove $\varphi(0)$ and $\varphi(m)$ from the table, we (score a point and) get a new instance of the game with $2(n-1)$ tiles, and you could convince yourself that it is uniformly sampled from the set of such games. We can count how much adjacent indices there are in that smaller instance with the law of $\text{Adj}_{n-1}$. Then, when we add back $\varphi(m)$, we have some chance of breaking an adjacent index, which depends on the number of adjacent indices $\text{Adj}_{n-1}$. Numerically, with $X_n = \text{Adj}_n$ :

$$(X_{n+1} = k) \Leftrightarrow (m = 1 \wedge X_n = k-1) \vee (m \neq 1 \wedge X_n = k \wedge \varphi(m) \textrm{ doesn't cut }X_n) \vee (m \neq 1 \wedge X_n = k+1 \wedge \varphi(m) \textrm{ cuts }X_n)$$

$$P(X_{n+1} = k) = \frac 1 {2n+1} P(X_n = k-1) + \frac {2n} {2n+1} P(X_n = k)\frac {2n - k} {2n} + \frac {2n} {2n+1} P(X_n = k+1)\frac {k+1} {2n}$$ Hence $$P(X_{n+1} = k) = \frac {P(X_n = k-1) + (2n - k)P(X_n = k) + (k+1) P(X_n = k+1)} {2n+1}$$

As reasonable mathematicians, we can compute the first values to see what happens :

Values of $P(X_n)$: $$\begin{matrix} n=1 & 0 & 1 & 0 & \dots \\ n=2 & \frac 1 3 &\frac 1 3 &\frac 1 3 &0 & \dots \\ n=3 & \frac 5 {15} & \frac 6 {15} & \frac 3 {15} & \frac 1 {15} & 0 \\ n=4 & \frac {36} {105}& \frac {41} {105}& \frac {21} {105}& \frac {6} {105}& \frac {1} {105} \end{matrix}$$

Entering the numerators into the OEIS yields https://oeis.org/A079267 which has lots of references about the problem, a direct formula, an exponential generative function...