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$. 



What is the expected number of missing random integers?
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)$.


