Papers › Sampling first-passage times of fractional Brownian Motion using adaptive bisections
Sampling first-passage times of fractional Brownian Motion using adaptive bisections
Benjamin Walter, Kay Joerg Wiese
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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ₑᵣᵣₒᵣᵗᵒᵗ=10⁻⁶. This leads to significant improvements in both memory and speed. For H=0.33 and N_(eff)=2³², we need 5 000 times less CPU time and 10 000 times less memory than the classical Davies Harte algorithm. The gain grows for H=0.25 and N_(eff) = 2⁴² to 3·10⁵ for CPU and 10⁶ for memory. We estimate our algorithmic complexity as C^(ABSec)(N_(eff)) = O(( lnN_(eff))³), to be compared to Davies Harte which has complexity Cᴰᴴ(N) = O(N lnN ). Decreasing Pₑᵣᵣₒᵣᵗᵒᵗ results in a small increase in complexity, proportional to ln(1/Pₑᵣᵣₒᵣᵗᵒᵗ). Our current implementation is limited to the values of N_(eff) given above, due to a loss of floating-point precision. The algorithm can be adapted to other extreme events and arbitrary Gaussian processes. It enables one to numerically validate theoretical predictions that were hitherto inaccessible.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections