Probability of having at least 'k' marbles specific to each of 'm' bags filled by sampling with replacement

I'm going to rewrite my original question to make it a bit clearer:

Assume I have some set $P$ with $||P|| = N$ unique elements. I also have $S$ multisets, $(m_1, ..., m_S)$, of cardinality $L$, consisting of elements in $P$ chosen with uniform probability. We call a multiset, $m_i$, 'distinguishable' if it contains at least $k$ elements, though not necessarily distinct elements, that exist in no other multiset.

What is the probability of all $M$ multisets being 'distinguishable' according to this definition?

While sampling $S$ times with replacement from the set $P$, we can state the probability of never choosing the same element twice as:

Prob( $S$ unique selections from $P$ ) = $\prod \frac{(N - i)}{N}$ for $i = 0$ to $(S - 1)$

Or equivalently, we can calculate the probability that the multiset of $S$ sampled elements contains all unique elements as:

Prob( $S$ unique selections from $P$ ) = $\prod ((1-(\frac{1}{N - i}))^{(S - 1 - i)})$ for $i = 0$ to $(S - 1)$

• There was a question yesterday that was formulated differently, about "pruning" of multisets, but AFAIR was effectively the same question. I can't find it anymore; it may have been deleted. Was that question by you, too? – joriki Apr 8 '11 at 5:28
• @joriki: didn't you remember the number of the user? ;-) – Fabian Apr 8 '11 at 5:59
• @joriki, yes, alas, that was me... number 8861. I wanted to spend more time thinking about the question before posting it here, so I put up the 'pruning' example, then decided to take it down after about 20 minutes. Sorry if that was a faux pas. – user8861 Apr 8 '11 at 6:10
• @user8861: I wouldn't go so far as to call it a faux pas, but you could have mentioned it briefly in the question so that people who'd seen the other question wouldn't go looking for it to mark this as a duplicate. – joriki Apr 8 '11 at 6:40
• @joriki, fair enough, and thanks for looking at the original version! The reason I didn't mention it was mostly because I didn't want to confuse things, and the site told me that ~5 people looked at the original. I'm actually a bit surprised anyone noticed this as a rephrasing. – user8861 Apr 8 '11 at 6:55

This seems like an interesting problem even for $k=1$, which I would solve before attacking the more general version.
Your first calculation for the probability that a multiset has distinct elements is correct, although you are using $P$ rather than $N$ to mean $\#P$.
Your second calculation is unjustified and incorrect. You can compare it with the correct one. Suppose $N=10$ and $\#S=4$. The probability that $4$ draws are distinct is $\frac{10}{10} \times \frac{9}{10} \times \frac{8}{10} \times \frac {7}{10} = \frac{504}{1000} = 0.504$. Your second expression says $(1-\frac{1}{10}^3) \times (1-\frac{1}{9}^2) \times (1-\frac{1}{8}^1) \times (1-\frac{1}{7}^0)$. That last term is $0$, which makes the whole product $0$. If we leave it out, we get $\frac{259}{300} = 0.86333...$ which is quite different from the correct value.