The homotopical reduction of a nearest neighbor random walk*

Consider a nearest neighbor random walk on a graph G and discard all the segments of its trajectory that are homotopically equivalent to a single point. We prove that if the lift of the random walk to the covering tree of G is transient, then the resulting reduced trajectories induce a Markov chain on the set of oriented edges of G. We study this chain in relation with the original random walk. As an intermediate result, we give a simple proof of the Markovian structure of the harmonic measure on trees.* Supported by Nucleus Millennium Information and Randomness ICM P01-005.