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

Škulj, Damjan (author)

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.

• Language: English
• Keywords: random walk, weighted graph, interval weight, imprecise Markov chain, reversibility, inhomogeneous Markov chain, uncertainty
• Work type: Other
• Typology: 1.08 - Published Scientific Conference Contribution
• Organization: FDV - Faculty of Social Sciences
• Publication status: Published
• Publication version: Version of Record
• Year: 2025
• Number of pages: Str. 252-262
• PID: 20.500.12556/RUL-181276
• UDC: 519.217
• ISSN on article: 2640-3498
• COBISS.SI-ID: 273534467
• Publication date in RUL: 30.03.2026

Record is a part of a proceedings

• Title: International Symposium on Imprecise Probabilities: Theories and Applications, 15-18 July 2025, Zentrum für interdisziplinäre Forschung, Bielefeld, Germany
• COBISS.SI-ID: 273531651

Record is a part of a journal

• Title: Proceedings of Machine learning research
• Shortened title: Proc. Mach. Learn. Res.
• Publisher: JMLR
• ISSN: 2640-3498
• COBISS.SI-ID: 27067395

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Projects

• Funder: ARIS - Slovenian Research and Innovation Agency
• Project number: P5-0168
• Name: Družboslovna metodologija, statistika in informatika