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?

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?

Update (April 18th): I rewrote the probability of an element being unique in a selected set of $S*L$ elements, and this agrees well with simulation. However, my final step, where I use the binomial formula to calculate the probability that one of the $m$ multisets has at least $k$ unique elements... still fails to match simulations. I suspect I'm failing to understand how to treat dependencies.

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

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?

Update (April 18th): I rewrote the probability of an element being unique in a selected set of $S*L$ elements, and this agrees well with simulation. However, my final step, where I use the binomial formula to calculate the probability that one of the $m$ multisets has at least $k$ unique elements... still fails to match simulations. I suspect I'm failing to understand how to treat dependencies.

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*r*{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?

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?

Update (April 18th): I rewrote the probability of an element being unique in a selected set of $S*L$ elements, and this agrees well with simulation. However, my final step, where I use the binomial formula to calculate the probability that one of the $m$ multisets has at least $k$ unique elements... still fails to match simulations. I suspect I'm failing to understand how to treat dependencies.

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?