Hacker News Reader

Comment by robzyb | Hacker News Reader

> There is nothing random about pi.

That is exactly what makes Monte Carlo neat! There is nothing random about pi, yet using randomness we can arrive at pi.

View on HN

We don't necessarily have to use randomness. We can take equally-spaced points in the quarter as well, rather than sampling. This is called pseudo-Monte Carlo.

Using equally spaced points doesn't produce an unbiased estimator, while a monte carlo simulation does.

Could you substantiate this with any references? I thought hard about this, and I find no reason to believe that equally-spaced points would give a biased estimator.

The comment has a point. It is possible that the particular deterministic rule that chooses points could interact with the shape (quarter circle).

In this case, the error would not necessarily go to zero as the number of points increases without bound.

In the particular case of a grid based deterministic probe, and a quarter-circle target, it seems clear that this would not happen.

But consider another example where the underlying target was "all points with rational coordinates". All the probes in a grid sampling scheme would hit the target, but the target has measure zero.

Incidentally, the idea of using a deterministic, low variability sequence for sampling is called quasi Monte Carlo (http://en.wikipedia.org/wiki/Quasi-Monte_Carlo_method). It can give almost order 1/n convergence, much better than the 1/sqrt(n) convergence possible with ordinary Monte Carlo.

> But consider another example where the underlying target was "all points with rational coordinates". All the probes in a grid sampling scheme would hit the target, but the target has measure zero.

And how exactly would the Monte Carlo version differ here? Every single random number generated is going to be rational isn't it?

Every single random number being generated will be rational, but that is much finer granularity than any fixed grid that you might be using.

Unless your fixed grid includes every single rational point that could be expressed by the (P)RNG.

It's just a smart-aleck comment pointing out that there is a "bias" because we're using a finite number of points and we get the same exact answer every time -- and since that answer isn't exactly equal to pi, the procedure is "biased".

Which no one cares about because (1) this isn't a probabilistic process in the first place, so "bias" itself is meaningless, and (2) there is now an exact bound on the error, unlike the previous case (I guess you can think of this as the "variance" if you want).

Imagine if you were sampling the amount of black area in a checker board.

Who cares? The error is going to be there either way. And Monte Carlo can't guarantee any hard bound on that error, whereas using equally spaced points gives you a pretty darn good hard bound.

Calling it "pseudo-Monte Carlo" is like calling a landline phone a "wired cell phone". It kind of misses the point.

No, you missed the point. In problems with a very large sample space, quasi-MC methods are invaluable. They converge faster and can be shown to approximately have the benefits of traditional MC methods.

I think we're talking past each other here. Talking about "sample space" inherently assumes you're dealing with a random process. My point is pi isn't random, so coming up with a random process just so you can force MC on it and then suddenly deciding you want to make it deterministic just so you can call it "pseudo-MC" is kinda... weird, to say the least.

I really wish people would stop trying to find ways of calling their algorithms "Monte Carlo" just to make their work sound fancy. All it really achieves is it makes them avoid thinking about how to solve the problem. Monte Carlo isn't a universal hammer. First you're supposed to show randomness actually helps you gain something, then you're supposed to start using it.

I think there is some value to this method, but it may not be readily apparent in the present context. If you have a problem that you don't yet have a firm theoretical handle on you can figure out a baseline value for the answer using this technique, and then work backwards to give you the formula that allows you to arrive at the real answer.

I use that trick a lot, for instance with Euler problem 307 I could not find the answer easily in an analytical way, did the simulation, found an approximate answer (to within 6 decimal places or so), used that to figure out what I was doing wrong and then computed the real answer.

Some may see that as cheating, but it works wonders and not just on that particular problem.

I've done that too, and I think there's nothing wrong with that. All I'm saying is people should stop calling it Monte Carlo once they've found the correct solution and realized it has nothing to do with randomness.

Reply on news.ycombinator.com