3
$\begingroup$

For Monte Carlo simulations, or any other numerical methods that rely heavily on the quality of the pseudo-random numbers generated (i.e even/desired distribution on a certain domain) for that matter, why aren't evenly-spaced and perfectly/accurately distributed numbers (not pseudo-random) used as opposed to pseudo-random numbers?

The reason I ask this is because I would imagine the main purpose of sampling tons of pseudo-random data as opposed to non-random data would be to speed up the time taken by the program that is sampling that data, much like how throwing a bunch of paintballs at a canvas/wall would, more easily and quickly, cover up that canvas/wall than carefully painting it with a paintbrush would. However, many pseudo-random number generator algorithms that I have seen look more complicated and time-consuming than just using non-pseudo-random, perfectly distributed data.

Clearly I have a misunderstanding of this topic. Could anybody help clear this issue up?

Improve this question
$\endgroup$
5
  • $\begingroup$ en.wikipedia.org/wiki/Quasi-Monte_Carlo_method $\endgroup$ – k20 Jun 27 '14 at 20:11
  • $\begingroup$ By "evenly-spaced and perfectly/accurately distributed numbers ", a certain period has been assumed implicitly. $\endgroup$ – lorniper Jun 27 '14 at 20:54
  • $\begingroup$ Yes, a period of 1. For example, in the ever-so-famous example of approximating pi with a Monte Carlo simulation, why is it more practical to use a large set of pseudo-random points, rather than making a grid of evenly distributed points (like a matrix of a bunch of these perfectly distributed points in the first quadrant) and using that? Here's what I mean. $\endgroup$ – Arturo don Juan Jun 27 '14 at 21:34
  • $\begingroup$ The example of a circle is misleading, since the dimension (2) is fixed and very small. The number of uniform points you need for a good covering grows exponentially with the dimension, while this is not the case for random points. Monte Carlo only becomes competitive if the dimension is large (say, 100 and above). $\endgroup$ – Christian Clason Jun 27 '14 at 21:47
  • $\begingroup$ To elaborate: Take the same number of points as in your sketch, and repeat the experiment for a sphere. Now do the same with a four-dimensional hypersphere. Watch the result for uniform sampling get worse much faster than for random sampling. $\endgroup$ – Christian Clason Jun 27 '14 at 22:08
3
$\begingroup$

The main purpose of sampling tons of pseudo-random data as opposed to non-random data is related to Runge's phenomenon for polynomial interpolation: Uniform spacing of interpolation points is often a bad idea. But choosing better interpolation points require knowledge of the function you want to interpolate (or integrate etc.). If you don't have that knowledge, or if computing the points is infeasible due to the high dimensionality of the function, your best bet (literally) is to draw points at random. You might not hit the "good" points often, but at least you're not systematically missing all of them.

(In your example: If you don't know where the walls are, throwing brushes at random means you will likely(!) hit them earlier than if you were starting in one corner and methodically working your way around. Remember, you don't have to cover all the wall, just enough of them to see the shape.)

Of course, if your points are truly random, it can happen with positive (albeit small) probability that there's a large part of space where none of the points land (or a wall you never hit, because all of your brushes by chance go in the other direction). This is the point of quasi-Monte Carlo methods: The points are still random (meaning there's no possibly bad structure), but there's some guarantee of uniform coverage on a large scale.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are there quasi-Monte Carlo methods that allow various types of net-distributions? For example, rather than just a straight-forward uniform distribution across some domain, could you have a logarithmic distribution as you approach the edges, or maybe a gaussian distribution over the whole domain? $\endgroup$ – Arturo don Juan Jun 27 '14 at 21:49
  • $\begingroup$ Yes, of course, if you have a priori information where something interesting happens, you can tailor your probability density function to draw points there with a higher probability. That is something people do. $\endgroup$ – Christian Clason Jun 27 '14 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.