Return to Answer

$\newcommand{\J}{\mathcal J}$More or less straightforward calculations show that $$E_n=\frac1{(2 n-1)!}\sum _{k=0}^n a_k,$$ where $$a_k:=a_{n,k}:=k! (2 n-k-1)! \binom{2 n-k+1}{k}.$$

This is rather easy to analyze by considering the ratios $a_{k+1}/a_k$, to get $$E_n\asymp\sqrt n,$$ as suggested in the comment by Sam Hopkins (even though I do not understand why this is very close to the birthday problem).

For an illustration, here is the (connected) plot $\{(n,E_n)\colon n=1,\dots,1000\}$:

Thinking a bit more about the comment by Sam Hopkins, now the similarity with the birthday problem seems clearer to me: there, we deal with exact coincidences of birthdays, here with near coincidences of ($2n$)-nomial outcomes.

Details: We do not have to assume that the number of cards, say $m$, is even. Let then $n:=\lfloor(m+1)/2\rfloor$.

Let $\nu_m$ be the number of steps needed to pick up, at least for some $k$, the neighbor cards labeled $k$ and $k+1$, so that \begin{equation*} E_m:=E\nu_m=\sum_{r=0}^\infty P(\nu_m>r). \tag{1} \end{equation*} Note that \begin{equation*} P(\nu_m>r)=\frac1{m^r}\,\sum_{k\ge0}\,\sum_{J\in\J_{m,k}}S_{k,r} =\frac1{m^r}\,\sum_{k\ge0}|\J_{m,k}| \, S_{k,r}, \tag{2} \end{equation*} where \begin{equation*} \J_{m,k}:=\Big\{J\subseteq[m]\colon|J|=k,\ \sum_{j=0}^{m-1}1(\{j,j+1\}\subseteq J)=0\Big\}, \end{equation*} $[m]:=\{1,\dots,m\}$, $|\cdot|$ denotes the cardinality, and $S_{k,r}$ is the number of maps from $[r]$ onto $[k]$. By inclusion-exclusion, \begin{equation*} S_{k,r}=\sum_{j=0}^k(-1)^j\binom kj (k-j)^r, \end{equation*} with $0^0:=1$.

The set $\J_{m,k}$ is obviously in a one-to-one correspondence with the set (say $Q_{m,k}$) of all sequences in $\{0,1\}^m$ with exactly $k\,$ $1$'s such that between any two subsequent $1$'s there is at least one $0$.

In turn, the set $Q_{m,k}$ is in a one-to-one correspondence with the set (say $R_{m,k}$) of all sequences in $\{0,1\}^{m-(k-1)}$ with exactly $k\,$ $1$'s: a bijection from $Q_{m,k}$ onto $R_{m,k}$ can be obtained by removing one $0$ from between any two subsequent $1$'s.

Thus, $|\J_{m,k}|=|Q_{m,k}|=|R_{m,k}|=\binom{m-k+1}k$ and hence, by (1) and (2), \begin{equation*} \begin{aligned} E_m &=\sum_{k\ge0}\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \sum_{r=0}^\infty\frac{(k-j)^r}{m^r} \\ &=\sum_{k=0}^n\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \frac m{m-k+j} \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \int_0^1 dx\,x^{m-k+j-1} \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \int_0^1 dx\,x^{m-k-1}(1-x)^k \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \frac{k!(m-k-1)!}{m!} \\ &=\sum_{k=0}^n b_k, \end{aligned} \tag{3} \end{equation*} where \begin{equation*} b_k:=b_{m,k}:=\binom{m-k+1}k\Big/\binom{m-1}k. \end{equation*}

