  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 been crossed yet 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 walk jumps along it to the neighboring
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 $\Z^d$
for all $d \geq 3$.
