# NAG FL Interfaceg05xef (bb_​make_​bridge_​order)

## ▸▿ Contents

Settings help

FL Name Style:

FL Specification Language:

## 1Purpose

g05xef takes a set of input times and permutes them to specify one of several predefined Brownian bridge construction orders. The permuted times can be passed to g05xaf or g05xcf to initialize the Brownian bridge generators with the chosen bridge construction order.

## 2Specification

Fortran Interface
 Subroutine g05xef ( t0, tend, move,
 Integer, Intent (In) :: bgord, ntimes, nmove, move(nmove) Integer, Intent (Inout) :: ifail Real (Kind=nag_wp), Intent (In) :: t0, tend, intime(ntimes) Real (Kind=nag_wp), Intent (Out) :: times(ntimes)
#include <nag.h>
 void g05xef_ (const Integer *bgord, const double *t0, const double *tend, const Integer *ntimes, const double intime[], const Integer *nmove, const Integer move[], double times[], Integer *ifail)
The routine may be called by the names g05xef or nagf_rand_bb_make_bridge_order.

## 3Description

The Brownian bridge algorithm (see Glasserman (2004)) is a popular method for constructing a Wiener process at a set of discrete times, ${t}_{0}<{t}_{1}<{t}_{2}<,\dots ,<{t}_{N}, for $N\ge 1$. To ease notation we assume that $T$ has the index $N+1$ so that $T={t}_{N+1}$. Inherent in the algorithm is the notion of a bridge construction order which specifies the order in which the $N+2$ points of the Wiener process, ${X}_{{t}_{0}},{X}_{T}$ and ${X}_{{t}_{i}}$, for $\mathit{i}=1,2,\dots ,N$, are generated. The value of ${X}_{{t}_{0}}$ is always assumed known, and the first point to be generated is always the final time ${X}_{T}$. Thereafter, successive points are generated iteratively by an interpolation formula, using points which were computed at previous iterations. In many cases the bridge construction order is not important, since any construction order will yield a correct process. However, in certain cases, for example when using quasi-random variates to construct the sample paths, the bridge construction order can be important.

### 3.1Supported Bridge Construction Orders

g05xef accepts as input an array of time points ${t}_{1},{t}_{2},\dots ,{t}_{N},T$ at which the Wiener process is to be sampled. These time points are then permuted to construct the bridge. In all of the supported construction orders the first construction point is $T$ which has index $N+1$. The remaining points are constructed by iteratively bisecting (sub-intervals of) the time indices interval $\left[0,N+1\right]$, as Figure 1 illustrates:
Figure 1
The time indices interval is processed in levels ${L}^{\mathit{i}}$, for $\mathit{i}=1,2,\dots$. Each level ${L}^{i}$ contains ${n}_{i}$ points ${L}_{1}^{i},\dots ,{L}_{{n}_{i}}^{i}$ where ${n}_{i}\le {2}^{i-1}$. The number of points at each level depends on the value of $N$. The points ${L}_{j}^{i}$ for $i\ge 1$ and $j=1,2,\dots {n}_{i}$ are computed as follows: define ${L}_{0}^{0}=N+1$ and set
 $Lji = J+ (K-J)/2 where J= max{Lkp:1≤k≤np, ​0≤pLji}$
By convention the maximum of the empty set is taken to be to be zero. Figure 1 illustrates the algorithm when $N+1$ is a power of two. When $N+1$ is not a power of two, one must decide how to round the divisions by $2$. For example, if one rounds down to the nearest integer, then one could get the following:
Figure 2
From the series of bisections outlined above, two ways of ordering the time indices ${L}_{j}^{i}$ are supported. In both cases, levels are always processed from coarsest to finest (i.e., increasing $i$). Within a level, the time indices can either be processed left to right (i.e., increasing $j$) or right to left (i.e., decreasing $j$). For example, when processing left to right, the sequence of time indices could be generated as:
 $N+1 L11 L12 L22 L13 L23 L33 L43 ⋯$
while when processing right to left, the same sequence would be generated as:
 $N+1 L11 L22 L12 L43 L33 L23 L13 ⋯$
g05xef, therefore, offers four bridge construction methods; processing either left to right or right to left, with rounding either up or down. Which method is used is controlled by the bgord argument. For example, on the set of times
 $t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 T$
the Brownian bridge would be constructed in the following orders:
• ${\mathbf{bgord}}=1$ (processing left to right, rounding down)
 $T t6 t3 t9 t1 t4 t7 t11 t2 t5 t8 t10 t12$
• ${\mathbf{bgord}}=2$ (processing left to right, rounding up)
 $T t7 t4 t10 t2 t6 t9 t12 t1 t3 t5 t8 t11$
• ${\mathbf{bgord}}=3$ (processing right to left, rounding down)
 $T t6 t9 t3 t11 t7 t4 t1 t12 t10 t8 t5 t2$
• ${\mathbf{bgord}}=4$ (processing right to left, rounding up)
 $T t7 t10 t4 t12 t9 t6 t2 t11 t8 t5 t3 t1 .$
The four construction methods described above can be further modified through the use of the input array move. To see the effect of this argument, suppose that an array $A$ holds the output of g05xef when ${\mathbf{nmove}}=0$ (i.e., the bridge construction order as specified by bgord only). Let
 $B = {tj:j=move(i),i=1,2,…,nmove}$
be the array of all times identified by move, and let $C$ be the array $A$ with all the elements in $B$ removed, i.e.,
 $C = {A(i):A(i)≠B(j),i=1,2,…,ntimes,j=1,2,…,nmove} .$
Then the output of g05xef when ${\mathbf{nmove}}>0$ is given by
 $B(1) B(2) ⋯ B(nmove) C(1) C(2) ⋯ C(ntimes-nmove)$
When the Brownian bridge is used with quasi-random variates, this functionality can be used to allow specific sections of the bridge to be constructed using the lowest dimensions of the quasi-random points.
Glasserman P (2004) Monte Carlo Methods in Financial Engineering Springer

## 5Arguments

1: $\mathbf{bgord}$Integer Input
On entry: the bridge construction order to use.
Constraint: ${\mathbf{bgord}}=1$, $2$, $3$ or $4$.
2: $\mathbf{t0}$Real (Kind=nag_wp) Input
On entry: ${t}_{0}$, the start value of the time interval on which the Wiener process is to be constructed.
3: $\mathbf{tend}$Real (Kind=nag_wp) Input
On entry: $T$, the largest time at which the Wiener process is to be constructed.
4: $\mathbf{ntimes}$Integer Input
On entry: $N$, the number of time points in the Wiener process, excluding ${t}_{0}$ and $T$.
Constraint: ${\mathbf{ntimes}}\ge 1$.
5: $\mathbf{intime}\left({\mathbf{ntimes}}\right)$Real (Kind=nag_wp) array Input
On entry: the time points, ${t}_{1},{t}_{2},\dots ,{t}_{N}$, at which the Wiener process is to be constructed. Note that the final time $T$ is not included in this array.
Constraints:
• ${\mathbf{t0}}<{\mathbf{intime}}\left(\mathit{i}\right)$ and ${\mathbf{intime}}\left(\mathit{i}\right)<{\mathbf{intime}}\left(\mathit{i}+1\right)$, for $\mathit{i}=1,2,\dots ,{\mathbf{ntimes}}-1$;
• ${\mathbf{intime}}\left({\mathbf{ntimes}}\right)<{\mathbf{tend}}$.
6: $\mathbf{nmove}$Integer Input
On entry: the number of elements in the array move.
Constraint: $0\le {\mathbf{nmove}}\le {\mathbf{ntimes}}$.
7: $\mathbf{move}\left({\mathbf{nmove}}\right)$Integer array Input
On entry: the indices of the entries in intime which should be moved to the front of the times array, with ${\mathbf{move}}\left(j\right)=i$ setting the $j$th element of times to ${t}_{i}$. Note that $i$ ranges from $1$ to ntimes. When ${\mathbf{nmove}}=0$, move is not referenced.
Constraint: $1\le {\mathbf{move}}\left(\mathit{j}\right)\le {\mathbf{ntimes}}$, for $\mathit{j}=1,2,\dots ,{\mathbf{nmove}}$.
The elements of move must be unique.
8: $\mathbf{times}\left({\mathbf{ntimes}}\right)$Real (Kind=nag_wp) array Output
On exit: the output bridge construction order. This should be passed to g05xaf or g05xcf.
9: $\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{bgord}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{bgord}}=1$, $2$, $3$ or $4$
${\mathbf{ifail}}=2$
On entry, ${\mathbf{ntimes}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{ntimes}}\ge 1$.
${\mathbf{ifail}}=3$
On entry, ${\mathbf{nmove}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{ntimes}}=⟨\mathit{\text{value}}⟩$.
Constraint: $0\le {\mathbf{nmove}}\le {\mathbf{ntimes}}$.
${\mathbf{ifail}}=4$
On entry, ${\mathbf{intime}}\left(⟨\mathit{\text{value}}⟩\right)=⟨\mathit{\text{value}}⟩$ and ${\mathbf{intime}}\left(⟨\mathit{\text{value}}⟩\right)=⟨\mathit{\text{value}}⟩$.
Constraint: the elements in intime must be in increasing order.
On entry, ${\mathbf{intime}}\left(1\right)=⟨\mathit{\text{value}}⟩$ and ${\mathbf{t0}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{intime}}\left(1\right)>{\mathbf{t0}}$.
On entry, ${\mathbf{ntimes}}=⟨\mathit{\text{value}}⟩$, ${\mathbf{intime}}\left({\mathbf{ntimes}}\right)=⟨\mathit{\text{value}}⟩$ and ${\mathbf{tend}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{intime}}\left({\mathbf{ntimes}}\right)<{\mathbf{tend}}$.
${\mathbf{ifail}}=5$
On entry, ${\mathbf{move}}\left(⟨\mathit{\text{value}}⟩\right)=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{move}}\left(i\right)\ge 1$ for all $i$.
On entry, ${\mathbf{move}}\left(⟨\mathit{\text{value}}⟩\right)=⟨\mathit{\text{value}}⟩$ and ${\mathbf{ntimes}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{move}}\left(i\right)\le {\mathbf{ntimes}}$ for all $i$.
${\mathbf{ifail}}=6$
On entry, ${\mathbf{move}}\left(⟨\mathit{\text{value}}⟩\right)$ and ${\mathbf{move}}\left(⟨\mathit{\text{value}}⟩\right)$ both equal $⟨\mathit{\text{value}}⟩$.
Constraint: all elements in move must be unique.
${\mathbf{ifail}}=-99$
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

g05xef is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

None.

## 10Example

This example calls g05xef, g05xaf and g05xbf to generate two sample paths of a three-dimensional free Wiener process. The array move is used to ensure that a certain part of the sample path is always constructed using the lowest dimensions of the input quasi-random points. For further details on using quasi-random points with the Brownian bridge algorithm, please see Section 2.6 in the G05 Chapter Introduction.

### 10.1Program Text

Program Text (g05xefe.f90)

None.

### 10.3Program Results

Program Results (g05xefe.r)