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

Question

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?

Answer 1

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}$.

Answer 2

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.

Answer 3

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