bayesian_filtering_arxiv_version.pdf
Many processes across the natural sciences admit as a common description an overdamped Brownian dynamics on a free energy landscape. Examples include protein conformational changes,[1 ] ion channel gating,[2 ] and the El Niño–Southern Oscillation (ENSO).[3 , 4 ] The shape of the landscape encodes the physics of each system, with barrier heights defining transition rates and well depths defining equilibrium populations.
Yet this landscape lives in a latent space, and what is measured is not the latent state itself but a function of it, such as fluorescence intensity,[5 ] ionic conductance,[2 ] or sea-level pressure differences.[6 ] This mapping, the emission function, is generally non-linear and non-invertible. The task is thus to recover the free energy landscape and the emission function jointly, from observed trajectories alone and without assuming parametric forms for either. We will address this problem by Bayesian inference.
Making this inference tractable has so far required additional assumptions on the latent space or the emission function. The most common is the discrete-state hidden Markov model (HMM).[7 , 8 ] For continuous systems, like proteins probed by single-molecule FRET,9–12 discretization coarsens the shape of the landscape. Few states collapse complex transition paths into single rate constants,13,14 whereas many states turn inference into an ill-posed inverse problem. Non-parametric HMMs15 regularize the number of states, but not the smoothness of the landscape, which is the natural prior but difficult to apply on a discrete graph of states.
Continuous diffusion models, in contrast, preserve the landscape but assume the latent coordinate is observed directly, as in single-molecule pulling,16 position-dependent diffusion models,17 and econometric diffusion estimators.18 Bayesian filtering19 lifts this assumption but is analytically solvable only for the quadratic landscape of the Kalman–Bucy filter.20 Extended and unscented Kalman filters21,22 handle non-linear dynamics but force the latent density to be Gaussian. Non-parametric landscapes have been inferred jointly with the latent state for single-molecule FRET.23–25 The non-linear dynamics and the high-dimensional representation of the latent density make such inference costly. Particle MCMC estimates the exact likelihood by Monte Carlo,26,27 whereas simulation-based inference replaces it with a neural surrogate.28,29
All of these approaches assume a fully specified or parametric emission function. Jointly inferring the emission allows analysis of systems without a closed-form emission, such as the mapping from a latent climate regime to atmospheric pressures. It also avoids imposing physical laws that are only approximate in practice, such as the 1 / r 6 1/r^{6} 1/ r 6 law of FRET efficiency,30 given linker flexibility and fluorophore orientation. Both gains come at a further computational cost.
With non-linear dynamics and joint landscape and emission inference, the filtering likelihood becomes computationally costly to evaluate. Worse, its recursion is sequential: each step conditions on the previous one, so runtime grows with trajectory length whatever the parallel resources available. Parallelizing this recursion requires restructuring it. Parallel prefix scans do so by recasting it as an associative operation,31,32 but require prediction and update to compose in closed form, which holds exactly for linear-Gaussian models or transition densities expressible as dense matrices, and only approximately otherwise, through iterated Gaussian linearization.33 A parallel-in-time (PinT) particle smoother exists,34 though it draws the particles of each time step independently, resulting in error growing faster with trajectory length than that of sequential smoothers. Parallel fixed-point solvers sidestep associativity altogether, evaluating general non-linear recursions, MCMC chains included, by Newton or Picard iteration over the whole trajectory.35–39
Under filter stability,40 filters started from different initial densities converge as observations accumulate, leaving distant time points only weakly coupled, the regime in which PinT methods excel.41,42 Yet PinT iteration has not been combined with filter stability to parallelize Bayesian filtering.
Here we infer the landscape and the emission function jointly and non-parametrically, under a prior that imposes a controlled level of smoothness. The model likelihood is computed by Bayesian filtering, which propagates the non-parametric latent density through the Fokker–Planck equation of overdamped Brownian dynamics. We remove the sequential bottleneck of this filtering with a parallel-in-time algorithm that splits the trajectory into short blocks, filters them in parallel, and iterates until it reproduces exactly the output of the sequential filter. For the model studied here, filter stability40 on its compact latent domain makes the iteration count independent of the number of observations N N N . The span of a likelihood evaluation, its runtime given unlimited parallel resources, therefore falls from O ( N ) O(N) O ( N ) to O ( 1 ) O(1) O ( 1 ) , at the cost of a small multiple of total work. Because the algorithm treats the filter as a black box, it requires neither the associative reformulation of scan methods nor the Jacobians of fixed-point solvers, and applies to other hidden Markov models, though not necessarily with the same span.
Results
Non-parametric hidden Brownian dynamics model
Figure 1. a INPUT; observed y ( t ) y(t) y ( t ) ; Joint Bayesian Inference; P ( Δ G , f , x ( ⋅ ) ∣ y ) P(\Delta G, f, x(\cdot)\mid y) P ( Δ G , f , x ( ⋅ ) ∣ y ) ; OUTPUTS; latent state x ( t ) x(t) x ( t ) ; density; landscape G ( x ) G(x) G ( x ) ; posterior mean; 95% CI; Δ G \Delta G Δ G (RT); emission y = f ( x ) y=f(x) y = f ( x ) ; observable y y y ; latent coordinate x x x . b 1 Sequential filtering; N = 64 N=64 N = 64 steps, strictly one after another; 2 Folded into B B B blocks; block 1; block 2; block 3; block 16; 3 Parallel-in-time filtering; iteration k = 1 k=1 k = 1 ; iteration k = 2 k=2 k = 2 ; iteration k = 3 k=3 k = 3 ; Filtering 16 blocks in parallel; Converged (equivalent to sequential); Unconverged; exact π 0 \pi_0 π 0 ; trial; converged.
Figure 1 (PDF p. 5). Joint inference of landscape, emission and latent state, and parallel-in-time evaluation of the likelihood. (a) Inference goal: given observable trajectories y ( t ) y(t) y ( t ) (Input panel, teal), we jointly infer the free-energy landscape G ( x ) G(x) G ( x ) , the emission function f f f mapping latent space coordinate x x x to observable y = f ( x ) y=f(x) y = f ( x ) , and the latent state trajectory x ( t ) x(t) x ( t ) (Outputs panel), all three in the form of a Bayesian posterior distribution. (Synthetic data shown). (b) Parallel-in-time (PinT) evaluation of the filtering likelihood. Sequential filtering (1) processes the N N N steps in order. Folding the trajectory into B B B blocks (2) exposes parallelism, but each block needs the final density of its predecessor. PinT filtering (3) starts the first block from the exact initial density π 0 \pi_0 π 0 and every other block from a trial density, filters all blocks in parallel, and passes boundary densities on at each iteration until they converge.
We model the latent process as overdamped Brownian dynamics on a free-energy landscape G ( x ) G(x) G ( x ) , with x x x the latent space coordinate, observed through a non-linear emission function f ( x ) f(x) f ( x ) that need not be injective (Figure 1a). Here we focus on a one-dimensional latent coordinate, obeying d X t = − D k B T ∇ G ( X t ) d t + 2 D d W t dX_t=-\frac{D}{k_{\mathrm{B}}T}\nabla G(X_t)\,\mathrm{d}t+\sqrt{2D}\,\mathrm{d}W_t d X t = − k B T D ∇ G ( X t ) d t + 2 D d W t . Observations are drawn conditionally independently given the latent trajectory, from a user-specified distribution whose location parameter is controlled by the emission, Y t k ∣ X t k ∼ p o b s ( ⋅ ∣ f ( X t k ) ) Y_{t_k}\mid X_{t_k}\sim p_{\mathrm{obs}}(\cdot\mid f(X_{t_k})) Y t k ∣ X t k ∼ p obs ( ⋅ ∣ f ( X t k )) . The dynamics are thus assumed reversible and unforced, with a time-independent landscape and a position- and time-independent diffusion coefficient D D D . Within these assumptions, G G G and f f f are inferred non-parametrically, with a prior on their wavelet coefficients expansion targeting a Besov smoothness class (Methods).43
The likelihood is evaluated by Bayesian filtering,19, 22, 44 which alternates prediction, propagating the latent density by the Fokker–Planck equation, and update, conditioning it on the new observation. The generator of the Fokker–Planck equation is projected onto a basis and diagonalized, yielding the propagator. The model likelihood is the product of the normalization factor of the update steps ∏ k ∫ p o b s ( y t k ∣ f ( x ) ) p ( x ∣ y t 1 : t k − 1 ) d x \prod_k\int p_{\mathrm{obs}}(y_{t_k}\mid f(x))p(x\mid y_{t_1:t_{k-1}})\,\mathrm{d}x ∏ k ∫ p obs ( y t k ∣ f ( x )) p ( x ∣ y t 1 : t k − 1 ) d x .
Non-injective emissions give rise to local maxima in the posterior, as emissions of different preimage multiplicity are separated by regions of low likelihood. Our automated inference protocol therefore samples a variety of candidate emission functions of different preimage multiplicities, takes each to their local maximum of the posterior, and selects the top candidate for posterior sampling (Methods). The method is implemented in PlanX, an open-source, GPU-accelerated Python package built on JAX,45 whose filtering model can be embedded within larger Bayesian models.
To parallelize filtering, the sequential trajectory (Figure 1b, panel 1) is split into B B B blocks of L L L time steps that are filtered concurrently (panels 2–3). Each block needs as its initial density the final density of its predecessor, which is not available a priori . The first block therefore starts from the exact initial density π 0 \pi_0 π 0 , and all others from a trial density, here p e q p_{\mathrm{eq}} p eq for both. Each iteration filters all blocks in parallel, then hands the final density of each block to its successor, until these block-boundary densities stop changing (Methods). For our model, the number of iterations is set by how quickly the filter forgets an incorrect initial density, not by the trajectory length. The wall-clock time of a likelihood evaluation therefore does not grow with the number of observations, at the price of filtering each block a few times over.
Method validation
We validated the method on synthetic trajectories generated from known landscapes and emission functions (Figure 2 a and Figure 2 b). As a particular challenge, both emissions are non-injective, a single observation being consistent with up to two latent positions in (a) and three in (b), and both landscapes contain fine structure within their wells. The data were limited to 32 trajectories of two to ten transitions each, with observation noise narrow (σ = 0.25 \sigma= 0.25 σ = 0.25 ) compared to the emission range (− 5 -5 − 5 to 15), so that any ambiguity in the latent state arises from non-injectivity rather than noise. Inference followed the protocol of the application cases, without knowledge of the ground truth except for the diffusion coefficient D = 1 D = 1 D = 1 , which only sets the gauge of the latent coordinate (Methods). The posterior recovers the landscape and the emission quite accurately, including the emission degeneracies and the fine structure of the landscape, with the ground truth well within its credible intervals.
Figure 2. Inference on synthetic data and latent ambiguity resolution. (a), (b) Inferred posterior for the landscape (top) and emission function (bottom) from synthetic trajectories, shown against the ground truth (orange dashed line). The posterior mean (solid blue line) is shown alongside the interquartile range (darker blue band) and the 95% credible interval (lighter blue band) quantifying posterior uncertainty. (c) Filtered latent density for a trajectory of system (a), as a function of time (x x x -axis) and latent coordinate (y y y -axis). The latent density is shown as highest-density-region (HDR) level in shades of blue (darker is more probable), with the true latent trajectory superimposed (orange line). The observed value y y y at each step is shown in the plot below (green line).
Recovering a landscape despite non-injective emissions requires tracking the latent state through the resulting ambiguities in localization (Figure 2 c, one trajectory of system (a)). The emission of (a) is an inverted “V”, its two branches spanning similar ranges of the observable, so that a single observation cannot resolve on which side of the peak the system is. When the latent trajectory reaches the peak, around time step 745, the observations become compatible with relaxation into either well, and the filtered density accordingly splits into two modes, at − 4 -4 − 4 and 4 4 4 , until later observations fall outside the range of one branch and resolve the ambiguity. This example shows the advantage of a non-parametric latent density over established Gaussian-latent filters, such as the extended or unscented Kalman filter,21 which must represent the latent state by a single mode. Every subsequent observation would then be evaluated against an incorrect latent, biasing the likelihood and thus the inferred landscape and emission.
Scaling and benchmark
Accurate inference of this kind requires many thousands of likelihood-and-gradient evaluations, so its practicality rests on the speed of each evaluation. We verify empirically the two properties of our PinT filter proven in Supplementary Information S1, exactness at convergence and, for our model, O ( 1 ) O(1) O ( 1 ) span, then measure its throughput against the sequential filter and on multiple GPUs.
Figure 7 (PDF p. 8).
We computed the model log-likelihood with both the sequential filter and PinT filter on 14 test systems, at parameters both far from and near the high-density region of the posterior (Methods). The relative error of the PinT log-likelihood, compared to sequential, is typically around 10 − 9 10^{-9} 1 0 − 9 , and always well below our target of 10 − 6 10^{-6} 1 0 − 6 , with no increase with trajectory length, no systematic difference between systems, and only a slight increase with GPU count (Figure 3 a and Supplementary Information S3). Our algorithm is therefore numerically equivalent to the sequential filter, to within single-precision round-off.
Figure 3. Correctness, speed-up and scaling of PinT filtering. (a) Cumulative distribution of the relative error of the PinT log-likelihood against the sequential filter, for 1 to 4 GPUs (colors), across 14 test systems and trajectory lengths from 400 to 168k time points (Methods). The dashed line marks the accuracy target of 10 − 6 10^{-6} 1 0 − 6 . (b) Throughput, in likelihood-and-gradient evaluations per second within the Hamiltonian Monte Carlo sampler, of the sequential and PinT filters on a single GPU, with the PinT speed-up above each pair of bars. Error bars show the standard deviation across replicate runs. (c) Strong scaling: throughput as a function of GPU count, for five trajectory lengths (labeled at right), with ideal linear scaling dashed. Replicate-to-replicate variation is below 1%, so error bars are omitted. (d) Parallel efficiency, the speed-up over a single GPU divided by the GPU count, as a function of trajectory length and GPU count, with the 70, 80 and 90% iso-efficiency contours in white. (e) Weak scaling: throughput as a function of GPU count, for fixed workloads of 1k to 54k time points per GPU (vertical axis broken), with ideal weak scaling dashed. Error bars show 95% confidence intervals from the inter-replicate variance. (f) Weak-scaling efficiency E ( n G P U ) E(n_{\mathrm{GPU}}) E ( n GPU ) , the throughput with n G P U n_{\mathrm{GPU}} n GPU GPUs and an n G P U n_{\mathrm{GPU}} n GPU -fold workload relative to a single GPU, as a function of GPU count, for a range of workloads per GPU (color scale). Error bars as in (e).
Near the maximum a posteriori estimate, the iteration count is constant over close to three orders of magnitude of trajectory length, from hundreds to hundreds of thousands of time points, showing a constant span empirically (Supplementary Information S3). The iteration count depends on how quickly the filter forgets its initial condition, a property of the landscape and emission function that varies between systems. Since the iteration count, here 2 to 4, is also the factor by which total work exceeds that of the sequential filter, the speed-ups below cost a corresponding increase in total computation. Despite this, on a single GPU, PinT filtering evaluates the likelihood and gradient 9 times faster than the sequential filter at 1k time points, and 26.8 times faster at 5k (Figure 3 b). This seemingly paradoxical speed-up results from better use of within-GPU parallelism. The chain of matrix-vector products in the sequential filter is a thin, latency-bound workload, whereas our algorithm uses dense matrix multiplications that use compute and memory bandwidth more efficiently.
Strong scaling, the speed-up from adding GPUs at fixed trajectory length (Figure 3 c), is limited by an unparallelizable fixed cost of about 4 ms per evaluation, dominated by operator diagonalization, which accounts for more than half of single-GPU runtime below about 6k time points (Supplementary Information S3). The 4k-point trajectory accordingly plateaus beyond two GPUs, the 50k-point trajectory speeds up sublinearly up to eight, and trajectories of 200k time points and more scale linearly up to eight. Ninety percent parallel efficiency is reached at approximately 60k and 100k time points on two and three GPUs, and above 200k on eight (Figure 3 d), lengths typical of single-molecule recordings. Weak scaling, the ability to maintain a constant runtime as trajectory length and GPU count grow together, is shown in Figure 3 e. Performance drops mainly from one to two GPUs, at the onset of inter-GPU communication. Each block exchanges only 3 to 6 kB with its neighbors (Methods), so this cost is latency-dominated, at about 0.4 ms per evaluation. The weak-scaling efficiency stays above 0.90 for workloads above 1k time points per GPU, and approaches 0.98 above 10k (Figure 3 f). A trajectory spread over enough GPUs to keep at least 10k time points on each thus scales almost ideally, for instance on two GPUs for the 24k-point optical tweezer recording analyzed below. Tens to low hundreds of likelihood-and-gradient evaluations per second are therefore readily achievable, even for long trajectories of several hundred thousand time points. These figures are deliberately conservative, as they were obtained on five-year-old GPUs with inter-GPU transfers staged through host memory (Methods).
Application examples
Next, we applied our method to three representative systems from different fields, a single-molecule optical tweezer trajectory, a century-long climate index, and a daily financial index.
The first application is a single-protein nano-aperture optical tweezer recording of bovine serum albumin (BSA),46 in which the transmission of the trapping laser reports on the conformational state of the protein. The recovered landscape has two steep-walled wells of uncertain relative depth (Figure 4 a), with an inter-well relaxation time (325 ms) much slower than all others (≤ 20.8 \leq20.8 ≤ 20.8 ms; Figure 4 d), justifying a two-state description. The free energy difference between the wells is 0.84 k B T k_{\mathrm{B}}T k B T (CI95 0.17 to 1.69) and the barrier height 4.03 k B T k_{\mathrm{B}}T k B T (CI95 3.58 to 4.68). The original non-Bayesian analysis46 reported a free energy difference near 1.5 k B T k_{\mathrm{B}}T k B T and a barrier around 3 k B T k_{\mathrm{B}}T k B T .
Figure 4. Landscape, emission and kinetics of a single BSA molecule in a nano-aperture optical tweezer. (a) Posterior distribution of the landscape (top, in k B T k_{\mathrm{B}}T k B T ) and the emission function (bottom, in arbitrary units equal to 1/30 volt; see Methods), showing the posterior mean (solid blue line), the interquartile range (IQR, dark band) and the 95 percent credible interval (CI95, light band). The free energy difference between the wells Δ G \Delta G Δ G and the barrier height Δ G ‡ \Delta G^{\ddagger} Δ G ‡ are marked by arrows. Diffusion D = 5 ⋅ 10 − 5 D = 5 \cdot10^{-5} D = 5 ⋅ 1 0 − 5 . (b) Autocorrelation of the observable, as observed (dashed red line) and under the posterior predictive distribution (dark blue line, with IQR and CI95 as shaded bands). Lag is given in time steps (bottom axis) and in milliseconds (top axis). (c) Standardized pre-update residuals, i.e., the difference between each observed value and its one-step-ahead predictive mean, divided by the predictive standard deviation. The observation distribution is a mixture of 99 percent Gaussian and 1 percent uniform; the Gaussian component alone is drawn as a solid dark blue line and the full mixture as a dashed orange line. (d) The five slowest relaxation timescales of the inferred landscape, in milliseconds, as a box plot. The posterior median (dark blue line), IQR (box) and CI95 (vertical line) are shown with the median printed above each.
The inferred emission function is non-injective, rising at the barrier between wells, so that, as in our most challenging validation example (Figure 2 a), a given transmission value is compatible with latent positions on both sides of the barrier. Unlike FRET efficiency, which follows from the donor–acceptor distance through a known law, optical transmission reports on the polarizability of the protein, a function of its conformation which is well-defined, but whose functional form is system-dependent and difficult to specify. Such non-injectivity may therefore be frequent in this type of experiment, where it could prevent interpretation by other methods assuming a monotonic emission. Posterior predictive checks reveal excess autocorrelation at 20 to 135 ms of lag (Figure 4 b), pointing to a slow degree of freedom hidden by the one-dimensional projection, such as conformational substates within the wells, or to apparatus drift (Supplementary Information S6.4). The one-step-ahead residuals also show ten isolated jumps of 4 to 5 standard deviations (Figure 4 c), which the observation noise model absorbs (Methods). Both of these findings suggest partial model misspecification, though the inferred landscape and emission are likely still reliable.
The second application is the El Niño–Southern Oscillation (ENSO), the dominant mode of interannual climate variability. The observable is the monthly Southern Oscillation Index (SOI) from 1866 to 2025, the normalized sea-level pressure difference between Tahiti and Darwin, which measures the atmospheric side of the ENSO. The inferred landscape is broadly harmonic and the emission linear: an Ornstein–Uhlenbeck model fitted to the posterior mean stays within the 95% credible interval throughout (Figure 5 a, dashed lines). Our non-parametric approach thus identified this simpler model from the data rather than assuming it.
Figure 5. Landscape, emission and external validation of the ENSO latent state. (a) Posterior for the landscape (top) and for the emission function (bottom), showing the posterior mean (solid blue line), the interquartile range (IQR, dark band) and the 95 percent credible interval (CI95, light band). The dashed orange line is a fitted Ornstein–Uhlenbeck model, harmonic in the landscape and linear in the emission. Diffusion D = 0.35 D = 0.35 D = 0.35 . (b) Smoothed latent coordinate (posterior mean, with CI95 as vertical bars) against the Oceanic Niño Index (ONI), a sea surface temperature index over the Niño 3.4 region that defines the ENSO phase (color). Dashed vertical lines mark the standard NOAA thresholds at ± 0.5 \pm0.5 ± 0.5 K. (c) Autocorrelation of the observable, as observed (dashed red line) and under the posterior predictive (dark blue line, with IQR and CI95 as shaded bands).
To test whether the inferred latent coordinate tracks the ENSO state, we compare it with the Oceanic Niño Index (ONI), which was not used during inference (Figure 5 b). The ONI, a sea surface temperature anomaly in the Pacific, measures the oceanic side of ENSO and defines its El Niño and La Niña phases. The smoothed latent coordinate correlates strongly with the ONI (Spearman ρ s = − 0.865 \rho_s = -0.865 ρ s = − 0.865 ) and classifies the NOAA phases with a ROC AUC of 0.93 for El Niño and 0.94 for La Niña. Inferred from atmospheric pressure alone, the latent coordinate thus captures the full ENSO state, oceanic as well as atmospheric.
The posterior predictive autocorrelation of the observable matches the observed one over most lags, including the sharp drop from lag zero to one that measures the observation noise (Figure 5 c). The exception is a negative lobe between 14 and 25 months of lag, implying a period of roughly 30 to 38 months. Reversible dynamics cannot produce a negative autocorrelation at any lag, so this lobe reveals an oscillatory component outside the model class, most likely the quasi-biennial component of ENSO.47
Figure 1 (PDF p. 14).
The third system is financial market volatility, observed through the logarithm of the CBOE Volatility Index (logVIX), recorded daily from 1990 to 2026. The inferred landscape has two wells, a low- and a high-volatility regime holding 74 and 26 percent of the equilibrium population, clearly separated by a substantial barrier (Figure 6 a). The emission has one rising branch on each side of the barrier, so that the same logVIX value can arise in either regime (Figure 6 a). The regimes are thus distinguished by the temporal pattern of fluctuations, which the filter tracks through the latent state, rather than by the level of logVIX alone.
Figure 6. Two volatility regimes in the logVIX record, recovered from a single Brownian dynamics. (a) Posterior for the landscape (top) and for the emission function (bottom), showing the posterior mean (solid line), the interquartile range (IQR, darker band) and the 95 percent credible interval (CI95, lighter band). The dashed vertical line marks the barrier top separating the low-volatility (blue) and high-volatility (red) regimes. Diffusion D = 0.02 D = 0.02 D = 0.02 . (b) Smoothed posterior mean of the latent coordinate over time. The dashed horizontal line marks the barrier top, and the band between (b) and (c) shows the regime occupied at each time, labeled where a period corresponds to a known episode. (c) Model surprise over time: measured as the Kullback–Leibler divergence between the predicted and the filtered latent density at each step, sharing its time axis with (b). The dashed horizontal line is the flagging threshold, set at the 95th percentile of that divergence over the whole series. Flagged dates are labeled with the corresponding market event where one is clearly identifiable. (d), (e) Landscape (top) and emission function (bottom) of the low- and high-volatility halves of (a), the landscape re-referenced to the minimum of each well, with posterior mean and CI95. Panel titles give the equilibrium weight of each regime. Dashed lines show three classical volatility models, log Ornstein–Uhlenbeck, Heston and 3/2, each fitted to the corresponding half. (f), (g) Distribution of the observable within the low- and high-volatility regime respectively, as observed (histogram) and under the posterior predictive (solid line, with CI95 as shaded band). Observations are assigned to a regime by the side of the barrier on which the smoothed latent state lies.
Remarkably, the smoothed latent trajectory shows abrupt regime switches, separated by long stretches, often years, within a single well (Figure 6 b). High-volatility periods align with episodes of prolonged market stress, from the Asian, Russian and dot-com crises of the late 1990s to the 2007 subprime crisis and the COVID-19 pandemic. Brief volatility jumps lasting days are flagged by a Kullback–Leibler (KL) surprise metric, the divergence between the predicted and filtered latent densities, which is large when an observation is unlikely under the model (Figure 6 c). The largest surprises, over 4 days, coincide with identifiable shocks such as the 2010 Flash Crash or “Liberation day” tariffs, though some correspond to no identifiable event. They occur in both regimes and only some accompany a regime switch, suggesting that short-lived shocks and persistent regime switches are distinct phenomena.
We fitted three classical volatility models, the log Ornstein–Uhlenbeck, Heston and 3/2 models, 48 to each well (Figure 6 d,Figure 6 e). All three stay close to the credible interval in the high-volatility regime, but none reproduces local features such as the shoulder in the low-volatility well, nor has any notion of regime switching. Markov-switching models49 introduce such switching as explicit jumps between separate regimes. In our model, by contrast, both regimes and the switches between them emerge from a single Brownian dynamics on the inferred landscape, which also reproduces the observed logVIX distribution within each regime, including their overlap and the heavier tail of the high-volatility regime (Figure 6 f,Figure 6 g).
Discussion
We have developed a Bayesian method to infer the underlying free energy landscape and emission function jointly and non-parametrically from trajectories of a single observable. We have tested the method on three representative systems from different fields such as protein dynamics, climate science and finance. We have further demonstrated that our method can evaluate the model likelihood for trajectories of hundreds of thousands of points, without approximations such as particle filters, linearization or a discretized latent state, so that the resolution of the inferred landscape and emission is limited only by the data.
Several features distinguish our method from other approaches, each with practical consequences. First, the emission is inferred rather than specified, and may be non-injective, with several latent states producing the same observed value. Boltzmann inversion, by contrast, assumes an identity emission, and Gaussian-latent filters such as the extended Kalman filter21,22 cannot represent the multimodal latent density that non-injectivity creates. In contrast, our method can be used for systems for which the emission functional form is not known a priori , such as the mapping between transmittance and protein conformation in our optical tweezer application, which moreover was shown to be non-injective. In the financial market volatility example, non-injectivity is likewise what allows two volatility regimes to emerge.
Second, the landscape is non-parametric and its shape is constrained only by a smoothness prior. This contrasts with fixed-form landscapes, such as the harmonic potential of the Ornstein–Uhlenbeck process,50 and with parametric landscapes, whose number of wells is fixed and only their depths and barriers adjusted.51 Using our method, the suitability of a simpler model is therefore a result supported by data, not an a priori assumption. Our ENSO application from climate science illustrated this, with our posterior validating the use of a simpler quadratic-linear model. In our logVIX application, in contrast, we showed that classical volatility models are severe approximations, and a two-regime model better describe the data.
Third, our model likelihood is exact and explicitly computed, rather than replaced by a surrogate as in simulation-based inference.28,29 As a consequence, when the true process is not an overdamped Brownian dynamics, i.e. , when the model is misspecified, the posterior concentrates asymptotically on the overdamped Brownian dynamics closest to the data in Kullback–Leibler divergence.52 Under mild misspecification, the recovered landscape and emission are thus still an informative, albeit inexact, model of the true process, a guarantee of robustness that surrogate likelihoods do not generally share. Further, misspecification is straightforward to detect, since the observable and statistics predicted under the model can be directly compared to the data. These checks also make it possible to identify the type of misspecification, such as a hidden slow degree of freedom, external forcing, or non-Brownian jumps, all three demonstrated in our applications.
Finally, our parallel-in-time algorithm makes our likelihood computationally practical to evaluate. Already faster than sequential filtering on a single GPU, it scales well when using multiple GPUs. Without our algorithm, inference on the optical tweezer application would have been impractically slow, and our other applications would require fivefold more runtime. Unlike parallel prefix scans,31,32 the algorithm requires no closed-form composition of prediction and update. It therefore generalizes beyond our model, to hidden Markov models whose filter propagates a probability density, discrete-state models included. We conjecture that its span complexity, proven independent of trajectory length for our model, would grow only logarithmically in the general case. More broadly, our parallel-in-time algorithm reduces the need to trade off model sophistication and data volume in likelihood-based inference for such models.
The following limitations of our approach point to directions for future work. It currently supports only a single observable and a one-dimensional latent space, whereas many systems are probed through several observables simultaneously. Further observables would enter as additional factors in the observation likelihood, providing the information needed for higher-dimensional latent inference. However, the explicit basis we use to represent the latent density, and with it the computational cost, grows exponentially with the latent dimension, becoming prohibitive beyond two dimensions. Particle filters could avoid this cost, scaling instead with the number of particles, but whether or not our parallel-in-time algorithm could be adapted to them is an open question. If such adaptation were possible can, our approach would extend to models whose transitions can be simulated but not evaluated, a class currently addressed mainly by simulation-based inference.28,29
Methods
Our inference problem combines three components: a model for the latent dynamics, a model for the emission function, and Bayesian filtering to compute the likelihood of observed trajectories given both. We define each in turn, then the wavelet representation with its smoothness priors. The filtering likelihood follows, with the parallel-in-time algorithm that evaluates it, the sampling and benchmarking protocols, and the synthetic and application cases. The convergence proof of the parallel-in-time algorithm, complete parametrizations, and implementation details are given in the Supplementary Information (S1, S6 and S2, respectively).
Model definition
We consider a continuous–discrete filtering model: a continuous-time, continuous-state latent process, observed at discrete times through an emission function that is non-linear and need not be injective.
The latent process { X t } t ≥ 0 \{X_t\}_{t \ge0} { X t } t ≥ 0 takes values in the state space X = [ a , b ] n ⊂ R n \mathcal{X} = [a,b]^n \subset\mathbb{R}^n X = [ a , b ] n ⊂ R n and satisfies the overdamped Langevin equation
d X t = − D k B T ∇ G θ l a n d ( X t ) d t + 2 D d W t , (1) \mathrm{d}X_t = -\frac{D}{k_{\mathrm{B}}T}\nabla G_{\theta_{\mathrm{land}}}(X_t)\,\mathrm{d}t + \sqrt{2D}\,\mathrm{d}W_t, \tag*{(1)} d X t = − k B T D ∇ G θ land ( X t ) d t + 2 D d W t , (1)
where D > 0 D > 0 D > 0 is the diffusion coefficient and { W t } t ≥ 0 \{W_t\}_{t \ge0} { W t } t ≥ 0 the standard Wiener process. The equation holds for overdamped dynamics, in which momentum relaxes fast compared with the observation interval. The free energy landscape G θ l a n d : X → R G_{\theta_{\mathrm{land}}} : \mathcal{X} \to\mathbb{R} G θ land : X → R decomposes as G θ l a n d = G i n t e r i o r , θ l a n d + G w a l l G_{\theta_{\mathrm{land}}} = G_{\mathrm{interior},\theta_{\mathrm{land}}} + G_{\mathrm{wall}} G θ land = G interior , θ land + G wall , the first term parameterized by θ l a n d ∈ Θ l a n d \theta_{\mathrm{land}} \in\Theta_{\mathrm{land}} θ land ∈ Θ land , the second fixed and known, rising steeply near ∂ X \partial\mathcal{X} ∂ X (Supplementary Information S2). Both terms are assumed continuously differentiable with bounded second derivative on X \mathcal{X} X , and a formal zero-flux condition at ∂ X \partial\mathcal{X} ∂ X closes the domain. The stationary density is then p e q ( x ) = Z − 1 e − β G θ l a n d ( x ) p_{\mathrm{eq}}(x) = Z^{-1}e^{-\beta G_{\theta_{\mathrm{land}}}(x)} p eq ( x ) = Z − 1 e − β G θ land ( x ) , with β = 1 / k B T \beta= 1/k_{\mathrm{B}}T β = 1/ k B T and Z Z Z the normalizing constant.
The observed process { Y t k } k = 1 N \{Y_{t_k}\}_{k=1}^{N} { Y t k } k = 1 N takes values in the observation space Y ⊆ R \mathcal{Y} \subseteq\mathbb{R} Y ⊆ R , sampled at times t k = k Δ t t_k = k\Delta t t k = k Δ t for simplicity, though the method allows non-uniform observation times. Conditional on the latent state, observations are generated via the emission model
Y t k ∣ X t k ∼ p o b s ( ⋅ ∣ f θ e m ( X t k ) ) (2) Y_{t_k}\mid X_{t_k} \sim p_{\mathrm{obs}}\!\left(\cdot\mid f_{\theta_{\mathrm{em}}}(X_{t_k})\right) \tag*{(2)} Y t k ∣ X t k ∼ p obs ( ⋅ ∣ f θ em ( X t k ) ) (2)
where f θ e m : X → S f_{\theta_{\mathrm{em}}} : \mathcal{X} \to\mathcal{S} f θ em : X → S is the emission function parameterized by θ e m ∈ Θ e m \theta_{\mathrm{em}} \in\Theta_{\mathrm{em}} θ em ∈ Θ em , assumed continuously differentiable with bounded second derivative. Here S \mathcal{S} S is the parameter space of the observation (noise) distribution and p o b s ( ⋅ ∣ s ) p_{\mathrm{obs}}(\cdot\mid s) p obs ( ⋅ ∣ s ) is a probability density on Y \mathcal{Y} Y indexed by s ∈ S s \in\mathcal{S} s ∈ S . If p o b s p_{\mathrm{obs}} p obs is Gaussian with fixed σ \sigma σ and variable mean, for instance, then S = R \mathcal{S} = \mathbb{R} S = R and s s s is that mean. The observation distribution is specified by the user rather than inferred, subject only to f θ e m f_{\theta_{\mathrm{em}}} f θ em controlling a location parameter of it. Its identifiability jointly with the landscape and emission is untested. In the application cases, we chose it empirically from the one-step-ahead residuals of a preliminary run. Given the trajectory { X t } \{X_t\} { X t } , the observations { Y t k } \{Y_{t_k}\} { Y t k } are conditionally independent.
The model is identified only up to gauge freedoms of the latent coordinate: isometries such as reflections and rotations, and its scale set by the diffusion coefficient D D D (Supplementary Information S4). We break the isometries with a weak prior and fix D D D rather than infer it. Its value comes from a preliminary run in which D D D is free, fixed within the range the posterior supports and reported alongside the posteriors (gauge-fixing procedure, Supplementary Information S4).
Representation and regularization
Recovering G G G and f f f from finite, noisy trajectories is an inverse problem, and unregularized solutions to such problems fit detail that the data cannot resolve. Bayesian inference mitigates this by returning a posterior rather than a point estimate, so that unsupported detail appears as uncertainty. We regularize nonetheless on two grounds. First, as an inductive prior: a projection onto a few collective coordinates averages over many degrees of freedom, so that the resulting landscape and emission are generally smooth. Second, for efficiency, as restricting the search space reduces the sampling needed to reach a given accuracy. Besov spaces B p , p s B^s_{p,p} B p , p s comprise the functions of a prescribed regularity, indexed by a smoothness order s s s and a sparsity type p p p . We target this class by expanding G G G and f f f in a wavelet basis and placing the corresponding prior on the coefficients, which shrinks them geometrically with resolution level and is discretization-invariant in the sense of Lassas et al.43 We use the biorthogonal 3.3 synthesis wavelet, a compactly supported quadratic spline, continuously differentiable with bounded second derivative, so that finite expansions meet the regularity assumed above. Defaults are s = 2 s = 2 s = 2 , the lowest order that penalizes curvature, which enters the Fokker–Planck operator in the symmetrized form we diagonalize, and p = 2 p = 2 p = 2 , which makes the coefficient prior Gaussian. Both are user-settable (Supplementary Information S5). The posterior is robust to the prior scales and to the weight of the isometry-breaking prior, more sensitive to s s s , and concentrates on the ground truth as the trajectory lengthens (Supplementary Information S6.6).
The wavelet basis carries the prior, but filtering is computed in a second basis. parametrize G G G and f f f in the wavelet basis, 24 coefficients each, and compute in a basis of Gaussian functions on a regular grid, N g = 96 N_g = 96 N g = 96 per dimension (256 for the logVIX case), giving N b = N g n N_b = N_g^n N b = N g n basis functions. A linear change of basis maps between the two. Gaussians are chosen for quadrature, the non-linear operations of filtering being evaluated at Gauss-Hermite nodes and projected back by the quadrature weights, efficiently on GPU (Supplementary Information S2). Computation is mixed precision: filtering runs in single precision, while operator assembly, diagonalization and the log-likelihood reduction run in double.
Filtering and smoothing
The central computational task is evaluating the likelihood p ( { Y t k } ∣ θ ) p(\{Y_{t_k}\} \mid\theta) p ({ Y t k } ∣ θ ) , which Bayesian filtering decomposes into predict–update iterations.22 Prediction propagates the density between observations, p t k p r e d = e L Δ t p t k − 1 p_{t_k}^{\mathrm{pred}} = e^{\mathcal{L}\Delta t}p_{t_{k-1}} p t k pred = e L Δ t p t k − 1 , with L \mathcal{L} L the Fokker–Planck operator, projected onto the computation basis and diagonalized to form the propagator. The update multiplies by the observation likelihood and renormalizes, with
Z t k = ∫ X p o b s ( Y t k ∣ f θ e m ( x ) ) ⋅ p t k p r e d ( x ) d x , (3) Z_{t_k} = \int_{\mathcal{X}} p_{\mathrm{obs}}(Y_{t_k} \mid f_{\theta}^{\mathrm{em}}(x)) \cdot p_{t_k}^{\mathrm{pred}}(x)\, dx, \tag*{(3)} Z t k = ∫ X p obs ( Y t k ∣ f θ em ( x )) ⋅ p t k pred ( x ) d x , (3)
so that the total log-likelihood is ∑ k log Z t k \sum_k \log Z_{t_k} ∑ k log Z t k . Because the update takes place in X \mathcal{X} X , no Jacobian correction is needed despite the non-invertible emission. The recursion is initialized with p t 0 = p e q p_{t_0} = p_{\mathrm{eq}} p t 0 = p eq , and the backward Kitagawa smoother gives exact non-linear smoothing for latent trajectory reconstruction. Implementation details are given in Supplementary Information S2.
Parallel In Time (PinT) filtering
The filtering recursion is sequential: the density at step k k k depends on that at step k − 1 k - 1 k − 1 , giving a span complexity of O ( N ) O(N) O ( N ) in the number of time steps. We convert this span into parallel work with an iterative algorithm in the manner of waveform relaxation42 (Figure 1b). Each trajectory of N N N time steps is partitioned into B = ⌈ N / L ⌉ B = \lceil N/L \rceil B = ⌈ N / L ⌉ contiguous blocks of length L L L , distributed across the available devices. Splitting the trajectory this way requires the latent density at each block boundary, which is not available in advance. The leading block therefore starts from the model’s initial density, p e q p_{\mathrm{eq}} p eq here, and every other from a trial density, for which we also use p e q p_{\mathrm{eq}} p eq . Each iteration filters all blocks concurrently, accumulating their likelihood contributions, then passes the terminal density of block b − 1 b - 1 b − 1 to the start of block b b b . At the fixed point of this iteration, the boundary densities and the log-likelihood agree exactly with those of the sequential filter (Supplementary Information, Proposition P1). Blocks communicate only through these boundary densities, so the inner filter enters as a black box: any predict–update recursion can be substituted for ours. Exactness at the fixed point follows for any such substitution; the iteration count established below does not, resting on the forgetting rate of whichever filter is used. Pseudocode and convergence proofs, with partial Lean formalization, are given in Supplementary Information S1.
Convergence is measured by the change in the block-boundary densities between successive iterations, in the weighted root-mean-square (WRMS) norm standard in adaptive ODE error control (Supplementary Information S1.1). The norm scales each basis coefficient by a mixed absolute and relative tolerance, so that it is dimensionless and stays well defined for coefficients approaching zero. Because the sequential filter is reproduced exactly only where the boundary densities stop changing altogether, the iteration stops once this norm falls to one or below, with atol = rtol = 10 − 6 10^{-6} 1 0 − 6 , about ten times the machine epsilon of the single precision in which the filter runs, so that the fixed point is reached to within floating-point noise.
Convergence is guaranteed in at most B B B iterations and without approximation, since exact boundary conditions propagate across one further block per iteration. This guarantees convergence even for a filter that never forgets its initialization, though of course the speed-up is then nil. A stronger result holds for our model: the iteration count does not grow with N N N , giving a span of O ( N i t e r L ) \mathcal{O}(N_{\mathrm{iter}}L) O ( N iter L ) rather than O ( N ) \mathcal{O}(N) O ( N ) . At iteration n n n , block b b b has been conditioned on n L nL n L consecutive filtering steps. By filter stability 40 a misspecified initialization is forgotten after some number of steps k f k_{\mathrm{f}} k f , so once n L > k f nL > k_{\mathrm{f}} n L > k f every block has converged, and N i t e r = ⌈ k f / L ⌉ N_{\mathrm{iter}} = \lceil k_{\mathrm{f}}/L \rceil N iter = ⌈ k f / L ⌉ . It is the particularly strong forgetting rate of our model that allows an O ( 1 ) \mathcal{O}(1) O ( 1 ) span, as it provides a global k f k_{\mathrm{f}} k f derived from the compactness of the latent domain or the spectral gap of the propagator. For models with neither property, and hence without such a global forgetting time, we expect instead O ( log N ) \mathcal{O}(\log N) O ( log N ) span. Total work is O ( N i t e r N ) \mathcal{O}(N_{\mathrm{iter}}N) O ( N iter N ) , a small multiple of that of the sequential filter, the price of the reduced span.
HMC also requires the gradient of the likelihood, which we obtain without differentiating through the iterations. Writing that iteration as P ( n + 1 ) = Φ ( P ( n ) , θ ) P^{(n+1)} = \Phi(P^{(n)}, \theta) P ( n + 1 ) = Φ ( P ( n ) , θ ) , with P P P the block boundary densities, reverse-mode gradients follow from the implicit function theorem.53 At convergence the gradient of the likelihood with respect to θ \theta θ solves the adjoint equation
u = P ˉ + ( ∂ Φ ∂ P ) T u , u = \bar{P} + \left(\frac{\partial\Phi}{\partial P}\right)^{\mathsf{T}} u, u = P ˉ + ( ∂ P ∂ Φ ) T u ,
itself a contractive fixed-point iteration. Differentiating the converged solution rather than the iterations keeps the gradient exact and its memory cost independent of the iteration count.
Inference protocol
Reaching the region of highest posterior density is difficult: emission functions differing in preimage multiplicity, the number of latent values mapping to a given observation, occupy separate basins that a chain rarely crosses even when the destination is better. Our protocol therefore covers the basins by construction, rather than requiring any chain to cross between them.
We fan out over a library of candidate parameter sets, 25 to 150 per chain, each pairing a flat landscape with an emission function drawn as a piecewise-linear path through a coarse grid of nodes. Each candidate is taken to a local maximum of the log-posterior by L-BFGS, then explored by HMC, both under a tempered posterior π γ ( θ ) ∝ [ π ( θ ) p ( Y ∣ θ ) ] γ \pi_\gamma(\theta) \propto[\pi(\theta)\,p(Y \mid\theta)]^\gamma π γ ( θ ) ∝ [ π ( θ ) p ( Y ∣ θ ) ] γ with γ \gamma γ starting at γ 0 = 0.8 \gamma_0 = 0.8 γ 0 = 0.8 for the application cases and 0.1 for the validation cases. The observation distribution is tempered in its tails as well, mixed with a broad density (triangular, or uniform where p o b s p_{\mathrm{obs}} p obs already has a uniform component) spanning the observed range, p o b s ( ε ) = ( 1 − ε ) p o b s + ε Tri ( y min , y max ) p_{\mathrm{obs}}^{(\varepsilon)} = (1-\varepsilon)\,p_{\mathrm{obs}} + \varepsilon\,\operatorname{Tri}(y_{\min}, y_{\max}) p obs ( ε ) = ( 1 − ε ) p obs + ε Tri ( y m i n , y m a x ) , with ε \varepsilon ε between 0.05 and 0.3 (Supplementary Information S6), adjusted empirically upward if divergences are encountered during HMC. Far from the true landscape, a predicted density and an observation can overlap negligibly, so the likelihood and its gradient reflect almost nothing about how far apart they are. The mixture restores that signal, acting in one dimension much like a Wasserstein distance between the two densities. Annealing then proceeds in two stages, first raising γ \gamma γ to one, then lowering ε \varepsilon ε to a residual 0.5 percent that keeps the likelihood positive for every θ \theta θ , after which a short untempered HMC phase settles each candidate into its local optimum. The Hessian at the L-BFGS optimum sets the initial diagonal mass matrix, which is then adjusted, together with the step size, by warmup-style adaptation throughout the fan-out. One candidate is retained by importance sampling on its posterior probability at the end of that phase. The best candidate typically has overwhelmingly better posterior probability than the other candidates: the other basins are local optima carrying negligible posterior mass, so that retaining one candidate discards no appreciable part of the posterior. Step size and a diagonal mass matrix are then re-adapted for the production run by the Stan window algorithm,54 and samples are collected by HMC.55 The whole protocol, fan-out included, is run independently for each of four chains, which are therefore independent in the strict sense. Convergence is assessed by split r ^ \hat{r} r ^ , Bayesian fraction of missing information, and effective sample size. We use static HMC with a fixed number of leapfrog steps and large sample counts rather than adaptive path lengths (as in NUTS), since GPU-accelerated likelihood evaluation makes over-sampling inexpensive. Sample counts and remaining settings are given in Supplementary Information S6.
Benchmarks
All benchmarks ran on a single compute node with eight NVIDIA A4000 GPUs, on one landscape (double well) and one emission function (linear). The measured quantity is the time to collect 10 posterior samples by HMC with 8 leapfrog steps. The accuracy comparison (Figure 3 a) used 14 test systems: the validation and application systems of this work, further applications not reported here, and additional validation runs such as the prior sensitivity scans (Supplementary Information S6). Each was evaluated at the initial flat landscape, at the ground-truth parameters where available, and at posterior samples. The benchmark therefore carries every overhead of practical use, likelihood accumulation and the backward pass for gradients included. Block length was scanned from 3 to 20 time steps per block, and the best performance for each problem size and GPU count is reported. Each configuration was replicated five times, re-running the whole sampling loop without recompilation, to give confidence intervals on the timings. Sequential timings were collected by the same protocol. Non-monotonic speed-ups beyond run-to-run noise reflect JAX emitting different machine code for each GPU count and problem size, a known limitation of the framework.
Communication between blocks, and hence between GPUs, is nearest-neighbor: each block receives one boundary density per trajectory from its predecessor and sends one to its successor. The volume is de minimis , a density of N b N_b N b coefficients, 3 to 6 kB. The algorithm is therefore latency-bound in its communication, so we deliberately used the slowest available transfer, a staging buffer in host memory, to give worst-case conditions for within-node parallelization.
Validation examples
Ground-truth landscapes and emission functions were drawn from the prior (s = 2 s = 2 s = 2 , p = 2 p = 2 p = 2 ), then modified to add multiple wells and two- and three-way non-injectivity. From 10 such draws we retained the two most challenging, those with the most overlapping emission branches, on the reasoning that a method handling those handles easier cases.
Trajectories were generated by Euler–Maruyama integration at a step roughly one hundred times smaller than the observation interval, reduced further so that Δ t \Delta t Δ t falls on an exact integer multiple of it. Integration error is therefore negligible at the scale of the observation interval, so that the validation tests the method essentially against the continuous-time process. Observations were drawn from a Gaussian observation distribution with σ = 0.25 \sigma= 0.25 σ = 0.25 .
The diffusion coefficient was set to D = 1 D = 1 D = 1 for both generation and inference. The gauge is therefore fixed by construction rather than by the preliminary run used for the application cases. Inference then followed the protocol above unchanged, starting from the candidate library with no knowledge of the ground truth, exactly as for the application cases. Posteriors are shown as produced, with no alignment to the ground truth except for fixing the minimum free energy of each sample to zero, the dynamics being invariant to an offset of the whole landscape.
Prior sensitivity was assessed by re-inferring the landscape of validation system (b) across smoothness orders s ∈ { 1 , 1.5 , 2 , 2.5 , 3 } s \in\{1, 1.5, 2, 2.5, 3\} s ∈ { 1 , 1.5 , 2 , 2.5 , 3 } at p = 2 p = 2 p = 2 and isometry-breaking weights w s y m ∈ { 1 , 4 , 8 , 10 , 20 } w_{\mathrm{sym}} \in\{1, 4, 8, 10, 20\} w sym ∈ { 1 , 4 , 8 , 10 , 20 } , and that of system (a) across prior scales σ 0 ∈ { 10 , 20 , 40 } \sigma_0 \in\{10, 20, 40\} σ 0 ∈ { 10 , 20 , 40 } and multipliers C s ∈ { 2 , 5 , 20 } C_s \in\{2, 5, 20\} C s ∈ { 2 , 5 , 20 } , with C s σ 0 C_s\sigma_0 C s σ 0 the scale of the scaling-function prior. Together, σ 0 \sigma_0 σ 0 and C s C_s C s set our prior belief in the overall free-energy variation. Data sensitivity was assessed on a separate double-well landscape with linear emission, for trajectories of N = 10 000 N = 10\,000 N = 10 000 to 50 000 time steps. Trajectory counts and lengths, integrator settings, and the remaining parameters are given in Supplementary Information S6.1, S6.2 and S6.6.
El Niño (ENSO) case study
We model ENSO as a stationary diffusion over the 160-year observational record, the same assumption underlying autoregressive models routinely fitted to climate indices over comparable windows. Slow non-stationarity from volcanic, orbital, and anthropogenic forcing is absorbed into a single time-averaged potential. The inferred landscape is the dimensionless effective potential G ( x ) G(x) G ( x ) , defined by p e q ∝ e − G p_{\mathrm{eq}} \propto e^{-G} p eq ∝ e − G ; no thermal interpretation is needed, though G G G directly determines transition statistics (e.g. , occupation ratios, mean residence times).
Observable: the Southern Oscillation Index (SOI), the standardized pressure differential between Tahiti and Darwin, recorded monthly from January 1866 to December 2025 (1920 observations).56, 57 As independent validation, we compare inferred ENSO phase assignments against the Sea Surface Temperature-based Oceanic Niño Index (ONI),58, 59 available for 909 of these months, using standard NOAA thresholds (± 0.5 \pm0.5 ± 0.5 K) to derive El Niño, La Niña, and neutral labels. The ONI plays no role in the inference. The observation distribution is a Student-t t t (ν = 9.5 \nu= 9.5 ν = 9.5 , σ = 0.60 \sigma= 0.60 σ = 0.60 ), chosen empirically from the one-step-ahead residuals of a preliminary run, and the diffusion coefficient was fixed at D = 0.35 D = 0.35 D = 0.35 after a short run with free D D D . See Supplementary Information S6.3 for detailed parametrization.
Nano-aperture optical tweezer application
Observable: the transmission of the trapping laser through a double nano-hole aperture, recorded as an avalanche photodiode voltage, reporting on the conformational state of a single bovine serum albumin molecule held at 37 ∘ C 37\,^\circ\mathrm{C} 37 ∘ C .46 We use 24 thousand points, sampled every 2.5 ms, of the single trajectory available as open data. The recorded voltage was offset by its minimum and rescaled by a factor of 30 to improve numerical conditioning; the emission function is reported in these arbitrary units, which correspond to 1/30 volt. The observation distribution is a mixture, 99 percent Gaussian (σ = 0.10 \sigma= 0.10 σ = 0.10 ) and 1 percent uniform over the observable range, the uniform component serving only to absorb ten isolated frame-to-frame jumps of 4 to 5 standard deviations, incompatible with Brownian dynamics (Figure 4 c). As in the other case studies, the diffusion coefficient was fixed, here at D = 5 ⋅ 10 − 5 D = 5 \cdot10^{-5} D = 5 ⋅ 1 0 − 5 , after a short run with free D D D . See Supplementary Information S6.4 for detailed parametrization.
Implied volatility case study
Observable: option-implied, forward-looking volatility of the S&P 500 as logVIX (daily close, 2 Jan 1990 – 13 Mar 2026, Chicago Board Options Exchange; 9142 observations).60 The index was introduced in 1993, and its methodology revised in September 2003, when it moved from S&P 100 to S&P 500 options and to a wider range of strikes. Values before that date were computed retroactively by the exchange under the revised methodology. As in the ENSO study, the inferred landscape is the dimensionless effective potential G ( x ) G(x) G ( x ) . For the observation distribution we use an empirically determined Student-t t t (ν = 2.6 \nu= 2.6 ν = 2.6 , σ = 0.023 \sigma= 0.023 σ = 0.023 ), based on residual fitting after an initial inference. The diffusion coefficient was fixed at D = 0.02 D = 0.02 D = 0.02 after a short run with free D D D . See Supplementary Information S6.5 for detailed parametrization.
Data availability
The datasets, input files, and scripts used for the validation and application cases presented here are available at Zenodo (DOI 10.5281/zenodo.24311789), including final posterior data.
Code availability
The Planx package implementing the described method, and used to produce the application cases, is available under the GPLv3 license at https://gitlab.com/ElianeBriand/planx .
Use of AI statement
The large language model Claude (Anthropic) was used to help write the software package and the plotting code, and to edit this manuscript.
Appendix
Acknowledgments
This work was funded by the German Federal Ministry of Education and Research (BMBF) as part of its SCALEXA (New Methods and Technologies for Exascale Computing) initiative.
Convergence of PinT filtering algorithm
The grey boxes documents how the proof various proposition are expressed the Lean 4 / Mathlib formalization, i.e. the computer-verified version of the proof. Readers not interested in this formalization may skip these boxes.
Setting and scope
Algorithms under consideration. The following three algorithms/subroutines are the subjects of the proof.
BlockFilter($p_{\mathrm{in}}$, $Y_{\mathrm{seg}}$, $\theta$):
$p \leftarrow p_{\mathrm{in}}$; $\ell \leftarrow 0$
for each $Y$ in $Y_{\mathrm{seg}}$: $L$ steps in a block
$p_{\mathrm{pred}} \leftarrow e^{\mathcal{L}\Delta t}p$ predict
$Z \leftarrow \int p_{\mathrm{obs}}(Y \mid f_\theta(x))p_{\mathrm{pred}}(x)\,\mathrm{d}x$ normalizer = likelihood
$p \leftarrow p_{\mathrm{obs}}(Y \mid f_\theta(\cdot))p_{\mathrm{pred}}/Z$ update
$\ell \leftarrow \ell + \log Z$
return $p,\ell$
BlockFilter is a generic, density-based non-linear Bayesian filter operating on a block of L L L time steps with observations Y s e g = { Y i = 1 … L } Y_{\mathrm{seg}} = \{Y_{i=1\ldots L}\} Y seg = { Y i = 1 … L } , indexed locally within the block, and Fokker–Planck operator L \mathcal{L} L . In addition to the latent densities p p p , the model log-likelihood is also returned in ℓ \ell ℓ .
SequentialFilter($Y,\theta$):
$p_0 \leftarrow \pi_0$
for $\beta = 0,\ldots,B-1$: strictly serial, span $\mathcal{O}(N)$
$p_{\beta+1},\ell_\beta \leftarrow \operatorname{BlockFilter}(p_\beta,Y_{I_\beta},\theta)$
return $\sum_\beta \ell_\beta,\{p_\beta\}$
SequentialFilter is the sequential Bayesian filter, the naive algorithm corresponding to sequential application of the filtering recursion. We express it equivalently as a sequential iteration on B = N / L B = N/L B = N / L blocks of L L L time steps, given a trajectory of N N N total time steps, with repeated application of BlockFilter, passing the boundary density resulting from each application to the next one.
PinTFilter($Y,\theta,\pi_0,\bar{\pi}_0$):
$p_0^{(0)} \leftarrow \pi_0$; True initial condition
p β ( 0 ) ← π ˉ 0 for β = 1 , … , B − 1 p_{\beta}^{(0)} \leftarrow\bar{\pi}_0 \quad\text{for } \beta=1,\ldots,B-1 p β ( 0 ) ← π ˉ 0 for β = 1 , … , B − 1
for j = 1 , … , B j=1,\ldots,B j = 1 , … , B : PiNT iteration (at most B B B iterations)
parallel for β = 0 , … , B − 1 \beta=0,\ldots,B-1 β = 0 , … , B − 1 :
q β ( j ) , ℓ β ( j ) ← BlockFilter ( p β ( j − 1 ) , Y I β , θ ) q_{\beta}^{(j)},\ell_{\beta}^{(j)} \leftarrow\operatorname{BlockFilter}(p_{\beta}^{(j-1)},Y_{I_\beta},\theta) q β ( j ) , ℓ β ( j ) ← BlockFilter ( p β ( j − 1 ) , Y I β , θ ) Filter each block in parallel
p 0 ( j ) ← π 0 p_0^{(j)}\leftarrow\pi_0 p 0 ( j ) ← π 0 Leading boundary pinned
p β ( j ) ← q β − 1 ( j ) p_\beta^{(j)}\leftarrow q_{\beta-1}^{(j)} p β ( j ) ← q β − 1 ( j ) for β = 1 , … , B − 1 \beta=1,\ldots,B-1 β = 1 , … , B − 1 Pass densities tail-to-head to next block
δ ( j ) ← max β ≥ 1 ∥ c [ p β ( j ) ] − c [ p β ( j − 1 ) ] ∥ W R M S \delta^{(j)}\leftarrow\max_{\beta\geq1}\lVert\mathsf{c}[p_\beta^{(j)}]-\mathsf{c}[p_\beta^{(j-1)}]\rVert_{\mathrm{WRMS}} δ ( j ) ← max β ≥ 1 ∥ c [ p β ( j ) ] − c [ p β ( j − 1 ) ] ∥ WRMS Convergence criterion in density
if δ ( j ) ≤ 1 \delta^{(j)}\leq1 δ ( j ) ≤ 1 : break
return ∑ β ℓ β ( j ) , { p β ( j ) } \sum_\beta\ell_\beta^{(j)},\{p_\beta^{(j)}\} ∑ β ℓ β ( j ) , { p β ( j ) }
PiNTFilter is our parallel-in-time filter. As in SequentialFilter, each trajectory of N N N time steps is partitioned into B = N / L B=N/L B = N / L contiguous blocks of L L L steps. Filtering the blocks in parallel requires the latent density at each block boundary, a density that only the chain of preceding blocks can produce, and which is thus not available in advance. We therefore start the leading block from the true initial density π 0 \pi_0 π 0 , and other blocks from a trial density π ˉ 0 \bar{\pi}_0 π ˉ 0 . In each iteration j j j , all blocks are concurrently filtered, accumulating their log-likelihood contributions, and the terminal density of block β − 1 \beta-1 β − 1 is then passed on to block β \beta β , as its next initial condition. To detect convergence, we measure, for each block, how much its initial condition has changed compared to the previous iteration,
δ β ( j ) = ∥ c [ p β ( j ) ] − c [ p β ( j − 1 ) ] ∥ W R M S , \delta_\beta^{(j)}=\lVert\mathsf{c}[p_\beta^{(j)}]-\mathsf{c}[p_\beta^{(j-1)}]\rVert_{\mathrm{WRMS}}, δ β ( j ) = ∥ c [ p β ( j ) ] − c [ p β ( j − 1 ) ] ∥ WRMS ,
and take the maximum over blocks, δ ( j ) = max β ≥ 1 δ β ( j ) \delta^{(j)}=\max_{\beta\geq1}\delta_\beta^{(j)} δ ( j ) = max β ≥ 1 δ β ( j ) , which we call the increment at iteration j j j . When no initial condition changes are detected, the algorithm has converged, since the block filter is deterministic and identical inputs yield identical outputs. In exact arithmetic, the test would be δ ( j ) = 0 \delta^{(j)}=0 δ ( j ) = 0 . Floating-point arithmetic makes successive passes boundary densities differ slightly, so the implementation uses a Weighted Root Mean Square (WRMS) norm with absolute and relative tolerances, both at the floating-point floor (e.g. , 10 − 6 10^{-6} 1 0 − 6 in single precision). The log-likelihoods ℓ β ( j ) \ell_\beta^{(j)} ℓ β ( j ) and boundary densities p β ( j ) p_\beta^{(j)} p β ( j ) returned on exit both come from the j j j -th pass, whose inputs are the boundary densities p β ( j − 1 ) p_\beta^{(j-1)} p β ( j − 1 ) of the previous iteration.
The weighted root-mean-square (WRMS) norm is defined as
δ ( n ) = max b ∥ p 0 , b ( n ) − p 0 , b ( n − 1 ) ∥ W R M S , ∥ v ∥ W R M S = 1 N b ∑ i = 1 N b ( v i a t o l + r t o l ⋅ ∣ u i ∣ ) 2 . (4) \delta^{(n)}=\max_b\lVert p_{0,b}^{(n)}-p_{0,b}^{(n-1)}\rVert_{\mathrm{WRMS}},\qquad
\lVert v\rVert_{\mathrm{WRMS}}=
\sqrt{\frac{1}{N_b}\sum_{i=1}^{N_b}\left(\frac{v_i}{\mathrm{atol}+\mathrm{rtol}\cdot\lvert u_i\rvert}\right)^2}. \tag*{(4)} δ ( n ) = b max ∥ p 0 , b ( n ) − p 0 , b ( n − 1 ) ∥ WRMS , ∥ v ∥ WRMS = N b 1 i = 1 ∑ N b ( atol + rtol ⋅ ∣ u i ∣ v i ) 2 . (4)
where u i u_i u i denotes coefficient i i i of p 0 , b ( n − 1 ) p_{0,b}^{(n-1)} p 0 , b ( n − 1 ) and N b N_b N b is the basis dimension.
Figure S1. Sequential versus PinT filtering. a, Sequential filtering processes each of N t r a j N_{\mathrm{traj}} N traj trajectories as a chain of N N N filtering steps; trajectories are independent and thus parallelizable, but within each every step depends on its predecessor, yielding a span complexity of O ( N ) \mathcal{O}(N) O ( N ) . b, Splitting each trajectory into B = N / L B = N/L B = N / L contiguous blocks of length L ≪ N L \ll N L ≪ N , with the associated intermediate p ( x ) p(x) p ( x ) densities. c, Parallel-in-Time filtering: at the first iteration, the leading block is initialized with the true initial density while all subsequent blocks receive a starting guess p e q ( x ) p_{\mathrm{eq}}(x) p eq ( x ) (purple and teal tall rectangles) in place of the intermediate densities, which are not yet available. All blocks are then filtered concurrently. Between iterations, the terminal intermediate density of each block is passed forward as the initial condition of its successor (arrows), and a convergence check (CC) is applied at each block boundary. Blocks whose initial condition has converged (green) produce the same filtered densities as the sequential algorithm. d, Information propagation with iteration: each block has its history prolonged backward by the boundary density propagation, one block at every iteration, hence the relevance of the filter stability results.
Let us discuss informally some properties of this algorithm to contextualize the proofs stated in the following sections:
Remark (cost of speed-up). We will show below that, for our particular model, PINTFILTER has O ( 1 ) O(1) O ( 1 ) span complexity: for a fixed block length L L L , its span does not grow with the trajectory length N N N , whereas that of the sequential filter is O ( N ) O(N) O ( N ) . On parallel hardware, this results in a shorter wall-clock runtime. The speed-up comes at the cost of more total computation. In each iteration, all B B B blocks of L L L steps are filtered, which costs as much as the whole sequential filter, so the total work is the number of iterations times the work of the sequential filter.
Remark (the algorithm always terminates). After B − 1 B-1 B − 1 iterations, the true initial condition has propagated through all blocks, and the boundary densities are exactly those of the sequential filter (Corollary S-9). The increment at the next iteration is then zero, so the algorithm stops after at most B B B iterations. In this worst case, however, nothing is gained: the span is B ⋅ L = N B \cdot L = N B ⋅ L = N steps, the same as that of the sequential filter, and the total work is B B B times that of the sequential filter, so that B − 1 B-1 B − 1 full passes of computation are wasted.
Remark (trial densities). In our implementation, the trial density π ˉ 0 \bar{\pi}_0 π ˉ 0 is the equilibrium density p e q p_{\mathrm{eq}} p eq of the model, which is also the true initial density π 0 \pi_0 π 0 . Any other trial density is admissible. The number of iterations to convergence would change for different trial densities, but not the converged result, since the fixed point is the sequential filter whatever π ˉ 0 \bar{\pi}_0 π ˉ 0 is (Theorem S-12). The p e q p_{\mathrm{eq}} p eq density is a natural choice as the latent marginal, likely the best among trial densities that ignore the observations.
Remark (iterations as extending history). The iterations can also be read as extending, for every block, the history it conditions on. At iteration j j j , the initial condition of block β \beta β is the result of filtering the j j j preceding blocks, starting from the trial density (Lemma S-7). Each iteration adds one more block of past observations. This continues until either the history reaches the true initial condition, or it is long enough for filter stability to make the density forget the misspecified trial density. From that iteration on, the density at the block boundary changes only negligibly, whatever density it was started from, i.e. convergence.
Remark (iterations as a Picard iteration). The algorithm is also a Picard iteration for a fixed-point problem. Collect the boundary densities of iteration j j j into P ( j ) = ( p β ( j ) ) β P^{(j)} = (p_{\beta}^{(j)})_{\beta} P ( j ) = ( p β ( j ) ) β . One iteration, which filters all blocks in parallel and passes each terminal density on, is the map P ( j ) = F ( P ( j − 1 ) ) P^{(j)} = F(P^{(j-1)}) P ( j ) = F ( P ( j − 1 ) ) , with F F F the boundary-update map defined in § 4.0.3 . The iteration stops when the boundary densities no longer change, that is, at a fixed point of F F F , and this fixed point is the sequential filter (Theorem S-12).
Remark (relation to other PinT algorithms). The algorithm is somewhat similar to waveform relaxation,[1 ] with its splitting of the time domain and passing of boundary values between iterations. It is also a special case of Parareal.[2 ] Parareal updates each boundary value as
U β + 1 ( j ) = G ( U β ( j ) ) + F ( U β ( j − 1 ) ) − G ( U β ( j − 1 ) ) , U_{\beta+1}^{(j)} = \mathcal{G}\left(U_{\beta}^{(j)}\right) + \mathcal{F}\left(U_{\beta}^{(j-1)}\right) - \mathcal{G}\left(U_{\beta}^{(j-1)}\right), U β + 1 ( j ) = G ( U β ( j ) ) + F ( U β ( j − 1 ) ) − G ( U β ( j − 1 ) ) ,
with a fine propagator F \mathcal{F} F and a coarse propagator G \mathcal{G} G . With a coarse propagator ignoring its input and always returning π ˉ 0 \bar{\pi}_0 π ˉ 0 , the two G \mathcal{G} G terms cancel, and the update becomes
U β + 1 ( j ) = F ( U β ( j − 1 ) ) . U_{\beta+1}^{(j)} = \mathcal{F}\left(U_{\beta}^{(j-1)}\right). U β + 1 ( j ) = F ( U β ( j − 1 ) ) .
This is our iteration, with \mathcal{F} = \textsc{BlockFilter} . Like Parareal, and as discussed above, it therefore converges exactly, in the worst case, once the initial condition has propagated through all blocks.
Remark (discretization error). We want to prove that \textsc{PintFilter} reproduces the sequential filter as implemented, not that either of them is close to the exact, idealized filter. To that end, both algorithms call the same implementation of \textsc{BlockFilter}, so they share the same discretization error, up to the stopping tolerance. We do not attempt to bound the discretization error itself.
Notation
The following notation is used throughout the proof.
Our model. As described in the Methods section:
the latent domain is a cube X = [ a , b ] n \mathcal{X} = [a,b]^n X = [ a , b ] n , with a reflecting zero-flux boundary.
the free energy landscape G ∈ W 2 , ∞ ( X ) G \in W^{2,\infty}(\mathcal{X}) G ∈ W 2 , ∞ ( X ) , continuously differentiable with bounded second derivative, is bounded with p e q ∝ e − G / k B T p_{\mathrm{eq}} \propto e^{-G/k_{\mathrm{B}}T} p eq ∝ e − G / k B T its equilibrium density, and its equilibrium measure P e q ( d y ) = p e q ( y ) d y P_{\mathrm{eq}}(dy) = p_{\mathrm{eq}}(y)\,dy P eq ( d y ) = p eq ( y ) d y .
Q t ( x , d y ) Q_t(x,dy) Q t ( x , d y ) is the transition kernel of the latent dynamics over a time t t t , and κ t \kappa_t κ t its density with respect to P e q P_{\mathrm{eq}} P eq : Q t ( x , d y ) = κ t ( x , y ) P e q ( d y ) Q_t(x,dy) = \kappa_t(x,y)P_{\mathrm{eq}}(dy) Q t ( x , d y ) = κ t ( x , y ) P eq ( d y ) .
observations Y t 1 , … , Y t N Y_{t_1},\ldots,Y_{t_N} Y t 1 , … , Y t N are taken at the times t k = k Δ t t_k = k\Delta t t k = k Δ t , and N N N is the trajectory length.
the latent state x x x is observed through the emission f θ : X → S f_\theta: \mathcal{X} \to\mathcal{S} f θ : X → S and the observation density p o b s ( ⋅ ∣ s ) p_{\mathrm{obs}}(\cdot\mid s) p obs ( ⋅ ∣ s ) . The likelihood of the k k k -th observation, as a function of the latent state, is Ψ k ( x ) : = p o b s ( Y t k ∣ f θ ( x ) ) \Psi_k(x) := p_{\mathrm{obs}}(Y_{t_k} \mid f_\theta(x)) Ψ k ( x ) := p obs ( Y t k ∣ f θ ( x )) .
Blocks and iterates. As in the algorithms above:
L L L divides N N N , so each trajectory is split into B = N / L B = N/L B = N / L blocks. Block β \beta β update based on the observations Y I β Y_{\mathcal{I}_\beta} Y I β with indices I β = { β L + 1 , … , ( β + 1 ) L } \mathcal{I}_\beta= \{\beta L + 1, \ldots, (\beta+ 1)L\} I β = { β L + 1 , … , ( β + 1 ) L } .
p β ( j ) p_\beta^{(j)} p β ( j ) is the density at the start of block β \beta β after iteration j j j , i.e. , the initial condition of that block in the next pass. π ˉ 0 \bar{\pi}_0 π ˉ 0 is the trial density used for every block β ≥ 1 \beta\ge1 β ≥ 1 at iteration 0.
P ( X ) \mathcal{P}(\mathcal{X}) P ( X ) is the set of probability measures on X \mathcal{X} X . We identify a density p p p with the measure p ( x ) d x p(x)\,dx p ( x ) d x , so the filter states p β ( j ) p_\beta^{(j)} p β ( j ) and p β s e q p_\beta^{\mathrm{seq}} p β seq are elements of P ( X ) \mathcal{P}(\mathcal{X}) P ( X ) .
Norms.
∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ is the total variation norm, normalized as in Le Gland–Oudjane, i.e. , ∥ μ − μ ′ ∥ ≤ 2 \|\mu-\mu'\| \le2 ∥ μ − μ ′ ∥ ≤ 2 for probability measures. We write ∥ ⋅ ∥ T V \|\cdot\|_{\mathrm{TV}} ∥ ⋅ ∥ TV when confusion is possible.
Assumptions
We assume the following for the proof.
(A1) Nondegenerate channel. For every s ∈ S s \in\mathcal{S} s ∈ S , p o b s ( ⋅ ∣ s ) p_{\mathrm{obs}}(\cdot\mid s) p obs ( ⋅ ∣ s ) admits a Lebesgue density on Y \mathcal{Y} Y ; hence Ψ k \Psi_k Ψ k is a well-defined non-negative measurable function on X \mathcal{X} X .
(A2) Non-vanishing, integrable likelihood. For the observed record, 0 < ∫ X Ψ k d P e q < ∞ 0 < \int_{\mathcal{X}} \Psi_k\,d\mathbb{P}_{\mathrm{eq}} < \infty 0 < ∫ X Ψ k d P eq < ∞ for every k k k .
(A3) Source of mixing. One of the following assumptions, (A3a) or (A3b), must hold, to provide mixing condition (E). (A3a) is the default route: it holds for every Δ t \Delta t Δ t and gives the best possible constant in (E), but only as the minimum and maximum of the transition
density, which are not known in closed form. (A3b) applies in the sparse-sampling regime, where it gives a constructive lower bound on that constant, computable from the spectral gap λ 1 \lambda_1 λ 1 and the diagonal values of the transition density. (Further variants used to establish (E) could be added without modifying the proof apart from § 4 .)
(A3a) Compact positivity. The transition density κ Δ t \kappa_{\Delta t} κ Δ t is continuous on X × X \mathcal{X} \times\mathcal{X} X × X , strictly positive, and satisfies
∫ X κ Δ t ( x , y ) P e q ( d y ) = 1 for every x . \int_{\mathcal{X}} \kappa_{\Delta t}(x,y)\,P_{\mathrm{eq}}(dy) = 1 \qquad\text{for every }x. ∫ X κ Δ t ( x , y ) P eq ( d y ) = 1 for every x .
(A3b) Spectral gap, with sparse sampling. For every t > 0 t > 0 t > 0 , the transition density κ t \kappa_t κ t is continuous on X × X \mathcal{X} \times\mathcal{X} X × X and symmetric, κ t ( x , y ) = κ t ( y , x ) \kappa_t(x,y) = \kappa_t(y,x) κ t ( x , y ) = κ t ( y , x ) (reversibility). Moreover, the dynamics has a spectral gap λ 1 > 0 \lambda_1 > 0 λ 1 > 0 : for every t > 0 t > 0 t > 0 and every f ∈ L 2 ( P e q ) f \in L^2(P_{\mathrm{eq}}) f ∈ L 2 ( P eq ) with ∫ f d P e q = 0 \int f\,dP_{\mathrm{eq}} = 0 ∫ f d P eq = 0 ,
∥ P t f ∥ L 2 ( P e q ) ≤ e − λ 1 t ∥ f ∥ L 2 ( P e q ) , P t f ( x ) : = ∫ X κ t ( x , y ) f ( y ) P e q ( d y ) . \lVert P_t f\rVert_{L^2(P_{\mathrm{eq}})} \le e^{-\lambda_1 t}\lVert f\rVert_{L^2(P_{\mathrm{eq}})}, \qquad P_t f(x) := \int_{\mathcal{X}} \kappa_t(x,y)f(y)\,P_{\mathrm{eq}}(dy). ∥ P t f ∥ L 2 ( P eq ) ≤ e − λ 1 t ∥ f ∥ L 2 ( P eq ) , P t f ( x ) := ∫ X κ t ( x , y ) f ( y ) P eq ( d y ) . Finally, the sampling is sparse enough: for some t 0 ∈ ( 0 , Δ t / 2 ) t_0 \in(0,\Delta t/2) t 0 ∈ ( 0 , Δ t /2 ) ,
e − λ 1 ( Δ t − 2 t 0 ) sup x ( κ 2 t 0 ( x , x ) − 1 ) < 1. e^{-\lambda_1(\Delta t-2t_0)}\sup_x\bigl(\kappa_{2t_0}(x,x)-1\bigr) < 1. e − λ 1 ( Δ t − 2 t 0 ) x sup ( κ 2 t 0 ( x , x ) − 1 ) < 1.
(A4) Finite-dimensional representation. The states of the filter are densities in a finite-dimensional subspace V ⊂ L 1 ( X ) V \subset L^1(\mathcal{X}) V ⊂ L 1 ( X ) with a basis e 1 , … , e N b e_1,\ldots,e_{N_b} e 1 , … , e N b , and c : V → R N b \mathbf{c}:V \to\mathbb{R}^{N_b} c : V → R N b is the coordinate map in this basis, p = ∑ i c i [ p ] e i p = \sum_i c_i[p]e_i p = ∑ i c i [ p ] e i . In particular, two states with equal coefficient vectors are equal. We write
M e : = sup 0 ≠ p ∈ V max i ∣ c i [ p ] ∣ ∥ p ∥ T V M_e := \sup_{0\ne p\in V}\frac{\max_i\lvert c_i[p]\rvert}{\lVert p\rVert_{\mathrm{TV}}} M e := 0 = p ∈ V sup ∥ p ∥ TV max i ∣ c i [ p ]∣ for the norm of c \mathbf{c} c from the total variation norm to the maximum norm. It is finite because V V V is finite-dimensional, and max i ∣ c i [ p ] ∣ ≤ M e ∥ p ∥ T V \max_i\lvert c_i[p]\rvert\le M_e\lVert p\rVert_{\mathrm{TV}} max i ∣ c i [ p ]∣ ≤ M e ∥ p ∥ TV for every p ∈ V p \in V p ∈ V .
Remark (on (A2)). The integral in (A2) is the equilibrium observation marginal at the observed value,
∫ X Ψ k d P e q = ∫ X p o b s ( Y t k ∣ f θ ( x ) ) p e q ( x ) d x = p Y ( Y t k ) , \int_{\mathcal{X}} \Psi_k\,dP_{\mathrm{eq}} = \int_{\mathcal{X}} p_{\mathrm{obs}}(Y_{t_k}\mid f_\theta(x))\,p_{\mathrm{eq}}(x)\,dx = p_Y(Y_{t_k}), ∫ X Ψ k d P eq = ∫ X p obs ( Y t k ∣ f θ ( x )) p eq ( x ) d x = p Y ( Y t k ) ,
so (A2) says that p Y ( Y t k ) ∈ ( 0 , ∞ ) p_Y(Y_{t_k}) \in(0,\infty) p Y ( Y t k ) ∈ ( 0 , ∞ ) . When the data are generated by the model itself, at its true parameters, this holds almost surely given (A1). The latent chain starts at π 0 = p e q \pi_0 = p_{\mathrm{eq}} π 0 = p eq and is stationary, so each Y t k Y_{t_k} Y t k has density p Y p_Y p Y , and a density is almost surely positive and finite under its own law. Since there are countably many k k k , (A2) then holds for almost every observation record, and so does Proposition P1.
If the model is misspecified, or at parameters θ \theta θ far from the bulk of the posterior, as in the early phases of inference, (A2) is a genuine assumption. It holds for every θ \theta θ when p o b s > 0 p_{\mathrm{obs}} > 0 p obs > 0 everywhere, as with Gaussian observation noise, since then Ψ k > 0 \Psi_k > 0 Ψ k > 0 . When p o b s ( ⋅ ∣ s ) p_{\mathrm{obs}}(\cdot\mid s) p obs ( ⋅ ∣ s ) has bounded support, by contrast, an observed Y t k Y_{t_k} Y t k can fall outside the support of every emission distribution p o b s ( ⋅ ∣ f θ ( x ) ) p_{\mathrm{obs}}(\cdot\mid f_\theta(x)) p obs ( ⋅ ∣ f θ ( x )) . Then Ψ k ≡ 0 \Psi_k \equiv0 Ψ k ≡ 0 , the normalizer Z Z Z vanishes, the log-likelihood is − ∞ -\infty − ∞ , and the update step is undefined. A practical remedy is to implement the observation model as a technical mixture of p o b s p_{\mathrm{obs}} p obs with a uniform component of weight 1%, which keeps Ψ k > 0 \Psi_k > 0 Ψ k > 0 , and hence (A2) for every θ \theta θ . One then checks a posteriori on the inferred posterior whether some observations are explained only by the uniform component.
Remark (on (A3)). (A3) is the most stringent assumption on the model. In either variant, it makes the propagator mix uniformly, through compactness and positivity in (A3a) and through a spectral gap in (A3b). This is what gives the algorithm its O ( 1 ) O(1) O ( 1 ) span complexity. In practice, if Δ t \Delta t Δ t is longer than the relaxation timescale 1 / λ 1 1/\lambda_1 1/ λ 1 (sparse-observation regime), then (A3b) is satisfied, and it gives an explicit value for the constant in (E), hence an explicit bound on the iteration count. Under (A3a) alone, the constant exists but its value is not known, so the iteration count is shown to be finite and independent of N N N , without an explicit bound. When sampling is fast, the constant is moreover small, whichever route is used. The resulting bound is then still sufficient for the span complexity result, but far above the iteration counts observed in practice, so the proof gives no insight into the actual mechanism of convergence.
Statement of the result (Proposition P1)
Proposition P1 (Constant span complexity). Assume (A1)–(A4), and let ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) satisfy (E), as provided by § 4 . Run PintFilter with the WRMS stopping rule. Then the following hold.
Equivalence. The iteration has a unique fixed point, the sequential filter: at it, every filtered density and the total log-likelihood agree exactly with those of Sequential-Filter (Theorem S-12), and an exactly zero increment verifies that it has been reached (Corollary S-13).
Convergence, at an N N N -independent rate. At iteration j j j , the total-variation error between the densities of PᴵⁿᵗFⁱˡᵗᵉʳ and SᵉᑫᵘᵉⁿᵗⁱᵃˡFⁱˡᵗᵉʳ, E β ( j ) : = ∥ p β ( j ) − p β s e q ∥ T V E_{\beta}^{(j)} := \lVert p_{\beta}^{(j)} - p_{\beta}^{\mathrm{seq}}\rVert_{\mathrm{TV}} E β ( j ) := ∥ p β ( j ) − p β seq ∥ TV , satisfies max β E β ( j ) ≤ min { 2 , C 0 τ j L } \max_{\beta} E_{\beta}^{(j)} \le\min\{2, C_{0}\tau^{jL}\} max β E β ( j ) ≤ min { 2 , C 0 τ j L } , where τ < 1 \tau< 1 τ < 1 and C 0 C_{0} C 0 depend only on ε \varepsilon ε (Proposition S-10). Hence any target accuracy δ T V \delta_{\mathrm{TV}} δ TV is reached within N i t e r ( δ T V ) N_{\mathrm{iter}}(\delta_{\mathrm{TV}}) N iter ( δ TV ) iterations, which depends only on ( ε , L , δ T V ) (\varepsilon, L, \delta_{\mathrm{TV}}) ( ε , L , δ TV ) (Theorem S-11).
Span complexity. The WRMS rule stops the algorithm within N s t o p N_{\mathrm{stop}} N stop iterations, where N s t o p N_{\mathrm{stop}} N stop depends only on ( ε , L , M e , a t o l ) (\varepsilon, L, M_{\mathrm{e}}, \mathrm{atol}) ( ε , L , M e , atol ) (Corollary S-17). The span complexity is therefore O ( N s t o p ⋅ L ) O(N_{\mathrm{stop}}\cdot L) O ( N stop ⋅ L ) , independent of N N N .
A posteriori certificate. At iteration j j j , the total-variation error, which the program cannot observe, is bounded by the WRMS increment it computes: max β E β ( j ) ≤ A Γ δ ( j ) \max_{\beta} E_{\beta}^{(j)} \le A\Gamma\delta^{(j)} max β E β ( j ) ≤ A Γ δ ( j ) , with constants A = A ( ε , L ) A=A(\varepsilon,L) A = A ( ε , L ) and Γ \Gamma Γ , which depends only on the basis and the tolerances (Proposition S-15, Lemma S-16). In particular, when the rule δ ( j ) ≤ 1 \delta^{(j)} \le1 δ ( j ) ≤ 1 stops the algorithm, this error is at most A Γ A\Gamma A Γ , independently of N N N .
Lean: Proposition P1 — WaveformRelax.converges_to_sequential
Top-level proposition in PlanxAlgorithm/Relaxation.lean.
The names in the Lean statement are mapped to the human-readable proof as follows:
S is the set of states, here the probability measures on X \mathcal{X} X , and dist is the total variation distance on it.
Φ \Phi Φ b is the block map Φ β \Phi_{\beta} Φ β of block β = b \beta=b β = b ; π 0 \pi_{0} π 0 and π 0 ′ \pi_{0}' π 0 ′ are the prior π 0 \pi_{0} π 0 and the trial density π ˉ 0 \bar{\pi}_{0} π ˉ 0 .
iter Φ π₀ π₀' n b is p β ( j ) p_{\beta}^{(j)} p β ( j ) , with j = n j=n j = n ; seq Φ π₀ b is p β s e q p_{\beta}^{\mathrm{seq}} p β seq ; IsFixedPoint Φ π₀ P says that P P P is a fixed point of the boundary-update map; iterCount is N i t e r N_{\mathrm{iter}} N iter .
L is the block length, and the hypothesis hL : 0 < L says that blocks are not empty. It is used only to obtain τ L < 1 \tau^{L}<1 τ L < 1 , for the iteration count and for the geometric series in the a posteriori bound.
F : BlockForgetting Φ L is the hypothesis that the block maps satisfy the contraction bounds (F-abs) and (F-lip), the output of Section S1.7. It bundles the constants F.τ, F.C₀ and F.C₁, which are τ \tau τ , C 0 C_{0} C 0 and C 1 C_{1} C 1 , together with the two bounds. Despite the letter, it is unrelated to the boundary-update map F F F of the text.
theorem converges_to_sequential {L : ℕ} (F : BlockForgetting Φ L) (hL : 0 < L) :
(∀ P : ℕ → S, IsFixedPoint Φ π₀ P ↔ P = seq Φ π₀) ∧
( ∀ n b , dist ( iter Φ π 0 π 0 ′ n b ) ( seq Φ π 0 b ) ≤ F . C 0 ∗ F . τ ( n ∗ L ) ) ∧ ( ∀ δ : R , 0 < δ → ∀ n , iterCount F . C 0 F . τ L δ ≤ n → ∀ b , dist ( iter Φ π 0 π 0 ′ n b ) ( seq Φ π 0 b ) ≤ δ ) ∧ ( ∀ d : N → R , ( ∀ m b , 1 ≤ b → dist ( iter Φ π 0 π 0 ′ ( m + 1 ) b ) ( iter Φ π 0 π 0 ′ m b ) ≤ d m ) → ∀ m b , dist ( iter Φ π 0 π 0 ′ ( m + 1 ) b ) ( seq Φ π 0 b ) ≤ F . C 1 ∗ F . τ ( L − 1 ) ∗ d m / ( 1 − F . τ L ) ) \begin{aligned}
&(\forall n\, b,\ \operatorname{dist}(\operatorname{iter}\ \Phi\ \pi_0\ \pi_0'\ n\ b)(\operatorname{seq}\ \Phi\ \pi_0\ b) \le F.C_0 * F.\tau^ (n * L)) \land\\
&(\forall\delta: \mathbb{R},\ 0 < \delta\to\forall n,\ \operatorname{iterCount}\ F.C_0\ F.\tau\ L\ \delta\le n \to\\
&\qquad\forall b,\ \operatorname{dist}(\operatorname{iter}\ \Phi\ \pi_0\ \pi_0'\ n\ b)(\operatorname{seq}\ \Phi\ \pi_0\ b) \le\delta) \land\\
&(\forall d : \mathbb{N} \to\mathbb{R}, \\
&\qquad(\forall m\ b,\ 1 \le b \to\\
&\qquad\qquad\operatorname{dist}(\operatorname{iter}\ \Phi\ \pi_0\ \pi_0'\ (m + 1)\ b)(\operatorname{iter}\ \Phi\ \pi_0\ \pi_0'\ m\ b) \le d\ m) \to\\
&\qquad\forall m\ b,\ \operatorname{dist}(\operatorname{iter}\ \Phi\ \pi_0\ \pi_0'\ (m + 1)\ b)(\operatorname{seq}\ \Phi\ \pi_0\ b) \\
&\qquad\le F.C_1 * F.\tau^ (L - 1) * d\ m / (1 - F.\tau^ L))
\end{aligned} ( ∀ n b , dist ( iter Φ π 0 π 0 ′ n b ) ( seq Φ π 0 b ) ≤ F . C 0 ∗ F . τ ( n ∗ L )) ∧ ( ∀ δ : R , 0 < δ → ∀ n , iterCount F . C 0 F . τ L δ ≤ n → ∀ b , dist ( iter Φ π 0 π 0 ′ n b ) ( seq Φ π 0 b ) ≤ δ ) ∧ ( ∀ d : N → R , ( ∀ m b , 1 ≤ b → dist ( iter Φ π 0 π 0 ′ ( m + 1 ) b ) ( iter Φ π 0 π 0 ′ m b ) ≤ d m ) → ∀ m b , dist ( iter Φ π 0 π 0 ′ ( m + 1 ) b ) ( seq Φ π 0 b ) ≤ F . C 1 ∗ F . τ ( L − 1 ) ∗ d m / ( 1 − F . τ L ))
The proposition statement is four parts (lowest identation above) joined by ∧ \land ∧ :
A family of boundary densities is a fixed point exactly when it is the sequential filter, i.e. the first half of clause 1 (Theorem S-12). This part uses neither F nor hL as hypothesis, so holds for any block map Φ \Phi Φ .
For every iteration and every block, the convergence bound of clause 2 (Proposition S-10).
The iteration count of clause 2: from iteration iterCount on, every block is within δ \delta δ of the sequential filter (Theorem S-11).
The total-variation form of the a posteriori bound (Proposition S-15): if d m bounds the increments between iterations m + 1 and m, then the error at iteration m + 1 is at most A A A times d m, with A = C 1 τ L − 1 / ( 1 − τ L ) A = C_1\tau^{L-1}/(1-\tau^L) A = C 1 τ L − 1 / ( 1 − τ L ) .
The hypotheses of the theorem are therefore exactly F and hL. Clause 3 of P1 and the WRMS form of clause 4 are proved separately. The stopping iteration is exists_stop (Corollary S-17). The WRMS form follows from part 4 together with dist_le_wrms (Lemma S-16). The bound ∣ c i [ μ ] ∣ ≤ M e |c_i[\mu]| \le M_e ∣ c i [ μ ] ∣ ≤ M e used to obtain Γ \Gamma Γ is not formalized. We also do not formalize the notion of span complexity, instead simply show the iteration count does not take as input the trajectory length directly or indirectly, rather just the contraction data and the tolerance.
Remark (log-likelihood). By clause 1 of P1, the computed log-likelihood ∑ β ℓ β \sum_\beta\ell_\beta ∑ β ℓ β is exact at the fixed point. When the algorithm stops instead on δ ( j ) ≤ 1 \delta^{(j)} \le1 δ ( j ) ≤ 1 , each ℓ β \ell_\beta ℓ β has a small error from its initial density, adding up over the B B B blocks. The total error is of order C ( ε ) B max β E β C(\varepsilon)\,B\max_\beta E_\beta C ( ε ) B max β E β , growing linearly with N N N . We do not prove this bound here. Note that the sequential filter also has extensive-in-N N N error: its log-likelihood is a sum of N N N terms log Z k \log Z_k log Z k , each carrying a rounding error of the order of the unit roundoff u u u , so its total error is of order N u Nu N u . With the stopping tolerances at the floating-point floor, the error of PintFilter is of order B u ≤ N u Bu \le Nu B u ≤ N u , the same order in N N N up to C ( ε ) C(\varepsilon) C ( ε ) . Relative to ∣ log p ∣ |\log p| ∣ log p ∣ , which grows linearly in N N N , both errors are of order u u u and independent of N N N . We report on this relative error in our benchmarks in the main text.
Structure of the proof
Section S1.6: Mixing property. From (A3), in whichever variant is assumed, we derive the envelope condition (E) below.
Section S1.7: From mixing to block forgetting. From (E), (A1) and (A2), with Le Gland–Oudjane’s Hilbert-metric theory of filter stability,1 we derive the contraction bounds (F-abs) and (F-lip) on the block maps Φ β \Phi_\beta Φ β , with constants depending only on ( ε , L ) (\varepsilon,L) ( ε , L ) , and not on N N N .
Section S1.8: Algorithmic arguments. From these two bounds and (A4), without further measure theory, we show Proposition P1.
The only property of the model that Section S1.6 passes to the following section is the envelope condition (E): a constant ε > 0 \varepsilon> 0 ε > 0 with
ε ≤ κ Δ t ( x , y ) ≤ ε − 1 for all x , y ∈ X . (5) \varepsilon\le\kappa\Delta_t(x,y) \le\varepsilon^{-1}\qquad\text{for all }x,y\in\mathcal{X}. \tag*{(5)} ε ≤ κ Δ t ( x , y ) ≤ ε − 1 for all x , y ∈ X . (5)
Such an ε \varepsilon ε is at most 1 1 1 , since ε ≤ ε − 1 \varepsilon\le\varepsilon^{-1} ε ≤ ε − 1 . A different model that also satisfies (E), by whatever argument, can use Sections S1.7 and S1.8 as-is.
Lean: condition (E)
In PlanxAlgorithm/Envelope.lean.
The conditions on ε \varepsilon ε are grouped in the structure IsEnvelope, in the form used by the Le Gland–Oudjane mixing definition.
structure IsEnvelope (ε : ℝ) (κ : X → X → ℝ) : Prop where
eps_pos : 0 < ε
eps_le_one : ε ≤ 1
lower : ∀ x y, ε ≤ κ x y
upper : ∀ x y, κ x y ≤ ε⁻¹
The field eps_le_one follows from the two bounds when X is non-empty, kept as a separate property for convenience.
Mixing property
This section derives the envelope condition (E) from assumption (A3). Only one of the two subsections below is needed: §S1.6.1 if (A3a) is assumed, and §S1.6.2 if (A3b) is assumed. The observations play no role here.
From compactness alone
This route assumes (A3a). We argue that a continuous, strictly positive function on a compact set has a positive minimum and a finite maximum, and these two numbers give the two sides of (E).
Proposition S-2′ (Unconditional envelope). Under (A3a), (E) holds for every Δ t > 0 \Delta t > 0 Δ t > 0 with
ε 0 : = min ( m , 1 / M ) , m : = min x , y κ Δ t ( x , y ) , M : = max x , y κ Δ t ( x , y ) . \varepsilon_0 := \min(m,1/M), \qquad m := \min_{x,y}\kappa_{\Delta t}(x,y), \qquad M := \max_{x,y}\kappa_{\Delta t}(x,y). ε 0 := min ( m , 1/ M ) , m := x , y min κ Δ t ( x , y ) , M := x , y max κ Δ t ( x , y ) . All three depend on Δ t \Delta t Δ t , and we write ε 0 ( Δ t ) \varepsilon_0(\Delta t) ε 0 ( Δ t ) when relevant.
Proof. Since κ Δ t \kappa_{\Delta t} κ Δ t is continuous on the compact set X × X \mathcal{X} \times\mathcal{X} X × X , the minimum m m m and the maximum M M M are attained, and m > 0 m > 0 m > 0 by strict positivity. Hence ε 0 > 0 \varepsilon_0 > 0 ε 0 > 0 . For all x , y x,y x , y ,
ε 0 ≤ m ≤ κ Δ t ( x , y ) ≤ M ≤ ε 0 − 1 , \varepsilon_0 \le m \le\kappa_{\Delta t}(x,y) \le M \le\varepsilon_0^{-1}, ε 0 ≤ m ≤ κ Δ t ( x , y ) ≤ M ≤ ε 0 − 1 , the first inequality because ε 0 ≤ m \varepsilon_0 \le m ε 0 ≤ m , and the last because ε 0 ≤ 1 / M \varepsilon_0 \le1/M ε 0 ≤ 1/ M . This is (E) with ε = ε 0 \varepsilon= \varepsilon_0 ε = ε 0 .
Optimality. The constant ε 0 \varepsilon_0 ε 0 is the best ε \varepsilon ε constant, as a given ε > 0 \varepsilon> 0 ε > 0 satisfies (E) exactly when ε ≤ m \varepsilon\le m ε ≤ m and ε ≤ 1 / M \varepsilon\le1/M ε ≤ 1/ M .
Limit behavior. ε 0 \varepsilon_0 ε 0 behaves as expected in Δ t \Delta t Δ t . With Δ t → 0 \Delta t \to0 Δ t → 0 , the transition density concentrates near the diagonal, so m → 0 m \to0 m → 0 , M → ∞ M \to\infty M → ∞ and ε 0 → 0 \varepsilon_0 \to0 ε 0 → 0 . With Δ t → ∞ \Delta t \to\infty Δ t → ∞ , an ergodic process forgets its starting point, κ Δ t → 1 \kappa_{\Delta t} \to1 κ Δ t → 1 , and ε 0 → 1 \varepsilon_0 \to1 ε 0 → 1 . The issue of this route is therefore not the size of ε 0 \varepsilon_0 ε 0 , but that its value is not computable in closed form, contrary to the spectral gap route below.
Lean: Proposition S-2′ — KernelData.isEnvelope
In PlanxAlgorithm/Kernel.lean.
structure KernelData (X : Type*) [TopologicalSpace X] [CompactSpace X]
[MeasurableSpace X] [OpensMeasurableSpace X] (µ : Measure X)
[IsProbabilityMeasure μ] where
κ : X → X → ℝ
cont : Continuous fun p : X × X => κ p.1 p.2
pos : ∀ x y, 0 < κ x y
markov : ∀ x, ∫ y, κ x y ∂μ = 1
theorem KernelData.isEnvelope [Nonempty X] (K : KernelData X μ) :
IsEnvelope K.eps K.κ
Here K.eps is the constant min ( m , 1 / M ) \min(m,1/M) min ( m , 1/ M ) , defined from the attained extrema. The hypothesis [Nonempty X] ensures these extrema exist. The field markov, the mass condition of (A3a), is used only to prove the field eps_le_one of IsEnvelope, which the text instead obtains from ε ≤ ε − 1 \varepsilon\leq\varepsilon^{-1} ε ≤ ε − 1 .
From the spectral gap
This route assumes (A3b). For our model, the dynamics is reversible with respect to p e q p_{\mathrm{eq}} p eq by construction, and its generator has a compact resolvent, thus a discrete spectrum and a spectral gap. Whether the sampling is sparse enough depends on Δ t \Delta t Δ t , which, in the notation introduced below, corresponds to the condition δ ( Δ t ) < 1 \delta(\Delta t)<1 δ ( Δ t ) < 1 . Since the κ t \kappa_t κ t are the transition densities of a Markov process with invariant measure P e q P_{\mathrm{eq}} P eq , they satisfy, for all s , t > 0 s,t>0 s , t > 0 and x , y ∈ X x,y\in\mathcal{X} x , y ∈ X ,
∫ X κ t ( x , y ) P e q ( d y ) = 1 , κ s + t ( x , y ) = ∫ X κ s ( x , u ) κ t ( u , y ) P e q ( d u ) . (6) \int_{\mathcal{X}}\kappa_t(x,y)P_{\mathrm{eq}}(dy)=1,\qquad
\kappa_{s+t}(x,y)=\int_{\mathcal{X}}\kappa_s(x,u)\kappa_t(u,y)P_{\mathrm{eq}}(du). \tag*{(6)} ∫ X κ t ( x , y ) P eq ( d y ) = 1 , κ s + t ( x , y ) = ∫ X κ s ( x , u ) κ t ( u , y ) P eq ( d u ) . (6)
the second identity being the Chapman–Kolmogorov equation. We define the heat-kernel constant and the envelope
Θ ( t ) : = sup x κ t ( x , x ) − 1 , δ ( Δ t ) : = inf 0 < t 0 < Δ t / 2 e − λ 1 ( Δ t − 2 t 0 ) Θ ( 2 t 0 ) . \Theta(t):=\sup_x\kappa_t(x,x)-1,\qquad
\delta(\Delta t):=\inf_{0<t_0<\Delta t/2}e^{-\lambda_1(\Delta t-2t_0)}\Theta(2t_0). Θ ( t ) := x sup κ t ( x , x ) − 1 , δ ( Δ t ) := 0 < t 0 < Δ t /2 inf e − λ 1 ( Δ t − 2 t 0 ) Θ ( 2 t 0 ) .
Θ ( t ) \Theta(t) Θ ( t ) is finite because κ t \kappa_t κ t is continuous on the compact set X × X \mathcal{X}\times\mathcal{X} X × X . Heuristically, Θ ( t ) \Theta(t) Θ ( t ) measures how far the process, started at the worst possible point, still is from equilibrium after time t t t , and δ ( Δ t ) \delta(\Delta t) δ ( Δ t ) bounds how much of its starting point one step of the dynamics still remembers.
Proposition S-1 (Equilibrium envelope). Under (A3b), sup x , y ∣ κ Δ t ( x , y ) − 1 ∣ ≤ δ ( Δ t ) \sup_{x,y}|\kappa_{\Delta t}(x,y)-1|\leq\delta(\Delta t) sup x , y ∣ κ Δ t ( x , y ) − 1∣ ≤ δ ( Δ t ) .
Proof. Fix t 0 ∈ ( 0 , Δ t / 2 ) t_0\in(0,\Delta t/2) t 0 ∈ ( 0 , Δ t /2 ) and x , y ∈ X x,y\in\mathcal{X} x , y ∈ X , and write s : = Δ t − 2 t 0 s:=\Delta t-2t_0 s := Δ t − 2 t 0 , which is thus positive. The spectral gap controls functions in L 2 ( P e q ) L^2(P_{\mathrm{eq}}) L 2 ( P eq ) , but κ Δ t ( x , y ) \kappa_{\Delta t}(x,y) κ Δ t ( x , y ) is a pointwise quantity describing the process started exactly at x x x , a point mass not in L 2 L^2 L 2 . We therefore split the time Δ t \Delta t Δ t into three segments, t 0 + s + t 0 t_0+s+t_0 t 0 + s + t 0 . During the first part, the process started at x x x spreads into the density κ t 0 ( x , ⋅ ) \kappa_{t_0}(x,\cdot) κ t 0 ( x , ⋅ ) , a bounded function and hence in L 2 L^2 L 2 . By reversibility, the same holds at the other end for y y y . We then apply the spectral gap property to the middle segment, at the cost of a Θ ( 2 t 0 ) \Theta(2t_0) Θ ( 2 t 0 ) factor and the loss of 2 t 0 2t_0 2 t 0 in the exponent.
Step 1: minorization. For z ∈ X z \in\mathcal{X} z ∈ X , let g z ( u ) : = κ t 0 ( z , u ) − 1 g_z(u):=\kappa_{t_0}(z,u)-1 g z ( u ) := κ t 0 ( z , u ) − 1 . By the first identity in (CK), we have ∫ g z d P e q = 0 \int g_z\,\mathrm{d}P_{\mathrm{eq}}=0 ∫ g z d P eq = 0 . We show its norm to be controlled by Θ \Theta Θ , by expanding the square:
∥ g z ∥ L 2 ( P e q ) 2 = ∫ X ( κ t 0 ( z , u ) − 1 ) 2 P e q ( d u ) = ∫ X κ t 0 ( z , u ) 2 P e q ( d u ) − 2 ∫ X κ t 0 ( z , u ) P e q ( d u ) + 1 = ∫ X κ t 0 ( z , u ) 2 P e q ( d u ) − 1 by (CK) = ∫ X κ t 0 ( z , u ) κ t 0 ( u , z ) P e q ( d u ) − 1 by symmetry = κ 2 t 0 ( z , z ) − 1 by (CK) with s = t = t 0 ≤ Θ ( 2 t 0 ) . \begin{aligned}
\|g_z\|_{L^2(P_{\mathrm{eq}})}^2
&= \int_{\mathcal{X}} \bigl(\kappa_{t_0}(z,u)-1\bigr)^2 P_{\mathrm{eq}}(\mathrm{d}u) \\
&= \int_{\mathcal{X}} \kappa_{t_0}(z,u)^2 P_{\mathrm{eq}}(\mathrm{d}u)-2\int_{\mathcal{X}}\kappa_{t_0}(z,u)P_{\mathrm{eq}}(\mathrm{d}u)+1 \\
&= \int_{\mathcal{X}} \kappa_{t_0}(z,u)^2 P_{\mathrm{eq}}(\mathrm{d}u)-1
\qquad\text{by (CK)} \\
&= \int_{\mathcal{X}} \kappa_{t_0}(z,u)\kappa_{t_0}(u,z)P_{\mathrm{eq}}(\mathrm{d}u)-1
\qquad\text{by symmetry} \\
&= \kappa_{2t_0}(z,z)-1
\qquad\text{by (CK) with }s=t=t_0 \\
&\le\Theta(2t_0).
\end{aligned} ∥ g z ∥ L 2 ( P eq ) 2 = ∫ X ( κ t 0 ( z , u ) − 1 ) 2 P eq ( d u ) = ∫ X κ t 0 ( z , u ) 2 P eq ( d u ) − 2 ∫ X κ t 0 ( z , u ) P eq ( d u ) + 1 = ∫ X κ t 0 ( z , u ) 2 P eq ( d u ) − 1 by (CK) = ∫ X κ t 0 ( z , u ) κ t 0 ( u , z ) P eq ( d u ) − 1 by symmetry = κ 2 t 0 ( z , z ) − 1 by (CK) with s = t = t 0 ≤ Θ ( 2 t 0 ) .
Step 2: factorization. We now write κ Δ t ( x , y ) − 1 \kappa_{\Delta t}(x,y)-1 κ Δ t ( x , y ) − 1 in terms of g x g_x g x and g y g_y g y . We split twice Δ t = t 0 + ( s + t 0 ) \Delta t=t_0+(s+t_0) Δ t = t 0 + ( s + t 0 ) then s + t 0 s+t_0 s + t 0 using (CK),
κ Δ t ( x , y ) = ∫ X κ t 0 ( x , u ) κ s + t 0 ( u , y ) P e q ( d u ) = ∫ X ∫ X κ t 0 ( x , u ) κ s ( u , v ) κ t 0 ( v , y ) P e q ( d u ) P e q ( d v ) . \begin{aligned}
\kappa_{\Delta t}(x,y)
&= \int_{\mathcal{X}}\kappa_{t_0}(x,u)\kappa_{s+t_0}(u,y)P_{\mathrm{eq}}(\mathrm{d}u) \\
&= \int_{\mathcal{X}}\int_{\mathcal{X}}\kappa_{t_0}(x,u)\kappa_s(u,v)\kappa_{t_0}(v,y)P_{\mathrm{eq}}(\mathrm{d}u)P_{\mathrm{eq}}(\mathrm{d}v).
\end{aligned} κ Δ t ( x , y ) = ∫ X κ t 0 ( x , u ) κ s + t 0 ( u , y ) P eq ( d u ) = ∫ X ∫ X κ t 0 ( x , u ) κ s ( u , v ) κ t 0 ( v , y ) P eq ( d u ) P eq ( d v ) .
Substituting κ t 0 ( x , u ) = 1 + g x ( u ) \kappa_{t_0}(x,u)=1+g_x(u) κ t 0 ( x , u ) = 1 + g x ( u ) and, by symmetry, κ t 0 ( v , y ) = κ t 0 ( y , v ) = 1 + g y ( v ) \kappa_{t_0}(v,y)=\kappa_{t_0}(y,v)=1+g_y(v) κ t 0 ( v , y ) = κ t 0 ( y , v ) = 1 + g y ( v ) . Expanding the product gives four terms,
κ Δ t ( x , y ) = T 0 + T x + T y + T x y . \kappa_{\Delta t}(x,y)=T_0+T_x+T_y+T_{xy}. κ Δ t ( x , y ) = T 0 + T x + T y + T x y .
where
T 0 = ∫ X ∫ X κ s ( u , v ) P e q ( d u ) P e q ( d v ) , T x = ∫ X ∫ X g x ( u ) κ s ( u , v ) P e q ( d u ) P e q ( d v ) , T y = ∫ X ∫ X κ s ( u , v ) g y ( v ) P e q ( d u ) P e q ( d v ) , T x y = ∫ X ∫ X g x ( u ) κ s ( u , v ) g y ( v ) P e q ( d u ) P e q ( d v ) . \begin{aligned}
T_0 &= \int_{\mathcal{X}}\int_{\mathcal{X}} \kappa_s(u,v)\,P_{\mathrm{eq}}(du)\,P_{\mathrm{eq}}(dv),\\
T_x &= \int_{\mathcal{X}}\int_{\mathcal{X}} g_x(u)\,\kappa_s(u,v)\,P_{\mathrm{eq}}(du)\,P_{\mathrm{eq}}(dv),\\
T_y &= \int_{\mathcal{X}}\int_{\mathcal{X}} \kappa_s(u,v)\,g_y(v)\,P_{\mathrm{eq}}(du)\,P_{\mathrm{eq}}(dv),\\
T_{xy} &= \int_{\mathcal{X}}\int_{\mathcal{X}} g_x(u)\,\kappa_s(u,v)\,g_y(v)\,P_{\mathrm{eq}}(du)\,P_{\mathrm{eq}}(dv).
\end{aligned} T 0 T x T y T x y = ∫ X ∫ X κ s ( u , v ) P eq ( d u ) P eq ( d v ) , = ∫ X ∫ X g x ( u ) κ s ( u , v ) P eq ( d u ) P eq ( d v ) , = ∫ X ∫ X κ s ( u , v ) g y ( v ) P eq ( d u ) P eq ( d v ) , = ∫ X ∫ X g x ( u ) κ s ( u , v ) g y ( v ) P eq ( d u ) P eq ( d v ) .
All functions involved are bounded, so by Fubini we evaluate one variable at a time:
T 0 = 1 T_0=1 T 0 = 1 . Integrating over v v v , ∫ X κ s ( u , v ) P e q ( d v ) = 1 \int_{\mathcal{X}}\kappa_s(u,v)\,P_{\mathrm{eq}}(dv)=1 ∫ X κ s ( u , v ) P eq ( d v ) = 1 for every u u u , by (CK). The remaining integral over u u u is then P e q ( X ) = 1 P_{\mathrm{eq}}(\mathcal{X})=1 P eq ( X ) = 1 .
T x = 0 T_x=0 T x = 0 . Integrating over v v v first again gives 1 1 1 . Remaining is ∫ g x d P e q = 0 \int g_x\,dP_{\mathrm{eq}}=0 ∫ g x d P eq = 0 , by Step 1.
T y = 0 T_y=0 T y = 0 . Integrating over u u u first, ∫ X κ s ( u , v ) P e q ( d u ) = ∫ X κ s ( v , u ) P e q ( d u ) = 1 \int_{\mathcal{X}}\kappa_s(u,v)\,P_{\mathrm{eq}}(du)=\int_{\mathcal{X}}\kappa_s(v,u)\,P_{\mathrm{eq}}(du)=1 ∫ X κ s ( u , v ) P eq ( d u ) = ∫ X κ s ( v , u ) P eq ( d u ) = 1 , by symmetry and (CK). Remaining is ∫ g y d P e q = 0 \int g_y\,dP_{\mathrm{eq}}=0 ∫ g y d P eq = 0 .
Finally, for T x y T_{xy} T x y , we first integrate over v v v giving ∫ X κ s ( u , v ) g y ( v ) P e q ( d v ) = P s g y ( u ) \int_{\mathcal{X}}\kappa_s(u,v)\,g_y(v)\,P_{\mathrm{eq}}(dv)=P_sg_y(u) ∫ X κ s ( u , v ) g y ( v ) P eq ( d v ) = P s g y ( u ) , so
T x y = ∫ X g x ( u ) P s g y ( u ) P e q ( d u ) = ⟨ g x , P s g y ⟩ L 2 ( P e q ) . T_{xy}=\int_{\mathcal{X}}g_x(u)\,P_sg_y(u)\,P_{\mathrm{eq}}(du)=\langle g_x,P_sg_y\rangle_{L^2(P_{\mathrm{eq}})}. T x y = ∫ X g x ( u ) P s g y ( u ) P eq ( d u ) = ⟨ g x , P s g y ⟩ L 2 ( P eq ) .
Reassembling, we get
κ Δ t ( x , y ) − 1 = ⟨ g x , P s g y ⟩ L 2 ( P e q ) . \kappa_{\Delta t}(x,y)-1=\langle g_x,P_sg_y\rangle_{L^2(P_{\mathrm{eq}})}. κ Δ t ( x , y ) − 1 = ⟨ g x , P s g y ⟩ L 2 ( P eq ) .
Step 3: spectral gap. Since g y g_y g y has mean zero, the spectral gap of (A3b) gives ∥ P s g y ∥ ≤ e − λ 1 s ∥ g y ∥ \lVert P_sg_y\rVert\le e^{-\lambda_1s}\lVert g_y\rVert ∥ P s g y ∥ ≤ e − λ 1 s ∥ g y ∥ . We get
∣ κ Δ t ( x , y ) − 1 ∣ ≤ ∥ g x ∥ ∥ P s g y ∥ by Cauchy–Schwarz ≤ e − λ 1 ( Δ t − 2 t 0 ) ∥ g x ∥ ∥ g y ∥ by the spectral gap ≤ e − λ 1 ( Δ t − 2 t 0 ) Θ ( 2 t 0 ) by Step 1. \begin{aligned}
\left|\kappa_{\Delta t}(x,y)-1\right| &\le\lVert g_x\rVert\lVert P_sg_y\rVert&&\text{by Cauchy--Schwarz}\\
&\le e^{-\lambda_1(\Delta t-2t_0)}\lVert g_x\rVert\lVert g_y\rVert&&\text{by the spectral gap}\\
&\le e^{-\lambda_1(\Delta t-2t_0)}\Theta(2t_0) &&\text{by Step 1.}
\end{aligned} ∣ κ Δ t ( x , y ) − 1 ∣ ≤ ∥ g x ∥ ∥ P s g y ∥ ≤ e − λ 1 ( Δ t − 2 t 0 ) ∥ g x ∥ ∥ g y ∥ ≤ e − λ 1 ( Δ t − 2 t 0 ) Θ ( 2 t 0 ) by Cauchy–Schwarz by the spectral gap by Step 1.
This holds for every t 0 ∈ ( 0 , Δ t / 2 ) t_0\in(0,\Delta t/2) t 0 ∈ ( 0 , Δ t /2 ) and all x , y x,y x , y . As the left-hand side does not depend on t 0 t_0 t 0 , we can take the infimum over t 0 t_0 t 0 on the right, which is δ ( Δ t ) \delta(\Delta t) δ ( Δ t ) , and then the supremum over ( x , y ) (x,y) ( x , y ) on the left, giving sup x , y ∣ κ Δ t ( x , y ) − 1 ∣ ≤ δ ( Δ t ) \sup_{x,y}\left|\kappa_{\Delta t}(x,y)-1\right|\le\delta(\Delta t) sup x , y ∣ κ Δ t ( x , y ) − 1 ∣ ≤ δ ( Δ t ) .
Lean: Proposition S-1 – HeatData.abs_kappa_sub_one_le
In PlanxAlgorithm/Envelope.lean. We formalize a special case of (A3b) as the structure HeatData. We notably assumes an eigendecomposition with a discrete spectrum 0 = λ 0 < λ 1 ≤ λ 2 ≤ ⋯ 0 = \lambda_0 < \lambda_1 \le\lambda_2 \le\cdots 0 = λ 0 < λ 1 ≤ λ 2 ≤ ⋯ , eigenfunctions ϕ i \phi_i ϕ i with ϕ 0 ≡ 1 \phi_0 \equiv1 ϕ 0 ≡ 1 , and a pointwise expansion κ t ( x , y ) = ∑ i e − λ i t ϕ i ( x ) ϕ i ( y ) \kappa_t(x,y) = \sum_i e^{-\lambda_i t}\phi_i(x)\phi_i(y) κ t ( x , y ) = ∑ i e − λ i t ϕ i ( x ) ϕ i ( y ) whose diagonal tails are bounded by Θ ( t ) \Theta(t) Θ ( t ) . Such an expansion implies (A3b), with the same λ 1 \lambda_1 λ 1 and Θ \Theta Θ . (There is not spectral theorem for unbounded operator in Mathlib, which is why we have to assume the eigendecomposition as member of the structure, rather than obtain it from the operator)
structure HeatData (X : Type*) where
lam : ℕ → ℝ -- the eigenvalues
phi : ℕ → X → ℝ -- the eigenfunctions
kappa : ℝ → X → X → ℝ -- the ratio kernel
theta : ℝ → ℝ -- the heat-kernel constant
lam_zero : lam 0 = 0
phi_zero : ∀ x, phi 0 x = 1
lam_mono : Monotone lam
gap : 0 < lam 1
hasSum_kappa : ∀ t, 0 < t → ∀ x y,
HasSum (fun i => Real.exp (-lam i * t) * (phi i x * phi i y)) (kappa t x y)
diagSummable : ∀ t, 0 < t → ∀ x,
Summable fun i => Real.exp (-lam (i + 1) * t) * phi (i + 1) x ^ 2
diag_le_theta : ∀ t, 0 < t → ∀ x,
∑' i, Real.exp (-lam (i + 1) * t) * phi (i + 1) x ^ 2 ≤ theta t
theorem HeatData.abs_kappa_sub_one_le (h∆ : 0 < ∆t) (ht₀ : 0 < t₀) (h : 2 * t₀ < ∆t)
(x y : X) :
|H.kappa ∆t x y - 1| ≤ Real.exp (-H.lam 1 * (∆t - 2 * t₀)) * H.theta (2 * t₀)
The Lean statement is expressed for every admissible t 0 t_0 t 0 , with right-hand side B ( t 0 ) : = e − λ 1 ( Δ t − 2 t 0 ) Θ ( 2 t 0 ) B(t_0) := e^{-\lambda_1(\Delta t-2t_0)}\Theta(2t_0) B ( t 0 ) := e − λ 1 ( Δ t − 2 t 0 ) Θ ( 2 t 0 ) . Since the left-hand side does not depend on t 0 t_0 t 0 , the infimum step δ ( Δ t ) = inf t 0 B ( t 0 ) \delta(\Delta t) = \inf_{t_0} B(t_0) δ ( Δ t ) = inf t 0 B ( t 0 ) follows immediately, but is not formalized. In the next proposition S-2, we give the envelope ε = 1 − B ( t 0 ) \varepsilon= 1 - B(t_0) ε = 1 − B ( t 0 ) which can be made arbitrarily close to 1 − δ ( Δ t ) 1-\delta(\Delta t) 1 − δ ( Δ t ) but need not equal it if the infimum is not attained. Since every later proposition needs only ε > 0 \varepsilon> 0 ε > 0 , it is fine to not formalize this last step.
Proposition S-2 (Envelope ⇒ \Rightarrow ⇒ mixing). Given δ ( Δ t ) < 1 \delta(\Delta t) < 1 δ ( Δ t ) < 1 by A3b, the bound (E) holds with ε : = 1 − δ ( Δ t ) \varepsilon:= 1 - \delta(\Delta t) ε := 1 − δ ( Δ t ) . Consequently, for every x x x and every Borel set U U U ,
ε P e q ( U ) ≤ Q Δ t ( x , U ) ≤ ε − 1 P e q ( U ) , \varepsilon P_{\mathrm{eq}}(U) \le Q_{\Delta t}(x,U) \le\varepsilon^{-1}P_{\mathrm{eq}}(U), ε P eq ( U ) ≤ Q Δ t ( x , U ) ≤ ε − 1 P eq ( U ) ,
i.e. Q Δ t Q_{\Delta t} Q Δ t is mixing in the sense of Le Gland–Oudjane, 20043 with reference P e q P_{\mathrm{eq}} P eq and constant ε \varepsilon ε .
Proof. Write δ = δ ( Δ t ) \delta=\delta(\Delta t) δ = δ ( Δ t ) . Proposition S-1 gives, for all x , y x,y x , y ,
1 − δ ≤ κ Δ t ( x , y ) ≤ 1 + δ . 1-\delta\leq\kappa_{\Delta t}(x,y) \leq1+\delta. 1 − δ ≤ κ Δ t ( x , y ) ≤ 1 + δ .
The lower bound is ε \varepsilon ε by definition. For the upper bound, since 0 ≤ δ < 1 0\leq\delta<1 0 ≤ δ < 1 we have
( 1 − δ ) ( 1 + δ ) = 1 − δ 2 ≤ 1 , (1-\delta)(1+\delta)=1-\delta^2\leq1, ( 1 − δ ) ( 1 + δ ) = 1 − δ 2 ≤ 1 ,
hence
1 + δ ≤ 1 1 − δ = ε − 1 . 1+\delta\leq\frac{1}{1-\delta}=\varepsilon^{-1}. 1 + δ ≤ 1 − δ 1 = ε − 1 .
Together these give (E), with ε > 0 \varepsilon>0 ε > 0 because δ < 1 \delta<1 δ < 1 . For the measure form, fix x x x and a Borel set U U U . Since κ Δ t \kappa_{\Delta t} κ Δ t is the density of Q Δ t Q_{\Delta t} Q Δ t with respect to P e q P_{\mathrm{eq}} P eq ,
Q Δ t ( x , U ) = ∫ U κ Δ t ( x , y ) P e q ( d y ) . Q_{\Delta t}(x,U)=\int_U\kappa_{\Delta t}(x,y)\,P_{\mathrm{eq}}(dy). Q Δ t ( x , U ) = ∫ U κ Δ t ( x , y ) P eq ( d y ) .
Integrating the two-sided bound (E) over U U U against P e q P_{\mathrm{eq}} P eq gives
ε P e q ( U ) ≤ ∫ U κ Δ t ( x , y ) P e q ( d y ) ≤ ε − 1 P e q ( U ) . \varepsilon P_{\mathrm{eq}}(U)\leq\int_U\kappa_{\Delta t}(x,y)\,P_{\mathrm{eq}}(dy)\leq\varepsilon^{-1}P_{\mathrm{eq}}(U). ε P eq ( U ) ≤ ∫ U κ Δ t ( x , y ) P eq ( d y ) ≤ ε − 1 P eq ( U ) .
Note that neither bound depends on x x x , because (E) is uniform in both arguments. □
Lean: Proposition S-2, in two pieces
The algebraic part is in PlanxAlgorithm/Envelope.lean and the measure part in PlanxAlgorithm/Kernel.lean. In the code, the set A is the Borel set U U U of the text.
theorem envelope_of_abs_sub_one_le {δ κ : ℝ} (hδ : δ < 1) (h : |κ - 1| ≤ δ) :
1 - δ ≤ κ ∧ κ ≤ (1 - δ)⁻¹
theorem HeatData.isEnvelope [Nonempty X] (h∆ : 0 < ∆t) (ht₀ : 0 < t₀) (h : 2 * t₀ < ∆t)
(hδ : Real.exp (-H.lam 1 * (∆t - 2 * t₀)) * H.theta (2 * t₀) < 1) :
IsEnvelope (1 - Real.exp (-H.lam 1 * (∆t - 2 * t₀)) * H.theta (2 * t₀))
(H.kappa ∆t)
theorem setIntegral_le_of_isEnvelope (h : IsEnvelope ε κ)
(hκ : ∀ x, Integrable (κ x) µ) (x : X) {A : Set X} (hA : MeasurableSet A) :
ε * µ.real A ≤ ∫ y in A, κ x y ∂µ ∧
∫ y in A, κ x y ∂µ ≤ ε⁻¹ * µ.real A
General condition IsEnvelope is shared by both route to (E). The Lean statement uses real-valued integrals and measures instead of default measures: μ . r e a l A \mu.\mathrm{real}\ A μ . real A is P e q ( U ) P_{\mathrm{eq}}(U) P eq ( U ) as a real number. Mathlib measures can take values in [ 0 , ∞ ] [0,\infty] [ 0 , ∞ ] by default, making two-sided bounds with constant factors awkward to manipulate given ∞ \infty ∞ is a possible measure. Since P e q P_{\mathrm{eq}} P eq is a probability measure, every quantity here is finite, so using the real-value measure is equivalent and avoids this issue. Both bounds are free of x x x , as necessary in the proof to have a uniform (E).
Relation to the compactness route. Under (A3b), the transition density κ Δ t \kappa_{\Delta t} κ Δ t is continuous, has unit mass by (CK), and is strictly positive by Proposition S-1, since δ ( Δ t ) < 1 \delta(\Delta t)<1 δ ( Δ t ) < 1 . So (A3a) holds as well, and Proposition S-2′ applies. Since ε 0 ( Δ t ) \varepsilon_0(\Delta t) ε 0 ( Δ t ) is the largest constant for which (E) holds,
1 − δ ( Δ t ) ≤ ε 0 ( Δ t ) . 1-\delta(\Delta t)\leq\varepsilon_0(\Delta t). 1 − δ ( Δ t ) ≤ ε 0 ( Δ t ) .
The spectral route therefore does not give a larger constant. What it gives is a constructive one, computed from λ 1 \lambda_1 λ 1 and Θ \Theta Θ rather than from the unknown extrema of the transition density.
Remarks
The implemented kernel must satisfy (E) too. We have established (E) for the exact transition kernel κ Δ t \kappa_{\Delta t} κ Δ t . In the implementation, a discretized kernel κ ^ Δ t \hat{\kappa}_{\Delta t} κ ^ Δ t is used and must also verify (E). This requires some care: at small Δ t \Delta t Δ t , the exact kernel is sharply peaked, and with too few basis functions, the discretized density may show Gibb’s phenomenon/ringing, which violates (E). Therefore, basis function should be increased for small Δ t \Delta t Δ t and ringing can be checked at runtime. The change in the varepsilon bound caused by discretization are out of the scope of this proof.
The ε = 1 \varepsilon=1 ε = 1 case. If (E) holds for some ε \varepsilon ε , it also holds for any smaller ε ′ ∈ ( 0 , ε ] \varepsilon'\in(0,\varepsilon] ε ′ ∈ ( 0 , ε ] , since the interval [ ε ′ , 1 / ε ′ ] [\varepsilon',1/\varepsilon'] [ ε ′ , 1/ ε ′ ] only widens. We may therefore assume ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) from here on, at no cost: even in the degenerate case κ Δ t ≡ 1 \kappa_{\Delta t}\equiv1 κ Δ t ≡ 1 , where (E) holds with ε = 1 \varepsilon=1 ε = 1 , it also holds with any smaller ε \varepsilon ε . This assumption simplifies several steps below that divide by 1 − ε 2 1-\varepsilon^2 1 − ε 2 or similar quantities.
From mixing to block forgetting
The input of this section is the envelope condition (E) from § 4 : a non-random ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) with ε ≤ κ Δ t ≤ ε − 1 \varepsilon\leq\kappa_{\Delta t}\leq\varepsilon^{-1} ε ≤ κ Δ t ≤ ε − 1 , the same at every step.
One-step filter kernel
Let R k ( x , d x ′ ) : = Q Δ t ( x , d x ′ ) Ψ k ( x ′ ) R_k(x,dx') := Q_{\Delta t}(x,dx')\Psi_k(x') R k ( x , d x ′ ) := Q Δ t ( x , d x ′ ) Ψ k ( x ′ ) be the unnormalized one-step filter kernel, with Q Δ t Q_{\Delta t} Q Δ t the transition kernel of the latent dynamics over one observation interval and Ψ k \Psi_k Ψ k the likelihood of the k k k -th observation.
Lemma S-3 (One-step mixing). Assume (A1), (A2) and (E), and write
ν k ( d x ′ ) : = Ψ k ( x ′ ) P e q ( d x ′ ) \nu_k(dx') := \Psi_k(x')P_{\mathrm{eq}}(dx') ν k ( d x ′ ) := Ψ k ( x ′ ) P eq ( d x ′ ) for the observation-weighted reference measure. Then:
R k R_k R k is mixing in the sense of (Le Gland–Oudjane, 2004)[3 ] with the non-random constant ε \varepsilon ε and reference ν k \nu_k ν k : ε ν k ( U ) ≤ R k ( x , U ) ≤ ε − 1 ν k ( U ) \varepsilon\nu_k(U) \le R_k(x,U) \le\varepsilon^{-1}\nu_k(U) ε ν k ( U ) ≤ R k ( x , U ) ≤ ε − 1 ν k ( U ) for every x x x and every Borel set U U U .
H ( R k ) ≤ 4 log ( 1 / ε ) H(R_k) \le4\log(1/\varepsilon) H ( R k ) ≤ 4 log ( 1/ ε ) and τ k : = τ ( R k ) ≤ τ : = ( 1 − ε 2 ) / ( 1 + ε 2 ) < 1 \tau_k := \tau(R_k) \le\tau:= (1-\varepsilon^2)/(1+\varepsilon^2) < 1 τ k := τ ( R k ) ≤ τ := ( 1 − ε 2 ) / ( 1 + ε 2 ) < 1 , uniformly in k k k and in the realized observations.
For any r r r consecutive steps, τ ( R k + r − 1 : k ) ≤ τ r \tau(R_{k+r-1:k}) \le\tau^r τ ( R k + r − 1 : k ) ≤ τ r .
Proof. We use the following three results, for which we refer to (Le Gland–Oudjane, 2004)[3 ] for definitions and proofs.
The Hilbert projective metric h h h between two comparable non-zero finite measures μ , μ ′ \mu,\mu' μ , μ ′ is the logarithm of the ratio between the supremum and the infimum of μ ( U ) / μ ′ ( U ) \mu(U)/\mu'(U) μ ( U ) / μ ′ ( U ) over sets U U U of positive mass. It is scale-invariant: h ( a μ , b μ ′ ) = h ( μ , μ ′ ) h(a\mu,b\mu')=h(\mu,\mu') h ( a μ , b μ ′ ) = h ( μ , μ ′ ) for a , b > 0 a,b>0 a , b > 0 .
For a non-negative kernel R R R , H ( R ) : = sup μ , μ ′ h ( R μ , R μ ′ ) H(R):=\sup_{\mu,\mu'}h(R\mu,R\mu') H ( R ) := sup μ , μ ′ h ( R μ , R μ ′ ) is the h h h -diameter of its image. Its Birkhoff contraction coefficient τ ( R ) \tau(R) τ ( R ) is the smallest constant with h ( R μ , R μ ′ ) ≤ τ ( R ) h ( μ , μ ′ ) h(R\mu,R\mu')\le\tau(R)h(\mu,\mu') h ( R μ , R μ ′ ) ≤ τ ( R ) h ( μ , μ ′ ) . Birkhoff’s theorem gives τ ( R ) = tanh ( H ( R ) / 4 ) \tau(R)=\tanh(H(R)/4) τ ( R ) = tanh ( H ( R ) /4 ) .
τ \tau τ is submultiplicative under composition. We write R k + r − 1 : k : = R k + r − 1 ⋯ R k R_{k+r-1:k}:=R_{k+r-1}\cdots R_k R k + r − 1 : k := R k + r − 1 ⋯ R k for the composite of r r r consecutive steps.
Part (1). By (A1), Ψ k \Psi_k Ψ k is non-negative and measurable, and since κ Δ t \kappa_{\Delta t} κ Δ t is the density of Q Δ t Q_{\Delta t} Q Δ t with respect to P e q P_{\mathrm{eq}} P eq , we have
R k ( x , U ) = ∫ U Ψ k ( x ′ ) κ Δ t ( x , x ′ ) P e q ( d x ′ ) . R_k(x,U)=\int_U\Psi_k(x')\kappa_{\Delta t}(x,x')P_{\mathrm{eq}}(dx'). R k ( x , U ) = ∫ U Ψ k ( x ′ ) κ Δ t ( x , x ′ ) P eq ( d x ′ ) .
Note that x x x only appears in κ Δ t ( x , ⋅ ) \kappa_{\Delta t}(x,\cdot) κ Δ t ( x , ⋅ ) . With the integrant non-negative, we can apply (E) under the integral sign, replacing κ Δ t ( x , x ′ ) \kappa_{\Delta t}(x,x') κ Δ t ( x , x ′ ) by ε \varepsilon ε and ε − 1 \varepsilon^{-1} ε − 1 , yielding
ε ∫ U Ψ k d P e q ≤ R k ( x , U ) ≤ ε − 1 ∫ U Ψ k d P e q , \varepsilon\int_U \Psi_k\,dP_{\mathrm{eq}} \le R_k(x,U) \le\varepsilon^{-1}\int_U \Psi_k\,dP_{\mathrm{eq}}, ε ∫ U Ψ k d P eq ≤ R k ( x , U ) ≤ ε − 1 ∫ U Ψ k d P eq ,
Both the integrals are finite, since κ Δ t ≤ ε − 1 \kappa_{\Delta t} \le\varepsilon^{-1} κ Δ t ≤ ε − 1 and Ψ k \Psi_k Ψ k is P e q P_{\mathrm{eq}} P eq -integrable by (A2). Substituting ν \nu ν , we get
ε ν k ( U ) ≤ R k ( x , U ) ≤ ε − 1 ν k ( U ) . \varepsilon\nu_k(U) \le R_k(x,U) \le\varepsilon^{-1}\nu_k(U). ε ν k ( U ) ≤ R k ( x , U ) ≤ ε − 1 ν k ( U ) .
The bound in this inequality no longer depend on x x x , i.e., the constant ε \varepsilon ε is a property of the propagator alone, and the observation Y t k Y_{t_k} Y t k has been absorbed into the finite, non-zero, reference measure ν k \nu_k ν k .
Part (2). Let μ , μ ′ \mu,\mu' μ , μ ′ be finite non-zero measures. Integrating part (1) against μ \mu μ gives
ε μ ( X ) ν k ( U ) ≤ ( R k μ ) ( U ) ≤ ε − 1 μ ( X ) ν k ( U ) , \varepsilon\mu(\mathcal{X})\nu_k(U) \le(R_k\mu)(U) \le\varepsilon^{-1}\mu(\mathcal{X})\nu_k(U), ε μ ( X ) ν k ( U ) ≤ ( R k μ ) ( U ) ≤ ε − 1 μ ( X ) ν k ( U ) ,
and likewise for μ ′ \mu' μ ′ . Hence, for every U U U with ν k ( U ) > 0 \nu_k(U)>0 ν k ( U ) > 0 ,
ε 2 μ ( X ) μ ′ ( X ) ≤ ( R k μ ) ( U ) ( R k μ ′ ) ( U ) ≤ ε − 2 μ ( X ) μ ′ ( X ) . \varepsilon^2\frac{\mu(\mathcal{X})}{\mu'(\mathcal{X})}
\le\frac{(R_k\mu)(U)}{(R_k\mu')(U)}
\le\varepsilon^{-2}\frac{\mu(\mathcal{X})}{\mu'(\mathcal{X})}. ε 2 μ ′ ( X ) μ ( X ) ≤ ( R k μ ′ ) ( U ) ( R k μ ) ( U ) ≤ ε − 2 μ ′ ( X ) μ ( X ) .
Sets with ν k ( U ) = 0 \nu_k(U)=0 ν k ( U ) = 0 receive zero mass under both images, and do not enter h h h . The ratio of the supremum to the infimum of this quotient is therefore at most ε − 4 \varepsilon^{-4} ε − 4 , so
H ( R k ) ≤ log ε − 4 = 4 log ( 1 / ε ) . H(R_k) \le\log\varepsilon^{-4} = 4\log(1/\varepsilon). H ( R k ) ≤ log ε − 4 = 4 log ( 1/ ε ) .
By Birkhoff’s theorem, and since tanh \tanh tanh is increasing,
τ k = tanh [ H ( R k ) 4 ] ≤ tanh [ log ( 1 / ε ) ] = ε − 1 − ε ε − 1 + ε = 1 − ε 2 1 + ε 2 = τ , \tau_k = \tanh\left[\frac{H(R_k)}{4}\right] \le\tanh[\log(1/\varepsilon)] = \frac{\varepsilon^{-1}-\varepsilon}{\varepsilon^{-1}+\varepsilon} = \frac{1-\varepsilon^2}{1+\varepsilon^2} = \tau, τ k = tanh [ 4 H ( R k ) ] ≤ tanh [ log ( 1/ ε )] = ε − 1 + ε ε − 1 − ε = 1 + ε 2 1 − ε 2 = τ ,
and τ ∈ ( 0 , 1 ) \tau\in(0,1) τ ∈ ( 0 , 1 ) because ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . The bound depends on ε \varepsilon ε only, hence neither on k k k nor on the realized observations.
Part (3). The contraction coefficient is submultiplicative under composition, so
τ ( R k + r − 1 : k ) ≤ ∏ k ′ = k k + r − 1 τ k ′ ≤ τ r . \tau(R_{k+r-1:k}) \le\prod_{k'=k}^{k+r-1}\tau_{k'} \le\tau^r. τ ( R k + r − 1 : k ) ≤ k ′ = k ∏ k + r − 1 τ k ′ ≤ τ r .
Table 1.
(hΨint : Integrable Ψ µ) (x : X) {A : Set X} (hA : MeasurableSet A) :
ε * (∫ y in A, Ψ y ∂µ) ≤ ∫ y in A, Ψ y * κ x y ∂µ ∧
∫ y in A, Ψ y * κ x y ∂µ ≤ ε⁻¹ * (∫ y in A, Ψ y ∂µ)
Part (2) is not formalized, as it depends on Birkhoff’s contraction theorem, which Mathlib does not have. We instead have the conclusion as member of the structure BlockForgetting below.
Block operator
Definition (Block operator). Φ β : P ( X ) → P ( X ) \Phi_\beta: \mathcal{P}(\mathcal{X}) \to\mathcal{P}(\mathcal{X}) Φ β : P ( X ) → P ( X ) is the measure-level map realized by BlockFilter on the segment Y I β Y_{I_\beta} Y I β : the composition of the L L L normalized predict–update operators. For j j j consecutive blocks, Φ β [ j ] : = Φ β + j − 1 ∘ ⋯ ∘ Φ β \Phi_\beta^{[j]} := \Phi_{\beta+j-1} \circ\cdots\circ\Phi_\beta Φ β [ j ] := Φ β + j − 1 ∘ ⋯ ∘ Φ β , a composite of j L jL j L one-step kernels, and Φ β [ 0 ] : = i d \Phi_\beta^{[0]} := \mathrm{id} Φ β [ 0 ] := id .
We first check that Φ β \Phi_\beta Φ β is well defined. By Lemma S-3(1) with U = X U = \mathcal{X} U = X , for every non-zero finite measure μ \mu μ ,
ε μ ( X ) ν k ( X ) ≤ ( R k μ ) ( X ) ≤ ε − 1 μ ( X ) ν k ( X ) , \varepsilon\mu(\mathcal{X}) \nu_k(\mathcal{X}) \le(R_k\mu)(\mathcal{X}) \le\varepsilon^{-1}\mu(\mathcal{X}) \nu_k(\mathcal{X}), ε μ ( X ) ν k ( X ) ≤ ( R k μ ) ( X ) ≤ ε − 1 μ ( X ) ν k ( X ) ,
and ν k ( X ) ∈ ( 0 , ∞ ) \nu_k(\mathcal{X}) \in(0,\infty) ν k ( X ) ∈ ( 0 , ∞ ) by (A2). So the normalizing constant is positive and finite at every step, and Φ β \Phi_\beta Φ β is a well-defined map from P ( X ) \mathcal{P}(\mathcal{X}) P ( X ) to itself.
Lemma S-4 (Block forgetting). Under (A1), (A2), (E), for all μ , μ ′ ∈ P ( X ) \mu, \mu' \in\mathcal{P}(\mathcal{X}) μ , μ ′ ∈ P ( X ) , every β \beta β and every j ≥ 1 j \ge1 j ≥ 1 :
(abs) ∥ Φ β [ j ] ( μ ) − Φ β [ j ] ( μ ′ ) ∥ ≤ 8 log ( 1 / ε ) log 3 τ j L − 1 = C 0 τ j L , where C 0 : = 8 log ( 1 / ε ) τ log 3 , (lip) ∥ Φ β [ j ] ( μ ) − Φ β [ j ] ( μ ′ ) ∥ ≤ 2 ε 2 log 3 τ j L − 1 ∥ μ − μ ′ ∥ . \begin{aligned}
\text{(abs)}\qquad\lVert\Phi_\beta^{[j]}(\mu) - \Phi_\beta^{[j]}(\mu')\rVert&\le\frac{8\log(1/\varepsilon)}{\log3}\tau^{jL-1} = C_0\tau^{jL}, \qquad\text{where } C_0 := \frac{8\log(1/\varepsilon)}{\tau\log3},\\
\text{(lip)}\qquad\lVert\Phi_\beta^{[j]}(\mu) - \Phi_\beta^{[j]}(\mu')\rVert&\le\frac{2}{\varepsilon^2\log3}\tau^{jL-1}\lVert\mu-\mu'\rVert.
\end{aligned} (abs) ∥ Φ β [ j ] ( μ ) − Φ β [ j ] ( μ ′ )∥ (lip) ∥ Φ β [ j ] ( μ ) − Φ β [ j ] ( μ ′ )∥ ≤ log 3 8 log ( 1/ ε ) τ j L − 1 = C 0 τ j L , where C 0 := τ log 3 8 log ( 1/ ε ) , ≤ ε 2 log 3 2 τ j L − 1 ∥ μ − μ ′ ∥ . Proof. Besides the facts recalled before Lemma S-3, we use two comparisons between h h h and total variation from (Le Gland–Oudjane, 2004)[3 ] , where both bounds of the lemma appear as Theorem 4.1 and Corollary 4.2. For a kernel R R R mixing with constant ε \varepsilon ε and probability measures μ , μ ′ \mu,\mu' μ , μ ′ ,
h ( R μ , R μ ′ ) ≤ ε − 2 ∥ μ − μ ′ ∥ , h(R\mu,R\mu') \le\varepsilon^{-2}\lVert\mu-\mu'\rVert, h ( R μ , R μ ′ ) ≤ ε − 2 ∥ μ − μ ′ ∥ , and for non-zero finite measures μ , μ ′ \mu,\mu' μ , μ ′ with normalizations μ ˉ , μ ˉ ′ \bar{\mu},\bar{\mu}' μ ˉ , μ ˉ ′ ,
∥ μ ˉ − μ ˉ ′ ∥ ≤ 2 log 3 h ( μ , μ ′ ) . \lVert\bar{\mu}-\bar{\mu}'\rVert\le\frac{2}{\log3}h(\mu,\mu'). ∥ μ ˉ − μ ˉ ′ ∥ ≤ log 3 2 h ( μ , μ ′ ) .
Let η : = R ( β + j ) L : β L + 1 μ \eta:= R_{(\beta+j)L:\beta L+1}\mu η := R ( β + j ) L : β L + 1 μ and η ′ : = R ( β + j ) L : β L + 1 μ ′ \eta' := R_{(\beta+j)L:\beta L+1}\mu' η ′ := R ( β + j ) L : β L + 1 μ ′ . Since h h h is scale-invariant, and normalizing at each step only rescales, Φ β [ j ] ( μ ) \Phi_{\beta}^{[j]}(\mu) Φ β [ j ] ( μ ) and Φ β [ j ] ( μ ′ ) \Phi_{\beta}^{[j]}(\mu') Φ β [ j ] ( μ ′ ) are the normalizations of η \eta η and η ′ \eta' η ′ .
Step 1: the first kernel. By the first comparison, and by Lemma S-3(2),
h ( R β L + 1 μ , R β L + 1 μ ′ ) ≤ min { ε − 2 ∥ μ − μ ′ ∥ , 4 log ( 1 / ε ) } . h(R_{\beta L+1}\mu, R_{\beta L+1}\mu') \le\min\left\{\varepsilon^{-2}\lVert\mu-\mu'\rVert,\,4\log(1/\varepsilon)\right\}. h ( R β L + 1 μ , R β L + 1 μ ′ ) ≤ min { ε − 2 ∥ μ − μ ′ ∥ , 4 log ( 1/ ε ) } .
Step 2: the remaining j L − 1 jL-1 j L − 1 kernels. By Lemma S-3(2) and (3),
h ( η , η ′ ) ≤ τ j L − 1 h ( R β L + 1 μ , R β L + 1 μ ′ ) . h(\eta,\eta') \le\tau^{jL-1}h(R_{\beta L+1}\mu,R_{\beta L+1}\mu'). h ( η , η ′ ) ≤ τ j L − 1 h ( R β L + 1 μ , R β L + 1 μ ′ ) .
Step 3: back to total variation. By the second comparison,
∥ Φ β [ j ] ( μ ) − Φ β [ j ] ( μ ′ ) ∥ ≤ 2 log 3 τ j L − 1 h ( R β L + 1 μ , R β L + 1 μ ′ ) . \left\lVert\Phi_{\beta}^{[j]}(\mu)-\Phi_{\beta}^{[j]}(\mu')\right\rVert\le\frac{2}{\log3}\tau^{jL-1}h(R_{\beta L+1}\mu,R_{\beta L+1}\mu'). Φ β [ j ] ( μ ) − Φ β [ j ] ( μ ′ ) ≤ log 3 2 τ j L − 1 h ( R β L + 1 μ , R β L + 1 μ ′ ) .
Inserting the second branch of Step 1 gives (abs),
8 log ( 1 / ε ) log 3 τ j L − 1 = C 0 τ j L , \frac{8\log(1/\varepsilon)}{\log3}\tau^{jL-1}=C_0\tau^{jL}, log 3 8 log ( 1/ ε ) τ j L − 1 = C 0 τ j L ,
and inserting the first branch gives (lip),
2 ε 2 log 3 τ j L − 1 ∥ μ − μ ′ ∥ . \frac{2}{\varepsilon^2\log3}\tau^{jL-1}\lVert\mu-\mu'\rVert. ε 2 log 3 2 τ j L − 1 ∥ μ − μ ′ ∥ .
Contraction bounds
Section S1.8 uses Sections S1.6 and S1.7 only through two bounds on the block maps. With τ \tau τ , C 0 C_0 C 0 , C 1 C_1 C 1 as in Lemma S-4, for all μ , μ ′ ∈ P ( X ) \mu,\mu'\in\mathcal{P}(\mathcal{X}) μ , μ ′ ∈ P ( X ) , every β \beta β and every j ≥ 0 j\ge0 j ≥ 0 ,
∥ Φ β [ j ] ( μ ) − Φ β [ j ] ( μ ′ ) ∥ ≤ e ( j ) : = min { 2 , C 0 τ j L } , (7) \left\lVert\Phi_{\beta}^{[j]}(\mu)-\Phi_{\beta}^{[j]}(\mu')\right\rVert\le e(j):=\min\{2,C_0\tau^{jL}\}, \tag*{(7)} Φ β [ j ] ( μ ) − Φ β [ j ] ( μ ′ ) ≤ e ( j ) := min { 2 , C 0 τ j L } , (7)
∥ Φ β [ j ] ( μ ) − Φ β [ j ] ( μ ′ ) ∥ ≤ C 1 τ j L − 1 ∥ μ − μ ′ ∥ . (8) \left\lVert\Phi_{\beta}^{[j]}(\mu)-\Phi_{\beta}^{[j]}(\mu')\right\rVert\le C_1\tau^{jL-1}\lVert\mu-\mu'\rVert. \tag*{(8)} Φ β [ j ] ( μ ) − Φ β [ j ] ( μ ′ ) ≤ C 1 τ j L − 1 ∥ μ − μ ′ ∥ . (8)
For j ≥ 1 j\ge1 j ≥ 1 , these are Lemma S-4; the branch 2 in e ( j ) e(j) e ( j ) is the trivial bound on probability measures. The constants depend on ε \varepsilon ε alone, so e ( j ) e(j) e ( j ) depends only on ( ε , L , j ) (\varepsilon,L,j) ( ε , L , j ) , and not on β \beta β , B B B , N N N or the observations. It decays geometrically in j j j .
The case j = 0 j=0 j = 0 . At j = 0 j=0 j = 0 , Φ β [ 0 ] \Phi_{\beta}^{[0]} Φ β [ 0 ] is the identity, and both bounds reduce to facts about the constants. (F-abs) reads ∥ μ − μ ′ ∥ ≤ min { 2 , C 0 } \lVert\mu-\mu'\rVert\le\min\{2,C_0\} ∥ μ − μ ′ ∥ ≤ min { 2 , C 0 } , which holds if C 0 ≥ 2 C_0\ge2 C 0 ≥ 2 . (F-lip) reads ∥ μ − μ ′ ∥ ≤ C 1 τ − 1 ∥ μ − μ ′ ∥ \lVert\mu-\mu'\rVert\le C_1\tau^{-1}\lVert\mu-\mu'\rVert ∥ μ − μ ′ ∥ ≤ C 1 τ − 1 ∥ μ − μ ′ ∥ , which holds if C 1 ≥ 1 C_1\ge1 C 1 ≥ 1 , since τ < 1 \tau<1 τ < 1 . Both hold:
For C 0 C_0 C 0 , let g ( ε ) : = log ( 1 / ε ) − ( 1 − ε 2 ) / 2 g(\varepsilon) := \log(1/\varepsilon) - (1-\varepsilon^2)/2 g ( ε ) := log ( 1/ ε ) − ( 1 − ε 2 ) /2 . Then g ( 1 ) = 0 g(1) = 0 g ( 1 ) = 0 and g ′ ( ε ) = − 1 / ε + ε ≤ 0 g'(\varepsilon) = -1/\varepsilon+ \varepsilon\le0 g ′ ( ε ) = − 1/ ε + ε ≤ 0 on ( 0 , 1 ] (0,1] ( 0 , 1 ] , so g ≥ 0 g \ge0 g ≥ 0 , that is, log ( 1 / ε ) ≥ ( 1 − ε 2 ) / 2 \log(1/\varepsilon) \ge(1-\varepsilon^2)/2 log ( 1/ ε ) ≥ ( 1 − ε 2 ) /2 . Hence
C 0 = 8 log ( 1 / ε ) ( 1 + ε 2 ) ( 1 − ε 2 ) log 3 ≥ 4 ( 1 + ε 2 ) log 3 > 2. C_0 = \frac{8\log(1/\varepsilon)(1+\varepsilon^2)}{(1-\varepsilon^2)\log3} \ge\frac{4(1+\varepsilon^2)}{\log3} > 2. C 0 = ( 1 − ε 2 ) log 3 8 log ( 1/ ε ) ( 1 + ε 2 ) ≥ log 3 4 ( 1 + ε 2 ) > 2.
Lean: the contraction bounds (F-abs), (F-lip)
In PlanxAlgorithm/Relaxation.lean. Since the (Le Gland–Oudjane, 2004)[3 ] results are not formalized, as discussed in the previous box, they are taken as hypothesis as member of the structure BlockForgetting. In the code, n n n is the number j j j of consecutive blocks composed, and b b b the index β \beta β of the first of them.
structure BlockForgetting (Φ : N → S → S) (L : N) where
τ : R
C₀ : R
C₁ : R
τ_pos : 0 < τ
τ_lt_one : τ < 1
C₀_nonneg : 0 ≤ C₀
C₁_nonneg : 0 ≤ C₁
abs : ∀ b n μ μ’, dist (comp Φ b n μ) (comp Φ b n μ’) ≤ C₀ * τ ^ (n * L)
lip : ∀ b n μ μ’,
dist (comp Φ b n μ) (comp Φ b n μ’) ≤ C₁ * τ ^ (n * L - 1) * dist μ μ’
We omit deliberately the trivial branch min { 2 , ⋅ } \min\{2,\cdot\} min { 2 , ⋅ } , as it would need a dist ≤ 2 \operatorname{dist} \le2 dist ≤ 2 field, and as it is only a quirk of the total-variation and contributes to no bound in other sections. We also do not carry ε \varepsilon ε since it enters only through τ \tau τ , C 0 C_0 C 0 , C 1 C_1 C 1 . The fields abs and lip range over every n n n , including 0 0 0 ; this is the case j = 0 j = 0 j = 0 above. At j = 0 j = 0 j = 0 , Lean’s natural-number subtraction gives n ∗ L − 1 = 0 n * L - 1 = 0 n ∗ L − 1 = 0 , so lip reads dist ≤ C 1 dist \operatorname{dist} \le C_1\operatorname{dist} dist ≤ C 1 dist , which needs C 1 ≥ 1 C_1 \ge1 C 1 ≥ 1 . The field τ_pos corresponds to ε < 1 \varepsilon< 1 ε < 1 .
Algorithmic arguments
From previous Sections S1.6 and S1.7, we take two results: each block map Φ β \Phi_\beta Φ β is a well-defined map on P ( X ) \mathcal{P}(X) P ( X ) , and the contraction bounds (F-abs) and (F-lip) hold, with constants depending on ε \varepsilon ε alone, and not on N N N , B B B , β \beta β , the observations or π ˉ 0 \bar{\pi}_0 π ˉ 0 . The bounds are needed only for the rates, and nothing else about measures or kernels is used below.
WRMS norm definition. The stopping rule measures changes of coefficient vectors in R N b \mathbb{R}^{N_b} R N b with the weighted root-mean-square norm of the implementation. For a reference vector y ∈ R N b y \in\mathbb{R}^{N_b} y ∈ R N b ,
∥ v ∥ W R M S , y = N b − 1 / 2 ∥ W y v ∥ ℓ 2 , W y = diag ( w 1 , … , w N b ) , w i = ( atol + rtol ⋅ ∣ y i ∣ ) − 1 , \lVert v\rVert_{\mathrm{WRMS},y}=N_b^{-1/2}\lVert W_yv\rVert_{\ell_2},\qquad W_y=\operatorname{diag}(w_1,\ldots,w_{N_b}),\qquad w_i=(\operatorname{atol}+\operatorname{rtol}\cdot\lvert y_i\rvert)^{-1}, ∥ v ∥ WRMS , y = N b − 1/2 ∥ W y v ∥ ℓ 2 , W y = diag ( w 1 , … , w N b ) , w i = ( atol + rtol ⋅ ∣ y i ∣ ) − 1 ,
with tolerances atol > 0 \operatorname{atol}>0 atol > 0 and rtol ≥ 0 \operatorname{rtol}\ge0 rtol ≥ 0 , so that 0 < w i ≤ 1 / atol 0<w_i\le1/\operatorname{atol} 0 < w i ≤ 1/ atol . Since the weights are strictly positive, this is a norm on R N b \mathbb{R}^{N_b} R N b for each fixed y y y .
We now write the algorithms described in Section S1.1 as recursions on the density at the start of each block, with one call to BlockFilter on block β \beta β being one application of Φ β \Phi_\beta Φ β . SequentialFilter runs the blocks one after another, each starting from the output of the previous one. PintFilter starts every block β ≥ 1 \beta\ge1 β ≥ 1 from the trial density π ˉ 0 \bar{\pi}_0 π ˉ 0 at iteration 0. At iteration j + 1 j+1 j + 1 , it runs each block from the density its predecessor produced at iteration j j j . In both algorithms the first block starts from π 0 \pi_0 π 0 :
p 0 s e q = π 0 , p β + 1 s e q = Φ β ( p β s e q ) , p^{\mathrm{seq}}_0=\pi_0,\qquad p^{\mathrm{seq}}_{\beta+1}=\Phi_\beta\left(p^{\mathrm{seq}}_\beta\right), p 0 seq = π 0 , p β + 1 seq = Φ β ( p β seq ) ,
p 0 ( 0 ) = π 0 , p β + 1 ( 0 ) = π ˉ 0 , p^{(0)}_0=\pi_0,\qquad p^{(0)}_{\beta+1}=\bar{\pi}_0, p 0 ( 0 ) = π 0 , p β + 1 ( 0 ) = π ˉ 0 ,
p 0 ( j + 1 ) = π 0 , p β + 1 ( j + 1 ) = Φ β ( p β ( j ) ) . p^{(j+1)}_0=\pi_0,\qquad p^{(j+1)}_{\beta+1}=\Phi_\beta\left(p^{(j)}_\beta\right). p 0 ( j + 1 ) = π 0 , p β + 1 ( j + 1 ) = Φ β ( p β ( j ) ) .
Note that the block count B B B does not appear: B B B only truncates the index range, and every statement below is uniform in β \beta β .
Table Lean.
The state type S S S is an arbitrary type, with [PseudoMetricSpace S] added only where a rate is stated. Mathlib has SignedMeasure.totalVariation as a measure but no total-variation distance on probability measures, so instantiating at P ( X ) \mathcal{P}(X) P ( X ) would mean building that metric first, but we do not need it for the argument, so we do not do so. This also avoids the question of the TV normalization convention, i.e., ∥ μ − μ ′ ∥ ≤ 2 \lVert\mu-\mu'\rVert\le2 ∥ μ − μ ′ ∥ ≤ 2 versus ≤ 1 \le1 ≤ 1 . Blocks are indexed by N \mathbb{N} N rather than Fin B, and all indices are additive, so that no truncated subtraction appears inside an induction.
Reduction and unrolling
Lemma S-5 (Reduction). If p β ( j ) = p β s e q p_\beta^{(j)} = p_\beta^{\mathrm{seq}} p β ( j ) = p β seq for every β \beta β , then the filtered densities and log-likelihood at iteration j j j are exactly those of the sequential filter.
Proof. Both algorithms compute each block’s filtered densities and normalizers with BlockFilter, from the block’s initial condition and its observations. The observations are the same, and by hypothesis so are the initial conditions.
Lemma S-6 (Staggered chain). Let P : N → S P : \mathbb{N} \to S P : N → S satisfy P ( c + 1 ) = Φ c ( P ( c ) ) P(c+1)=\Phi_c(P(c)) P ( c + 1 ) = Φ c ( P ( c )) for all c c c . Then P ( β + j ) = Φ β [ j ] ( P ( β ) ) P(\beta+j)=\Phi_\beta^{[j]}(P(\beta)) P ( β + j ) = Φ β [ j ] ( P ( β )) for all β , j \beta,j β , j .
Proof. By induction on j j j . For j = 0 j=0 j = 0 , both sides equal P ( β ) P(\beta) P ( β ) , since Φ β [ 0 ] = id \Phi_\beta^{[0]}=\operatorname{id} Φ β [ 0 ] = id . For the step from j j j to j + 1 j+1 j + 1 ,
P ( β + j + 1 ) = Φ β + j ( P ( β + j ) ) by the hypothesis on P = Φ β + j ( Φ β [ j ] ( P ( β ) ) ) by the induction hypothesis = Φ β [ j + 1 ] ( P ( β ) ) by the definition of Φ β [ j + 1 ] . \begin{aligned}
P(\beta+j+1) &= \Phi_{\beta+j}(P(\beta+j)) && \text{by the hypothesis on }P\\
&= \Phi_{\beta+j}\left(\Phi_\beta^{[j]}(P(\beta))\right) && \text{by the induction hypothesis}\\
&= \Phi_\beta^{[j+1]}(P(\beta)) && \text{by the definition of }\Phi_\beta^{[j+1]}.
\end{aligned} P ( β + j + 1 ) = Φ β + j ( P ( β + j )) = Φ β + j ( Φ β [ j ] ( P ( β )) ) = Φ β [ j + 1 ] ( P ( β )) by the hypothesis on P by the induction hypothesis by the definition of Φ β [ j + 1 ] .
Applied to P = p s e q P=p^{\mathrm{seq}} P = p seq , whose recursion has exactly this form, Lemma S-6 gives the semigroup identity p β + j s e q = Φ β [ j ] ( p β s e q ) p_{\beta+j}^{\mathrm{seq}}=\Phi_\beta^{[j]}(p_\beta^{\mathrm{seq}}) p β + j seq = Φ β [ j ] ( p β seq ) .
Lemma S-7 (Diagonal unrolling). For all β , m , j \beta,m,j β , m , j : p β + m ( j + m ) = Φ β [ m ] ( p β ( j ) ) p_{\beta+m}^{(j+m)}=\Phi_\beta^{[m]}(p_\beta^{(j)}) p β + m ( j + m ) = Φ β [ m ] ( p β ( j ) ) .
Proof. Fix β \beta β and j j j , and argue by induction on m m m . For m = 0 m=0 m = 0 , both sides equal p β ( j ) p_\beta^{(j)} p β ( j ) , since Φ β [ 0 ] = id \Phi_\beta^{[0]}=\operatorname{id} Φ β [ 0 ] = id . For the step from m m m to m + 1 m+1 m + 1 ,
p β + m + 1 ( j + m + 1 ) = Φ β + m ( p β + m ( j + m ) ) by the recursion for p β + 1 ( j + 1 ) = Φ β + m ( Φ β [ m ] ( p β ( j ) ) ) by the induction hypothesis = Φ β [ m + 1 ] ( p β ( j ) ) by the definition of Φ β [ m + 1 ] . \begin{aligned}
p_{\beta+m+1}^{(j+m+1)} &= \Phi_{\beta+m}\left(p_{\beta+m}^{(j+m)}\right) && \text{by the recursion for }p_{\beta+1}^{(j+1)}\\
&= \Phi_{\beta+m}\left(\Phi_\beta^{[m]}(p_\beta^{(j)})\right) && \text{by the induction hypothesis}\\
&= \Phi_\beta^{[m+1]}(p_\beta^{(j)}) && \text{by the definition of }\Phi_\beta^{[m+1]}.
\end{aligned} p β + m + 1 ( j + m + 1 ) = Φ β + m ( p β + m ( j + m ) ) = Φ β + m ( Φ β [ m ] ( p β ( j ) ) ) = Φ β [ m + 1 ] ( p β ( j ) ) by the recursion for p β + 1 ( j + 1 ) by the induction hypothesis by the definition of Φ β [ m + 1 ] .
We can understand the Lemma S-7 result as follows. Taking the starting iteration to be 0, it gives p β ( j ) = Φ [ j ] p β − j ( 0 ) p_{\beta}^{(j)}=\Phi^{[j]}p_{\beta-j}^{(0)} p β ( j ) = Φ [ j ] p β − j ( 0 ) for β ≥ j \beta\ge j β ≥ j : the initial condition of block β \beta β at iteration j j j is obtained from the iteration-0 state of block β − j \beta-j β − j , followed by j L jL j L consecutive filtering steps, using the observations Y ( β − j ) L + 1 : β L Y_{(\beta-j)L+1:\beta L} Y ( β − j ) L + 1 : β L .
For β > j \beta> j β > j , that starting state is the trial density π ˉ 0 \bar{\pi}_0 π ˉ 0 . In other words, the only wrong input is the trial density π ˉ 0 \bar{\pi}_0 π ˉ 0 , and each iteration moves it one block further upstream of block β \beta β , behind L L L more filtering steps. Since the filter forgets its initial condition geometrically (Lemma S-4), its influence on block β \beta β shrinks by a factor τ L \tau^L τ L per iteration; this is the mechanism behind Proposition S-10. Once j ≥ β j \ge\beta j ≥ β , it has been pushed past the first block, which starts from the correct π 0 \pi_0 π 0 , and block β \beta β is exact; this is Lemma S-8 below.
Table ? (PDF p. 59).
theorem comp_of_step (P : N → S) (h : ∀ c, P (c + 1) = Φ c (P c)) (b n : N) :
P (b + n) = comp Φ b n (P b)
theorem seq_add (b n : N) : seq Φ π₀ (b + n) = comp Φ b n (seq Φ π₀ b)
theorem iter_add (b m n : N) :
iter Φ π₀ π₀’ (n + m) (b + m) = comp Φ b m (iter Φ π₀ π₀’ n b)
theorem iter_add_zero (b n : N) :
iter Φ π₀ π₀’ n (b + n) = comp Φ b n (iter Φ π₀ π₀’ 0 b)
iter_add_zero is the case j = 0 j=0 j = 0 of iter_add, as used in Proposition S-10 proof.
Lemma S-8 (Exactness of the leading blocks). If β ≤ j \beta\le j β ≤ j then p β ( j ) = p β s e q p_{\beta}^{(j)}=p_{\beta}^{\mathrm{seq}} p β ( j ) = p β seq .
Proof. We proceed by induction on β \beta β . For β = 0 \beta=0 β = 0 , both sides equal π 0 \pi_0 π 0 , since the first block starts from π 0 \pi_0 π 0 at every iteration. For the step, suppose the claim holds for β \beta β and every j ≥ β j \ge\beta j ≥ β , and let β + 1 ≤ j \beta+1 \le j β + 1 ≤ j . Then j ≥ 1 j \ge1 j ≥ 1 , so we can write j = m + 1 j=m+1 j = m + 1 with β ≤ m \beta\le m β ≤ m , and
p β + 1 ( m + 1 ) = Φ β ( p β ( m ) ) p_{\beta+1}^{(m+1)}=\Phi_\beta\left(p_\beta^{(m)}\right) p β + 1 ( m + 1 ) = Φ β ( p β ( m ) ) by the recursion
= Φ β ( p β s e q ) =\Phi_\beta\left(p_\beta^{\mathrm{seq}}\right) = Φ β ( p β seq ) by the induction hypothesis, since $\beta \le m
= p β + 1 s e q =p_{\beta+1}^{\mathrm{seq}} = p β + 1 seq by the sequential recursion.
Corollary S-9 (Finite exact termination). For j ≥ B − 1 j \ge B-1 j ≥ B − 1 , p β ( j ) = p β s e q p_{\beta}^{(j)}=p_{\beta}^{\mathrm{seq}} p β ( j ) = p β seq for every block β ≤ B − 1 \beta\le B-1 β ≤ B − 1 : PintFilter reproduces the sequential filter exactly after at most B − 1 B-1 B − 1 iterations.
Proof. For β ≤ B − 1 ≤ j \beta\le B-1 \le j β ≤ B − 1 ≤ j , Lemma S-8 applies.
This bound depends on N N N and is therefore irrelevant for our span complexity claim, but it makes the telescoping sum of Proposition S-14 finite.
Lean: Lemma S-8 and Corollary S-9
In the code, n n n is the iteration index j j j and b b b the block index β \beta β .
theorem iter_eq_seq_of_le {b n : ℕ} (h : b ≤ n) : iter Φ π₀ π₀’ n b = seq Φ π₀ b
theorem iter_eq_seq_of_le_of_le {b n B : ℕ} (hb : b ≤ B) (hn : B ≤ n) :
iter Φ π₀ π₀’ n b = seq Φ π₀ b
The fixed point is the sequential filter
Definition (Boundary-update map). F F F is the boundary-update map of PintFilter: given P = ( P β ) β P = (P_\beta)_\beta P = ( P β ) β , F ( P ) 0 = π 0 F(P)_0 = \pi_0 F ( P ) 0 = π 0 and F ( P ) β + 1 = Φ β ( P β ) F(P)_{\beta+1} = \Phi_\beta(P_\beta) F ( P ) β + 1 = Φ β ( P β ) .
We write P ( j ) : = ( p β ( j ) ) β P^{(j)} := (p_\beta^{(j)})_\beta P ( j ) := ( p β ( j ) ) β for the boundary densities at iteration j j j . By the recursions, P ( j ) = F ( P ( j − 1 ) ) P^{(j)} = F(P^{(j-1)}) P ( j ) = F ( P ( j − 1 ) ) for j ≥ 1 j \ge1 j ≥ 1 .
Theorem S-12 (Equivalence). P P P is a fixed point of F F F if and only if P β = p β s e q P_\beta= p_\beta^{\mathrm{seq}} P β = p β seq for every β \beta β . Hence F F F has a unique fixed point, and at it every filtered density, every normalizer Z t k Z_{t_k} Z t k , and the total log-likelihood agree with those of SequentialFilter exactly.
Proof. Componentwise, the equation F ( P ) = P F(P) = P F ( P ) = P reads
P 0 = π 0 , P β + 1 = Φ β ( P β ) for all β , P_0 = \pi_0,\qquad P_{\beta+1} = \Phi_\beta(P_\beta)\quad\text{for all }\beta, P 0 = π 0 , P β + 1 = Φ β ( P β ) for all β ,
which are exactly the equations defining p s e q p^{\mathrm{seq}} p seq .
Suppose first that P P P is a fixed point. We show P β = p β s e q P_\beta= p_\beta^{\mathrm{seq}} P β = p β seq by induction on β \beta β . The base case is P 0 = π 0 = p 0 s e q P_0 = \pi_0 = p_0^{\mathrm{seq}} P 0 = π 0 = p 0 seq . For the step, if P β = p β s e q P_\beta= p_\beta^{\mathrm{seq}} P β = p β seq , then
P β + 1 = Φ β ( P β ) = Φ β ( p β s e q ) = p β + 1 s e q . P_{\beta+1} = \Phi_\beta(P_\beta) = \Phi_\beta(p_\beta^{\mathrm{seq}}) = p_{\beta+1}^{\mathrm{seq}}. P β + 1 = Φ β ( P β ) = Φ β ( p β seq ) = p β + 1 seq .
Conversely, p s e q p^{\mathrm{seq}} p seq satisfies the two equations by construction, so it is a fixed point. Uniqueness follows, since the equations determine P P P recursively from π 0 \pi_0 π 0 . Finally, at the fixed point P β = p β s e q P_\beta= p_\beta^{\mathrm{seq}} P β = p β seq for every β \beta β , so by Lemma S-5 every filtered density, every normalizer and the total log-likelihood agree with those of SequentialFilter. □
No contraction bound is used here, only that each Φ β \Phi_\beta Φ β is a well-defined map (Section S1.7).
Corollary S-13 (Zero WRMS increment at the fixed point). Assume (A4). Recall that the increment at iteration j ≥ 1 j \ge1 j ≥ 1 is the largest change of a block initial condition since the previous iteration, measured on coefficient vectors,
δ ( j ) = max β ≥ 1 ∥ c [ p β ( j ) ] − c [ p β ( j − 1 ) ] ∥ W R M S . \delta^{(j)}=\max_{\beta\ge1}\left\Vert c[p_{\beta}^{(j)}]-c[p_{\beta}^{(j-1)}]\right\Vert_{\mathrm{WRMS}}. δ ( j ) = β ≥ 1 max c [ p β ( j ) ] − c [ p β ( j − 1 ) ] WRMS . If at some iteration j ≥ 1 j \ge1 j ≥ 1 the increment vanishes exactly, δ ( j ) = 0 \delta^{(j)}=0 δ ( j ) = 0 , then P ( j ) P^{(j)} P ( j ) is the fixed point of F F F , so p β ( j ) = p β s e q p_{\beta}^{(j)}=p_{\beta}^{\mathrm{seq}} p β ( j ) = p β seq for every β \beta β , and the algorithm returns the sequential filtered densities and log-likelihood exactly. Conversely, the current iterate is the fixed point if and only if the next increment is zero.
Proof. Since the weights are strictly positive, ∥ ⋅ ∥ W R M S , y \lVert\cdot\rVert_{\mathrm{WRMS},y} ∥ ⋅ ∥ WRMS , y is a norm on R N b \mathbb{R}^{N_b} R N b , so δ ( j ) = 0 \delta^{(j)}=0 δ ( j ) = 0 forces c [ p β ( j ) ] = c [ p β ( j − 1 ) ] c[p_{\beta}^{(j)}]=c[p_{\beta}^{(j-1)}] c [ p β ( j ) ] = c [ p β ( j − 1 ) ] for every β ≥ 1 \beta\ge1 β ≥ 1 . By (A4), the coefficient map is injective on the states of the filter, so p β ( j ) = p β ( j − 1 ) p_{\beta}^{(j)}=p_{\beta}^{(j-1)} p β ( j ) = p β ( j − 1 ) for β ≥ 1 \beta\ge1 β ≥ 1 ; for β = 0 \beta=0 β = 0 we have p 0 ( j ) = p 0 ( j − 1 ) = π 0 p_{0}^{(j)}=p_{0}^{(j-1)}=\pi_{0} p 0 ( j ) = p 0 ( j − 1 ) = π 0 , since the first block always starts from π 0 \pi_{0} π 0 . Substituting p β ( j − 1 ) = p β ( j ) p_{\beta}^{(j-1)}=p_{\beta}^{(j)} p β ( j − 1 ) = p β ( j ) into the recursion p β + 1 ( j ) = Φ β ( p β ( j − 1 ) ) p_{\beta+1}^{(j)}=\Phi_{\beta}(p_{\beta}^{(j-1)}) p β + 1 ( j ) = Φ β ( p β ( j − 1 ) ) gives
p 0 ( j ) = π 0 , p β + 1 ( j ) = Φ β ( p β ( j ) ) , p_{0}^{(j)}=\pi_{0},\qquad p_{\beta+1}^{(j)}=\Phi_{\beta}(p_{\beta}^{(j)}), p 0 ( j ) = π 0 , p β + 1 ( j ) = Φ β ( p β ( j ) ) , that is, F ( P ( j ) ) = P ( j ) F(P^{(j)})=P^{(j)} F ( P ( j ) ) = P ( j ) . Theorem S-12 then gives p β ( j ) = p β s e q p_{\beta}^{(j)}=p_{\beta}^{\mathrm{seq}} p β ( j ) = p β seq for every β \beta β . The converse direction follows by reading the same argument backwards: if P ( j ) P^{(j)} P ( j ) is the fixed point, then P ( j + 1 ) = F ( P ( j ) ) = P ( j ) P^{(j+1)}=F(P^{(j)})=P^{(j)} P ( j + 1 ) = F ( P ( j ) ) = P ( j ) , so the next increment is zero.
Lean: Theorem S-12 and Corollary S-13
In the code, n is the iteration index j j j and b the block index β \beta β .
structure IsFixedPoint (Φ : ℕ → S → S) (π₀ : S) (P : ℕ → S) : Prop where
head : P 0 = π₀
step : ∀ b, P (b + 1) = Φ b (P b)
theorem isFixedPoint_iff {P : ℕ → S} :
IsFixedPoint Φ π₀ P ↔ ∀ b, P b = seq Φ π₀ b
theorem IsFixedPoint.unique {P P’ : ℕ → S} (h : IsFixedPoint Φ π₀ P)
(h’ : IsFixedPoint Φ π₀ P’) : P = P’
theorem increment_eq_zero_iff_isFixedPoint {n : ℕ} :
(∀ b, iter Φ π₀ π₀’ (n + 1) b = iter Φ π₀ π₀’ n b) ↔
IsFixedPoint Φ π₀ (iter Φ π₀ π₀’ n)
theorem eq_seq_of_increment_eq_zero {n : ℕ}
(h : ∀ b, iter Φ π₀ π₀’ (n + 1) b = iter Φ π₀ π₀’ n b) (b : ℕ) :
iter Φ π₀ π₀’ n b = seq Φ π₀ b
The equivalence between the parallel and the sequential filter is a quasi-trivial function which needs nothing except BlockFilter being a function.
Lean: Corollary S-13 for the implementation
In PlanxAlgorithm/Wrms.lean, with c the coefficient map c, b is the block index β \beta β and D the basis dimension N b N_b N b . The increment is taken between iterations n n n and n + 1 n + 1 n + 1 , that is, j − 1 j - 1 j − 1 and j j j in the text.
theorem wrms_eq_zero_iff {atol rtol : R} (hatol : 0 < atol) (hrtol : 0 ≤ rtol)
(y v : Fin D → R) (hD : 0 < D) : wrms atol rtol y v = 0 ↔ v = 0
theorem eq_seq_of_wrms_eq_zero {c : S → Fin D → R} (hc : Function.Injective c)
{atol rtol : R} (hatol : 0 < atol) (hrtol : 0 ≤ rtol) (hD : 0 < D) {n : ℕ}
(h : ∀ b, 1 ≤ b → wrms atol rtol (c (iter Φ π₀ π₀’ n b))
(c (iter Φ π₀ π₀’ (n + 1) b) - c (iter Φ π₀ π₀’ n b)) = 0) (b : ℕ) :
iter Φ π₀ π₀’ n b = seq Φ π₀ b
We prove only the property of WRMS that is used: a vector with zero WRMS norm is zero, so a zero increment means equal coefficient vectors. This needs the weights to be strictly positive. Assumption (A4), injectivity of the coefficient map, is the hypothesis hc.
Absolute convergence with N N N -independent rate
Proposition S-10 (Absolute convergence). Under (F-abs), for every j ≥ 1 j \ge1 j ≥ 1 and every β \beta β ,
∥ p β ( j ) − p β s e q ∥ ≤ e ( j ) = min { 2 , C 0 τ j L } . \left\lVert p_{\beta}^{(j)} - p_{\beta}^{\mathrm{seq}} \right\rVert\le e(j) = \min\{2, C_0\tau^{jL}\}. p β ( j ) − p β seq ≤ e ( j ) = min { 2 , C 0 τ j L } .
Proof. If β ≤ j \beta\le j β ≤ j , then p β ( j ) = p β s e q p_{\beta}^{(j)} = p_{\beta}^{\mathrm{seq}} p β ( j ) = p β seq by Lemma S-8, and the bound holds trivially. Now let β > j \beta> j β > j , and write β = c + j \beta= c + j β = c + j with c ≥ 1 c \ge1 c ≥ 1 , so that block c c c lies j j j blocks before block β \beta β . We express both densities at block β \beta β in terms of block c c c . By Lemma S-7, with starting iteration 0 0 0 and m = j m = j m = j ,
p c + j ( j ) = Φ c [ j ] ( p c ( 0 ) ) = Φ c [ j ] ( π ˉ 0 ) , p_{c+j}^{(j)} = \Phi_c^{[j]}(p_c^{(0)}) = \Phi_c^{[j]}(\bar{\pi}_0), p c + j ( j ) = Φ c [ j ] ( p c ( 0 ) ) = Φ c [ j ] ( π ˉ 0 ) ,
the last equality because c ≥ 1 c \ge1 c ≥ 1 . By the semigroup identity following Lemma S-6,
p c + j s e q = Φ c [ j ] ( p c s e q ) . p_{c+j}^{\mathrm{seq}} = \Phi_c^{[j]}(p_c^{\mathrm{seq}}). p c + j seq = Φ c [ j ] ( p c seq ) .
Both densities are therefore obtained by applying the same map Φ c [ j ] \Phi_c^{[j]} Φ c [ j ] , which runs the filter through blocks c , … , c + j − 1 c,\ldots,c+j-1 c , … , c + j − 1 , to two different initial conditions, π ˉ 0 \bar{\pi}_0 π ˉ 0 and p c s e q p_c^{\mathrm{seq}} p c seq . Applying (F-abs ) to this pair gives
∥ p c + j ( j ) − p c + j s e q ∥ = ∥ Φ c [ j ] ( π ˉ 0 ) − Φ c [ j ] ( p c s e q ) ∥ ≤ e ( j ) . \lVert p_{c+j}^{(j)}-p_{c+j}^{\mathrm{seq}}\rVert=\lVert\Phi_c^{[j]}(\bar{\pi}_0)-\Phi_c^{[j]}(p_c^{\mathrm{seq}})\rVert\leq e(j). ∥ p c + j ( j ) − p c + j seq ∥ = ∥ Φ c [ j ] ( π ˉ 0 ) − Φ c [ j ] ( p c seq )∥ ≤ e ( j ) .
Theorem S-11 (N -independent iteration count). Under (F-abs ), for any target δ T V ∈ ( 0 , 2 ) \delta_{\mathrm{TV}}\in(0,2) δ TV ∈ ( 0 , 2 ) ,
N i t e r ( δ T V ) : = max { 1 , ⌈ 1 L ( 1 + log 1 / τ 8 log ( 1 / ε ) δ T V log 3 ) ⌉ } N_{\mathrm{iter}}(\delta_{\mathrm{TV}}):=\max\left\{1,\left\lceil\frac{1}{L}\left(1+\log_{1/\tau}\frac{8\log(1/\varepsilon)}{\delta_{\mathrm{TV}}\log3}\right)\right\rceil\right\} N iter ( δ TV ) := max { 1 , ⌈ L 1 ( 1 + log 1/ τ δ TV log 3 8 log ( 1/ ε ) ) ⌉ } satisfies max β ∥ p β ( j ) − p β s e q ∥ ≤ δ T V \max_{\beta}\lVert p_{\beta}^{(j)}-p_{\beta}^{\mathrm{seq}}\rVert\leq\delta_{\mathrm{TV}} max β ∥ p β ( j ) − p β seq ∥ ≤ δ TV for every j ≥ N i t e r ( δ T V ) j\geq N_{\mathrm{iter}}(\delta_{\mathrm{TV}}) j ≥ N iter ( δ TV ) . The quantity N i t e r N_{\mathrm{iter}} N iter depends only on ( ε , L , δ T V ) (\varepsilon,L,\delta_{\mathrm{TV}}) ( ε , L , δ TV ) , and in particular it is independent of the trajectory length N N N and the block count B B B .
Proof. By Proposition S-10 it suffices to find the j j j for which C 0 τ j L ≤ δ T V C_0\tau^{jL}\leq\delta_{\mathrm{TV}} C 0 τ j L ≤ δ TV . Substituting C 0 = 8 log ( 1 / ε ) / ( τ log 3 ) C_0=8\log(1/\varepsilon)/(\tau\log3) C 0 = 8 log ( 1/ ε ) / ( τ log 3 ) , this condition reads
8 log ( 1 / ε ) log 3 τ j L − 1 ≤ δ T V . \frac{8\log(1/\varepsilon)}{\log3}\tau^{jL-1}\leq\delta_{\mathrm{TV}}. log 3 8 log ( 1/ ε ) τ j L − 1 ≤ δ TV . Taking logarithms and using log ( 1 / τ ) > 0 \log(1/\tau)>0 log ( 1/ τ ) > 0 , since τ < 1 \tau<1 τ < 1 , this is equivalent to
( j L − 1 ) log ( 1 / τ ) ≥ log 8 log ( 1 / ε ) δ T V log 3 , that is, j ≥ 1 L ( 1 + log 1 / τ 8 log ( 1 / ε ) δ T V log 3 ) . (jL-1)\log(1/\tau)\geq\log\frac{8\log(1/\varepsilon)}{\delta_{\mathrm{TV}}\log3},\qquad\text{that is,}\qquad j\geq\frac{1}{L}\left(1+\log_{1/\tau}\frac{8\log(1/\varepsilon)}{\delta_{\mathrm{TV}}\log3}\right). ( j L − 1 ) log ( 1/ τ ) ≥ log δ TV log 3 8 log ( 1/ ε ) , that is, j ≥ L 1 ( 1 + log 1/ τ δ TV log 3 8 log ( 1/ ε ) ) . Since τ j L \tau^{jL} τ j L decreases in j j j , the inequality holds for every j j j at or above the right-hand side, and in particular for every j ≥ N i t e r ( δ T V ) j\geq N_{\mathrm{iter}}(\delta_{\mathrm{TV}}) j ≥ N iter ( δ TV ) . The maximum with 1 reflects that at least one iteration is run, which is also the range where Proposition S-10 applies. In fact, the ceiling is already at least 1, since C 0 > 2 > δ T V C_0>2>\delta_{\mathrm{TV}} C 0 > 2 > δ TV .
Lean: Propositions S-10 and S-11
In the code, n is the iteration index j j j and b the block index β \beta β .
theorem dist_iter_seq_le (F : BlockForgetting Φ L) (n b : N) :
dist (iter Φ π₀ π₀’ n b) (seq Φ π₀ b) ≤ F.C₀ * F.τ ^ (n * L)
noncomputable def iterCount (C τ : R) (L : N) (δ : R) : N :=
⌈Real.log (C / δ) / ((L : R) * (-Real.log τ))⌉₊
theorem dist_iter_seq_le_of_iterCount_le (F : BlockForgetting Φ L) (hL : 0 < L)
{δ : R} (hδ : 0 < δ) {n : N} (hn : iterCount F.C₀ F.τ L δ ≤ n) (b : N) :
dist (iter Φ π₀ π₀’ n b) (seq Φ π₀ b) ≤ δ
theorem exists_iterCount (F : BlockForgetting Φ L) (hL : 0 < L) {δ : ℝ}
(hδ : 0 < δ) :
∃ N : ℕ, ∀ n, N ≤ n → ∀ b, dist (iter Φ π₀ π₀′ n b) (seq Φ π₀ b) ≤ δ
iterCount is stated in terms of C 0 C_0 C 0 rather than 8 log ( 1 / ε ) / log 3 8\log(1/\varepsilon)/\log3 8 log ( 1/ ε ) / log 3 . It solves C 0 τ j L ≤ δ C_0\tau^{jL}\leq\delta C 0 τ j L ≤ δ directly, which is the same threshold as N i t e r N_{\mathrm{iter}} N iter after substituting C 0 C_0 C 0 .
The maximum with 1 in N i t e r N_{\mathrm{iter}} N iter is absent in Lean, because the Lean bound dist_iter_seq_le also holds at j = 0 j=0 j = 0 .
We do not argue N N N -independence in the formalization, as a meta-argument. Rather, the fact that the statement do not accept either N N N or B B B as input proves it. That is, the arguments of iterCount are the contraction data and the tolerance, no trajectory length and no block count occurs in either statement. Similarly, in exists_iterCount, N N N is produced before any block index is mentioned.
Remark (choice of L L L ). The condition of Theorem S-11 bounds the product j L jL j L , the total number of filtering steps separating a block from the trial density, and not L L L alone. Blocks much shorter than the forgetting time are therefore admissible: the algorithm then needs more iterations, but the span N i t e r ⋅ L N_{\mathrm{iter}}\cdot L N iter ⋅ L stays of the order of the forgetting time plus one block. The choice of L L L trades parallel width B = N / L B=N/L B = N / L against per-iteration overhead, not against correctness.
A posteriori bound from observable increments
The error to the sequential filter is not directly computable in practice, since the sequential densities are exactly what we wish to avoid computing. The increment between successive iterations is our only observable.
Write Δ β ( j ) : = ∥ p β ( j ) − p β ( j − 1 ) ∥ \Delta_{\beta}^{(j)} := \lVert p_{\beta}^{(j)}-p_{\beta}^{(j-1)}\rVert Δ β ( j ) := ∥ p β ( j ) − p β ( j − 1 ) ∥ (the increment) and E β ( j ) : = ∥ p β ( j ) − p β s e q ∥ E_{\beta}^{(j)} := \lVert p_{\beta}^{(j)}-p_{\beta}^{\mathrm{seq}}\rVert E β ( j ) := ∥ p β ( j ) − p β seq ∥ (the error to sequential filter), and let δ T V ( j ′ ) \delta_{\mathrm{TV}}^{(j')} δ TV ( j ′ ) be any bound with Δ β ( j ) ≤ δ T V ( j ′ ) \Delta_{\beta}^{(j)}\leq\delta_{\mathrm{TV}}^{(j')} Δ β ( j ) ≤ δ TV ( j ′ ) for all β ≥ 1 \beta\geq1 β ≥ 1 .
Proposition S-14 (Telescoping). For every j ≥ 1 j\geq1 j ≥ 1 and every β \beta β ,
E β ( j ) ≤ ∑ j ′ = j + 1 β Δ β ( j ′ ) ≤ ∑ j ′ = j + 1 β δ T V ( j ′ ) . E_{\beta}^{(j)}\leq\sum_{j'=j+1}^{\beta}\Delta_{\beta}^{(j')}\leq\sum_{j'=j+1}^{\beta}\delta_{\mathrm{TV}}^{(j')}. E β ( j ) ≤ j ′ = j + 1 ∑ β Δ β ( j ′ ) ≤ j ′ = j + 1 ∑ β δ TV ( j ′ ) .
Proof. If β ≤ j \beta\leq j β ≤ j , then E β ( j ) = 0 E_{\beta}^{(j)}=0 E β ( j ) = 0 by Lemma S-8, and the sums are empty. Let β > j \beta>j β > j . By
Lemma S-8, p β ( β ) = p β s e q p_{\beta}^{(\beta)}=p_{\beta}^{\mathrm{seq}} p β ( β ) = p β seq , so the error telescopes over the iterations j + 1 , … , β j+1,\ldots,\beta j + 1 , … , β :
p β s e q − p β ( j ) = p β ( β ) − p β ( j ) = ∑ j ′ = j + 1 β ( p β ( j ′ ) − p β ( j ′ − 1 ) ) . p_{\beta}^{\mathrm{seq}}-p_{\beta}^{(j)}=p_{\beta}^{(\beta)}-p_{\beta}^{(j)}=\sum_{j'=j+1}^{\beta}\left(p_{\beta}^{(j')}-p_{\beta}^{(j'-1)}\right). p β seq − p β ( j ) = p β ( β ) − p β ( j ) = j ′ = j + 1 ∑ β ( p β ( j ′ ) − p β ( j ′ − 1 ) ) .
By the triangle inequality, E β ( j ) ≤ ∑ j ′ = j + 1 β Δ β ( j ′ ) E_{\beta}^{(j)}\leq\sum_{j'=j+1}^{\beta}\Delta_{\beta}^{(j')} E β ( j ) ≤ ∑ j ′ = j + 1 β Δ β ( j ′ ) . Each term is at most δ T V ( j ′ ) \delta_{\mathrm{TV}}^{(j')} δ TV ( j ′ ) , since β > j ≥ 1 \beta>j\geq1 β > j ≥ 1 .
This bound uses no contraction: it only uses that the iteration reaches p β s e q p_{\beta}^{\mathrm{seq}} p β seq after finitely many steps (Lemma S-8). But its sum has up to β \beta β terms, so it grows with N N N . Proposition S-15 uses (F-lip) to bound the whole sum by the current increment alone.
Proposition S-15 (A posteriori error ≤ \leq ≤ constant × \times × observed increment). Under (F-lip), for every j ≥ 1 j\geq1 j ≥ 1 ,
max β ≥ 1 E β ( j ) ≤ A δ T V ( j ) , A : = 2 ε 2 log 3 ⋅ τ L − 1 1 − τ L , \max_{\beta\geq1}E_{\beta}^{(j)}\leq A\delta_{\mathrm{TV}}^{(j)},\qquad A:=\frac{2}{\varepsilon^{2}\log3}\cdot\frac{\tau^{L-1}}{1-\tau^{L}}, β ≥ 1 max E β ( j ) ≤ A δ TV ( j ) , A := ε 2 log 3 2 ⋅ 1 − τ L τ L − 1 , with A A A depending only on ( ε , L ) (\varepsilon,L) ( ε , L ) , and not on N N N , B B B , β \beta β , j j j , or π ˉ 0 \bar{\pi}_0 π ˉ 0 . Setting δ T V ( j ) = 0 \delta_{\mathrm{TV}}^{(j)}=0 δ TV ( j ) = 0 recovers Corollary S-13.
Proof. Step 1: increments decay. We claim that for all j , m ≥ 1 j,m\geq1 j , m ≥ 1 ,
max β ≥ 1 Δ β ( j + m ) ≤ ρ m δ T V ( j ) , ρ m : = 2 ε 2 log 3 τ m L − 1 . (9) \max_{\beta\geq1}\Delta_{\beta}^{(j+m)}\leq\rho_m\delta_{\mathrm{TV}}^{(j)},\qquad\rho_m:=\frac{2}{\varepsilon^{2}\log3}\tau^{mL-1}. \tag*{(9)} β ≥ 1 max Δ β ( j + m ) ≤ ρ m δ TV ( j ) , ρ m := ε 2 log 3 2 τ m L − 1 . (9)
Fix β ≥ 1 \beta\geq1 β ≥ 1 . If β ≤ j + m − 1 \beta\leq j+m-1 β ≤ j + m − 1 , Lemma S-8 gives p β ( j + m ) = p β s e q = p β ( j + m − 1 ) p_{\beta}^{(j+m)}=p_{\beta}^{\mathrm{seq}}=p_{\beta}^{(j+m-1)} p β ( j + m ) = p β seq = p β ( j + m − 1 ) , so Δ β ( j + m ) = 0 \Delta_{\beta}^{(j+m)}=0 Δ β ( j + m ) = 0 . Otherwise β ≥ j + m \beta\geq j+m β ≥ j + m , so block β − m ≥ j ≥ 1 \beta-m\geq j\geq1 β − m ≥ j ≥ 1 exists. By Lemma S-7, applied over the m m m blocks from β − m \beta-m β − m to β \beta β , starting at iterations j j j and j − 1 j-1 j − 1 ,
p β ( j + m ) = Φ β − m [ m ] ( p β − m ( j ) ) , p β ( j + m − 1 ) = Φ β − m [ m ] ( p β − m ( j − 1 ) ) . p_{\beta}^{(j+m)}=\Phi_{\beta-m}^{[m]}\left(p_{\beta-m}^{(j)}\right),\qquad p_{\beta}^{(j+m-1)}=\Phi_{\beta-m}^{[m]}\left(p_{\beta-m}^{(j-1)}\right). p β ( j + m ) = Φ β − m [ m ] ( p β − m ( j ) ) , p β ( j + m − 1 ) = Φ β − m [ m ] ( p β − m ( j − 1 ) ) .
This is the same map Φ β − m [ m ] \Phi_{\beta-m}^{[m]} Φ β − m [ m ] applied to two initial conditions, so
Δ β ( j + m ) = ∥ Φ β − m [ m ] ( p β − m ( j ) ) − Φ β − m [ m ] ( p β − m ( j − 1 ) ) ∥ ≤ C 1 τ m L − 1 ∥ p β − m ( j ) − p β − m ( j − 1 ) ∥ by (F-lip) = ρ m Δ β − m ( j ) since C 1 = 2 / ( ε 2 log 3 ) ≤ ρ m δ T V ( j ) since β − m ≥ 1. \begin{aligned}
\Delta_{\beta}^{(j+m)}
&=\left\|\Phi_{\beta-m}^{[m]}\left(p_{\beta-m}^{(j)}\right)-\Phi_{\beta-m}^{[m]}\left(p_{\beta-m}^{(j-1)}\right)\right\|\\
&\leq C_1\tau^{mL-1}\left\|p_{\beta-m}^{(j)}-p_{\beta-m}^{(j-1)}\right\| && \text{by (F-lip)}\\
&=\rho_m\Delta_{\beta-m}^{(j)} && \text{since }C_1=2/(\varepsilon^2\log3)\\
&\leq\rho_m\delta_{\mathrm{TV}}^{(j)} && \text{since }\beta-m\geq1.
\end{aligned} Δ β ( j + m ) = Φ β − m [ m ] ( p β − m ( j ) ) − Φ β − m [ m ] ( p β − m ( j − 1 ) ) ≤ C 1 τ m L − 1 p β − m ( j ) − p β − m ( j − 1 ) = ρ m Δ β − m ( j ) ≤ ρ m δ TV ( j ) by (F-lip) since C 1 = 2/ ( ε 2 log 3 ) since β − m ≥ 1.
Taking the maximum over β ≥ 1 \beta\geq1 β ≥ 1 gives (*).
Step 2: summing. By Proposition S-14, E β ( j ) ≤ ∑ j ′ = j + 1 β Δ β ( j ′ ) E_\beta^{(j)} \le\sum_{j'=j+1}^{\beta} \Delta_\beta^{(j')} E β ( j ) ≤ ∑ j ′ = j + 1 β Δ β ( j ′ ) for every β \beta β . Extending this sum of non-negative terms to all j ′ > j j' > j j ′ > j , bounding each term by its maximum over blocks, and writing j ′ = j + m j' = j + m j ′ = j + m gives
max β E β ( j ) ≤ ∑ m ≥ 1 max β ≥ 1 Δ β ( j + m ) . \max_\beta E_\beta^{(j)} \le\sum_{m \ge1} \max_{\beta\ge1} \Delta_\beta^{(j+m)}. β max E β ( j ) ≤ m ≥ 1 ∑ β ≥ 1 max Δ β ( j + m ) .
By ( ∗ ) (*) ( ∗ ) , and summing the geometric series, which converges since τ < 1 \tau< 1 τ < 1 ,
max β E β ( j ) ≤ ∑ m ≥ 1 ρ m δ T V ( j ) = 2 ε 2 log 3 δ T V ( j ) ∑ m ≥ 1 τ m L − 1 = 2 ε 2 log 3 δ T V ( j ) τ L − 1 ∑ m ≥ 0 ( τ L ) m = 2 ε 2 log 3 τ L − 1 1 − τ L δ T V ( j ) = A δ T V ( j ) . \begin{aligned}
\max_\beta E_\beta^{(j)} \le\sum_{m \ge1} \rho_m \delta_{\mathrm{TV}}^{(j)} = \frac{2}{\varepsilon^2 \log3}\delta_{\mathrm{TV}}^{(j)} \sum_{m \ge1}\tau^{mL-1} \\
&= \frac{2}{\varepsilon^2 \log3}\delta_{\mathrm{TV}}^{(j)}\tau^{L-1}\sum_{m \ge0}(\tau^L)^m = \frac{2}{\varepsilon^2 \log3}\frac{\tau^{L-1}}{1-\tau^L}\delta_{\mathrm{TV}}^{(j)} = A\delta_{\mathrm{TV}}^{(j)}.
\end{aligned} β max E β ( j ) ≤ m ≥ 1 ∑ ρ m δ TV ( j ) = ε 2 log 3 2 δ TV ( j ) m ≥ 1 ∑ τ m L − 1 = ε 2 log 3 2 δ TV ( j ) τ L − 1 m ≥ 0 ∑ ( τ L ) m = ε 2 log 3 2 1 − τ L τ L − 1 δ TV ( j ) = A δ TV ( j ) .
Lean: Propositions S-14 and S-15
In the code, n is the iteration index j j j and b the block index β \beta β .
theorem dist_iter_seq_le_sum_dist (n b : N) :
dist (iter Φ π₀ π₀’ n b) (seq Φ π₀ b)
≤ ∑ j ∈ Finset.Ico n b,
dist (iter Φ π₀ π₀’ j b) (iter Φ π₀ π₀’ (j + 1) b)
theorem dist_iter_shift_le (F : BlockForgetting Φ L) {d : N → R}
(hd : ∀ m b, 1 ≤ b →
dist (iter Φ π₀ π₀’ (m + 1) b) (iter Φ π₀ π₀’ m b) ≤ d m)
(m k b : N) :
dist (iter Φ π₀ π₀’ (m + k + 1) b) (iter Φ π₀ π₀’ (m + k) b)
≤ F.C₁ * F.τ ^ (k * L - 1) * d m
theorem dist_iter_seq_le_const_mul (F : BlockForgetting Φ L) (hL : 0 < L)
{d : N → R}
(hd : ∀ m b, 1 ≤ b →
dist (iter Φ π₀ π₀’ (m + 1) b) (iter Φ π₀ π₀’ m b) ≤ d m)
(m b : N) :
dist (iter Φ π₀ π₀’ (m + 1) b) (seq Φ π₀ b)
≤ F.C₁ * F.τ ^ (L - 1) * d m / (1 - F.τ ^ L)
There are three differences from the proofs as written above, mostly to avoid awkward subtraction of indices.
Proposition S-14 is reindexed to Finset.Ico n b with increments ( j ′ , j ′ + 1 ) (j',j'+1) ( j ′ , j ′ + 1 ) , where the summation index j ′ j' j ′ is Lean’s j. This is the same as ∑ j ′ = j + 1 β \sum_{j'=j+1}^{\beta} ∑ j ′ = j + 1 β but avoids the subtraction j ′ − 1 j' - 1 j ′ − 1 .
Indexing blocks by N rather than Fin B lets the telescoping sum end at j ′ = β j' = \beta j ′ = β rather than at j ′ = B − 1 j' = B - 1 j ′ = B − 1 . In Proposition S-15, d d d is an abstract bounding sequence rather than sup β \sup_{\beta} sup β , which would need ciSup and a boundedness side condition, which we ultimately do not use later. Finally, dist_iter_shift_le drops the condition m ≥ 1 m \ge1 m ≥ 1 of (*): it is unnecessary, because (F-lip) at j = 0 j = 0 j = 0 already asserts ∥ μ − μ ′ ′ ∥ ≤ C 1 ∥ μ − μ ′ ∥ \lVert\mu- \mu'' \rVert\le C_1 \lVert\mu- \mu' \rVert ∥ μ − μ ′′ ∥ ≤ C 1 ∥ μ − μ ′ ∥ and so forces 1 ≤ C 1 1 \le C_1 1 ≤ C 1 .
From TV to WRMS
So far, we measured increments and errors in total variation (TV). However, the stopping rule of PintFilter is based on the WRMS norm of coefficient differences. We now translate TV bounds to WRMS.
Lemma S-16 (TV controls WRMS). Assume (A4). For any two states p , p ′ p, p' p , p ′ of the filter and every weighting reference y ∈ R N b y \in\mathbb{R}^{N_b} y ∈ R N b :
1.
∥ c [ p ] − c [ p ′ ] ∥ W R M S , y ≤ M e a t o l ∥ p − p ′ ∥ T V . \lVert\mathbf{c}[p] - \mathbf{c}[p'] \rVert_{\mathrm{WRMS},y} \le\frac{M_e}{\mathrm{atol}} \lVert p - p' \rVert_{\mathrm{TV}}. ∥ c [ p ] − c [ p ′ ] ∥ WRMS , y ≤ atol M e ∥ p − p ′ ∥ TV . conversely,
∥ p − p ′ ∥ T V ≤ N b max i ≤ N b ( a t o l + r t o l ∣ y i ∣ ) ∥ e i ∥ L 1 ∥ c [ p ] − c [ p ′ ] ∥ W R M S , y . \lVert p - p' \rVert_{\mathrm{TV}} \le N_b \max_{i \le N_b}(\mathrm{atol} + \mathrm{rtol}\,|y_i|)\lVert e_i \rVert_{L^1}\lVert\mathbf{c}[p] - \mathbf{c}[p'] \rVert_{\mathrm{WRMS},y}. ∥ p − p ′ ∥ TV ≤ N b i ≤ N b max ( atol + rtol ∣ y i ∣ ) ∥ e i ∥ L 1 ∥ c [ p ] − c [ p ′ ] ∥ WRMS , y .
Proof. Write v : = c [ p ] − c [ p ′ ] v := \mathbf{c}[p] - \mathbf{c}[p'] v := c [ p ] − c [ p ′ ] . Since c \mathbf{c} c is linear, v = c [ p − p ′ ] v = \mathbf{c}[p - p'] v = c [ p − p ′ ] , and p − p ′ p - p' p − p ′ lies in V V V .
Part (1). By the definition of M e M_e M e in (A4), for each i i i ,
∣ v i ∣ = ∣ c i [ p − p ′ ] ∣ ≤ M e ∥ p − p ′ ∥ T V . |v_i| = |c_i[p - p']| \le M_e \lVert p - p' \rVert_{\mathrm{TV}}. ∣ v i ∣ = ∣ c i [ p − p ′ ] ∣ ≤ M e ∥ p − p ′ ∥ TV .
The weights satisfy w i ≤ 1 / a t o l w_i \le1/\mathrm{atol} w i ≤ 1/ atol , whatever y y y is. A root mean square is at most the maximum of the entries, so
∥ v ∥ W R M S , y = ( 1 N b ∑ i ( w i v i ) 2 ) 1 / 2 ≤ max i w i ∣ v i ∣ ≤ M e a t o l ∥ p − p ′ ∥ T V . \lVert v \rVert_{\mathrm{WRMS},y} = \left(\frac{1}{N_b}\sum_i (w_i v_i)^2\right)^{1/2} \le\max_i w_i |v_i| \le\frac{M_e}{\mathrm{atol}}\lVert p - p' \rVert_{\mathrm{TV}}. ∥ v ∥ WRMS , y = ( N b 1 i ∑ ( w i v i ) 2 ) 1/2 ≤ i max w i ∣ v i ∣ ≤ atol M e ∥ p − p ′ ∥ TV .
Part (2). By (A4), p = ∑ i c i [ p ] e i p = \sum_i c_i[p]e_i p = ∑ i c i [ p ] e i and likewise for p ′ p' p ′ , so p − p ′ = ∑ i v i e i p - p' = \sum_i v_i e_i p − p ′ = ∑ i v i e i . Using this expansion, and inserting w i w i − 1 = 1 w_iw_i^{-1}=1 w i w i − 1 = 1 in each term,
∥ p − p ′ ∥ T V = ∫ ∣ p − p ′ ∣ ≤ ∑ i ∣ v i ∣ ∥ e i ∥ L 1 = ∑ i w i ∣ v i ∣ ⋅ w i − 1 ∥ e i ∥ L 1 ≤ max i ( w i − 1 ∥ e i ∥ L 1 ) ∑ i w i ∣ v i ∣ . \lVert p-p'\rVert_{\mathrm{TV}}=\int\lvert p-p'\rvert\le\sum_i\lvert v_i\rvert\lVert e_i\rVert_{L^1}=\sum_i w_i\lvert v_i\rvert\cdot w_i^{-1}\lVert e_i\rVert_{L^1}
\le\max_i\left(w_i^{-1}\lVert e_i\rVert_{L^1}\right)\sum_i w_i\lvert v_i\rvert. ∥ p − p ′ ∥ TV = ∫ ∣ p − p ′ ∣ ≤ i ∑ ∣ v i ∣ ∥ e i ∥ L 1 = i ∑ w i ∣ v i ∣ ⋅ w i − 1 ∥ e i ∥ L 1 ≤ i max ( w i − 1 ∥ e i ∥ L 1 ) i ∑ w i ∣ v i ∣ .
By the Cauchy–Schwarz inequality on R N b \mathbb{R}^{N_b} R N b ,
∑ i w i ∣ v i ∣ ≤ N b ∥ W y v ∥ ℓ 2 = N b ⋅ N b ∥ v ∥ W R M S , y = N b ∥ v ∥ W R M S , y . \sum_i w_i\lvert v_i\rvert\le\sqrt{N_b}\lVert W_yv\rVert_{\ell^2}=\sqrt{N_b}\cdot\sqrt{N_b}\lVert v\rVert_{\mathrm{WRMS},y}=N_b\lVert v\rVert_{\mathrm{WRMS},y}. i ∑ w i ∣ v i ∣ ≤ N b ∥ W y v ∥ ℓ 2 = N b ⋅ N b ∥ v ∥ WRMS , y = N b ∥ v ∥ WRMS , y .
Substituting w i − 1 = a t o l + r t o l ∣ y i ∣ w_i^{-1}=\mathrm{atol}+\mathrm{rtol}\lvert y_i\rvert w i − 1 = atol + rtol ∣ y i ∣ gives the claim.
Corollary S-17 (Implementation stops at N N N -independent iteration count). Under (F-abs) and (A4), for every j ≥ 1 j\ge1 j ≥ 1 ,
δ ( j ) ≤ 2 M e C 0 a t o l τ ( j − 1 ) L . \delta^{(j)}\le\frac{2M_eC_0}{\mathrm{atol}}\tau^{(j-1)L}. δ ( j ) ≤ atol 2 M e C 0 τ ( j − 1 ) L . Hence the rule δ ( j ) ≤ 1 \delta^{(j)}\le1 δ ( j ) ≤ 1 is met at the latest at iteration
N s t o p : = 1 + max { 0 , ⌈ log ( 2 M e C 0 / a t o l ) L log ( 1 / τ ) ⌉ } , N_{\mathrm{stop}}:=1+\max\left\{0,\left\lceil\frac{\log(2M_eC_0/\mathrm{atol})}{L\log(1/\tau)}\right\rceil\right\}, N stop := 1 + max { 0 , ⌈ L log ( 1/ τ ) log ( 2 M e C 0 / atol ) ⌉ } , which depends on ( ε , L , M e , a t o l ) (\varepsilon,L,M_e,\mathrm{atol}) ( ε , L , M e , atol ) only, not on N N N or B B B .
Proof. We first note that E β ( m ) ≤ C 0 τ m L E_\beta^{(m)}\le C_0\tau^{mL} E β ( m ) ≤ C 0 τ m L holds for every m ≥ 0 m\ge0 m ≥ 0 , not only for m ≥ 1 m\ge1 m ≥ 1 . For m ≥ 1 m\ge1 m ≥ 1 this is Proposition S-10. For m = 0 m=0 m = 0 it reads E β ( 0 ) ≤ C 0 E_\beta^{(0)}\le C_0 E β ( 0 ) ≤ C 0 , which holds because total variation distances between probability measures are at most 2, and C 0 > 2 C_0>2 C 0 > 2 (Section S1.7, the case j = 0 j=0 j = 0 ).
Now fix j ≥ 1 j\ge1 j ≥ 1 and β ≥ 1 \beta\ge1 β ≥ 1 . By the triangle inequality through p β s e q p_\beta^{\mathrm{seq}} p β seq , then the bound just established at j j j and at j − 1 ≥ 0 j-1\ge0 j − 1 ≥ 0 , and finally τ j L ≤ τ ( j − 1 ) L \tau^{jL}\le\tau^{(j-1)L} τ j L ≤ τ ( j − 1 ) L ,
∥ p β ( j ) − p β ( j − 1 ) ∥ T V ≤ E β ( j ) + E β ( j − 1 ) ≤ C 0 τ j L + C 0 τ ( j − 1 ) L ≤ 2 C 0 τ ( j − 1 ) L . \lVert p_\beta^{(j)}-p_\beta^{(j-1)}\rVert_{\mathrm{TV}}\le E_\beta^{(j)}+E_\beta^{(j-1)}\le C_0\tau^{jL}+C_0\tau^{(j-1)L}\le2C_0\tau^{(j-1)L}. ∥ p β ( j ) − p β ( j − 1 ) ∥ TV ≤ E β ( j ) + E β ( j − 1 ) ≤ C 0 τ j L + C 0 τ ( j − 1 ) L ≤ 2 C 0 τ ( j − 1 ) L .
Now apply Lemma S-16(1) with the reference y = c [ p β ( j − 1 ) ] y=c[p_\beta^{(j-1)}] y = c [ p β ( j − 1 ) ] that the implementation uses:
∥ c [ p β ( j ) ] − c [ p β ( j − 1 ) ] ∥ W R M S , y ≤ M e a t o l ∥ p β ( j ) − p β ( j − 1 ) ∥ T V ≤ 2 M e C 0 a t o l τ ( j − 1 ) L . \lVert c[p_\beta^{(j)}]-c[p_\beta^{(j-1)}]\rVert_{\mathrm{WRMS},y}\le\frac{M_e}{\mathrm{atol}}\lVert p_\beta^{(j)}-p_\beta^{(j-1)}\rVert_{\mathrm{TV}}\le\frac{2M_eC_0}{\mathrm{atol}}\tau^{(j-1)L}. ∥ c [ p β ( j ) ] − c [ p β ( j − 1 ) ] ∥ WRMS , y ≤ atol M e ∥ p β ( j ) − p β ( j − 1 ) ∥ TV ≤ atol 2 M e C 0 τ ( j − 1 ) L .
The bound is uniform in y y y , so it does not matter that the reference changes from block to block and from iteration to iteration; taking the maximum over β ≥ 1 \beta\ge1 β ≥ 1 gives the first claim. For the second, the right-hand side is at most 1 as soon as $(j-1)L\log(1/\tau)\ge log ( 2 M e C 0 / a t o l ) \log(2M_eC_0/\mathrm{atol}) log ( 2 M e C 0 / atol ) , that is, for j ≥ 1 + ⌈ log ( 2 M e C 0 / a t o l ) / ( L log ( 1 / τ ) ) ⌉ j \ge1 + \lceil\log(2M_eC_0/\mathrm{atol})/(L\log(1/\tau)) \rceil j ≥ 1 + ⌈ log ( 2 M e C 0 / atol ) / ( L log ( 1/ τ ))⌉ ; the maximum with 0 ensures j ≥ 1 j \ge1 j ≥ 1 , as the first claim requires.
Lean: Lemma S-16 and Corollary S-17
In PlanxAlgorithm/Wrms.lean. The Lean state space is abstract, with no densities or basis functions, so Assumption (A4) enters as two hypotheses on the coefficient map c c c :
hc: ∣ c i [ x ] − c i [ x ′ ] ∣ ≤ M dist ( x , x ′ ) |c_i[x] - c_i[x']| \le M \operatorname{dist}(x,x') ∣ c i [ x ] − c i [ x ′ ] ∣ ≤ M dist ( x , x ′ ) , the bound defining M e M_e M e in (A4), with M = M e M = M_e M = M e ;
hsyn: dist ( x , x ′ ) ≤ ∑ i a i ∣ c i [ x ] − c i [ x ′ ] ∣ \operatorname{dist}(x,x') \le\sum_i a_i |c_i[x] - c_i[x']| dist ( x , x ′ ) ≤ ∑ i a i ∣ c i [ x ] − c i [ x ′ ] ∣ , the consequence of the expansion p = ∑ i c i [ p ] e i p = \sum_i c_i[p]e_i p = ∑ i c i [ p ] e i used in Lemma S-16(2), with a i = ∥ e i ∥ L 1 a_i = \lVert e_i\rVert_{L^1} a i = ∥ e i ∥ L 1 .
In the code, b is the block index β \beta β and D the basis dimension N b N_b N b . A is not a Borel set here, but a bound on ( a t o l + r t o l ∣ y i ∣ ) a i (\mathrm{atol}+\mathrm{rtol}\,|y_i|)a_i ( atol + rtol ∣ y i ∣ ) a i , so that D * A is the constant of Lemma S-16(2). The increment is taken between iterations n and n + 1, so Lean’s n is the paper’s j − 1 j-1 j − 1 .
theorem wrms_le_of_lipschitz (hM : 0 ≤ M)
(hc : ∀ x x’ i, |c x i - c x’ i| ≤ M * dist x x’)
(hatol : 0 < atol) (hrtol : 0 ≤ rtol) (y : Fin D → ℝ) (x x’ : S) :
wrms atol rtol y (c x - c x’) ≤ M / atol * dist x x’
theorem dist_le_wrms (hA0 : 0 ≤ A) (hA : ∀ i, (atol + rtol * |y i|) * a i ≤ A)
(hatol : 0 < atol) (hrtol : 0 ≤ rtol)
(hsyn : dist x x’ ≤ ∑ i, a i * |c x i - c x’ i|) :
dist x x’ ≤ (D : ℝ) * A * wrms atol rtol y (c x - c x’)
theorem wrms_increment_le (F : BlockForgetting Φ L) (hM : 0 ≤ M)
(hc : ∀ x x’ i, |c x i - c x’ i| ≤ M * dist x x’)
(hatol : 0 < atol) (hrtol : 0 ≤ rtol) (n b : ℕ) (y : Fin D → ℝ) :
wrms atol rtol y (c (iter Φ π₀ π₀’ (n + 1) b) - c (iter Φ π₀ π₀’ n b))
≤ 2 * M * F.C₀ / atol * F.τ ^ (n * L)
theorem exists_stop (F : BlockForgetting Φ L) (hL : 0 < L) (hM : 0 ≤ M)
(hc : ∀ x x’ i, |c x i - c x’ i| ≤ M * dist x x’)
(hatol : 0 < atol) (hrtol : 0 ≤ rtol) :
∃ N : ℕ, ∀ n, N ≤ n → ∀ b (y : Fin D → ℝ),
wrms atol rtol y (c (iter Φ π₀ π₀’ (n + 1) b) - c (iter Φ π₀ π₀’ n b)) ≤ 1
The four theorems are, in order:
wrms_increment_le is the first claim of Corollary S-17, with τ n L = τ ( j − 1 ) L \tau^{nL}=\tau^{(j-1)L} τ n L = τ ( j − 1 ) L . The case n = 0 n=0 n = 0 needs no separate argument in Lean, because BlockForgetting already includes the case j = 0 j=0 j = 0 of (F-abs);
exists_stop is the second claim. Its witness is iterCount applied to ( 2 M C 0 / a t o l , τ , L , 1 ) (2MC_0/\mathrm{atol},\tau,L,1) ( 2 M C 0 / atol , τ , L , 1 ) , so, as for Theorem S-11, the stopping iteration visibly depends on none of N N N , B B B or the observations.
Proof of Proposition P1
We recall the statement.
Proposition P1 (Constant span complexity). Assume (A1)–(A4), and let ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) satisfy (E), as provided by § 4 . Run PintFilter with the WRMS stopping rule. Then the following hold.
Equivalence. The iteration has a unique fixed point, the sequential filter: at it, every filtered density and the total log-likelihood agree exactly with those of SequentialFilter (Theorem S-12), and an exactly zero increment verifies that it has been reached (Corollary S-13).
Convergence, at an N N N -independent rate. At iteration j j j , the total-variation error between the densities of PintFilter and SequentialFilter, E β ( j ) : = ∥ p β ( j ) − p β s e q ∥ T V E_\beta^{(j)} := \lVert p_\beta^{(j)}-p_\beta^{\mathrm{seq}}\rVert_{\mathrm{TV}} E β ( j ) := ∥ p β ( j ) − p β seq ∥ TV , satisfies max β E β ( j ) ≤ min { 2 , C 0 τ j L } \max_\beta E_\beta^{(j)} \le\min\{2,C_0\tau^{jL}\} max β E β ( j ) ≤ min { 2 , C 0 τ j L } , where τ < 1 \tau<1 τ < 1 and C 0 C_0 C 0 depend only on ε \varepsilon ε (Proposition S-10). Hence any target accuracy δ T V \delta_{\mathrm{TV}} δ TV is reached within N i t e r ( δ T V ) N_{\mathrm{iter}}(\delta_{\mathrm{TV}}) N iter ( δ TV ) iterations, which depends only on ( ε , L , δ T V ) (\varepsilon,L,\delta_{\mathrm{TV}}) ( ε , L , δ TV ) (Theorem S-11).
Span complexity. The WRMS rule stops the algorithm within N s t o p N_{\mathrm{stop}} N stop iterations, where N s t o p N_{\mathrm{stop}} N stop depends only on ( ε , L , M e , a t o l ) (\varepsilon,L,M_e,\mathrm{atol}) ( ε , L , M e , atol ) (Corollary S-17). The span complexity is therefore O ( N s t o p ⋅ L ) O(N_{\mathrm{stop}}\cdot L) O ( N stop ⋅ L ) , independent of N N N .
A posteriori certificate. At iteration j j j , the total-variation error, which the program cannot observe, is bounded by the WRMS increment it computes: max β E β ( j ) ≤ A Γ δ ( j ) \max_\beta E_\beta^{(j)} \le A\Gamma\delta^{(j)} max β E β ( j ) ≤ A Γ δ ( j ) , with constants A = A ( ε , L ) A=A(\varepsilon,L) A = A ( ε , L ) and Γ \Gamma Γ , which depends only on the basis and the tolerances (Proposition S-15, Lemma S-16). In particular, when the rule δ ( j ) ≤ 1 \delta^{(j)}\le1 δ ( j ) ≤ 1 stops the algorithm, this error is at most A Γ A\Gamma A Γ , independently of N N N .
Proof of Proposition P1. By Section S1.7, which uses (A1), (A2) and (E), the block maps Φ β \Phi_\beta Φ β are well defined, and the contraction bounds (F-abs) and (F-lip) hold with the constants of Lemma S-4.
Clause 1 (equivalence). By Theorem S-12, F F F has a unique fixed point, it is p s e q p^{\mathrm{seq}} p seq , and, at it, the filtered densities, normalizers and log-likelihood coincide with those of SequentialFilter. By Corollary S-13, which uses (A4), an exactly zero increment implies that the current iterate is that fixed point.
Clause 2 (convergence). Proposition S-10 gives max β ∥ p β ( j ) − p β s e q ∥ T V ≤ min { 2 , C 0 τ j L } \max_{\beta}\lVert p_{\beta}^{(j)}-p_{\beta}^{\mathrm{seq}}\rVert_{\mathrm{TV}}\le\min\{2,C_{0}\tau^{jL}\} max β ∥ p β ( j ) − p β seq ∥ TV ≤ min { 2 , C 0 τ j L } . Theorem S-11 gives the iteration count N i t e r ( δ T V ) N_{\mathrm{iter}}(\delta_{\mathrm{TV}}) N iter ( δ TV ) , which depends only on ( ε , L , δ T V ) (\varepsilon,L,\delta_{\mathrm{TV}}) ( ε , L , δ TV ) .
Clause 3 (span). Each iteration runs the B B B block filters in parallel, each of L L L steps, so the span of one iteration is O ( L ) O(L) O ( L ) . By Corollary S-17, which uses (A4), the rule δ ( j ) ≤ 1 \delta^{(j)}\le1 δ ( j ) ≤ 1 is met at the latest at iteration N s t o p N_{\mathrm{stop}} N stop , which depends only on ( ε , L , M e , a t o l ) (\varepsilon,L,M_e,\mathrm{atol}) ( ε , L , M e , atol ) . The span is therefore O ( N s t o p ⋅ L ) O(N_{\mathrm{stop}}\cdot L) O ( N stop ⋅ L ) , independent of N N N .
Clause 4 (a posteriori certificate). Proposition S-15 gives max β E β ( j ) ≤ A δ T V ( j ) \max_{\beta}E_{\beta}^{(j)}\le A\delta_{\mathrm{TV}}^{(j)} max β E β ( j ) ≤ A δ TV ( j ) with A = A ( ε , L ) A=A(\varepsilon,L) A = A ( ε , L ) , for any δ T V ( j ) \delta_{\mathrm{TV}}^{(j)} δ TV ( j ) bounding the total-variation increments at iteration j j j . The algorithm observes the WRMS increment δ ( j ) \delta^{(j)} δ ( j ) , not the total-variation one, and Lemma S-16(2) converts one into the other. For each β ≥ 1 \beta\ge1 β ≥ 1 , with the reference y = c [ p β ( j − 1 ) ] y=c[p_{\beta}^{(j-1)}] y = c [ p β ( j − 1 ) ] that the implementation uses, it gives
∥ p β ( j ) − p β ( j − 1 ) ∥ T V ≤ N b max i ( a t o l + r t o l ∣ y i ∣ ) ∥ e i ∥ L 1 δ ( j ) . \lVert p_{\beta}^{(j)}-p_{\beta}^{(j-1)}\rVert_{\mathrm{TV}}\le N_b\max_i(\mathrm{atol}+\mathrm{rtol}\,|y_i|)\lVert e_i\rVert_{L^1}\,\delta^{(j)}. ∥ p β ( j ) − p β ( j − 1 ) ∥ TV ≤ N b i max ( atol + rtol ∣ y i ∣ ) ∥ e i ∥ L 1 δ ( j ) .
The constant still depends on the coefficients y i y_i y i of the current iterate, but it is bounded uniformly. The reference y y y is the coefficient vector of a state p = p β ( j − 1 ) p=p_{\beta}^{(j-1)} p = p β ( j − 1 ) of the filter, a probability density, so ∥ p ∥ T V = 1 \lVert p\rVert_{\mathrm{TV}}=1 ∥ p ∥ TV = 1 and, by (A4),
∣ y i ∣ = ∣ c i [ p ] ∣ ≤ M e ∥ p ∥ T V = M e . |y_i|=|c_i[p]|\le M_e\lVert p\rVert_{\mathrm{TV}}=M_e. ∣ y i ∣ = ∣ c i [ p ] ∣ ≤ M e ∥ p ∥ TV = M e .
Hence the constant is at most Γ = N b ( a t o l + r t o l M e ) max i ∥ e i ∥ L 1 \Gamma=N_b(\mathrm{atol}+\mathrm{rtol}\,M_e)\max_i\lVert e_i\rVert_{L^1} Γ = N b ( atol + rtol M e ) max i ∥ e i ∥ L 1 . Therefore δ T V ( j ) : = Γ δ ( j ) \delta_{\mathrm{TV}}^{(j)}:=\Gamma\delta^{(j)} δ TV ( j ) := Γ δ ( j ) bounds the total-variation increments, and Proposition S-15 gives max β E β ( j ) ≤ A Γ δ ( j ) \max_{\beta}E_{\beta}^{(j)}\le A\Gamma\delta^{(j)} max β E β ( j ) ≤ A Γ δ ( j ) . At termination δ ( j ) ≤ 1 \delta^{(j)}\le1 δ ( j ) ≤ 1 , which gives the bound A Γ A\Gamma A Γ . The constant Γ \Gamma Γ , and hence the error bound, grows linearly with the basis size N b N_b N b , which is chosen together with Δ t \Delta t Δ t .
Limitations
Loose constants. The proof establishes the O ( 1 ) O(1) O ( 1 ) span complexity, but the convergence rate obtained is very loose compared to that obtained in practice, for instance in our benchmarks. This is because the Le Gland–Oudjane contraction ignores the observation, which can contribute greatly to forgetting. We are not aware of results that account for the observations and give a contraction rate computable from the actual data, with the possible exception of the recent work of Kim et al.[4 ] The proof therefore gives no insight into the actual mechanism of convergence, apart from the sparse observation regime, where we expect the bound to be close to sharp.
Mixing assumptions. (A3) makes the transition density uniformly bounded above and below, which in practice requires a compact latent state space. While our model satisfies this, many other state-space models do not (such as even the simple Kalman filter on R n \mathbb{R}^{n} R n ). A more general proof would accept weaker forms of mixing, and consequently worse span complexity. We expect O ( log N ) O(\log N) O ( log N ) in the general case, and still useful speed-up in practical cases.
Finite-dimensional representation. Assumption (A4) matches the implementation, which works with a finite basis and the WRMS norm. This makes the total variation to WRMS conversion simple. A proof that stops at convergence in L 2 L^{2} L 2 , for instance, without assuming a discretization, would be more elegant.
Partial formalization. The Lean formalization covers Section S1.8 and parts of Sections S1.6 and S1.7, but two gaps remain. First, Birkhoff’s contraction theorem and the Hilbert projective metric on measures are absent from Mathlib, as is the measure-level block operator of Le Gland–Oudjane, so Lemmas S-3(2) and S-4 are not formalized, rather enter as hypothesis in structure BlockForgetting. Second, Mathlib has no theory of stochastic differential equations, so the latent dynamics cannot be constructed, and we instead directly assume eigendecomposition results.
Implementation details
We use the biorthogonal 3.3 synthesis wavelet as the parametrization basis throughout, owing to its compact support and regularity, its synthesis functions being quadratic B-splines, continuously differentiable with bounded second derivative. For the computation, we use Gaussians on a n n n D grid, with equal spacing and σ \sigma σ corresponding to a 65 percent overlap between nearby basis, and N = 96 N = 96 N = 96 basis per dimension by default.
For the prediction step of Bayesian filtering, we proceed by diagonalization of the Fokker-Planck operator. To facilitate this, we internally use the self-adjoint operator L ~ = p e q − 1 / 2 L p e q 1 / 2 \tilde{L} = p_{\mathrm{eq}}^{-1/2}\mathcal{L}p_{\mathrm{eq}}^{1/2} L ~ = p eq − 1/2 L p eq 1/2 and convert back to probability densities when needed, as this form is more amenable to differentiation (lack of gauge freedom in the eigenvectors). We then assemble the matrix exponential propagator P = V ⋅ diag i ( exp ( D ⋅ Δ t ⋅ λ i ) ) ⋅ V T ⋅ S P = V \cdot\operatorname{diag}_{i}(\exp(D \cdot\Delta t \cdot\lambda_{i})) \cdot V^{\mathsf{T}} \cdot S P = V ⋅ diag i ( exp ( D ⋅ Δ t ⋅ λ i )) ⋅ V T ⋅ S with V the eigenvectors, λ i \lambda_i λ i the eigenvalues, S S S the computation basis Gram Matrix. Diagonalization is obtained with the built-in jax eigh routine. For the update step, we project onto a grid comprised of Gauss-Hermite quadrature nodes, then perform the multiplication of density pointwise at those nodes. We then reduce back to densities-as-vector using the Gauss-Hermite quadrature weights. We use a mixed precision scheme, where operator assembly, diagonalization and propagator assembly occur in double precision, while the filtering loop takes place in single precision. Final loglikelihood reduction is then conducted in double precision. All computation, including the Hamiltonian Monte Carlo sampling, take place on GPU.
Because the observation likelihood depends on the data Y 0 : K Y_{0:K} Y 0 : K but not on the model parameters θ \theta θ , we precompute them as a function of the emission parameter s s s , and project them in a Gaussian basis, the so-called data basis, at program start-up. For each evaluation of the likelihood, we project from data basis to latent coordinate Gauss-hermite node according to the emission function f θ e m ( x ) f_{\theta_{\mathrm{em}}}(x) f θ em ( x ) in a single large matrix computation. This reduce the filtering step, which is the critical path, to only the pointwise multiplication described below for the update step.
We use confining, exponential wall potential:
G w a l l ( x ) = k w ∑ i = 1 n [ e − a w ( x i − a i ) + e a w ( x i − b i ) ] (10) G_{\mathrm{wall}}(\mathbf{x}) = k_w \sum_{i=1}^{n} \left[e^{-a_w(x_i-a_i)} + e^{a_w(x_i-b_i)}\right] \tag*{(10)} G wall ( x ) = k w i = 1 ∑ n [ e − a w ( x i − a i ) + e a w ( x i − b i ) ] (10)
where k w = 20 k b T k_w = 20\,k_bT k w = 20 k b T sets the wall strength, and a w = 8 a_w = 8 a w = 8 controls the steepness. Of note, this particular G w a l l ( x ) G_{\mathrm{wall}}(\mathbf{x}) G wall ( x ) form is not essential to the method.
Since the landscape and emission function can only be inferred up to isometry, i.e. , the physics of the reflected (in 1D) or rotated system is indistinguishable, we use an isometry breaking prior, which can be of either of two type. For the first type, the center of probability mass prior, we compute the center of mass of the equilibrium distribution, and penalize loglikelihood when this point lies either to the left of the 1D landscape, or away from the lower coordinate quadrant in 2D. Similar quadrant convention can be used in dimension above 2. This penalty is the distance d d d to the allowed boundary, softened with the log ( 1 + e d ) \log(1+e^d) log ( 1 + e d ) softplus function to allow for gradient-based optimization. For the second type, the emission maximum prior, we compute the soft maximum of the emission function, and apply a penalty as described above to ensure it lies to the right of the 1D landscape, or away from the lower coordinate quadrant in 2D. The second type of prior is preferable when applicable (i.e. , when the emission is close to linear), as it imparts no bias in the inferred landscape, whereas the first has a small but non-negligible impact when both side of the landscape have similar probability density (i.e. , it forces slightly deeper wells on the right).
Additional benchmark results
We quantify the agreement between the PinT algorithm and sequential filters by the relative log-likelihood error
ε = ∣ log p W R − log p s e q ∣ max ( ∣ log p W R ∣ , ∣ log p s e q ∣ ) , (11) \varepsilon= \frac{\left|\log p_{\mathrm{WR}}-\log p_{\mathrm{seq}}\right|}{\max\left(\left|\log p_{\mathrm{WR}}\right|,\left|\log p_{\mathrm{seq}}\right|\right)}, \tag*{(11)} ε = max ( ∣ log p WR ∣ , ∣ log p seq ∣ ) ∣ log p WR − log p seq ∣ , (11)
normalised symmetrically so that ε ∈ [ 0 , 2 ] \varepsilon\in[0,2] ε ∈ [ 0 , 2 ] and neither evaluation is privileged as the denominator.
The single-GPU runtime of a likelihood-and-gradient evaluation is well described by a linear cost model in the trajectory length N N N , T ( N ) = T 0 + c N T(N)=T_0+cN T ( N ) = T 0 + c N , fitted to replicated benchmark runtimes. The intercept T 0 ≈ 3.9 T_0 \approx3.9 T 0 ≈ 3.9 ms is a fixed cost per evaluation, comprising operator assembly, prior evaluation and, above all, operator diagonalization. The slope c ≈ 0.63 c \approx0.63 c ≈ 0.63 μ \mu μ s is the average cost per time point of PinT filtering, including its repeated filtering of each block. It is not comparable with the 36–42 μ \mu μ s per time point of the sequential filter (main text, Figure 3 b), which runs as a latency-bound chain of matrix-vector products. The two terms are equal at N ∗ = T 0 / c ≈ 6300 N^* = T_0/c \approx6300 N ∗ = T 0 / c ≈ 6300 time points, below which the fixed cost dominates. The model fits closely beyond a few thousand time points, and slightly underestimates the runtime of the shortest trajectories. Since additional GPUs reduce only the per-time-point term, this fixed cost caps strong scaling at these lengths.
Figure 8 (PDF p. 74).
Figure S2. PinT iteration count as a function of trajectory length. Number of iterations required for the PinT filter to converge, at parameters near the maximum a posteriori estimate, as a function of total trajectory length, for three block lengths L L L . The count is constant over close to three orders of magnitude of trajectory length, consistent with a constant span, and shows no run-to-run variation. It is set by L L L and by the number of time steps the filter needs to forget its initial condition, here 12, and reaches its floor of two iterations, the minimum to compute inter-iteration differences, for L ≥ 12 L \ge12 L ≥ 12 .
Figure S3. Weak scaling parallel efficiency as a function of trajectory length. and number of GPU (symbol and color), with the ideal linear scaling as dashed line. Note that the noise, as well as the slight overshoot beyond perfect scaling, is due to JAX code generation, as the run-ton-run variability at exactly the same settings is below 1 percent. This is a known downside of high level frameworks where code generation is not manually controlled but tuned by heuristics.
Figure S4. PinT loglikelihood relative error as a function of the number of GPU compared to the sequential reference loglikelihood. The slight increase with GPU count reflects the changed order of floating-point summations, which are not associative, when the work is split across more devices.
Figure S5. PinT loglikelihood relative error as a function of the trajectory length (and number of GPU) compared to the sequential reference loglikelihood.
Gauge freedom and gauge fixing in the diffusion D coefficient
When D D D is inferred alongside the landscape and emission function, an affine freedom is present: for any α ≠ 0 \alpha\ne0 α = 0 and c ∈ R c \in\mathbb{R} c ∈ R ,
D → α 2 D , G ( x ) → G ( x − c α ) , f ( x ) → f ( x − c α ) (12) D \to\alpha^{2}D,\qquad G(x) \to G\left(\frac{x-c}{\alpha}\right),\qquad f(x) \to f\left(\frac{x-c}{\alpha}\right) \tag*{(12)} D → α 2 D , G ( x ) → G ( α x − c ) , f ( x ) → f ( α x − c ) (12)
leaves the observed process { Y t k } \{Y_{t_k}\} { Y t k } invariant. The fixed wall potential formally breaks this symmetry. Where G i n t e r i o r G_{\mathrm{interior}} G interior confines the dynamics to an effective domain [ a ′ , b ′ ] n ⊂ [ a , b ] n [a',b']^{n} \subset[a,b]^{n} [ a ′ , b ′ ] n ⊂ [ a , b ] n , however, the walls are barely explored and the degeneracy remains severe in practice.
We therefore fix D D D rather than infer it, removing the scaling freedom α \alpha α . Choosing a value for which the latent trajectory spans the whole domain [ a , b ] n [a,b]^{n} [ a , b ] n removes the translation freedom c c c as well, leaving only isometries: reflections in one dimension, rotations in two. These we eliminate with a prior that lightly biases the centre of mass of the equilibrium distribution toward a conventional location (§ 4.2 ).
To choose the value of D D D , we first treat it as a free parameter rather than a constant, inferring it alongside G G G and f f f . A short posterior ascent followed by a brief HMC run then locates the range of D D D the posterior supports, in which the latent landscape spans the whole domain. We fix a value in that range and report it alongside the posterior distributions.
Note that this is a separate issue from whether a constant diffusion D D D , i.e., independent of latent location, is appropriate. Even with a location-dependent D D D , there is a gauge between the length of the latent dimensions and a multiplicative prefactor for D D D , such that gauge fixing must still be done. Note also that in 1 dimension, a location-dependent D D D can be absorbed into the landscape shape (stretching when D D D is locally low, compressing when D D D is locally high). However, beyond 1 dimensions, our choice of a global D D D is a modelling choice (as stretching of the landscape cannot account for local D D D ).
Wavelet representation and the Besov prior
Figure 9 (PDF p. 77).
We regularize using Besov function spaces B p , p s B^{s}_{p,p} B p , p s , whose members have a regularity set by the smoothness order s s s and the sparsity type p p p .⁵,⁶ Besov regularity can be enforced directly by expressing landscape and emission function in a wavelet basis (Figure S6 ):
Figure S6. Wavelet representation and Besov prior. a, Biorthogonal 3.3 synthesis basis functions: the scaling functions φ 3 \varphi_{3} φ 3 (blue) capture coarse shape, while wavelet functions ψ 3 \psi_{3} ψ 3 , ψ 2 \psi_{2} ψ 2 , ψ 1 \psi_{1} ψ 1 (red) encode progressively finer detail. Translates at each level shown faded. b, A sample draw of coefficients from the prior, illustrating how each coefficient weights the corresponding basis functions. Coefficients at finer levels are shrunk toward zero, suppressing high-frequency detail unless supported by data. c, Prior standard deviation σ j / σ 0 \sigma_{j}/\sigma_{0} σ j / σ 0 as a function of detail level j j j for three Besov classes B p , p s B^{s}_{p,p} B p , p s . Higher smoothness s s s and lower p p p produce steeper decay, more aggressively regularizing fine-scale structure. Insets show the corresponding coefficient prior density (Laplace for p = 1 p=1 p = 1 , Gaussian for p = 2 p=2 p = 2 ). d, Representative functions drawn from each prior, showing how s s s controls smoothness (rougher at left, smoother at right) and p p p controls sparsity structure (piecewise features for p = 1 p=1 p = 1 versus globally smooth variation for p = 2 p=2 p = 2 ).
g = ∑ k c k φ φ k + ∑ j = 1 J ∑ k c j , k ψ ψ j , k , (13) g = \sum_{k} c^{\varphi}_{k}\,\varphi_{k} + \sum_{j=1}^{J}\sum_{k} c^{\psi}_{j,k}\,\psi_{j,k}, \tag*{(13)} g = k ∑ c k φ φ k + j = 1 ∑ J k ∑ c j , k ψ ψ j , k , (13)
where φ k \varphi_{k} φ k are scaling functions capturing the coarse shape and ψ j , k \psi_{j,k} ψ j , k are wavelet functions at successively finer resolution levels j = 1 , … , J j = 1,\ldots,J j = 1 , … , J . Membership in B p , p s B^{s}_{p,p} B p , p s is enforced by assigning each detail coefficient a level-dependent prior
π ( c j , k ψ ) ∝ exp ( − ∣ c j , k ψ / σ j ∣ p ) , (14) \pi(c^{\psi}_{j,k}) \propto\exp\left(-\left|c^{\psi}_{j,k}/\sigma_{j}\right|^{p}\right), \tag*{(14)} π ( c j , k ψ ) ∝ exp ( − c j , k ψ / σ j p ) , (14)
with scale decaying geometrically across levels:
σ j = σ 0 ⋅ 2 − j α , α = s + 1 2 − 1 p , (15) \sigma_{j} = \sigma_{0}\cdot2^{-j\alpha}, \qquad\alpha= s + \frac{1}{2} - \frac{1}{p}, \tag*{(15)} σ j = σ 0 ⋅ 2 − j α , α = s + 2 1 − p 1 , (15)
where σ 0 \sigma_{0} σ 0 sets the overall prior scale and the exponent α \alpha α controls how aggressively fine-level coefficients are shrunk toward zero. For p = 2 p=2 p = 2 the prior is Gaussian; for p = 1 p=1 p = 1 it is Laplace, thus sparsity-enforcing. This prior is discretization-invariant in the sense of Lassas et al.⁷ so the expansion can be truncated at a finite level J J J without altering the prior at resolved scales.
The scaling coefficients c k φ c^{\varphi}_{k} c k φ determine the coarse shape of the function (overall depth and broad structure), which is dictated by the physical system rather than by smoothness assumptions: their scale σ 0 φ \sigma^{\varphi}_{0} σ 0 φ is accordingly set independently and more permissively.
Inference protocol parameters
We now list the parameters common to each validation or application case:
Table S1. Settings common to all inference runs. Per-experiment settings are given in Table S4 –Table S8 . RT is evaluated at the run temperature.
Table S4. ENSO (Southern Oscillation Index). Experiment enso_A71. † Step size in Gram-whitened coordinates.
Table S8. Landscape Besov parameters of the sensitivity sweep (Table S7 ). α = s + 1 2 − 1 p \alpha= s + \frac{1}{2} - \frac{1}{p} α = s + 2 1 − p 1 is the level-decay exponent of the prior scale. Step sizes are ranges over the four chains.
Table S7. Prior sensitivity sweep on landscape 10 / emission 8. Experiment newlandscan_l010_e008_A07: eight runs differing only in the landscape Besov parameters (Table S8 ). Ground truth as in Table S2 .
We now list the parameters for each system:
Validation system 1
Validation system 2
Table S3. Synthetic validation, landscape 10 / emission 8. Experiment newlandscan_l010_e008_A02. Ground truth as in Table S2 .
Table S2. Synthetic validation, landscape 9 / emission 7. Experiment newlandscan_l009_e007_A02. Ground truth: D = 1 D = 1 D = 1 , Gaussian observation noise σ = 0.25 \sigma= 0.25 σ = 0.25 , Euler–Maruyama step 5 × 10 − 4 5 \times10^{-4} 5 × 1 0 − 4 , trajectory duration 1200.
ENSO application example
Domain boundary. The credible intervals of the landscape widen toward the edges of the domain, where extreme observations are rare. There, the stiff exponential wall imposed at the domain boundary compresses the landscape, and the latent coordinate saturates for the strongest events of either sign (main text, Figure 5 b). A flexible, inferable wall stiffness is a natural extension of the model.
Nano-aperture optical tweezer application example
Table S5. Nano-aperture optical tweezer, BSA at 37 °C. Experiment not_1_37deg_A31. ‡ Chains 3 and 5 stopped at 10 000 samples.
Model checks. The observed autocorrelation exceeds the posterior predictive credible interval from roughly 20 to 135 ms of lag (main text, Figure 4 b). As the excess is absent at the shortest lags, frame averaging and particle inertia, which would act at those timescales, are unlikely causes. Its timescale, slower than any relaxation within the wells (≤ 20.8 \le20.8 ≤ 20.8 ms) but faster than inter-well transitions (325 ms), indicates a slow degree of freedom acting within the wells rather than on barrier crossings, such as conformational substates hidden by the one-dimensional projection. Slow drift of the experimental apparatus could produce a similar excess. The ten frame-to-frame jumps of 4 to 5 standard deviations (main text, Figure 4 c) may be rare instrumental artifacts, or entropically disfavored but faster crossings of the landscape, another artifact of the one-dimensional projection.
Conformer assignment. The two wells could correspond to the F and E conformers of BSA, respectively, following the assignment of Peters et al.⁸ Because the two analyses use different models, the correspondence between their states and our wells is uncertain.
LogVIX application example
Table S6. Implied volatility (logVIX). Experiment logvix_A61.
Prior sensitivity scans
Figure S7 shows how the inferred landscape depends on the prior hyperparameters and on the amount of data, all other settings being at their defaults. The prior scale σ 0 \sigma_{0} σ 0 and multiplier C s C_{s} C s , which together set the expected free-energy range, have virtually no effect over the scanned range (a), the data overriding the prior. The weight w s y m w_{\mathrm{sym}} w sym of the isometry-breaking prior likewise has no noticeable effect between 1 and 20 (c), as expected for a weak prior whose only role is to select one orientation of the latent coordinate. The posterior is more sensitive to the smoothness order s s s of the Besov class B 2 , 2 s B^{s}_{2,2} B 2 , 2 s targeted by the prior (b, Methods in the main text, and Supplementary Information S5). For p = 2 p = 2 p = 2 , the negative log-prior is, up to constants, the squared H s H^{s} H s norm of the landscape, so that s = 2 s = 2 s = 2 is the lowest order penalizing its curvature. We want curvature regularized because the second derivative of the landscape enters the Fokker–Planck operator, through the effective potential of its symmetrized form. Strictly, samples of this prior lie almost surely in B 2 , 2 t B^{t}_{2,2} B 2 , 2 t only for t < s − 1 / 2 t < s - 1/2 t < s − 1/2 ,2 so that s = 2 s = 2 s = 2 sets a penalty on curvature rather than the regularity of every sample, which the finite quadratic-spline expansion guarantees instead. At s = 1 s = 1 s = 1 , the curvature is unpenalized and the posterior is far from converged, its chains remaining in widely different basins even after about 240 000 draws per chain. At s = 1.5 s = 1.5 s = 1.5 , the landscape is recovered, though the posterior is slightly unconverged after about 256 000 draws per chain. At s = 2.5 s = 2.5 s = 2.5 and 3, higher derivatives are penalized too, and the prior can no longer accommodate the sharp features of the true landscape. At s = 2.5 s = 2.5 s = 2.5 , the bands exclude the ground truth in places, and at s = 3 s = 3 s = 3 the main barrier is underestimated and the two small wells within the rightmost basin are no longer resolved. The validation ground truths were themselves drawn from an s = 2 s = 2 s = 2 prior before modification (Methods in the main text), so this scan favors the default by construction, and s s s should be relaxed where finer detail is expected. Finally, the posterior concentrates on the ground truth as the trajectory lengthens (d), its credible intervals narrowing from N = 10 000 N = 10\,000 N = 10 000 to 50,000 time steps.
Figure S7. Prior and data sensitivity of the inferred landscape. Posterior mean (solid line), 95% credible interval (band) and ground truth (dashed), as in main text Figure 2 . Highlighted panels mark the defaults used throughout this work. (a) Prior scale σ 0 \sigma_0 σ 0 (k B T k_{\mathrm{B}}T k B T ) of the coarsest wavelet level and multiplier C s C_s C s of the coarsest scale function, on validation system 1. (b) Smoothness order s s s of the Besov prior, at p = 2 p = 2 p = 2 , on validation system 2. (c) Weight w s y m w_{\mathrm{sym}} w sym of the isometry-breaking prior, on validation system 2. (d) Trajectory length N N N , in time steps, on a double-well landscape with linear emission, chosen to isolate the effect of the amount of data.