sub-random sequences in high dimension MC sims?

erstwhile · October 12th, 2004, 6:22 am

For a 100 factor sim, is it worth using Halton/Sobol sequences, or is convergence not vastly better than when using simple randoms?For high dimensionality Halton sequences, there seems to be a lot of clumping and recognisable patterns.Maybe it's best to just use "true" randoms?

exotiq · October 12th, 2004, 12:29 pm

Right, it's non-trivial to extend quasi-random sequance generation to be valid in extra dimensions, especially up in the 100 range.If you have a "true" random number generator, like one of those advanced ones that read heat or particle patterns, of course use those, otherwise pseudo-randoms are just good for not having dimension scaling issues or worrying about the KH inequality.

erstwhile · October 12th, 2004, 1:16 pm

Sadly, my random number generator is not linked to the cosmic background radiation.Anything in principal wrong with using a bog-standard built-in function to generate 100 randoms at a time, and then correlate them using the Cholesky decomposition of the 100 x 100 correlation matrix?

exotiq · October 12th, 2004, 1:56 pm

If your "bog-standard" randoms are serially independent (which was your problem with quasi-randoms), then sure, go ahead. The Cholesky decomposition will give them the correlations you put in, and you can test this easily.The bigger problem is how valid, stable, and useful to you really consider that 100x100 covariance matrix to be? I truly have trouble thinking of any financial scenario where you could get more that a few of those 10,000 numbers within a useful degree of accuracy. What I see more often in the simulation of large baskets of correlated things are factor models which to a good degree of confidence capture 80-95% of the co-variation of your variables...

erstwhile · October 12th, 2004, 2:55 pm

The intention is to create a (functionally) very simple testbed that estimates tranched credit index values. As you know, the standard model uses one correlation for every credit pair. I want to investigate the effects of this assumption. Clearly, as you say, a 100 x 100 correlation matrix doesn't contain 4950 bits of useful information. But I think simplifying the entire matrix to a single number is too simple!With a simple and flexible simulation, it would be easy to start with a single correlation for every pair, then let the correlations be randomly distributed with a mean and standard deviation, for example. Or one could simulate a single sector getting distressed and highly correlated.Once this simple sim "works" (meaning I can approximately reproduce screen pricing of things like iTraxx tranches) then I can try and implement some quasi-analytic methods (maybe Hull and White?).The ultimate goal is to gain intuition with the tranched products and evaluate some of the trading strategies that are going around the market.If the strategies end up being interesting, then a practical trading tool would be needed.But for now, I just want to avoid doing something ignorant with the randoms...

pj · October 23rd, 2004, 1:18 pm

