Ranking graphs through Markov chains and hitting times

Abstract

In the present paper we show that for any given digraph $\mathbb{G}=([n],\vec{E})$, i.e. 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,\dots ,T_n$ on this chain such that the probability of the event $T_i>T_j$, for any $i,j=1,\dots n$, is larger than $\frac{1}{2}$ if and only if $(i,j)\in \vec{E}$. This result is related to various paradoxes in probability theory, concerning in particular non-transitive dice.

14 pages

References in corpus (1)

• Load-sharing dependence models and construction of voting situations for any arbitrary ranking schemes

Cited by in corpus (1)

• Load-sharing dependence models and construction of voting situations for any arbitrary ranking schemes