nag_rand_bb_make_bridge_order (g05xe) 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 nag_rand_bb_init (g05xa) or nag_rand_bb_inc_init (g05xc) to initialize the Brownian bridge generators with the chosen bridge construction order.
The Brownian bridge algorithm (see Glasserman (2004)) is a popular method for constructing a Wiener process at a set of discrete times, , for . To ease notation we assume that has the index so that . Inherent in the algorithm is the notion of a bridge construction order which specifies the order in which the points of the Wiener process, and , for , are generated. The value of is always assumed known, and the first point to be generated is always the final time . 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.
Supported Bridge Construction Orders
nag_rand_bb_make_bridge_order (g05xe) accepts as input an array of time points 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 which has index . The remaining points are constructed by iteratively bisecting (sub-intervals of) the time indices interval , as Figure 1 illustrates:
The time indices interval is processed in levels , for . Each level contains points where . The number of points at each level depends on the value of . The points for and are computed as follows: define and set
By convention the maximum of the empty set is taken to be to be zero. Figure 1 illustrates the algorithm when is a power of two. When is not a power of two, one must decide how to round the divisions by . For example, if one rounds down to the nearest integer, then one could get the following:
From the series of bisections outlined above, two ways of ordering the time indices are supported. In both cases, levels are always processed from coarsest to finest (i.e., increasing ). Within a level, the time indices can either be processed left to right (i.e., increasing ) or right to left (i.e., decreasing ). For example, when processing left to right, the sequence of time indices could be generated as:
while when processing right to left, the same sequence would be generated as:
nag_rand_bb_make_bridge_order (g05xe) 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
the Brownian bridge would be constructed in the following orders:
(processing left to right, rounding down)
(processing left to right, rounding up)
(processing right to left, rounding down)
(processing right to left, rounding up)
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 holds the output of nag_rand_bb_make_bridge_order (g05xe) when (i.e., the bridge construction order as specified by bgord only). Let
be the array of all times identified by move, and let be the array with all the elements in removed, i.e.,
Then the output of nag_rand_bb_make_bridge_order (g05xe) when is given by
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
Compulsory Input Parameters
– double scalar
, the start value of the time interval on which the Wiener process is to be constructed.
– double scalar
, the largest time at which the Wiener process is to be constructed.
– double array
The time points, , at which the Wiener process is to be constructed. Note that the final time is not included in this array.
and , for ;
– int64int32nag_int array
The indices of the entries in intime which should be moved to the front of the times array, with setting the th element of times to . Note that ranges from to ntimes. When , move is not referenced.
An unexpected error has been triggered by this routine. Please
Your licence key may have expired or may not have been installed correctly.
Dynamic memory allocation failed.
This example calls nag_rand_bb_make_bridge_order (g05xe), nag_rand_bb_init (g05xa) and nag_rand_bb (g05xb) 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 Brownian Bridge in the G05 Chapter Introduction.
fprintf('g05xe example results\n\n');
% Get information required to set up the bridge
[bgord,t0,tend,ntimes,intime,nmove,move] = get_bridge_init_data();
% Make the bridge construction bgord
[times, ifail] = g05xe( ...
t0, tend, intime, move, 'bgord', bgord);
% Initialize the Brownian bridge generator
[rcomm, ifail] = g05xa( ...
t0, tend, times);
% Get additional information required by the bridge generator
[npaths,d,start,a,term,c] = get_bridge_gen_data();
% Generate the Z values
[z] = get_z(npaths, d, a, ntimes);
% Call the Brownian bridge generator routine
[z, b, ifail] = g05xb( ...
npaths, start, term, z, c, rcomm, 'a', a);
% Display the results
for i = 1:npaths
fprintf('Weiner Path %d, %d time steps, %d dimensions\n', i, ntimes+1, d);
w = transpose(reshape(b(:,i), d, ntimes+1));
ifail = x04ca('G', ' ', w, '');
function [bgord,t0,tend,ntimes,intime,nmove,move] = get_bridge_init_data()
% Set the basic parameters for a Wiener process
t0 = 0;
ntimes = int64(10);
% We want to generate the Wiener process at these time points
intime = 1.71*double(1:ntimes) + t0;
tend = t0 + 1.71*double(ntimes + 1);
% We suppose the following 3 times are very important and should be% constructed first. Note: these are indices into intime
move = [int64(3), 5, 4];
bgord = int64(3);
function [npaths,d,start,a,term,c] = get_bridge_gen_data();
% Set the basic parameters for a non-free Wiener process
npaths = int64(2);
d = 3;
a = int64(0);
start = zeros(d, 1);
term = zeros(d, 1);
% As a = 0, term need not be initialized% We want the following covariance matrix
c = [ 6, 1, -0.2;
1, 5, 0.3;
-0.2, 0.3, 4 ];
% Cholesky factorize of the covariance matrix c
[c, info] = f07fd('l', c);
function [z] = get_z(npaths, d, a, ntimes)
idim = d*(ntimes+1-a);
% We now need to generate the input pseudorandom points% First initialize the base pseudorandom number generator
state = initialize_prng(int64(6), int64(0), [int64(1023401)]);
% Scrambled quasi-random sequences preserve the good discrepancy% properties of quasi-random sequences while counteracting the bias% some applications experience when using quasi-random sequences.% Initialize the scrambled quasi-random generator.
[iref, state] = initialize_scrambled_qrng(int64(1), int64(2), ...
% Generate the quasi-random points from N(0,1)
xmean = zeros(idim, 1);
std = ones(idim, 1);
[z, iref, ifail] = g05yj( ...
xmean, std, npaths, iref);
z = z';
function [state] = initialize_prng(genid, subid, seed)
% Initialize the generator to a repeatable sequence
[state, ifail] = g05kf( ...
genid, subid, seed);
function [iref, state] = initialize_scrambled_qrng(genid,stype,idim,state)
iskip = int64(0);
nsdigits = int64(32);
[iref, state, ifail] = g05yn( ...
genid, stype, int64(idim), ...
iskip, nsdigits, state);