Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say that I have a set of unique elements, $P$, and a multiset $M$ that I fill with $N \leq ||P||$ elements by sampling with replacement from $P$. What is the probability that the multiset $M$ contains $0 \leq k \leq N$ elements that occur once (i.e. elements with only a single copy in the multiset)?

The probability of a single element in a multiset of cardinality $N$ occurring only once should be equivalent to tossing $N$ balls into $||P||$ bins, and finding the probability that a particular ball is by itself in a bin.


To get started...

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

P[$r$] = ${N \choose r}$ $(\frac{1}{||P||})^r(1-\frac{1}{||P||})^{(N-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] = $||P||*r*{N \choose r}$ $(\frac{1}{||P||})^r(1-\frac{1}{||P||})^{(N-r)}$

For $r = 1$, $E[X] = N*(1-\frac{1}{||P||})^{N-1}$

share|improve this question
    
Just count: How many possibilities to choose N elements of p elements and then linearly ordering them? How many possibilities to choose N times one of p elements? And then you do division. –  Phira Apr 19 '11 at 22:35

1 Answer 1

up vote 2 down vote accepted

This is another variant on the birthday problem and the coupon collector's problem. Let's say there are $p$ elements of $P$ (possible birthdays) and a sample size with replacement of $n$ (people in the room). $k$ is then the number of people who do not share a birthday with anyone else in the room.

The expected number who do not share a birthday (i.e. $E[K]$) is not as difficult to state:
$$n \left(1-\frac{1}{p}\right)^{n-1}$$ while the variance is: $$n \left(1-\frac{1}{p}\right)^{n-1} + n (n-1) \left(1-\frac{1}{p}\right) \left(1-\frac{2}{p}\right)^{n-2} - n^2 \left(1-\frac{1}{p}\right)^{2(n-1)}.$$

These are similar in form to the expressions I gave on a similar question for number of distinct birthdays (distinct elements of $M$ in your question).

Added:

I think you can calculate the numbers using the following integer recurrence:

$$f(a,b,c,d) = (d-b+1) f(a-1,b-1,c-1,d) + (b-a) f(a,b,c-1,d) + (a+1) f(a+1,b,c-1,d)$$

starting at $f(a,b,0,d)=0$ except that $f(0,0,0,d)=1$. The probabilities you are looking for will then be

$$Pr(K=k|n,p) = p^{-n} \sum_b f(k,b,n,p).$$

As an example, looking at $n=5$ and $p=10$, you should find $f(0,1,5,10) = 10$, $f(0,2,5,10) = 900$, $f(1,2,5,10) = 450$, $f(1,3,5,10) = 10800$, $f(2,3,5,10) = 7200$, $f(3,4,5,10) = 50400$, and $f(5,5,5,10) = 30240$. This will lead to probabilities for the number of unique elements of

  • $Pr(K=0|n=5, p=10) = 0.0091$,
  • $Pr(K=1|n=5, p=10) = 0.1125$,
  • $Pr(K=2|n=5, p=10) = 0.0720$,
  • $Pr(K=3|n=5, p=10) = 0.5040$,
  • $Pr(K=4|n=5, p=10) = 0$, and
  • $Pr(K=5|n=5, p=10) = 0.3024$.

Given the lack of an obvious pattern in these probabilities as $k$ increases, I think there is unlikely to be a simple closed form in general.

share|improve this answer
    
Dear Henry, yes I noticed the answer you were referring too earlier! =) My E[X] for the expected number of balls that exist in bins with no other balls should be equivalent to your E[K]. I'm just having trouble understanding how to do the calculation for different values $k$. –  user8861 Apr 19 '11 at 23:31
    
According to Mathematica, for $r = 1$ my expression for E[X] is exactly your expression for E[K]. –  user8861 Apr 19 '11 at 23:37
    
The expectation is easy: identifying a particular ball, the probability another identified ball is not in the same urn is $(1-1/p)$ so the probability all the other $n-1$ balls are not in the same urn is $(1-1/p)^{n-1}$ and so the expected number of lonely balls is $n(1-1/p)^{n-1}$. –  Henry Apr 19 '11 at 23:53
    
@Henry, I did simulations for your example with about $10^6$ iterations, and they seem to converge to your values. Nice work, now I just need to understand where you're coming from... –  user8861 Apr 20 '11 at 1:22
1  
After you have introduced a new ball, there were three possibilities: (1) it went in an empty urn; (2) it went in an urn which already had multiple balls; (3) it went in an urn with previously has a lonely ball. $a$ is the number of lonely balls, $b$ is the number of occupied urns, $c$ is the total number of balls so far, $d$ is the number of urns, and $f$ is the number of possibilities. –  Henry Apr 20 '11 at 22:50

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.