Pulling cards from a deck without replacement to reach a goal: average draws needed?

Question

I have the following probability problem that I think must be quite common. The problem is as follows:

Let's say I have a goal of drawing 3 jacks from a regular deck of 52 cards (in which there are 4 jacks). I conduct many experiments. In each experiment, I shuffle the deck and pull cards one-by-one and discard the card without replacement. When I reach my goal of having pulled 3 jacks, I write down the number of cards I had needed to pull and stop the experiment. e.g. in the first experiment I might have hit the 3rd jack on the 40th card, so I write down '40'.

I repeat this infinite times, and then average the number of cards pulled to reach 3 jacks. On average, how many cards did I need to pull before reaching 3 jacks?

Note that I am stopping after pulling the third jack, so my last draw must be a successful jack draw.

I think I can solve this problem using hypergeometric distributions, but the solution is ugly and complicated (it gives 31.8 draws on average are needed, which matches Monte Carlo simulations a colleague ran for me). I think I've stumbled upon a much simpler formula:

average draws needed = (n) * (x+1)/(y+1)

where n is the number of jacks I want (3), x is the number of cards in the deck (52), and y is the number of jacks in the deck (4).

Other than by blind luck of simple observation that I got playing around with numbers, I have no idea how to derive the above formula.

Has anyone seen this problem and know how this simple formula might be derived?

I should also note that the simple formula has been tested for many n, x, and y values and matches both the complicated formula and several simulations run for this problem. So there is a decent degree of confidence that it is correct.

Answer 1

Your formula is correct, and can be justified as follows.

There are $y$ special cards and $x-y$ regular cards in the deck. For $1\leq i\leq x-y$, define $U_i$ to be an indicator random variable which is equal to 1 if the $i^\text{th}$ regular card precedes the $n^\text{th}$ special card, and is equal to 0 otherwise.

The number of draws needed to get $n$ special cards is, $N=n+\sum_{i=1}^{x-y} U_i$. The relative order of the $y+1$ cards made up of all the special cards plus card $i$ is completely random. So the chance that $U_i = 1$ is $\frac{n}{y+1}$.

Taking the expectation of $N$ gives $$\mathbb{E}(N)=n+\sum_{i=1}^{x-y} \mathbb{P}(U_i=1)=n+(x-y)\,{n\over y+1}={n(x+1)\over y+1}.$$

Answer 2

Yes. Consider the 48 non-jacks in the deck, and how they might be distributed into the following five buckets.

• Drawn before the first jack
• Drawn between the first jack and the second jack
• Drawn between the second jack and the third jack
• Drawn between the third jack and the fourth jack
• Drawn after the fourth jack

Among all $52!$ orderings of the deck, any given card will have equally many placings in each of the five buckets, and therefore has a probability of $3/5$ of falling into one of the first three. With $48$ such cards, the expected number in the first three buckets is therefore $48\times 3/5$. Since we must also draw the three jacks themselves, the expected total number of cards we need to draw is $3+48\times 3/5 = 53\times 3/5$, or more generally, $\displaystyle\frac {n(x+1)}{y+1}$.

Answer 3

Let $f(n,x,y)$ denote the expected number for $n$ of $y$ jacks in a deck of $x$ cards. Then for $n>1$ $$\tag1f(n,x,y)=1 +\frac yxf(n-1,x-1,y-1)+\frac{x- y}xf(n,x-1,y)$$ (you must make one move and then have one of two possible simpler problems depending on whether that was a jack or not) and $$\tag2f(0,x,y)=0$$ (you are "ready before you begin"). Your conjecture $f(n,x,y)= \frac{(x+1)n}{y+1}$ is certainly valid for $n=0$ as it matches $(2)$. But it also matches the recursion $(1)$, as indeed:

$$1+\frac yx \cdot \frac{(n-1)x}y+\frac{x-y}x\cdot\frac{n x}{y+1} =\frac{n(x+1)}{y+1}.$$ Therefore $f(m,x,y)=\frac{n(x+1)}{y+1}$ holds generally.

Answer 4

Here is an alternative explanation. The indices of the $y$ jacks in a thoroughly shuffled deck of size $x$ is a random sample $\{i_1,i_2,\dots, i_y\}$ drawn from the set $\{1,2,\dots, x\}$. That is, all subsets of size $y$ are equally likely to occur.

Using the argument from " Why does this expected value simplify as shown? " (and changing notation), the expected value of the $n$th order statistic is $$\mathbb{E}(i_{(n)})=n\,{x+1\over y+1}.$$ This is the average position of the $n$th jack in a well-shuffled deck.