Suppose I have a stack of 11 different cards and I deal a hand of 9 cards to myself. Then, I put all 11 cards back together and deal another hand of 9 cards to myself. And repeat.
How can I calculate the probability that I’ve been dealt all 11 different cards after X hands?
(Obviously, the probability after 1 hand is 0.)
Is there a quick and easy way to do this?
It depends on what you consider quick and easy. The key insight is that after the first hand, you’ve seen all but two of the cards, so you only need to worry about how many new cards you see in any subsequent hand. That means that you can model this as a Markov chain where the state space is the number of cards you haven’t seen yet, and the transition probabilities are just the probability of getting some number of new cards in any draw. From there, you can pretty easily compute everything that you’re interested in.
(I would do some explicit calculations here, but I’m in a bit of a hurry. If no one else fills the numbers in before I get a chance to do so I’ll take care of it later this afternoon.)
First some basics. There are 55 (= (11 choose 2) = 1110/2) different 9 card hands you can get from 11 cards. If you’ve seen only nine different cards (after the first or any subsequent deal), there are 36 (= (9 choose 2) = 98/2) different hands you can get to finish the job. The probability of this is 36/55. There are 18 (= (2 choose 1) * (9 choose 1)) ways to see one of the missing cards. The probability of this is 18/55. The probability you don’t see a new card is 1 - 36/55 - 18/55 = 1/55 (i.e., you must draw exactly the same hand you’ve seen every time.
If after some number of deals you’ve seen 10 different cards, there are 45 (= (10 choose 2) = 10*9/2) different hands you can deal to complete your task. The probability of this is 45/55.
Let P(x) be the probability that you’ll seen all cards on the xth deal. Let Q(x) be the probability that you’ll have seen exactly 10 different cards by the xth deal. Let R(x) be the probability you’ll have seen only 9 different cards by the xth deal. Then
R(1) = 1, Q(1) = P(1) = 0
R(x+1) = R(x)/55
Q(x+1) = Q(x)*10/55 + R(x)*18/55
P(x+1) = R(x)*36/55 + Q(x)*45/55
Now iterate to compute. I get
x = 2 65.45%
x = 3 27.97%
x = 4 5.58%
x = 5 0.98%
x = 6 0.18%
x = 7 0.03%
x = 8 6E-5
x = 9 1E-5
x = 10 2E-6 (2 chances in a million)
etc.
There’s probably a general formula.
This being SDMB, I’m sure someone will be long soon to do something similar and thereby check my math.
1 - (2*10^(x-1) - 1) / 55^(x-1)
Thanks for the replies and the explanation!