Memory-Dependent Interval Markov Chain Abstractions of Stochastic Dynamics
Abstract
Finite-state interval Markov-chain (IMC) abstractions provide sound verification and performance bounds for continuous-state stochastic systems by enclosing cell-to-cell transition probabilities and costs in intervals. Finite-state Markovian abstractions are generally lossy, as state aggregation often destroys the Markov property. Recently, memory-dependent Markov-chain (MC) abstractions of stochastic systems have been developed to mitigate this by recording recently visited cells. In this paper, we develop the memory-dependent extension of IMC abstractions. Building on the insight that memory narrows the family of state distributions that could occur inside the current cell, we prove that memory tightens the local intervals, at the price of a larger abstraction. We also formulate no-memory IMC abstractions, tightening classic IMC abstraction intervals without enlarging the state space. To characterize spatial refinement relative to memory, we derive two cost-guarantee tightness upper bounds. The bounds depend, respectively, on cell size, and on the worst-case remaining distributional ambiguity after filtering over the remembered past. We then specialize our result to linear-Gaussian systems, for which we derive a closed-form upper bound on this ambiguity. Numerical examples show that the memory-dependent and no-memory constructions can produce tighter expected-cost intervals than comparable partition refined models.
Related
- Learning Memory-Dependent Neural Network Correlation Potentials for Accurate Electron Dynamics
- Asymptotic behaviour for escaping an interval by Lévy flights under stochastic resetting
- On the dynamics of self-consistent transfer operators for interval maps with singularities
- Singular Stochastic Heat Equations with Fractional Memory
- Safe Controller Synthesis for Nonlinear Switched Systems via Probabilistic Abstractions
BibTeX
@misc{zutphen2026memorydependent,
title = {{Memory-Dependent Interval Markov Chain Abstractions of Stochastic Dynamics}},
author = {Menno van Zutphen and Adrien Banse and Domagoj Herceg and Giannis Delimpaltadakis and Duarte Antunes},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02950},
eprint = {2610.02950},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02950},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Memory-Dependent Interval Markov Chain Abstractions of Stochastic Dynamics
AU - Menno van Zutphen
AU - Adrien Banse
AU - Domagoj Herceg
AU - Giannis Delimpaltadakis
AU - Duarte Antunes
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02950
UR - https://arxiv.org/abs/2610.02950
AB - Finite-state interval Markov-chain (IMC) abstractions provide sound verification and performance bounds for continuous-state stochastic systems by enclosing cell-to-cell transition probabilities and costs in intervals. Finite-state Markovian abstractions are generally lossy, as state aggregation often destroys the Markov property. Recently, memory-dependent Markov-chain (MC) abstractions of stochastic systems have been developed to mitigate this by recording recently visited cells. In this paper, we develop the memory-dependent extension of IMC abstractions. Building on the insight that memory narrows the family of state distributions that could occur inside the current cell, we prove that memory tightens the local intervals, at the price of a larger abstraction. We also formulate no-memory IMC abstractions, tightening classic IMC abstraction intervals without enlarging the state space. To characterize spatial refinement relative to memory, we derive two cost-guarantee tightness upper bounds. The bounds depend, respectively, on cell size, and on the worst-case remaining distributional ambiguity after filtering over the remembered past. We then specialize our result to linear-Gaussian systems, for which we derive a closed-form upper bound on this ambiguity. Numerical examples show that the memory-dependent and no-memory constructions can produce tighter expected-cost intervals than comparable partition refined models.
ER -