Had to think about this one for a while! A quick note about terminology: "expected", "average", and "mean" typically mean the same thing in statistics, but that's not what you're looking for here. In operational terms, the "expected number of draws needed" is what you would get by drawing until you got all
N balls, writing down the number of draws it took you, and then repeating the experiment many times to get an average. What you want is for a number of draws
D, what is the probability
P to draw each ball in
D draws or less. As far as I can tell, this is a significantly tougher problem. My solution isn't super-elegant, but I think it works; please point out any errors you see, or any cleaner solutions.
When faced with a problem of the form "what is the probability of
x happening at least once?" it often helps to re-frame it as "what is the probability of
x not happening at all?" Since
x must either happen or not happen, you can subtract the answer to either problem from 1 to get the answer to the other. In this case, the re-framed question becomes "what is the probability that one or more balls will never be drawn across
D attempts?" For starters, we can note that for a given draw, any particular ball will
not be drawn with probability $$\frac{N-1}{N}$$. The probability of a given ball not being drawn during
D consecutive attempts is then $$\left(\frac{N-1}{N}\right)^D$$. Since any of the
N balls not being drawn is sufficient for failure, we might naively just multiply this probability by
N:
$$1-P\approx N\left(\frac{N-1}{N}\right)^D$$
Unfortunately, this expression is too high, because it over counts the cases in which
more than one ball is never drawn. For example, the above expression includes probabilities for both "ball 1 was never drawn" and "ball 2 was never drawn", both of which will include cases where neither ball 1 nor ball 2 was drawn. To correct such double-counted events, we can subtract off the cases where two given balls are never drawn. By similar logic to above, the probability of each one of these cases is $$\left(\frac{N-2}{N}\right)^D$$. How many such cases are there? We want all the ways to choose 2 elements out of a list of
N options, which is the choose function $${N \choose 2}$$. This gives us the less-naive estimate
$$1-P\approx N\left(\frac{N-1}{N}\right)^D-{N \choose 2}\left(\frac{N-2}{N}\right)^D$$
While this is better, we now face the problem of under-counting cases in which
three balls are never drawn. Just counting by hand, we can find that we need one more copy of each triple-failure case, so we need to add an extra $${N \choose 3}\left(\frac{N-3}{N}\right)^D$$. By now, we see that every change we make will force a higher-order correction, but fortunately, a pattern is emerging. For even-
n terms, we subtract $${N \choose n}\left(\frac{N-n}{N}\right)^D$$, while for odd-
n terms, we add the same. Formally, we know this pattern will hold for all
n from the identity
$$\displaystyle\sum_{n=1}^N (-1)^{n-1}{N \choose n}=1$$
I leave the proof of this as an exercise to the reader.
Carrying this pattern through all the way to the end, we finally get the exact expression we want:
$$1-P = \displaystyle\sum_{n=1}^N (-1)^{n-1}{N \choose n}\left(\frac{N-n}{N}\right)^D$$
Not too shabby! There are a number of ways one can shuffle the terms in this sum around and pull out common factors, but I couldn't find anything that really simplified it. Please let me know if you see any improvements!
