So given say, a deck of cards, I draw cards until I pick out a specific one, in this case, the ace of spades. Once the ace of spades has been drawn, you restart. Now, this continues till infinity. On average, how many tries does it take to get the card? Is there a solution to a deck of size $n$?
Probability over time
2 Answers
Drawing cards serially
Assuming a 52-card deck, shuffled completely randomly, the Ace of Spades has a 1/52 chance of occupying any position in the deck.
Let $X$ denote the position of the ace of spades. Then, $P(X = x) = 1/52$ for all $x = 1, 2, \ldots, 52$.
The average value of $X$ is given by the formula for expectation of a discrete random variable:
$$E[X] = \sum_{i=1}^{52} i P(X = i) = \frac{1}{52} \sum_{i=1}^{52} i = \frac{52\cdot (52+1)}{52\cdot 2} = \frac{53}{2}$$
This generalizes to $n$ by replacing 52 with $n$.
Drawing cards randomly
The expected value formula is the same, but we modify $P(X=x)$ to reflect the random drawing of cards.
It is easy to see that the probability of drawing the Ace of Spades on the $i$th try is the same as the probability of $i-1$ failures followed by a single success.
The probability of $j-1$ failures, without replacement, can be written
$$ \frac{51}{52} \frac{50}{51} \cdots \frac{52-(j-1)-1}{52-(j-1)}.$$
It should be clear that diagonal terms cancel, leaving
$$\frac{52-j}{52}.$$
However, do note that because of the indexing, we have $j = i-1$. That is, if we pull the Ace of Spades on the first card ($i=1$), we have zero preceding failures.
After drawing $i-1$ cards, there are $52-(i-1)$ cards remaining in the deck, so the probability of success on the ith try is $1/(53-i)$.
Multiplying these together, one gets
$$P(X=i) = \frac{53-i}{52} \frac{1}{53-i} = \frac{1}{52}.$$
Hopefully it is more clear now that the result is the same as before.
-
0I think I explained the problem wrong, cards are selected without replacement. – 2012-11-26
-
0Ok, but you say "this continues till infinity". I interpret that to mean "pick a card, stop when you get the ace of spades, write down the ace of spades position, shuffle, and repeat." If that is the case, then I am correct, because every time you re-shuffle the deck, the ace has a 1/52 chance of being in any particular spot. – 2012-11-26
-
0Just to make sure, what I mean is that you take the deck, remove cards till you find the ace of spaces, mark position, return all the cards, and repeat, forever. – 2012-11-26
-
0Right. I am assuming you are removing the cards serially (e.g. top card first). In this case, the answer is correct, and in fact intuitive: the Ace of Spades has an equal probability to be in any position in the deck. Since a 52 card deck has an even number of cards, it's "average" position is somewhere between the last card of the first half-deck, and the first card of the second half-deck -- 26.5 = 53/2. – 2012-11-26
-
0Original poster here again, I registered this time, not sure how to mark your answer as correct... – 2012-11-26
-
0@dzk87: I have merged your accounts. You should be able to upvote and accept the answer you want. – 2012-11-26
-
0@dzk87 I have edited this to be more clear with my indexing and notation. Specifically, when computing the preceding failures, the summation index matters greatly. I made a slight error and didn't carry this through in my final formula, but now it is fixed. – 2012-11-26
This is well discussed in these forums itself, I've summarized it here. Hope that helps