Sampling first-passage times of fractional Brownian motion using adaptive bisections.

We present an algorithm to efficiently sample first-passage times for fractional Brownian motion. To increase the resolution, an initial coarse lattice is successively refined close to the target, by adding exactly sampled midpoints, where the probability that they reach the target is non-negligible. Compared to a path of N equally spaced points, the algorithm achieves the same numerical accuracy N_{eff}, while sampling only a small fraction of all points. Though this induces a statistical error, the latter is bounded for each bridge, allowing us to bound the total error rate by a number of our choice, say P_{error}^{tot}=10^{-6}. This leads to significant improvements in both memory and speed. For H=0.33 and N_{eff}=2^{32}, we need 5000 times less CPU time and 10000 times less memory than the classical Davies-Harte algorithm. The gain grows for H=0.25 and N_{eff}=2^{42} to 3×10^{5} for CPU and 10^{6} for memory. We estimate our algorithmic complexity as C^{ABSec}(N_{eff})=O[(lnN_{eff})^{3}], to be compared to Davies-Harte, which has complexity C^{DH}(N)=O(NlnN). Decreasing P_{error}^{tot} results in a small increase in complexity, proportional to ln(1/P_{error}^{tot}). Our current implementation is limited to the values of N_{eff} given above, due to a loss of floating-point precision. Our algorithm can be adapted to other extreme events and arbitrary Gaussian processes. It enables one to numerically validate theoretical predictions that were hitherto inaccessible.