4 ms·

I will never understand why people think Monte Carlo is such a neat solution. There is nothing random about pi. Why didn't you just pick the center of the squa

I will never understand why people think Monte Carlo is such a neat solution. There is nothing random about pi. Why didn't you just pick the center of the square, use that to partition it into 4 pieces, and recurse for each subsquare? Or just as easily do this? http://pastebin.com/ezi7S35N http://pastebin.com/ezi7S35N (Edit: just noticed a typo -- I should be initializing the numerator/denominator inside the loop, not outside, sorry.) What's the point of adding randomness?

robzyb 12y ago
> 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.
- sherjilozair 12y ago
  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.
  - wfunction 12y ago
    Calling it "pseudo-Monte Carlo" is like calling a landline phone a "wired cell phone". It kind of misses the point.
    - retroencabulato 12y ago
      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.
      - wfunction 12y ago
        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.
        jacquesm 12y ago
        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.
        wfunction 12y ago
        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.
  - teisman 12y ago
    Using equally spaced points doesn't produce an unbiased estimator, while a monte carlo simulation does.
    - wfunction 12y ago
      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.
    - sherjilozair 12y ago
      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.
      - wfunction 12y ago
        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).
      - mturmon 12y ago
        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 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.
afafsd 12y ago
You're right, as a method for computing pi it's silly and inefficient. As a way of demonstrating the utility of Monte Carlo algorithms in general, though, it's a neat and easily visualisable example, which is why it's used so often in elementary introductions of the concept. Actual examples of how Monte Carlo algorithms can be useful involve the sampling of many-dimensional spaces via algorithms which sample points you're interested in more often than points you're not interested in -- check out the Metropolis-Hastings algorithm for an example of useful Monte Carlo in action.
- wfunction 12y ago
  See my comment here. https://news.ycombinator.com/item?id=8159270 https://news.ycombinator.com/item?id=8159270
adwn 12y ago
Monte Carlo methods are never "seriously" used to approximate pi – there are algorithms which converge much, much faster. This here, however, is not a "serious" attempt at computing pi, but a learning exercise for someone who just found out about Monte Carlo methods. Regarding the randomness of the problem to solve: A practical application for Monte Carlo methods is integration over a high-dimensional space (with dozens or more degrees of freedom). Traditional deterministic methods have a runtime which is exponential in the number of dimensions, while for Monte Carlo integration, the error of the result decreases as 1/sqrt(N) (where N is the number of samples, which is proportional to the runtime), independent of the dimensionality of the integration space.
- wfunction 12y ago
  I think you missed my point. I know this isn't how pi is calculated, that is completely irrelevant to what I've been trying to say. I also know Monte Carlo has other benefits, and that's entirely my point: the actual benefits aren't illustrated in the example. what I'm saying is that the entire point of illustrating an algorithm by example is to illustrate the power of the algorithm compared to a naive approach, regardless of whether or not there is a better way to solve the example problem. i.e., the example should motivate the algorithm. But computing pi is one of the worst possible illustrations of why anyone would use Monte Carlo, because it's inferior to the naive approach. i.e., it doesn't motivate why anyone would want to use Monte Carlo.
  - keithpeter 12y ago
    "But computing pi is one of the worst possible illustrations of why anyone would use Monte Carlo, because it's inferior to the naive approach. i.e., it doesn't motivate why anyone would want to use Monte Carlo." Any suggestions for a simulation that does illustrate the use of Monte Carlo methods while still being explainable with 16+ age range non-specialist mathematics? I'm hacking around with two step simulations like a tree diagram... http://sohcahtoa.org.uk/pages/maths_montecarlo.html http://sohcahtoa.org.uk/pages/maths_montecarlo.html My crack at saying how slowly a monte-carlo simulation 'converges' to a value of pi (not really converging, just confidence intervals tightening around the value).
