NAG Library Routine Document

G05XEF

+− Contents

1 Purpose

2 Specification

+− 3 Description

3.1 Supported Bridge Construction Orders

4 References

5 Parameters

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

+− 9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

1 Purpose

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.

2 Specification

SUBROUTINE G05XEF (

BGORD, T0, TEND, NTIMES, INTIME, NMOVE, MOVE, TIMES, IFAIL)

INTEGER	BGORD, NTIMES, NMOVE, MOVE(NMOVE), IFAIL
REAL (KIND=nag_wp)	T0, TEND, INTIME(NTIMES), TIMES(NTIMES)

3 Description

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} < T

, for

N \geq 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 Weiner process,

X_{t_{0}}, X_{T}

and

X_{t_{i}}

, for

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.1 Supported 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

[0, N + 1]

, as Figure 1 illustrates:

Figure 1

The time indices interval is processed in levels

L^{i}

, for

i = 1, 2, \dots

. Each level

L^{i}

contains

n_{i}

points

L_{1}^{i}, \dots, L_{n_{i}}^{i}

where

n_{i} \leq 2^{i - 1}

. The number of points at each level depends on the value of

N

. The points

L_{j}^{i}

for

i \geq 1

and

j = 1, 2, \dots n_{i}

are computed as follows: define

L_{0}^{0} = N + 1

and set

\begin{matrix} L_{j}^{i} = J + (K - J) / 2 & where \\ J = \max \{L_{k}^{p} : 1 \leq k \leq n_{p}, ​ 0 \leq p < i ​ and ​ L_{k}^{p} < L_{j}^{i}\} & ​ and ​ \\ K = \min \{L_{k}^{p} : 1 \leq k \leq n_{p}, ​ 0 \leq p < i ​ and ​ L_{k}^{p} > L_{j}^{i}\} \end{matrix}

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:

\begin{matrix} N + 1 & L_{1}^{1} & L_{1}^{2} & L_{2}^{2} & L_{1}^{3} & L_{2}^{3} & L_{3}^{3} & L_{4}^{3} & \dots \end{matrix}

while when processing right to left, the same sequence would be generated as:

\begin{matrix} N + 1 & L_{1}^{1} & L_{2}^{2} & L_{1}^{2} & L_{4}^{3} & L_{3}^{3} & L_{2}^{3} & L_{1}^{3} & \dots \end{matrix}

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 parameter. For example, on the set of times

\begin{matrix} t_{1} & t_{2} & t_{3} & t_{4} & t_{5} & t_{6} & t_{7} & t_{8} & t_{9} & t_{10} & t_{11} & t_{12} & T \end{matrix}

the Brownian bridge would be constructed in the following orders:

$BGORD = 1$ (processing left to right, rounding down)

\begin{matrix} T & t_{6} & t_{3} & t_{9} & t_{1} & t_{4} & t_{7} & t_{11} & t_{2} & t_{5} & t_{8} & t_{10} & t_{12} \end{matrix}

$BGORD = 2$ (processing left to right, rounding up)

\begin{matrix} T & t_{7} & t_{4} & t_{10} & t_{2} & t_{6} & t_{9} & t_{12} & t_{1} & t_{3} & t_{5} & t_{8} & t_{11} \end{matrix}

$BGORD = 3$ (processing right to left, rounding down)

\begin{matrix} T & t_{6} & t_{9} & t_{3} & t_{11} & t_{7} & t_{4} & t_{1} & t_{12} & t_{10} & t_{8} & t_{5} & t_{2} \end{matrix}

$BGORD = 4$ (processing right to left, rounding up)

\begin{matrix} T & t_{7} & t_{10} & t_{4} & t_{12} & t_{9} & t_{6} & t_{2} & t_{11} & t_{8} & t_{5} & t_{3} & t_{1} \end{matrix} .

The four construction methods described above can be further customized through the use of the input array MOVE. To see the effect of this parameter, suppose that an array

A

holds the output of G05XEF when

NMOVE = 0

(i.e., the unmodified bridge construction order as specified by BGORD). Let

B = \{t_{j} : j = MOVE (i), i = 1, 2, \dots, 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) \neq B (i), i = 1, 2, \dots, NTIMES, j = 1, 2, \dots, NMOVE\} .

