10
$\begingroup$

I have the following problem:

I have 100 unique items (n), and I'm selecting 43 (m) of them one at a time (with replacement).

I need to solve for the expected number of uniques (only selected once, k = 1), doubles (selected exactly twice k = 2), tripples (exactly k =3), quads etc...

I've been able to find plenty of results on the probability of there being at least one double (birthday paradox), but not on the expected number of pairs in the population.

$\endgroup$
  • $\begingroup$ Would a Monte Carlo estimate be useful to you, or do you need the answer in a closed form? $\endgroup$ – David J. Harris Apr 26 '13 at 15:56
  • $\begingroup$ I would prefer a closed form formula so I can easily apply it to different values of n, m and k. $\endgroup$ – Kaitlyn K Apr 26 '13 at 17:04
7
$\begingroup$

The $i^{th}$ iterm will be selected $\text{Binom}(m, \, 1/n)$ times. From this, you can find all the quantities you want, because, e.g., $$\mathbb{E}[\text{number of pairs}] = \sum_{i = 1}^n \mathbb{P}[i^{th} \text{ item appears twice}] $$ For example, the expected number of pairs is given by $$ n \cdot \mathbb{P}[\text{Binom}(m, \, 1/n) = 2]. $$

You can get the numeric value in R with the command n*dbinom(k, m, 1/n).

$\endgroup$
  • $\begingroup$ Can that formula be used for a k=0 or 1? $\endgroup$ – Kaitlyn K Apr 26 '13 at 20:00
  • $\begingroup$ Yes it can. With k = 0, you can interpret it as `how many points will not appear among the m selected ones'. $\endgroup$ – Stefan Wager Apr 26 '13 at 23:11
  • $\begingroup$ But these events are not independent. E.g. when item 1 appears m times, then no other items can ever appear. You cannot simply add up the P's. $\endgroup$ – asterix314 Aug 28 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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