We draw $m$ uniform independent random values among $n$, with $m\ge n$. We consider the probability $p(m,n)$ that not all $n$ values have been drawn. We want an upper bound within a constant factor.
The probability that a given value was not drawn is $q(m,n)=(1-1/n)^m$. If these probabilities were independent, we could use $1-(1-q(m,n))^n$ for $p(m,n)$. However the probabilities are dependent and that expression yields dead wrong values.
How can we rigorously derive an upper bound? I needs not be tight, I'd be happy with something within any constant factor.
The question's motivation is to prove that $\displaystyle\lim_{n\to+\infty}p(n\left\lceil\log_2(n)\right\rceil,n)=0$, if possible with an explicit upper bound (towards answering an often-asked question about cryptographic hashes reaching their whole stated destination set, under a random oracle model).
This itself is plausible because (as studied in the coupon collector's problem) the expected number of draws to get all $n$ values is $n(\ln(n)+\gamma)+\frac12+\mathcal O(\frac1n)$, and $n\left\lceil\log_2(n)\right\rceil$ grows faster than that, by a factor $\frac1{\ln(2)}>1$.
Best Answer
By the standard urns and balls interpretation, we have $$p(m,n)=1-\frac{n! \, S_{m,n}}{n^m}$$
where $S_{m,n}$ is the Stirling number of the second kind. Then the question is equivalent to ask for a lower bound for $S_{m,n}$. There are many, but don't expect something very neat... or practical. For example. Or this one.
Added: Still not an aswer, but another plausibility argument. The number of balls can be approximated (Poissonization) by $n$ iid Poisson variables with $\lambda=m/n$. Then the probability that all urns are occupied is
$$ 1-p(m,n) \approx \left( 1 - \exp(- \lambda)\right)^n$$
If we take $m = a \log(n) n$ and we assume that the approximation is asympotically precise, then for large $n$ we get
$$ 1-p(m,n) \approx \exp(- n^{1-a}) \to \begin{cases} 0 & a<1 \\ 1 & a>1\end{cases}$$