# Mixed moments for the birthday problem

Let $X_1,X_2,\dots$ be iid draws from the uniform distribution on $\{1,2,...,m\}$, and let the random variable $N$ be the minimum $j$ such that $X_j = X_i$ for some $i<j$.

I'm aware that the expected value of $N \choose 2$ (I call this a "mixed moment" since it's 1/2 times the second moment minus 1/2 times the first moment) is exactly $m$. Who first noticed/proved this?

Also, I've heard that, more generally, the expected value of $N \choose k$ is a degree-$k/2$ polynomial function of $m$ when $k$ is even. Where can I learn more about this?

$\newcommand{\N}{\mathbb N} \newcommand{\R}{\mathbb R} \newcommand{\B}{\mathcal B} \newcommand{\F}{\mathcal F} \newcommand{\X}{\mathcal X} \newcommand{\ep}{\epsilon} \newcommand{\la}{\lambda} \newcommand{\si}{\sigma} \newcommand{\Si}{\Sigma} \renewcommand{\c}{\circ} \newcommand{\tr}{\operatorname{tr}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\PP}{\operatorname{\mathsf P}}$

For any natural $n$, \begin{multline*} \PP(N>n)=\PP(X_1,\dots,X_n\text{ take distinct values })=\frac{m(m-1)\cdots(m-n+1)}{m^n} \\ =\frac{(m-1)\cdots(m-n+1)}{m^{n-1}}, \end{multline*} whence \begin{equation} \PP(N=n)=\PP(N>n-1)-\PP(N>n) =\frac{(m-1)\cdots(m-n+2)}{m^{n-1}}\,(n-1). \end{equation} So, \begin{multline*} \mu_k(m):=\E \binom Nk \\ =\frac1{k!}\sum_{n=k}^{m+1}\frac{n-1}{m^{n-1}}\,n(n-1)\cdots(n-k+1)(m-1)\cdots(m-n+2). \tag{1} \end{multline*} From here, with the help of Mathematica, I do get \begin{equation} \E \binom N2=m. \end{equation}

However, $\mu_4(10)-3\mu_4(9)+3\mu_4(8)-\mu_4(7)=0.0126\ldots\ne0$, so that $\mu_4$ is not a polynomial of degree $4/2=2$. That is, in general the statement that $\E \binom Nk$ is a polynomial of degree $k/2$ in $m$ is false.

Let us now show that $\mu_4(m)$ is not a polynomial in $m$ of any degree. Let $X_m$ be a random variable (r.v.) with the Gamma distribution with parameters $m$ and $1$, so that $X_m$ has the distribution of the sum of $m$ iid standard exponential r.v.'s, each of those r.v.'s with mean $1$. Then, by the central limit theorem, $\PP(X_m>m)\to1/2$ as $m\to\infty$.
An expression for $\mu_4(m)$ for any natural $m$ (also obtained with the help of Mathematica) is $\frac{1}{3} m \left(-2 e^m m E_{1-m}(m)+m+1\right)$, where $E_n(z)=\int_1^\infty t^{-n}e^{-tz}\,dt$ is "the exponential integral function"; I have verified numerically that for $m=1,\dots,100$ the latter expression for $\mu_4(m)$ matches the special case of (1) for $k=4$. So, if $\mu_4(m)$ were a polynomial in $m$, then so would be $e^m m^2 E_{1-m}(m)$. But \begin{multline*} e^m m^2 E_{1-m}(m)=e^m m^2 \frac1{m^m}\int_m^\infty u^{m-1}e^{-u}du =m\,\frac{e^m m!}{m^m}\,\PP(X_m>m) \\ \sim m\,\sqrt{2\pi m}\,\frac12 \end{multline*} as $m\to\infty$, by Stirling's formula and because $\PP(X_m>m)\to1/2$. So, $e^m m^2 E_{1-m}(m)$ cannot be a polynomial in $m$. Thus, $\mu_4(m)$ is not a polynomial in $m$, of any degree.

Here is an approach via Lagrange inversion.

Let $N$ denote the time of the first repeat, and let $T(z)$ (the tree function'') be the formal power series satisfying $T(z)=z\,e^{T(z)}$.

If $F$ is a formal power series the coefficients of $G(z):=F(T(z))$ are given by (Lagrange inversion) $$[z^0]G(z)=[z^0] F(z) \mbox{ , } [z^k]G(z)=\tfrac{1}{k} [y^{k-1}] F^\prime(y)\,e^{ky} =[y^k](1-y)F(y)\,e^{ky}\mbox{ for } k\geq 1\;.$$ In particular
$$[z^m] T(z)^k=\frac{k}{m} \frac{m^{m-k}}{(m-k)!}\mbox{ and } \frac{1}{1-T(z)}=\sum_{n\geq 0}\frac{n^{n}}{n!}z^n$$ Using the first relation it is easily seen that the generating function of $N$ may be written as $$\mathbb{E} t^N=\frac{m!}{m^m} [z^m]\frac{t}{1- tT(z)}$$ Thus the binomial moments $\mathbb{E}{N \choose k}$ of $N$ can be obtained as $$\mathbb{E}{N \choose k} = \frac{m!}{m^m} [z^m t^k]\frac{1+t}{1- (1+t)T(z)}=\frac{m!}{m^m} [z^m ]\frac{T(x)^{k-1}}{(1- T(z))^{k+1}}$$ Differentiation shows that $z\,T^\prime(z)= \frac{T(z)}{1-T(z)}$. Therefore \begin{align*} \mathbb{E}{N \choose 2} &=\frac{m!}{m^m} [z^m ]\frac{T(z)}{(1- T(z))^{3}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\frac{T^\prime(z)}{(1- T(z))^{2}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m} ]\frac{1}{1- T(z)} =m\end{align*} (I don't know who first observed that.) Similarly \begin{align*} \mathbb{E}{N \choose 4} &=\frac{m!}{m^m} [z^m ]\frac{T(z)^3}{(1- T(z))^{5}}\\ &=\frac{m!}{m^m} [z^{m-1} ] T^\prime(z)\frac{T(z)^2}{(1- T(z))^{4}}\\ &=\frac{m!}{m^m} [z^{m-1} ]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)^\prime\\ &=\frac{m!}{m^m} m\,[z^{m}]\big(\frac{1}{1- T(z)}-\frac{2}{3}\frac{1}{(1-T(z))^2}+\frac{1}{3}\frac{T(z)}{(1-T(z))^3}\big)\\ &=\frac{m^2}{3} +m -\frac{2}{3} m\,\mathbb{E}(N)\end{align*} Clearly other binomial moments can be treated in the same way.