Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. The Range of a Random Walk on a Comb
 
research article

The Range of a Random Walk on a Comb

Pach, Janos  
•
Tardos, Gabor
2013
Electronic Journal Of Combinatorics

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 Csaki, Csorgo, Foldes, Revesz, and Tusnady by showing that the expected number of vertices visited by a random walk on the comb after n steps is (1/2 root 2 pi + o(1)) root n log n. This contradicts a claim of Weiss and Havlin.

  • Details
  • Metrics
Type
research article
DOI
10.37236/3571
Web of Science ID

WOS:000325472100005

Author(s)
Pach, Janos  
Tardos, Gabor
Date Issued

2013

Publisher

Electronic Journal Of Combinatorics

Published in
Electronic Journal Of Combinatorics
Volume

20

Issue

3

Start page

P59

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Available on Infoscience
December 9, 2013
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/97723
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés