1
$\begingroup$

I'd like help finding a formula for the probability of rolling higher than a target number, $N$, by summing the highest $X$ number of dice out of a set $Y$ number of dice, each with $Z$ sides, numbered $1 \to Z$.

Given (and obvious): $N < X*Z, \:\:X < Y$

Edit #1: For sake of simplicity lets make $Z=6$ and $X=3$

In dice notation it would be $P(Yd6k3>N)$. Thanks to SuperJedi224 for that.

I've tried brute force through an Excel sheet and http://rumkin.com/reference/dnd/diestats.php but the Excel sheet got really cumbersome after 46656 lines ($6d6k3$) and the website bugged out at $8d6k3$.

Edit #2: What would the odds be of each of the possible outcomes on $Y$ dice?

For example, what are the odds that $Y$ dice roll the set (4,5,3)? If that could be figured out for each of the $6^3$ possible outcomes, it would get us really close to an answer for the original question.

$\endgroup$
  • $\begingroup$ You are looking for P(YdZkX>N), correct? $\endgroup$ – SuperJedi224 Feb 12 '16 at 1:05
  • $\begingroup$ Yes. I'm hoping for an answer written as a algebraic expression. $\endgroup$ – Tsorraught Feb 13 '16 at 20:29
  • $\begingroup$ Sry, I missread the question... you are adding a maximal subset of a throw. An exact answer to this problem seems too complicate, it is far faster just take the probabilities through experimentation (try something better than excel). $\endgroup$ – Masacroso Feb 14 '16 at 11:06
  • $\begingroup$ An approach could be to figure out the probability of each possible result of 3 to 18 on $X$ dice $\endgroup$ – Tsorraught Feb 15 '16 at 19:25
  • $\begingroup$ So I've found an answer to my prior comment and second edit. The probability, $P$, of getting each of the $6^3$ possible sets of 3 numbers on $Y$ dice is $[1-(5/6)^Y]*[1-(5/6)^{Y-1}]*[1-(5/6)^{Y-2}]$. Now I just need to find a little time to work out the rest of the math. $\endgroup$ – Tsorraught Feb 17 '16 at 16:13
0
$\begingroup$

Probability for some sum after discarding the $m$ lowest dice

We want to count the sum of some dice in a throw after we discard some dice with the lowest values. By example: we are throwing six dice and we want to count the sum of the four greater values (after discard the two lowest values).

For this kind of task we need to take into account a key value that I will name $v$, that is the maximum value of the dice that we are discarding. By example: we throw six dice and we get 2,3,4,1,4,3 and we want to discard the 3 lowest values, then we discard 1, 2, 3 and we hold 3, 4, 4. In this throw the $v$ value is 3, i.e., the maximum value of the discarded group.

Then we will divide our throw in two group: the discarded group and the group that we sum; and we divide the values of the dice in three kind of values: the $v$ values, the values that are lower than $v$, and the values that are greater than $v$.

Then I define to our evaluations:

  1. The number of dice in the throw is $n$.
  2. The number of sides of the dice is $d$.
  3. The length of the group to discard $m$.
  4. The key value $v$ as the maximum of the discarded group.
  5. The length $\ell$ as the number of values on the discarded group different of $v$.
  6. The length $h$ as the number of values on the non discarded group different of $v$.
  7. The sum of the non discarded group will be represented by $s$.
  8. I will represent the random variables in uppercase, by example, the random variable that take the different $m$ lengths is $M$. A dice will be represented by the random variable $X$ or $X_i$

Then the $n$ random variable $X_i$ (that represent the $n$ dice that we throw) can be of kind $\ell$, $v$ or $h$, and the discarded group only can be composed by $\ell$ or $v$ dice. And the group that we hold and sum only can be composed by dice of kind $v$ or $h$. We will symbolize these three kind of dice as $X_{\ell}$, $X_v$ and $X_h$.

Then

$$X_{\ell}\in\{1,...,v-1\},\ X_v=v,\ X_h\in\{v+1,...,d\}\\\ell\in\{0,...,m-1\},\ h\in\{0,...,n-m\},\ v\in\{1,...d\}\\m\in\{0,...,n-1\},\ s\in\{n-m,...,(n-m)d\}$$

And the probability of some sum $s$ under some condition $m$, $\ell$, $v$ and $h$ is

$$f(s,m,\ell,h,v)=\frac{[x^s]g(x,m,h,v)}{\binom{n}{\ell,h,n-\ell-h}(d-v)^h(v-1)^\ell}$$

Where $[x^s]g(x,m,h,v)$ is the coefficient of $x^s$ in the generating function

$$g(x,m,h,v)=x^{(n-m-h)v}\left(\sum_{k=v+1}^{d}x^k\right)^h=x^{(n-m)v+h}\frac{(1-x^{d-v})^h}{(1-x)^h}=\\=x^{(n-m)v+h}\sum_{j\ge 0}\binom{h+j-1}{j}x^j\sum_{k\ge 0}\binom{h}{k}(-1)^k x^{(d-v)k}$$

Then $$s=(n-m)v+h+j+(d-v)k\implies j=s-(n-m)v-(d-v)k-h$$

So $$[x^s]g(x,m,h,v)=\sum_{k\ge 0}(-1)^k\binom{s-(n-m)v-(d-v)k-1}{h-1}\binom{h}{k}$$

for binomial of positive coefficients, to be more precise

$$h-1\le s-(n-m)v-(d-v)k-1\implies k\le \frac{s-(n-m)v-h}{d-v}$$

then

$$[x^s]g(x,m,h,v)=\sum_{k= 0}^{\left\lfloor\frac{s-(n-m)v-h}{d-v}\right\rfloor}(-1)^k\binom{s-(n-m)v-(d-v)k-1}{h-1}\binom{h}{k}$$

And finally

$$f(s,m)=\sum_{\substack{1\le v\le d\\0\le\ell\le m-1\\0\le h\le m-n}}\frac{\sum_{k= 0}^{\left\lfloor\frac{s-(n-m)v-h}{d-v}\right\rfloor}(-1)^k\binom{s-(n-m)v-(d-v)k-1}{h-1}\binom{h}{k}}{\binom{n}{\ell,h,n-\ell-h}(d-v)^h(v-1)^\ell}$$

And if we want some cumulative probability we only need to sum the $s$ values for the cumulative probability that we want. By example the probability "higher than" some $s$ is

$$\Pr[S>s|M=m]=\sum_{i=s+1}^{(n-m)d}f(i,m)$$

Because this formula doesn't have a closed form and because using this directly to count with a program is not efficient (maybe except if $n$ or $d$ are too large, but anyway Im unsure) I think this formula could be useful for trying to get some approximation or bound to the real values, or it can be useful too for write a efficient program to count.

$\endgroup$
  • $\begingroup$ Thank you Masacroso. I really do appreciate all of the work you put into that, but I haven't dealt with those kinds of equations in a couple of decades and they now go right over my head. Is there possibly an equation that is more in the realm of high school algebra 1 or 2? $\endgroup$ – Tsorraught Feb 13 '16 at 20:38
  • $\begingroup$ I edited the question @Tsorraught, surely you dont have any problem now. $\endgroup$ – Masacroso Feb 13 '16 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.