The Beginning of the Monte Carlo Method (1987) | Hacker News Reader

The Beginning of the Monte Carlo Method (1987)

fermatslibrary.com

124 pointsmgdo31 comments

The jewel of monte carlo methods is Markov Chain Monte Carlo (MCMC) for sampling from high-dimensional probability distributions. The math is more involved, but the problem it solves is really hard and really important.

While the math is complex, the algorithms are not necessarily. In its simplest form, MCMC sampling can be implemented in 10 lines of code (Metropolis-Hastings algorithm) -- an exercise that I recommend to everyone who's interested in the topic.

Yeah I've noticed that pattern when I implement numerical algorithms by hand. A lot of the time they're pretty simple. But you need the analysis to be confident that it will work. A point in favor of formal CS / applied math :)

This is a good application: https://en.wikipedia.org/wiki/Metropolis_light_transport

If anyone is looking for the "10 line" version of Metropolis, there's a tiny toy example in, for example, these SIGGRAPH course notes from 2001: http://cseweb.ucsd.edu/~viscomp/classes/cse274/wi18/readings...

I’ve tried several times, but th page is just unreadable for me! I like to click the page and highlight words as I read. However, the interactive side bar moves the page and kills your (my) ability to read. So despite being signed up for the last few months, I haven’t ever made it past the first couple of pages :(

Can I not just have the PDF to read? The problems ultimately stem from the desire to prevent people from consuming the content in their own way.

It's usually easier to just look for the paper somewhere else once you've decided you want to read it your own way. In this case, you can find it here [0]. As they often show kind-of-classic papers, many of them are publicly available through a Google search.

[0] http://library.lanl.gov/cgi-bin/getfile?00326866.pdf

Thanks for this solution! I had just assumed it would be too difficult to find elsewhere :/

I have the same problem.

Try disabling JavaScript in your browser, it works perfectly fine without JavaScript.

NoScript!

Thanks for this solution! I’ll disable it just for the site

At its heart, Monte Carlo is just trying something a bunch of times and seeing what happens, right1?

My wife and I used Monte Carlo to buy our second house. We were trying to sell a house, buy a new one, juggle a couple of other transactions, predict interest rates, all while trying to understand our new budget (we were newly together and hadn't lived together yet at that time).

So, there were a bunch of different variables that led to a final scenario of how big our final monthly payment would be. We were both conservative in our choices, too.

The trick with Monte Carlo is that if we had been conservative on our predictions on every single variable, I don't think we ever would have bought our house.

But by doing a Monte Carlo simulation - assuming each variable was roughly independent of the others, and picking a sane-seeming variance for each prediction - we were able to simulate 10,000 scenarios, and then pick the numbers that led to us meeting our budget in 95% of cases. They key number there was the "asking price" of the house we were looking for.

That asking price - that was safe in 95% of scenarios - was much higher than it would have been had we been conservative with every single variable.

And it worked great. The conservatism of the 95% estimate gave us some wiggle room, a couple of the other variables broke our way, and our combined monthly budget still allowed us to save more money than when we were living separately.

I'd love to have a web-app for that

Me too. Or a layman's level worked write-up.

Monte Carlo has been called "integration by darts." This is a play on words of the better-known "integration by parts" method of undergraduate calculus.

Indeed. A classic (and simple) Monte Carlo procedure lets you estimate pi by essentially throwing darts.

1) Draw a unit square.

2) Inscribe a circle inside the square.

3) Throw a whole bunch of darts at the square, distributing them as randomly as possible.

4) Count the number of dart holes inside the circle. Divide by the total number of dart holes. Now you have an estimate of the ratio of the areas of the circle and the square. Call this number C. Since you know the area of the square is 1, the area of the circle must be C. C is also equal to pi * r^2, where r is the radius of the inscribed circle (which is 0.5). Thus, C = pi * (0.5)^2 = pi/4. Pi is therefore approximately 4C.

