Balancing fractional Brownian motion
2026-08-10 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors investigate how to balance multiple independent fractional Brownian motion paths, which are random functions with memory, focusing on how the difficulty changes depending on a parameter H between 0 and 1. They find a clear change in behavior at H = 0.5: for values less than 0.5, the discrepancy grows as a power of n, while at exactly 0.5, it stays constant, and beyond 0.5, it behaves differently with logarithmic factors. The authors also explore the geometry of solutions and provide efficient algorithms to find near-optimal balanceings. Their approach uses wavelet-based methods combined with probability theory to analyze these problems in an infinite-dimensional setting.
fractional Brownian motionHurst exponentdiscrepancy theoryGaussian processeswavelet representationphase transitionoverlap gap propertylocal minimarandomized algorithmsprobabilistic analysis
Authors
Hengrui Luo, Yiming Xu
Abstract
We study the discrepancy of balancing $n$ independent sample paths of fractional Brownian motion with Hurst exponent $H\in(0,1)$ on $[0,1]$, an infinite-dimensional analogue of balancing Gaussian vectors. We establish a phase transition at $H=1/2$: with high probability, the discrepancy is $Ω(n^{1/2-H})$ and $\mathcal O(n^{1/2-H}(\log n)^{c(H)})$, where $c(H)=H+1/2$ if $H\geq 1/2$ and $c(H)=1/2$ otherwise. At the critical exponent $H=1/2$, we show that the discrepancy is $Θ(1)$ with constant probability as $n\to\infty$. In this regime, we further characterize the geometry of the solution space by computing the expected number of local minima, establishing an overlap gap property near the existence threshold, and proving its absence at every diverging optimality threshold. We also give randomized polynomial-time algorithms that compute signings with discrepancy $\mathcal O(n^{1/2-H}\sqrt{\log n})$ for $H<1/2$, $\mathcal O((\log n)^{3/2})$ for $H=1/2$, and $\mathcal O(\sqrt{\log n})$ for $H>1/2$, with high probability. Our analysis combines a truncated balancing argument based on a wavelet representation of fractional Brownian motion with probabilistic methods.