Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
This passes one simple test: the expected number of draws for 2 jacks plus the expected number for 3 should add to 53. This is because if you draw $n$ cards to get 3 jacks, counting from the other end you would draw $53-n$ to get 2. –  Ross Millikan Oct 3 '12 at 21:58
add comment

4 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
Thanks! This is exactly what I was looking for. A quick comment that the second paragraph should read "The relative order of the y+1 cards made up of..." rather than "x+1" cards. –  user43532 Oct 3 '12 at 22:41
    
@user43532 Thanks for noting the typo. –  Byron Schmuland Oct 3 '12 at 23:19
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.