The range of a random walk on a comb

zbMATH Open1295.05215arXiv1309.6360MaRDI QIDQ396906FDOQ396906

Authors: János Pach, Gábor Tardos 

Publication date: 14 August 2014

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

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.

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

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

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

zbMATH Keywords

random walk

Mathematics Subject Classification ID

Random walks on graphs (05C81)

Cited In (7)

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