# Drawing Cards and Expected Value

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.

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.