Then the output of G05XEF when

NMOVE > 0

is given by

\begin{matrix} B (1) & B (2) & \dots & B (NMOVE) & C (1) & C (2) & \dots & C (NTIMES - NMOVE) \end{matrix}

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.

4 References

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

5 Parameters

1: BGORD – INTEGERInput

On entry: the bridge construction order to use.

Constraint:

BGORD = 1

2

3

4

2: 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: TEND – REAL (KIND=nag_wp)Input

On entry:

T

, the largest time at which the Wiener process is to be constructed.

4: NTIMES – INTEGERInput

On entry:

N

, the number of time points in the Weiner process, excluding

t_{0}

and

T

Constraint:

NTIMES \geq 1

5: INTIME(NTIMES) – REAL (KIND=nag_wp) arrayInput

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:

$T0 < INTIME (i)$ and $INTIME (i) < INTIME (i + 1)$ , for $i = 1, 2, \dots, NTIMES - 1$ ;
$INTIME (NTIMES) < TEND$ .

6: NMOVE – INTEGERInput

On entry: the number of elements in the array MOVE.

Constraint:

0 \leq NMOVE \leq NTIMES

7: MOVE(NMOVE) – INTEGER arrayInput

On entry: the indices of the entries in INTIME which should be moved to the front of the TIMES array, with

MOVE (j) = i

setting the

j

th element of TIMES to

t_{i}

. Note that

i

ranges from

1

to NTIMES. When

NMOVE = 0

, MOVE is not referenced.

Constraint:

1 \leq MOVE (j) \leq NTIMES

, for

j = 1, 2, \dots, NMOVE

The elements of MOVE must be unique.

8: TIMES(NTIMES) – REAL (KIND=nag_wp) arrayOutput

On exit: the output bridge construction order. This should be passed to G05XAF or G05XCF.

9: IFAIL – INTEGERInput/Output

On entry: IFAIL must be set to

0

- 1 ​ or ​ 1

. 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

- 1 ​ 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 parameter, the recommended value is

0

. When the value $- 1 or 1$ is used it is essential to test the value of IFAIL on exit.

On exit:

IFAIL = 0

unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry

IFAIL = 0

- 1

, explanatory error messages are output on the current error message unit (as defined by X04AAF).

Errors or warnings detected by the routine:

$IFAIL = 1$: On entry, $BGORD = ⟨value⟩$ .
Constraint: $BGORD = 1$ , $2$ , $3$ or $4$

$IFAIL = 2$: On entry, $NTIMES = ⟨value⟩$ .
Constraint: $NTIMES \geq 1$ .

$IFAIL = 3$: On entry, $NMOVE = ⟨value⟩$ and $NTIMES = ⟨value⟩$ .
Constraint: $0 \leq NMOVE \leq NTIMES$ .

$IFAIL = 4$: On entry, $INTIME (⟨value⟩) = ⟨value⟩$ and $INTIME (⟨value⟩) = ⟨value⟩$ .
Constraint: the elements in INTIME must be in increasing order.

On entry, $INTIME (1) = ⟨value⟩$ and $T0 = ⟨value⟩$ .
Constraint: $INTIME (1) > T0$ .

On entry, $NTIMES = ⟨value⟩$ , $INTIME (NTIMES) = ⟨value⟩$ and $TEND = ⟨value⟩$ .
Constraint: $INTIME (NTIMES) < TEND$ .

$IFAIL = 5$: On entry, $MOVE (⟨value⟩) = ⟨value⟩$ .
Constraint: $MOVE (i) \geq 1$ for all $i$ .

On entry, $MOVE (⟨value⟩) = ⟨value⟩$ and $NTIMES = ⟨value⟩$ .
Constraint: $MOVE (i) \leq NTIMES$ for all $i$ .

$IFAIL = 6$: On entry, $MOVE (i) = MOVE (j) = ⟨value⟩$ for $i = ⟨value⟩$ and $j = ⟨value⟩$ .
Constraint: all elements in MOVE must be unique.

7 Accuracy

Not applicable.

8 Further Comments

None.

9 Example

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.