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

dmtcs:3344 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03) - https://doi.org/10.46298/dmtcs.3344
Discrete Random Walks on One-Sided ``Periodic'' GraphsArticle

Authors: Michael Drmota 1

  • 1 Institut für Geometrie

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.


Volume: DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)
Section: Proceedings
Published on: January 1, 2003
Imported on: May 10, 2017
Keywords: discrete random walk,generating functions,singularity analysis,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

1 Document citing this article

Consultation statistics

This page has been seen 339 times.
This article's PDF has been downloaded 238 times.