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.
Best Answer
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}.$$