7 ms·
Monte Carlo theory, methods and examples (2013)
- noir_lord 9y agoI 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 9y agoI'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_lord 9y agoYeah 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 9y agoProfessor Owen has been a leader in Monte Carlo, sampling, and experimental design. He recently chaired the relevant conference (http://mcqmc2016.stanford.edu 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 9y agoWhy is there so much written on Monte Carlo theory and (comparatively) hardly anything on Las Vegas theory?
- jamesrom 9y agoBecause what happens in Vegas... doesn't fit stochastic calculus.
- musikele 9y agoHERO :D
- muyuu 9y agoBecause the system is rigged, folks.
- Mathnerd314 9y agoLas Vegas is a city, the only theory it has is urban planning. Whereas Monte Carlo was a code name from the Manhattan Project.
- mrow84 9y agoProbably 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.
- kummap 9y agoWe 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&CFTOKEN=49114698 http://dl.acm.org/citation.cfm?id=2935745&CFID=782777315&CFT... or just email to some of the authors to get the pdf ...
- SeanDav 9y agoI 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 9y agoIt'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.
- kummap 9y agoToo bad it's too late to use your words on the paper
- Dayshine 9y agoIf 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 9y agoTheir 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 9y agoJudging 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 9y agoI 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 9y agoSome 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 9y agoI 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
- logicallee 9y agoas 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.)
- Chris2048 9y 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
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- MustafaAdam 9y agoWhat's the target audience for the book? I'm somewhat interested in self learning this, but I'm intimated by the topic and would appreciate a beginner friendly introductory resource. Also, any exercises and solutions?
- onikolas 9y agoFun 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.
- gadders 9y agoWhoah Black Betty, STAN ULAM. Karma suicide Post
- Ntrails 9y agoI'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 9y agoAs 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 9y agoIn 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 9y agoThe theoretical validation of these methods drove much of the early development of computing in the 1930s (as a way to compute Monte Carlo estimates.)
- abowenmc 9y agoAuthor 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.
- knbknb 9y agoOnly the first 10 book chapters are linked to on this page (http://statweb.stanford.edu/~owen/mc/ http://statweb.stanford.edu/~owen/mc/), why is that? The Table of Contents lists 17 chapters.
- olsgaard 9y agoThank 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"?
- abowenmc 9y agoI'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 9y agoHas any work been done on this book since 2013?
- abowenmc 9y agoSome of the posted chapters have had typos corrected since then. There are other unposted chapters that have been developing somewhat since then.
- Chris2048 9y agoIt's interesting that MC can work best with non-random numbers :-)
- phatoni 9y agoI remember simulating the Monty Hall problem with random numbers, because it was hard to imagine.
- styrophone 9y agoI 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 9y agoFooled by Randomness by Nassim Nicholas Taleb talks about the Monte Carlo theory extensively.