Monte Carlo theory, methods and examples (2013)

http://statweb.stanford.edu/~owen/mc/

by pmalynin • 9 years ago

277 44 9 years ago

statweb.stanford.edu

noir_lord2• 9 years ago

I remember using Monte Carlo to calculate Pi on an XT back in the late 80's (the explanation was in a kids math book), iirc (it's been a while) it took all night to get to 4 sig fig, it was an interesting demonstration.

keithpeter• 9 years ago

I've done that one with a basic maths class using rice grains dropped on a circle drawn on graph paper and then in a spreadsheet with rand() function generating the coords. Seems to help understanding.

Someone here suggested extending to finding the volume of the Steinmetz solid which I must get round to.

noir_lord2• 9 years ago

Yeah it was in a book with a title like "Fun with Maths" or something unusually for that type of book it's title was true.

mturmon• 9 years ago

Professor Owen has been a leader in Monte Carlo, sampling, and experimental design. He recently chaired the relevant conference (http://mcqmc2016.stanford.edu). People who do experimental design should have some understanding of what QMC, for example, can offer -- standard error reduction by 1/n as opposed to just 1/sqrt(n).

He was also one of the few statisticians who was seriously interested in neural nets long before they became fashionable, serving as a reviewer of learning theory work for NIPS.

wfunction• 9 years ago

Why is there so much written on Monte Carlo theory and (comparatively) hardly anything on Las Vegas theory?

jamesrom• 9 years ago

Because what happens in Vegas... doesn't fit stochastic calculus.

musikele• 9 years ago

HERO :D

muyuu• 9 years ago

Because the system is rigged, folks.

Mathnerd3142• 9 years ago

Las Vegas is a city, the only theory it has is urban planning. Whereas Monte Carlo was a code name from the Manhattan Project.

mrow84• 9 years ago

Probably because there are lots of situations where getting an answer that is probabilistically correct in bounded time is useful, because the world is such a noisy place anyway.

Conversely, there are not so many situations where getting the correct answer within some probabilistic time is particularly useful, because humans live short lives, and need to get things done.

kummap2• 9 years ago

We made an algorithm for Monte Carlo related random number generation. It makes slightly worse random numbers fast, but in a way which is good in some situations. I am still very excited about it!

Please see our paper: An Efficient Method for Generating Discrete Random Variables with General Distributions for example from http://dl.acm.org/citation.cfm?id=2935745&CFID=782777315&CFT...

or just email to some of the authors to get the pdf ...

SeanDav• 9 years ago

I am a layman in this field and not read the paper (behind a paywall), but not sure I see how using a method that requires random numbers to generate random numbers makes sense?

Maken• 9 years ago

It's not a method to generate random numbers, but to re-distribute random numbers according to an arbitrary distribution. In general RNG generate purely uniform distributions.

Dayshine• 9 years ago

If you roll one die you get 1-6 equally.

If you roll two dice you get 7 most often, 6 and 8 slightly less, 5 and 9 even less, etc.

Say you only have 1 die and want to generate the random number distribution that 2 dice give. Easy, just roll twice, and add them.

But what if you only have the output from 2 dice, and want to pretend to roll 1 die. You need a more general way of converting one random distribution to another.

nerdponx• 9 years ago

Their work answers the question "how do I take what's coming out of /dev/random and turn it into a disctete probability distribution?"

A "random" process is one in which every outcome is independent and unrelated to every other outcome. Drawing "random numbers" doesn't always mean drawing them uniformly at random, where every number in some range, like 0 to 1, is equally likely. You can draw random numbers according to a probability distribution, which is a mathematical expression describing the probability of drawing one number or another.

One very popular distribution is called the "normal distribution" (named for the "normal equations" of physics) or the "Gaussian distribution" (named for Karl Gauss). Normally-distributed random numbers tend to follow a "bell curve" pattern, with values closer to the peak of the bell curve being more probable than numbers further away.

That's a continuous distribution. You can also have a discrete distribution. Some examples of physical processes that can be moseled with discrete probability distributions:

- Coin toss: do I get a Heads?

- A sequence of coin tosses: how many Heads do I get?

- A die roll: do I get a 5?

- A sequence of die rolls: do I get at least one 5? Is the sum of the die rolls at most 30?

- A poker hand: will I get a flush on my next draw?

- Traffic accidents at an intersection: will there be more than 2 accidents in the next 5 days?

These are all "stochastic" questions, meaning that there is uncertainty, in their answers. So we use probability, and therefore randomness, usually non-uniform, to model these scenarios.

Sometimes you need to generate new random numbers from these distributions as part of your analysis, or for generating predictions. In those cases, you need to take a continuous stream of uniform random numbers, like /dev/random, and turn them into a sequence of numbers that follows one of these distributions.

wodenokoto• 9 years ago

Judging from the copyright notices, this hasn't been updated since 2013.

Did the author finish the book and leave this draft online, or was it never finished?

Asdfbla• 9 years ago

I always wonder where the upvotes for those posts that simply plant a link to highly specialized lectures/books that likely take months to work through (given a sufficient mathematical background) come from. Especially since the material at hand isn't relevant unless you work in certain specialized subfields.

Don't get me wrong, the resources posted here are often good and learning is great, but I doubt anyone who sees them here actually follows through and starts studying.

elcapitan• 9 years ago

Some people just collect resources for later use. I keep Evernote notebooks for certain topics. Collections of such posts give me a quick overview in case I need it later, and the combination of the reputation/upvote system and the discussions (which I usually link in my notes too) allows for some kind of ranking of the resource I collected. I interpret it as a vote of confidence.

ajakate• 9 years ago

I often skim hn from my phone browser and save posts that look interesting to read later. Unfortunately, you can't mark a post as favorite from the main page, so for me, upvoting them is the fastest way to make sure I can access it later

logicallee2• 9 years ago

as a hacker news reader it's your responsibility to become an expert in the basics of things like computer vision, machine learning, wavelet algorithms (even if it becomes irrelevant) and so forth.

at the end of the day, someone has to build something using all this, and that someone is us.

I mean what else are you going to do while waiting for another javascript framework to appear? surely we can't all write new front-end frameworks. It just doesn't make sense.

(note: this comment might be at least partly sarcastic, but I'm not sure which part and how much.)

Chris20482• 9 years ago

surely we can't all write new front-end frameworks

If you're a JS dev, it's your job to do this every 3 months

_e2• 9 years ago

I am glad you added a disclaimer stating your post is meant to be sarcastic because my automated deep learning HN voting bot has not learned sarcasm, opencv or angular6 yet.

I don't know how or why but it has mastered memory management in spark.

Mathnerd3142• 9 years ago

A lot of the material overlaps significantly with others I've read, so AFAICT "working through" the book, at least for me, amounts to a few hours reading some background definitions plus the last chapter. Maybe it does seem hard to get to that position, but really it's just building up skills incrementally. Google all the terms you don't understand, read the explanatory posts until you get to something you don't understand, and repeat recursively until it's clear or you get bored... so far depth-first seems to work better than breadth-first, there aren't that many foundational concepts.

zintinio5• 9 years ago

I certainly have in the past when something really grabbed my attention. My library has expanded in recent years partly because of the topics shared on Hackernews and mentioned in discussions. I would hazard a guess that most people don't follow up and just upvote a cool sounding title. It really does take months/years to work through some of this material, but there are some people who do it. Also important to keep in mind is that readers specialize (I'm big into math/stats/ml, but some of the guys I work with are deep into logic programming and theorem provers) so no single reader is knowledgeable in everything posted here.

atemerev• 9 years ago

The number of upvotes reflects a perceived outlook of HN readers on technology's perspectives.

Probabilistic programming, Monte Carlo methods, and other complex topics are back in vogue these days. Because programmers who only can do simpler coding tasks will be soon replaced by robots, that are programmed probabilistically. And if you want to have one of those really rare jobs of maintaining said robots, you have to be prepared.

Fear and learn.

onikolas• 9 years ago

Fun trivia: Stan Ulam was on sick-leave and was playing solitaire. He came up with the Monte Carlo method while trying to calculate the probability of a successful solitaire game. The method was named after his uncle's favorite place to gamble.

When he got back from sick-leave, he immediately began applying it to his work: calculations leading to the fusion bomb.

I find that little background stories like this help students to get engaged with subject.

Ntrails• 9 years ago

I've been thinking a bit about hands of solitaire recently as I play it on my phone on the commute to work. It's cool to know that it's an interesting problem to other people as well.

At the same time, you know, I didn't even think to use Monte Carlo let alone design the damned thing...

zeristor• 9 years ago

As I understand it he got bored of the game itself, and was thinking about it at a higher level.

I've been playing it heavily recently though, and it seems to be so well weighted. Completing games about 10% of the time.

Trying to work out strategies to finish more games.

Florin_Andrei• 9 years ago

In the computer age, I am used to methods like this using huge numbers of samples to calculate the result.

How was this done before computers?

infinite8s• 9 years ago

The theoretical validation of these methods drove much of the early development of computing in the 1930s (as a way to compute Monte Carlo estimates.)

abowenmc3• 9 years ago

Author here: I was pleased to see this while attending MCM 2017 (Monte Carlo methods). I'm open to reports about mistakes in the notes, or even thoughts on which further topics (from within MCMC, QMC, SMC, ETC) are most worthy of coverage in future chapters.

olsgaard• 9 years ago

Thank you for releasing this book. I've just started working with simulations to solve some toy problems I've been pondering, and couldn't solve analytical, so the timing of this post is impeccable!

I've read the first chapter and it is very well written and easy to follow, and the exercises look really good.

I have 2 questions:

1) Are you open reports on minor spelling/grammar mistakes? (There's a missing full-stop on page 6, and on page 4 you write "in the road" instead of "on the road". Really minor things.)

2) Do you consider the current chapters "done"?

