Book of Hook Forum Index Book of Hook
Also, I can kill you with my brain
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Math challenge!

 
Post new topic   Reply to topic    Book of Hook Forum Index -> Game Development
View previous topic :: View next topic  
Author Message
brianhook
Site Admin


Joined: 12 Dec 2003
Posts: 2521
Location: seattle, wa

PostPosted: Fri May 20, 2005 2:06 am    Post subject: Math challenge! Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
brianhook
Site Admin


Joined: 12 Dec 2003
Posts: 2521
Location: seattle, wa

PostPosted: Sat May 21, 2005 6:06 pm    Post subject: Reply with quote

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(2x-1)/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
View user's profile Send private message Send e-mail Visit poster's website
Gus_Smedstad



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

PostPosted: Sat May 21, 2005 7:22 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
JasonR



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

PostPosted: Mon May 23, 2005 1:23 am    Post subject: Reply with quote

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
View user's profile Send private message
brianhook
Site Admin


Joined: 12 Dec 2003
Posts: 2521
Location: seattle, wa

PostPosted: Mon May 23, 2005 1:54 am    Post subject: Reply with quote

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 six-sided 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
View user's profile Send private message Send e-mail Visit poster's website
JasonR



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

PostPosted: Mon May 23, 2005 2:18 am    Post subject: Reply with quote

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
View user's profile Send private message
brianhook
Site Admin


Joined: 12 Dec 2003
Posts: 2521
Location: seattle, wa

PostPosted: Mon May 23, 2005 2:24 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
JasonR



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

PostPosted: Mon May 23, 2005 2:50 am    Post subject: Reply with quote

Eh, I give up! I tried to solve it but failed.
Back to top
View user's profile Send private message
brianhook
Site Admin


Joined: 12 Dec 2003
Posts: 2521
Location: seattle, wa

PostPosted: Mon May 23, 2005 10:44 am    Post subject: Reply with quote

Okay, got the answer from a guy I know who is an associate prof at diku.
Quote:

It is an arithmetic-geometric series. These have the form:

a + (a+d)r + (a+2d)r^2 + ...

and have sum a/(1-r) + rd/(1-r)^2.

In your case, a = -15, d = 30 and r = 1/6, so we get the sum

-15/(1-1/6) + (1/6)*30/(5/6)^2

= -18 + 36/5

Now, the arithmetic-geometric series starts from x=0, so we must
subtract the first term (-15), so we get -3+36/5 = (36-15)/5 = 21/5.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
JasonR



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

PostPosted: Mon May 23, 2005 11:32 pm    Post subject: Reply with quote

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
View user's profile Send private message
brianhook
Site Admin


Joined: 12 Dec 2003
Posts: 2521
Location: seattle, wa

PostPosted: Tue May 24, 2005 6:59 am    Post subject: Reply with quote

It's a role-playing game thing. Many RPGs have the concept of "open-ended 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 open-ended rolls "reroll at most once" and others have unbounded open-ended 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
View user's profile Send private message Send e-mail Visit poster's website
FogChicken



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

PostPosted: Wed Jun 15, 2005 3:09 pm    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Book of Hook Forum Index -> Game Development All times are GMT - 5 Hours
Page 1 of 1

 
Jump to:  
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