# Birthday Problem: Asymptotics of Expected Time Until a Match Occurs

I'm working on a variant of the birthday problem that I haven't found discussed on this site.

Suppose the sequence $(X_n)$ of independent random variables takes values uniformly in $\{ 1,...,N \}$. Let $F_{N} = \min\{ m: X_m = X_k, k<m \}$ be the first time that a match is observed.

I want to know what can be said about $E(F_N)$ as $N \to \infty$.

It's easy to see that $$P(F_N = k) = \frac{N}{N} \frac{N-1}{N}... \frac{N - (k-2)}{N} \frac{k-1}{N}.$$

Hence, $$E(F_N) = \sum_{k=2}^{N+1} k \Big[\frac{N}{N} \frac{N-1}{N}... \frac{N - (k-2)}{N} \frac{k-1}{N} \Big].$$

Any suggestions about where to go from here?

• Note that $$P(F_N \geqslant k+2) = \prod_{i=1}^{k}\left(1-\frac{i}N\right)$$ and that the RHS is of order $$e^{-k^2/(2N)}$$ hence, if $k_N^2\ll N\ll j_N^2$, then $$P(F_N\geqslant k_N)\to1\qquad P(F_N\geqslant j_N)\to0$$ In this sense, $$F_N=\Theta(\sqrt{N})$$ and one can guess that the same asymptotics holds for $E(F_N)$. – Did Sep 25 '16 at 22:43
• Conjecture: $$\lim_{N\to\infty}\frac{E(F_N)}{\sqrt{N}}=\sqrt{\frac\pi2}$$ – Did Sep 25 '16 at 23:15
• @i707107 It seems that, for every fixed $n$, setting $F_N^{(0)}=0$, the random vector $$\left(\frac{F_N^{(k)}-F_N^{(k-1)}}{\sqrt{N}}\right)_{1\leqslant k\leqslant n}$$ converges in distribution to a continuous nonnegative random vector with joint PDF $$x_1x_2\cdots x_n\,e^{-(x_1+x_2+\cdots+x_n)^2/2}$$ This suggests that each $(F_N^{(n)}-F_N^{(n-1)})/\sqrt{N}$ converges in distribution to a random variable with PDF $$xe^{-x^2/2}$$ and that, for every fixed $n$, $$\lim_{N\to\infty}\frac{E(F_N^{(n)})}{\sqrt{N}}=n\,\sqrt{\frac{\pi}2}$$ – Did Sep 27 '16 at 5:53
• @i707107 Indeed, I stand corrected. Then $$\lim_{N\to\infty}\frac{E(F_N^{(k)})}{\sqrt{N}}=m_k$$ with $$m_k=\frac1{2^{k-1}(k-1)!}\int_0^\infty x^{2k}e^{-x^2/2}dx=\frac{(2k-1)!!}{2^{k-1}(k-1)!}\sqrt{\frac\pi2}=\frac{k}{2^{2k-1}}{2k\choose k}\sqrt{\frac\pi2}$$ – Did Sep 28 '16 at 6:23
• ...and, again unless I am mistaken, $$\lim_{k\to\infty}\frac{m_k}{\sqrt{k}}=2\sqrt2$$ – Did Sep 28 '16 at 6:30

