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!)[953029440]

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/