0
$\begingroup$

In many strategic board games, there is a stack of cards with events. I'm interested in the number of cards that need to be drawn until you can expect a certain card or a combination of certain cards to occur.

The following example: There is a deck with 20 unique cards (e.g. 1 - 20), drawn without returning.

  1. How many cards must be drawn before you can expect a certain card (e.g. 7) to be drawn?

  2. How many cards must be drawn before you can expect two specific cards (e.g. 3 and 5) to be drawn (order is irrelevant)?

  3. how many cards must be drawn before you can expect (1) OR (2) to occur ?

As far as I understand from this related question the solution of (1) should be:

$$1 + \frac{19}{2} = 10.5$$

Is this correct and how about (2) and (3)?

Thanks for helping.

$\endgroup$
1
$\begingroup$

Suppose your deck has $n$ cards, and you are interested in the expected number of draws until a particular card is drawn. Call this $u(n)$. We condition on the result of the first draw. With probability $1/n$, it is your target, and you are done. With probability $1 - 1/n$, it is not your target: you are now in the same situation as before except that you have a deck of $n-1$ instead of $n$. Thus we have the recursion equation

$$ u(n) = 1 + \frac{n-1}{n} u(n-1) $$

The solution of this with initial condition $u(1)=1$ is $$ u(n) = \frac{n+1}{2}$$

Now consider case (2) where you are waiting for two specific cards to be drawn. Let $v(n)$ be the expected number of draws here. With probability $2/n$, the result of the first draw is one of your two target cards; the expected number of additional draws you need is then $u(n-1)$. With probability $1-2/n$, it is not one of your targets, and then your expected number of additional draws is $v(n-1)$. Thus we have the recursion

$$ v(n) = 1 + \frac{2}{n} u(n-1) + \frac{n-2}{n} v(n-1) $$ With initial condition $v(2)=2$, the solution is

$$ v(n) = \frac{2n+2}{3} $$

I'll leave case (3) to you to figure out.

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