Hitting Probabilities and Green Functions on Regular Trees

Branching Changes the Walk

A simple random walk on a line can repeatedly revisit the same sites. On a tree with enough branching, the number of routes leading away from a starting point grows with distance. This creates an outward bias in the distance from the root, even though every individual step is chosen uniformly among the neighboring vertices.

That bias can be quantified exactly. It determines the probability of returning to the root, the probability of ever reaching a specified vertex, and the expected number of visits recorded by the Green function. We will also distinguish reaching a vertex from the different question of which direction the walk takes at infinity.

The Regular Tree and Its Boundary

Let $T_d$ be an infinite connected tree in which every vertex has exactly $d$ neighbors, where $d\ge 3$. Write $o$ for a fixed root and $X_n$ for simple random walk: from its current vertex, the walk chooses each of the $d$ neighbors with probability $1/d$. Let $\operatorname{dist}(x,y)$ denote the number of edges on the unique path between vertices $x$ and $y$.

Viewed from $o$, each vertex other than $o$ has one neighbor closer to the root and $d-1$ neighbors farther away. Set $q=d-1$. Thus, at any positive distance from $o$, the distance increases with probability $q/d$ and decreases with probability $1/d$. The root itself has $d$ outward neighbors.

Definition: A boundary ray from $o$ is an infinite path starting at $o$ that never traverses an edge twice. The boundary $\partial T_d$ is the set of these rays. For a vertex $v$ at distance $n\ge1$ from $o$, the cylinder $C(v)$ is the set of boundary rays that pass through $v$.

There are $d q^{n-1}$ vertices at distance $n$. The cylinder $C(v)$ records a direction at infinity, not the event that the walk ever visits $v$. These two probabilities will differ: the walk can visit a vertex and later leave its branch, while its eventual boundary ray records the branch it follows in the long run.

Hitting the Root from a Given Distance

For $k\ge0$, let $h_k$ be the probability that a walk started at distance $k$ from $o$ ever hits $o$. We calculate this probability by first restricting the walk to the interval of distances from $0$ to $N$. For $1\le k<N$, let $h_k^{(N)}$ be the probability of hitting distance $0$ before distance $N$. The boundary values are $h_0^{(N)}=1$ and $h_N^{(N)}=0$, and the one-step recurrence is

h_k^{(N)} = \frac{q}{d}h_{k+1}^{(N)} + \frac{1}{d}h_{k-1}^{(N)}.

Multiplying by $d$ and using $q=d-1$, the characteristic equation for solutions of the form $r^k$ is $q r^2-dr+1=0$. Its roots are $1$ and $1/q$, so the solutions have the form $A+Bq^{-k}$. Applying the two boundary values gives

h_k^{(N)} = \frac{q^{-k}-q^{-N}}{1-q^{-N}}.

As $N$ increases, the events “hit $0$ before $N$” increase to the event “ever hit $0$.” Indeed, any path that hits $0$ does so in finitely many steps and has a finite maximum distance before that hit. Taking $N$ to infinity therefore yields the hitting probability.

Theorem: For simple random walk on $T_d$, $d\ge3$, the probability of ever hitting the root from distance $k$ is $$ \mathbb{P}_x(T_o<\infty)=q^{-k}, \qquad k=\operatorname{dist}(x,o), $$ where $T_o=\inf\{n\ge0:X_n=o\}$.

Proof. If $k=0$, the walk is already at the root and the probability is $1=q^0$. For $k\ge1$, the finite-interval calculation above gives the probability of hitting $0$ before $N$. These events increase to eventual hitting of $0$, so continuity of probability for increasing events gives

\mathbb{P}_x(T_o<\infty) = \lim_{N\to\infty} \frac{q^{-k}-q^{-N}}{1-q^{-N}} = q^{-k}. \qquad\square

In particular, after a step away from the root, the walk is at distance $1$. The probability that it ever returns is $1/q$. This is less than one precisely because $d\ge3$.

Hitting a Specified Vertex

The same calculation applies with any fixed vertex $y$ as the root: the tree looks the same when viewed from $y$. If the walk starts at $x$, its probability of ever hitting $y$ therefore depends only on the distance between them.

Theorem: For $x,y\in T_d$, $$ \mathbb{P}_x(T_y<\infty) = q^{-\operatorname{dist}(x,y)}. $$

Proof. Regard $y$ as the root. A vertex at distance $k=\operatorname{dist}(x,y)$ has the same outward and inward distance transition probabilities used above. The root-hitting result gives probability $q^{-k}$, including $k=0$, when the walk starts at $y$. This proves the formula for all $x,y$.

Worked Example: Hitting a Vertex on a 4-Regular Tree

Here $d=4$, so $q=3$. If $y$ is three edges from the starting point $x$, then

\mathbb{P}_x(T_y<\infty) = 3^{-\operatorname{dist}(x,y)} = 3^{-3} = \frac{1}{27}.

This is the probability of ever reaching that particular vertex, not the probability of reaching any vertex three edges away. The latter event has probability $1$: every step changes distance by one, so the walk must reach distance three on its way away from the root unless it returns first; even after returns, it eventually reaches that level almost surely by the outward drift.

The Green Function

The Green function counts visits, including the visit at time zero when the walk starts at the vertex being counted. Write

G(x,y) = \sum_{n=0}^{\infty}\mathbb{P}_x(X_n=y) = \mathbb{E}_x\!\left[\sum_{n=0}^{\infty}\mathbf{1}_{\{X_n=y\}}\right].

