Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 0 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.