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