2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This question might be improved by cutting it off after “probability 1/2”. In particular I recommend against describing bad ideas with more than one sentence. $\endgroup$ – Matt F. Jan 24 '18 at 4:25
  • $\begingroup$ @MattF. Let's hope someone has better ideas. I expected suggestions along these lines because they were made in somewhat similar problems (where only one range contributes to the leading term and the rest are estimated as negligible), so this is to suggest that some additional ideas are needed to make it work here. But I will be happy with a completely different idea that works. $\endgroup$ – Conifold Jan 24 '18 at 23:46
  • $\begingroup$ From what you wrote, it seems that you are able to obtain that $1-O(1/\sqrt{n\log(n)})$ elements will be missing. Are you looking for something sharper? $\endgroup$ – N. Gast Jan 26 '18 at 7:40
  • $\begingroup$ @N.Gast Yes, I'd like to know what the leading term(s) are for $n-S_n$ (number of present integers), naive guess is $n-S_n\sim\frac12\pi n\ln n+\frac12\pi\!\ln\pi\,n$, but I do not know how to get rid of the $\varepsilon$-s so it is possible that the growth is more subtle. And I'd like to know a general approach for refining the asymptotic for similar sums (which would come in estimating variance, etc.), if there is one, these estimates seem ad hoc and unimprovable along these lines. $\endgroup$ – Conifold Jan 26 '18 at 17:06
  • $\begingroup$ I must say that I do not know a general way to obtain such estimate. If I were to try, I would use the same approach as you do and would try to get rid of the epsilon by using some kind of uniform bound like Hoeffding's inequality. $\endgroup$ – N. Gast Jan 29 '18 at 9:12
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you. I seem to have gotten an extra $\sqrt{\pi}$ factor, did I mess up the LLT? I thought about switching to an integral but not about the rescaling or the way you get rid of the $n$-th power. Would using more terms in $(1-z)^n$ produce the precise form of the $O(\sqrt n)$ term? $\endgroup$ – Conifold Jan 30 '18 at 5:29
  • $\begingroup$ I computed the exact values up to $n=100000$ and there is no $\sqrt\pi$ for sure. As for the $O(\sqrt n)$ term, I just chose a function that worked but experimentally it seems fairly sharp. The exact value is $0.09358\sqrt n$ for $n=10$ and $0.08404\sqrt n$ for $n=100000$. The precise nature of that term could be determined but I'm not going to work on this further. $\endgroup$ – Brendan McKay Jan 30 '18 at 6:37
  • $\begingroup$ Yes of course, thank you for taking it so far. It gives me many new ideas to think over. $\endgroup$ – Conifold Jan 30 '18 at 7:45

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.