
Book of Hook Also, I can kill you with my brain

View previous topic :: View next topic 
Author 
Message 
brianhook Site Admin
Joined: 12 Dec 2003 Posts: 2521 Location: seattle, wa

Posted: Fri May 20, 2005 2:06 am Post subject: Math challenge! 


My math sucks, so I spent tonight trying to analytically determine the average value of a 3d6 that's open ended, i.e. when a 6 is rolled, you substitute 6 + reroll (ad infinitum).
In my stupidity I went ahead and unrolled it, looked at it, and came up with a summation of an infinite series and then got stumped trying to figure out if it converged or not. So when I got stuck there, I asked around, and...
Someone else came up with a stupidly simple algebraic solution that I'm embarrassed I didn't figure out, but it goes to show just how much of math (and programming) is strictly intuitive and not rote.
This reminds me of a similar graphics problem of "How do you recover the frustum planes from a projection matrix" which had similarly intuitive, algebraic answer but which I couldn't think of to save my life. 

Back to top 


brianhook Site Admin
Joined: 12 Dec 2003 Posts: 2521 Location: seattle, wa

Posted: Sat May 21, 2005 6:06 pm Post subject: 


Okay, so here it is.
Basically the average of a 1d6 is 3.5 (1+2+3+4+5+6)/6. If you open end it, then algebraically it becomes:
Code: 
X = ( 1 + 2 + 3 + 4 + 5 + 6 + X ) /6
6X = 21+X
5X = 21
X = 21/5
X = 4.2

However that's not terribly stable, and if you substitute arbitrary values for the unroll it can explode (drive towards infinity) with strange answers like X=21. Still I should have thought about it, but I'm not terribly comfortable defining variables in terms of themselves. It feels unnatural.
The correct way is to do this as a summation of an infinite series:
F(x) = 15(2x1)/6^x
SUM( x=1, x > +inf, F(x) )
If I take the above and put it into MathCAD it solves for what you'd expect (4.2), however I have no idea how to do that manually. Most texts indicate that you should look for a common sequence pattern and then substitute for that, but of the sequences I've seen that converge (geometric, etc.) it doesn't fit.
So I'm not sure if I'm missing something or what, but maybe one of y'all with a formal edumacation can fill me in. 

Back to top 


Gus_Smedstad
Joined: 17 Dec 2003 Posts: 590 Location: Boston area, MA

Posted: Sat May 21, 2005 7:22 pm Post subject: 


I used to know how to answer stuff like that. Haven't used that part of my brain for neigh on 20 years, so it's all rotted away.
 Gus 

Back to top 


JasonR
Joined: 13 May 2004 Posts: 77 Location: Dallas/Fort Worth, Texas

Posted: Mon May 23, 2005 1:23 am Post subject: 


I don't understand what a 3d6 is; some kind of dice is my guess, but it seems to me like you are trying to take an average of a number that has an infinitely low possibility of infinity being the result. Since there is this chance, it cannot have an average and the average would be infinity. The problem is that the following roll (even though you don't often get a chance) never converges to 0 in the luckiest of cases, so it keeps adding up to infinity. I could be wrong, but I am pretty confident you cannot take such an average in any useful manner. 

Back to top 


brianhook Site Admin
Joined: 12 Dec 2003 Posts: 2521 Location: seattle, wa

Posted: Mon May 23, 2005 1:54 am Post subject: 


JasonR wrote:  I don't understand what a 3d6 is 
That means "roll 3 six sided dice and add them", but for this case just a single sixsided die is sufficient.
Quote:  it seems to me like you are trying to take an average of a number that has an infinitely low possibility of infinity being the result. 
Yes.
Quote:  Since there is this chance, it cannot have an average and the average would be infinity. 
Welcome to wonderful world of limits =)
Quote:  I could be wrong, but I am pretty confident you cannot take such an average in any useful manner. 
Well, calculus is confident otherwise.
At its essence, calculus is all about solving problems like this. However I'm not sure there is a clear analytical solution to this and I may be forced to settle for a numerical approximation, but the fact that MathCAD gave me an exact answer of 4.2 seems to point to some kind of analytical answer. 

Back to top 


JasonR
Joined: 13 May 2004 Posts: 77 Location: Dallas/Fort Worth, Texas

Posted: Mon May 23, 2005 2:18 am Post subject: 


Ah, I see now. I was wrong. I have taken up to calc3, discrete2, and have a minor in math and I can't answer that. I don't think this is a calculus problem though. Isn't calculus based on continuous functions? I think this would fall under discrete math.
Last edited by JasonR on Mon May 23, 2005 3:29 am; edited 2 times in total 

