The range of a random walk on a comb

MaRDI QIDQ396906zbMATHFDO

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.

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