NAG CL Interface
g05xcc (bb_​inc_​init)

Settings help

CL Name Style:


1 Purpose

g05xcc initializes the Brownian bridge increments generator g05xdc. It must be called before any calls to g05xdc.

2 Specification

#include <nag.h>
void  g05xcc (double t0, double tend, const double times[], Integer ntimes, double rcomm[], NagError *fail)
The function may be called by the names: g05xcc or nag_rand_bb_inc_init.

3 Description

3.1 Brownian Bridge Algorithm

Details on the Brownian bridge algorithm and the Brownian bridge process (sometimes also called a non-free Wiener process) can be found in Section 2.6 in the G05 Chapter Introduction. We briefly recall some notation and definitions.
Fix two times t0<T and let (ti) 1iN be any set of time points satisfying t0<t1<t2<⋯<tN<T. Let (Xti) 1iN denote a d-dimensional Wiener sample path at these time points, and let C be any d×d matrix such that CCT is the desired covariance structure for the Wiener process. Each point Xti of the sample path is constructed according to the Brownian bridge interpolation algorithm (see Glasserman (2004) or Section 2.6 in the G05 Chapter Introduction). We always start at some fixed point Xt0 = xd . If we set XT =x+ C T-t0 Z where Z is any d-dimensional standard Normal random variable, then X will behave like a normal (free) Wiener process. However if we fix the terminal value XT = wd , then X will behave like a non-free Wiener process.
The Brownian bridge increments generator uses the Brownian bridge algorithm to construct sample paths for the (free or non-free) Wiener process X, and then uses this to compute the scaled Wiener increments
Xt1 - Xt0 t1 - t0 , Xt2 - Xt1 t2 - t1 ,, XtN - XtN-1 tN - tN-1 , XT - XtN T - tN .  
Such increments can be useful in computing numerical solutions to stochastic differential equations driven by (free or non-free) Wiener processes.

3.2 Implementation

Conceptually, the output of the Wiener increments generator is the same as if g05xac and g05xbc were called first, and the scaled increments then constructed from their output. The implementation adopts a much more efficient approach whereby the scaled increments are computed directly without first constructing the Wiener sample path.
Given the start and end points of the process, the order in which successive interpolation times tj are chosen is called the bridge construction order. The construction order is given by the array times. Further information on construction orders is given in Section 2.6.2 in the G05 Chapter Introduction. For clarity we consider here the common scenario where the Brownian bridge algorithm is used with quasi-random points. If pseudorandom numbers are used instead, these details can be ignored.
Suppose we require the increments of P Wiener sample paths each of dimension d. The main input to the Brownian bridge increments generator is then an array of quasi-random points Z1,Z2,…,ZP where each point Zp = (Z1p,Z2p,,ZDp) has dimension D=d(N+1) or D=dN depending on whether a free or non-free Wiener process is required. When g05xdc is called, the pth sample path for 1pP is constructed as follows: if a non-free Wiener process is required set XT equal to the terminal value w, otherwise construct XT as
XT = Xt0 + C T-t0 [ Z1p Zdp ]  
where C is the matrix described in Section 3.1. The array times holds the remaining time points t1 , t2 ,… tN in the order in which the bridge is to be constructed. For each j=1,…,N set r=times[j-1], find
q = max { t0, times[i-1] : 1i<j , times[i-1] < r }  
and
s = min {T, times[i-1] : 1i<j , times[i-1] > r }  
and construct the point Xr as
Xr = Xq (s-r) + Xs (r-q) s-q + C (s-r) (r-q) (s-q) [ Zjd-ad+1p Zjd-ad+dp ]  
where a=0 or a=1 depending on whether a free or non-free Wiener process is required. The function g05xec can be used to initialize the times array for several predefined bridge construction orders. Lastly, the scaled Wiener increments
Xt1 - Xt0 t1 - t0 , Xt2 - Xt1 t2 - t1 ,…, XtN - XtN-1 tN - tN-1 , XT - XtN T - tN  
are computed.

4 References

Glasserman P (2004) Monte Carlo Methods in Financial Engineering Springer

5 Arguments

1: t0 double Input
On entry: the starting value t0 of the time interval.
2: tend double Input
On entry: the end value T of the time interval.
Constraint: tend>t0.
3: times[ntimes] const double Input
On entry: the points in the time interval (t0,T) at which the Wiener process is to be constructed. The order in which points are listed in times determines the bridge construction order. The function g05xec can be used to create predefined bridge construction orders from a set of input times.
Constraints:
  • t0<times[i-1]<tend, for i=1,2,,ntimes;
  • times[i-1] times[j-1], for i,j=1,2,ntimes and ij.
4: ntimes Integer Input
On entry: the length of times, denoted by N in Section 3.1.
Constraint: ntimes1.
5: rcomm[12×(ntimes+1)] double Communication Array
On exit: communication array, used to store information between calls to g05xdc. This array MUST NOT be directly modified.
6: fail NagError * Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_BAD_PARAM
On entry, argument value had an illegal value.
NE_INT
On entry, ntimes=value.
Constraint: ntimes1.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.
NE_REAL
On entry, tend=value and t0=value.
Constraint: tend>t0.
NE_REAL_ARRAY
On entry, times[i-1]=times[j-1]=value, for i=value and j=value.
Constraint: all elements of times must be unique.
On entry, times[value]=value, t0=value and tend=value.
Constraint: t0<times[i-1]<tend for all i.

7 Accuracy

Not applicable.

8 Parallelism and Performance

Background information to multithreading can be found in the Multithreading documentation.
g05xcc is not threaded in any implementation.

9 Further Comments

The efficient implementation of a Brownian bridge algorithm requires the use of a workspace array called the working stack. Since previously computed points will be used to interpolate new points, they should be kept close to the hardware processing units so that the data can be accessed quickly. Ideally the whole stack should be held in hardware cache. Different bridge construction orders may require different amounts of working stack. Indeed, a naive bridge algorithm may require a stack of size N 4 or even N 2 , which could be very inefficient when N is large. g05xcc performs a detailed analysis of the bridge construction order specified by times. Heuristics are used to find an execution strategy which requires a small working stack, while still constructing the bridge in the order required.

10 Example

The following example program calls g05xac and g05xbc to generate two sample paths from a two-dimensional free Wiener process. It then calls g05xcc and g05xdc with the same input arguments to obtain the scaled increments of the Wiener sample paths. Lastly, the program prints the Wiener sample paths from g05xbc, the scaled increments from g05xdc, and the cumulative sum of the unscaled increments side by side. Note that the cumulative sum of the unscaled increments is identical to the output of g05xbc.
Please see g05xdc for additional examples.

10.1 Program Text

Program Text (g05xcce.c)

10.2 Program Data

None.

10.3 Program Results

Program Results (g05xcce.r)