Can anyone solve this probability problem?
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 1034
 Joined: Fri Feb 07, 2014 3:15 pm UTC
Can anyone solve this probability problem?
First of all, read this: http://www.mspaintadventures.com/extras/ps000020.html
If the die in the center of that machine had n sides, what would the average resulting damage be.
If the die in the center of that machine had n sides, what would the average resulting damage be.
"You are not running off with CowSkull Man Dracula Skeletor!"
Socrates
Socrates
Re: Can anyone solve this probability problem?
to be clear, the k crucibles are created each with an ksided dice if the prime dice rolls k?
Re: Can anyone solve this probability problem?
If we roll a single die with a_1 sides, our expected output is E_1(a_1) = (1+a_1)/2.
If we roll two dice, each (initially) with a_2 sides, then our first roll is equally likely to be any number from 1 to a_2. This modifies the second die, to be either a_2, 2 a_2, ..., or a_2^2. The expected values of each of these rolls, respectively, are E_1(a_2) = 1/2(1+a_2), E_1(2a_2) = 1/2(1+2a_2), ..., and E_1(a_2^2) = 1/2(1+a_2^2), so the expected value of the twodie system is 1/a_2 [1/2(1+a_2) + 1/2(1+2a_2) + ... + 1/2(1+ a_2^2)] = 1/(2a_2) [(1+1+...+1) + (a_2 + 2a_2 + ... + a_2^2)] = 1/(2a_2) [a_2 + a_2^2 (a_2+1)/2] = 1/2 [1 + a_2 (a_2 + 1)/2] = 1/2 + 1/4 a_2 + 1/4 a_2^2 = E_2(a_2).
If we roll three dice, each (initially) with a_3 sides, then our first roll is equally likely to be any number from 1 to a_3. This modifies the other two dice, so that we then perform the twodie scenario with a_2 = a_3, or 2a_3, or..., or a_3^2. Each of these is equally likely, and we know the expected value for each (since we know the expected value for the general twodie roll), so the expected value of the threedie roll is 1/a_3 [(1/2 + 1/4 a_3 + 1/4 a_3^2) + (1/2 + 1/4 (2 a_3) + 1/4 (2 a_3)^2) + ... + (1/2 + 1/4 (a_3)^2 + 1/4 (a_3^2)^2) ] = 1/a_3 [1/2 (1+1+...+1) + 1/4 (a_3 + 2 a_3 + ... + a_3)^2 + 1/4 (a_3^2 + (2 a_3)^2 + ... + ((a_3)^2)^2)] = 1/a_3 [1/2 (1+1+...+1) + 1/4 a_3(1 + 2 + ... + a_3) + 1/4 a_3^2 (1^2 + 2^2 + ... + a_3^2)] = 1/a_3 [1/2 a_3 + 1/4 a_3^2 (a_3+1)/2 + 1/4 a_3^3 (a_3+1)(2a_3+1)/6 ] = 1/2 + 1/8 a_3 (a_3 + 1) + 1/24 a_3^2 (a_3+1)(2a_3+1) = 1/2 + [1/8 a_3 + 1/8 a_3^2] + [1/24 a_3^2 + 1/8 a_3^3 + 1/12 a_3^4] = 1/2 + 1/8 a_3 + 1/6 a_3^2 + 1/8 a_3^3 + 1/12 a_3^4 = E_3(a_3).
We can see, then, the general pattern: E_n(k) = 1/k(E_{n1}(k) + E_{n1}(2k) + E_{n1}(3k) + ... + E_{n1}(k^2)). This sum involves the sum from 1 to k of various power functions. I'm not sure what a closed form would be, but it can be recursively calculated as far as you need it.
Then, an msided generator die has an expected value of 1/m (E_1(1) + E_2(2) + E_3(3) + ... + E_m(m)).
If we roll two dice, each (initially) with a_2 sides, then our first roll is equally likely to be any number from 1 to a_2. This modifies the second die, to be either a_2, 2 a_2, ..., or a_2^2. The expected values of each of these rolls, respectively, are E_1(a_2) = 1/2(1+a_2), E_1(2a_2) = 1/2(1+2a_2), ..., and E_1(a_2^2) = 1/2(1+a_2^2), so the expected value of the twodie system is 1/a_2 [1/2(1+a_2) + 1/2(1+2a_2) + ... + 1/2(1+ a_2^2)] = 1/(2a_2) [(1+1+...+1) + (a_2 + 2a_2 + ... + a_2^2)] = 1/(2a_2) [a_2 + a_2^2 (a_2+1)/2] = 1/2 [1 + a_2 (a_2 + 1)/2] = 1/2 + 1/4 a_2 + 1/4 a_2^2 = E_2(a_2).
If we roll three dice, each (initially) with a_3 sides, then our first roll is equally likely to be any number from 1 to a_3. This modifies the other two dice, so that we then perform the twodie scenario with a_2 = a_3, or 2a_3, or..., or a_3^2. Each of these is equally likely, and we know the expected value for each (since we know the expected value for the general twodie roll), so the expected value of the threedie roll is 1/a_3 [(1/2 + 1/4 a_3 + 1/4 a_3^2) + (1/2 + 1/4 (2 a_3) + 1/4 (2 a_3)^2) + ... + (1/2 + 1/4 (a_3)^2 + 1/4 (a_3^2)^2) ] = 1/a_3 [1/2 (1+1+...+1) + 1/4 (a_3 + 2 a_3 + ... + a_3)^2 + 1/4 (a_3^2 + (2 a_3)^2 + ... + ((a_3)^2)^2)] = 1/a_3 [1/2 (1+1+...+1) + 1/4 a_3(1 + 2 + ... + a_3) + 1/4 a_3^2 (1^2 + 2^2 + ... + a_3^2)] = 1/a_3 [1/2 a_3 + 1/4 a_3^2 (a_3+1)/2 + 1/4 a_3^3 (a_3+1)(2a_3+1)/6 ] = 1/2 + 1/8 a_3 (a_3 + 1) + 1/24 a_3^2 (a_3+1)(2a_3+1) = 1/2 + [1/8 a_3 + 1/8 a_3^2] + [1/24 a_3^2 + 1/8 a_3^3 + 1/12 a_3^4] = 1/2 + 1/8 a_3 + 1/6 a_3^2 + 1/8 a_3^3 + 1/12 a_3^4 = E_3(a_3).
We can see, then, the general pattern: E_n(k) = 1/k(E_{n1}(k) + E_{n1}(2k) + E_{n1}(3k) + ... + E_{n1}(k^2)). This sum involves the sum from 1 to k of various power functions. I'm not sure what a closed form would be, but it can be recursively calculated as far as you need it.
Then, an msided generator die has an expected value of 1/m (E_1(1) + E_2(2) + E_3(3) + ... + E_m(m)).
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: Can anyone solve this probability problem?
>) wrote:to be clear, the k crucibles are created each with an ksided dice if the prime dice rolls k?
I thought the first step was the number of iterations. Otherwise the center one is just like the others.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Can anyone solve this probability problem?
We can approximate this as a continuous process. Suppose instead of your dice having n sides, it produced a uniform distribution from 0 to 1. We then took the ln of this value, and added up k such rolls.
If we raise it e^ of the resulting sum, this is the same as the product of the values.
Some work still needs to be done.
Imagine a_0 as 0 to 1. a_1 is then 0 to a_0. a_2 is then 0 to a_1.
Now take a_2 * 6^3  that closely mirrors the distribution we'd get with the discrete rolls.
I think the observation worth mentioning is that the early roll has a larger impact than later rolls. A 2 on the first roll means every other roll is roughly doubled  a two on the last roll, and only the result is doubled. In effect, with 6 cascades, the first one is ^6, while the last one is ^1.
Now, ln( 6 * uniform(0,1) ) is ln(6) + ln uniform(0,1).
e^{ 6 ln 6 * ( sum i = 1 to 6[ (ln 6 + ln uniform(0,1))^(i) ] )}
which is still a mess.
Still, we can use this to approximate the lnaverage of the result. Given the exponential process, that may even be more meaningful than the linearaverage.
The lnaverage gives us the geometric mean, which is a kind of average.
...
Stepping back, another approach would be to bound the effects of simplification. Treating a roll of 2 on the first roll as doubling the result isn't quite right, because of the "half steps" left out. In effect, a roll of 2 on the first die makes the second die return a die twice as big, but you also subtract a (d21) from the result  a fudge factor.
If you roll a 6 on the first die, the second die is x6 the old value, minus (d61) fudge factor.
If you roll a k on the first die, the second die is d6 * k, minus a (dk1) fudge factor.
If we neglect the fudge factors at every stage, then the size of the last die is (d6)^5 * (d6)^4 * (d6)^3 * (d6)^2 * (d6)^1. This has a universe size of 7776 elements. Exhaustively examining this space is easy. Then the average value of the last die is easy to calculate.
We can do the same for the 6 possible "seed" die rolls.
Finally, repeat this process with a maximized fudge factor.
That will give us a window within which the average must occur. I expect it to be large, but it at least gives you orders of magnitude of orders of magnitude of orders of magnitude of the result.
If we raise it e^ of the resulting sum, this is the same as the product of the values.
Some work still needs to be done.
Imagine a_0 as 0 to 1. a_1 is then 0 to a_0. a_2 is then 0 to a_1.
Now take a_2 * 6^3  that closely mirrors the distribution we'd get with the discrete rolls.
I think the observation worth mentioning is that the early roll has a larger impact than later rolls. A 2 on the first roll means every other roll is roughly doubled  a two on the last roll, and only the result is doubled. In effect, with 6 cascades, the first one is ^6, while the last one is ^1.
Now, ln( 6 * uniform(0,1) ) is ln(6) + ln uniform(0,1).
e^{ 6 ln 6 * ( sum i = 1 to 6[ (ln 6 + ln uniform(0,1))^(i) ] )}
which is still a mess.
Still, we can use this to approximate the lnaverage of the result. Given the exponential process, that may even be more meaningful than the linearaverage.
The lnaverage gives us the geometric mean, which is a kind of average.
...
Stepping back, another approach would be to bound the effects of simplification. Treating a roll of 2 on the first roll as doubling the result isn't quite right, because of the "half steps" left out. In effect, a roll of 2 on the first die makes the second die return a die twice as big, but you also subtract a (d21) from the result  a fudge factor.
If you roll a 6 on the first die, the second die is x6 the old value, minus (d61) fudge factor.
If you roll a k on the first die, the second die is d6 * k, minus a (dk1) fudge factor.
If we neglect the fudge factors at every stage, then the size of the last die is (d6)^5 * (d6)^4 * (d6)^3 * (d6)^2 * (d6)^1. This has a universe size of 7776 elements. Exhaustively examining this space is easy. Then the average value of the last die is easy to calculate.
We can do the same for the 6 possible "seed" die rolls.
Finally, repeat this process with a maximized fudge factor.
That will give us a window within which the average must occur. I expect it to be large, but it at least gives you orders of magnitude of orders of magnitude of orders of magnitude of the result.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Can anyone solve this probability problem?
Just to clarify the question in programmer's terms, using pseudocode:
...is this an accurate model for the question being asked?
(The question here of course being, "What is the average return value for this pseudocode?")
Code: Select all
prime_bubble = rand(6);
// Note: rand(n) returns a random whole number from 1 to n.
die_size = 6;
while (prime_bubble > 1)
{
die_size *= rand(die_size);
prime_bubble = 1;
}
return rand(die_size);
(The question here of course being, "What is the average return value for this pseudocode?")
There's no such thing as a funny sig.
 Xanthir
 My HERO!!!
 Posts: 5423
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Can anyone solve this probability problem?
Yes, that's accurate pseudocode for the table, I think.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
Re: Can anyone solve this probability problem?
I believe there are three possible interpretations of the prime die. Assuming you roll an N on the prime die, it can mean either:
Roll N dice, starting with a d6.
Roll 6 dice, starting with a dN.
Roll N dice, starting with a dN.
Roll N dice, starting with a d6.
Roll 6 dice, starting with a dN.
Roll N dice, starting with a dN.
 Xanthir
 My HERO!!!
 Posts: 5423
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Can anyone solve this probability problem?
Yes, those are possible interpretations, but all but the first is vanishingly unlikely. There are 6 potential spots for a bubble to appear, and dN with N != 2, 4, or 6 is rare and strange. So starting with a d6 seems very likely, with the prime controlling the number of bubbles you get.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
 Eebster the Great
 Posts: 3484
 Joined: Mon Nov 10, 2008 12:58 am UTC
 Location: Cleveland, Ohio
