Non-backtracking random walk
= Non-backtracking random walk
A non-backtracking random walk remembers its preceding vertex and excludes that neighbor from the next choice. At vertices of degree at least two, it is a <Markov chain> on directed edges: $(a,b)$ moves to $(b,c)$ with probability $1/(\deg b-1)$ for each neighbor $c\ne a$. Dead ends require an additional convention. An initial vertex without a preceding edge uses the ordinary first-step neighbor distribution.