Suppose we draw cards out of a deck without replacement. How many cards do we expect to draw out before we get an ace?
Expected value of sums
9 Answers
It depends (slightly) on how one interprets before. There are two interpretations possible: (i) Before means not including the draw that got us the first Ace and (ii) We include in the count the draw that got us the first Ace.
There is no big difference between (i) and (ii): The count (and expectation) in (ii) is just $1$ more than the count, and expectation, in (i), We use interpretation (i). So let $W$ be the number of draws before the first Ace, not including the draw that got us the Ace. We want $E(W)$.
The argument is simple but a bit delicate, so the solution below is given in great detail. Luckily, the actual computation is almost formula-free. We use indicator random variables. Label the $48$ non-Aces $1$ to $48$. Don't bother to label the Aces.
Define random variable $X_i$ by $X_i=1$ if the card with label $i$ was drawn before any Ace, and let $X_i=0$ otherwise. Then $W=X_1+X_2+\cdots+X_{48}.$ By the linearity of expectation, which holds even when the random variables are not independent, we have $E(W)=E(X_1+X_2+\cdots+X_{48})=E(X_1)+E(X_2)+\cdots+E(X_{48}).$ By symmetry, all the $X_i$ have the same distribution. We find, for example, the probability that $X_1=1$. So we want the probability that card with label $1$ is drawn before any Ace.
Consider the $5$-card collection consisting of the $4$ Aces and the card labelled $1$. All orders of these cards in the deck are equally likely. It follows that the probability that card with label $1$ is in front of the $4$ Aces is $\frac{1}{5}$. Thus $E(X_1)=\frac{1}{5}$.
We conclude that $E(W)=\dfrac{48}{5}$.
If we want to take interpretation (ii), and include the draw that got us the Ace, our expectation is $1+\dfrac{48}{5}=\dfrac{53}{5}$.
-
0Don't know of one. I sure have stressed it. – 2012-11-27
Add a fifth ace, uniformly randomly arrange the $53$ cards in a circle, and break the circle into a line at the added ace. By symmetry, the expected number of cards between two of the $5$ aces is $\frac{48}5$, so this is the expected number of cards between the beginning of the line and the first ace.
Distribute the $52$ cards uniformly between $0$ and $1$, so on average they're at $k/53$ for $k=1,2,3,\ldots,52$. The four aces are on average at $1/5,\ 2/5,\ 3/5,\ 4/5$. So $ 0.2 = \frac{k}{53} $ implies $ k = 10.6. $ and $(0.8)\cdot53 = 42.4$. So on average the four aces are the $10.6$th, $21.2$th, $31.8$th, and $42.4$th cards.
I came across this in The Theory of Gambling and Statistical Logic By Richard A. Epstein so pasting a snippet here. I got this from Google Books (public domain) so hopefully there is no copyright violation here. It's amazing how Andre, Michael and Patrick derived the correct answer differently.
A good way to go about this is as follows. Let $T$ be the number of cards drawn at the time of the first ace. This is a $\mathbb{N}$ valued random variable. Therefore $E(T) = \sum_{n=0}^\infty P(T > n).$ You may find this helpful.
I think that the answer lies in the Hypergeometric distribution or else k successes in n draws from a finite population of size N containing m successes without replacement
(quoting from Wikipedia).
In your case, you want a single success in $p$ draws, and from the distribution you can find an average.
Edit: $P(X=1) = \frac{\binom{m}{1}\binom{N-m}{n-1}}{\binom{N}{n}}$ and taking an average should be something like the following $\bar M = \sum_{i=1}^{N-m}i\frac{\binom{m}{1}\binom{N-m}{i-1}}{\binom{N}{i}}$ for $N=52, m=4$.
End of edit.
Wikipedia also has some examples with urns, black and white balls, so you can work the answer from those.
I did not see this approach in any of the answers, which is one that makes sense to me: you can get the ace in either the 1st, 2nd,..., 49th trial.
Then the expected number of cards dealt is $ 1(1/13)+2(12/13)(1/13)+..n(12/13)^{n-1}(1/13)+48(12/13)^{47}(1/13) $.
Try this. (edited based on comment below) You will need just 1 pull with probability 4/52 2 with probability (4/51 x 48/52). 48/52 for the probability of not getting and ace in the first and getting it in the second (4/51), and so on. This yields 1 x 4/52 + 2x(4/51 x 48/52) + 3x(4/50 x 48/52 x 44/50) + ... There must be some simplification for the above, but I'ven't looked deeper into, but you get the idea. Here are similar ones
-
0This assumes there is only one ace in the deck. – 2012-11-27
In response to ncmathsadist:
I have always liked this shortcut (proof here), which also holds for continuous random variables defined on $x \geq{0},\,x \in \mathbb{R}$. For some reason it was called "The Darth Vader" rule in my actuarial study manual but I digress. For this problem: $P(T>n) = \frac{\binom{48}{n}n!}{\binom{52}{n}n!} = \frac{\binom{48}{n}}{\binom{52}{n}}$ This is easily reasoned as follows:
$P(T>n)$ is the probability that there are no aces up to and including the $n$th draw which means that in these first $n$ draws, out of the $48$ non-aces we count the number of ways to choose $n$ of them and permute them. We divide this by the total number of outcomes for the first $n$ draws which is $\binom{52}{n}n!$ (we must include the aces this time, thus the 52).
Therefore: $E(T) = \sum_{n=0}^{48}\frac{\binom{48}{n}}{\binom{52}{n}} = \sum_{n=0}^{48}\frac{(52-n)(51-n)(50-n)(49-n)}{52\times51\times50\times49} = 53/5 = 10.6$
We could sum to $\infty$ like ncmathsadist stated but the values of $P(T>n)$ for $n>48$ are $0$ anyway.
I will admit that I cheated in my final step by using wolframalpha. Wolfram Alpha is a GREAT free resource by the way. I do hope that the logic behind solving the problem is not lost as a result. - Patrick
Sidebar: My initial naive guess was that $E(T) = 13$ since there are on average $12$ cards between each ace. I am trying to figure out an intuitive understanding for why the actual answer is less that $13$ now.
-
0If you wonder why $13$ is too big, consider the expected number of trials needed to get all four aces. Would that be $52$? Only if you never get the fourth ace until the last card in the deck. – 2012-11-27