We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Ranking graphs through hitting times of Markov chains.
- Authors
De Santis, Emilio
- Abstract
In the present paperwe showthat for any given digraph G = ([n], E), 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 T1, ..., Tn on this chain such that the probability of the event Ti >Tj, for any i, j=1, ..., n, is larger than 1 2 if and only if (i, j) E. This result is related to various paradoxes in probability theory, concerning in particular non-transitive dice.
- Subjects
MARKOV processes; PROBABILITY theory; DIRECTED graphs
- Publication
Random Structures & Algorithms, 2021, Vol 59, Issue 2, p189
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20998