naginterfaces.library.rand.bb_​make_​bridge_​order

naginterfaces.library.rand.bb_make_bridge_order(t0, tend, intime, bgord=1, move=None)

bb_make_bridge_order 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 bb_init() or bb_inc_init() to initialize the Brownian bridge generators with the chosen bridge construction order.

For full information please refer to the NAG Library document for g05xe

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/g05/g05xef.html

Parameters

t0float

$t_0$, the start value of the time interval on which the Wiener process is to be constructed.

tendfloat

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

intimefloat, array-like, shape $\left(\text{ntimes}\right)$

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.

bgordint, optional

The bridge construction order to use.

moveNone or int, array-like, shape $\left(\text{nmove}\right)$, optional

The indices of the entries in $intime$ which should be moved to the front of the $times$ array, with $move[j-1]=i$ setting the $j$th element of $times$ to $t_i$. Note that $i$ ranges from $1$ to $\text{ntimes}$. When $\text{nmove}=0$, $move$ is not referenced.

Returns

timesfloat, ndarray, shape $\left(\text{ntimes}\right)$

The output bridge construction order. This should be passed to bb_init() or bb_inc_init().

Raises

NagValueError

(errno $-99$)

An unexpected error occurred during execution of bb_make_bridge_order. Please contact NAG with the following error message: error in $⟨value⟩$, $\text{ASSERT}=⟨value⟩$.

(errno $1$)

On entry, $bgord=⟨value⟩$.

Constraint: $bgord=1$, $2$, $3$ or $4$

(errno $2$)

On entry, $\text{ntimes}=⟨value⟩$.

Constraint: $\text{ntimes}\ge 1$.

(errno $3$)

On entry, $\text{nmove}=⟨value⟩$ and $\text{ntimes}=⟨value⟩$.

Constraint: $0\le \text{nmove}\le \text{ntimes}$.

(errno $4$)

On entry, $intime\left[0\right]=⟨value⟩$ and $t0=⟨value⟩$.

Constraint: $intime\left[0\right]>t0$.

(errno $4$)

On entry, $intime[⟨value⟩]=⟨value⟩$ and $intime[⟨value⟩]=⟨value⟩$.

Constraint: the elements in $intime$ must be in increasing order.

(errno $4$)

On entry, $\text{ntimes}=⟨value⟩$, $intime[\text{ntimes}-1]=⟨value⟩$ and $tend=⟨value⟩$.

Constraint: $intime[\text{ntimes}-1]<tend$.

(errno $5$)

On entry, $move[⟨value⟩]=⟨value⟩$.

Constraint: $move\left[i\right]\ge 1$ for all $i$.

(errno $5$)

On entry, $move[⟨value⟩]=⟨value⟩$ and $\text{ntimes}=⟨value⟩$.

Constraint: $move\left[i\right]\le \text{ntimes}$ for all $i$.

(errno $6$)

On entry, $move[⟨value⟩]$ and $move[⟨value⟩]$ both equal $⟨value⟩$.

Constraint: all elements in $move$ must be unique.

Notes

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\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 $\text{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.

Supported Bridge Construction Orders

bb_make_bridge_order 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 [label omitted] illustrates:

[figure omitted]

The time indices interval is processed in levels $L^{\text{i}}$, for $\text{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

$$\begin{array}{c}\begin{array}{cc}{L}_j^i=J+(K-J)/2& \text{where}\\ J=max\{L_k^p:1\le k\le n_p\text{,}0\le p<i\text{and}{L}_k^p<L_j^i\}& \text{and}\\ K=min\{L_k^p:1\le k\le n_p\text{,}0\le p<i\text{and}{L}_k^p>L_j^i\}& \end{array}\end{array}$$

By convention the maximum of the empty set is taken to be to be zero. Figure [label omitted] 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 omitted]

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{array}{ccccccccc}N+1& L_1^1& L_1^2& L_2^2& L_1^3& L_2^3& L_3^3& L_4^3& \cdots \end{array}$$

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

$$\begin{array}{ccccccccc}N+1& L_1^1& L_2^2& L_1^2& L_4^3& L_3^3& L_2^3& L_1^3& \cdots \end{array}$$

bb_make_bridge_order, 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

$$\begin{array}{ccccccccccccc}{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{array}$$

the Brownian bridge would be constructed in the following orders:

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

$$\begin{array}{ccccccccccccc}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{array}$$

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

$$\begin{array}{ccccccccccccc}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{array}$$

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

$$\begin{array}{ccccccccccccc}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{array}$$

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

$$\begin{array}{ccccccccccccc}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{array}\text{.}$$

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 bb_make_bridge_order when $\text{nmove}=0$ (i.e., the bridge construction order as specified by $bgord$ only). Let

$$B=\{t_j:j=move[i-1],i=1,2,\dots ,\text{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\left(i\right):A\left(i\right)\ne B\left(j\right),i=1,2,\dots ,\text{ntimes},j=1,2,\dots ,\text{nmove}\}\text{.}$$

Then the output of bb_make_bridge_order when $\text{nmove}>0$ is given by

$$\begin{array}{cccccccc}B\left(1\right)& B\left(2\right)& \cdots & B\left(\text{nmove}\right)& C\left(1\right)& C\left(2\right)& \cdots & C(\text{ntimes}-\text{nmove})\end{array}$$

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.

References

Glasserman, P, 2004, Monte Carlo Methods in Financial Engineering, Springer

See also

naginterfaces.library.examples.rand.bb_inc_ex.main()