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.
-
0@dzk87 I have edited this to be more clear with my indexin$g$ and notation. Specifically, when computin$g$ 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