Needs moar math: Reroll averages Question [RESOLVED]

[ben-zayb]

Does anyone have a shortcut for determining averages for rerolls of the notation XdnB1 (roll a dN dice X times, and then choose the best roll)

My initial result is:
[summation of (n*((n^X)-((n-1)^X))), from n=1 to n=N]/(N^X)

That's...crazy complicated for my average D&D. In normal D&D where X is just 2 (I.e. abilities that let's someone reroll once and take the better roll), the equation is a simpler:
(n*(2n-1)), from n=1 to n=N]/(N^2), which is easier on the eyes in practice...

[1*1 + 2*3 + 3*5 + 4*7 + ... (N*(2N-1))]/(N^2) for a dN dice

So am I missing another shortcut somewhere, or is determining average rolls serious business??

[ben-zayb]

Bumping in case our resident math wizards are already available...

[Lightlawbliss]

might I recomend anydice (http://anydice.com/).

[ben-zayb]

Hmm.. that's quite neat. Thanks!:smallbiggrin:

I still do have to get the summation of (n * probability of n), from n=1 to n=N, and then divide it by 100, to get the average roll, but that looks faster if done on a no-function calculator the bigger a dice gets (i.e. d100). Still a bit more math for my average D&D game, but this one looks better.

EDIT: Whoa, didn't see the Export button already has the average die... now this is awesome! And a few clicks/type away, so less math for my average D&D game.:smallamused:

[Lightlawbliss]

the function library on the side will help you use even less math. also, there is the summary option on the main page

[meschlum]

Does anyone have a shortcut for determining averages for rerolls of the notation XdnB1 (roll a dN dice X times, and then choose the best roll)

My initial result is:
[summation of (n*((n^X)-((n-1)^X))), from n=1 to n=N]/(N^X)

That's...crazy complicated for my average D&D. In normal D&D where X is just 2 (I.e. abilities that let's someone reroll once and take the better roll), the equation is a simpler:
(n*(2n-1)), from n=1 to n=N]/(N^2), which is easier on the eyes in practice...

[1*1 + 2*3 + 3*5 + 4*7 + ... (N*(2N-1))]/(N^2) for a dN dice

So am I missing another shortcut somewhere, or is determining average rolls serious business??


Of course there are shortcuts. Especially in this case, where you're just taking the best die result. If you were rolling 2 dice many times and taking the best total, things would be much less pleasant.

One standard trick is that the sum of n^X for n=1 to N is fairly well known, so you can cheat.

Another relies on cleverly rearranging the numbers so things cancel out as efficiently as possible.

Behold!

n * (n^X) - n * (n - 1)^X = n ^ (X+1) - (n-1+1) * (n-1)^X
= n^(X+1) - (n-1)*(n-1)^X - (n-1)^X
= n^(X+1) - (n-1)^(X+1) - (n-1)^X

So if you sum that from n=1 to n=N, the first two terms almost completely cancel out, and you get

N^(X+1) - 0 - sum(n=0 to n=N-1) (n^X), and since 0^X = 0

= N^(X+1) - sum(n=1 to n=N-1) (n^X)

Next, the sum of n^X can be computed fairly easily, as it is a polynomial of order X+1, with well known behavior at low n.

X = 1: sum of (n=1 to n=K) (n) = a (K)^2 + b (K) + c
K = 0: get 0, so c = 0
K = 1: get 1, so a + b = 1, so b = 1 - a
K = 2: get 3, so 4a + 2b = 3, so 4a + 2(1 - a) = 3, so 2a + 2 = 3, so 2a = 1

This gives K(K+1)/2

So you get (N-1)N/2 for the sum, and the total is N(N+1)/2. Divide by N, and you get (N+1)/2, which is the average of a dN.


X = 2: sum of n^2 = aK^3 + bk^2 +cK + d
K = 0: sum = 0, so d = 0 (this extends to all X)
K = 1: sum = 1, so a + b + c = 1, and c = 1 - a - b
K = 2: sum = 5, so 8a + 4b + 2(1 - a - b) = 5
6a + 2b = 3, so b = 3/2 - 3a
K = 3: sum = 14, so 27a + 9(3/2 - 3a) + 3(1 - a - (3/2 - 3a)) = 14
27/2 + 3 - 3a - 9/2 + 9a = 14
18/2 + 3 + 6a = 14
12 + 6a = 14
6a = 2
a = 1/3, b = 1/2, c = 1/6
This gives K(2K^2+3K+1)/6 = K(K+1)(2K+1)/6

So you get (N-1)N(2N-1)/6 for the sum, and the total is (N^3 - 2N^3/6) +3N^2/6 - N/6, which can be simplified to:

2N^3/3 + N^2/2 - N/6 = N(4N^2+3N - 1)/6 = N(N+1)(4N-1)/6. Divide by N^2, and you get (N+1)(4N-1)/6N.

The average of a dN is (N+1)/2, so you have (N+1)/2 * (4N-1)/3N.

As N becomes large, the second term gets close to 4/3, so for large dice you're increasing you average by a factor of 4/3 (and a bit less for small dice: with a d2 you're multiplying by 'only' 7/6).


X = 3: aK^4 + bK^3 + cK^2 +dK (n=0 tells us e = 0)
K = 1: the sum is 1
K = 2: the sum is 9 (= 3^2)
K = 3: the sum is 36 (= 6^2)
K = 4: the sum is 100 (= 10^2)

We take the convenient shortcut being offered here, and notice that we're getting the square of 1, 3, 6, 10... which are the sums for X=1.

So we get a total of (K(K+1)/2)^2 for the sum. That's K^4/4 + K^3/2 + K^2/4

The difference is 3N^4/4 - N^3/2 -N^2/4 = N^2(3N^2 - N - 1)/4. Sadly, this does not simplify conveniently any further.

The average is therefore (3N^2 - N - 1)/4N, so it's around 3N/4 when N is large - about 3/2 times the average value with no rerolls.


So you'll notice that there are some interesting trends taking place if you're willing to use approximations.

X = 1: average is about N/2
X = 2: average is about 2N/3
X = 3: average is about 3N/4
...

A bit of thought should suggest what happens for higher values of X, so long as the dice are large.