Expected value of sums

Suppose we draw cards out of a deck without replacement. How many cards do we expect to draw out before we get an ace?

-

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

-
Now I'm wondering if this answer should be considered essentially the same as mine. – Michael Hardy Nov 27 '12 at 1:54
Hard to decide! Mine (of course it's not mine, it is pretty standard stuff, I have used it in lectures) is very formal. – André Nicolas Nov 27 '12 at 1:59
Has anyone written an exposition of the fact that expectations are often easier to find than probabilities? – Michael Hardy Nov 27 '12 at 2:01
Don't know of one. I sure have stressed it. – André Nicolas Nov 27 '12 at 2:04

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.

-

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

-

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

-
This assumes there is only one ace in the deck. – Michael Hardy Nov 27 '12 at 1:05

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.

-
It is 13 only if there is replacement. As there isn't any replacement the probability goes up so that interval should shrink eventually converging to 10.6. BTW could you elaborate how you simplified the average to 53/5? – broccoli Nov 27 '12 at 7:52
You're right, if there is replacement then $T \sim Geometric(p)$ where $p$ is the probability of finding an ace ($1/13$) and $E(T) = 1/p = 13.$ As for an elaboration I just plugged the sum into wolfram alpha's calculator. Andres solution above is much better as the calculations can be done in your head and his method is applicable to other similar problems. – Patrick Nov 27 '12 at 13:33
If 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. – Michael Hardy Nov 27 '12 at 19:16

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.

-