Quote:
Originally Posted by OmahaDonk
Yeah, when I pressed him for some sort of analysis, he said that's what he thought I wanted. Will see if he does the more difficult problem
|
I got it *trumpets*.
I figured out how to compute the average number of rolls to get all of the numbers 2-12. The answer is 61.21738 rolls. The principle is simple, but the computations were automated to get the exact result.
The average rolls to get a 2 is 36. The average rolls to get a 2 and a 12 is
36 + (1-0.5)*36 = 54
The 0.5 is there because half of the time the 12 will come before the 2, and so the other half of the time it comes after the 2, in which case we need another 36 rolls to get the 12.
To understand the remaining terms, refer to this table, where E is the average number of rolls for each number.
Code:
number prob (in 36) E
2 1 36
12 1 36
3 2 18
11 2 18
4 3 12
10 3 12
5 4 9
9 4 9
6 5 7.2
8 5 7.2
7 6 6
Now to include another number, say 3, we get
54 + [1 - (2/3 + 2/3 - 2/4)]*18 = 57
The value in () is the probability that the 3 will come before either the 2 or the 12 by inclusion-exclusion. The probability is 2/3 that it comes before the 2, plus 2/3 that it comes before the 12, minus 2/4 that it comes before both. 1 minus that fraction of the time it comes after both, in which case we need another 18 rolls to get the 3 since it has probability 1/18.
The next one for including the 11 is
57 + [1 - (2/3 + 2/3 + 2/4 - 2/4 -2/5 - 2/5 + 2/6)]*18 = 59.4
The value in () is the probability that the 11 will come before the 2, 12, or 3. In this case, we add the 3 probabilities for coming before each of the previous 3 numbers, then subtract the 3 probabilites for coming before each of the C(3,2) = 3 combinations of 2 of the 3 numbers, then add back the probability of coming before all 3 numbers. 1 minus this fraction of the time it comes after all 3, in which case we need another 18 rolls to get the 11 since it has probability 1/18.
The next term for including the 4 is
59.4 + [1 - (3/4 + 3/4 + 3/5 + 3/5 - 3/5 - 3/6 - 3/6 - 3/6 -3/6 -3/7 + 3/7 + 3/7 + 3/8 + 3/8 - 3/9)]*12
=~ 60.05714
The value in () is the probability that the 4 will come before the 2, 12, or 3, or 11. In this case, we add the 4 probabilities for coming before each of the previous 4 numbers, then subtract the 6 probabilites for coming before each of the C(4,2) = 6 combinations of 2 of the 4 numbers, then add back the 4 probabilities of coming before each of the C(4,3) = 4 numbers, then subtract the probability of coming before all 4 numbers. 1 minus this fraction of the time it comes after all 4, in which case we need another 12 rolls to get the 4 since it has probability 1/12.
As you can see, the calculations are getting complicated quickly, and we still have 6 numbers to go. However, the numbers in [] are guaranteed to keep getting smaller since the probability of each number being after all the previous numbers gets smaller as we have more numbers and as the numbers become more probable. At this point, we know that the remaining rolls to be added must be smaller than than the last term in [], which is about 0.054762, times the sum of the average number of rolls for the remaining numbers. So the final answer T must be
T > 60.0571
and
T < 60.05741 + 0.054762*(12+9+9+7.2+7.2+6) =~ 62.81741
So by hand we have computed that it must lie between these two numbers.
Now these terms follow a pattern which I've identified, and such a pattern could be used either in an automated program to compute all of the terms, or it could possibly be used to find a generating function. However, R provides us with a convenient function which will enumerate the combinations of the elements in an array slice. This is exactly what we need here, and this makes the R program to compute all the terms very short. The function is called combn. It returns a 2-dimensional array with the combinations of a given size in each column. We sum these columns for each size combination just as we have been doing by hand.
The following R program computes the exact answer, which comes to 61.21738 rolls, in agreement with the simulations.
Code:
in_36 = c(1,1,2,2,3,3,4,4,5,5,6)
E = c(36,36,18,18,12,12,9,9,7.2,7.2,6)
T = 36
for (i in 2:11) {
p = 0
for (j in 1:(i-1)) {
terms = combn(in_36[1:(i-1)],j)
for (k in 1:(length(terms)/j)) {
p = p + (-1)^(j+1) * in_36[i]/(in_36[i] + sum(terms[1:j,k]))
}
}
T = T + (1-p)*E[i]
}
T
Two Plus Two
Linear Mode
