Definitions...how to construct them...uses...all info gratefully received.P

What are low discrepancy numbers or what is quasi monte carlo ?BrieflyLow discrepancy sequence are constructed in order to avoid clustering. As such the numbers are added in such a way that successive numbers are as away as possible from previous number.It is therefore obvious that low discrepancy sequence are totally deterministic. A good example of basic low discrepancy sequences can be found in the Wilmott Quant Finance book.The construction of low discrepancy sequence aims at higher accuracy and shorter computational time. Unfortunately these low discrepancy sequences do suffer from high dimensionality. And currently, we almost only have high dimensional problems: asian baskets, structured products etc

There are several kinds of these sequences (LDS), namely : Halton, Faure, Niederreiter, Sobol...(see the corresponding papers)Sobol sequences have proven to outperform in high dimension problems, provided that one is able to workout an effective algorithm for computing primitive AND irreducible polynomials of a specific Galois field, in order to generate the good initializing sequence (direction numbers...). Unfortunately, achieving a good implementation of Sobol sequences remains extremely tricky, so that many practitioners prefer either to buy some available 'black box' dlls, or to use some hand-crafting to get round (locally) the various difficulties they may encounter.In all cases, before using a generated LDS one has always to check on multiprojection sctterplots if the required features are there (e.g. the points should be evenly spread, there should be no clustering - or at least not 'too much', no stressed peridicity...); moreover, it may also prove useful to run some 'test functions' to quantify the goodness of the sequence at hand.

As much as plugs are deprecated, I could recommend a book that goes into detail on the subject of low discrepancy numbers, specifically Sobol' numbers. According to Sobol' himself, the presentation of his numbers in that book isn't too bad...Regards,pj

Thanks, pj, but can you summarize that excellent presentation for the purposes of our FAQs Forum?!P

I am afraid I have to resort to a quote here : "Things should be made as simple as possible, but not any simpler."The key concept behind all low discrepancy number generation is to find some kind of way of mapping a unique generating identifier (I call it the generating integer) to one unique number in each dimension that is asymptotically uniformly distributed in each dimension as we iterate through many different generating integers. Uniformity across different dimensions is achieved by virtue of some kind of independence or orthogonality or incommensurability of the generating algorithms in each dimension. Halton numbers use a different base representation in each dimension and asymptotic independence is attained by the use of different prime numbers in different dimensions. Faure numbers are based on certain features of the so-called infinite Pascal matrix. Sobol' numbers are based on primitive polynomials modulo two which one can think of as some form of prime number in the domain of ordered bit sequences with an additional orthogonality feature (they are not just irreducible which is the equivalent to numbers being prime, but they are also primitive which ensures some extra form of independence). The number theory behind these more advanced low discrepancy sequences is, alas, rather involved, but fortunately, the resulting construction algorithms can be amazingly simple and fast. Niederreiter-Xing numbers use not only polynomial but also rational functions with asymptotic indepence features and since this extension enables them, at least theoretically, to be asymptotically superior.The key with Sobol' numbers is to pick a decent initialisation of the so-called direction numbers. The direction numbers are governed by a recursion rule given by modulo-two arithmetics of the primitive polynomials, but the recursion requires a certain number of start-up integers, and the better they are chosen, the more homogeneous will any short subsequence appear. Sobol' introduced the notion of property A and property A' to denote additional uniformity features and derived some conditions that are sufficient for these properties to be present. Under no circumstances should one use what I call trivial initialisation of the direction numbers which is to set them all to 1 since this leads to particularly poor Sobol' numbers (they start looking very bad for dimensions > 5).Regards,pj

If we approssimate an integral using the average value of the integrand estimated on a sequence of deterministic vectors [q(n)] ni=1,2 we could make a mistake. Error from the approximation is = product of two terms; the first the variation of the integrand or smoothness, the second factor is discrepancy of the underlying number distribution q(n). If we observe an integration interval [0,1]and find N numbers, q(1)...,q(N), in this interval, our aim is to determine the discrepancy of these numbers or deviation from a perfect distribution. For every sub-interval [0,x) for any x, the perfect sequence would have x*N of its first N terms to be found in the sub-interval [0,x). Observing the number of q(i)s we could find in the subinterval [0,x) and then taking its difference from x*N, we’ll obtain the deviation of this data from the perfect distribution.Take the absolute value of this difference, divide it by N, and extract the greatest this number as x increases between 0 and 1, we calculate a discrepancy of the observed numbers q(i) from the perfect distribution; sequences with the smallest discrepancies are named low discrepancy distributions.Waiting for your comments, thanks.

Every Monte Carlo simulation computes an expectation E(X) as an averageE(f(X)) = (f(X1)+f(X2)+...+f(Xn))/n,where the Xj are independent observation from the distribution of X. This is justifid by the Strong Law of Large Numbers (SLLN)E(f(X)) = lim_{n->oo} (f(X1)+f(X2)+...+f(Xn))/n (*)Usually this is done by (easy) reduction to the case where X is uniformly distributed in a cube (0,1)^d.The SLLN only holds in the ideal world of mathematical abstraction.In the real world of finite computers we cannot let n->oo nor do we have independent and uniformly distributedobservations Xj. Instead we have a random number generator with a finite number of distinct values (the cycle).Consequently (*) cannot hold for all functions f, for example it does not hold for any nonzero f which is zero onthe cycle of the random number generator. For which f does it hold?What is the error in (*) if the limit is replaced with some finite n?The mathematical theory provides probabilistic error estimates (probabilities that the error satisfies certain bounds)valid in the ideal world of mathematical abstraction. They are not valid in the real world of finite computers.We should recall that the SLLN asserts that (*) holds with probability one but what does this mean on a computer where there is no randomness. In other words we are on very unsure footing and in fact the SLLN does not provide any security and cannot not even be applied.A low discrepancy sequence Xj, j=1,2,... in (0,1)^d on the other hand is designed especially so that (*) works for known classes of reasonable f and there are deterministic error estimates relating the error to attributes of and the size of n. The theoretical results do actually apply to computer simulation.If you are worried about litigation use low discrepancy sequences.

QuoteIf you are worried about litigation use low discrepancy sequences.acutally don't. Columbia hold a patent on the use of lds in finance so if you use them you are making yourself open tolitigation.MJ