3
$\begingroup$

Problem: Suppose you have a set of p elements and during each trial, you randomly and uniformly select r elements from that set with replacement. What is the probability distribution for the number of trials it would take for every element of that set to have been selected at least once?

Example: You have a standard deck of 52 cards, and during each trial you randomly select 5 cards from the deck. What is the probability distribution for the number of trials it would take for you to have held every card in the deck?

Notes: I've worked out that the probability of drawing i new elements when you've already seen $p-t$ elements is

$$\dfrac {\binom{p-t}{r-i} \binom {t} {i}} {\binom{p}{r}}$$

But I'm not sure how this could be used to get the distribution for the number of trials it would take for there to be no new elements. I suspect that this probability distribution is geometric.

$\endgroup$
1
$\begingroup$

I'm making the assumption that each trial's sample of size $r$ is conducted with replacement and there is replacement between each trial, I believe that's the intention. Note that I'll use $n$ to mean the number of elements ($p$ will be used for probability).

The special case where $r=1$ is known as the Coupon Collector's Problem. More details can be found here: https://en.wikipedia.org/wiki/Coupon_collector%27s_problem. In short, each individual trial is geometrically distributed but the whole process (number of trails conducted to select each unique item) is not geometrically distributed as the probability updates with each trial (sample). While the expectation of the geometric distribution is $E(X)=1/p$ the expectation of the Coupon Collector's Problem is $E(T)=n \times (1/1 + 1/2 + ... + 1/n)$ where $T=$ number of trials. If we plug in the deck of cards example but set $r=1$ we see that $E(T)=52 \times (1/1 + 1/2 + ... + 1/52) \approx 235.98$ trials.

For cases of $r>1$ we're effectively still running the same Coupon Collector's Problem but conducting our samples in batches. Assuming $n=52$, the impact, roughly speaking, is that the expectation is reduced by $1/r$, or, $E(T) \approx 52/r \times (1/1 + 1/2 + ... + 1/52) \approx 47.20$. The reason the result is approximate and not exact is the error introduced during the final trial. Imagine the unique (and highly unlikely) case that during the first 10 trials we selected only unique cards with $r=5$. This means we only need 2 more unique cards during trial 11 but there are several unique paths that can get us those 2 cards when we go to draw 5 times. This effectively boosts the probability of achieving our result during the final trial.

I ran a simulation of the deck of cards example using the R language with results aligned to the expected values noted above using $r=1$ and $r=5$. The distribution has asymptotic tails (obviously truncated on the left) and is heavily right-skewed. Adjusting $r$ simply slides (shifts) the distribution left or right (holding the same shape) as expected.

$\endgroup$

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.