Message Boards Message Boards

Record optimally first hitting times?

Posted 8 years ago

I'm back with a question about how to record the first hitting times optimally.

So, the task is to simulate 1mln Geometric Brownian Motion paths and record, for each of them, the first time a barrier $H$ is hit.

In the notebook attached below, I provide such an implementation - the fastest I was able to produce. It is, however 2x slower than the MATLAB code.

The question is: how to gain speed? Maybe anyone can look at the C-Compilation code, which is somewhat heuristically written there, and which does not display any speed improvement.

Attachments:
POSTED BY: Sandu Ursu
10 Replies
Posted 8 years ago

Thank you, Sander. Exp outside and Random Number generation with specified mean and standard deviation is a nice tip.

I don't know very well how to write Mathematica code to be compiled in C. Nevertheless, I tried that below, but it does not improve much. What am I doing wrong here?

tryC = Compile[{{n, _Integer}},
   Block[{spot = ConstantArray[95.0, n], K = 100, \[Sigma] = 0.15, 
     T = 1, r = 0.01, H = 85, m = 50, h, \[Alpha], RND, index, cc},
    h = T/m;
    \[Alpha] = r - \[Sigma]^2/2;
    index = ConstantArray[0.0, n];
    RND = 
     RandomVariate[
      NormalDistribution[\[Alpha] h, \[Sigma] Sqrt[h]], {m, n}];
    Table[spot = spot RND[[i]];
     cc = Clip[spot, {H + 33 $MachineEpsilon, H}, {i, 0}];
     index += Clip[index + cc, {i, i}, {0, 0}];
     , {i, m}];
    index],
   CompilationOptions -> {"InlineExternalDefinitions" -> True}, 
   "CompilationTarget" -> "C", "RuntimeOptions" -> "Speed"];

index = IntegerPart@
    Clip[tryC[1000000], {1, 50}, {50, 50}]; // AbsoluteTiming

Another question is why does it take so long to generate the random numbers? Is is because these numbers are "more random"? or because they are more precise (more decimal digits)?

POSTED BY: Sandu Ursu

they can, indeed, be 'more' (better?) random. Some methods give better/worse random numbers, but also the speed is different for different methods.

SeedRandom[1, Method -> "MKL"];

that one is faster (2-3 x) than the default ( "ExtendedCA"), at least on my system. But I'm not sure about the 'quality' of the numbers, and how critical it is for your application. One has to be very careful in the choice of the generator if one uses it for e.g. encryption.

POSTED BY: Sander Huisman

In your updated code, if you do the scaling and Exp outside, it speeds up like 40% or so on my laptop:

spot=S;index=ConstantArray[0,n]; (* vector specifying the hitting times for each path *)
RND=Exp[RandomVariate[NormalDistribution[\[Alpha] h,\[Sigma] Sqrt[h]],{m,n}]];
Table[spot*= RND[[i]]; (* simulation of prices in period i *)
    cc=Clip[spot,{H+33$MachineEpsilon,H},{i,0}];
    index+=Clip[index+cc,{i,i},{0,0}]; (* record the hitting times to index *)
,{i,m}];//AbsoluteTiming
index=IntegerPart@Clip[index,{1,50},{50,50}];//AbsoluteTiming
POSTED BY: Sander Huisman
Posted 8 years ago

In the beginning it is all True, but then when some of the elements of vtau record hitting times (lower than m=50), it will basically be true only if a hitting time didn't occur before. So that expression basically identifies which paths hit the barrier in that round and didn't hit it before.


I have updated my code to take RandVatriate outside the Table and it does indeed work faster (if you don't time the random number generation). I have also added some comments.

POSTED BY: Sandu Ursu

In my matlab 'converted' code, everything is a PackedArray (Developer`PackedArrayQ), so also there, there is not much room for speedups...

I'm not sure if you can really make it a lot faster in Mathematica to be honest without resorting to C and/or parallelisation.

POSTED BY: Sander Huisman

I understand the Matlab code now...

POSTED BY: Sander Huisman

You can translate your Matlab code to:

   S0=95.0;
   K=100;
   sigma=0.15;
   T=1;
   r=0.01
   alpha=(r-1/2*sigma^2);
   H=85;
   b=-Log[H/S0];
   c=Log[K/S0];
   m=50;
   h=T/m;

   n=1000000;
   AbsoluteTiming[mZ =Exp[RandomVariate[NormalDistribution[alpha h,sigma Sqrt[h]],{m,n}]];]

   vS=ConstantArray[S0,n];
   vtau=ConstantArray[m,n];

   Do[
       vS *= mZ[[i]];
       tmp=UnitStep[H-vS](1-Unitize[vtau-m]);
       vtau*= tmp;
       vtau+= tmp i;
   ,
       {i,m}
   ]//AbsoluteTiming

Most time is in the creation of the random numbers, which you probably can't really speed up...

POSTED BY: Sander Huisman

The code seems to be quite different, the Matlab code is better vectorized, creating random numbers at once; n*m matrix.

What is Clip[index + cc, {i, i}, {0, 0}] supposed to do? That specification for the second and third argument don't make a lot of sense. This is always 0 right?

POSTED BY: Sander Huisman
Posted 8 years ago

Not always, Sander. If you have a list with some of the elements equal to i, then it will give zero everywhere except those elements which equal i.

For instance, let i = 3, then

Clip[{0, 1, 3, 6, 3, 9, 3}, {3, 3}, {0, 0}]

gives:

{0, 0, 3, 0, 3, 0, 3}

I figured this is a faster way to do a Replace operation.


So, in the code, this line:

cc = Clip[spot, {H + 33 $MachineEpsilon, H}, {i, 0}];

identifies which which paths go below H and gives a vector cc with time i in positions corresponding to these paths and zero for others.

Then, this line of code:

index += Clip[index + cc, {i, i}, {0, 0}];

adds to index only the paths which hit the barrier in time i, eliminating those which did that previously ((a previous hitting time + i) > i replaced by zero in the resulting Clip vector).


I see now that the price process simulation alone takes more than the entire MATLAB code. Why are you saying that it is not vectorized?

POSTED BY: Sandu Ursu

I'm not sure if you should use these kind of tricks, but that is up to you of course.

You can also change the Table to a Do loop; should save some time... Also you could parallelise the code quite easily, I presume you're gonna do this kind of process many many times... so you could parallelise it on a large scale...

I'm not really sure what your code does because of the cryptic use of functions and the lack of any comments. It can probably be done faster, but I can't understand what you exactly do or what you want to do. the intro is kinda vague...

Edit: I meant to say that RandomVariate could be done outside the Table, at once creating a n*m matrix. I'll update my post above.

POSTED BY: Sander Huisman
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract