# Balls from bin with replacement, distinct elements, concentration inequality

Draw $n$ numbers, denoted by $a_1, a_2, \ldots, a_n$, from set $[n]$, that is, for each $i$, $a_i$ is a uniformly random number from $[n]$.

Let $A = \{a_1, a_2, \ldots, a_n\}$. Then $$\mathbb{E}[|A|] = n - n (\frac{n-1}{n})^n \approx n (1 - 1/e).$$ How to prove a concentration bound on $|A|$? For example, prove $\Pr[|A| < n / 100] < 2^{-\Omega(n)}$.

We have that $$P(|A|\le cn) \le \binom{n}{cn} c^n$$ (first choose a subset of cardinality $cn$ and then insist that all numbers come from this set). By Stirling's formula, this bound is asymptotically $$\sim \frac{1}{\sqrt{n}} \left( \frac{c}{1-c} \right)^{(1-c)n} ,$$ which is of the requested type as long as $c<1/2$.