Dice Rolling A Given Sum

Given a set of n dice, each with k faces numbered from 1 to k, the 
most straight-forward way of determining the probabilities and expected 
values for various outcomes is by simply counting the combinatorial 
possibilities. The classical result, due to De Moivre, is that the
probability of a total of T for n dice, each with S sides numbered 1
through S, is

                      1   jmax     j  / n \  / T - jS - 1 \
     Pr{total = T} = --- SUM   (-1)  (     )(              )
                     S^n  j=0         \ T /  \    n - 1   /

where jmax is the largest integer less than or equal to (T+n)/S. Using
the same combinatorial counting approach, we can determine the answers
to other similar questions. For example, suppose we want to determine the 
expected value of the lowest number appearing on the n dice (or n tosses 
of a single die). In other words, if we repeatedly throw the n dice, 
and record the lowest of the individual numbers, what is the long-term 
average of these recorded results? 

We know there are a total of k^n possible outcomes, and this is also
the number of outcomes for which the number on each die is 1 or greater.
The number of outcomes for which each die shows 2 or greater is (k-1)^n, 
and the number of outcomes for which each die shows 3 or greater is 
(k-2)^n, and so on. Now, the number of outcomes with a minimum showing 
of j equals the number for which each die shows j or more, minus the 
number for which each die shows j+1 or more. Therefore, the probability
of having a minumum of j is

                             (k+1-j)^n - (k-j)^n
            Pr{min = j}  =  ---------------------
                                    k^j

It follows that the expected value of the minimum number showing for n
k-sided dice is

                        k
                      SUM  [ (k+1-j)^n - (k-j)^n ] j
                       j=1
          E{n,k}  =   ------------------------------
                                   k^j  


However, it is not always feasible to explicitly evaluate all the
combinatorial possibilities in this way. For example, suppose we have 
a set of n dice, each of which has k faces numbered 0 through k-1. In 
how many different ways can these dice give a particular sum S?  

Assuming we regard the individual dice as distinct, there are obviously 
k^n different possible results, which could also be modeled as sequences 
of throwing a single k-sided die n times, and keeping track of the order 
of the results as well as the cumulative sum.  If n and k are small the 
exact answer can easily be computed combinatorially for each possible 
sum, but for large values of n and k, such as n=k=256, we are better off
applying the central limit theorem and dealing with proportions rather 
than absolute numbers.

Taking n=k=256 as an example, we have 256 independent random variables, 
each of which has a flat (rectangular) distribution with a mean of 255/2 
and a standard deviation of 255/2sqrt(3).  Our "outcome population" is 
the sum of these individual populations, so it has a mean of 
256(255/2) = 32640 and a standard deviation given by  

                                  /   255     \ 2
                   sigma^2 = 256 (  ---------  )
                                  \  2sqrt(3) /


Therefore, we have sigma = 2040/sqrt(3) =~ 1177.79.  By the central limit 
theorem, it follows that the density of sequences for a given sum x is

                       exp( -[x-32640]^2 / 2(1177.79)^2 )
       d(x) = 256^256  ----------------------------------
                              (1179.79) sqrt(2 PI)

For an interval of width 1 surrounding x=32768, this gives the expected 
number of sequences equal to approximately 

                      0.00034015 * 256^256

so about 1 out of every 2939.88 sequences would give the sum 32768.