grabben
Member
Posts: 126
Joined: Aug 2002
|
Thu Dec 19, 02 10:13 AM
|
|
Sorry to barge in on the discussion, but Quasi Monte Carlo is one of my interestes, so I just can't help myself... 
Rutger. Quasi random (QR) sequences are not really random. Neither are pseudo random (PR) numbers, which are normally used as random numbers in the Monte Carlo method. However, PR-sequences are constructed to be serially uncorrelated. This is not the case with QR-sequences, which just try to be as uniformly distributed as possible. This is especially easy to observe in the Halton sequence. In a base-2 sequence, the first number is 0.5, i.e. smack in the middle. The next two numbers are 0.25 and 0.75. These are the best numbers you can find if you want to have a uniform distributed variable (and only want 3 numbers in one dimension). Also, the two last numbers are directly a function of the first random number, as they are choosen so that they are at a maximum distance from all the previous numbers (as well as the "border values" 0 and 1).
In the base-3 sequence, the fist two numbers are 1/3 and 2/3. The following numbers are 1/9, 4/9, 7/9, 2/9, 5/9, and 8/9. These numbers are the best "random" numbers you can find if you only want to use 8 numbers in one dimension.
If we were to use a base-4 sequence now, the numbers would be 0.25, 0.5 and 0.75. However, these are the same numbers as the first 3 numbers in the base-2 sequence. Not a good idea! This is the reason for using the n:th prime as the base for the n:th dimension, and the 3rd dimension is therefor a base-5 sequence.
Now, note that the first n-1 numbers in any base-n sequence is simply i/n for i = 1,2,...,n-1. As the 49th and 50th primes are 227 and 229 respectively (both quite high bases, compared with the 100 random numbers you wanted to find, but also a quite small difference between the two...), its easy to see why <i>"at higher dimensions the columns seem to converge to ''the same'' random numbers"</i>. This is simply the way the Halton sequence works and is the main reason why this sequence is not a very good sequence to use for high dimensional problems. Also, if you use the Halton sequence, try to use b^x-1 numbers from the sequence (b = base, x = any integer), as this will make the drawings "complete" (using a couple of drawings more or less than b^x-1 will only make the distribution less uniform, however, the distribution is simply an equally spaced abscissa...).
-------------------------
There are three kinds of people: Those who can count, and those who can't.
Edited: Thu Dec 19, 02 at 12:55 PM by grabben
|
|
