NAG FL Interfaceg05xaf (bb_​init)

1Purpose

g05xaf initializes the Brownian bridge generator g05xbf. It must be called before any calls to g05xbf.

2Specification

Fortran Interface
 Subroutine g05xaf ( t0, tend,
 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))
#include <nag.h>
 void g05xaf_ (const double *t0, const double *tend, const double times[], const Integer *ntimes, double rcomm[], Integer *ifail)
The routine may be called by the names g05xaf or nagf_rand_bb_init.

3Description

3.1Brownian 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 ${t}_{0} 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}. 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 {ℝ}^{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 {ℝ}^{d}$, then $X$ will behave like a non-free Wiener process.

3.2Implementation

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 quasi-random points. If pseudorandom numbers are used instead, these details can be ignored.
Suppose we require $P$ Wiener sample paths each of dimension $d$. The main input to the Brownian bridge algorithm is then an array of quasi-random 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$ respectively, depending on whether a free or non-free Wiener process is required. When g05xbf is called, the $p$th sample path for $1\le p\le P$ is constructed as follows: if a non-free Wiener process is required set ${X}_{T}$ equal to the terminal value $w$, otherwise construct ${X}_{T}$ 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 ${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
 $q = max t0, timesi : 1≤i
and
 $s = min T, timesi : 1≤i r$
and construct the point ${X}_{r}$ 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$ respectively depending on whether a free or non-free Wiener process is required. Note that in our discussion $j$ is indexed from $1$, and so ${X}_{r}$ 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.

4References

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

5Arguments

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) array Input
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}$Integer Input
On entry: the length of times, denoted by $N$ in Section 3.1.
Constraint: ${\mathbf{ntimes}}\ge 1$.
5: $\mathbf{rcomm}\left(12×\left({\mathbf{ntimes}}+1\right)\right)$Real (Kind=nag_wp) array Communication Array
On exit: communication array, used to store information between calls to g05xbf. This array must not be directly modified.
6: $\mathbf{ifail}$Integer Input/Output
On entry: ifail must be set to $0$, $-1$ or $1$ to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of $0$ causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of $-1$ means that an error message is printed while a value of $1$ means that it is not.
If halting is not appropriate, the value $-1$ or $1$ is recommended. If message printing is undesirable, then the value $1$ is recommended. Otherwise, the value $0$ is recommended. When the value $-\mathbf{1}$ 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).

6Error 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}}=〈\mathit{\text{value}}〉$ and ${\mathbf{t0}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{tend}}>{\mathbf{t0}}$.
${\mathbf{ifail}}=2$
On entry, ${\mathbf{ntimes}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{ntimes}}\ge 1$.
${\mathbf{ifail}}=3$
On entry, ${\mathbf{times}}\left(〈\mathit{\text{value}}〉\right)=〈\mathit{\text{value}}〉$, ${\mathbf{t0}}=〈\mathit{\text{value}}〉$ and ${\mathbf{tend}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{t0}}<{\mathbf{times}}\left(i\right)<{\mathbf{tend}}$ for all $i$.
${\mathbf{ifail}}=4$
On entry, ${\mathbf{times}}\left(〈\mathit{\text{value}}〉\right)$ and ${\mathbf{times}}\left(〈\mathit{\text{value}}〉\right)$ both equal $〈\mathit{\text{value}}〉$.
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 7 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

Not applicable.

8Parallelism and Performance

g05xaf 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. 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.

10Example

This example calls g05xaf, g05xbf and g05xef to generate two sample paths of a three-dimensional free Wiener process. Pseudorandom variates are used to construct the sample paths.
See Section 10 in g05xbf and g05xef for additional examples.

10.1Program Text

Program Text (g05xafe.f90)

None.

10.3Program Results

Program Results (g05xafe.r)