MrQuincle 12y ago
Do not underestimate the value of these visualizations. They reach 1000s of kids, students, and who-knows, adults fooling around on Sundays. So, perhaps you can turn this around, and ask for a special visualization that would be better in your opinion. In that case you might be lucky and have a person like krat0sprakhar nicely visualizing your specific problem. And just my two cents: most problems I encounter are integration (full Bayesian) and the detection of extremes (MAP). There is nothing random about these problems either, maybe even less than pi (which might be "normal", nobody knows yet)! I'd be happy to see a visualization of another nice, simple problem, that is more up your alley!

robzyb 12y ago

> 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.

sherjilozair 12y ago
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.
- wfunction 12y ago
  Calling it "pseudo-Monte Carlo" is like calling a landline phone a "wired cell phone". It kind of misses the point.
  - retroencabulato 12y ago
    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.
    - wfunction 12y ago
      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.
      - jacquesm 12y ago
        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.
        wfunction 12y ago
        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.
- teisman 12y ago
  Using equally spaced points doesn't produce an unbiased estimator, while a monte carlo simulation does.
  - wfunction 12y ago
    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.
  - sherjilozair 12y ago
    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.
    - wfunction 12y ago
      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).
    - mturmon 12y ago
      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 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.

afafsd 12y ago

You're right, as a method for computing pi it's silly and inefficient. As a way of demonstrating the utility of Monte Carlo algorithms in general, though, it's a neat and easily visualisable example, which is why it's used so often in elementary introductions of the concept. Actual examples of how Monte Carlo algorithms can be useful involve the sampling of many-dimensional spaces via algorithms which sample points you're interested in more often than points you're not interested in -- check out the Metropolis-Hastings algorithm for an example of useful Monte Carlo in action.

wfunction 12y ago
See my comment here. https://news.ycombinator.com/item?id=8159270 https://news.ycombinator.com/item?id=8159270

adwn 12y ago

Monte Carlo methods are never "seriously" used to approximate pi – there are algorithms which converge much, much faster. This here, however, is not a "serious" attempt at computing pi, but a learning exercise for someone who just found out about Monte Carlo methods. Regarding the randomness of the problem to solve: A practical application for Monte Carlo methods is integration over a high-dimensional space (with dozens or more degrees of freedom). Traditional deterministic methods have a runtime which is exponential in the number of dimensions, while for Monte Carlo integration, the error of the result decreases as 1/sqrt(N) (where N is the number of samples, which is proportional to the runtime), independent of the dimensionality of the integration space.

wfunction 12y ago
I think you missed my point. I know this isn't how pi is calculated, that is completely irrelevant to what I've been trying to say. I also know Monte Carlo has other benefits, and that's entirely my point: the actual benefits aren't illustrated in the example. what I'm saying is that the entire point of illustrating an algorithm by example is to illustrate the power of the algorithm compared to a naive approach, regardless of whether or not there is a better way to solve the example problem. i.e., the example should motivate the algorithm. But computing pi is one of the worst possible illustrations of why anyone would use Monte Carlo, because it's inferior to the naive approach. i.e., it doesn't motivate why anyone would want to use Monte Carlo.
- keithpeter 12y ago
  "But computing pi is one of the worst possible illustrations of why anyone would use Monte Carlo, because it's inferior to the naive approach. i.e., it doesn't motivate why anyone would want to use Monte Carlo." Any suggestions for a simulation that does illustrate the use of Monte Carlo methods while still being explainable with 16+ age range non-specialist mathematics? I'm hacking around with two step simulations like a tree diagram... http://sohcahtoa.org.uk/pages/maths_montecarlo.html http://sohcahtoa.org.uk/pages/maths_montecarlo.html My crack at saying how slowly a monte-carlo simulation 'converges' to a value of pi (not really converging, just confidence intervals tightening around the value).

MrQuincle 12y ago

Do not underestimate the value of these visualizations. They reach 1000s of kids, students, and who-knows, adults fooling around on Sundays. So, perhaps you can turn this around, and ask for a special visualization that would be better in your opinion. In that case you might be lucky and have a person like krat0sprakhar nicely visualizing your specific problem. And just my two cents: most problems I encounter are integration (full Bayesian) and the detection of extremes (MAP). There is nothing random about these problems either, maybe even less than pi (which might be "normal", nobody knows yet)! I'd be happy to see a visualization of another nice, simple problem, that is more up your alley!