It's a nice exercise to show the following decomposition of a simple random walk on an infinite $(d+1)$-regular tree into a nonbacktracking walk with independent excursions. Hopefully I got all the details right below.
Define a random nonbacktracking walk as one that moves to a uniformly chosen neighbor in its first step, and then at subsequent steps moves to a vertex chosen uniformly from its neighbors except for the one it just came from.
For any vertex $v$ with a neighbor $u$, define a $v$-excursion with first step to $u$ as a walk that starts at $v$, moves to $u$, and then at each step after moves with probability $d/(d+1)$ back towards $v$ and with probability $1/d(d+1)$ to each of its $d$ other neighbors, stopping when it returns to $v$.
Let $(X_0,X_1,\ldots)$ be a random nonbacktracking walk starting from $v_0$. Define another walk by $$(Y_i)_{i\geq 0}= (X_0,E_1^0,\ldots,E_{\ell_0}^0,X_1,E_1^1,\ldots,E_{\ell_1}^1,X_2,\ldots), $$ where conditionally on $(X_i)$, the paths $(E_i^j)_{i=1}^{\ell_j}$ are independent and distributed as follows:
- Let $G$ be distributed geometrically with parameter $(d-1)/d$ on $\{0,1,\ldots\}$. Let $(X_0,E^0_1,\ldots,E^0_{\ell_0})$ be the concatenation of $G$ independent $v_0$-excursions with first step chosen uniformly from the neighbors of $v_0$.
- Let $G$ be distributed geometrically with parameter $d/(d+1)$ on $\{0,1,\ldots\}$. For $j\geq 1$, let $(X_j,E^j_1,\ldots,E^j_{\ell_j})$ be the concatenation of $G$ independent $X_j$-excursions with first step chosen uniformly from the neighbors of $X_j$ other than $X_{j-1}$.
Then $(Y_i)_{i\geq 0}$ is a simple random walk starting from $v_0$.
Has this decomposition appeared elsewhere, perhaps in some disguised form?
Update: This is now Proposition A.1 in Infection spread for the frog model on trees. But someone must have done it before!
