Probability distribution for draws with conditional replacement? (or how many matches does it take to beat Yugi The Destiny?)

Question

While trying to figure out an old video game, I seem to have stumbled upon a problem that's halfway between a binomial distribution problem and a hyper-geometric distribution problem. With the hopes of letting R do the hard work for me, I'm trying to find out if there's a standard probability distribution for this class of problem. A heavily simplified example for the sort of problem that I'm trying to solve is as follows:

• Suppose that we have an urn containing 50 white balls and 100 black balls. At each turn, I draw one ball from the urn. If the ball is black, I put it back in the urn. If the ball is white, I do not put it back in the urn. The game ends when I draw the last white ball. What is the probability distribution on the total number of turns that I play?

However, the full problem that I'm attempting to solve is as follows:

• I'm playing a game. When I win a match, I am rewarded with 3 cards out of a (presumably) equiprobable list of 155. Cards can be won more than once, and the 3 cards that I am given when I win appear to be drawn independently of each other and of the cards that I possess. I currently have 77 of the 155 possible cards and will stop playing once I have won the remaining 78. What is the probability distribution on the number of matches that I will have to win?

To be clear, what I really want is just the name of the probability distribution(s) that I should be looking in to for this class of problem. As for everything else, I'm willing to do that work myself.

Answer 1

Your second problem is a variant of the coupon collector problem [there are a number of posts on it here and on math.SE]

In this case you have 77 cards already.

Given that, and following the same reasoning at the Wikipedia page, your expected number of cards required is $155 (\frac{1}{78}+\frac{1}{77}+...+\frac{1}{1}) \approx 765.75$, or a further $256$ sets of $3$ cards.

However, the median number of cards required is lower (the distribution is right skew); i.e. frequently you'll need less than 256 wins, but sometimes it will take many more.

If you were starting from scratch you'd expect to need $nH_n=872$ cards (or 291 sets of 3).

Details on the distribution of the number of trials in the coupon collector problem are given in several places, for example, here; similar analysis could be done where you already have part of the collecting done.

Also see here