We can design an algorithm for generating Brownian bridge according to the theory above. The backward generation algorithm for Brownian bridge is to generate a sequence between \(a\) and \(b\). A practical strategy is called binary partitioning on \([0, T]\). It is based on a procedure of gradually reducing the grid size to half. Specifically, we start from \(T\) (level 0), then \(T/4, 3T/4\), then \(T/8, 3T/8, 5T/8, 7T/8\), etc.
The detailed algorithm:
Input: a sequence of random variate \(Z\) with standardized normal distribution and length \(N=2^{K}\)
Output: a Brownian bridge sequence \(W\) in time range \([0,T]\) and length \(N\)
\(W_{T} = \sqrt{T}Z\), \(W_{0}=0\), \(h=T\)
For k from 1 to \(K\)
\(h = h/2\)
for \(j\) from 1 to \(2^{k-1}\)
\(W_{(2j-1)h}=\dfrac{1}{2}(W_{2(j-1)h} + W_{2jh}) + \sqrt{h}Z\)
A generalized algorithm for any sequence length \(N\):
Input: a sequence of random variate \(Z\) with standardized normal distribution with length \(N\)
Output: a Brownian bridge sequence \(W\) in time range \([0,T]\) and length \(N\)
- \(W_{T} = \sqrt{T}Z_{0}\), \(j = 0\)
- Intialize array map[\(0..N-1\)] as all 0, except for map[\(N-1\)] = 1
- For \(i\) from 1 to \(N-1\)
- Find the first unpopulated entry in the map from current position of \(j\)
- Find the next populated entry in the map from there, noted as \(k\)
- Find the middle position of \(j\) and \(k\), noted as \(l\)
- bridgeIndex[\(i\)] = \(l\), leftIndex[\(i\)] = \(j\), rightIndex[\(i\)] = \(k\)
- Move \(j\) to the right position of \(k\), if it is out of map boundary, set \(j\) to 0
- For \(i\) from 1 to \(N-1\)
- \(l\) = bridgeIndex[\(i\)], \(j\) = leftIndex[\(i\)], \(k\) = rightIndex[\(i\)]
- \(W_{l}=\dfrac{t_{k}-t_{l}}{t_{k}-t_{j-1}} W_{j-1} + \dfrac{t_{l}-t_{j-1}}{t_{k}-t_{j-1}} W_{k} + \sqrt{\dfrac{(t_{l}-t_{j-1})(t_{k}-t_{l})}{t_{k}-t_{j-1}}}Z_{i}\). (\(t_{j-1}\) is treated as 0 when j is 0.)