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:
- The number of dice in the throw is $n$.
- The number of sides of the dice is $d$.
- The length of the group to discard $m$.
- The key value $v$ as the maximum of the discarded group.
- The length $\ell$ as the number of values on the discarded group different of $v$.
- The length $h$ as the number of values on the non discarded group different of $v$.
- The sum of the non discarded group will be represented by $s$.
- 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.
P(YdZkX>N), correct? $\endgroup$ – SuperJedi224 Feb 12 '16 at 1:05