16
$\begingroup$

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.

enter image description here

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?
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Masacroso Mar 3 '16 at 19:22
  • $\begingroup$ 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$? $\endgroup$ – anonymouse Mar 3 '16 at 19:26
  • $\begingroup$ $\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. $\endgroup$ – Masacroso Mar 3 '16 at 19:33
  • $\begingroup$ Maybe a less complicated approach is just count the throws were $M=m$ and take the mean of it (discarding the minimum). $\endgroup$ – Masacroso Mar 3 '16 at 19:45
  • $\begingroup$ I'm not sure I completely understand. What do you mean by "count the throws where $M = m$ and take the mean of it"? $\endgroup$ – anonymouse Mar 4 '16 at 15:13
4
+50
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – anonymouse Mar 7 '16 at 14:51
  • $\begingroup$ @SSS I have added the argument for general $m$. Let me know if you have any questions. $\endgroup$ – user940 Mar 10 '16 at 2:18
0
$\begingroup$

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.)

$\endgroup$

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.