The probability of the first match on the $k^\text{th}$ trial is \begin{align} &\overbrace{\frac nn\frac{n-1}n\cdots\frac{n-k+2}n}^{\text{no match in k-1 trials}}-\overbrace{\frac nn\frac{n-1}n\cdots\frac{n-k+1}n}^{\text{no match in k trials}}\\ &=\frac{n!}{n^{k-1}(n-k+1)!}-\frac{n!}{n^k(n-k)!}\\ &=\frac{n!}{n^{k-1}(n-k+1)!}-\frac{n!}{n^{k-1}(n-k+1)!}\frac{n-k+1}n\\ &=\frac{n!\,(k-1)}{n^k(n-k+1)!}\tag{1} \end{align} Therefore, the expected value is \begin{align} E(F_n)= &\sum_{k=0}^n\frac{n!\,k(k-1)}{n^k(n-k+1)!}\\ &=\frac{n!}{n^{n+1}}\sum_{k=0}^n\frac{k(k-1)}{(n-k+1)!}n^{n-k+1}\\ &=\frac{n!}{n^{n+1}}\sum_{k=1}^{n-1}\frac{(n-k+1)(n-k)}{k!}n^k\\ &=\frac{n!}{n^{n+1}}\sum_{k=1}^{n-1}\frac{n(n+1)-2kn+k(k-1)}{k!}n^k\\ &=\frac{(n+1)!}{n^n}\sum_{k=1}^{n-1}\frac{n^k}{k!}-\frac{2n!}{n^{n-1}}\sum_{k=0}^{n-2}\frac{n^k}{k!}+\frac{n!}{n^{n-1}}\sum_{k=0}^{n-3}\frac{n^k}{k!}\\ &=-\frac{(n+1)!}{n^n}+\frac{n!}{n^n}\sum_{k=0}^n\frac{n^k}{k!}\tag{2} \end{align} Applying equation $(11)$ from this answer and Stirling's Approximation gives the expected value as $$\bbox[5px,border:2px solid #C0A000]{E(F_n)=\frac12\sqrt{2\pi n}+\frac23+O\left(\frac1{\sqrt{n}}\right)}\tag{3}$$

Extended Asymptotics

Extending the computation we did for $(3)$, we get $$E(F_n) =\sqrt{2\pi n}\left(\frac12+\frac1{24n}+\frac1{576n^2}\right) +\left(\frac23-\frac4{135n}+\frac8{2835n^2}\right) +O\left(\frac1{n^{5/2}}\right)\tag{4}$$

This is an elaboration of what @Did commented on $n$-th match.

Fix $K>0$. Denote by $F_N^{(n)}$ the time of $n$-th match and set $F_N^{(0)}=0$. For any fixed $n\geq 1$, we will find the joint CDF: For positive integers $k_1, \ldots , k_n$ with $0<k_1<k_2<\cdots <k_n\leq N$ and $k_n \leq K\sqrt N$, \begin{align} P &(F_N^{(1)} =k_1, \ldots , F_N^{(n)} =k_n ) \\ &=\frac{k_1-1}N\prod_{i=1}^{k_1-2}\left(1-\frac{i}N\right) \frac{k_2-2}N\prod_{i=k_1-1}^{k_2-3}\left(1-\frac iN\right)\cdots \frac{k_n-n}N\prod_{i=k_{n-1}-(n-1) }^{k_n-(n+1)}\left(1-\frac iN\right)\\ &=\frac{k_1-1}N \cdots \frac{k_n-n}N \prod_{i=1}^{k_n-(n+1)}\left(1-\frac iN\right)\\ &=\frac{k_1-1}N \cdots \frac{k_n-n}N \exp\left( -\frac{(k_n-(n+1))^2}{2N}+O(N^{-2})\right). \end{align} This gives $$P (F_N^{(1)} =k_1, \ldots , F_N^{(n)} =k_n ) = \frac{k_1-1}{\sqrt N } \cdots \frac{k_n- n}{\sqrt N}\exp\left( -\frac12 \left(\frac{ k_n-(n+1) }{\sqrt N}\right)^2+O(N^{-2})\right) \frac 1{\sqrt N^n} .$$ Fix $0\leq x_1, \ldots , x_n\leq K$, and sum this up for $k_i\leq x_i \sqrt N$, we have as $N\rightarrow\infty$, $$P\left( \frac{F_N^{(1)}}{\sqrt N}\leq x_1, \ldots , \frac{F_N^{(n)}}{\sqrt N} \leq x_n\right) \rightarrow \int_{0\leq t_1\leq \cdots \leq t_n, \ \forall i, t_i\leq x_i} t_1 \cdots t_n \exp \left(-\frac12 t_n^2\right) dV$$ (Think of this as summing the probabilities over the boxes with side length $1/\sqrt N$. The Dominated Convergence Theorem will suffice to justify this limit.)

