Hitting Times in Markov Chains with Restart and their Application to Network Centrality
Le Temps de Premier Passage dans les Processus de Markov avec Redémarrage et leur Application à la Mesure de Centralité de Réseau
Résumé
Motivated by applications in telecommunications, computer science
and physics, we consider a discrete-time Markov process with
restart. At each step the process either
with a positive probability restarts from a given distribution, or
with the complementary probability continues according to a Markov
transition kernel. The main contribution of the present work is that
we obtain an explicit expression for the expectation of the hitting
time (to a given target set) of the process with restart.
The formula is convenient when considering the problem of optimization
of the expected hitting time with respect to the restart probability.
We illustrate our results with two examples
in uncountable and countable state spaces and
with an application to network centrality.
Motivé par diverses applications provenant de télécommunications, informatique
et de la physique, nous considérons un processus générale de Markov dans l'espace de Borel
avec une possibilité de redémarrage. A chaque étape, avec une probabilité le processus
redémarre a partir d'une distribution donnée et avec la probabilité complémentaire
le processus continue l'évolution selon une noyau de Markov.
Nous étudions l'espérance du temps de premier passage
à l'ensemble donné. Nous obtenons une formule explicite pour l'espérance du temps
de premier passage et démontrons que le processus avec redémarrage est Harris positif récurrent.
Ensuite, nous établissons que les assertions suivantes sont équivalentes :
(a) le fait d'être limité (par rapport à l'état initiale) de l'espérance du temps
de premier passage; (b) la finitude de l'espérance du temps de premier passage
pour presque tous les états initiaux par rapport à la probabilité invariante unique;
et, (c) l'ensemble cible est de mesure positive par rapport à la
probabilité invariante. Enfin, nous illustrons nos résultats théoriques avec
deux exemples dans les espaces dénombrables et non dénombrables et avec l'application
à la mesure de centralité de réseau.
Origine : Fichiers produits par l'(les) auteur(s)