Exploding dice: Help with calculating averages

[jpegbert]

I am working on a system that uses exploding dice against a target number.  Can someone tell me how to calculate an average roll for an exploding die of any size?  I'm pretty sure it involves calculas but I'm willing to give it a whirl.  Alternately, if someone just happens to know the averages for the following exploding dice: d4, d6, d8, d10, and d12, that'd be good too.  I understand that averages aren't the end-all-be-all and that the distributions are pretty kurtioc (kurtotic?) but I just need a rough idea of how my system pans out.  

Also, any comments or critisism of the system would be appreciated.  Basically the way it works is this: Skill success is determined by: Attribute+1d10+Proficiency Die.  The Proficiency Die can be any die between 1d4 and 1d12, depending on how skilled the character is.  The proficiency die and only the proficiency die explodes infinitely.  Characters untrained in the skill they are using do not get a proficiency die.

[Harlequin]

No calculus, just a trick.

Call the actual average on one exploding die, X.  The size of the die is N sides.

On the 1 through (N-1) sides, we just get its value, so these sides contribute (1+2+...+(N-1))/N to the average value.  One plus two plus... plus Q in general, can be expressed as (1/2)*(Q^2+Q) - I always forget how to prove this, and have to empirically recreate it, but it's correct.  So with (N-1) as Q, this is (1/2)*((N^2-2N+1)+(N-1)) = (1/2)*(N^2-N).

The last side, the exploding side, contributes (1/N) - for being only one side of the die - times its value, which is N plus another exploding die, whose average is going to be X.  This gets us:

X = (N^2 - N)/(2N) + (N+X)/N = N/2 + 1/2 + X/N

Moving both Xes to the left, we get:

X * (1 - 1/N) = N/2 + 1/2 = (N + 1)/2

or, multiplying both sides by N,

X * (N - 1) = (N^2 + N)/2

so, bringing the (N - 1) to the right:

X = (N^2 + N)/(2N - 2)

which is the value you wanted.  Unless I've made an error somewhere which is quite possible as I'm redoing this here.  Insert the die size N.  For a d4, for example, this makes it (16+4)/(8-2) = 20/6 = 3.3333... .

The important thing to remember is that just 'cause a d4 open-ends more easily than a d6, does NOT mean that this helps its average roll or even its odds of any given roll over 3.  So your system sounds reasonable enough, and you can figure that the proficiency die will make a difference to their average roll equal to the above formula.

- Eric

[Calithena]

Hi there.

Harlequin, your numbers are right if you don't subtract one from the extra dice after the first. If you do that (so you get a continuous curve: your way you can roll e.g. on a d6 1 thru 5 or 7 thru 11 or ... (ie no multiples of 6).

If you do subtract that one point off the extra dice for explosion, to ensure a smooth range of numbers, the averages are always exactly half a point higher than the normal. So 3 for d4, 4 for d6, 5 for d8, 6 for d10, and 7 for d12.

