We study a discrete time self-interacting random process on graphs, which we call greedy random walk. The walker is located initially at some vertex. As time evolves, each vertex maintains the set of adjacent edges touching it that have not yet been crossed by the walker. At each step, the walker, being at some vertex, picks an adjacent edge among the edges that have not traversed thus far according to some (deterministic or randomized) rule. If all the adjacent edges have already been traversed, then an adjacent edge is chosen uniformly at random. After picking an edge the walker jumps along it to the neighbouring vertex. We show that the expected edge cover time of the greedy random walk is linear in the number of edges for certain natural families of graphs. Examples of such graphs include the complete graph, even degree expanders of logarithmic girth, and the hypercube graph. We also show that GRW is transient in d for all d ≥ 3.

Orenshtein, T., Shinkar, I. (2014). Greedy random walk. COMBINATORICS PROBABILITY & COMPUTING, 23(2), 269-289 [10.1017/S0963548313000552].

Greedy random walk

Orenshtein T.
;
2014

Abstract

We study a discrete time self-interacting random process on graphs, which we call greedy random walk. The walker is located initially at some vertex. As time evolves, each vertex maintains the set of adjacent edges touching it that have not yet been crossed by the walker. At each step, the walker, being at some vertex, picks an adjacent edge among the edges that have not traversed thus far according to some (deterministic or randomized) rule. If all the adjacent edges have already been traversed, then an adjacent edge is chosen uniformly at random. After picking an edge the walker jumps along it to the neighbouring vertex. We show that the expected edge cover time of the greedy random walk is linear in the number of edges for certain natural families of graphs. Examples of such graphs include the complete graph, even degree expanders of logarithmic girth, and the hypercube graph. We also show that GRW is transient in d for all d ≥ 3.
Articolo in rivista - Articolo scientifico
2010 Mathematics subject classification: Primary 05C85; Secondary 60K35;
English
20-nov-2013
2014
23
2
269
289
none
Orenshtein, T., Shinkar, I. (2014). Greedy random walk. COMBINATORICS PROBABILITY & COMPUTING, 23(2), 269-289 [10.1017/S0963548313000552].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/362295
Citazioni
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 8
Social impact