In a chaotic system, small changes to a parameter (a forcing strength, a stretching rate) shift long-run averages smoothly, yet every individual trajectory diverges exponentially. Practitioners therefore estimate the derivative of a long-time average, called the linear response, by running one long simulation from some starting point and averaging a carefully stabilized quantity along it. Two questions are almost never asked. Which starting points make this average converge to the true derivative? And how far from the truth is the number after $T$ steps? Algorithmic randomness is the theory of which individual points behave "typically," defined by passing every effective statistical test. It has shown that some computable points provably behave typically for ergodic averages. Sensitivity analysis has produced estimators whose integrand stays bounded on chaotic attractors. This proposal joins the two. We will construct explicit computable initial points at which the time-averaged linear-response estimator provably converges, with a computable error bound. We will then use the same lens to explain where the shadowing approach to chaotic sensitivity can go wrong.
The core idea fits in two sentences. Ni et al.'s Space-Split Sensitivity rewrites the derivative of a chaotic average as an ordinary ergodic average of a bounded function, and Galatolo, Hoyrup and Rojas proved that such averages converge effectively at explicitly constructible computable points. Composing the two gives a certified derivative at a known starting point instead of a statistical guess from an arbitrary floating-point seed. The second half asks a pointed version of an open question: when the parameter moves, does a typical point stay typical? We argue that the shadowing approach moves the point along a conjugacy, and that conjugacy carries typicality to the wrong measure.
Core Claim
Efficient Computation of Linear Response of Chaotic Attractors with One-Dimensional Unstable Manifolds supplies the estimator. It splits the response into a stable part, computed by a tangent equation with the unstable direction projected out, and an unstable part, which integration by parts along the one-dimensional unstable manifold turns into an ergodic average of a bounded integrand. The paper reports 10% relative error with 10,000 samples on the perturbed Baker's map, where finite differences need billions. Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems supplies the typicality machinery. For a computable ergodic system with a computable invariant measure, time averages of computable observables converge with a computable rate, and there exist computable "pseudorandom points" at which convergence holds. That paper explicitly leaves parameter sensitivity untouched. S3 never asks at which points its average converges, and treats its integrand classically.
Our first claim is a theorem to be proved. For uniformly hyperbolic computable maps with a one-dimensional unstable direction and a computable physical invariant measure, the S3 integrand is an almost-everywhere computable bounded observable. The physical invariant measure (often called the SRB measure) is the one that long simulations from almost all starting points sample. The integrand's ingredients are the unstable direction, its derivative along the unstable manifold, and the stable tangent solution. In uniform hyperbolicity each of these is a limit of iterated tangent vectors converging at an exponential rate set by the hyperbolicity constants, which makes them computable away from a null set of discontinuities. The effective ergodic theorem then applies to the response integrand itself. The output is a computable point $x^*$ and a computable function $T(\varepsilon)$ such that
$$\Big|\frac{1}{T}\sum_{t<T} g_\theta(F_\theta^t x^*) - \frac{d}{d\theta}\int f\,d\mu_\theta\Big| \le \varepsilon \quad \text{for all } T \ge T(\varepsilon).$$
Here $F_\theta$ is the parametrized map, $\mu_\theta$ its physical invariant measure, $f$ the observable of interest, and $g_\theta$ the S3 integrand. Discontinuities, such as the cut of the Baker's map, are handled with the almost-everywhere-decidable cell partitions of Computable randomness and betting for computable probability spaces. That paper shows that betting and tests can be carried out on such partitions in a general computable metric space without a clean binary coordinate structure.
Our second claim concerns open Gap B: does typicality survive a parameter change? Structural stability gives a conjugacy $h_\delta$, a continuous change of coordinates carrying orbits of $F_\theta$ to orbits of $F_{\theta+\delta}$. This conjugacy is exactly what shadowing trajectories follow. Applying a computable conjugacy to a typical point gives a point typical for the pushed-forward measure $(h_\delta)_*\mu_\theta$. By the conservation-of-randomness results in When does randomness come from randomness?, typicality can be transported only to that image measure. Generically, that image measure is mutually singular to $\mu_{\theta+\delta}$, because the density of the physical measure along unstable directions changes with the parameter. So the shadowed point is typical for the wrong measure. We conjecture that the resulting bias is exactly the unstable contribution S3 adds back. In algorithmic terms, a uniform test over the parametrized class $\{\mu_\theta\}$, in the sense of Algorithmic tests and randomness with respect to a class of measures, should flag shadowed points as non-random for $\mu_{\theta+\delta}$, with a randomness deficiency that grows with trajectory length.
This sits in tension with Least Squares Shadowing sensitivity analysis of chaotic limit cycle oscillations. That paper finds a shadowing trajectory that stays close to the reference orbit, which makes the problem well conditioned, and it reports accurate gradients on Lorenz-63 and an aeroelastic oscillator. We do not dispute those results. Our prediction is narrower: the shadowing bias is small when the unstable-direction density barely depends on the parameter, and clearly nonzero on systems built to make it depend, such as the perturbed Baker's map. The experiments will measure this directly.
Research Program
The theoretical work has three parts. First, we prove computability of the S3 integrand for uniformly hyperbolic maps with one-dimensional unstable direction, given computable hyperbolicity constants. Second, we derive an explicit $T(\varepsilon)$. The generic rate from the effective ergodic theorem is computable but may be astronomically loose. We will therefore also derive a rate from exponential decay of correlations, which holds for these systems and gives a usable bound. Third, we prove or refute the singularity statement for conjugacy-transported points, and compute the resulting shadowing bias in closed form on the perturbed Baker's map.
The computable-measure hypothesis is not free. Statistical properties of dynamical systems – Simulation and abstract computation exhibits computable systems whose physical measures are not computable. It also shows how to compute invariant measures as fixed points of the transfer operator, the operator that pushes densities forward one step, using Wasserstein-distance estimates and explicit Lasota–Yorke constants. We will use that construction for two purposes: to certify computability of $\mu_\theta$ on our benchmarks, and to produce independent ground truth for the response.
The computable-metric-space framing does real work in this program. The invariant measure is a point in the space of probability measures with the Wasserstein metric, which is itself a computable metric space by Computability of probability measures and Martin-Löf randomness over metric spaces. Certifying the response for a whole computable family of Lipschitz test functions $f$ therefore bounds the derivative of $\theta \mapsto \mu_\theta$ in the dual-Lipschitz norm. That is the quantity a metric-space sensitivity index such as the one in Sensitivity analysis in general metric spaces would need as an input. That paper builds Sobol-style indices for metric-valued outputs from pick-freeze U-statistics, but it assumes each model evaluation is well conditioned. We treat combining the two into a global sensitivity index of a chaotic invariant measure as a stretch goal, not a core deliverable.
The software deliverable implements S3 in interval or ball arithmetic, which carries rigorous error enclosures through every operation, rather than in double precision. It also includes a constructor for pseudorandom starting points following the effective Borel–Cantelli argument, and a finite-horizon randomness-deficiency estimator based on the $\sup_x \mathbf{m}(x)/P(x)$ characterization of Bienvenu et al. Because the a priori probability $\mathbf{m}$ is uncomputable, the estimator replaces it with compression-based upper bounds. We label it a heuristic diagnostic, not a test.
Baselines
The do-nothing reference is central finite differences of long-time averages from double-precision random seeds. This is what practitioners default to, and its failure is already documented. Ni et al. report that finite differences need billions of samples for 10% relative error on the perturbed Baker's map, and Wang, Hu and Blonigan show tangent and finite-difference derivatives blowing up on Lorenz-63. We will run it at matched wall-clock budget only to calibrate scale, not as a serious competitor.
The strongest competitor is S3 itself, run from random high-precision seeds, with error bars from batch means. This is the method our certificate wraps. It reaches 10% relative error at 10,000 samples on the perturbed Baker's map (Ni et al.). On the Smale–Williams solenoid we found no reported number on Lacuna, only a qualitative statement that errors follow Monte Carlo rates. For fairness, both arms use the same integrand code, the same arithmetic precision, and the same total number of map evaluations. Our method cannot beat it on point accuracy, because it is the same estimator. Beating it means three things. Our certified interval must contain the transfer-operator ground truth in every trial while the batch-means interval fails nominal coverage in identifiable regimes. The certified width must stay within a stated factor of the batch-means width, with a factor of 10 as the bar for practical usefulness. And the cost of constructing the point must stay comparable to the simulation itself.
For the shadowing hypothesis, the competitor is Least Squares Shadowing via the LSSODE module mentioned by Wang et al., run on identical trajectories and horizons. Two ablations isolate our key ingredients. The first keeps S3 but replaces the certified point with a random seed of equal precision. Any coverage difference then comes from typicality, not arithmetic. The second removes S3's unstable contribution, leaving a pure shadowing estimate. The gap between this ablation and full S3 is the measured shadowing bias, which we compare against our predicted closed form.
Why not just…?
Why not just run S3 from random seeds and trust the central-limit error bars? This is the real threat. On well-behaved uniformly hyperbolic toys it may produce intervals that empirically cover the truth almost always. If our coverage experiment shows batch-means intervals are already reliable and our certified bounds are much wider, then the practical contribution reduces to the theorem and the shadowing analysis, and we will say so. Two things could still separate the methods. Batch-means bars assume the seed is typical, which is precisely what fails for special seeds. On the Baker's map in particular, the doubling component in binary floating point collapses onto a fixed point after roughly the mantissa length in steps. A naive double-precision run is then not sampling the attractor at all, and its error bars are confidently wrong. The coverage experiment makes this visible.
Why not just use finite differences with a huge ensemble? Ni et al.'s billions-versus-10,000 gap on the same benchmark settles it as a primary method. It also gives no pointwise guarantee, since Galatolo, Hoyrup and Rojas note that arbitrary computable points can sit on non-convergent orbits.
Why not just use Least Squares Shadowing, which is already well conditioned? LSS is well conditioned and accurate on the systems it was tested on. But it neither certifies its error nor addresses the measure the shadow orbit samples. Our second claim predicts a specific nonzero bias on systems where the physical measure's unstable density depends on the parameter. The shadow-only ablation on the perturbed Baker's map either confirms this bias or refutes it. If the bias is negligible everywhere we test, the second claim fails and we report that.
Proposed Experiments
On the perturbed Baker's map we will compute ground-truth responses from rigorous transfer-operator fixed points, following Galatolo et al.
- We then compare four estimates against this truth over a sweep of parameters and trajectory lengths: certified-point S3, random-seed S3 in high precision, random-seed S3 in double precision, and shadow-only. We report coverage, interval width, wall-clock time, and the arithmetic precision needed to keep the certified enclosure finite. The Smale–Williams solenoid repeats the comparison on a continuous attractor. Lorenz-63 serves as a deliberate stress test outside uniform hyperbolicity. There the theorem does not apply, but the deficiency diagnostic and the shadowing-bias measurement can still be run.
Two outcomes decide the proposal. Certified intervals must cover the ground truth in every trial and stay within a usable factor of the batch-means width. The measured shadow-only bias on the Baker's map must match the predicted unstable contribution in sign and magnitude, while the deficiency diagnostic separates conjugacy-transported points from points freshly constructed for $\mu_{\theta+\delta}$. If the first outcome fails because the bounds are vacuous, the result is a negative finding about effective ergodic rates. If the second fails, the conjugacy account of shadowing error is wrong.
References
- Efficient Computation of Linear Response of Chaotic Attractors with One-Dimensional Unstable Manifolds
- Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems
- Computable randomness and betting for computable probability spaces
- When does randomness come from randomness?
- Algorithmic tests and randomness with respect to a class of measures
- Least Squares Shadowing sensitivity analysis of chaotic limit cycle oscillations
- Statistical properties of dynamical systems – Simulation and abstract computation
- Computability of probability measures and Martin-Löf randomness over metric spaces
- Sensitivity analysis in general metric spaces