What is the expected number of missing random integers?

Question

Consider $n$ numbers randomly generated by independent generators that can produce integers from $0$ to $n$. How many of these integers will be missing on average for large $n$? If $p_{k,n}$ is the probability that $k$ is generated by a given generator then the probability that it is missing from all $n$ is $(1-p_{k,n})^n$, so $E_n=\sum_{k=0}^n(1-p_{k,n})^n$ is the expected number of misses. If all $k$-s were equally likely, i.e. $p_{k,n}=\frac1{n+1}$, it is easy to estimate: $E_n=\sum_{k=0}^n(1-\frac1{n+1})^n\sim\frac{n+1}e+\frac12+O(\frac1n)$, i.e. just over a third of integers will be missing.

I am interested in the case when the numbers are generated binomially: there are $n$ heaps of objects with $n$ in each heap, and each one is kept or discarded with probability $\frac12$. The resulting number of objects in a heap is then $k\leq n$ with probability $p_{k,n}=\frac{C_n^k}{2^n}$. For this distribution we expect the counts to cluster symmetrically around $k=\frac{n}2$, so using the Stirling formula or the local limit theorem $p_{k,n}\sim\frac1{\sqrt{\pi n/2}}e^{-\frac{(k-n/2)^2}{\pi n/2}}$, and after shifting and rescaling $E_n\sim2S_{\frac{n}2}$, where $$S_n=\sum_{k=0}^n\Big(1-\frac1{\sqrt{\pi n}}e^{-\frac{k^2}{\sqrt{\pi n}}}\Big)^{2n}.$$ If not for the $2n$-th power there are standard methods using Mellin transforms or the Euler-Maclaurin formula to find asymptotics of such sums, but as is...

Using the binomial formula on the inside looks like a bad idea, it produces terms with positive powers of $n$ and alternating signs, so there must be massive cancellations since obviously $S_n\leq n+1$. There are thresholds for terms' behavior at large $n$. Let $$k_{n,\varepsilon}^2:=(\frac12+\varepsilon)\pi n\ln n+\frac12\pi\!\ln\pi\,n,$$ then the summands are exponentially close to zero if $k\leq k_{n,-\varepsilon}$ and inverse power close to $1$ if $k\geq k_{n,\varepsilon}$. So $$\big(n+1-k_{n,\varepsilon}\big)\big(1-O(n^{-\varepsilon})\big)\lesssim S_n\lesssim n+1-k_{n,-\varepsilon}.$$ This does imply that the fraction of missing integers approaches 1 for large $n$, but it is not exactly sharp, and I do not see how to make it so (one can improve on it slightly by noticing that for $k^2\gtrsim n^{1+\varepsilon}$ the terms are exponentially close to $1$). There is an intermediate range with $k^2:=\frac12\pi n\ln n+\frac12\pi\!\ln\pi\,n+O(1)$, which corresponds to summands $(1-\frac{c}n)^{2n}\sim e^{-2c}$, with $c$ from $O(1)$. It almost seems like one has to sum or integrate over "ranges" with orders of growth in place of numbers and then add the results. But I do not know what that can mean exactly for the intermediate range, and I have not seen anything of this sort done. Perhaps, one should "change variables" to transform the range somehow.

Any advice/ideas/references are appreciated. It is entirely possible that I am on the wrong track, this seems like a reasonable probabilistic/combinatorial question and there might be standard methods for asymptotics of such sums that I missed. This example is representative of a type I am interested in, with sums of $n$-th powers of terms close to $1$.

Answer 1

The expected number of values hit is asymptotic to $\sqrt{n\log n}$.

Start with Stirling's formula: $$ P(n,k) := 2^{-n}\binom{n}{n/2+k} = \sqrt{\frac{2}{\pi n}} e^{-2k^2/n} (1 + O(1/n)), $$ provided $k$ is not too large (smaller than $n^{1/3}$ is more than enough).

The probability that value $n/2+k$ is hit is $$P(n,k)=1 - \biggl(1 - 2^{-n}\binom{n}{n/2+k}\biggr)^n.$$ Now scale by $k=x\sqrt{n\log n}$. Dropping the error terms for simplicity, and using $(1-z)^n=e^{-zn+O(z^2n)}$ we have $$P(n,k) \approx P_0(n,x) := 1 - \exp\biggl( -\frac 2\pi n^{1/2-2x^2} \biggr).$$

The function $P_0(n,x)$ has a plateau shape with tiny tails. As $n\to\infty$, we have $$ P_0(n,x) ~~\begin{cases} \to 1, & |x|<1/2\\ = 1 - e^{-\sqrt{2/\pi}}, &|x|=1/2\\ \to 0, & |x|>1/2, \end{cases} $$ where in the first and third cases convergence is very rapid. Thus we have $$\int_{-\infty}^\infty P_0(n,x)\,dx \to 1 ~\text{ as $n\to\infty$}.$$

The sum and the integral are asymptotically equal (which in this case is easy to see since the function rapidly converges to a step function), so we conclude that $$\sum_{k=-n/2}^{n/2} P(n,k) \sim \sqrt{n\log n}.$$ In detail, for any $\epsilon>0$, values in $[n/2-(1/2-\epsilon)\sqrt{n\log n},n/2+(1/2-\epsilon)\sqrt{n\log n}]$ almost certainly appear and values outside $[n/2-(1/2+\epsilon)\sqrt{n\log n},n/2+(1/2+\epsilon)\sqrt{n\log n}]$ almost certainly don't appear.

All this could be done with more precision.

ADDED: Working directly, if $|k|\le \frac12\sqrt{n\log n}-\sqrt{n}$ then $n/2+k$ almost certainly occurs, while if $|k|\ge \frac12\sqrt{n\log n}+\sqrt{n}$ then $n/2+k$ almost certainly does not occur. Doing this with error estimates shows that the expected number of values hit is $\sqrt{n\log n}+O(\sqrt n)$.