# Probability of an item being selected in a multiset

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?

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$.
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}$.
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. – Marc van Leeuwen Jan 28 '13 at 12:53
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. – aaronstacy Jan 29 '13 at 12:38