A friend pointed out to me that the dice puzzle of last week is very similar to one posted here. However, the variation posted there (#50) is more complex. Still, it is easily solved with the simple tools of probability.

Again we throw a handful of dice, but instead of asking how many dice we would throw to have even odds of all faces appearing, we ask a different question: What is the expected value of the highest face to appear when looking at the results of throwing n dice?

From last week we know that when a person throws 15 dice, there is about an even chance that all faces will appear at least once. So we guess that for n equal to 15 or greater that we will expect six to be the highest number. Of course that is a long way from specifying a numerical probability. Naively we might guess that with six dice the odds are about even that six will be the highest number, but that is a guess.

My background is physics. Physicists like to approach problems by considering the limits or boundary conditions. We have loosely established an upper boundary condition beyond which the answer is always six. What about a lower bound? If we throw one die, what is the expected highest number? Since a die has six sides, we might guess that the most probable highest value is 3.5 since this cuts the continuum in half. That is, the probability of the die coming up four or greater is 0.5. The probability of the die coming up three or less is 0.5. So the boundary must be in the middle between three and four. So we guess at 3.5. Now we can start the hard work of trying to solve the problem exactly and comparing the results with these initial estimates.

Try it yourself before reading on. (BTW, would you prefer I wait a week to show the solution to this type of problem?)

In what follows, I will use Nick’s notation for those of you who might want to compare our methods. Start by remembering the each throw is an independent event. Then observe that, for a value, if k is the range of one through six, there are k ways that a die can show k or lower. That is, if k = three, then there are three values equal to less than three. That is pretty straightforward.

Next, since the face of each die is independent of the others, there are k^{n} ways that the ensemble of dice will show k or lower. There are six ^{n} total ways for the dice to fall. We know how to calculate the probability that the k face of lower will be the expected value (right?). Now all we have to do is subtract the “or lower” part.

The number of ways the highest face is lower that k is simply (k-1)^{n}. So the number of ways that k is the highest number showing divided by the total number of ways (i.e. the probability of k) is [k^{n} – (k-1)^{n}]/6^{n}. This looks formidable, but we are almost there.

The expected value is the sum of k times the probability of k for all values of k (1-6). The simplified expression for this is not as bad as you might think. Nick shows it as:

E(^{n}) = [6(6^{n}-5^{n}) + 5(5^{n}-4^{n}) + 4(4^{n}-3^{n}) + 3(3^{n}-2^{n}) + 2(2^{n}-1^{n}) + 1(1^{n}-0^{n})]/6^{n}.

= 6 – (1^{n} + 2^{n} + 3^{n} + 4^{n} + 5^{n})/6^{n}.

You do not need to work it down to that detail to get the results, but it is a pretty result. If you solve for n=1 (the only value you can do easily in your head), you get 3.5! If you work out the expected values for other n’s, you will see that by the time you get to n=6, the odds are slightly better than even that the highest face shown will be six — so our initial guess was not too bad!

*In response to the interest my original tutorial generated, I have completely rewritten and expanded it. Check out the tutorial availability through Lockergnome. The new version is over 100 pages long with chapters that alternate between discussion of the theoretical aspects and puzzles just for the fun of it. Puzzle lovers will be glad to know that I included an answers section that includes discussions as to why the answer is correct and how it was obtained. Most of the material has appeared in these columns, but some is new. Most of the discussions are expanded compared to what they were in the original column format.*

[tags]statistics, probability, decision theory[/tags]