If you sample $n$ integers from the range $1$ to $n$ inclusive it seems intuitive that you are likely to get a lot of numbers exactly once. Call $X\_n$ the number of integers you get that occur exactly once in your sample. Is there a nice simple way of showing the following for all $n\geq 2$.


$$\exists a,b >0\text{ such that } P(X\_n \leq an) \leq 2^{-bn} $$ 



Probability of having many unique elements
$X\_n$ is a random variable on the product space $\Omega = \{1,\ldots,n\}^n$ such that changing the value of any one coordinate of $\omega \in \Omega$ changes $X\_n(\omega)$ by at most 2. This is a classic case in which [martingale concentration inequalities](https://en.wikipedia.org/wiki/Azuma%27s_inequality) can be applied to show that $$\mathbb{P}(|X\_n - \mathbb{E}(X\_n)| \geq t) \leq 2e^{-t^2/8n}.$$ So in fact $X\_n$ almost always takes a value in some interval of length about $\sqrt n$. $\mathbb{E}(X\_n) = n(1-1/n)^{n-1} \sim n/e$, so you can find a $b$ for any $a < 1/e$.


