# Rolling $n$ $k$-sided dice and discarding the lowest $m$ of them.

In this question I will use the notation $\Bbb{E}(n,k,m)$ to refer to the expected average of rolling $n$ $k$-sided dice and discarding the lowest $m$ of them.

The most trivial response happens when $m = 0$, in which case we discard no dice and we arrive at the result:

$$\Bbb{E}(n,k,0) = \frac{k}{2} + \frac{1}{2}$$

When $m = 1$, I considered a sample case to give some intuition for this problem. Looking at the case of $\Bbb{E}(2, 6, 1)$, I found the following pattern. There are one $1$s, three $2$s, five $3$s, etc.

The sum of these outcomes is:

$$\sum_{i=1}^{6} i(2i-1)$$

In general, the expected outcome for $\Bbb{E}(2,k,1)$ is:

$$\frac{\sum_{i=1}^{k} i(2i-1)}{k^2} = \frac{\sum_{i=1}^{k} 2i^2 - \sum_{i=1}^{k} i}{k^2} = \frac{\frac{2k(k+1)(2k+1)}{6} - \frac{k(k+1)}{2}}{k^2} = \frac{2}{3}k + \frac{1}{2} - \frac{1}{6k}$$

Now I want to consider $\Bbb{E}(3,k,2)$. In the previous case each value $i$ occurred $2i - 1$ number of times. Where did $2i - 1$ come from?

It looks like the frequency of occurrence is the difference of consecutive squares.

$$i^2 - (i-1)^2 = 2i - 1$$

This seems intuitive based on the image I provided. We can reason that in the case of $n = 3$, the frequency of occurrence will be the difference of consecutive cubes.

$$i^3 - (i-1)^3 = 3i^2 - 3i + 1$$

The expected outcome of $\Bbb{E}(3,k,2)$ is messy, so I'll just write the initial expression and the simplified expression.

$$\frac{\sum_{i=1}^{k} i(3i^2-3i+1)}{k^3} = \frac{3}{4}k + \frac{1}{2} - \frac{1}{4k}$$

Let's finally look at the case of $\Bbb{E}(n,k,n-1)$. Based on the previous results, I conjecture that it looks like:

$$\frac{\sum_{i=1}^{k} i(i^n - (i-1)^n))}{k^n} = \frac{n}{n+1}k + \frac{1}{2} - \mathcal{O}(\frac{1}{k})$$

My two questions are this:

• Is my conjecture for $\Bbb{E}(n,k,n-1)$ correct, and if so, how can I prove this?
• What happens when $m \ne n-1$? How can I adjust my analysis to account for discarding dice such that I leave not just the maximum value?
• If $m>1$ I dont think a closed form exist, just brute force or some kind of bound. For $m=1$ you are just discarding the minimum, for this case exist a closest form (you can use conditional probabilities). – Masacroso Mar 3 '16 at 19:22
• I just edited my post: my analysis isn't actually the case of $m = 1$ (discarding the minimum), but actually the case of $m = n - 1$ (discarding all but the maximum). How would I compute a closed form for the case of $m = 1$? – anonymouse Mar 3 '16 at 19:26
• $\Pr[\text{some setup}|M=m]$ where $M$ is the random variable for the minimum and "some setup" any kind of group where the values are equal or more than $m$. The probability $\Pr[M=m]$ is easier to evaluate through $\Pr[M\le m]$ and when you have $F_M(m)$ taking the derivative what is just $\nabla F_M(m)=f_m(m)$, where $\nabla$ is the backward difference operator. – Masacroso Mar 3 '16 at 19:33
• Maybe a less complicated approach is just count the throws were $M=m$ and take the mean of it (discarding the minimum). – Masacroso Mar 3 '16 at 19:45
• I'm not sure I completely understand. What do you mean by "count the throws where $M = m$ and take the mean of it"? – anonymouse Mar 4 '16 at 15:13

