[Math] Drawing Cards and Expected Value

card-gamesexpected valueprobability

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.

Best Answer

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.

Related Question