In the present paper we show that 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 chainandnidentically distributed hitting timesT1,...,Tn on this chain such that the probability of the event Ti bigger than Tj (for i,j=1,...,n),is larger than1/2 if and only if (i,j)∈E.This result is related to various paradoxesin probability theory,concerning in particular non-transitive dice.
Ranking graphs through hitting times of Markov chains / DE SANTIS, Emilio. - In: RANDOM STRUCTURES & ALGORITHMS. - ISSN 1042-9832. - 59:2(2021), pp. 189-203. [10.1002/rsa.20998]
Ranking graphs through hitting times of Markov chains
Emilio De Santis
2021
Abstract
In the present paper we show that 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 chainandnidentically distributed hitting timesT1,...,Tn on this chain such that the probability of the event Ti bigger than Tj (for i,j=1,...,n),is larger than1/2 if and only if (i,j)∈E.This result is related to various paradoxesin probability theory,concerning in particular non-transitive dice.| File | Dimensione | Formato | |
|---|---|---|---|
|
DeSantis_postprint_Ranking-graphs_2021.pdf
accesso aperto
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
353.5 kB
Formato
Adobe PDF
|
353.5 kB | Adobe PDF | |
|
DeSantis_Ranking-graphs_2021.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
332.52 kB
Formato
Adobe PDF
|
332.52 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
