Sum of best X dice in Y dice rolled (or roll X pick best Y) odds/calculation

Question

Background: In many pen and paper RPGs there is often an option or bonus/penalty to rolls that incorporates rolling multiples of the required die and taking the best or worst of those rolls for your roll.

Example: Advantage/Disadvantage in D&D 5e is best/worst die in 2 twenty-sided die rolls. This generally alters the average roll (of 1d20 or one twenty-sided die equaling 10.5) by 3.325 total (average of 13.825 with Advantage, 7.175 with Disadvantage).

Example 2: Best two dice of three six-sided dice rolled. This usually improves the average roll (of 2d6 or two six-sided dice summed, 7) by 1.45833 (8.4583 3-repeating if best, 5.5416 6-repeating if worst) total.

Example 3: Best two of four six-sided dice rolled. This usually improves the average roll (of 2d6 or two six-sided dice summed, 7) by about 2.344136 (9.344136 if best, 4.655864 if worst) total.

Questions: I was wondering what the specific means of calculating certain total rolls (such as rolls totaling a specific number, or that number and higher) and averages would be? Or if that was more easy to calculate than simply finding all the possible combinations and totaling them.

Part A: Given X best of Y dice with Z number of sides, is there a simple expression one can write to calculate this easier than just summing all the combinations?

Part B: Given the above scenario, is there a simple expression one can write to calculate the number of rolls at/equaling a specific number?

Part C: Given the above scenarios, is there a simple expression one can write to calculate the number of rolls at/equaling or above a specific number?

Other notes: I imagine that this will include a lot of factorial math and the Permutation/Combination functions, but I'm not sure how to proceed.

Answer 1

I will use the notation that there are $n$ dice in total, $k$ highest of them are kept and each die has $d$ faces.

There is a method to count them with a Markov chain where states are $k$-multi-subsets of $[0\dots d]$. I will encode such a multi-subset as a $k$-vector sorted in ascending order. From each state $(x_1, \dots , x_k)$ we make a transition with each value $v \in [1\dots d]$ (having probability $\frac{1}{d}$) to a state that is gotten by

• If $v<x_1$: replacing $x_1$ with $v$ if $x_1<v$ (and sorting the vector again)
• otherwise: doing nothing, i.e. transition is to the same state

For example ($k=3, d=6$) from the state $(0, 2, 5)$ with $v=3$ we make a transition to the state $(2, 3, 5)$.

In words, a state records the dice we are currently keeping (zero indicates a missing die) and a transition corresponds to rolling another die.

We start from $(0,\dots, 0)$ and make $n$ transitions, so the probabilities of arriving at a particular state can be read from the first row of the $n$th power of the transition matrix (assuming we index $(0,\dots, 0)$ as the first state). Here's an example with $k=2, d=2, n=3$. In the graph the edge labels mean how many transitions lead to that state, i.e. with how many different die-values is it made. The circles are self-loops. (Sorry, I can't make the picture nice, Sage just draws it how it wants.)

If states are indexed as [(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2)] the transition matrix is

$$ A = \frac{1}{2} \displaystyle \left(\begin{array}{rrrrrr} 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 2 \end{array}\right) A^3 = \frac{1}{8} \displaystyle \left(\begin{array}{rrrrrr} 0 & 0 & 0 & 1 & 3 & 4 \\ 0 & 0 & 0 & 1 & 3 & 4 \\ 0 & 0 & 0 & 0 & 1 & 7 \\ 0 & 0 & 0 & 1 & 3 & 4 \\ 0 & 0 & 0 & 0 & 1 & 7 \\ 0 & 0 & 0 & 0 & 0 & 8 \end{array}\right) $$

Now, if we want the probability of the total to equal $s$, sum all the entries of first row off $A^3$ where the state sums to $s$. For the previous example and $s=3$ you would take just the $\frac{3}{8}$ corresponding to the state $(1, 2)$.

Here's a Sage code doing these calculations. The function returns a dictionary that tells for each state how many rolls lead to it, you get probabilities by dividing by $d^n$.