Expected value of the minimum (discrete case)

Maybe related to this question

In the comments of this question they say that it gets easier if the variables are identically and independently distributed. But i don't see how because in my case the variable is discrete

Here is my problem : I toss 4 dice and keep the 3 best results. What is the expected value of the result ?

I think tossing 4 dice and keep the 3 best is like tossing 4 dice and removing the minimum.

• Let X be the result of a standard die.
• Let Y be tossing 4 dice and keeping the 3 best

Is that correct : $E(Y) = 4*E(X) - E(min)$ ?

So how calculate E(min) ? I know if the variable was uniform on [0,1] I could have started with $F_Y = 1 - ( 1-F_X )^p$ where p is the number of dice I toss, but here the variable is discrete so i don't know where to start.

Generalization : How to calculate the expected value of k realizations of a discrete random variable in [0-n]?

It's been a while since i studied probability, so my basic calculation may be wrong. Also, English is not my mother tongue, so please forgive my mistakes.

edit : spelling mistakes

For clarity, suppose that the dice have ID numbers $1,2,3,4$. Let $X_i$ be the result on die $i$. Let $Y$ be the sum of the three largest of the $X_i$, and let $W$ be the minimum of the $X_i$.

Then $Y=X_1+X_2+X_3+X_4-W$. By the linearity of expectation, it follows that $$E(Y)=E(X_1)+E(X_2)+E(X_3)+E(X_4)-E(W).$$ The linearity of expectation is a very useful result. Note that linearity always holds: independence is not required.

The expectation of the minimum can be calculated by first finding the distribution of the minimum $W$.

The minimum is $1$ unless the dice all show a number $\ge 2$. The probability of this is $1-\left(\frac{5}{6}\right)^4$. We rewrite this as $\frac{6^4-5^4}{6^4}$.

The minimum is $2$ if all the dice are $\ge 2$ but not all are $\ge 3$. The probability of this is $\frac{5^4-4^4}{6^4}$/

The minimum is $3$ if all results are $\ge 3$ but not all are $\ge 4$. This has probability $\frac{4^4-3^4}{6^4}$.

And so on. Now use the ordinary formula for expectation. We get that the expectation of $W$ is $$\frac{1}{6^4}\left(1(6^4-5^4)+ 2(5^4-4^4)+3(4^4-3^4)+4(3^4-2^4)+5(2^4-1^4)+6(1^4-0^4) \right).$$ We leave you the task of computing. Before computing, simplify!

Generalization: Suppose we toss $k$ "fair" $(n+1)$-sided dice, with the numbers $0$ to $n$ written on them. For $i=1$ to $k$, let $X_i$ be the number showing on the $i$-th die. Let $S$ be the sum of the dice. Then $S=X_1+\cdots+X_k$. The expectation of $X_i$ is $\frac{0+1+\cdots +n}{n+1}$. By the usual expression for the sum of consecutive integers, $E(X_i)=\frac{n}{2}$ and therefore $E(S)=\frac{kn}{2}$.

The analysis of the minimum $W$ goes along the same lines as the earlier one. The probability that the minimum is $j$ is $\frac{(n+1-j)^k -(n-j)^k}{(n+1)^k}$. If we use the ordinary formula for expectation, and simplify, we find that $$E(W)=\frac{1^k+2^k+\cdots+n^k}{(n+1)^k}.$$

A nice way to find $E(W)$: The following is a useful general result. Let $X$ be a random variable that only takes non-negative integer values. Then $$E(X)=\sum_{i=1}^\infty \Pr(X\ge i).$$ We apply that to the case of the random variable $W$ which is the minimum of $X_1,\dots,X_4$. The probability that $W\ge i$ in that case is $\frac{(7-i)^k}{6^k}$.

The same procedure works for the more general situation you asked about.

• In your initial equation do you mean E(Y) = E(X1) + E(X2) + E(X3) + E(X4) - E(W) ? – Kalissar Apr 9 '13 at 15:03
• @Kalissar: Thanks for spotting the typo! Corrected. I have added a short discussion of the general situation that you asked about. Similar techniques can be used for variants of your problem. – André Nicolas Apr 9 '13 at 15:10
• In the last formula for $E(X)$ the series should start at $i=1$. – Did Apr 10 '13 at 15:11
• Your comment is very kind but not quite accurate: this is a classical mistake... – Did Apr 10 '13 at 15:52

Yes, your equation is correct, and this is a good and efficient way to perform this calculation. To find the expected value of the minimum, consider the hypercubes $[k,6]^4$ for $k=1,\dotsc,6$. The number of these hypercubes that a result is in is given by the minimum value of the dice. Thus we get the expected value of the minimum by adding up the probabilities of hitting these hypercubes:

$$\mathbb E[\min]=\frac{\displaystyle\sum_{k=1}^6k^4}{6^4}=\left.\frac1{30}\frac{n(n+1)(2n+1)(3n^2+3n-1)}{6^4}\right|_{n=6}=\frac{2275}{1296}\approx1.7554\;.$$

• Thank you very much. I accepted the other answer because it includes a way to calculate the distribution. I find yours very interesting though. – Kalissar Apr 9 '13 at 15:15
• @Kalissar: No worries about accepting the answer. About the distribution: Because of the linearity of expectation, expected values are often much easier to obtain than distributions. So if you wanted the distribution, that's good, but if you don't need it and only need the expected value, then an approach that doesn't involve calculating the distribution is usually better. – joriki Apr 9 '13 at 15:27