Sunday, April 15, 2018

probability - 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


Answer



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.



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...