Ranking graphs through hitting times of Markov chains. Issue 2 (4th February 2021)

• Record Type: Journal Article
• Authors: De Santis, Emilio
• Is Part Of: Random structures & algorithms. Volume 59:Issue 2(2021)
• Page Start: 189
• Page End: 203
• Publication Date: 2021-02-04
• Subjects: 1‐dependent Markov chain -- ordering -- paradoxes in probability theory; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20998
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: In the present paper we show that for any given digraph 𝔾 = ( [ 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 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 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.