|
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 as follows: 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, and Failures leave our position unchanged. Our overall outcome depends on where we end up relative to zero. |
|
|
|
One way of computing the result is based on the fact 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 xk in the expansion of the generating function |
|
|
|
|
|
|
|
For example, if we have a=1, b=4, c=5, and N=3 dice, the generating function is |
|
|
|
|
|
|
|
If we multiply this out we find |
|
|
|
|
|
|
|
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−2D (where D is the number of super-botches) has the value k is just the coefficient of xk in the expansion of the function |
|
|
|
|
|
|
|
This raises an interesting question: What is the most efficient way of extracting the coefficient of xt 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−2D has the value k−2N is the coefficient of xk in the expansion of |
|
|
|
|
|
|
|
To find the coefficient of xk 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 |
|
|
|
|
|
so the kth derivative at x = 0 is (k!)ck. 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 + cx2)N approach as N increases? It must be some sort of skewed distribution as suggested by |
|
|
|
|
|
|
|
By the way, a more explicit answer to the original problem would be: With N dice the number of outcomes for which S−B has the value k−N is |
|
|
|
|
|
|
|
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 |
|
|
|
|
|
|
|
The number of "failures" is the single summation |
|
|
|
|
|
|
|
The number of successes is the double sum |
|
|
|
|
|
|
