Ranking graphs through hitting times of Markov chains
Random Structures & Algorithms · 2021-09 · 59 (2) · 189-203
DOI: 10.1002/rsa.20998 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 04.02.2021. Verfasst von Emilio De Santis. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 23 Literaturangaben.
Abstract (Originalsprache)
In the present paper we show that for any given digraph , that is, an oriented graph without self‐loops and 2‐cycles, one can construct a 1‐dependent Markov chain and n identically distributed hitting times T 1 , … , T n on this chain such that the probability of the event T i > T j , for any i , j = 1, … , n , is larger than if and only if . This result is related to various paradoxes in probability theory, concerning in particular non‐transitive dice.
Zitieren
APA
Santis, E. D. (2021). Ranking graphs through hitting times of Markov chains. Random Structures & Algorithms, 59(2), 189-203. https://doi.org/10.1002/rsa.20998
Vancouver
Santis ED. Ranking graphs through hitting times of Markov chains. Random Structures & Algorithms. 2021;59(2):189-203. doi:10.1002/rsa.20998
BibTeX
@article{Santis2021,
author = {Santis, Emilio De},
title = {Ranking graphs through hitting times of Markov chains},
journal = {Random Structures & Algorithms},
year = {2021},
volume = {59},
number = {2},
pages = {189--203},
doi = {10.1002/rsa.20998}
}
EUVIMED