1
$\begingroup$

In the role playing game Exalted, there is a dice mechanic whereby you have a certain number of 10-sided dice in a dice pool and when you roll them, each die showing a 7, 8, or 9 count as one success and those showing a 10 count as 2 successes (the idea being that you need some threshold number of successes to accomplish a task).

It's been a very long time since I've done this, but I do remember the basics of using generating functions to calculate these sorts of things. Specifically, I can write a polynomial representing a 10 dice pool as $(6 + 3x + x^2)^{10}$ and get Wolfram Alpha to do the heavy lifting for me to calculate the specific coefficients.

But then I got to wondering if there was a more general way to calculate the coefficient for all powers of x for an arbitrary n (i.e. for any number of dice in the pool). Moreover, it would be nice to know what the chance of getting at least k successes in a pool of size n would be, though I suspect that the answer to the former question leads immediately to the latter.

$\endgroup$
2
  • 4
    $\begingroup$ Are you familiar with the Multinomial Theorem? $\endgroup$ Jun 1, 2015 at 3:54
  • $\begingroup$ I am now. :) I'm having a hard time wrapping my head around a closed form solution for the coefficient for an arbitrary power of x even given a fixed power. That is, it seems like I need to account for all possible combinations where the powers of x sum to at least (or exactly) some target and then calculate the individual multinomial coefficients that way. I must be missing something, though. $\endgroup$
    – Ben Thul
    Jun 3, 2015 at 4:55

1 Answer 1

4
$\begingroup$

So, this is a pretty old question, but fortunately for you I've been going through this very problem recently, so here's an answer for anyone else who comes across this one:

Firstly, your generating function is a little incorrect if you're planning to generate probabilities, since all the coefficients need to equal 1. so, your generating function should be $(\frac{6}{10}+\frac{3x}{10}+\frac{x^2}{10})^n$. We'll use those values going forward.

For this particular question, we're looking at a multinomial distribution, which for three possible options has the following general formula for an arbitrary combination of options:

$$\frac{n!}{x!y!z!}(S)^x(F)^y(D)^z$$

You've already (mostly) provided our probabilities $S$ (success), $F$ (fail) & $D$ (double), so it's just $x$,$y$ and $z$ we need to determine. Let us define $h$ as the total successes (ie power of $x$) you're looking for here. for any given roll, the number of successes will be the number of $S$ events times twice the number of $D$ events, so:

$$h = x + 2z$$

And by the definition of the multinomial, $n$, the number of dice thrown:

$$n = x + y + z$$

Now, you were correct in that for any given $n$ there's multiple combinations of $x$ and $z$ that can equal $h$, so we're going to need to cycle through them and sum the probabilities together. We'll use $k$ as our iterating variable, and set $z$ to $k$ (we could set $x$ to $k$ and determine $z$, but it ends up being neater this way). We can then determine $x$:

$$h=x+2k$$ $$x=h-2k$$

And we can now use these to determine $y$:

$$n = h-2k + y + k$$ $$n=h-k+y$$ $$y=n-h+k$$

So, we now know $x$, $y$, and $z$ in terms of $h$ and $n$ and thus we have our closed form:

$$P(H=h)= \sum_{k=0}^{n}\frac{n!}{(h-2k)!(n-h+k)!k!}\left ( \frac{3}{10} \right )^{h-2k}\left ( \frac{6}{10} \right )^{n-h+k}\left (\frac{1}{10} \right )^k$$

As an aside, this can be generalised to any success-multiplier - if $m$ is our success multiplier, $z=k$, $x=h-mk$ and $y=n-h+(m-1)k$.

$\endgroup$
1
  • $\begingroup$ Another way to get normalized probabilities is to start with the unnormalized version, e.g., $f(x)=(x^2+3x+6)^n$. Then $f(x)/f(1)$ is properly normalized. (As a bonus, the first moment of the distribution is $f’(1)//f(1)$.) $\endgroup$ Dec 24, 2023 at 3:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .