Getting One of Each Number (1-6) Rolling N Dice
Date: 05/24/2001 at 13:58:10 From: Kevin Mayville Subject: Probability of getting at least one of each number (1-6) rolling N dice I've been trying to determine some probabilities involving randomly distributing items to a group of six people. Certain of them, such as the probability of someone getting M items out of N rolls or of the items being divided evenly (with N a multiple of 6), were readily solvable for me using binomial distribution. I'm having some difficulty getting a handle on either a formula or a systematic approach at determining the odds that each person gets at least one item when N > 6. Attacking it in a manner such as doing combinations like 123456XXXXXX (for N = 12) doesn't seem viable because the X's aren't a separate group of results... it doesn't matter what they are as far as the answer goes, but they affect the number of combinations. Any ideas?
Date: 05/25/2001 at 21:25:57 From: Doctor Pat Subject: Re: Probability of getting at least one of each number (1-6) rolling N dice Kevin, If you are familiar with matrices, the Markov method is a good approach, but it does need some calculation (I used my trusty TI-83). Think of the seven states you can be in during the process if you roll the dice (or assign the objects) one at a time. Each state corresponds to the number of non-empty bins. Before you roll you are in state zero, but after your first roll you will never be back to this state, so we focus on the six remaining states and the eleven (or N-1) remaining rolls. At each level it is easy to determine the probability that you go to the next state, and the probability you remain in your given state, (all other states have probability zero for that transition - you can't get from two bins occupied to four bins occupied in a single assignment). We express these transitions as a 6x6 probability matrix where each row,column value (m,n) expresses the probability of going from state m to state n on the next roll. The matrix looks like this: 1/6 5/6 0 0 0 0 0 1/3 2/3 0 0 0 0 0 1/2 1/2 0 0 0 0 0 2/3 1/3 0 0 0 0 0 5/6 1/6 0 0 0 0 0 1 The state 6,6 is absorbing because if six bins are occupied after any roll, they will still be occupied after any subsequent roll. The top row also represents the probability of being in any particular state after two rolls (remember we took one roll to get in state one). If we multiply this matrix times itself, it gives us the probability of where we might be after three rolls, and again, the top row tells us the probabilities of the state we will end up in after two rolls starting from position one (three rolls from position zero). These should match what you would get with a simple tree diagram of the probabilities. For that line I got 1/36, 5/12, 5/9, 0, 0, 0 as we would expect. If you raise the original state matrix to the eleventh power (to find the probabilities after 12 rolls in all) you get about 43% probability of being in state 6 (six bins occupied). The actual value was 1654565/ 3779136. Hope that is of help to you. Good luck. - Doctor Pat, The Math Forum http://mathforum.org/dr.math/
Date: 05/27/2001 at 16:24:38 From: Kevin J Mayville Subject: Re: Probability of getting at least one of each number (1-6) rolling N dice Thanks, that's exactly what I was looking for (even though it means I need to get a better calculator or at least a program that will multiply matrices). I've been having a hard time convincing people that even if random numbers are *unbiased*, that doesn't mean that the final distribution will be fair or even approximately fair except in the realm of large numbers.
Date: 05/28/2001 at 15:43:07 From: Doctor Anthony Subject: Re: Probability of getting at least one of each number (1-6) rolling N dice The probability that all 6 numbers will have occurred after 12 rolls of a die can be calculated as follows: We find an expression for T(n,m) where this represents the number of ways of placing n distinguishable objects at random into m distinguishable boxes so that no box is empty. In our problem we have n=12 balls and m=6 boxes. The generating function for this number is [e^x - 1]^6 and we must pick out the coefficient of x^12/12!. This is simply the usual exponential generating function with the -1 there to ensure that no box is empty. The number of such arrangements is given by: 12! ------------------ where n1 + n2 + n3 + n4 +n5 + n6 = 12 n1!n2!n3!n4!n5!n6! with no n(i) = 0 and if we sum this for ALL possible solutions of n1+n2+n3+n4+n5+n6 = 12 and no n(i) = 0 we obtain the number of ways that 12 different objects can be placed at random into 6 different boxes with no empty boxes. [e^x - 1]^6 = e^(6x) - C(6,1)e^(5x) + C(6,2)e^(4x) - C(6,3)e^(3x) + C(6,4)e^(2x) - C(6,5)e(x) + 1 We now pick out the terms in x^12 = 6^12/12! - 6(5^12/12!) + 15(4^12/12!) - 20(3^12/12!) + 15(2^12/12!) - 6(1^12/12!) = (1/12!)[6^12 - 6(5^12) + 15(4^12) - 20(3^12) + 15(2^12) - 6] = (1/12!) and so the coefficient of x^12/12! is 953029440 If you throw a die 12 times the total number of possible outcomes, with 6 possibilities at each throw, is 6^12 So the required probability is 953029440/6^12 = 0.43781568 - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/
Date: 05/30/2001 at 16:50:12 From: Kevin J Mayville Subject: Re: Probability of getting at least one of each number (1-6) rolling N dice Thanks for the help! Is there a straightforward way to generalize the generating function for varying minimum numbers of items per box? I experimented with (e^x - 2)^6, etc., and it didn't seem to give accurate results. Do you know of any resources you could point me at online for a good overview of this method so I don't end up sending another email every time I decide to play around with this problem some more?
Date: 05/30/2001 at 17:26:50 From: Doctor Anthony Subject: Re: Probability of getting at least one of each number (1-6) rolling N dice If you want minimum numbers (say 2) in the boxes you can start by putting one ball in each box and then distribute the remaining balls using the method already described. There are so many variations to these occupancy problems that you really require a good textbook on combinatorics to guide you through the maze. A classic of this type is _Applied Combinatorics_ by Fred S. Roberts. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/
Date: 05/30/2001 at 18:06:12 From: Doctor Pat Subject: Re: Probability of getting at least one of each number (1-6) rolling N dice Kevin, This is not nearly as elegant as Dr. Anthony's exponential, but I think an understandable approach would be to use polynomial generating functions. I believe this will work, but you can check with some simulation. If you represent the possible number of balls in a bin by a polynomial power of that number, and multiply all the possibilities out, you can then look at the appropriate power to find the number of permutations... That is hard to understand, so a brief example. Suppose with the case of 12 balls and four bins you want to know the probability of getting at least two in each bin.. Then in each bin there may be as few as two, and as many as six (if 2 are in each of three bins and six in another) Express the number of possible balls in one bin by (x^2/2! + x^3/3!+x^4/4!+x^5/5!+x^6/6!) where x^2/2! is accounting for the case of exactly two balls in the bin, x^3 for three, etc. Now we raise this to the fourth power since there are four bins with the same chances. We get a huge polynomial (24th power) but we are looking only for the coefficient of x^12/12! as in Dr. Anthony's solution. I got a little over 7.27 million ways for this. Hope this helps. I'll be looking for the book Dr. Anthony recommended too; his was a really elegant approach. Good luck. - Doctor Pat, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.