Certified Long-Run Statistics of Nearly Deterministic Systems

Many engineering questions are about the long run: what fraction of the time a regulated room, a chaotic flow, or a noisy controlled robot spends in a bad region. The usual answer is to simulate for a long time and average. Work on computable dynamics says this can fail badly. There are one-line deterministic maps whose attractor (the set of states the system keeps visiting) can be computed, yet whose long-run visiting frequencies cannot be computed by any algorithm. For these maps, simulation averages never settle on the right answer in any predictable time. Control and verification tools mostly sidestep the issue. They either assume determinism, or they certify only finite-horizon safety under noise.

This note proposes to measure how that impossibility turns into a concrete cost once a small amount of noise is added. We apply convex "moment" relaxations to nearly deterministic systems. These are optimization problems that return guaranteed upper and lower bounds on a long-run average. We then track how the polynomial degree needed to shrink the bound interval grows as the noise level σ goes to zero. Our expectation is that the bounds never give a wrong answer. At σ = 0 the interval should stall at the full range of values the average takes over all invariant distributions, which is a computable quantity. For σ > 0 it should close at a rate set by how fast the noisy system mixes. Simulation, by contrast, gives confident but wrong estimates in exactly the regimes where the computability results say it must struggle.

Core Claim

There are two ways to describe a system's long-run behavior. One is the topological object: the set of states the system keeps revisiting. The other is the statistical object: how often it visits each part of that set. The gap between them is the gap between what can be certified by invariant sets and what is actually needed for occupation-time guarantees. How to lose at Monte Carlo proves this gap exists for the logistic family $f_a(x)=ax(1-x)$. It builds parameters where the attractor is computable but the unique physical measure is not. Statistical properties of dynamical systems – Simulation and abstract computation formalizes computability of invariant measures and shows that in some systems no invariant measure is computable at all. Both results motivate this proposal. Both are also silent on what happens once noise is added, which is the situation every real controller lives in.

The method comes from Bounding Stationary Averages of Polynomial Diffusions via Semidefinite Programming. That work bounds the long-run average $\int g\,d\pi$ of a polynomial $g$ under a polynomial stochastic system with stationary distribution $\pi$. It does so by optimizing over moment sequences that satisfy the stationarity constraints

$$\int \big(\mathcal{A}_\sigma p\big)(x)\,d\mu(x) = 0 \quad \text{for all polynomials } p \text{ of degree} \le d,$$

where $\mathcal{A}_\sigma$ is the generator at noise level $\sigma$. For a discrete-time kernel, $\mathcal{A}_\sigma p(x) = \mathbb{E}[p(X_{1})\mid X_0=x]-p(x)$. The relaxation returns an interval $[L_d(\sigma), U_d(\sigma)]$ that is guaranteed to contain $\int g\,d\pi$.

We are not proposing a new solver. The new part is the question we ask of it and the claim we make about the answer. We define the gap-closing degree

$$d^*(\sigma,\varepsilon) = \min\{d : U_d(\sigma) - L_d(\sigma) \le \varepsilon\},$$

and make two predictions.

The first is a theorem we aim to prove for compactly supported polynomial systems. At $\sigma = 0$, the constraints admit every invariant measure: Dirac masses on periodic orbits as well as the physical measure. The limit interval therefore equals the range of $\int g\,d\mu$ over all invariant $\mu$. That range is computable. So the relaxation stays sound, and it stays informative about the attractor, exactly where the physical statistic is uncomputable.

The second is an empirical scaling law. For $\sigma>0$ with a unique stationary measure, $d^*(\sigma,\varepsilon)$ should track the inverse spectral gap of the noisy transfer operator. It should grow mildly for stochastically stable parameters and sharply near parameters where the physical measure is fragile. If this holds, "statistical non-computability at σ = 0" becomes a measurable certificate cost at σ > 0.

Research Program

The theoretical part has three pieces. First, we state and prove the σ = 0 limit characterization for polynomial maps on compact semialgebraic sets, where the standard compactness condition for these relaxations applies. Second, we prove convergence $U_d-L_d\to 0$ for fixed σ > 0 under uniqueness of the stationary measure. Third, we attempt an upper bound on $d^*$ in terms of the mixing rate. That third piece is the hardest, and failing to get it would not sink the program, because the empirical scaling can still be measured.