I get off doing this calculation e.g. for the d4 as letting the average equal an infinite sequence (x=2.5+.25*(1.5+.25*(1.5... and then multiplying through by 4 and setting the same infinite sequence equal to x-2.5, then solving.  This is 'street math' though - I don't think Cauchy or Weierstrass would have approved. But it works.

[HMT]

No calculus, just a trick.

... One plus two plus... plus Q in general, can be expressed as (1/2)*(Q^2+Q) - I always forget how to prove this, ...

- Eric

To prove this consider twice this number:

1   +    2    +    3     + ... + (Q-1) + Q +
Q + (Q-1) + (Q-2) + ... +    2    + 1

Combine each term in the last row with the term above it:

(Q+1) + (Q+1) + (Q+1) + ... + (Q+1) + (Q+1)

to get Q identical terms, each equal to Q+1.

[Calithena]

Oh, I love math. I can't resist going on about this a little bit more.

Let's say you've got an exploding d8. Then your average is

x=36/8+1/8*(28/8+1/8*(28/8....

So you multiply through by 8 and get

8x = 36+28/8+1/8*(28/8+1/8*.....

Now note that everything to the right of the 28/8 is the last term in x! So substituting we see that that whole infinite expression is itself equal to x-36/8, and thus

8x = 36+28/8+x-36/8

so when we cancel we get

7x = 35 and x =5, which is the right average for the exploding d8 with the ones shaved off.

If you just added another d8 to every 8 indefinitely you would have instead

x=36/8+1/8*(36/8+1/8*(36/8....

8x = 36+36/8+1/8*(36/8+1/8*.....

8x = 36+36/8+x-36/8

or 7x=36 which is some crappy decimal you can calculate for yourself. Another reason to subtract one from the extra exploding dice after the first.

[Calithena]

Here's some theorems though.

For an n-sided die, an exploding die that does NOT have one subtracted from it will average SUM(x from 1 to n) over n-1.

If it does have one subtracted from it, it will average SUM(x from 2 to n) over n-1. This is always equal to n/2+1 for n>= 2. An exploding coin averages 2 for instance (if you score heads 1 and tails 2 I mean).

Consequently the extra factor you get from that additional point on the exploding die is not equal for all dice. Your average for an 'unshaved' exploding die will be (n/2)+1+(1/n-1): five and one-seventh for the eight-sider, but three and one-third for the four-sider, and eleven and one-nineteenth for the twenty-sider.

[Harlequin]

All of which, I'm sure, does nothing for the thread starter.  Easy, guys.  Be nice. :)  There are other ramifications to the "continuous exploding die" - mostly social ones having to do with your target audience.  And those are a lot more important than the above.

Just because we're math geeks doesn't mean it has to show.  (But if it does, shameless plug, go check out Attack Vector: Tactics which has math geek fun aplenty - just what tricks can one use to make vector calculus in arbitrary 3-space doable for eight-year-olds?  Come look.  </plug>)

- Eric

[Valamir]

I told Ken accurate vector movement without simplifying assumptions in a playable game was impossible.
I told him making it 3d and keeping it playable was impossible
I told him tracking ballistic weapons in a playable manner was impossible.

I've had to eat a lot of crow talking to Ken.
He does things with math that are illegal in 17 states.

[Ron Edwards]

Hi everyone,

Guys, restrain yourselves for a while and let jpegbert give you some feedback on whether you're helping him or not.

Yeah, this is one of those moderator posts; I'm wearing the hat with the little points around the rim this time.

Best,
Ron

[Harlequin]

Yes, moderator Ron.  I still wanted to grin at Ralph for that last - because the last two impossible things on that list I take personal credit for.  Thank you, Ralph.

- Eric

[jpegbert]

Wow, this must be an active board.  I had no idea there would be this many responses to such an esoteric topic this quickly.  

Because I didn't think I would get replies this quickly, I decided to use the brute force method to see what I came up with.  I whipped up a quick die rolling program.  In all cases I took the average of 1mill. iterations.  Results:
d4: 2.78
d6: 3.89
d8: 5.00
d10: 5.55
d12: 6.56

I noticed these deviated from the formulae you guys provided so I audited my program by running it through data sets of 5, giving me the rolls as it went so that I could manually calculate the results, so it appears to be calculating averages correctly.  I then removed the exploding part of the code and ran every die through 1 mill. iterations just to see if the randomizer was skewed but all averages came out as expected.  Do my results HAVE to be wrong.  It's possible that I screwed somehting up in the code but if so, the error doesn't show up for small datasets.

[jpegbert]

I just noticed that the d10 and the d 12 results are extremely whacky, but the code for two digit dice was slightly different then for the others.  I will review that part again, but the d4 - d8 looks solid as far as I can see.

[Harlequin]

Strange... aha.  Your listed result for a d8, plus Sean (Calithena)'s post above, make me suspect that you're using "with the ones shaved" methods just as Sean was discussing.

If I roll an eight on d8, roll again, get a three, do I have an eleven in your system, or a ten?  The system which makes that roll an eleven has bobbles (eight and sixteen aren't possible rolls), which is why some games "shave" things so that the exploding die keeps seven (on a d8) and then rolls again and adds.  In which case Sean quotes 5.00 as the average on d8, same as you obtain, and my derivation would need to use (N - 1 + X)/N in the place of the (N + X)/N term.

It's not a proof, but it's a guess.  Otherwise I'm not sure; Sean's post does seem to validate my algebra, which otherwise I'd point to as most likely to contain an error (having been tossed rapidly together right here).

Failing that, I'm not sure.  Perhaps your random number generator does have one-after-the-next issues, which affect the explosions but are hiding in the nonexploding data?  (Stronger chance that, after rolling an M, you're likelier to roll M-2 than anything else, modulo the die size... that sort of thing would do it, and be fairly well hidden without statistical analysis.  Perhaps you should log the difference between each roll and the one before it, and histogram those results - the above M -> M+2 rule would spike around -2, with a smaller rise above background at +6.  It is of course unlikely to be so simple, if this is the problem.)

- Eric

[jpegbert]

point taken on shaving the ones.  But aside from the d8, my results seem all seem lower than the algrebraic methods posted here.  Wouldn't shaving the ones generally result in an even lower average?

I'm afraid you lost me on your methodological suggestions.  I'm afraid I'm not much of a statician.

[Harlequin]

Your averages are low, and the shave-the-ones results are also low, so I figured that might be the case.  You might want to recheck the code for that; your post makes it obvious that this isn't intentional, if so.

Another thought is that although your nonexploding-die results look OK, and therefore you're obviously mapping the standard (0-0.99999) computer random number scale into the (1 to N) scale of integers properly at that point, rounding properly to get that transfer can be tricky.  Perhaps you're adding two not-yet-rounded-up values together and then rounding to the next highest int, or perhaps your exploded die is rounding down instead of up, that kind of thing.  With a low value that's where I might look in the code.

Finally, to elucidate the methodology suggested (though I should note that I'm fairly confident that the algebraic method is correct so you may just want to give up the program as an unknown bibble and go on with your life), what I'm suggesting is do this (d8s used as the specific die size for example purposes):

- Every time you roll a die (an actual, "physical" d8), log its value.  Also, except for the very first die rolled, subtract the value of the previous die roll from this one.  [In practice, subtract first, then overwrite the log of "last roll" with the current die roll.]
- Tally the result.  By this I mean, keep track of how many minus-sevens this operation generates, and also minus-sixes, minus-fives, zeroes, and the rest through plus-sevens.
- After you've done your million exploding dice rolls, and have therefore rolled rather more than a million actual "physical" exploding dice, you'll have very large numbers in each of these categories.  Graph these as a bar graph, with -7, -6, etc, +7 along the x-axis and number of occurrences as the y-value.
- You'll get a huge triangular curve, whereby zero is roughly eight times as common as -7, because there are eight sequences which give zero (one-then-one, two-then-two, etc), but only one which gives -7.  This will almost certainly swamp out all real data if you've taken a million data points.  Take it away; subtract off the theoretical distribution one would expect given the number of dice you "rolled" and keep only what's left.
- Then look at the result.  The skew I described, and it's unlikely to actually occur, would be a case of "weighted dice" where each roll tended (very slightly) to be two less than the previous one, wrapping around such that sevens were likely to follow ones and eights to follow twos.  The result would be seen in your bar graph, where you'd get a spike at -2 (die roll number M+1 is likely to be two less than die roll M) and another at +6 (for the one-seven, two-eight pattern).

Basically it's a pattern which would, if present, give the lowered average you see, because although it wouldn't change the overall average on nonexploding dice, the explosive die would tend to be smaller than the one that produced it.  [Actually, I suppose the pattern would only have to key to eights, nothing else, since that's the condition to explode.]

But really. You don't need to know this, I don't think.  The odds of a discernible pattern like this emerging from any half-decent computer random number chart are very, very low... perhaps lower than the chance of your average being off in those million tries, perhaps not.

And either way, all you're trying to do is predict how well Joe the Skilled Warrior will tend to do at poking people with sharp things.  The difference between his skill die producing 2.78 or 3.33 on average, especially when a true average result is always less common than we think, is probably not worth the breath we've spent on it. :)

- Eric