If $M$ is the maximum value on the $n$ dice thrown, then $\mathbb{P}(M\leq x)=(x/k)^n$ so that $\mathbb{E}(M)=\sum_{x=0}^{k-1} \left(1-\left({x\over k}\right)^n\right)=k-{1\over k^n}\sum_{x=0}^{k-1}x^n.$ Using Faulhaber's formula you can show that $$\sum_{x=0}^{k-1}x^n ={1\over n+1}\left[k^{n+1}-{1\over 2}(n+1)k^n+O(k^{n-1})\right]$$ and putting these together gives, as you expected, $$\mathbb{E}(M)={n\over n+1}\,k+{1\over 2}+O(1/k).$$

Here is a more general argument. For any $1\leq j\leq n$ let $X_{(j)}$ be the $j$th order statistic of the $n$ dice rolls. For $0\leq x<k$, let $Y$ be the number of dice rolls that take values in $\{1,2,\dots, x\}$. We have $X_{(j)}>x$ if and only if $Y<j$ so that $$\mathbb{P}(X_{(j)}>x)=\mathbb{P}(Y<j)=\sum_{y=0}^{j-1}{n\choose y} \left({x\over k}\right)^y \left(1-{x\over k}\right)^{n-y}.$$

Therefore we have the explicit formula $$\mathbb{E}(X_{(j)})=\sum_{x=0}^{k-1}\sum_{y=0}^{j-1}{n\choose y} \left({x\over k}\right)^y \left(1-{x\over k}\right)^{n-y}.\tag1$$

For large $k$ asymptotics, exchange the order of summation and rewrite as a Riemann sum to get $$\mathbb{E}(X_{(j)})=k\sum_{y=0}^{j-1}\sum_{x=0}^{k-1}{n\choose y} \left({x\over k}\right)^y \left(1-{x\over k}\right)^{n-y}{1\over k}\approx k\sum_{y=0}^{j-1} \int_0^1 {n\choose y} w^y(1-w)^{n-y}\,dw={k\,j\over n+1}.$$

Using the Euler-Maclaurin formula, you can get more terms in the asymptotic expansion, for example, $$\mathbb{E}(X_{(j)})={k\,j\over n+1}+{1\over 2}+O(1/k).$$

Asymptotics are nice, but the formula (1) also allows us to derive the bounds $${kj\over n+1}\leq \mathbb{E}(X_{(j)})\leq {kj\over n+1}+1.$$

• There's no way to extend this idea to other values of $m$, is there? Here we considered the maximal dice because we're discarding all but 1, but perhaps there's a way to consider the two maximal dice, maybe with a second summation... – anonymouse Mar 7 '16 at 14:51
• @SSS I have added the argument for general $m$. Let me know if you have any questions. – user940 Mar 10 '16 at 2:18

## Expected value of a dice after throwing it $n$ times and discarding the lowest $m$ values

We start with some $n$ identical fair dice of $d$ sides that go from $1$ to $d$. I will start defining for each dice a random variable $X_i$, and I will define the r.v. $A$ as the average of the $X_i$ i.e.

$$A=\frac1n\sum X_i$$

Then the expected value of $A$ will be

$$\Bbb E[A]=\Bbb E\left[\frac1n\sum X_i\right]=\frac1n\sum\Bbb E[X_i]$$

Then we define two groups: the discarded group of length $m$ and the remaining group of length $n-m$, and three kind of dice depending of the values that hold in some setup: the dice $X_v$ with the maximum value $v$ of the discarded group, the dice $X_\ell$ with values lower than $v$, and the dice $X_h$ that hold values greater than $v$ i.e.

$$X_v=v,\ X_\ell\in\{1,...,v-1\},\text{ and }X_h\in\{v+1,...,d\}\\V\in\{1,...,d\}$$

where $V$ is the r.v. for the $v$ value. The three kind of dice are independent one of each other but they range depends of $V$.

