NAG Library Routine Document
g05xcf (bb_inc_init)
1
Purpose
g05xcf initializes the Brownian bridge increments generator
g05xdf. It must be called before any calls to
g05xdf.
2
Specification
Fortran Interface
Integer, Intent (In)  ::  ntimes  Integer, Intent (Inout)  ::  ifail  Real (Kind=nag_wp), Intent (In)  ::  t0, tend, times(ntimes)  Real (Kind=nag_wp), Intent (Out)  ::  rcomm(12*(ntimes+1)) 

3
Description
3.1
Brownian Bridge Algorithm
Details on the Brownian bridge algorithm and the Brownian bridge process (sometimes also called a nonfree Wiener process) can be found in
Section 2.6 in the G05 Chapter Introduction. We briefly recall some notation and definitions.
Fix two times
${t}_{0}<T$ and let
${\left({t}_{i}\right)}_{1\le i\le N}$ be any set of time points satisfying
${t}_{0}<{t}_{1}<{t}_{2}<\cdots <{t}_{N}<T$. Let
${\left({X}_{{t}_{i}}\right)}_{1\le i\le N}$ denote a
$d$dimensional Wiener sample path at these time points, and let
$C$ be any
$d$ by
$d$ matrix such that
$C{C}^{\mathrm{T}}$ is the desired covariance structure for the Wiener process. Each point
${X}_{{t}_{i}}$ 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
${X}_{{t}_{0}}=x\in {\mathbb{R}}^{d}$. If we set
${X}_{T}=x+C\sqrt{T{t}_{0}}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
${X}_{T}=w\in {\mathbb{R}}^{d}$, then
$X$ will behave like a nonfree Wiener process.
The Brownian bridge increments generator uses the Brownian bridge algorithm to construct sample paths for the (free or nonfree) Wiener process
$X$, 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 nonfree) Wiener processes.
3.2
Implementation
Conceptually, the output of the Wiener increments generator is the same as if
g05xaf and
g05xbf 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
${t}_{j}$ 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 quasirandom 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 quasirandom points
${Z}^{1},{Z}^{2},\dots ,{Z}^{P}$ where each point
${Z}^{p}=\left({Z}_{1}^{p},{Z}_{2}^{p},\dots ,{Z}_{D}^{p}\right)$ has dimension
$D=d\left(N+1\right)$ or
$D=dN$ depending on whether a free or nonfree Wiener process is required. When
g05xdf is called, the
$p$th sample path for
$1\le p\le P$ is constructed as follows: if a nonfree Wiener process is required set
${X}_{T}$ equal to the terminal value
$w$, otherwise construct
${X}_{T}$ as
where
$C$ is the matrix described in
Section 3.1. The array
times holds the remaining time points
${t}_{1},{t}_{2},\dots {t}_{N}$ in the order in which the bridge is to be constructed. For each
$j=1,\dots ,N$ set
$r={\mathbf{times}}\left(j\right)$, find
and
and construct the point
${X}_{r}$ as
where
$a=0$ or
$a=1$ depending on whether a free or nonfree Wiener process is required. The routine
g05xef 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: $\mathbf{t0}$ – Real (Kind=nag_wp)Input

On entry: the starting value ${t}_{0}$ of the time interval.
 2: $\mathbf{tend}$ – Real (Kind=nag_wp)Input

On entry: the end value $T$ of the time interval.
Constraint:
${\mathbf{tend}}>{\mathbf{t0}}$.
 3: $\mathbf{times}\left({\mathbf{ntimes}}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: the points in the time interval
$\left({t}_{0},T\right)$ 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.
Constraints:
 ${\mathbf{t0}}<{\mathbf{times}}\left(\mathit{i}\right)<{\mathbf{tend}}$, for $\mathit{i}=1,2,\dots ,{\mathbf{ntimes}}$;
 ${\mathbf{times}}\left(i\right)\ne {\mathbf{times}}\left(j\right)$, for $i,j=1,2,\dots {\mathbf{ntimes}}$ and $i\ne j$.
 4: $\mathbf{ntimes}$ – IntegerInput

On entry: the length of
times, denoted by
$N$ in
Section 3.1.
Constraint:
${\mathbf{ntimes}}\ge 1$.
 5: $\mathbf{rcomm}\left(12\times \left({\mathbf{ntimes}}+1\right)\right)$ – Real (Kind=nag_wp) arrayCommunication Array

On exit: communication array, used to store information between calls to
g05xdf. This array
must not be directly modified.
 6: $\mathbf{ifail}$ – IntegerInput/Output

On entry:
ifail must be set to
$0$,
$1\text{ or}1$. If you are unfamiliar with this argument you should refer to
Section 3.4 in How to Use the NAG Library and its Documentation for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value
$1\text{ or}1$ is recommended. If the output of error messages is undesirable, then the value
$1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is
$0$.
When the value $\mathbf{1}\text{ or}\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit:
${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see
Section 6).
6
Error Indicators and Warnings
If on entry
${\mathbf{ifail}}=0$ or
$1$, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Errors or warnings detected by the routine:
 ${\mathbf{ifail}}=1$

On entry, ${\mathbf{tend}}=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{t0}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{tend}}>{\mathbf{t0}}$.
 ${\mathbf{ifail}}=2$

On entry, ${\mathbf{ntimes}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{ntimes}}\ge 1$.
 ${\mathbf{ifail}}=3$

On entry, ${\mathbf{times}}\left(\u2329\mathit{\text{value}}\u232a\right)=\u2329\mathit{\text{value}}\u232a$, ${\mathbf{t0}}=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{tend}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{t0}}<{\mathbf{times}}\left(i\right)<{\mathbf{tend}}$ for all $i$.
 ${\mathbf{ifail}}=4$

On entry,
${\mathbf{times}}\left(i\right)={\mathbf{times}}\left(j\right)=\u2329\mathit{\text{value}}\u232a$, for
$i=\u2329\mathit{\text{value}}\u232a$ and
$j=\u2329\mathit{\text{value}}\u232a$.
Constraint: all elements of
times must be unique.
 ${\mathbf{ifail}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 3.9 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{ifail}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 3.8 in How to Use the NAG Library and its Documentation for further information.
 ${\mathbf{ifail}}=999$
Dynamic memory allocation failed.
See
Section 3.7 in How to Use the NAG Library and its Documentation for further information.
7
Accuracy
Not applicable.
8
Parallelism and Performance
g05xcf is not threaded in any implementation.
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
$\frac{N}{4}$ or even
$\frac{N}{2}$, which could be very inefficient when
$N$ is large.
g05xcf 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
g05xaf and
g05xbf to generate two sample paths from a twodimensional free Wiener process. It then calls
g05xcf and
g05xdf with the same input arguments to obtain the scaled increments of the Wiener sample paths. Lastly, the program prints the Wiener sample paths from
g05xbf, the scaled increments from
g05xdf, 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
g05xbf.
Please see
Section 10 in
g05xdf for additional examples.
10.1
Program Text
Program Text (g05xcfe.f90)
10.2
Program Data
None.
10.3
Program Results
Program Results (g05xcfe.r)