1.) Never use Cholesky decomposition, use Numerical Recipes tred2, tqli, eigsrt, in that order, or any other robust spectral decomposition you like. All text book Cholesky decompositions (including Numerical Recipes in C's) already fail when you have a zero or near-zero but positive eigenvalue which is perfectly permissible for a correlation matrix. Spectral decompositions will not fail there, and they also allow you to truncate the noisy sub-zero ones that are irrelevant.2.) Sobol' numbers if initialised sensibly work extremely well in dimensions well above 100, Halton numbers don't. There are number theoretical reasons for that: the dimensionality coefficient c(d) in the convergence order c(d)log(N)/N grows geometrically for many low-discrepancy numbers but not for Sobol' or Niederreiter-Xing numbers. Niederreiter-Xing numbers require serious number theoretical calculations to precompute the construction numbers (see http://www.dismat.oeaw.ac.at/pirs/niedxing.html), and I don't know if anyone has precomputed them up to d=100 or higher. In my experience, they are no better than Sobol' numbers for d>5, and Sobol' numbers are much simpler to construct, so I always use those.3.) The myth about high-dimensionality and low discrepancy numbers is the main reason I wrote "Monte Carlo Methods in Finance". Please discontinue the myth. It is not true that you cannot use low discrepancy numbers in high dimensions. Honestly.Yours truly,Peter Jaeckel

erstwhile · October 25th, 2004, 9:26 am

peter - many thanks for that.it was no doubt the myth (as well as naive use of Cholseky + high dimension Halton numbers) that caused me to start this thread.i haven't encountered any problems with the Cholesky decomposition so far, but given your comments will implement something more robust.i seem to have misplaced my Sobol' generator but it shouldn't take long to make/find a new one.i bet many people working in the tranched credit area could benefit from the more rapid convergence afforded by low discrepancy numbers, as they would not be tied to analytic approximations to get their greeks.i am placing an order for your book today...

rleeuk · October 25th, 2004, 12:26 pm

Just out of interest, how many simulations do you have to run in order to get acceptable numbers for the greeks? In my experience for a ~100 name portfolio using a 1 factor gaussian copula, Sobol sequence & likelihood ratio method I needed at least 500K scenarios, even then not all deltas converge (I did have a very complicated cashflow engine though).

erstwhile · October 25th, 2004, 1:01 pm

I'm actually just finishing my credit sim, but when I built lower dimensional correlation type models in equity derivatives, my rule of thumb was that roughly 50 times as many runs are needed for "good deltas" as for "good prices" (obviously depending upon the delta of the option). Stratified (importance) sampling would have helped in the low delta options.One interesting approach I saw someone use was to use a single low discrepancy sequence which never changed, and then to treat this result as exact. Moving the spot prices and recalculating prices produced the greeks with little extra work...

abednego · October 26th, 2004, 12:45 am

Importance sampling may be of help in your investigations. There is a paper posted in the discussion thread "Importance sampling for CDOs". Also available is some software on fastmontecarlo.com.

rleeuk · October 26th, 2004, 10:21 am

I am not convinced that IS will have a positive effect on the estimation of greeks (using likelihood ratio method at least), I think mj also commented in his paper that further work needs to be done on this.Does anyone have a case where IS actually helped (say, halved the number of runs)?

junbum · June 2nd, 2005, 3:06 pm

Hello Erstwhile,I was wondering if you could send your simulation(in Visual Basic) on this to gvmrb@yahoo.co.uk.I am a graduate student an cannot afford to buy software but would like to try some tweaks for projects.Your help will be acknowledged and appreciated.

serko70 · June 7th, 2005, 9:50 am

I have been using digits of number PI to generate random numbers for Monte Carlo simulations. Over 1 trillion digits to the decimal calculated so far, noone could come up with any sort of algorithm or repeating sequence etc yet. I believe this is as truly random as we mortals can ever achieve. Attached is an Excel file which uses 14,285 uniformly distributed normalized random numbers derived from the first 99,995 decimal digits of PI for simulation in a sample Monte Carlo function called MC().The VBA code also includes a technic whcih accelerates the simulation process impressively and makes repetead uses of the MC() function in the spreadsheet possible.I used single precision random numbers because Excel's (before 2003) Normsinv() function is only accurate that much. One can easily generate double precision random numbers by using a better normalization function.

karlmarx · June 8th, 2005, 10:16 am

QuoteOriginally posted by: pj1.) Never use Cholesky decomposition, use Numerical Recipes tred2, tqli, eigsrt, in that order, or any other robust spectral decomposition you like. All text book Cholesky decompositions (including Numerical Recipes in C's) already fail when you have a zero or near-zero but positive eigenvalue which is perfectly permissible for a correlation matrix. Spectral decompositions will not fail there, and they also allow you to truncate the noisy sub-zero ones that are irrelevant.The cholesky algorithm can be slightly modified to handle positive definite matrix that are not full rank. Morevoer, I agree that spectral decomposition can enhance the convergence when combined with quasi random sequences, but the advantage of cholesky is that you get a lower triangular structure that cuts the number of elementary operations to half when correlating your iid random numbers.