2

The starting point is the following:

Given the positive fractions $0 \lt c \le d \le 1$, what is the probability of getting at least $m=cn$ unique numbers when selecting $k=dn$ integers independently and uniformly from the range $[1,n]$?

In a related question, an exact answer for a fixed $m$ is given as a sum involving binomial coefficients: https://math.stackexchange.com/a/1087968/471924

Instead of an exact answer, I would like to consider where $m$ is significantly smaller than the expectation value, and to discuss the asymptotics of the probability as $n$ increases without bound.

In particular I am looking for conditions on $c$ and $d$ that allow a statement like:
With probability $1-o(1)$ there are at least $cn$ unique numbers when randomly selecting $dn$ integers uniformly from the range $[1,n]$.

Is there someway to get from the exact results to conditions on $c,d$ which would make the above asymptotic statement true?

JJMalone
  • 63

1 Answers1

2

The number $Z_{dn} $ of unique numbers when selecting $dn$ numbers with replacement from $n$ is about $(1-e^{-d})n$ on average. Moreover, the variance is of order $n$, so $Z_{dn} = (1-e^{-d})n + O_p(\sqrt{n})$.

It can be shown that the error of this approximation is asymptotically normal. Here is the idea. Let the numbers be drawn one by one. Denote by $T_k$ the time of $k$th unique number appearing. Then $T_k = G_1 + \dots + G_k$, where $G_k$ are independent with $G_k\simeq \mathrm{Geo}(\frac{n-k+1}{n})$. Despite they have different distribution, the CLT (e.g. in the Lindeberg form) can be applied for $k = cn$, $c\in(0,1)$. In order to deduce the asymptotic normality for $Z$ from here, notice that $\{Z_{m}\ge k\} = \{T_k\le m\}$.

TLDR: you have the desired statement for any $c<1-e^{-d}$.

Let $A_i = \{\text{the number $i$ is chosen}\}$. Then the expectation of $Z_{nd}$ is $$ \mathrm{E}[Z_{nd}] = \mathrm{E}\Big[ \sum_{i=1}^{n} \mathbf{1}_{A_i}\Big] = \sum_{i=1}^n \left(1 - \mathrm{P}(A_i^c)\right) = n \left(1 - \Big(1-\frac1n\Big)^{nd}\right)\approx n (1-e^{-d}). $$

zhoraster
  • 25,481
  • Can you show how to deduce those facts? Or provide a reference for those facts so I can see how that is worked out? (in particular regarding the error of the approximation) – JJMalone Aug 14 '17 at 20:16
  • @JJMalone, the expectation part should not be a problem for you. Concerning the asymptotic normality, I gave some ideas. Unfortunately, no references for you. But currently my master student is writing a paper on this problem, it may be finished soon. – zhoraster Aug 15 '17 at 09:42
  • @zhoraster Maybe I'm just misunderstanding, but when selecting n integers with replacement from 1...n, a quick test in python seems to indicate I get roughly n/e numbers selected uniquely. Above it looks like you are claiming it is (1-1/e)n, which looks like you are calculating the opposite number (how many in that range are not selected exactly 1 time). Did I misunderstand something? – BuddyJohn Aug 19 '17 at 22:22
  • @BuddyJohn, see the edit and check your code. – zhoraster Aug 20 '17 at 09:54
  • @zhoraster Okay, I see. I interpreted "unique" differently. I took it to mean making nd selections, and how many of the selections are unique (ie. the number was selected exactly one time). And rereading, that does not appear to be the intention. – BuddyJohn Aug 22 '17 at 11:15