= Radial random walk on a regular tree
{title2=$p_{\rm out}=(z-1)/z,\ p_{\rm in}=1/z$}
For a <simple random walk> on an infinite <regular tree> of degree $z\geq2$, every <vertex> other than the chosen root has one neighbour closer to the root and $z-1$ farther away. The <graph distance> from the root is therefore a nearest-neighbour <Markov chain> on the nonnegative integers, with the displayed bulk transition <probabilities> and a certain outward step from zero. For shell <probabilities> $P_r(N)$,
$$
P_0(N+1)=\frac{P_1(N)}z,\qquad
P_1(N+1)=P_0(N)+\frac{P_2(N)}z,
$$
$$
P_r(N+1)=\frac{z-1}{z}P_{r-1}(N)+\frac1zP_{r+1}(N),\qquad r>1.
$$
Shell <probabilities> include all <vertices> at the given distance. They differ from single-vertex <probabilities> by the shell size, $1$ at the root and $z(z-1)^{r-1}$ for $r\geq1$.
Back to article page
