12
$\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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Would a Monte Carlo estimate be useful to you, or do you need the answer in a closed form? $\endgroup$
    – David J. Harris
    Commented Apr 26, 2013 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
    Commented Apr 26, 2013 at 17:04

1 Answer 1

Reset to default
8
$\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).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can that formula be used for a k=0 or 1? $\endgroup$
    – Kaitlyn K
    Commented Apr 26, 2013 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
    Commented Apr 26, 2013 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
    Commented Aug 28, 2019 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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