Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $D$ be the amount of distinct numbers in a sequence of $k$ random numbers in range $[1,\ldots,n]$ (n>k). I want to show that: $D=\Omega(k)$ with exponential high probability. I'm interested in the case where $k/n \rightarrow 0$, e.g., $k=\sqrt{n}$.

I tried the following approach:

$D$ is the amount of nonempty bins when throwing $k$ balls into $n$ bins. $Y$ is the amount of empty bins when throwing $k$ balls into $n$ bins. So, $D=n-Y$.

Now, using Chernoff bound and the fact that $\text{E}[Y]=ne^{\frac{-k}{n}}$:

$$\begin{align}\Pr(Y>(1+\delta)\text{E}[Y])\le 2^{-\delta \text{E}[Y]}\\ \Pr(D<n-(1+\delta)\text{E}[Y])\le 2^{-\delta \text{E}[Y]}\end{align}$$

where $\delta>2e-1$.

I want to find $\Pr(D<\beta k)$, but to do so I have to take $\delta=\frac{n-\beta k-\text{E}[Y]}{\text{E}[Y]}$ which is negative since $\text{E}[Y]\rightarrow n$.

What I'm doing wrong, or there is some other way to show that $D=\Omega(k)$ with exponential high probability? Or maybe this statement is wrong?

Thanks!

share|improve this question
1  
Your first task is to make precise the asymptotics you consider: $k\to\infty$ and $n\gt k$ but how? $n=k+1$, or $n\gg k$, or $n/k\to\alpha$ positive and finite? –  Did Jan 27 '13 at 16:22
    
Thank for the comment. I'm interested in the case where $k/n \rightarrow 0$, e.g., $k=\sqrt{n}$. –  Michael Jan 27 '13 at 16:27
add comment

1 Answer

up vote 3 down vote accepted

so I have to take $\delta=\frac{n-\beta k-\text{E}[Y]}{\text{E}[Y]}$ which is negative since $\text{E}[Y]\rightarrow\infty$ (first version of the question), or $\text{E}[Y]\rightarrow n$ (revised version of the question).

Not quite...

  • First, the mean of $Y$ is not what you write but $\mathbb E(Y)=n\left(1-\frac1n\right)^k$.
  • Second, $\delta$ has the sign of the numerator divided by $n$, which is $$ \gamma=1-\beta\frac{k}n-\left(1-\frac1n\right)^k. $$ For every fixed $\beta\lt1$, when $n\to\infty$ with $k\ll n$, one gets $$ \gamma=1-\beta\frac{k}n-\left(1-\frac{k}n+o\left(\frac{k}n\right)\right)\sim(1-\beta)\frac{k}n, $$ hence $\gamma\gt0$ for every $n$ large enough.

Edit: One can control the distribution of $D$ as follows. Consider the event $[D\leqslant k-i]$ and choose the $k$ numbers sequentially. Then $D\leqslant k-i$ means that at least $i$ times, one chooses an already chosen number. This happens each time with probability $\leqslant\frac{k}n$ and there are $\binom{k}i\leqslant2^k$ ways of choosing these $i$ moments, hence $\mathbb P(D\leqslant k-i)\leqslant2^k\left(\frac{k}n\right)^i$ $(\ast)$.

For example, $\mathbb P(D\leqslant\frac12k)\leqslant\mathrm e^{-\Lambda(n,k)}$ with $\Lambda(n,k)=-\frac12k\log\left(\frac{k}n\right)-k\log2$. One sees that, if $1\ll k\ll n$, then $\Lambda(n,k)\gg k$ hence the control on $\mathbb P(D\leqslant\frac12k)$ is at least exponential in $k$.

Edit 2: To see that $(\ast)$ holds, for every subset $I$ of $\{1,2,\ldots,k\}$ of size $i$, call $A_I$ the event that at every time in $I$ one chooses an already chosen number and at every time not in $I$ but earlier than some element in $I$ one chooses a new number (at every time not in $I$ later than the whole set $I$, the choice is free). Then the events $A_I$ are disjoint and their union over every $I$ of size $i$ included in $\{1,2,\ldots,k\}$ is $[D\leqslant k-i]$. There are exactly ${k\choose i}\leqslant2^k$ such sets $I$, and for every such set $I$, $\mathbb P(A_I)\leqslant\left(\frac{k}n\right)^i$. The upper bound of $\mathbb P(D\leqslant k-i)$ follows.

share|improve this answer
    
Thanks Did! I will check it tonight. –  Michael Jan 27 '13 at 16:47
    
No, it didn't work... to use this formula ($2^{-\delta \text{E}[Y]}$), we have to ensure that $\delta > 2e-1$ which is not the case here... And if I use the general Chernoff bound: $$\Pr(D<n-(1+\delta)\text{E}[Y])\le \left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\text{E}[Y]},$$ I get that this probability goes to 1 and not to 0... So maybe the statement that $D=\Omega(k)$ w.h.p. is not correct? –  Michael Jan 28 '13 at 9:29
1  
Hmmm, rather unconventional, I would say. // Anyway, see Edit. –  Did Jan 28 '13 at 14:00
1  
Forget my last comment and see Edit 2. –  Did Feb 18 '13 at 17:14
1  
No. Please read: for every subset $I$ of {1,2,…,k} of size $i$, *call $A_I$ the event*... and, later on, *There are exactly ${k\choose i}$*... **such sets** $I$. –  Did Feb 19 '13 at 7:58
show 8 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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