Botches, Failures, and Successes

Here's an interesting random walk problem.  Suppose we have N dice, 
each of which has a+b+c faces, where "a" is the number of "botch" 
faces, "b" is the number of failure faces, and "c" is the number of 
success faces.  (Each individual face is considered equally likely).
Then, we roll all N of the dice and evaluate the results like this:  
Let B denote the number of botched dice, F the number of failures, 
and S the number of successes.  The overall status is either a botch, 
a failure, or a success accordingly as S-B is less than, equal to, 
or greater than zero.  In other words, we start at zero on the number 
line, and each botched die moves us 1 to the left, each successful 
die moves us 1 to the right.  (Failure dice leave our position 
unchanged.)  Oour overall outcome depends on where we end up
relative to zero.

There may be some very efficient way of computing the result, but
all I can think of is that out of all possible outcomes from rolling 
the N dice the number of outcomes for which S-B has the value k is 
just the coefficient of x^k in the expansion of the function

           f(x)   =    (a x^-1  +  b  +  c x)^N

(This is called a generating function.)  For example, if we have 
a=1, b=4, c=5, and N=3 dice, the generating function is

             f(x)  =  ( x^-1  +  4  +  5 x )^3

If we multiply this out we find

 f(x)  =  x^-3 + 12 x^-2 + 63 x^-1 + 184 + 315 x + 300 x^2 + 125 x^3

which shows that there is 1 outcome with S-B = -3, and there are 
exactly 12 outcomes with S-B=-2, and so on up to 125 outcomes with 
S-B=+3.  Our criterion says that any outcome with S-B < 0 is an
overall botch, so there are 1 + 12 + 63 = 76 botches.  Then there 
are 184 outcomes with S-B = 0, so these are the "failures".  Finally, 
there are 315 + 300 + 125 = 740 successes, i.e., outcomes with 
S-B > 0.

Obviously this could be generalized to include other categories.
For example, if we have N dice, each with a+b+c+d sides, where
a is the number of "super-botches" (which cancel TWO successes), b
is the number of botches, c is the number of failures, and d is the
number of successes, then the number of outcomes for which S-B-2SB
has the value k is just the coefficient of x^k in the expansion of 
the function

      f(x)   =    (a x^-2  +  b x^-1  +  c  +  d x)^N

This raises an interesting question:  What is the most efficient
way of extracting the coefficient of x^t from a given generating
function?  For simplicity, let's increase each power of x by 2, so
the number of outcomes for which S-B-2SB has the value k-2N is the 
coefficient of x^k in the expansion of

       f(x)   =    (a  +  b x  +  c x^2  +  d x^3)^N

To find the coefficient of x^k we could simply expand the function
by raising the polynomial to the Nth power, but another approach 
would be to numerically evaluate the kth derivatives of f(x) at x=0.  
We know that

    f(x) = c_0 + c_1 x + c_2 x^2 + ... + c_k x^k + ...

so the kth derivative at x=0 is (k!)c_k.  If we have enough precision 
in our calculations we could determine the kth derivative based on 
k+1 values of f(x) very near x=0.  I'm not sure if this would be more
or less efficient than just expanding f(x).  Are there any other ways
of determining the coefficients implied by a generating function?

Another interesting question is whether the coefficients are
approximated by some known continuous distribution.  For example
we know that (normalized) coefficients of  f(x) = (1 + x)^N   
approach a normal distribution as N increases.  What function do 
the (normalized) coefficients of (a + bx + cx^2)^N  approach as N 
increases?  It must be some sort of skewed distribution as 
suggested by

                1   12   63  184  315  300  125 

By the way, a more formulaic answer to the original problem would 
be: with N dice the number of outcomes for which S-B has the value 
k-N is

      [k/2]                N!
      SUM        --------------------  a^(N-k+j) b^(k-2j) c^(j) 
    j=max(0,k-N)  (N-k+j)! (k-2j)! j!

where the square brackets [x] signify the largest integer less than x. 
So, the number of "botches" for N dice with a+b+c sides is given by
the double summation

              N-1   [k/2]          N!
 botch(N) =   SUM   SUM   -------------------  a^(N-k+j) b^(b-2j) c^(j)
              k=0   j=0   (N-k+j)! (k-2j)! j!

The number of "failures" is the single summation

                 [N/2]          N!
 failure(N) =    SUM   -------------------  a^(N-k+j) b^(b-2j) c^(j)
                 j=0   (N-k+j)! (k-2j)! j!

The number of successes is the double sum

                2N   [k/2]          N!
 success(N) =  SUM   SUM    ------------------- a^(N-k+j) b^(b-2j) c^(j)
              k=N+1  j=k-N  (N-k+j)! (k-2j)! j!


Return to MathPages Main Menu
Сайт управляется системой uCoz