Re: Can anyone solve this probability problem?
What if instead of the expected value, we asked what the probability of rolling 1 was? I assume it would be 1/36 + some small amount, right?
 Xanthir
 My HERO!!!
 Posts: 5423
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 Contact:
Re: Can anyone solve this probability problem?
Yeah.
It looks like the sum ends up about 1.5/36, or between 4% and 5%.
 If the prime bubble rolls a 1, then the single damage die has to roll a 1. 1/6*1/6 = 1/36
 If the prime bubble rolls a 2, then you have to end up rolling a 1 on the second die. This is either a 1/6, 1/12, 1/18, 1/24, 1/30, or 1/36 chance, depending on the first die roll, all with an equal chance of happening. Averaging them gives you approximately 1/15, times 1/6 for approximately 1/90 total.
 Higher prime results are more complicated, but boil down to the same thing. The third one is worth a little less than 1/300, the fourth is about 1/1560, etc.
It looks like the sum ends up about 1.5/36, or between 4% and 5%.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
 Eebster the Great
 Posts: 3484
 Joined: Mon Nov 10, 2008 12:58 am UTC
 Location: Cleveland, Ohio
Re: Can anyone solve this probability problem?
Yeah the second term is a bit larger than I expected, 49/4320 = .0113, but the general idea seems ok.
The expected value is very hard to estimate, since the number of sides grows much faster than the denominator of the probability.
The expected value is very hard to estimate, since the number of sides grows much faster than the denominator of the probability.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Can anyone solve this probability problem?
So I wrote some code to find an upper bound.
We have 1d61 cascade dice, 1 final die.
The normal rules have each cascade die equal to the product of the previous cascade dice, times 6. The final die is the product of all the cascade dice.
I replaced this with the value of each cascade die is 1d6 times the produce of the values of the previous cascade dice. This is easy to show as being strictly larger. (as 2*1d6 is strictly larger than 1d12).
http://coliru.stackedcrooked.com/a/3dddaadbce785ea8 is an attempt to program it. It is untested and an early pass, it probably contains errors.
It outputs 1.5e9.
Note that the largest die size possible is 6^(6*5/2) = 470184984576. Which is 300 times larger than the average. So at least the average is plausible.
We have 1d61 cascade dice, 1 final die.
The normal rules have each cascade die equal to the product of the previous cascade dice, times 6. The final die is the product of all the cascade dice.
I replaced this with the value of each cascade die is 1d6 times the produce of the values of the previous cascade dice. This is easy to show as being strictly larger. (as 2*1d6 is strictly larger than 1d12).
http://coliru.stackedcrooked.com/a/3dddaadbce785ea8 is an attempt to program it. It is untested and an early pass, it probably contains errors.
It outputs 1.5e9.
Note that the largest die size possible is 6^(6*5/2) = 470184984576. Which is 300 times larger than the average. So at least the average is plausible.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Can anyone solve this probability problem?
Yakk wrote:Note that the largest die size possible is 6^(6*5/2) = 470184984576. Which is 300 times larger than the average. So at least the average is plausible.
What? The largest possible die is 6^(2^5). On a best roll you square the remaining dice, and this could happen 5 times at best.
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
 Eebster the Great
 Posts: 3484
 Joined: Mon Nov 10, 2008 12:58 am UTC
 Location: Cleveland, Ohio