We also address the computable-analysis literature's open question of whether bounding hierarchies can circumvent non-computability. Our answer is a qualified yes: they can circumvent it in the sense of returning sound intervals, but not in the sense of pinning down the physical measure. This is consistent with Gamarnik's undecidability results. That paper shows that exact stationary probabilities are undecidable even when a Lyapunov certificate proves stability, while approximation is possible given a geometric Lyapunov function. Our σ > 0 regime is the approximable side of that line, and our σ = 0 plateau is the honest face of the other side.

On the systems side, we turn the bounds into occupation-safety certificates. The occupation probability of an unsafe set $S$ is the long-run fraction of time spent in $S$. To bound it, we minimize $\int q\,d\mu$ over polynomials $q$ that dominate the indicator of $S$, with the domination condition certified by sums of squares. This targets the gap the file identifies in stochastic barrier work. Stochastic control barrier functions, data-driven SCBFs and scenario-based barrier certificates all certify finite-horizon reach-avoid probabilities. Sets-only tools like Fossil 2.0 are restricted to deterministic models. The SOS completeness result over unbounded domains shows that deterministic barrier synthesis can be made complete. We ask what the stochastic long-run analogue costs.

The testbeds need to be exactly polynomial and to stay in a compact set. For the logistic family we therefore use random-parameter noise, $x_{n+1}=a_n x_n(1-x_n)$ with $a_n$ uniform on $[a-\sigma,a+\sigma]\subset(0,4]$. This keeps $[0,1]$ invariant and makes the kernel's moments polynomial. It is also the standard perturbation in stochastic-stability studies.

We cannot numerically realize the diagonalized non-computable parameters of How to lose at Monte Carlo. Instead we use fragile proxies:

  • the period-doubling accumulation point;
  • parameters just outside periodic windows, where the physical measure jumps;
  • well-behaved chaotic parameters as controls.

We state plainly that these are proxies, not instances of non-computability.

For higher dimension we use the stochastic Lorenz system with additive noise. Its polynomial drift and confining Lyapunov function fit the setting of Bounding Stationary Averages of Polynomial Diffusions via Semidefinite Programming directly. We also use a coupled logistic lattice of dimension 2 to 6, to study scaling with dimension. Finally, we use a closed-loop version of the synthetic nonlinear SDE benchmark from Data-Driven Learning of Safety-Critical Control with Stochastic Control Barrier Functions, with a polynomial feedback law. This last case ties the study to a system the control community already uses.

Baselines

The naive reference point is long Monte Carlo averaging with ordinary confidence intervals. We run it with a simulation budget matched in wall-clock time to the relaxation solve at each degree, and also at 10× that budget. On the logistic testbed, ground truth comes from a fine Ulam discretization, described below, with a certified error bound. The claim to test is not that Monte Carlo is slower. It is that its 95% intervals exclude the true value at a measurably elevated rate near the fragile parameters, while the certified interval contains it by construction. Beating this baseline means a significantly higher false-confidence rate for Monte Carlo at fragile parameters than at control parameters, with zero soundness violations for the relaxation.

The strongest existing competitor for rigorous long-horizon guarantees is scenario convex programming for stochastic barrier certificates, from Data-driven Safety Verification of Stochastic Systems via Barrier Certificates. On the room temperature benchmark it reports a safety probability of at least 0.9 at confidence 0.99, using N = 1,018,779 samples, for a finite horizon. We rerun it on the room temperature model and on our polynomial testbeds, under the same noise model and the same computational budget. We then compare its finite-horizon bound, extrapolated by union bound to the horizon at which it becomes vacuous, against our model-based occupation bound. Beating it means a non-vacuous infinite-horizon occupation bound that is tighter than the extrapolated scenario bound at every horizon beyond the mixing time, using zero trajectory samples. The comparison is not symmetric: our method needs the polynomial model and the scenario method does not. We report this openly.