How do you figure out how many holes are inside the circle if you don't already know pi, though? I mean, a human could do it, but I don't follow how this extrapolates to a mathematical process.

Check the distance from the center to the dart?

Ok, that makes sense.

At its heart, yes. But that is also one of the basic tenets of probability theory in general, since the very beginnings. Called the law of large numbers. Monte Carlo usually refers to situations where "trying something a bunch of times" is not a straight forward procedure, because some "somethings" are more interesting than others and there is also a question of how large the "bunch" of times should be to see the true picture.

I think you create a markov chain and from there see if the chain end up in a steady state somewhere.

Bayesian use MCMC to indirectly get the joint distribution without actually doing integrating by sampling the distribution and getting the average from the chain. You start anywhere reasonable or guess where to start from the chain so you usually burn the first 10-15% of the chain and get the average of the chain.

You can have multiple chains in the simulation each chain represent a parameter estimate.

edit:

The reason why Bayesian use MCMC is because integration is hard and each model have their own different integration problem. If you choose to model salmon migration you may have your own take on the model and in the end you have this nasty integration for that take of your model. If you change your model you have a new integration problem... You can try to integrate it or you can just MCMC it and by pass integration. Instead of integrating to get the PDF you can just sample from the joint distribution and estimate it (the parameters of the distributions) from the sample.

This is what I've always believed. Happy to be corrected or refuted!

You're looking at something which has unknowns to its shape. You do not have the luxury of an exhaustive test of all variances in the input, or model. You need an optimisation which explores the space, and allows you to intuit refinements to the model.

In some cases, you have the experimental data. So you are looking for a decision-logic over which part(s) to use, and how to interpret them.

You test with a random selection of inputs, models, conditions and see how they cluster. The questions about what to do, would be "how many" and "how random-y"

I guess pared down to its absolute core, this is what Monte Carlo is - you just generate many a large ensemble of possible states.

But this simplified explanation misses out on one key aspect of Monte Carlo: sometimes different kinds of Monte Carlo moves can be designed that can allow it to more efficiently sample the phase space than other methods such as gradient descent.

Unfortunately, doing so is can be very involved, and is not always very general, so it isn't as easy to do as using other methods for exploring phase space.

Your answer feels like its saying "its only partly random, you use the outcome of your experiments to walk the space of possible solutions more carefully, in the light of experience" which would make it more like GLMM or something markov-y

> The war ended before we finished our problems

Damn, how do you get a job like that? If something takes more than a couple hours I get criticized.

unsolvable problems require unmeasurable time to be resolved

In addition to the historical account of Mote Carlo Meothod, an accurate prediction of computing was given in 1987 at the end of the article...

> The miracle of the chip, like most miracles, is almost unbelievable. Yet the fantastic performances achieved to date havenot quieted all users. At the same time we are reaching upper limits on the computing power of a single processor.

> One bright facet of the miracle is the lack of macroscopic moving parts, which makes the chip a very reliable bit of hardware. Such reliability suggests parallel processing. The thought here is not a simple extension to two, or even four or eight, processing systems.

> Such extensions are adiabatic transitions that, to be sure, should be part of the immediate, short-term game plan. Rather, the thought is massively parallel operations with thousands of interacting processors-even millions!

The neutron diffusion simulation seems simplistic and probably reflects the limitations of the time. Can one imagine what John Von Neumann would do given access a modern supercomputer?

> Can one imagine what John Von Neumann would do given access a modern supercomputer?

come up with new architecture? It might be interesting feeling when one looks at his own idea implemented decades later on the scale multifold beyond the scale it was originally conceived at - ie. from "architecture" to "bottleneck" :) On the other side it is a testament to his vision that we still can't transcend it.

Just imagine how many personalized ads von Neumann could get us to click on.

Few, for many, because digital ads aren't terribly persuasive.

Chances are he might have gotten distracted.

Reply on news.ycombinator.com