NAG Library Function Document
nag_rand_bb_inc_init (g05xcc)
1 Purpose
nag_rand_bb_inc_init (g05xcc) initializes the Brownian bridge increments generator
nag_rand_bb_inc (g05xdc). It must be called before any calls to
nag_rand_bb_inc (g05xdc).
2 Specification
#include <nag.h> |
#include <nagg05.h> |
|
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
and let
be any set of time points satisfying
. Let
denote a
-dimensional Wiener sample path at these time points, and let
be any
by
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
where
is any
-dimensional standard Normal random variable, then
will behave like a normal (free) Wiener process. However if we fix the terminal value
, then
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
, and then uses this to compute the
scaled Wiener increments
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
nag_rand_bb_init (g05xac) and
nag_rand_bb (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
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
Wiener sample paths each of dimension
. The main input to the Brownian bridge increments generator is then an array of quasi-random points
where each point
has dimension
or
depending on whether a free or non-free Wiener process is required. When
nag_rand_bb_inc (g05xdc) 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
as
where
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
set
, find
and
and construct the point
as
where
or
depending on whether a free or non-free Wiener process is required. The function
nag_rand_bb_make_bridge_order (g05xec) can be used to initialize the
times array for several predefined bridge construction orders. Lastly, the scaled Wiener increments
are computed.
4 References
Glasserman P (2004) Monte Carlo Methods in Financial Engineering Springer
5 Arguments
- 1:
t0 – doubleInput
On entry: the starting value of the time interval.
- 2:
tend – doubleInput
On entry: the end value of the time interval.
Constraint:
.
- 3:
times[ntimes] – const doubleInput
On entry: 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 function
nag_rand_bb_make_bridge_order (g05xec) can be used to create predefined bridge construction orders from a set of input times.
Constraints:
- , for ;
- , for and .
- 4:
ntimes – IntegerInput
On entry: the length of
times, denoted by
in
Section 3.1.
Constraint:
.
- 5:
rcomm[] – doubleCommunication Array
-
On exit: communication array, used to store information between calls to
nag_rand_bb_inc (g05xdc). This array MUST NOT be directly modified.
- 6:
fail – NagError *Input/Output
-
The NAG error argument (see
Section 3.6 in the Essential Introduction).
6 Error Indicators and Warnings
- NE_BAD_PARAM
-
On entry, argument had an illegal value.
- NE_INT
-
On entry, .
Constraint: .
- 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.
- NE_REAL
-
On entry, and .
Constraint: .
- NE_REAL_ARRAY
-
On entry,
, for
and
.
Constraint: all elements of
times must be unique.
On entry, , and .
Constraint: for all .
7 Accuracy
Not applicable.
8 Parallelism and Performance
Not applicable.
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
or even
, which could be very inefficient when
is large. nag_rand_bb_inc_init (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
nag_rand_bb_init (g05xac) and
nag_rand_bb (g05xbc) to generate two sample paths from a two-dimensional free Wiener process. It then calls nag_rand_bb_inc_init (g05xcc) and
nag_rand_bb_inc (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
nag_rand_bb (g05xbc), the scaled increments from
nag_rand_bb_inc (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
nag_rand_bb (g05xbc).
Please see
Section 10 in nag_rand_bb_inc (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)