For closed-loop control, the relevant reference is DDSCBF. On the synthetic nonlinear SDE it reports 84.3% safety success, against 86.8% for a known-noise SCBF and 77.3% for a deterministic CBF, all with diffusion $b(x_2)=0.1x_2$. On the inverted pendulum it reports 91%, against 0% for the deterministic CBF. These are finite-horizon success rates, not long-run occupation fractions, so we do not claim to beat them on their own metric. Instead we certify the long-run unsafe-occupation fraction of the closed loop they induce, and check it against very long simulations.

The key ablation sets σ = 0. If the relaxation keeps closing to a point at σ = 0 on fragile parameters, our limit characterization is wrong. If it plateaus at the invariant-measure range, the noise is doing the work we claim. For numerical bounds from the SDP method itself, we found no reported result on Lacuna for stationary-average bound values, so every relaxation number is produced here.

Why not just…?

Why not just run longer Monte Carlo? In well-mixing regimes it will work, and our experiments will show that. Near fragile parameters, however, How to lose at Monte Carlo proves there is no algorithmically predictable convergence time at σ = 0. At small σ, we expect transient lengths to blow up in ways that sample-variance confidence intervals cannot detect. The false-confidence experiment settles this directly. If Monte Carlo intervals stay calibrated at fragile parameters, our practical motivation weakens and we will report that.

Why not just use the existing SDP moment method? We do use it. The honest objection is whether anything is left to contribute. The existing paper already acknowledges non-guaranteed convergence and ill-conditioning. What it does not provide is three things: the σ → 0 characterization, the link between certificate cost and mixing, or occupation-safety certificates for closed loops. If the ill-conditioning its authors report makes high-degree solves unreliable before $d^*$ is reached, that is itself a finding about the zero-noise limit. We would then test alternative polynomial bases, such as Chebyshev instead of monomials, before concluding.

Why not just discretize into a finite Markov chain? In one dimension this is a real threat. Ulam-style discretization of the noisy logistic map, with error control, will likely beat the relaxation, and we use it as ground truth for that reason. Data-driven Abstractions via Adaptive Refinements and a Kantorovich Metric assumes exactly known transition probabilities, and its authors note that grid size is exponential in dimension. The coupled-lattice experiment tests where the crossover lies. We run the adaptive abstraction and the relaxation at matched solve time for lattice dimensions 2 to 6, and report which gives the tighter certified interval. If abstraction wins through dimension 6, we would reposition the relaxation as useful only beyond that point.

Why not just treat noise as a bounded disturbance and use robust barriers? Worst-case analysis certifies set invariance, not occupation frequencies. With unbounded Gaussian noise its bound on long-run unsafe occupation is trivially 1. The file also records the cost of worst-case barrier formulations under actuator limits: SRCBFs reach only 25% safe probability against 65% for SCBFs on cruise control in Safety-Critical Control of Stochastic Systems using Stochastic Control Barrier Functions. We include a robust-invariance certificate on the Lorenz and closed-loop testbeds only to show this vacuity concretely.

Proposed Experiments

The first decisive check is the σ = 0 plateau on the logistic family. At parameters with a known attracting periodic orbit and at chaotic parameters, we compute $U_d-L_d$ for degrees up to the numerical limit. We compare the plateau against the range spanned by Dirac measures on computed periodic orbits and by the Ulam estimate of the physical measure. A plateau matching the invariant-measure range confirms the characterization.

The second check is the scaling law. For σ on a logarithmic grid from 0.1 down to 1e-4, we measure $d^*(\sigma,\varepsilon)$ at ε = 1e-3 for observables $x$, $x^2$ and a polynomial dominating an interval indicator. We regress $d^*$ against the inverse spectral gap of the Ulam transfer matrix. We predict a monotone relationship that holds across both fragile and control parameters. A failure of this relationship would falsify the central empirical claim.

The third check is the false-confidence comparison with Monte Carlo at matched budgets, described in the Baselines section.

The fourth check covers dimension and closed-loop behavior. We run the coupled-lattice crossover against adaptive abstraction. We compute occupation certificates for stochastic Lorenz and for the polynomial closed-loop SDE, validated against simulations of at least 1e8 steps. We compare against the scenario barrier method at matched compute. Throughout, we report solve times, condition numbers of the moment matrices, and every soundness violation, since a single violation would indicate a numerical, not conceptual, failure that must be diagnosed before any claim stands.