Discrete Mathematics & Theoretical Computer Science |

3344

- 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.

Source: HAL:hal-01183939v1

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]

This page has been seen 196 times.

This article's PDF has been downloaded 167 times.