nag_rand_bb_init (g05xac) : NAG Library, Mark 24

nag_rand_bb_init (g05xac) initializes the Brownian bridge generator nag_rand_bb (g05xbc). It must be called before any calls to nag_rand_bb (g05xbc).

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

and let

{(t_{i})}_{1 \leq i \leq N}

be any set of time points satisfying

t_{0} < t_{1} < t_{2} <\dots< t_{N} < T

. Let

{(X_{t_{i}})}_{1 \leq i \leq N}

denote a

d

-dimensional Wiener sample path at these time points, and let

C

be any

d

d

matrix such that

C C^{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.

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} = (Z_{1}^{p}, Z_{2}^{p}, \dots, Z_{D}^{p})

has dimension

D = d (N + 1)

D = d N

respectively, depending on whether a free or non-free Wiener process is required. When nag_rand_bb (g05xbc) is called, the

p

th sample path for

1 \leq p \leq 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}

X_{T} = X_{t_{0}} + C \sqrt{T - t_{0}} [\begin{matrix} Z_{1}^{p} \\ ⋮ \\ Z_{d}^{p} \end{matrix}]

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 = times [j - 1]

, find

q = max \{t_{0}, times [i - 1] : 1 \leq i < j, times [i - 1] < r\}

and

s = min \{T, times [i - 1] : 1 \leq i < j, times [i - 1] > r\}

and construct the point

X_{r}

X_{r} = \frac{X_{q} (s - r) + X_{s} (r - q)}{s - q} + C \sqrt{\frac{(s - r) (r - q)}{(s - q)}} [\begin{matrix} Z_{j d - a d + 1}^{p} \\ ⋮ \\ Z_{j d - a d + d}^{p} \end{matrix}]

where

a = 0

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 function nag_rand_bb_make_bridge_order (g05xec) can be used to initialize the times array for several predefined bridge construction orders.

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

On entry: the starting value

t_{0}

of the time interval.

On entry: the end value

T

of the time interval.

Constraint:

tend > t0

On entry: the points in the time interval

(t_{0}, T)

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:

$t0 < times [i - 1] < tend$ , for $i = 1, 2, \dots, ntimes$ ;
$times [i - 1] \neq times [j - 1]$ , for $i, j = 1, 2, \dots ntimes$ and $i \neq j$ .

On entry: the length of times, denoted by

N

in Section 3.1.

Constraint:

ntimes \geq 1

On exit: communication array, used to store information between calls to nag_rand_bb (g05xbc). This array MUST NOT be directly modified.

The NAG error argument (see Section 3.6 in the Essential Introduction).

On entry, argument

⟨value⟩

had an illegal value.

On entry,

ntimes = ⟨value⟩

.
Constraint:

ntimes \geq 1

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.

On entry,

tend = ⟨value⟩

and

t0 = ⟨value⟩

.
Constraint:

tend > t0

On entry,

times [⟨value⟩] = ⟨value⟩

t0 = ⟨value⟩

and

tend = ⟨value⟩

.
Constraint:

t0 < times [i - 1] < tend

for all

i

On entry,

times [⟨value⟩]

and

times [⟨value⟩]

both equal

⟨value⟩

.
Constraint: all elements of times must be unique.

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. nag_rand_bb_init (g05xac) 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.

This example calls nag_rand_bb_init (g05xac), nag_rand_bb (g05xbc) and nag_rand_bb_make_bridge_order (g05xec) 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 nag_rand_bb (g05xbc) and nag_rand_bb_make_bridge_order (g05xec) for additional examples.

NAG Library Function Document

nag_rand_bb_init (g05xac)

+− Contents

1 Purpose

2 Specification

3 Description

3.1 Brownian Bridge Algorithm

3.2 Implementation

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG Library Function Documentnag_rand_bb_init (g05xac)

+− Contents

1 Purpose

2 Specification

3 Description

3.1 Brownian Bridge Algorithm

3.2 Implementation

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG Library Function Document

nag_rand_bb_init (g05xac)