tags:

views:

605

answers:

5
+11  A: 

It should say f(xi)

f() is the function we are trying to integrate via the numerical monte carlo method, which estimates an integral (and its error) by evaluating randomly choosen points from the integration region.

Ref.

Mitch Wheat
I'd rather change the summation index to r, and the limits of integration to a and b. That way there is no confusion about the x_i's.
Zach Scrivena
That was impressively fast.
Bill the Lizard
x_i is fairly standard notation.
Mitch Wheat
It's bad notation either way, because x1 and x2 are the limits of your integral. You want the xi or xr, whichever you prefer, to be randomly distributed in [x1,x2].
A. Rex
I disagree that it's bad notation. Like many things in Mathematics there are accepted forms that are used. To me x_i seems very natural
Mitch Wheat
Not sure why this answer was downvoted
Mitch Wheat
Re the notation: xi by itself is fine notation, and obviously accepted throughout math. The summation is over i from 1 to N, which means it also includes i=1 and i=2. That means that part of your sum is f(x1) and f(x2), which are the value of your function at the endpoints. You may not want this.
A. Rex
Should be x_r_i since x_1 and x_2 are the endpoints of integration.
Jason
Re the downvote: I was wavering back and forth about whether or not I should -1. The reason I did not want to is you're clearly trying to be helpful and the -1 is "not right". However, your original answer (that it should be f(xi)) did not answer the question, yet got 2 votes somehow.
A. Rex
Continuing: then, within the five minutes, you edited to include an answer to the actual question (but no one can tell that). I thought this was symptomatic of the "fastest gun in the west problem", and I decided to balance that with a -1. As I said, I've taken it away, but I hope you understand.
A. Rex
@A. Rex: I'm not sure what you mean? I did edit a few times, but I'm a lousy typist. sorry for any consusion
Mitch Wheat
@Mitch Wheat: The use of x_i is wrong here since the endpoints are labeled as x_1 and x_2. Thus, a different notation for the randomly chosen points is needed.
Jason
@Mitch Wheat: In short, here's the sequence of events: 1. You answer saying it should be x_i, which doesn't remotely answer the question. 2. I actually answer the question. 3. You *edit* your answer to actually answer the question. 4. You get upvoted a *lot*.
A. Rex
Very informative discussion. Thank you all.
kylex
@A Rex: well you got the accepted answer!
Mitch Wheat
@Mitch Wheat: It's true. By the way, please don't get me wrong: I think you're a great SO user. No hard feelings. =)
A. Rex
e.James
+7  A: 

Your goal is to compute the integral of f from x1 to x2. For example, you may wish to compute the integral of sin(x) from 0 to pi.

Using Monte Carlo integration, you can approximate this by sampling random points in the interval [x1,x2] and evaluating f at those points. Perhaps you'd like to call this MonteCarloIntegrate( f, x1, x2 ).

So no, MonteCarloIntegrate does not "feed back" into itself. It calls a function f, the function you are trying to numerically integrate, e.g. sin.

A. Rex
Thank, this is what I was looking for.
kylex
@Mitch Wheat: and +1 for you. =)
A. Rex
+1  A: 

Replace f(x_r) by f(x_r_i) (read: f evaluated at x sub r sub i). The r_i are chosen uniformly at random from the interval [x_1, x_2].

The point is this: the area under f on [x_1, x_2] is equal to (x_2 - x_1) times the average of f on the interval [x_1, x_2]. That is

A = (x_2 - x_1) * [(1 / (x_2 - x_1)) * int_{x_1}^{x_2} f(x)\, dx]

The portion in square brackets is the average of f on [x_1, x_2] which we will denote avg(f). How can we estimate the average of f? By sampling it at N random points and taking the average value of f evaluated at those random points. To wit:

avg(f) ~ (1 / N) * sum_{i=1}^{N} f(x_r_i)

where x_r_1, x_r_2, ..., x_r_N are points chosen uniformly at random from [x_1, x_2].

Then

A = (x_2 - x_1) * avg(f) ~ (x_2 - x_1) * (1 / N) * sum_{i=1}^{N} f(x_r_i).

Here is another way to think about this equation: the area under f on the interval [x_1, x_2] is the same as the area of a rectangle with length (x_2 - x_1) and height equal to the average height of f. The average height of f is approximately

(1 / N) * sum_{i=1}^{N} f(x_r_i)

which is value that we produced previously.

Jason
A: 

Whether it's xi or xr is irrelevant - it's the random number that we're feeding into function f().

I'm more likely to write the function (aside from formatting) as follows:

(x2-x1) * sum(f(xi))/N

That way, we can see that we're taking the average of N samples of f(x) to get an average height of the function, then multiplying by the width (x2-x1).

Because, after all, integration is just calculating area under the curve. (Nice pictures at http://hyperphysics.phy-astr.gsu.edu/Hbase/integ.html#c4.

Boofus McGoofus
A: 

x_r is a random value from the integral's range.

Substituting Random(x_1, x_2) for x_r would give an equivalent equation.

Strilanc