PJ,here is a question from your book:you mentioned in your book that you used brownian bridge path construction to deal with problems with thousands of time-steps. How do you apply Sobol' sequence to such a high dimensional problem because the highest dimension Sobol' sequence I've seen is about 370. If you do not use the Sobol sequence, do you use any other low discrepancy numbers?

all you need is another primitive polynomial for each extra dimension. So you just need a list sufficiently long. I think peter has such a list on his cd. If not you can generate a list of irredicubile polynomials via the Sieve ofErastosthenes and then check each one for primitivity. (every primitive polynomial is irreducible)

Reza,section 8.3, pages 80-87, is dedicated to the construction of Sobol' numbers. The only restriction in dimensionality I have is the ready availability of primitive polynomials modulo two. Indeed, only a comparatively small number of those were tabulated in the literature. This is why I provide a table of 8129334 primitive polynomials modulo two on the accompanying CD. Please note that primitive does not mean irreducible (i.e. prime), there is a difference, and the difference is by no means negligible. As a word of caution, an attempt to compile the entire set of 8 million primitive polynomials may result in your computer locking up since the source file is around 77 MB and the compiler will try to allocate many times that in memory. I find that#define PPMT_MAX_DIM N_PRIMITIVES_UP_TO_DEGREE_23gives me enough polynomials (i.e. Sobol' dimensions) for all practical purposes (634458, to be precise). The header and source file of those polynomials is documented.You may notice that while I provide code samples for a Brownian bridge and the code for the compilation of a table of primitive polynomials into a static array, I don't actually give code for the generation of Sobol' numbers (which naturally would have been very easy for me). There are two good reasons for that neither of which I feel at liberty to discuss in public. However, if you read my explanations in section 8.3 carefully, and also read the description of Sobol' numbers in Numerical Recipes and use their code as a starting point, it should be straightforward for you to devise your own Sobol' number generator without any practical dimensionality restriction. That's about as far as I can go in providing help for high-dimensional Sobol' number generation.Good luck,pjmuuh

Thanks very much !

Hi guys,This seems interesting, which book are you refering to ?Olivier

Peter Jackel's Monte-Carlo Methods in Finance

Monte Carlo Methods in FinanceP

PJ,here is a question from your book:you mentioned in your book that you used brownian bridge path construction to deal with problems with thousands of time-steps. How do you apply Sobol' sequence to such a high dimensional problem because the highest dimension Sobol' sequence I've seen is about 370. If you do not use the Sobol sequence, do you use any other low discrepancy numbers? >>i think the idea behind "applying brownian bridges to deal with high dimensions" is to get the maximum benefit from a smaller number of quasi-random or low discrepancy numbers. say we are generating a single path with 1000 points (=1000 dimensions). rather than using a 1000 dimensional sobol sequence (which i believe doesn't look too good if you take certain cross sections) use much lower dimensional sequence and "pad out" the rest of the numbers with the usual pseudo random numbers. the brownian bridges come in because it doesn't make sense to use the low discrepancy numbers for the last points in the path because if these points are closely spaced the variance of these points will be low. so the low discrepancy points are used to generate points on the path widely spaced apart (=high variance) and brownian bridges are used to calculate the intermediate points with the remaining pseudo-random numbers. in this way we ensure that the low discrepancy points are being used to their maximum advantage. any low discrepancy sequence tends to work very badly in high dimensions as the problem of covering the space evenly becomes impossible without enormous numbers of simulations.

oops - have just noticed another thread on a similar subject where pj gives a more detailed description of what i just said. don't have time to read the forum all the time... sorry!

pjAm I correct in thinking there is a typo in equation 8.20 of your book - namely that the upper limit of (XOR) summation should be 'b', and not 'd'? Thanks.