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)$

  • $\begingroup$ 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? $\endgroup$ – joriki Apr 8 '11 at 5:28
  • 1
    $\begingroup$ @joriki: didn't you remember the number of the user? ;-) $\endgroup$ – Fabian Apr 8 '11 at 5:59
  • $\begingroup$ @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. $\endgroup$ – user8861 Apr 8 '11 at 6:10
  • $\begingroup$ @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. $\endgroup$ – joriki Apr 8 '11 at 6:40
  • $\begingroup$ @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. $\endgroup$ – 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.

It looks like you use a product like the second one in the rest of your calculations, so whatever error led you to it seems to have propagated, although I am rather suspicious of some of the other steps, too.

  • $\begingroup$ "you are using P rather than N to mean #P." - fixed! Thanks for the heads up. $\endgroup$ – user8861 Apr 10 '11 at 9:13
  • $\begingroup$ My original expression was missing a set of parentheses, and should now be fixed... $\endgroup$ – user8861 Apr 13 '11 at 1:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.