abowenmc3• 9 years ago

I'm happy to get helpful suggestions. With enough eyeballs, every typo is shallow. I'm easy to find online.

The current chapters are done enough to post. They could change somewhat later but only to another 'done' state.

soberhoff• 9 years ago

Has any work been done on this book since 2013?

abowenmc3• 9 years ago

Some of the posted chapters have had typos corrected since then. There are other unposted chapters that have been developing somewhat since then.

knbknb• 9 years ago

Only the first 10 book chapters are linked to on this page (http://statweb.stanford.edu/~owen/mc/), why is that? The Table of Contents lists 17 chapters.

Chris20482• 9 years ago

It's interesting that MC can work best with non-random numbers :-)

phatoni• 9 years ago

I remember simulating the Monty Hall problem with random numbers, because it was hard to imagine.

styrophone• 9 years ago

I did the same thing to help me get my head around it. For anyone else finding it difficult to imagine the probabilities in Monty Hall intuitively, consider replacing the 3 doors with 100 doors. After you choose the first door, the host opens 98 of the remaining 99 doors. That generalization, at least for me, helps to show that the problem can be reduced to the choice of 1 door vs all unchosen doors.

yebsido1• 9 years ago

Fooled by Randomness by Nassim Nicholas Taleb talks about the Monte Carlo theory extensively.

Monte Carlo theory, methods and examples (2013)

Related Stories