Card Collection and Expected Time to Collect All Kinds

303 Views Asked by At

Suppose a deck of cards consists of 10 cards. Each card can be of different type (e.g. A, B, C, ...). There are two rare kinds: A and B. Each occurs in a card with probability $p$. And we assume that whether A occurs is independent of whether $B$ occurs. The question is the expected number of decks to buy in order to have at least one $A$ and one $B$.

This question sounds very similar to the coupon collection problem (https://en.wikipedia.org/wiki/Coupon_collector%27s_problem). My approach to solve is: each card needs $1/p$ times to be "successful". So averagely we need $2/p$ decks.

Does it make sense?

2

There are 2 best solutions below

0
On

It is simpler to first consider the number of cards rather than the number of decks. Let $X$ be the number of cards you need to draw to obtain at least one type $A$ card and one type $B$ card.

$X$ is a discrete random variable because its value changes depending on the randomness of the card draws. Clearly, the minimum is two (e.g., you draw two cards and you get one $A$ card and one $B$ card) and the maximum is $\infty$ (e.g., you need a very large number of draws to get the cards).

Ultimately, you want to keep drawing cards until you get both an $A$ and $B$ card. As a result, your last card will either be an $A$ or $B$. This gives us two scenarios:

  • Your last card is an $A$ card
  • Your last card is a $B$ card

Now, let $n$ be the number of card draws. Then you have a combined probability:

$$ \text{P} \left(X=n\right)=\text{P}\left( \text{draw A last} \right)+\text{P}\left( \text{draw B last} \right) $$

What are the probabilities on the right hand side? We'll take the case of drawing $A$ last as an example. In this specific scenario, we draw $A$ last but get $B$ (but not $A$) in the first through penultimate draws. However, we can also draw more than one $B$ card in the process. We can model this event with inspiration from the negative binomial distribution. Let $p_A$ be the probability of drawing an $A$ card from one draw and $p_B$ be the probability of drawing a $B$ card from one draw. Then:

$$ \text{P} \left( \text{draw A last} \right)= p_A \sum_{k=1}^{n-1} \binom{n-1}{k} p_B^k \left(1-p_A-p_B \right)^{(n-1)-k} $$

Here, the summation term represents all the ways of drawing at least one $B$ card but not any $A$ cards. It follows that the expression for $\text{P} \left( \text{draw B last} \right)$ is the same except you need to switch $A$ and $B$.

In your specific problem, you have the simplification that $p=p_A=p_B$. Applying this and combining the two scenarios, you get a total probability:

$$ \text{P} \left( X=n \right)=2 \sum_{k=1}^{n-1} p^{k+1} \left( 1-2p \right)^{(n-1)-k} $$

Using the definition of the expectation and noting that the minimum number of draws is 2, we have that:

$$ \text{E} \left( X \right)=2 \sum_{i=2}^\infty i \sum_{k=1}^{i-1} \binom{k}{i-1} p^{k+1} \left(1-2p\right)^{(i-1)-k} $$

Thus, your final solution is $\text{E} (X)$ cards. You simply need to divide by the number of cards in a deck to get the number of decks (and then round up because you can't get a partial deck). In practice, you can't sum to infinity, so you choose a large number up to which to sum. There might be a simpler form for $\text{E} (X)$ using geometric series or some other infinite series simplification.

As an example, I calculated an expected value of 15 cards for $p=0.1$. This is smaller than $\frac{2}{p}=20$ cards because, while the individual probabilities are independent, the outcome with respect to the number of $A$ and $B$ cards drawn is not.

0
On

It's simpler to compute the expected number of cards drawn rather than the number of decks.

The probability of drawing an A or a B is $2p$, so the expected number of cards drawn until one of these (an A or a B) is seen is $1/(2p)$. Then the probability of drawing the next card of interest (an A if a B was drawn, or a B if an A was drawn) is $p$, so the expected number of draws required is $1/p$. In all $$\frac{1}{2p} + \frac{1}{p} = \frac{3}{2p}$$ draws are required, on average.