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?



Probability of unique elements in each of 'S' multisets sampled with uniform probability
**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}$.