It is easy to see that $b_k$ is decreasing in $k$, with \begin{equation*} \frac{b_{k+1}}{b_k}=1-(1+o(1))\frac kn=\exp\Big\{-(1+o(1))\frac kn\Big\} \end{equation*} if $k=o(n)$. Since $b_0=1$, we have \begin{equation*} b_k=\exp\Big\{-(1+o(1))\frac{k^2}{2n}\Big\} \end{equation*} if $k=o(n)$. Also, since $b_k$ is decreasing in $k$, it follows that $b_k=\exp\big\{-c^2 n/3\big\}$ if $k\ge cn$ and $n$ is large enough, for any fixed $c>0$. Thus, by (3), \begin{equation*} \begin{aligned} E_m &\sim\int_0^n dx\,\exp\Big\{-\frac{x^2}{2n}\,(1+o(1))\Big\} \sim\sqrt{\frac\pi2}\, \sqrt n\approx1.25\,\sqrt n; \end{aligned} \tag{3} \end{equation*} cf. the picture above.

$\newcommand{\J}{\mathcal J}$More or less straightforward calculations show that $$E_n=\frac1{(2 n-1)!}\sum _{k=0}^n a_k,$$ where $$a_k:=a_{n,k}:=k! (2 n-k-1)! \binom{2 n-k+1}{k}.$$

This is rather easy to analyze by considering the ratios $a_{k+1}/a_k$, to get $$E_n\asymp\sqrt n,$$ as suggested in the comment by Sam Hopkins (even though I do not understand why this is very close to the birthday problem).

For an illustration, here is the (connected) plot $\{(n,E_n)\colon n=1,\dots,1000\}$:

Thinking a bit more about the comment by Sam Hopkins, now the similarity with the birthday problem seems clearer to me: there, we deal with exact coincidences of birthdays, here with near coincidences of ($2n$)-nomial outcomes.

Details: We do not have to assume that the number of cards, say $m$, is even. Let then $n:=\lfloor(m+1)/2\rfloor$.

Let $\nu_m$ be the number of steps needed to have picked up, at least for some $k$, the neighbor cards labeled $k$ and $k+1$, so that \begin{equation*} E_m:=E\nu_m=\sum_{r=0}^\infty P(\nu_m>r). \tag{1} \end{equation*} Note that \begin{equation*} P(\nu_m>r)=\frac1{m^r}\,\sum_{k\ge0}\,\sum_{J\in\J_{m,k}}S_{k,r} =\frac1{m^r}\,\sum_{k\ge0}|\J_{m,k}| \, S_{k,r}, \tag{2} \end{equation*} where \begin{equation*} \J_{m,k}:=\Big\{J\subseteq[m]\colon|J|=k,\ \sum_{j=0}^{m-1}1(\{j,j+1\}\subseteq J)=0\Big\}, \end{equation*} $[m]:=\{1,\dots,m\}$, $|\cdot|$ denotes the cardinality, and $S_{k,r}$ is the number of maps from $[r]$ onto $[k]$. By inclusion-exclusion, \begin{equation*} S_{k,r}=\sum_{j=0}^k(-1)^j\binom kj (k-j)^r, \end{equation*} with $0^0:=1$.

The set $\J_{m,k}$ is obviously in a one-to-one correspondence with the set (say $Q_{m,k}$) of all sequences in $\{0,1\}^m$ with exactly $k\,$ $1$'s such that between any two subsequent $1$'s there is at least one $0$.

In turn, the set $Q_{m,k}$ is in a one-to-one correspondence with the set (say $R_{m,k}$) of all sequences in $\{0,1\}^{m-(k-1)}$ with exactly $k\,$ $1$'s: a bijection from $Q_{m,k}$ onto $R_{m,k}$ can be obtained by removing one $0$ from between any two subsequent $1$'s.

Thus, $|\J_{m,k}|=|Q_{m,k}|=|R_{m,k}|=\binom{m-k+1}k$ and hence, by (1) and (2), \begin{equation*} \begin{aligned} E_m &=\sum_{k\ge0}\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \sum_{r=0}^\infty\frac{(k-j)^r}{m^r} \\ &=\sum_{k=0}^n\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \frac m{m-k+j} \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \int_0^1 dx\,x^{m-k+j-1} \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \int_0^1 dx\,x^{m-k-1}(1-x)^k \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \frac{k!(m-k-1)!}{m!} \\ &=\sum_{k=0}^n b_k, \end{aligned} \tag{3} \end{equation*} where \begin{equation*} b_k:=b_{m,k}:=\binom{m-k+1}k\Big/\binom{m-1}k. \end{equation*}