To compute it, first consider $G(y,y)$. Each time the walk visits $y$, it has probability $1/q$ of returning to $y$ after leaving. The number of visits, counting the initial one, therefore has a geometric distribution on $\{1,2,\ldots\}$ with success probability $1-1/q$, where “success” means no further return. Its expectation is $1/(1-1/q)$.

Theorem: On $T_d$, for $d\ge3$, $$ G(x,y) = \frac{q}{q-1}\,q^{-\operatorname{dist}(x,y)} = \frac{d-1}{d-2}\,(d-1)^{-\operatorname{dist}(x,y)}. $$ In particular, $G(y,y)=(d-1)/(d-2)$.

Proof. Starting from $y$, the probability of ever returning after leaving is $1/q$, by the root-hitting calculation at distance one. Thus successive returns give a geometric number of visits, with expectation

G(y,y) = 1+\frac1q+\frac1{q^2}+\cdots = \frac{1}{1-1/q} = \frac{q}{q-1}.

Now start from $x$. If the walk never hits $y$, it makes no visits to $y$. If it does hit $y$, the expected number of visits from that first hit onward, including that hit, is $G(y,y)$, by the Markov property at the first hitting time. Hence

G(x,y) = \mathbb{P}_x(T_y<\infty)G(y,y) = q^{-\operatorname{dist}(x,y)}\frac{q}{q-1}. \qquad\square

Worked Example: The Green Function on a 3-Regular Tree

For $d=3$, $q=2$, and the expected number of visits to the starting vertex is

G(o,o)=\frac{2}{2-1}=2.

If $y$ is four edges from $o$, then the probability of ever reaching $y$ is $2^{-4}=1/16$. Once the walk first reaches $y$, its expected total number of visits to $y$, including that first visit, is $2$. Consequently,

G(o,y) = \frac{1}{16}\cdot 2 = \frac18.

The value is smaller than $G(o,o)$ because the walk must first reach $y$, an event of probability $1/16$.

Hitting the Boundary at Infinity

The walk does not merely have a positive chance to escape far from the root. It almost surely determines a boundary ray. To see why, the return probability to any vertex after leaving it is $1/q<1$, so the expected number of visits to that vertex is $q/(q-1)<\infty$. A vertex is therefore visited only finitely often almost surely. Since the tree has countably many vertices, with probability one every vertex is visited only finitely often. For each finite ball around $o$, the walk eventually leaves that ball for the last time. After that last exit, it stays in a single component outside the ball: moving between different such components would require revisiting the ball. These consistent choices of components determine one boundary ray.

The law of the walk started at $o$ is unchanged by any tree symmetry that fixes $o$. Such symmetries act transitively on the vertices at each level, and therefore give equal probability to all cylinders at that level. The level-$n$ cylinders form a partition of the boundary, and there are $d q^{n-1}$ of them. Their probabilities must sum to one.

Theorem: For any vertex $v$ at distance $n\ge1$ from $o$, the probability that the walk’s limiting boundary ray belongs to $C(v)$ is $$ \mathbb{P}_o(\text{limiting ray belongs to }C(v)) = \frac{1}{d q^{n-1}}. $$

Worked Example: A Boundary Cylinder on a 4-Regular Tree

For $d=4$, we have $q=3$. A vertex $v$ at distance $3$ determines a boundary cylinder containing all rays that pass through $v$. There are $4\cdot3^2=36$ such cylinders at that level, and symmetry gives

\mathbb{P}_o(\text{limiting ray belongs to }C(v)) = \frac{1}{4\cdot3^2} = \frac{1}{36}.

By contrast, the probability of ever hitting that particular vertex is $3^{-3}=1/27$. The two events are not the same: a path may reach $v$ and subsequently leave its branch before settling on its limiting ray.

How the Degree Controls the Answer

The parameter $q=d-1$ records the number of outward choices available at each step away from the root. Increasing $d$ lowers the chance of returning from a neighbor, lowers the chance of hitting a specified distant vertex, and lowers the off-diagonal Green function at a fixed positive distance. The expected number of visits to the starting vertex is $q/(q-1)$, which also decreases as the degree increases.

The condition $d\ge3$ matters. At degree $2$, the infinite regular tree is the integer line, where simple random walk is recurrent: it returns to its starting point with probability one, and the Green function on the diagonal is infinite. Substituting $q=1$ into formulas derived for $q>1$ is invalid; the geometric series for $G(y,y)$ no longer converges.

A useful distinction is between three quantities: the probability of returning to a vertex, the probability of ever hitting a specified vertex, and the probability of ending in a boundary cylinder. The first two are governed by the factor $q^{-k}$ at distance $k$; the last is determined by the number of cylinders at that level. Keeping these events separate prevents a common error: treating “ever visits this vertex” as equivalent to “eventually follows this branch.”

Check Your Understanding

Use the formulas and arguments above to answer these questions.

On a $5$-regular tree, what is the probability that a walk started at distance $2$ ever hits the root?
Why does the probability of ever hitting a specified vertex depend only on its distance from the starting point?
Compute $G(x,y)$ on a $4$-regular tree when $\operatorname{dist}(x,y)=2$.
On a $3$-regular tree, compare the probability of hitting a specified vertex at level $2$ with the probability of limiting to its boundary cylinder.
Why can the finite Green-function formula not be extended to degree $2$ by direct substitution?