# Probability of unique elements in each of 'S' multisets sampled with uniform probability

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?

Edit - I would very very interested in approximate solutions to this question! As in my "bounded ratio of two types of balls question", here $$N$$ is at least an order of magnitude larger than $$S$$, $$S > 10^3$$, and $$L$$ is relatively small (around $$10^1$$ to $$10^2$$ or so).

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

Perhaps we can simplify this problem by restricting $$k$$ to include only distinct elements, i.e elements that exist only once in all of $$(m_1, ..., m_S)$$ multisets?

Here's what I'm thinking...

We first calculate the probability that one of the $$(S*L)$$ elements in multisets $$(m_1, ..., m_S)$$, selected from $$P$$ by sampling with replacement, is selected only once. This should be equivalent to tossing $$(S*L)$$ balls into $$||P|| = N$$ bins, and finding the probability that a particular ball is by itself in a bin.

From pg. 95 of "Probability and computing: Randomized algorithms and probabilistic analysis" by Michael Mitzenmacher and Eli Upfal, when we toss $$(S*L)$$ balls into $$N$$ bins, the probability that a specific bin has exactly $$r$$ balls, P[$$r$$], is given as:

P[$$r$$] = $${S*L \choose r}$$ $$(\frac{1}{N})^r(1-\frac{1}{N})^{(S*L-r)}$$

By linearity of expectation, we can now write an expression for the expected number of balls that exist in a bin of $$r$$ balls as: E[X] = $$N*r*{S*L \choose r}$$ $$(\frac{1}{N})^r(1-\frac{1}{N})^{(S*L-r)}$$. As balls here correspond to elements in the early problem description, this implies that we can write P[element is unique] as:

P[element is unique] = $$\frac{N*(1)*{S*L \choose 1}(\frac{1}{N})^1(1-\frac{1}{N})^{(S*L-1)}}{S*L}$$

Returning to the original problem, we have $$S$$ multisets that we fill with $$L$$ elements, and we want to calculate the probability that at least $$k$$ of the elements in each multiset are unique (i.e. in all the multisets, they appear nowhere else). As we now know the probability that a particular element is unique, we can use the binomial formula to find the probability that a particular multiset contains at least $$k$$ unique elements:

P[at least 'k' elements in a particular multiset, $$m_i$$, are unique] = 1 - $$\sum^{k-1}_{i=0}[ {L \choose i}$$ * P[element is unique]$$^i$$ * (1 - P[element is unique])$$^{L-i}$$]

By linearity of expectation: $$S$$ * P[at least 'k' elements in a particular multiset, $$m_i$$, are unique] ~ # of multisets with at least $$k$$ unique elements.

To calculate the probability that all multisets contain at least $$k$$ unique elements, we should be able to write the probability as: P[at least 'k' elements in a particular multiset, $$m_i$$, are unique]$$^S$$

These calculations seem to come close to simulated data, but they're still off and I imagine this will prove to be an accident. I'd appreciate any help in finding what are probably obvious flaws? Are there issues with independence, etc?

Edit: Changed the formulas slightly, making it (hopefully) correct, but even less useful.

I think I can write down an expression for the probability, but I'm not sure how useful it is. My interpretation of the random experiment is that a random $(S\times L)$-matrix over $\{1,\ldots,N\}$ is generated by choosing the entries independently and uniform, and the $i$-th multiset is then simply the $i$-th row of this matrix. Clearly, the probability for every single matrix is $1/N^{S\cdot L}$. A matrix is good if every row contains at least $k$ entries that do not appear in any other row, so it remains to count the good matrices. Any good matrix induces a partition $\{1,\ldots,N\}=B_0\cup B_1\cup\cdots\cup B_S$, where $B_i$ for $i=1,\ldots,S$ is the set of elements occuring only in row $i$ (in particular nonempty). The number of good matrices corresponding to a given partition is $$\prod_{i=1}^S\sum_{K=k}^L\binom{L}{K}S(K,|B_i|)\cdot |B_i|!\cdot |B_0|^{L-K},$$ where $S(K,|B_i|)$ is the Stirling number of the second kind, the number of partitions of a $K$-set into exactly $|B_i|$ nonempty subsets.

Now let $\mathcal P$ be the set of ordered partitions $N=b_0+b_1+\cdots+b_S$ of $N$ into nonnegative integers, where $1\leqslant b_i\leqslant L$ for $i=1,\ldots,S$. Then the total number of good matrices can be written as $$A=\sum_{(b_0,b_1,\ldots,b_S)\in\mathcal P}\binom{N}{b_1}\binom{N-b_1}{b_2}\cdots\binom{N-b_1-\cdots-b_{S-1}}{b_S}\prod_{i=1}^S\sum_{K=k}^L\binom{L}{K}S(K,b_i)\cdot b_i!\cdot b_0^{L-K},$$ and your probability is $A/N^{S\cdot L}$.

• Dear kali, I have to make sure I understand your answer, but it's actually very useful for me to know that I'm not likely to find a nice closed-form solution for this problem. – user14324 Apr 21 '11 at 16:35

Here is the case $k=1$, $S=2$, and $L\le 2$.

So we have two players who each choose $L$ many numbers among $N$ possibilities, aiming to choose something the other does not choose.

So let $p_{N,L}$ be the probability that they succeed, i.e., the two multisets are distinguishable.

Then $p_{2,L}=2^{-(2L-1)}$ for $L>0$ and for any $N$, $p_{N,1}=1-\frac1N$.

To find $p_{N,2}$ we reason as follows:

Player I chooses distinct numbers $a,b$ with probability $1-\frac1N$, in which case Player II chooses appropriately with probability $1-(2/N)^2$ (not $a,a$ or $b,b$ or $a,b$ or $b,a$).

Player II chooses nondistinct numbers $a,a$ with probability $1/N$, in which case Player II chooses appropriately (no $a$) with probability $(1-\frac1N)^2$.

Overall then $p_{3,2}=14/27$ and $$p_{N,2}=(1-\frac1N)(1-(\frac2N)^2)+\frac1N(1-\frac1N)^2$$ $$=1-4/N^2+4/N^3-2/N^2+1/N^3\approx 1-6/N^2.$$

So $p_{N,2}\rightarrow 1$ a bit faster than $p_{N,1}$, as is to be expected.

Your notations are too complicated and make it harder to see a solution. Your problems mix problems known as:

The Birthday Paradox The Classical Occupancy Problem Ion Saliu’s Paradox of N Trials

You can find solutions and also SOFTWARE here: http://saliu.com/monty-paradox.html http://saliu.com/birthday.html http://saliu.com/theory-of-probability.html