NAG Library Routine Document
G05XAF initializes the Brownian bridge generator G05XBF
. It must be called before any calls to G05XBF
||T0, TEND, TIMES(NTIMES), RCOMM(12*(NTIMES+1))
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
be any set of time points satisfying
-dimensional Wiener sample path at these time points, and let
matrix such that
is the desired covariance structure for the Wiener process. Each point
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
. If we set
-dimensional standard Normal random variable, then
will behave like a normal (free) Wiener process. However if we fix the terminal value
will behave like a non-free Wiener process.
Given the start and end points of the process, the order in which successive interpolation times
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
Wiener sample paths each of dimension
. The main input to the Brownian bridge algorithm is then an array of quasi-random points
where each point
respectively, depending on whether a free or non-free Wiener process is required. When G05XBF
is called, the
th sample path for
is constructed as follows: if a non-free Wiener process is required set
equal to the terminal value
, otherwise construct
is the matrix described in Section 3.1
. The array TIMES
holds the remaining time points
in the order in which the bridge is to be constructed. For each
and construct the point
respectively depending on whether a free or non-free Wiener process is required. Note that in our discussion
is indexed from
, and so
is interpolated between the nearest (in time) Wiener points which have already been constructed. The routine G05XEF
can be used to initialize the TIMES
array for several predefined bridge construction orders.
Glasserman P (2004) Monte Carlo Methods in Financial Engineering Springer
- 1: T0 – REAL (KIND=nag_wp)Input
On entry: the starting value of the time interval.
- 2: TEND – REAL (KIND=nag_wp)Input
On entry: the end value of the time interval.
- 3: TIMES(NTIMES) – REAL (KIND=nag_wp) arrayInput
: the points in the time interval
at which the Wiener process is to be constructed. The order in which points are listed in TIMES
determines the bridge construction order. The routine G05XEF
can be used to create predefined bridge construction orders from a set of input times.
- , for ;
- , for and .
- 4: NTIMES – INTEGERInput
: the length of TIMES
, denoted by
in Section 3.1
- 5: RCOMM() – REAL (KIND=nag_wp) arrayCommunication Array
: communication array, used to store information between calls to G05XBF
. This array must not
be directly modified.
- 6: IFAIL – INTEGERInput/Output
must be set to
. If you are unfamiliar with this parameter you should refer to Section 3.3
in the Essential Introduction for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
is recommended. If the output of error messages is undesirable, then the value
is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is
. When the value is used it is essential to test the value of IFAIL on exit.
unless the routine detects an error or a warning has been flagged (see Section 6
6 Error Indicators and Warnings
If on entry
, explanatory error messages are output on the current error message unit (as defined by X04AAF
Errors or warnings detected by the routine:
On entry, and .
On entry, .
On entry, , and .
Constraint: for all .
Constraint: all elements of TIMES
must be unique.
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
, which could be very inefficient when
is large. G05XAF 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.
This example calls G05XAF, G05XBF
to generate two sample paths of a three dimensional free Wiener process. Pseudorandom variates are used to construct the sample paths.
See Section 9 in G05XBF
for additional examples.
9.1 Program Text
Program Text (g05xafe.f90)
9.2 Program Data
9.3 Program Results
Program Results (g05xafe.r)