Balls from bin with replacement, distinct elements, concentration inequality

Question

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

Answer 1

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