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 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. |
Year | Venue | Keywords |
---|---|---|
2013 | ELECTRONIC JOURNAL OF COMBINATORICS | random walk |
Field | DocType | Volume |
Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Random walk,Expected value,Mathematics | Journal | 20.0 |
Issue | ISSN | Citations |
3.0 | 1077-8926 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
János Pach | 1 | 2366 | 292.28 |
Gábor Tardos | 2 | 1261 | 140.58 |