Expected number of duplicates (triplicates etc) when drawing with replacement

Question

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.

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

score 7 · Accepted Answer · answered Apr 26 '13 at 16:34

7

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).

answered Apr 26 '13 at 16:34

Stefan Wager

2,233
11
7

Can that formula be used for a k=0 or 1? – Kaitlyn K Apr 26 '13 at 20:00
Yes it can. With k = 0, you can interpret it as `how many points will not appear among the m selected ones'. – Stefan Wager Apr 26 '13 at 23:11
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. – asterix314 Aug 28 '19 at 02:10

Expected number of duplicates (triplicates etc) when drawing with replacement

1 Answers1

Linked