I would like to know that probability of an item occurring in a multiset (a combination of selections with repetitions).

Given a set $S = \{x_1,x_2,...,x_n\}$ the number of possible unordered subsets of size $k$ that can be chosen with repetitions is:

$${\left(n\choose k\right)} = {n + k - 1\choose k}$$

So if I want to know the probability that any given $x$ occurs in at least one of these multisets, how do I find it?

More Info

I'm trying to come up with a random variable $X_i$ which represents the probability that $x_i$ occurs at least once in a multiset.


If you pick one element uniformly at random from $S$, there is a probability of $\frac{n-1}n$ of not getting a fixed element $x \in S$. You do this $k$ times, the probability of not getting any $x$'s is $\left(\frac{n-1}{n}\right)^k$. Subtract this from $1$ to get the probability of getting at least one $x$.

I assume that the distribution of picking an element is uniform, but the distribution of multisets is not.

If you assume the distribution of multisets is uniform, then you would divide the number of sets having $x$ by the number of sets not having $x$. The number of multisubsets of $S$ of size $k$ not having $x$ is the same as the number of multisubsets of $S - \{x\}$ of size $k$, which is ${n + k - 2 \choose k}$. Therefore, the probability of not having $x$ in the multiset is $\frac{n + k - 2 \choose k}{n + k - 2 \choose k} = \frac{n-1}{n+k-1}$, and the answer to the question (the probability of finding $x$ at least once in the multiset) is $1-\frac{n-1}{n+k-1}=\frac k{n+k-1}$.

  • 1
    $\begingroup$ But the mentioned procedure is not at all one of selecting a size $k$ multiset on $S$ uniformly at random! For instance there are $\binom54=5$ size $4$ multiset of $\{A,B\}$, all but one of which contain $A$, so you sohuld get $80$% in this case. $\endgroup$ – Marc van Leeuwen Jan 28 '13 at 12:53
  • 1
    $\begingroup$ @MarcvanLeeuwen I realized that and I edited my answer, but then the OP accepted my answer, so I removed that part. Since you made a comment about that, I retyped it. $\endgroup$ – Tunococ Jan 28 '13 at 12:58
  • 1
    $\begingroup$ Good, +1. I've corrected a typo in the formula and also added the formula for the complementary probability that was asked for. $\endgroup$ – Marc van Leeuwen Jan 28 '13 at 13:10
  • $\begingroup$ @MarcvanLeeuwen Thank you. I forgot what the final answer was supposed to be :P $\endgroup$ – Tunococ Jan 28 '13 at 13:13
  • $\begingroup$ i accepted the first answer b/c i think i may have been misguided in using multisets in the first place. the original problem was "there are k ppl on an elevator on the ground floor, each wants to get off at a random floor of the n upper floors, so what's the expected # of lift stops." the best approach is w/ a rand var $X_i$ for the probability that >= 1 ppl get off at floor $x$. i saw it as a multiset problem, though as the first part of the answer shows, it's more like picking elements uniformly at random. $\endgroup$ – aaronstacy Jan 29 '13 at 12:38

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.