Help me calculate the averages, please

[The Troubadour]

Hey there, guys! I was wondering if anyone mathematically inclined would mind helping me calculate the averages? :-)

Here's how the system would work: the player would roll a number of d10s and keep only a single one, the highest. If any d10 comes up with a 10, that die is re-rolled and the new value is added to the 10.

As an example: let's say I roll 4d10 and get 2, 3, 7 and 10. I re-roll the 10 and get a 4. So the four results I got on a 4d10 roll were 2, 3, 7 and 14, and thus, my total result for the 4d10 check was 14.

So, with all that in mind, what would be the averages for the following checks:
1d10
2d10
3d10
4d10
5d10
6d10
7d10

A many thanks for any help provided! :-D

[Ravens_cry]

Add the smallest possible number you can roll with a particular set of dice to the largest and divide by two, averaging them.
That's my system anyway.

[DonDuckie]

I will do this :D I am not going to be doing the math, because it would involve integrals with the posibility of rolling infinite 10's... which is no fun - I just failed two statistics courses :(

however, i will write a simulation of this and run it many times, and it will give a good estimate.

to be continued...

[SowZ]

It seems like a cool system. Similar in a number of ways to WoD. May be a bit slow, but if most checks and combat checks only need one such roll it shouldn't work too slowly. As far as averages, I could help if we didn't factor in the exploding die mechanic. That makes averages hard.

[Ravens_cry]

Ooh, didn't see the exploding die part. You're right, that does make averages more difficult.

[AlterForm]

Hmmm. Each face of the d10 contributes 1/10 its value to the expected value of the die roll in total. The 10 face has an effective face value of 10 + the expected value of the roll. Symbolically:

.1 * (1 + 2 + ... + (10 + X) ) = X

Solving:

5.5 + .1X = X (Distribute)

5.5 = .9X (Subtract)

X = 6.111 (Divide)

Any multiple of these dice rolls is simply a multiple of this value.

[EDIT]: Eugh, roll and keep the highest? That's gonna take longer than I expected ... the Monte Carlo Simulation suggested upthread is probably the best way to handle that unless someone stumbles on a generalized EV for "roll and take the highest." I expect the impact of additional dice to quickly become negligible, however.

[DonDuckie]

1d10s avg: 6.10286
2d10s avg: 12.2348
3d10s avg: 18.3018
4d10s avg: 24.4446
5d10s avg: 30.5327
6d10s avg: 36.6289
7d10s avg: 42.7469
8d10s avg: 48.8544
9d10s avg: 54.9971
10d10s avg: 61.1585

with 100,000 rolls for each(it's enough)

forget that, missed the "keep the highest" as well... brb

[Vitruviansquid]

Are you accounting for the fact that you're not adding the dice, but choosing the highest one out of each pool?

[DonDuckie]

1d10s avg: 6.11176
2d10s avg: 8.33768
3d10s avg: 9.69978
4d10s avg: 10.6871
5d10s avg: 11.4927
6d10s avg: 12.1573
7d10s avg: 12.7436
8d10s avg: 13.2767
9d10s avg: 13.7596
10d10s avg: 14.1765

with 1,000,000 simulations each :D happy new year

[SowZ]

Actually, if you don't want exact numbers but want a good estimate I have a WoD die roller which automatically rolls an extra die for every ten result on my computer. I could send it to you and you could run each one a couple hundred times. That should work.

Nevermind- already done for you.

[Howler Dagger]

Any Dice may help you on this quest.

[Raum]

Perhaps this will help.

(Give it a bit of time to calculate. Also, the graph is easier to read than the default.)

[DonDuckie]

Perhaps this will help.

(Give it a bit of time to calculate. Also, the graph is easier to read than the default.)

That's pretty cool, it took a while for me to understand the output, and it doesn't explode more than twice (which is a bit weird)... but still cool.

EDIT: the point
but I am a computer scientist - I re-invent the spoon before i have breakfast :D

[The Troubadour]

First of all, thanks a lot for all the help, guys! :-) Second, a Happy New Year to all! Hope you had a great night. :-D

1d10s avg: 6.11176
2d10s avg: 8.33768
3d10s avg: 9.69978
4d10s avg: 10.6871
5d10s avg: 11.4927
6d10s avg: 12.1573
7d10s avg: 12.7436

Huh. Seems like, after a certain point, adding dice doesn't really do all that much on a mathematical level, eh?

[mucco]

Yeah, because no matter how many dice you add only one can be then rerolled. If the OP had asked for a reroll of all max dice, things would have gone up slightly faster.

[Chess435]

"The GitP friendly advice dispensers: Giving helpful advice on character builds, optimization, class balance, advanced probability and statistics, quantum physics, and Cantorian Set Theory since 2004."

[The Troubadour]

Yeah, because no matter how many dice you add only one can be then rerolled. If the OP had asked for a reroll of all max dice, things would have gone up slightly faster.

...But all dice that read "10" can be re-rolled, not just a single one. :-) You just have to keep the highest of them.
For instance, if I rolled two 10's, and then re-rolled a 5 on the first one and a 3 on the second one, I'd have two results - 15 and 13 -, and would keep the 15.
I imagine what actually limits so much the benefits of additional dice after a certain point is that you can only keep one of them.

Again, thanks a lot for the help, guys! :-D

[Lapak]

Each die can only explode once though, correct? Because if your maximum possible value is theoretically infinite it complicates things a bit.

[Binks]

Each die can only explode once though, correct? Because if your maximum possible value is theoretically infinite it complicates things a bit.

Amusingly enough, no. For the result to be usable it has to be finite, as otherwise you just keep re-rolling the die forever and never get a result. So you don't have to consider infinity as a possible value for calculating the average, as it will never be the result of any finite series of rolls, and we don't care about the result of an infinite series of rolls for this scenario.

Allowing multiple explosions of dice won't do much to the end result as the probability increases by a factor of 1/10 for each +10 to the result, ie the odds of getting, say, a 45 are 10 times lower than the odds of getting a 35, so there's far lower impact on the average for the higher numbers. Not saying it wouldn't skew things, but it's not going to send the average that much higher than a single explosion per die. Infinite series can have finite results after all.

I ran the math for my own amusement a while back (was going to post it, but it was for rolling X exploding d10's and summing the result, not taking the best) and if you allow an arbitrary d10 to explode any number of times it only averages 6.1, a whole .6 over a normal d10. It's really not that big of an impact on the average (though the standard deviation and min/max go WAY out of whack).

[meschlum]

Time to bring out the math!

When rolling n dice, each a k-sider, and keeping the highest, the expected result is:

k - (Sum (i = 1, k-1) (i^n)) / k^n

Examples:

1d9: 9 - (1+2+3+4+5+6+7+8)/9 = 9 - 4 = 5. Correct!
2d2: 2 - (1)/4 = 3.75 Correct! (1/4 roll two ones. Otherwise, at least one two)
2d9: 9 - (1+4+9+16+25+36+49+64)/81 = 9 - 68/27 = 6.48148148... (175/27)

Call this number M(n,k).

So now you know the expected value when taking the highest among n dice. But you're also rerolling!

If you don't roll any tens, you've got the maximum among dice that go from 1 to 9, so n = 9 and done.

If you roll any tens, the first time through, count how many dice you're rerolling, add ten, and you're set! Repeat as needed.

With one die:

9/10: M(1,9) (since the die roll is 9 or less)
1/10: reroll, so 9/100 of 10 + M(1,9), 1/100 of another reroll. Repeat

You get Value(1) = 9/10 M(1,9) + 1/10 (10 + Value(1)), so

Value(1) = 9/10 M(1,9) + 1 + 1/10 Value(1)

9 * Value(1) = 9 M(1,9) + 10

Value(1) = M(1,9) + 10 / 9 = 5 + 1.111111 = 6.1111 Success!


With two dice:

81 / 100: M(2,9) (both dice are 9 or less)
18 / 100: 10 + Value(1) (one die is 10, add the expected value for 1 die on top)
1 / 100: 10 + Value(2) (both dice are 10, so repeat)

Value(2) = 81 M(2,9) / 100 + 18 * 16.11111 / 100 + (10 + Value(2)) / 100

99 * Value(2) = 81 M(2,9) + 300

Value(2) = 9 M(2,9) / 11 + 300 / 99 = 8.3333


With three dice:

729 / 1000: M(3,9) (all three dice at 9 or less)
243 / 1000: 10 + Value(1) (one die is 10)
27 / 1000: 10 + Value(2) (two dice are 10)
1 / 1000: 10 + Value(3) (all dice are 10)

Value(3) = 9.694694...


And so on. This is probably useless, but you now have the tools to determine the exact average for any number of dice.

[DonDuckie]

Time to bring out the math!

When rolling n dice, each a k-sider, and keeping the highest, the expected result is:

k - (Sum (1, k-1) (k^n)) / k^n

I just need to make sure i understand this function.

The underlined k in the sum is not a constant but the variable you iterate over from 1 to k-1

[meschlum]

Yes, it is. My bad. Off to edit.

There probably are equations for M(x,y) out there besides the obvious, but I'm somewhat lazy at this point. Still...

M(1,y) = y - (y-1) / 2 = (y+1) / 2
Test: M(1,9) = 10/2 = 5. Correct!

M(2,y) = y - (y-1)(2y-1) / 6y = (4y^2 + 3y - 1) / 6y = (y+1)(4y-1) / 6y
Test: M(2,9) = (324 + 27 - 1) / 54 = 175 / 27. Correct!

M(3,y) = y - (y-1)^2 / 4y = (y+1)(3y-1)/4y

Hmmm...

As a hypothesis, it looks like it could be worth testing

M(x,y) = (y+1)(2xy + 1 - x)/2(x+1)y

If it's valid, you've got an exact (and relatively easy to assess) equation for any Value you're after.

The things I do to relax.

[The Troubadour]

...
My mind! It is broken!

[DonDuckie]

As a hypothesis, it looks like it could be worth testing

M(x,y) = (y+1)(2xy + 1 - x)/2(x+1)y

If it's valid, you've got an exact (and relatively easy to assess) equation for any Value you're after.

The things I do to relax.

It's not exact. I did some testing of the two functions. it has some problems with small dice. It's done with 200,000 simulations each. Everything using double floating point precision.

I spoillered the output:

Spoiler

Show

M1: M(n,k) = k - (Sum (i = 1 to k-1) (i^n)) / k^n
M2: M(n,k) = (k+1)(2nk + 1 - n)/2(n+1)k
----------------------------------------
 #  ||   Sim   |    M1:   |    M2
 1d2|   1.49965|       1.5|       1.5
 2d2|   1.75042|      1.75|      1.75
 3d2|   1.87466|     1.875|     1.875
 4d2|    1.9375|    1.9375|      1.95
 5d2|   1.96871|   1.96875|         2
 6d2|   1.98443|   1.98438|   2.03571
 7d2|   1.99236|   1.99219|    2.0625
 8d2|   1.99645|   1.99609|   2.08333
 9d2|   1.99808|   1.99805|       2.1
10d2|   1.99904|   1.99902|   2.11364
----------------------------------------
 #  ||   Sim   |    M1:   |    M2
 1d3|   1.99943|         2|         2
 2d3|   2.44724|   2.44444|   2.44444
 3d3|   2.66885|   2.66667|   2.66667
 4d3|   2.79047|   2.79012|       2.8
 5d3|   2.86455|    2.8642|   2.88889
 6d3|   2.91127|   2.91084|   2.95238
 7d3|   2.94183|   2.94102|         3
 8d3|   2.96028|   2.96083|   3.03704
 9d3|    2.9735|   2.97394|   3.06667
10d3|   2.98252|   2.98264|   3.09091
----------------------------------------
 #  ||   Sim   |    M1:   |    M2
 1d4|   2.49831|       2.5|       2.5
 2d4|   3.12536|     3.125|     3.125
 3d4|   3.43741|    3.4375|    3.4375
 4d4|   3.61693|   3.61719|     3.625
 5d4|   3.73029|   3.73047|      3.75
 6d4|   3.80633|   3.80615|   3.83929
 7d4|   3.85887|   3.85864|   3.90625
 8d4|    3.8959|   3.89597|   3.95833
 9d4|   3.92328|   3.92296|         4
10d4|   3.94289|   3.94271|   4.03409
----------------------------------------
 #  ||   Sim   |    M1:   |    M2
 1d6|   3.50341|       3.5|       3.5
 2d6|   4.46948|   4.47222|   4.47222
 3d6|   4.95638|   4.95833|   4.95833
 4d6|   5.24592|    5.2446|      5.25
 5d6|   5.43166|   5.43094|   5.44444
 6d6|   5.56154|   5.56029|   5.58333
 7d6|   5.65495|   5.65412|    5.6875
 8d6|   5.72326|   5.72435|   5.76852
 9d6|   5.77961|   5.77818|   5.83333
10d6|   5.82047|   5.82016|   5.88636
----------------------------------------
 #  ||   Sim   |    M1:   |    M2
 1d8|   4.49934|       4.5|       4.5
 2d8|   5.80682|    5.8125|    5.8125
 3d8|   6.47154|   6.46875|   6.46875
 4d8|   6.85651|    6.8584|    6.8625
 5d8|   7.11517|   7.11475|     7.125
 6d8|     7.295|   7.29497|    7.3125
 7d8|   7.42614|   7.42765|   7.45312
 8d8|    7.5283|   7.52868|    7.5625
 9d8|   7.60698|    7.6076|      7.65
10d8|   7.67141|   7.67048|   7.72159
----------------------------------------
 #  ||   Sim   |    M1:   |    M2
 1d10|   5.50302|       5.5|       5.5
 2d10|    7.1573|      7.15|      7.15
 3d10|   7.97727|     7.975|     7.975
 4d10|   8.46575|    8.4667|      8.47
 5d10|   8.78603|   8.79175|       8.8
 6d10|   9.02407|    9.0216|   9.03571
 7d10|    9.1885|   9.19196|    9.2125
 8d10|   9.32325|   9.32269|      9.35
 9d10|   9.42508|    9.4257|      9.46
10d10|   9.50927|   9.50857|      9.55
----------------------------------------
 #  ||   Sim   |    M1:   |    M2
 1d12|   6.50219|       6.5|       6.5
 2d12|   8.48101|   8.48611|   8.48611
 3d12|   9.47781|   9.47917|   9.47917
 4d12|    10.077|   10.0722|    10.075
 5d12|   10.4626|   10.4653|   10.4722
 6d12|   10.7434|   10.7441|    10.756
 7d12|   10.9552|   10.9516|   10.9688
 8d12|   11.1129|   11.1114|   11.1343
 9d12|   11.2418|   11.2379|   11.2667
10d12|    11.339|   11.3402|    11.375
----------------------------------------
 #  ||   Sim   |    M1:   |    M2
 1d20|   10.5169|      10.5|      10.5
 2d20|   13.8292|    13.825|    13.825
 3d20|   15.4948|   15.4875|   15.4875
 4d20|   16.4755|   16.4833|    16.485
 5d20|   17.1461|   17.1458|     17.15
 6d20|   17.6104|   17.6179|    17.625
 7d20|   17.9629|   17.9709|   17.9812
 8d20|   18.2425|   18.2445|   18.2583
 9d20|   18.4603|   18.4626|     18.48
10d20|   18.6388|   18.6403|   18.6614
----------------------------------------

[Razanir]

i'm still working on the "best of n" part, but I can easily help with the exploding part:

Ignoring the exploding, we have E=.1*1+.1*2+.1*3 ... +.1*10=5.5

Because it explodes, we roll another of these dice for 10, so we add on .1*(.1*1+.1*2+.1*3 ...)

This becomes an infinite geometric series, a_1=5.5, a_n = .1*a_(n-1) or in other terms, a = 5.5, r = .1

The sum is a/(1-r) = 5.5/(1-.1) = 5.5*10/9 = 6.1111...

Generalizing with n sides instead of 10, we get n(n+1)/2(n-1)

So long story short, I can't help that much with the "best of" part, but for an exploding die with n sides, the expected value is n(n+1)/2(n-1)

[Rorrik]

Ha, and I was going to do the probability by hand because I don't have a compiler on this computer. Good work, men!

[Razanir]

Ha, and I was going to do the probability by hand because I don't have a compiler on this computer. Good work, men!

Compiler... that gives me in idea!

One java program later...

I have 95% confidence intervals for the average of 1d10 - 5d10, based of 50 data points each and a Monte Carlo approach with 1,000,000 trials each

1d10- Min: 6.102775 Mean: 6.111526 Max: 6.120277

Spoiler

Show

For comparison, the true value was previously determined to be 6.1111...

The program was right

2d10- Min: 8.323373 Mean: 8.331783 Max: 8.340192

3d10- Min: 9.686582 Mean: 9.693847 Max: 9.701111

4d10- Min: 10.680596 Mean: 10.689970 Max: 10.699343

5d10- Min: 11.478561 Mean: 11.488551 Max: 11.498542

[Dr_S]

...But all dice that read "10" can be re-rolled, not just a single one. :-) You just have to keep the highest of them.
For instance, if I rolled two 10's, and then re-rolled a 5 on the first one and a 3 on the second one, I'd have two results - 15 and 13 -, and would keep the 15.
I imagine what actually limits so much the benefits of additional dice after a certain point is that you can only keep one of them.

Again, thanks a lot for the help, guys! :-D

Did you mention what happens when someone rerolls a 10?
Do they get 20?
or 10+10+next roll?
Is there a limit?

What you've got more or less is
the sum of 1-9 plus the average score if you roll a 10 divided by 10 per dice.
I have no idea how to calculate that as say an 87 requires 8 10's to be rolled which is rare so each consecutive 10 will reduce the amount by which that roll effects your average, except that higher values increase your average also.

[Excession]

Going further than averages I wrote some Python code:

Spoiler

Show

from __future__ import division

import random


def one_die():
    score = random.randint(1, 10)
    if score == 10:
        score += random.randint(1, 10)
    return score

def n_dice(n):
    return max(one_die() for i in xrange(n))

def simulate(n, iterations=100000):
    counts = [0] * 20
    for i in xrange(iterations):
        score = n_dice(n)
        counts[score - 1] += 1
    chances = [count / iterations for count in counts]
    return chances

def main():
    for n in xrange(1, 10):
        print '%dd10' % n
        chances = simulate(n)
        for i, chance in enumerate(chances):
            score = i + 1
            print '    %2d %6.3f%%' % (score, chance * 100)

main()

Unless I screwed something up, this uses simulation to determine the chance of each score between 1 and 20 for a number of d10s ranging from 1 to 10. It turns out 9s are pretty popular. These numbers are over 100,000 iterations:

Spoiler

Show

1d10
     1 10.056%
     2  9.889%
     3 10.058%
     4 10.002%
     5 10.074%
     6 10.049%
     7  9.968%
     8 10.026%
     9 10.044%
    10  0.000%
    11  0.957%
    12  0.955%
    13  1.001%
    14  1.009%
    15  0.954%
    16  0.973%
    17  0.977%
    18  1.015%
    19  0.985%
    20  1.008%
2d10
     1  0.983%
     2  3.047%
     3  5.009%
     4  7.117%
     5  8.970%
     6 10.901%
     7 13.123%
     8 14.988%
     9 16.896%
    10  0.000%
    11  1.894%
    12  1.856%
    13  1.814%
    14  1.907%
    15  1.917%
    16  1.806%
    17  1.944%
    18  1.967%
    19  1.988%
    20  1.873%
3d10
     1  0.108%
     2  0.678%
     3  1.984%
     4  3.633%
     5  6.086%
     6  9.258%
     7 12.654%
     8 16.876%
     9 21.544%
    10  0.000%
    11  2.490%
    12  2.511%
    13  2.540%
    14  2.639%
    15  2.637%
    16  2.794%
    17  2.821%
    18  2.868%
    19  2.905%
    20  2.974%
4d10
     1  0.008%
     2  0.142%
     3  0.669%
     4  1.789%
     5  3.704%
     6  6.782%
     7 10.953%
     8 16.934%
     9 24.695%
    10  0.000%
    11  2.972%
    12  3.024%
    13  3.239%
    14  3.247%
    15  3.417%
    16  3.503%
    17  3.562%
    18  3.740%
    19  3.772%
    20  3.848%
5d10
     1  0.000%
     2  0.022%
     3  0.220%
     4  0.815%
     5  2.075%
     6  4.661%
     7  9.058%
     8 16.058%
     9 26.165%
    10  0.000%
    11  3.289%
    12  3.528%
    13  3.729%
    14  3.832%
    15  3.994%
    16  4.228%
    17  4.326%
    18  4.410%
    19  4.667%
    20  4.923%
6d10
     1  0.000%
     2  0.005%
     3  0.068%
     4  0.336%
     5  1.155%
     6  3.121%
     7  7.038%
     8 14.445%
     9 27.066%
    10  0.000%
    11  3.776%
    12  3.844%
    13  3.933%
    14  4.389%
    15  4.574%
    16  4.718%
    17  5.032%
    18  5.216%
    19  5.584%
    20  5.700%
7d10
     1  0.000%
     2  0.001%
     3  0.024%
     4  0.151%
     5  0.594%
     6  2.022%
     7  5.612%
     8 12.665%
     9 26.488%
    10  0.000%
    11  3.867%
    12  4.076%
    13  4.396%
    14  4.761%
    15  5.026%
    16  5.326%
    17  5.626%
    18  6.138%
    19  6.382%
    20  6.845%
8d10
     1  0.000%
     2  0.000%
     3  0.005%
     4  0.062%
     5  0.297%
     6  1.243%
     7  4.150%
     8 11.129%
     9 26.142%
    10  0.000%
    11  3.990%
    12  4.355%
    13  4.668%
    14  4.961%
    15  5.412%
    16  5.809%
    17  6.273%
    18  6.569%
    19  7.254%
    20  7.681%
9d10
     1  0.000%
     2  0.000%
     3  0.003%
     4  0.028%
     5  0.190%
     6  0.825%
     7  3.086%
     8  9.318%
     9 25.260%
    10  0.000%
    11  4.119%
    12  4.388%
    13  4.871%
    14  5.182%
    15  5.770%
    16  6.123%
    17  6.762%
    18  7.445%
    19  7.880%
    20  8.750%

[The Troubadour]

Did you mention what happens when someone rerolls a 10?

Terribly sorry, it seems I haven't!
I'm actually of two minds about it, but I'm leaning towards letting the player keep on "exploding" the die. Or, as you put it:

Do they get 20?
or 10+10+next roll?
Is there a limit?

The second option, and no, there's not limit.