Premium
Ranking graphs through hitting times of Markov chains
Author(s) -
De Santis Emilio
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20998
Subject(s) - markov chain , dice , hitting time , digraph , transitive relation , combinatorics , mathematics , event (particle physics) , discrete mathematics , independent and identically distributed random variables , markov chain mixing time , construct (python library) , graph , markov property , computer science , random variable , markov model , statistics , physics , quantum mechanics , programming language
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 than1 2if and only if ( i , j ) ∈ E → . This result is related to various paradoxes in probability theory, concerning in particular non‐transitive dice.