Any throw is composed of dice of these three kind, throws only differ in the amount of each kind, and in every throw at least a dice of the kind $X_v$ is present. I will name the amount of $X_\ell$ as just the r.v. $L$, the amount of $X_h$ as $H$ and finally the amount of $X_v$ will be $n-H-L$, i.e.

$$L\in\{0,...,m-1\},\text{ and }H\in\{0,n-m\}$$

Notice that $L$ and $H$ are independent one of each other but they range depends of $V$, by example if $V=1$ there aren't $X_\ell$ dice in the throw so $L=0$.

Then we have that

\begin{align}\Bbb E[A|H,L,V]&=\frac1n\sum\Bbb E[X_i]=\frac1n(L\Bbb E[X_ \ell]+H\Bbb E[X_h]+(n-H-L)\Bbb E[X_v])\\&=\frac1n\left(\frac12LV+\frac12H(d+V+1)+(n-H-L)V\right) \end{align}

because $\Bbb E[X_\ell]=\Bbb E[X|X<v]$ and $\Bbb E[X_h]=\Bbb E[X|X>v]$ (notice that $\{X_i: X_i<v\}$, $\{X_i: X_i=v\}$ and $\{X_i: X_i>v\}$ is just a partition of the set $\{X_i\}$).

But cause we are discarding the $m$ lowest values we want average only the $X_i$ of the remaining group composed only of $X_h$ and some $X_v$ i.e.

$$\Bbb E[A^*|H,V]=\frac1{n-m}\left(H\frac{d+V+1}{2}+(n-m-H)V\right)$$

and

\begin{align}\Bbb E[A^*]&=\Bbb E[\Bbb E[A^*|H,V]]\\&=\sum_{h,v}\Bbb E[A^*|H=h,V=v]\Pr[H=h,V=v]\\&=\sum_{h,v}\frac1{n-m}\left(h\frac{d+v+1}{2}+(n-m-h)v\right)f(h,v)\end{align}

where $f(h,v)$ is the joint mass probability function of $H$ and $V$, and this is a marginal distribution of the more general $f(h,\ell,v)$ i.e. the joint mass probability function of $H$, $L$ and $V$, that is a kind of multinomial distribution because represent the different setups of a throw divided into three kind of events with different probability each one, i.e.

\begin{align}f(h,\ell,v)&=\binom{n}{\ell,h,n-\ell-h}\Pr[X_i>v]^h\Pr[X_i<v]^\ell\Pr[X_i=v]^{n-\ell-h}\\&=\binom{n}{\ell,h,n-\ell-h}\left(\frac{d-v}{d}\right)^h\left(\frac{v-1}{d}\right)^\ell\left(\frac{1}{d}\right)^{n-\ell-h}\\&=\frac1{d^n}\cdot\frac{n^{\underline{\ell+h}}}{\ell!h!}(d-v)^h(v-1)^\ell\end{align}

(where $a^{\underline b}$ is a falling factorial) and

$$f(h,v)=\sum_\ell f(h,\ell,v)$$

Then finally we have

\begin{align}\Bbb E[A^*]&=\sum_{h,\ell,v}\left(\frac{h(d+1-v)}{2(n-m)}+v\right)\binom{n}{\ell,h,n-\ell-h}\left(\frac{d-v}{d}\right)^h\left(\frac{v-1}{d}\right)^\ell\left(\frac{1}{d}\right)^{n-\ell-h}\\&=\frac1{d^n}\sum_{h,\ell,v}\left(\frac{h(d+1-v)}{2(n-m)}+v\right)\frac{n^{\underline{\ell+h}}}{\ell!h!}(d-v)^h(v-1)^\ell\end{align}

and I dont think that this expression can be simplified significantly (partial multinomial sums doesn't have closed form). Anyway you can use it to develop some program to evaluate $\Bbb E[A^*]$.

(*The range of the different summations are the range of the respective r.v.)