Re: Can anyone solve this probability problem?
Yeah, the best possible result is 6^{2⁵} = 6^{32} = 7958661109946400884391936 = 7.96 * 10^{24}.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Can anyone solve this probability problem?
Hmm. I may have made a mistake in my code then. Or maybe just my math.
0 die cascade (before the final die): max 6 (6^1)
1 die cascade (before the final die): max 36 (6^2)
2 die cascade (before the final die): max 1296 (6^4) not 6^(2+1)
3 die cascade (before the final die): max 1679616 (6^8) not 6^(3+2+1)
So my math is in error. Did I screw up the program as well?
If we roll 6 6 6 k with virtual dice, we rolled 6 36 1296 k*279936 with the real dice.
My math and program did 6^3 * 6^2 * 6 = 6^6
While the actual die size looks like:
6 * 6*(6) * 6*((6*(6))*6) = 6^7
Instead of the 6 applying once per later die, it applies once to the next die, twice to the next one, 4 times to the next one, etc. Hurm.
Here is updated version:
http://coliru.stackedcrooked.com/a/885b0a4f6c748e94
1.7e21 average?
0 die cascade (before the final die): max 6 (6^1)
1 die cascade (before the final die): max 36 (6^2)
2 die cascade (before the final die): max 1296 (6^4) not 6^(2+1)
3 die cascade (before the final die): max 1679616 (6^8) not 6^(3+2+1)
So my math is in error. Did I screw up the program as well?
If we roll 6 6 6 k with virtual dice, we rolled 6 36 1296 k*279936 with the real dice.
My math and program did 6^3 * 6^2 * 6 = 6^6
While the actual die size looks like:
6 * 6*(6) * 6*((6*(6))*6) = 6^7
Instead of the 6 applying once per later die, it applies once to the next die, twice to the next one, 4 times to the next one, etc. Hurm.
Here is updated version:
http://coliru.stackedcrooked.com/a/885b0a4f6c748e94
1.7e21 average?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Who is online
Users browsing this forum: No registered users and 6 guests