Quasi-Monte-Carlo-Methods

for the valuation of financial instruments

(c) Weber & Partner, financial technology, www.weber-und-partner.com

<< Statistics`
<< Graphics`

Quasi-Monte Carlo Methods

Generating of Quasi-Monte Carlo sequences

Aim of the Monte-Carlo Method is in the end to explore an unknown result space. The problem with Monte Carlo is that this exploration is random. This means that a specific area in the result space might be explored multiple times other areas are not explored at all. This problem can be seen by visualizing the generated random numbers.

n  =  1000;
ListPlot[Table[{i/n, Random[]}, {i, n}], Frame -> True, 
        AspectRatio -> 1];

There are clusters in some areas other areas are white. An alternative to random numbers are determistic number sequences which explore the result space systematicly. An example for such low discrepancy sequences are van-der Corput and Halton sequences. Following Ötken (1999) these sequences can be implemented in Mathematica as

Corput[n_, b_]  :=  
        IntegerDigits[n, b] . 
          (b^Range)[-Floor[Log[b, n] + 1], -1];
Attributes[Corput]  = Listable;

The first argument defines which element of the row will be calculated the second argument defines the basis to which the sequence is generated. Extensions of the van-der-Corput sequences are the Halton sequences (For further details on these sequences see Ötken (1999)).

Halton[n_, s_]  :=  Corput[n, Prime[Range[s]]]
ListPlot[Table[Halton[n, 2], {n, 1000}], Frame -> True, 
        AspectRatio ->  1];

Using the low discrepancy sequences

The simplest method to use the low discrepancy sequences is to overwrite the build in random generator of Mathematica.  The sequence can be generated once up front as an array.

n  =  1000;
rand  =  Array[Halton[#, 2] &, n] //  Flatten  //  
          N;
$RandomSequence  =  0;
Unprotect[Random];
Random[]  :=  rand[[$RandomSequence  += 1 ]];
Protect[Random];

Each call to Random returns a number of the sequence. The global variable $RandomSequence makes the necessary bookkeeping to assure that the returned number is always the next within the sequence.

$RandomSequence  =  0;
Table[Random[], {10}]

n  =  1000;
$RandomSequence  =  0;
ListPlot[Table[{i/n, Random[]}, {i, n}], Frame -> True, 
        AspectRatio -> 1];

Using the low discrepancy sequences together with the normal distribution

Mathematica uses a variant of the Box-Muller method to generate normal distributed random numbers. Within this method two equally distributed random numbers are used. Therefore a sequence of 2000 numbers is needed to generate 1000 normal distributed random numbers.

$RandomSequence  =  0;
ndata  =  Table[Random[NormalDistribution[]], {1000}];
Histogram[ndata, HistogramScale -> 1];
$RandomSequence

The advocated approach does not always work with RandomArray. The reason for this is that Mathematica automaticly compiles the function connected with RandomArray when the package is loaded (see the comments from the original developer in the package Statistics`NormalDistribution`). This problem can be circumvated if the build-in random generator is overwritten before the package is loaded.

Using the low discrepancy sequences together with the normal distribution

Following the described approach for low discrepancy sequences the implementation of a simple option is the same as with the normal Monte-Carlo method.

r  =  0.05;   
X  =  50;    
τ = 1.0;    
σ  =  0.2;     
(Subscript[S, 0])  =  49;   
Map[
        Max[(Subscript[S, 0]) (E^((- ((σ^2)/2) + r) τ + σ (Sqrt[ τ]) #)) - X, 0] &, 
        ndata]  //  (E^(-r τ)) Mean[#] &

Undoing the changes to Random[]

If it is necessary to recover the build-in random generator of Mathematica within a session the overwriting can be undone with the following commands.

Unprotect[Random];
Clear[Random];
Protect[Random];

Literature

Boyle, Philm P., 1977, Options: A Monte Carlo Approach, in: Journal of Financial Economics, 4/1977, p.141-158.
Clewlow, L./Strickland, C., 1998, Implementing Derivatives Models, John Wiley & Sons Ltd.
Ötken, Giray, 1999, Quasi-Monte Carlo Methods in Option Pricing, in: Mathematica in Education and Research, Vol. 8, No. 3-4, p. 52-57.
Shaw, William: Modelling Financial Derivatives with Mathematica, Cambridge 1998.