This article brings it up, but only as a "look at what you can do with MC methods" and not "here's this fundamental relation that's really important."
There's lots of useful understanding about importance sampling and related techniques that seem obvious when you look at it as an integration problem.
It was a really good course, but at the time I was not in a mental space where I could get the most out of it, so I'm kind of hoping someone else can point to a solid textbook or something.
There is also a MOOC (same title, same author) on Coursera that I found interesting. It doesn't not go to the same depth as the book however. They are more complementing each other, the book for theory, the MOOC for implementation exercises.
Also just to mention something else that is very interesting related with MC : "quasi-Monte Carlo techniques" (small example in https://github.com/ChristopheRappold/MCandPython/blob/master... ). For people interested in MC, just take a look to those keywords.
Does anyone know of an accessible proof of this statement?
edit: the tricky part is recognizing that P(sum < 1) is equal to 1/n!, after that, it's the world's most recognizable taylor series
One solver in particular submitted several elegant solutions: http://math.uchicago.edu/~timblack/blog/addtoone.html
If N is the number of uniforms needed to have a sum bigger than 1, you can see that P(N>n)=P(S_n<1).
P(S_n<1) is not too bad to compute, or you can wikipedia it (Irwin-Hall distribution) to find the expression P(S_n<1)=1/n!
Combining the things, E[N]=sum(P(N>n),n=0..infinity)=sum(1/n!,n=0..infinity)=exp(1).
Heck, my buddy at MIT made an open-source Monte Carlo code called OpenMC that's now run by Argonne National Lab . Now everyone can do truly legit reactor design with Monte Carlo!
For a more formal treatment, the projects in the MIT comp prob course are genuinely enjoyable to implement:
MITx 6.008.1x Computational Probability and Inference
The curse of dimensionality means you often need a huge number of samples to guarantee a useful level of precision. Additionally, many quantities you'd like to know come up in Monte Carlo simulations themselves. That creates an intractable O(N^2) problem.
Here's an example that I encountered at work yesterday:
You want to know P(x>=a and y>=b) where (x,y) is a standard bivariate normal with correlation R.
1. Simulate a bunch of (x,y) and take the mean of the indicator function 1[x>=a, y>=b]. This will take whole seconds to compute.
2. Use an adaptive quadrature method like scipy.integrate.nquad. This will take dozens to hundreds of milliseconds.
3. Write a fixed grid Gauss-Legendre quadrature routine in c. This will take less than a microsecond.
I needed this value inside a Monte Carlo simulation. If I had to simulate the solution, the problem would be intractable.
If you're curious:
Also if you’re plugging random numbers directly into the simulator like this article does, the convergence rate will be n^(1/2) which means that going from 8 digits of precision to 10 digits will take 10,000 times longer. In order to get a better convergence rate, you could use jittering/stratification or a low-discrepancy sequence instead of a bare random number generator. Even with a perfect QMC convergence rate of 1/n, getting 10 digits of precision reliably will take 100 times longer than 8 digits of precision.
I don’t remember the chip defect problem, so I’m not sure whether I solved it. ;) But based on your description, and knowing that Euler problems are designed to be resistant to long computations, I might bet on the convergence rate being the issue. I saw your comment about using a better RNG, but if you used a 64-bit RNG, I doubt that is the problem, I think you’d get away with a low quality RNG if you waited long enough.
 the wonderful svelte js compiler: https://svelte.dev/
More details here:
You can make a spreadsheet in 3 minutes that numerically solves the problem with MC. Now imagine that the cylinder is partly transparent and you want to know how much light makes it through. A few minutes of adjustment and the spreadsheet will do it no problem. Now imagine there is another object embedded in the first with its own transparency. Again only a relatively small amount of time is needed to get the simulation working. The analytical solution is not reachable by mortals.
Could you elaborate on this a bit? I'm having a hard time seeing why and how you would combine basic probabilities with a complex system.
The naive method of doing this is just to cover the space evenly and weight each value by its probability. This is often computationally inefficient because you spend lots of time generating samples that don't actually contribute much to the result.
This is why we have methods like Metropolis--Hastings or Gibbs: these take an appropriately encoded description of the desired distribution and, through clever means, generate samples from it relatively cheaply, in proportion to how likely they are.
This part of the problem is likely what the GP alluded to.
A nice writeup that helped me understand MCTS: https://tianjun.me/static/essay_resources/Lets_Play_Hanabi/p...
> Of course, for n ≥ 365 you don’t need any calculations, it’s a straightforward consequence of the pigeonhole principle.