Greedy Random Walk

DOI10.1017/S0963548313000552zbMATH Open1286.05159arXiv1101.5711OpenAlexW3104596862MaRDI QIDQ5410258FDOQ5410258

Authors: Tal Orenshtein, Igor Shinkar 

Publication date: 16 April 2014

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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 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 $$ for all $dgeq3$.

Full work available at URL: https://arxiv.org/abs/1101.5711

Recommendations

• Random walk on random walks
• Impatient random walk
• Greedy walk on the real line
• The greedy walk on an inhomogeneous Poisson process
• Randomly observed random walks
• Rational Random Walks
• A randomized variant of the Gröbner Walk
• Dirichlet random walks
• Reinforced random walk

zbMATH Keywords

discrete time self-interacting random process on graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Random walks on graphs (05C81)

Cites Work

• Expander graphs and their applications
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• A tight lower bound on the cover time for random walks on graphs
• A survey of random processes with reinforcement
• Random walk covering of some special trees
• Excited random walk
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• The power of choice in random walks: An empirical study
• Self-Avoiding Walks on Hyperbolic Graphs
• Bounds on the cover time
• Recurrence properties of Lorentz lattice gas cellular automata
• Linear cover time is exponentially unlikely

Cited In (10)

• The cover time of a biased random walk on a random cubic graph
• The greedy walk on an inhomogeneous Poisson process
• Deterministic walks with choice
• Distribution of the smallest visited point in a greedy walk on the line
• Once reinforced random walk on \(\mathbb{Z}\times\gamma\)
• Random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time
• Vacant sets and vacant nets: component structures induced by a random walk
• The power of two choices for random walks
• The cover time of a biased random walk on a random regular graph of odd degree
• The cover time of a biased random walk on a random regular graph of odd degree

This page was built for publication: Greedy Random Walk

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5410258)