4 ms·

A (minor) point not raised in the article is that the accuracy of these methods is typically bounded unless your RNG is truly random. So for example if you try

A (minor) point not raised in the article is that the accuracy of these methods is typically bounded unless your RNG is truly random. So for example if you try to calculate pi as shown you will not be able to finesse the answer beyond a certain accuracy if you are using a typical language's pseudo-random number generator, because the true space of possible values is only partially sampled.

jacquesm 5y ago
Ah, this may have been my problem (see other comment in this thread). I will have to try this again now with a better RNG. Thank you!
mathrando 5y ago
RNG quality is probably the least of your worries. 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. You can: 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.
- gbrown 5y ago
  Wouldn’t it be even faster to solve that problem conditionally? P(x >= a)P(y >= a | x >= a), since the conditional distribution is known and normal?
  - mathrando 5y ago
    You still need to integrate over x. y|x=c is Gaussian for each c, but there are many such c's in [a,inf]. If you're curious: https://www.ams.org/journals/mcom/1978-32-141/S0025-5718-1978-0461849-9/S0025-5718-1978-0461849-9.pdf https://www.ams.org/journals/mcom/1978-32-141/S0025-5718-197...
    - gbrown 5y ago
      Ah, duh. Not enough coffee.
cycomanic 5y ago
Does that mean we can use the calculation of e.g. pi and a check what value it converges to as a check of the sampling space of a rng? I guess the sampling space is only a necessary condition for rng "quality"?
- deleted 5y ago
  [deleted]

jacquesm 5y ago

Ah, this may have been my problem (see other comment in this thread). I will have to try this again now with a better RNG. Thank you!

mathrando 5y ago

RNG quality is probably the least of your worries. 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. You can: 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.

gbrown 5y ago
Wouldn’t it be even faster to solve that problem conditionally? P(x >= a)P(y >= a | x >= a), since the conditional distribution is known and normal?
- mathrando 5y ago
  You still need to integrate over x. y|x=c is Gaussian for each c, but there are many such c's in [a,inf]. If you're curious: https://www.ams.org/journals/mcom/1978-32-141/S0025-5718-1978-0461849-9/S0025-5718-1978-0461849-9.pdf https://www.ams.org/journals/mcom/1978-32-141/S0025-5718-197...
  - gbrown 5y ago
    Ah, duh. Not enough coffee.

cycomanic 5y ago

Does that mean we can use the calculation of e.g. pi and a check what value it converges to as a check of the sampling space of a rng? I guess the sampling space is only a necessary condition for rng "quality"?

deleted 5y ago
[deleted]