Discrete Random Walks on One-Sided ``Periodic'' Graphs

Abstract : In this paper we consider discrete random walks on infinite graphs that are generated by copying and shifting one finite (strongly connected) graph into one direction and connecting successive copies always in the same way. With help of generating functions it is shown that there are only three types for the asymptotic behaviour of the random walk. It either converges to the stationary distribution or it can be approximated in terms of a reflected Brownian motion or by a Brownian motion. In terms of Markov chains these cases correspond to positive recurrence, to null recurrence, and to non recurrence.
Type de document :
Communication dans un congrès
Cyril Banderier and Christian Krattenthaler. Discrete Random Walks, DRW'03, 2003, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), pp.83-94, 2003, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01183939
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 09:08:18
Dernière modification le : jeudi 11 mai 2017 - 01:03:08
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:38:11

Fichier

dmAC0108.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01183939, version 1

Collections

Citation

Michael Drmota. Discrete Random Walks on One-Sided ``Periodic'' Graphs. Cyril Banderier and Christian Krattenthaler. Discrete Random Walks, DRW'03, 2003, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), pp.83-94, 2003, DMTCS Proceedings. 〈hal-01183939〉

Partager

Métriques

Consultations de la notice

84

Téléchargements de fichiers

132