 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/(\mathrm{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.