The range of a random walk on a comb

MaRDI QIDQ396906zbMATH OpenFDO

Authors János Pach, Gábor Tardos

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.6360

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

random walk

Mathematics Subject Classification ID

Random walks on graphs (05C81)

Abstract: The graph obtained from the integer grid Z x 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 Cs'aki, Cs"org"o, F"oldes, R'ev'esz, and Tusn'ady by showing that the expected number of vertices visited by a random walk on the comb after n steps is (1/(2sqrt{2pi})+o(1))sqrt nlog n. This contradicts a claim of Weiss and Havlin.

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

Recommendations

• Asymptotic behaviour of the simple random walk on the 2-dimensional comb
• Random walks on combs
• Random walks on comb-type subsets of \(\mathbb{Z}^2\)
• On the area of the largest square covered by a comb-random-walk
• On the local time of random walk on the 2-dimensional comb

Cited in

(7)

• Random walks on comb-type subsets of \(\mathbb{Z}^2\)
• Asymptotic behaviour of the simple random walk on the 2-dimensional comb
• Random walks on uniform and non-uniform combs and brushes
• Random walks on combs
• The range of a rotor walk
• Eternal family trees and dynamics on unimodular random graphs
• On the area of the largest square covered by a comb-random-walk

This page was built for publication: The range of a random walk on a comb

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396906)