Collecting a deck of cards on the street
Colgathar
this is like drawing cards one-by-one from an infinite number of decks
shuffled together), how many cards must I pick up before I have a
50-50 chance of having a complete deck of 52 cards?
Anthony Buckland
And then you'll find that they have differing backs,
so you_still_ can't play poker with them.
Randy Poe
This is the coupon collector's problem.
Suppose you have N different types of "coupon" (52 here) and
a collection of n total coupons (cards) so far.
This problem is analyzed in many places, for instance in Ross,
"A First Course in Probability" (3rd ed., chapter 7, example 3g).
Let X_i = 1 if the set of cards has card i in it, 0 otherwise.
P{X_i=1} = 1-[(N-1)/N]^n
You are asking about P{X_1=1}P{X_2=1}...P{X_N=1}, which is
[1 - [(N-1)/N]^n]^N, and you want to know at which value
of n this reaches 50%.
A numerical calculation tells me it's around 220.
However, there's something slightly suspect in my analysis
because my formula gives nonzero answers for all n,
including values less than 52. I suspect it's the assumption
of independence in the probability calculation.
Ross doesn't ask this question, but analyzes the expectation
value of X = X_1 + ... + X_n (the number of different cards
you'd expect in a collection of size n), and the distribution
of Y = number of coupons collected before you get a complete
set.
- Randy
Doug Magnoli
possible outcomes: either you'll have a full deck, or you won't. So the
chances are 50-50.
(Notice that, using this model, the chances of a complete deck don't
improve as you collect more cards.)
Probability is so easy, isn't it?
-Doug Magnoli
[Delete the two and the three for email.]
Kevin Buhr
>
> This is the coupon collector's problem.
>
> Suppose you have N different types of "coupon" (52 here) and
> a collection of n total coupons (cards) so far.
> Let X_i = 1 if the set of cards has card i in it, 0 otherwise.
> P{X_i=1} = 1-[(N-1)/N]^n
>
> You are asking about P{X_1=1}P{X_2=1}...P{X_N=1}, which is
> [1 - [(N-1)/N]^n]^N, and you want to know at which value
> of n this reaches 50%.
>
> A numerical calculation tells me it's around 220.
>
> However, there's something slightly suspect in my analysis
> because my formula gives nonzero answers for all n,
> including values less than 52. I suspect it's the assumption
> of independence in the probability calculation.
That's correct. The events {X_i=1} are not independent. The exact
formula for the probability that after collecting n cards you have all
of N different types (i.e., a full deck) is:
sum_{k=0}^N (-1)^k (N choose k) (1-(k/N))^n
according to Feller in _An Introduction to Probability Theory and Its
Applications: Volume 1_.
An exact calculation shows that, for N=52, this probability first
exceeds 0.5 when n hits 225. After collecting 225 cards, you have
slightly more than a 50% chance of having a full deck.
However, the approximation you give above is surprisingly accurate.
The approximate probability is first above 0.5 for n=223.
--
Kevin Buhr <bu...@telus.net>
DMB
You're not serious, I assume? Using your "model," there's no such thing as
a biased coin, since a toss of any coin gives either a head or tail - 2
possibilites, so 50% chance of either outcome? And the chance of rain is
50% every day! Very nice!
DB
"Doug Magnoli" <dmagn...@attbi.com> wrote in message
news:3D616ACB...@attbi.com...
Randy Poe
DMB wrote:
>
> "Doug Magnoli" <dmagn...@attbi.com> wrote in message
> news:3D616ACB...@attbi.com...
> > The answer is obviously 52, because when you have 52 cards, there are two
> > possible outcomes: either you'll have a full deck, or you won't. So the
> > chances are 50-50.
>
> You're not serious, I assume?
No, Doug is not serious. However, the probability fallacy he
is talking about is unfortunately very common. Ranks right up
there with "I haven't gotten a 6 in a long time, so this
die wants to come up 6 now."
- Randy
Michael Press
colg...@yahoo.com (Colgathar) wrote:
About 225.
Suppose we have c = 52 cards in the deck and we pick up p cards.
Let E(i, p) be the event that the ith card is not collected after p pick-ups.
Probability [ E(i, p) ] = Pr [ E(i, p) ] = (1 - 1/c)^p ~ exp(-p/c)
and
Pr [not E(i, p)] ~ 1 - exp(-p/c)
Pr [All c cards are collected after p pick-ups]
= Pr[not ( E(1, p) or E(2, p) or ... or E(c, p) )]
= Pr[not E(1, p) & not E(2, p) & ... & not E(c, p)]
= Pr[not E(1, p)] * Pr[not E(2, p)] * ... * Pr[not E(c, p)]
~ (1 - exp(-p/c)^n
~ exp(-c * exp(-p/c))
Let p = c * log c + k * c.
Pr [All c cards are collected after c * log c + k * c pick-ups] ~ exp(-exp(-k))
Solving 1/2 = exp(-exp(-k)) for k gives k ~ 0.36651,
so the probability that all 52 cards are collected after
52 * log 52 + 0.36651 * 52 ~ 225 pick-ups ~ 1/2.
--
Michael Press
DMB
Stirling Numbers of the 2nd Kind, S2(n,k). If S2(n,k) is defined as the
number of ways to arrange n distinct objects into k non-empty subsets, then
the probability that k randomly selected cards are enough to give at least
one of each of the 52 is the following:
S2(n,52)*52!/52^n
We multiply S2(n,52) by 52! because the 52 subsets can be labeled with one
of the 52 cards in 52! ways. Then we divide by the number of ways to choose
a sequence of n cards, each card being one of 52 possibilities. The
interesting thing is that according to Mathematica, the value of n that
makes this meet or exceed 1/2 is 225, just like Michael says! More than one
way to skin a cat, I guess.
DMB
"Michael Press" <pre...@apple.com> wrote in message
news:prezky-2008...@blankverse.apple.com...
Doug Magnoli
probability of snow. This means the probability of rain on any given winter
day is 1/3, not 1/2.
Probability is easy, but you do have to use a little sense with it.
-Doug Magnoli
[Delete the two and the three for email.]