It is easy to see that $b_k$ is decreasing in $k$, with \begin{equation*} \frac{b_{k+1}}{b_k}=1-(1+o(1))\frac kn=\exp\Big\{-(1+o(1))\frac kn\Big\} \end{equation*} if $k=o(n)$. Since $b_0=1$, we have \begin{equation*} b_k=\exp\Big\{-(1+o(1))\frac{k^2}{2n}\Big\} \end{equation*} if $k=o(n)$. Also, since $b_k$ is decreasing in $k$, it follows that $b_k=\exp\big\{-c^2 n/3\big\}$ if $k\ge cn$ and $n$ is large enough, for any fixed $c>0$. Thus, by (3), \begin{equation*} \begin{aligned} E_m &\sim\int_0^n dx\,\exp\Big\{-\frac{x^2}{2n}\,(1+o(1))\Big\} \sim\sqrt{\frac\pi2}\, \sqrt n\approx1.25\,\sqrt n; \end{aligned} \tag{3} \end{equation*} cf. the picture above.

More or less straightforward calculations show that $$E_n=\frac1{(2 n-1)!}\sum _{k=0}^n a_k,$$ where $$a_k:=a_{n,k}:=k! (2 n-k-1)! \binom{2 n-k+1}{k}.$$

This is rather easy to analyze by considering the ratios $a_{k+1}/a_k$, to get $$E_n\asymp\sqrt n,$$ as suggested in the comment by Sam Hopkins (even though I do not understand why this is very close to the birthday problem).

For an illustration, here is the (connected) plot $\{(n,E_n)\colon n=1,\dots,1000\}$:

Thinking a bit more about the comment by Sam Hopkins, now the similarity with the birthday problem seems clearer to me: there, we deal with exact coincidences of birthdays, here with near coincidences of ($2n$)-nomial outcomes.

$\newcommand{\J}{\mathcal J}$More or less straightforward calculations show that $$E_n=\frac1{(2 n-1)!}\sum _{k=0}^n a_k,$$ where $$a_k:=a_{n,k}:=k! (2 n-k-1)! \binom{2 n-k+1}{k}.$$

This is rather easy to analyze by considering the ratios $a_{k+1}/a_k$, to get $$E_n\asymp\sqrt n,$$ as suggested in the comment by Sam Hopkins (even though I do not understand why this is very close to the birthday problem).

For an illustration, here is the (connected) plot $\{(n,E_n)\colon n=1,\dots,1000\}$:

Thinking a bit more about the comment by Sam Hopkins, now the similarity with the birthday problem seems clearer to me: there, we deal with exact coincidences of birthdays, here with near coincidences of ($2n$)-nomial outcomes.

Details: We do not have to assume that the number of cards, say $m$, is even. Let then $n:=\lfloor(m+1)/2\rfloor$.

Let $\nu_m$ be the number of steps needed to pick up, at least for some $k$, the neighbor cards labeled $k$ and $k+1$, so that \begin{equation*} E_m:=E\nu_m=\sum_{r=0}^\infty P(\nu_m>r). \tag{1} \end{equation*} Note that \begin{equation*} P(\nu_m>r)=\frac1{m^r}\,\sum_{k\ge0}\,\sum_{J\in\J_{m,k}}S_{k,r} =\frac1{m^r}\,\sum_{k\ge0}|\J_{m,k}| \, S_{k,r}, \tag{2} \end{equation*} where \begin{equation*} \J_{m,k}:=\Big\{J\subseteq[m]\colon|J|=k,\ \sum_{j=0}^{m-1}1(\{j,j+1\}\subseteq J)=0\Big\}, \end{equation*} $[m]:=\{1,\dots,m\}$, $|\cdot|$ denotes the cardinality, and $S_{k,r}$ is the number of maps from $[r]$ onto $[k]$. By inclusion-exclusion, \begin{equation*} S_{k,r}=\sum_{j=0}^k(-1)^j\binom kj (k-j)^r, \end{equation*} with $0^0:=1$.

