Probability of not choosing from a set of replaced values The problem statement is as follows:
There is a set of numbers N numbers $1..N$  (eg: N = $10^6$)
N numbers are chosen uniformly and independently with replacement

I would like to be able to answer questions in the following form:


*

*What is the probability that at least 1 number is not chosen?

*What is the probability that 5% of the N numbers are not chosen?

*What is the probability that greater than 10% of the N numbers are not chosen?
My initial approach is to say, what's the probability that the same number was chosen every single of the N-times, that would be $(\frac{1}{N})^N$ and for an N of 100 that would be the expectation that 99% of the numbers were not chosen.
 A: I'll solve this in more generality, since questions like this keep coming up and we need a standard answer to mark them as a duplicate of. So I'll calculate the probabilities for exactly $k$ bins to be empty and for at least $k$ bins to be empty when $m$ balls are distributed uniformly randomly over $n$ bins. Your case is $n=m=N$, with various $k$ given in your three questions.
The probability for $j$ particular bins to be empty is
$$
\left(1-\frac jn\right)^m\;.
$$
Thus, by inclusion-exclusion, the probability for exactly $k$ bins to be empty is
$$
\sum_{j=k}^n(-1)^{j-k}\binom nj\binom jk\left(1-\frac jn\right)^m\;.
$$
Then the probability for at least $k$ bins to be empty is
\begin{align}
\sum_{l=k}^n\sum_{j=l}^n(-1)^{j-l}\binom nj\binom jl\left(1-\frac jn\right)^m
&=
\sum_{j=k}^n\sum_{l=k}^j(-1)^{j-l}\binom nj\binom jl\left(1-\frac jn\right)^m
\\
&=
\sum_{j=k}^n(-1)^{j-k}\binom nj\binom{j-1}{k-1}\left(1-\frac jn\right)^m\;,\end{align}
the same as the result for exactly $k$ bins but with $\binom{j-1}{k-1}$.
You also wanted the probability for more than $k$ bins to be empty, which is the probability for at least $k$ bins to be empty minus the probability for exactly $k$ bins to be empty:
$$
\sum_{j=k}^n(-1)^{j-k}\binom nj\left(\binom{j-1}{k-1}-\binom jk\right)\left(1-\frac jn\right)^m=\sum_{j=k}^n(-1)^{j-k+1}\binom nj\binom{j-1}k\left(1-\frac jn\right)^m\;,
$$
again of the same form, but now with $\binom{j-1}k$ and with signs reversed.
Edit in response to the comment:
If $m$ and $n$ are large, with $m=\alpha n$ (i.e. in your case $\alpha=1$), we have
$$
\left(1-\frac jn\right)^m=\left(1-\frac{\alpha j}m\right)^m\approx\mathrm e^{-\alpha j}\;.
$$
Then
\begin{align}
\sum_{j=k}^n(-1)^{j-k}\binom nj\binom jk\left(1-\frac jn\right)^m
&\approx\sum_{j=k}^n(-1)^{j-k}\binom nj\binom jke^{-\alpha j}
\\
&=\binom nk(\mathrm e^{-\alpha})^k\left(1-\mathrm e^{-\alpha}\right)^{n-k}\;,
\end{align}
a binomial distribution with probability $\mathrm e^{-\alpha}$, as in this case the events of individual bins being empty are approximately independent and the probability for a bin to be empty is roughly $\mathrm e^{-\alpha}$. The probability for at least $k$ bins to be empty (which in this case is approximately the same as the probability for more than $k$ bins to be empty) can then be approximated using one of the known approximations to the binomial distribution, e.g. the normal approximation by the normal distribution $\mathcal N\left(n\mathrm e^{-\alpha},n\mathrm e^{-\alpha}\left(1-\mathrm e^{-\alpha}\right)\right)$, with
$$
\textsf{Pr}(K\ge k)\approx\frac12\left(1-\operatorname{erf}\left(\frac{k-n\mathrm e^{-\alpha}}{\sqrt2n\mathrm e^{-\alpha}\left(1-\mathrm e^{-\alpha}\right)}\right)\right)
$$
