The range of a random walk on a comb
type: Item
instance of: scholarly article
title: The range of a random walk on a comb
zbMATH Open document ID: 1295.05215
author: János Pach
author: Gábor Tardos
published in: The Electronic Journal of Combinatorics
publication date: 2014-08-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/1309.6360
review text: Summary: The graph obtained from the integer grid \(\mathbb{Z}\times\mathbb{Z}\) by the removal of all horizontal edges that do not belong to the \(x\)-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex \(v\), in the next step it will visit one of the neighbors of \(v\), each with probability \(1/d(v)\), where \(d(v)\) denotes the degree of \(v\). We answer a question of \textit{E. Csáki} et al. [Electron. J. Probab. 14, 2371--2390 (2009; Zbl 1190.60020)] by showing that the expected number of vertices visited by a random walk on the comb after \(n\) steps is \((\frac1{2\sqrt{2\pi}}+o(1))\sqrt{n}\log n.\) This contradicts a claim of \textit{G. H. Weiss} and \textit{Sh. Havlin} [``Some properties of a random walk on a comb structure'', Physica A 134, 474--482 (1986)].
Mathematics Subject Classification ID: 05C81
zbMATH DE Number: 6330331
zbMATH Keywords: random walk
MaRDI profile type: Publication
arXiv ID: 1309.6360
description: scientific article; zbMATH DE number 6330331