Expected value of highest dice rolled
You roll $N$ six-sided dice simultaneously. Your score is the highest number rolled. If you play this game many times, what is the expected value (mean) of your score?
Input
- A positive integer $N$.
- Your code must work for inputs up to and including 10, but may crash, error, or give incorrect output for larger inputs.
Output
- The expected value (the mean value) of the highest individual dice result when $N$ six-sided dice (with face values 1, 2, 3, 4, 5, 6) are rolled simultaneously.
- For inputs up to and including 10, your output is valid if rounding it to 6 decimal places results in the output shown in the test cases.
Note that this means that if you find an incorrect algorithm that happens to give the correct result when rounded to 6 decimal places for inputs from 1 to 10, that is still a valid entry.
Test cases
Test cases are in the format input : output.
1 : 3.500000
2 : 4.472222
3 : 4.958333
4 : 5.244599
5 : 5.430941
6 : 5.560292
7 : 5.654117
8 : 5.724354
9 : 5.778177
10 : 5.820159
Scoring
This is a code golf challenge. Your score is the number of bytes in your code.
Explanations are optional, but I'm more likely to upvote answers that have one.
2 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
Dyalog APL, 14 bytes
{6-+/⍵*⍨6÷⍨⍳5}
Not bruteforce! An exact implementation of the formula
\[ E_n = 6 - \sum_{i=1}^5 \left(\frac i 6\right)^n \]-
6-6 minus -
+/the sum of -
6÷⍨⍳5the list 1/6, 2/6, 3/6, 4/6, 5/6 -
⍵*⍨to the power of the argument of the function
Formula explanation
For simplicity, let's set $n=2$. This process trivially expands to higher dimensions.
If we roll 2 dice, this table represents all the possible pairs:
⍳6 6
┌───┬───┬───┬───┬───┬───┐
│1 1│1 2│1 3│1 4│1 5│1 6│
├───┼───┼───┼───┼───┼───┤
│2 1│2 2│2 3│2 4│2 5│2 6│
├───┼───┼───┼───┼───┼───┤
│3 1│3 2│3 3│3 4│3 5│3 6│
├───┼───┼───┼───┼───┼───┤
│4 1│4 2│4 3│4 4│4 5│4 6│
├───┼───┼───┼───┼───┼───┤
│5 1│5 2│5 3│5 4│5 5│5 6│
├───┼───┼───┼───┼───┼───┤
│6 1│6 2│6 3│6 4│6 5│6 6│
└───┴───┴───┴───┴───┴───┘
Let's take the maximum of each pair:
⌈/¨⍳6 6
1 2 3 4 5 6
2 2 3 4 5 6
3 3 3 4 5 6
4 4 4 4 5 6
5 5 5 5 5 6
6 6 6 6 6 6
Notice that if we sum the whole table and divide by $6^n$, we get our desired expected value
36÷⍨+/,⌈/¨⍳6 6
4.472222222
Alright, so we don't really care about the table, just its sum. I'll print it alongside the table as we build it.
(P←{⍵(+/,⍵)})⌈/¨⍳6 6
┌───────────┬───┐
│1 2 3 4 5 6│161│
│2 2 3 4 5 6│ │
│3 3 3 4 5 6│ │
│4 4 4 4 5 6│ │
│5 5 5 5 5 6│ │
│6 6 6 6 6 6│ │
└───────────┴───┘
Let's find another way to build the same table (sum). Start with a table of all 6's.
P 6 6⍴6
┌───────────┬───┐
│6 6 6 6 6 6│216│
│6 6 6 6 6 6│ │
│6 6 6 6 6 6│ │
│6 6 6 6 6 6│ │
│6 6 6 6 6 6│ │
│6 6 6 6 6 6│ │
└───────────┴───┘
We want to subtract 1 from all entries except for those in the last row or column. Alternatively, we want to subtract this table from ours:
~6∊¨⌈/¨⍳6 6
1 1 1 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0
0 0 0 0 0 0
This is a $5\times 5$ square.
We now get the following table:
P (6 6⍴6)-(~6∊¨⌈/¨⍳6 6)
┌───────────┬───┐
│5 5 5 5 5 6│191│
│5 5 5 5 5 6│ │
│5 5 5 5 5 6│ │
│5 5 5 5 5 6│ │
│5 5 5 5 5 6│ │
│6 6 6 6 6 6│ │
└───────────┴───┘
Repeating the same process for squares of side 4, 3, 2 and 1, we get exactly the original table (and sum!) we wanted.
Expressed mathematically, the expected value can therefore be written as
\[ \frac 1 {6^n} \left(6\cdot6^n - 5^n - 4^n - 3^n - 2^n - 1^n\right) = 6 - \sum_{i=1}^5 \left(\frac i 6\right)^n \]
Dyalog APL, 16 bytes
{(+/÷≢)⌈/¨,⍳⍵/6}
Explanation:
-
,⍳⍵/6generate a list of all the possible sets of rolls -
⌈/¨find the maximum of each -
+/÷≢find the average (sum up all values and divide by the length of the list)
this is incredibly slow and expensive memory-wise (computing 9 and 10 required increasing the default workspace memory size from .5GB to 2GB), but hey it works :)
1 comment thread