A Probability Problem

PhireKaLk6781

Ana and Bill are playing a game in which they take turns. In each turn, they put one bead into one of ten boxes (randomly, with each box having equal probability). Each box can hold an indefinite number of beads. Once all of the boxes are filled, the person who put the last bead wins.

Question 1: What is the probability that the game lasts more than 12 turns?
Question 2: What is the expected value of the number of turns needed to finish the game?
Question 3: Does the person who gets the first turn have an advantage, disadvantage, or no advantage?

**Posted:** Tue Nov 03, 2009 5:23 pm

JBL

**Posted:** Tue Nov 03, 2009 5:38 pm

_________________
Joel
Hi Deeps! <3

PhireKaLk6781

Whoops. Sorry for the lack of clearness. "Once all of the boxes are filled" should be "Once each box as at least one bead". Razz

**Posted:** Tue Nov 03, 2009 5:48 pm

PhireKaLk6781

Would someone be willing to answer and provide a solution? Neutral

**Posted:** Wed Nov 04, 2009 4:17 pm

PhireKaLk6781

I hope this isn't getting missed. Would someone please tell me how this problem is solved?

**Posted:** Fri Nov 06, 2009 5:13 pm

JBL

Here are some hints:

Question 1 is a counting problem: count the total number of possible ways the first 12 moves can go, then count the number of ways that result in all 10 boxes being filled, then subtract. (The answer is larger than 99%, i.e., it's extremely unlikely that the game ends in 10, 11 or 12 turns.)

For question 2, perhaps the easiest thing to do is a state diagram approach: let $e(n)$ be the number of expected moves required when there are $n$ boxes left unfilled. Thus, we're trying to compute $e(10)$ , and we have (for example) that $e(6) = 1 + \frac {4}{10} e(6) + \frac {6}{10} e(5)$ .

For question 3, a different but similar state diagram approach seems in order. Let $p(n)$ be the probability that the first player wins when starting with $n$ unfilled boxes. We have $p(0) = 0$ (the first player has just lost) and we want to compute $p(10)$ .

These questions are one form of the coupon-collector problem: part 2 is the most common version, I think. Question 1 can be answered in more generality using inclusion-exclusion, another common form. A search for the word "coupon" on the forum brings up several recent discussions.

**Posted:** Sat Nov 07, 2009 9:40 am

_________________
Joel
Hi Deeps! <3