Random walks on graphs with interval weights as a model of reversible imprecise Markov chains

Damjan Škulj
Proceedings of the Fourteenth International Symposium on Imprecise Probabilities: Theories and Applications, PMLR 290:252-262, 2025.

Abstract

We consider random walks on weighted graphs where the edge weights are interval-valued, reflecting uncertainty in the relationships between vertices. We study this model in the framework of reversible imprecise Markov chains by viewing them as sets of precise inhomogeneous Markov chains. We define and analyze the notion of reversibility for such sets by extending classical reversibility concepts to the imprecise setting. These concepts are then applied to interval-weighted random walks, where the individual weight functions may not be symmetric but their sets exhibit symmetry. Our approach provides a basis for analyzing random walks in environments with uncertain or incomplete information.

Cite this Paper

BibTeX
@InProceedings{pmlr-v290-skulj25a, title = {Random walks on graphs with interval weights as a model of reversible imprecise Markov chains}, author = {\v{S}kulj, Damjan}, booktitle = {Proceedings of the Fourteenth International Symposium on Imprecise Probabilities: Theories and Applications}, pages = {252--262}, year = {2025}, editor = {Destercke, Sébastien and Erreygers, Alexander and Nendel, Max and Riedel, Frank and Troffaes, Matthias C. M.}, volume = {290}, series = {Proceedings of Machine Learning Research}, month = {15--18 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v290/main/assets/skulj25a/skulj25a.pdf}, url = {https://proceedings.mlr.press/v290/skulj25a.html}, abstract = {We consider random walks on weighted graphs where the edge weights are interval-valued, reflecting uncertainty in the relationships between vertices. We study this model in the framework of reversible imprecise Markov chains by viewing them as sets of precise inhomogeneous Markov chains. We define and analyze the notion of reversibility for such sets by extending classical reversibility concepts to the imprecise setting. These concepts are then applied to interval-weighted random walks, where the individual weight functions may not be symmetric but their sets exhibit symmetry. Our approach provides a basis for analyzing random walks in environments with uncertain or incomplete information.} }
Endnote
%0 Conference Paper %T Random walks on graphs with interval weights as a model of reversible imprecise Markov chains %A Damjan Škulj %B Proceedings of the Fourteenth International Symposium on Imprecise Probabilities: Theories and Applications %C Proceedings of Machine Learning Research %D 2025 %E Sébastien Destercke %E Alexander Erreygers %E Max Nendel %E Frank Riedel %E Matthias C. M. Troffaes %F pmlr-v290-skulj25a %I PMLR %P 252--262 %U https://proceedings.mlr.press/v290/skulj25a.html %V 290 %X We consider random walks on weighted graphs where the edge weights are interval-valued, reflecting uncertainty in the relationships between vertices. We study this model in the framework of reversible imprecise Markov chains by viewing them as sets of precise inhomogeneous Markov chains. We define and analyze the notion of reversibility for such sets by extending classical reversibility concepts to the imprecise setting. These concepts are then applied to interval-weighted random walks, where the individual weight functions may not be symmetric but their sets exhibit symmetry. Our approach provides a basis for analyzing random walks in environments with uncertain or incomplete information.
APA
Škulj, D.. (2025). Random walks on graphs with interval weights as a model of reversible imprecise Markov chains. Proceedings of the Fourteenth International Symposium on Imprecise Probabilities: Theories and Applications, in Proceedings of Machine Learning Research 290:252-262 Available from https://proceedings.mlr.press/v290/skulj25a.html.

Related Material