Back to top 


brianhook Site Admin
Joined: 12 Dec 2003 Posts: 2521 Location: seattle, wa

Posted: Mon May 23, 2005 2:24 am Post subject: 


JasonR wrote:  Isn't calculus based on continuous functions? I think this would fall under discrete math. 
Calculus is about limits, and by and large it focuses on continuous functions, but there is definitely a strong relationship between sums and integrals (in fact, IIRC an integral can emulate a series by effectively saying "dx=dx instead of dx approaches 0").
Where this particular problem lies is tough to say. Calculus does cover series and sums, very lightly. Numerical analysis and discrete cover this in a bit more detail, but they tend to emphasize the practical methods (sampling, etc.) instead of analytical/symbolic methods. 

Back to top 


JasonR
Joined: 13 May 2004 Posts: 77 Location: Dallas/Fort Worth, Texas

Posted: Mon May 23, 2005 2:50 am Post subject: 


Eh, I give up! I tried to solve it but failed. 

Back to top 


brianhook Site Admin
Joined: 12 Dec 2003 Posts: 2521 Location: seattle, wa

Posted: Mon May 23, 2005 10:44 am Post subject: 


Okay, got the answer from a guy I know who is an associate prof at diku.
Quote: 
It is an arithmeticgeometric series. These have the form:
a + (a+d)r + (a+2d)r^2 + ...
and have sum a/(1r) + rd/(1r)^2.
In your case, a = 15, d = 30 and r = 1/6, so we get the sum
15/(11/6) + (1/6)*30/(5/6)^2
= 18 + 36/5
Now, the arithmeticgeometric series starts from x=0, so we must
subtract the first term (15), so we get 3+36/5 = (3615)/5 = 21/5.



Back to top 


JasonR
Joined: 13 May 2004 Posts: 77 Location: Dallas/Fort Worth, Texas

Posted: Mon May 23, 2005 11:32 pm Post subject: 


So how did you come about this problem? I thought it was pretty interesting. Why would you want to know that average? 

Back to top 


brianhook Site Admin
Joined: 12 Dec 2003 Posts: 2521 Location: seattle, wa

Posted: Tue May 24, 2005 6:59 am Post subject: 


It's a roleplaying game thing. Many RPGs have the concept of "openended rolls", which means "if you roll a high value, reroll and add the new roll to the high value".
For example, if you 3d6 "open" and get a 3, 3, and 6, you'd reroll the 6 and get, say, a 5. Your total would then be 17. This adds a certain degree of "over the topness", particularly for criticals.
Some systems have bounded openended rolls "reroll at most once" and others have unbounded openended rolls where you reroll ad infinitum.
The question then is "How does your average shift when you move from a closed roll to an open ended roll?" Knowing that is important when designing mechanics. 

Back to top 


FogChicken
Joined: 02 Apr 2004 Posts: 3 Location: Boston area

Posted: Wed Jun 15, 2005 3:09 pm Post subject: 


Hi all,
In for one of my infrequent visits. It seems like we reached the point in this discussion where everyone normally turns around and looks at me. Since I wasn't here it just died out instead. Here's what I would have said if I'd been around.
I wouldn't really describe this as calculus but analysis, which is a necessary precursor to calculus. In order to properly formulate a theory of calculus you have to get your head around the idea of infinity, which turns out to be pretty tricky to work with. Analysis is all about rigorously defining infinity in the context of real numbers, sequences and the like.
A sum to infinity, for example, doesn't mean that you add up infinitely many terms. That's not possible. What it means is that you add up all the terms up to a certain number (call it N) look at how the sums behave as N gets bigger and bigger, and see whether they converge to a limit. If they do, then that's your sum to infinity. If they don't then the sum doesn't exist (this is usually the case that gets people tied up in knots when they don't approach it properly).
So for this example, we might look at cases that aren't open ended but instead allow up to N extra rolls and then stop. Define F(N) as the average value of such a roll. Then fairly obviously:
F(N+1) = 3.5 (average of 1d6) + 1/6 * F(N).
If these values converge to a limit, call it F, then if we look at the limit as N goes to infinity of the above equation we get:
F = 3.5 + 1/6 F
which gives the algebraic solution F=4.2 that Brian came up with earlier.
Note that this is only valid if the sequence F(N) converges, which tends to be trickier to establish. In this case we can establish it pretty easily from the fact that whenever F(N) is less than 4.2, F(N+1) is greater than F(N) but less than 4.2 (both of these are easy to prove from the equation above). So it's an increasing sequence bounded above by 4.2 and therefore converges, and from the above we know that if it converges the limit must be exactly 4.2. 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
