A deck of $ n$ playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is $ (n+1)/2$.
Problem
Source: 1975 USAMO Problem 5
Tags: probability, symmetry, expected value
robbiez
15.03.2010 05:43
EDIT: Deleted
bobbym
15.03.2010 06:07
Hi;
This one actually has a formula for it. It is called the negative hypergeometric distribution. You can google for it.
The expected number of cards from an n card deck with 3 aces until you turn up 2 aces is
$ \frac {2(n - 3)}{4} + 2$
Which you can see equals your
$ \frac {n + 1}{2}$
ocha
15.03.2010 12:46
The probability that the $ m^{th}$ card is the second ace is given by
$ P(m) = (m - 1)\left(\frac {3}{n}\cdot\frac {n - 3}{n - 1}\cdot\frac {n - 4}{n - 2}\cdot\cdot\cdot\frac {n - m}{n - m + 2}\right)\frac {2}{n - m + 1}$
$ = 6(m - 1)\frac {(n - m)!}{n!}\frac {(n - 3)!}{(n - m - 1)!} = \frac {(n - m)(m - 1)}{\binom{n}{3}}$
Where $ 2\le m \le n - 1$
Therefore $ E(x) = \sum_{k = 2}^{n - 1} kP(k)$
$ = \frac {1}{\binom{n}{3}} \sum_{k = 2}^{n - 1} k(n - k)(k - 1)$
For $ n$ odd
There is symmetry in the expression $ p(m) = m(n - m)(m - 1)$, that is $ p(k) + p(n - k) = (n - 2)(n - k)k$
$ \therefore \sum_{k = 2}^{n - 1} k(n - k)(k - 1) = (n - 1)P(n - 1) + (n - 2)\sum_{k = 2}^{\frac {n - 1}{2}}k(n - k)$
$ = (n - 2)\left((n - 1) + \frac {(n - 1)(n^2 + n - 12)}{12}\right) = \frac {(n - 2)(n - 1)n(n + 1)}{12}$
For $ n$ even
The symetry is $ p(k) + p(n - k + 1) = (k - 1)(n - k)(n + 1)$
$ \therefore \sum_{k = 2}^{n - 1} k(n - k)(k - 1) = (n + 1)\sum_{k = 2}^{\frac {n}{2}}(k - 1)(n - k)$
$ = (n + 1)\left(\frac {x(x - 2)(x - 1)}{12}\right) = \frac {(n - 2)(n - 1)n(n + 1)}{12}$
$ \therefore E(x) = \frac {1}{\binom{n}{3}}\frac {(n - 2)(n - 1)n(n + 1)}{12} = \boxed{\frac {n + 1}{2}}$
math_explorer
15.03.2010 14:41
Am I not getting something? (The answer is right.)
Couldn't we just explain that given any ordering of the cards with $ k$ cards until the second ace, we can reverse the ordering and obtain an ordering with $ n - k + 1$ cards?
This operation (namely, reversing the order) also has these properties:
1. it is uniquely reversible
2. applying it twice restores the original ordering / it is its own inverse
3. no ordering is the same after applying it
(1. to 3. = it's an involution with no fixed points)
4. the average of the number of cards up to and including the second ace of any pair of orderings linked by this involution is $ \frac{n + 1}{2}$.
Then we could just average all the pair-averages, which are all $ \frac{n + 1}{2}$.
Brut3Forc3
16.03.2010 04:16
math_explorer wrote: Am I not getting something? (The answer is right.)
Couldn't we just explain that given any ordering of the cards with $ k$ cards until the second ace, we can reverse the ordering and obtain an ordering with $ n - k + 1$ cards?
This operation (namely, reversing the order) also has these properties:
1. it is uniquely reversible
2. applying it twice restores the original ordering / it is its own inverse
3. no ordering is the same after applying it
(1. to 3. = it's an involution with no fixed points)
4. the average of the number of cards up to and including the second ace of any pair of orderings linked by this involution is $ \frac {n + 1}{2}$.
Then we could just average all the pair-averages, which are all $ \frac {n + 1}{2}$.
No, that's completely correct.
xpmath
04.04.2010 20:43
Consider the first two aces to be drawn. Of the other $ n-3$ non-ace cards, each can either be before or after the second ace, so we expect $ \frac{n-3}{2}$ to be drawn before the second ace.
Adding in the two ace cards themselves, this gives us an expected number of $ \frac{n+1}{2}$ cards.
john0512
04.01.2023 23:50
Consider each of the $n-3$ other cards. For each card, consider its position relative to the three aces. It has a 1/2 chance of being in either the first or second position (i.e. before the second ace) since there are four possible positions. Therefore, by LOE, the expected number of non-ace cards before the second ace is (n-3)/2, so the answer is 2 + (n-3)/2 = (n+1)/2
huashiliao2020
14.04.2023 03:37
Hmm, am I missing something? Suppose we take the three aces, in their expected value places. Then they split the deck up into equivalent four piles (since they are in their expected value places), each with size (n-3)/4. Then the number of cards needed to be flipped is 2 piles * (n-3)/4 + 1 first ace + 1 second ace = (n-3)/2+2=(n+1)/2, as desired. $\blacksquare$ also, can someone tell me if this is rigorous, or if there is a specific theorem name for this? I am sure that there is a formal name and that I cannot just say “in their expected value places”
S.Das93
14.04.2023 03:43
That is correct. I believe you mean LoE (Linearity of Expectation)?
fysiksMoe1121
27.04.2023 04:41
This is obviously true by symmetry. We can consider a contradiction, that the ev is not equal to $(n+1)/2$. In other words the expected value is not in the middle of the deck. Then that means that we get a different expected value if we turn the cards over from left to right or right to left (assuming we lay the cards in a line on flat ground). But it should make no difference from which side we flip over the cards from so if we have different expectations from each side, we have a contradiction.