Thus, the random vector $\left(\frac{F_N^{(1)}}{\sqrt N}, \ldots , \frac{F_N^{(n)}}{\sqrt N}\right)$ converges in distribution to the continuous random variable with PDF $$f(t_1,\ldots , t_n) = t_1 \cdots t_n \exp\left(-\frac 12 t_n^2\right) \mathbf{1}_{0\leq t_1 \leq \cdots \leq t_n}.$$

The question was originally about the expectation in case with $n=1$. So, the above calculation suggests that the expectation can be similarly calculated as $N\rightarrow\infty$, $$\mathbf{E}\left(\frac{F_N^{(1)}}{\sqrt N} \right)\rightarrow \int_0^{\infty} t_1^2 \exp\left(-\frac12 t_1^2\right) dt_1 = \sqrt{\frac{\pi}2}.$$

But, we need to treat the case with $k_1\neq O(\sqrt N)$. In the general case $k_n\neq O(\sqrt N)$. To do this, we use $$\log(1-x) \leq -x.$$ Then for $K\sqrt N < k_n$, $$\frac{k_n}{\sqrt N}P (F_N^{(1)} =k_1, \ldots , F_N^{(n)} =k_n ) \leq \frac{k_1\cdots k_{n-1}k_n^2}{\sqrt N^{n+1}} \exp\left( -\frac12 \left(\frac{ k_n-n-1 }{\sqrt N}\right)^2\right)\frac1{\sqrt N^n}.$$ Again by the Dominated Convergence Theorem, the right side after summing up for $0\leq k_1\leq \cdots \leq k_n$, becomes as $N\rightarrow\infty$, $$\int_K^{\infty} \int_0^{t_n} \cdots \int_0^{t_2} t_1\cdots t_{n-1}t_n^2 \exp\left(-\frac12 t_n^2 \right) dt_1\cdots dt_n.$$ Note that this can be made arbitrarily small with sufficiently large $K$. This shows that the suggested calculation is valid. We now have $$\mathbf{E}\left(\frac{F_N^{(n)}}{\sqrt N}\right) \rightarrow \int_0^{\infty} \int_0^{t_n} \cdots \int_0^{t_2} t_1 \cdots t_{n-1}t_n^2 \exp\left(-\frac 12 t_n^2 \right) dt_1\cdots dt_n.$$ This integral is in fact as @Did computed in the last comment to the question, $$\frac1{2^{n-1}(n-1)!} \int_0^{\infty} t_n^{2n} \exp\left(-\frac 12 t_n^2 \right) dt_n=\frac{(2n-1)!!}{2^{n-1}(n-1)!} \sqrt{\frac{\pi}2}\sim \sqrt{2n}.$$

• Thank you! This is helpful, but yes, the question is about expectation and it seems there are still some details to fill in there. Also, I appreciate the generalization but would accept a detailed answer to the case $F_N$. – grndl Sep 28 '16 at 13:54
• I'm sure I should know this but can you tell me where $$\prod_{i=1}^{k_n - (n+1)} 1- i/N = \exp \left(- \frac{ (k_n - (n+1))^2}{2N} + O(N^{-2})\right)$$ comes from? – grndl Sep 28 '16 at 13:57
• I am editing to include the details. About the product, there is $-$ sign inside the exponential. The idea is discussed in the comments, and it uses the Maclaurin series of $\log (1-x)$. – Sungjin Kim Sep 28 '16 at 13:58
• Edited, thanks. I must have missed that in the comments. I'll look again more carefully. Thanks again! – grndl Sep 28 '16 at 13:59