The set $\J_{m,k}$ is obviously in a one-to-one correspondence with the set (say $Q_{m,k}$) of all sequences in $\{0,1\}^m$ with exactly $k\,$ $1$'s such that between any two subsequent $1$'s there is at least one $0$.

In turn, the set $Q_{m,k}$ is in a one-to-one correspondence with the set (say $R_{m,k}$) of all sequences in $\{0,1\}^{m-(k-1)}$ with exactly $k\,$ $1$'s: a bijection from $Q_{m,k}$ onto $R_{m,k}$ can be obtained by removing one $0$ from between any two subsequent $1$'s.

Thus, $|\J_{m,k}|=|Q_{m,k}|=|R_{m,k}|=\binom{m-k+1}k$ and hence, by (1) and (2), \begin{equation*} \begin{aligned} E_m &=\sum_{k\ge0}\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \sum_{r=0}^\infty\frac{(k-j)^r}{m^r} \\ &=\sum_{k=0}^n\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \frac m{m-k+j} \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \int_0^1 dx\,x^{m-k+j-1} \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \int_0^1 dx\,x^{m-k-1}(1-x)^k \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \frac{k!(m-k-1)!}{m!} \\ &=\sum_{k=0}^n b_k, \end{aligned} \tag{3} \end{equation*} where \begin{equation*} b_k:=b_{m,k}:=\binom{m-k+1}k\Big/\binom{m-1}k. \end{equation*}

It is easy to see that $b_k$ is decreasing in $k$, with \begin{equation*} \frac{b_{k+1}}{b_k}=1-(1+o(1))\frac kn=\exp\Big\{-(1+o(1))\frac kn\Big\} \end{equation*} if $k=o(n)$. Since $b_0=1$, we have \begin{equation*} b_k=\exp\Big\{-(1+o(1))\frac{k^2}{2n}\Big\} \end{equation*} if $k=o(n)$. Also, since $b_k$ is decreasing in $k$, it follows that $b_k=\exp\big\{-c^2 n/3\big\}$ if $k\ge cn$ and $n$ is large enough, for any fixed $c>0$. Thus, by (3), \begin{equation*} \begin{aligned} E_m &\sim\int_0^n dx\,\exp\Big\{-\frac{x^2}{2n}\,(1+o(1))\Big\} \sim\sqrt{\frac\pi2}\, \sqrt n\approx1.25\,\sqrt n; \end{aligned} \tag{3} \end{equation*} cf. the picture above.

More or less straightforward calculations show that $$E_n=\frac1{(2 n-1)!}\sum _{k=0}^n a_k,$$ where $$a_k:=a_{n,k}:=k! (2 n-k-1)! \binom{2 n-k+1}{k}.$$

This is rather easy to analyze by considering the ratios $a_{k+1}/a_k$, to get $$E_n\asymp\sqrt n,$$ as suggested in the comment by Sam Hopkins (even though I do not understand why this is very close to the birthday problem).

For an illustration, here is the (connected) plot $\{(n,E_n)\colon n=1,\dots,1000\}$:

More or less straightforward calculations show that $$E_n=\frac1{(2 n-1)!}\sum _{k=0}^n a_k,$$ where $$a_k:=a_{n,k}:=k! (2 n-k-1)! \binom{2 n-k+1}{k}.$$

This is rather easy to analyze by considering the ratios $a_{k+1}/a_k$, to get $$E_n\asymp\sqrt n,$$ as suggested in the comment by Sam Hopkins (even though I do not understand why this is very close to the birthday problem).

For an illustration, here is the (connected) plot $\{(n,E_n)\colon n=1,\dots,1000\}$:

Thinking a bit more about the comment by Sam Hopkins, now the similarity with the birthday problem seems clearer to me: there, we deal with exact coincidences of birthdays, here with near coincidences of ($2n$)-nomial outcomes.