Thread Rating:

Paradroid
Paradroid
  • Threads: 3
  • Posts: 17
Joined: Nov 1, 2010
November 29th, 2014 at 9:40:42 AM permalink
There is a game in which the player can acquire one of 32 different cards, divided into four suits of eight cards each. The cards are drawn with replacement, and each card is equally likely to be drawn. What is the expected number of draws to get

    At least one of all eight cards of any suit?
    At least one of all eight cards of one particular suit?
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6218
Joined: Jun 22, 2011
November 29th, 2014 at 10:33:59 AM permalink
Clarify the problem. Are you asking for:

(a) #1 is all eight ranks of the same suit, but it doesn't matter which suit, and #2 is all eight ranks of a predetermined suit (e.g. "at least one of all eight cards, all spades")

or

(b) #1 is all eight ranks, regardless of their suits (so they don't all have to be the same suit), and #2 is all eight ranks of the same suit, but it doesn't matter which suit?
Paradroid
Paradroid
  • Threads: 3
  • Posts: 17
Joined: Nov 1, 2010
November 29th, 2014 at 10:45:03 AM permalink
I should have expressed myself more clearly. It's (a) I'm curious about.
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6218
Joined: Jun 22, 2011
November 29th, 2014 at 1:14:19 PM permalink
For (b), I get 86 34/35, which was confirmed through simulation.

I'm not quite sure how to figure out (a) except through simulation; I get about 52 1/4.
Paradroid
Paradroid
  • Threads: 3
  • Posts: 17
Joined: Nov 1, 2010
November 29th, 2014 at 1:50:30 PM permalink
Yes, for the version where you need 8 particular cards, my intuition says that the expected number of draws would be

  • 32/8 for the first card
  • 32/7 for the second card
  • 32/6 for the third card
And so on until the expected number of draws is 32 for the last card. I could not figure out a good way to calculate the number of draws expected to complete any suit, which is why I posted to see if better minds than mine could work it out. Thank you for the work on the simulation.

As a side note, the application of this is World of Warcraft, which has items that work this way. You can craft an item called a Darkmoon Card, which yields one of 32 cards divided into four suits, and you need all ranks of a suit to get something useful.
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6218
Joined: Jun 22, 2011
November 29th, 2014 at 2:20:51 PM permalink
Quote: Paradroid

Yes, for the version where you need 8 particular cards, my intuition says that the expected number of draws would be

  • 32/8 for the first card
  • 32/7 for the second card
  • 32/6 for the third card
And so on until the expected number of draws is 32 for the last card.


Which adds up to 86 34/35 - how about that.
brando
brando
  • Threads: 1
  • Posts: 7
Joined: Jul 15, 2015
July 19th, 2015 at 7:43:04 AM permalink
The answer to the first question is

integral_0^infinity (1-(1-e^(-t/32))^32)dt ~~ 129.87

This answer has been calculated by using the Poissonization trick explained by BruzeZ in


This magic trick is due to A.N. Kolmogorov who published this trick in an obscure Italian
journal in 1933. Several interesting applications of the Poissonization trick can be found
in Henk Tijms' book Understanding Probability

mustangsally
mustangsally
  • Threads: 25
  • Posts: 2463
Joined: Mar 29, 2011
July 19th, 2015 at 9:44:01 AM permalink
Quote: brando

The answer to the first question is

integral_0^infinity (1-(1-e^(-t/32))^32)dt ~~ 129.87

this looks to be (to me) the mean
for collecting at least 1 of all 32 cards
I Heart Vi Hart
brando
brando
  • Threads: 1
  • Posts: 7
Joined: Jul 15, 2015
July 19th, 2015 at 11:28:22 AM permalink
Mustangsally, I made a mistake and calculated the expected number of picks until all 32 cards have been chosen at least once. I will think about the correct answer.
brando
brando
  • Threads: 1
  • Posts: 7
Joined: Jul 15, 2015
July 19th, 2015 at 11:43:25 AM permalink
Here is the correct answer to the first question. The answer has been calculated by the magic trick of imagining that the times at which a card is chosen are generated by a Poisson process with rate 1. The Poissonization trick leads to the exact answer
\[
\int_{0}^{\infty} (1-(1-e^{-t/32})^8)^4 dt=52.237,
\]
in agreement with the simulation result.
BruceZ
BruceZ
  • Threads: 2
  • Posts: 57
Joined: May 23, 2015
July 27th, 2015 at 4:32:06 AM permalink
Quote: brando

Here is the correct answer to the first question. The answer has been calculated by the magic trick of imagining that the times at which a card is chosen are generated by a Poisson process with rate 1. The Poissonization trick leads to the exact answer
\[
\int_{0}^{\infty} (1-(1-e^{-t/32})^8)^4 dt=52.237,
\]
in agreement with the simulation result.


brando originally showed me the Poissonization trick a couple years ago on another site under a different username.

The above also uses what I mentioned in a recent thread about getting expected value by integrating P(T > t). In this case, T is the time it takes to get 8 cards of the same suit when we imagine that the cards are drawn at times dictated by a Poisson process of rate 1. The integral gives us E(T) which will be the expected value of the number of cards since cards arrive at an average rate of 1 per unit time. P(T > t) is the probability that we have not gotten 8 of the same suit by time t. Since the 4 suits form 4 independent Poisson processes, P(T > t) is the 4th power of the probability that we have not gotten 8 of a particular suit by time t. This in turn is 1 minus the probability that we did get all 8 of a particular suit. But since the Poisson events corresponding to the cards of a single suit are also independent, this is the 8th power of the probability that we did get a particular card, which in turn is 1 minus the probability that we did not get a particular card, which is e^(-t/32) since the waiting time for a particularcard is exponentially distributed with rate 1/32 (or lambda = 32) since the waiting times to draw the next card are exponentially distributed with rate 1.
  • Jump to: