Roll 14 dice, take the highest 7

[Jademonkey]

I was playing a pencil and paper role playing game with some friends, and some questions came up about the what is most important to increase to get better at a skill. There are two values for each skill- the basic value and your training value. The basic value ranges from 1-7 and determines how many six sided dice you can add to your ability check. The training value must be less than or equal to your basic value and let's your roll extra dice, allowing you to keep the (basic value) highest.

For example, if you have a basic value of 5 and a training value of 3, you roll 8 dice and take the sum of the 5 highest.

I'm interested in determining how the mean (and maybe median) change as you add more basic and training dice.

I initially started to brute for the problem using java, but quickly realized that I'm working on a O(6^n) problem that way. So I decided to think about it a little more, and I'm probably going to use mathematica to implement something along these lines:

Let's say I'm using 7 basic and 7 training, for simplicity.
I view the problem as a question of combinations and permutations on a multiset, in essence.

We only need to worry about the highest 7 rolls, since we know that the other seven must be less than or equal to the lowest of the first seven.

Thus, for the lowest seven, there are always (lowest roll of the first 7)^7 possible permutations.

Then I'll use the multinomial theorem to find the number of permutations for each highest 7 dice combination. Since we are looking at the number of 7-combinations of 6 objects, there are only 792 (6+7-1 choose 7) to go through. Easy with a computer.

So, to find the mean, for each highest 7 dice outcome, I sum the dice, mutliply by the multinomial coefficient, and multiply by the number of permutations of the remaining seven dice with the restriction previously mentioned in mind. Then, I'll add all of these sums to together and divide by 6^14- the number of possible permutations on 14 dice.

I think the median would be fairly simple from here, since there are only 35 possible sums (7-42, all ones to all sixes), and I can easily figure out how many of each sum are possible then choose the middle based on that.

Is my logic here sound? Are there better ways to go about this? Is there a viable way of doing this without computer aid?

Thanks in advance!

PS: Sorry for the potentially superfluous back story and long post. I didn't want anyone to think I was trying to cheat on an assignment lol.

 

[techmologist]

This is a cool problem.

If I'm understanding your method correctly, it looks good except for one thing. It doesn't take into account that there are fewer outcomes in which the lowest roll of the highest 7 also occurs in the lowest 7. In other words, you are overcounting the outcomes where the highest 7 and lowest 7 both contain a roll of 3, say. Actually, it is probably more correct to say that you are undercounting those outcomes where the highest 7 and lowest 7 are disjoint in terms of values.

To see what I mean, apply your method to the easy case of rolling two dice and keeping the highest roll (roll 2, take the highest 1). If the highest is 3, there are 3^1 possible values for the lowest. So your method gives 3 ways to get 3 as the highest. But in reality, each of the outcomes (1,3) and (2,3) happens in two ways, while the outcome (3,3) happens only one way, for a total of 5 ways to get 3 as the highest. If you were to multiply your formula by (2*N choose N) = 2 to account for the number of ways of separating 2N dice rolls into the N highest and N lowest, your answer would give 6 ways of getting 3 as the highest roll. And in that case you would be counting the outcome (3,3) twice.

 

[Borek]

I think you will get quite good results calculating averages for - say - 1000 "experiments" for each base/training pair you are interested in. Or make it 10000. Or 100000 if 10000 calculates in a blink

 

[Jademonkey]

This is a cool problem.

If I'm understanding your method correctly, it looks good except for one thing. It doesn't take into account that there are fewer outcomes in which the lowest roll of the highest 7 also occurs in the lowest 7. In other words, you are overcounting the outcomes where the highest 7 and lowest 7 both contain a roll of 3, say. Actually, it is probably more correct to say that you are undercounting those outcomes where the highest 7 and lowest 7 are disjoint in terms of values.

To see what I mean, apply your method to the easy case of rolling two dice and keeping the highest roll (roll 2, take the highest 1). If the highest is 3, there are 3^1 possible values for the lowest. So your method gives 3 ways to get 3 as the highest. But in reality, each of the outcomes (1,3) and (2,3) happens in two ways, while the outcome (3,3) happens only one way, for a total of 5 ways to get 3 as the highest. If you were to multiply your formula by (2*N choose N) = 2 to account for the number of ways of separating 2N dice rolls into the N highest and N lowest, your answer would give 6 ways of getting 3 as the highest roll. And in that case you would be counting the outcome (3,3) twice.

Oh wow, you are absolutely right. I should know better than placing an order on something that has no order! Thanks.

Should I be summing the multinomial coefficients on the lowest seven instead, then? Is there a simple identity for that?

I think you will get quite good results calculating averages for - say - 1000 "experiments" for each base/training pair you are interested in. Or make it 10000. Or 100000 if 10000 calculates in a blink

I think I will do this, but the mathematics major in me wants to figure out an exact answer too! Thanks for the simpler approach!

 

[techmologist]

Oh wow, you are absolutely right. I should know better than placing an order on something that has no order! Thanks.

Should I be summing the multinomial coefficients on the lowest seven instead, then? Is there a simple identity for that.

The only way I see to do it is to conditionalize on how many times the lowest of the highest 7 (call this value x), occurs in the entire set of 14 dice rolls. You've got 14 dice rolls, i of them are strictly less than x, j of them are equal to x, and the rest are greater than x. The value x occurs i+j-7 times in the highest 7. So, for the highest 7 to sum to some value S, the 14-i-j rolls that are greater than x must sum to S-(i+j-7)x. When you figure out the expression in terms of i, j, and x, you then sum over the possible values of i, j, and x to get the total number of ways that the highest 7 sum to S. It is messy, but I think it works. Is this making sense?

 

[Jademonkey]

I'm going to have to think about the combinatorial approach a little more. I may see if one of my old professors minds looking at it with me.

Anyway, here's the results from 10 million trials (each) in java, in case anyone cares. The first number represents the number of dice taken, the second (with a b) represents the number of extra dice rolled. So, 5 4b means roll 9 dice and sum the highest 5, for example.

Good to know that the returns of more bonus dice diminish fairly quickly.

Average of 1 0b = 3.4999777
Average of 1 1b = 4.4716185
Average of 2 0b = 7.0006233
Average of 2 1b = 8.45763
Average of 2 2b = 9.3440604
Average of 3 0b = 10.5014903
Average of 3 1b = 12.2434161
Average of 3 2b = 13.4298458
Average of 3 3b = 14.2725354
Average of 4 0b = 14.0001635
Average of 4 1b = 15.9302557
Average of 4 2b = 17.3435511
Average of 4 3b = 18.4023819
Average of 4 4b = 19.2234638
Average of 5 0b = 17.499684
Average of 5 1b = 19.5581609
Average of 5 2b = 21.1533658
Average of 5 3b = 22.3887886
Average of 5 4b = 23.3748975
Average of 5 5b = 24.1810492
Average of 6 0b = 21.0013445
Average of 6 1b = 23.1531813
Average of 6 2b = 24.8863648
Average of 6 3b = 26.2756418
Average of 6 4b = 27.4074786
Average of 6 5b = 28.3481214
Average of 6 6b = 29.1414323
Average of 7 0b = 24.5008945
Average of 7 1b = 26.7252489
Average of 7 2b = 28.5727906
Average of 7 3b = 30.0860764
Average of 7 4b = 31.3482481
Average of 7 5b = 32.4114345
Average of 7 6b = 33.319577
Average of 7 7b = 34.1048892

 

[techmologist]

good agreement with theoretical value

The values from your simulation agree very nicely with the theoretical values:

1 basic, 0 training: expected sum 3.500000
1 basic, 1 training: expected sum 4.472222
2 basic, 0 training: expected sum 7.000000
2 basic, 1 training: expected sum 8.458333
2 basic, 2 training: expected sum 9.344136
3 basic, 0 training: expected sum 10.500000
3 basic, 1 training: expected sum 12.244599
3 basic, 2 training: expected sum 13.430170
3 basic, 3 training: expected sum 14.273791
4 basic, 0 training: expected sum 14.000000
4 basic, 1 training: expected sum 15.930941
4 basic, 2 training: expected sum 17.344479
4 basic, 3 training: expected sum 18.402756
4 basic, 4 training: expected sum 19.222277
5 basic, 0 training: expected sum 17.500000
5 basic, 1 training: expected sum 19.560292
5 basic, 2 training: expected sum 21.151460
5 basic, 3 training: expected sum 22.388805
5 basic, 4 training: expected sum 23.375062
5 basic, 5 training: expected sum 24.179310
6 basic, 0 training: expected sum 21.000000
6 basic, 1 training: expected sum 23.154117
6 basic, 2 training: expected sum 24.886813
6 basic, 3 training: expected sum 26.274812
6 basic, 4 training: expected sum 27.406675
6 basic, 5 training: expected sum 28.347241
6 basic, 6 training: expected sum 29.141009
7 basic, 0 training: expected sum 24.500000
7 basic, 1 training: expected sum 26.724354
7 basic, 2 training: expected sum 28.571949
7 basic, 3 training: expected sum 30.088016
7 basic, 4 training: expected sum 31.347410
7 basic, 5 training: expected sum 32.410309
7 basic, 6 training: expected sum 33.319426
7 basic, 7 training: expected sum 1.823745

Obviously the last one isn't right. I'm guessing the binomial coefficients got too large and overflowed some variable. You still have access to your old profs? Cool. Yeah, if you can get a professor to help you that would be awesome. Also, If you want me to expand on the hints I gave in post #5, I can.