Sampling first-passage times of fractional Brownian Motion using adaptive bisections

Abstract

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_{\mathrm{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_{\mathrm{error}}^{\mathrm{tot}}=10^{-6}$. This leads to significant improvements in both memory and speed. For $H=0.33$ and $N_{\mathrm{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_{\mathrm{eff}}=2^{42}$ to $3\cdot 10^5$ for CPU and $10^6$ for memory. We estimate our algorithmic complexity as ${\mathcal{C}}^{\mathrm{ABSec}}(N_{\mathrm{eff}})=\mathcal{O}\left({\left(\ln N_{\mathrm{eff}}\right)}^3\right)$, to be compared to Davies Harte which has complexity ${\mathcal{C}}^{\mathrm{DH}}(N)=\mathcal{O}\left(N\ln N\right)$. Decreasing $P_{\mathrm{error}}^{\mathrm{tot}}$ results in a small increase in complexity, proportional to $\ln (1/P_{\mathrm{error}}^{\mathrm{tot}})$. Our current implementation is limited to the values of $N_{\mathrm{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.

arXiv comment15 pages, 10 figues

References in corpus (13)

• Mean first-passage times of non-Markovian random walkers in confinement
• Spectral content of a single non-Brownian trajectory
• First passage time distribution in heterogeneity controlled kinetics: going beyond the mean first passage time
• Generalized arcsine laws for fractional Brownian motion
• Fractional Brownian motion in a finite interval: correlations effect depletion or accretion zones of particles near boundaries
• Extreme-Value Statistics of Fractional Brownian Motion Bridges
• Fractional Brownian motion with a reflecting wall
• Perturbation Theory for Fractional Brownian Motion in Presence of Absorbing Boundaries
• First Passage Times for a Tracer Particle in Single File Diffusion and Fractional Brownian Motion
• The Maximum of a Fractional Brownian Motion: Analytic Results from Perturbation Theory
• Universal first-passage statistics of aging processes
• First passage in an interval for fractional Brownian motion
• Extreme Events for Fractional Brownian Motion with Drift: Theory and Numerical Validation

Cited by in corpus (8)

• Stochastic interpolation of sparsely sampled time series via multi-point fractional Brownian bridges
• Resetting by rescaling: exact results for a diffusing particle in one-dimension
• Probability density of fractional Brownian motion and the fractional Langevin equation with absorbing walls
• First-passage area distribution and optimal fluctuations of fractional Brownian motion
• Exact joint distributions of three global characteristic times for Brownian motion
• Theory and Experiments for Disordered Elastic Manifolds, Depinning, Avalanches, and Sandpiles
• Functionals of fractional Brownian motion and the three arcsine laws
• On Approximate Representation of Fractional Brownian Motion