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$
6
  • $\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
    Commented Mar 3, 2016 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
    Commented Mar 3, 2016 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
    Commented Mar 3, 2016 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
    Commented Mar 3, 2016 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
    Commented Mar 4, 2016 at 15:13

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .