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



Balls from bin with replacement, distinct elements, concentration inequality
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$.


