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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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