For random walk on a finite tree, we can develop explicit formulas for means and variances of first passage times, and for distributions of first hitting places. We shall only treat the unweighted case, but the formulas can be extended to the weighted case without difficulty.
xxx notation below —change to ? Used haphazardly for vertices.
In this section we’ll write for the degree of a vertex , and for the distance between and . On a tree we may unambiguously write for the path from to . Given vertices in a tree, the intersection of the paths is a (maybe trivial) path; write for the length of this intersection path.
On an -vertex tree, the random walk’s stationary distribution is
Recall from the beginning of this chapter that an edge of a graph is essential if its removal would disconnect the graph into two components and , say, containing and respectively. Obviously, in a tree every edge is essential, so we get a lot of mileage out of the essential edge lemma (Lemma 5.1).
Consider discrete-time random walk on an -vertex tree.
For each edge ,
(5.81) |
(5.82) |
For arbitrary ,
(5.83) |
(5.84) |
For each edge ,
(5.85) |
For arbitrary ,
(5.86) |
Remarks. 1. There are several equivalent expressions for the sums above: we chose the most symmetric-looking ones. We’ve written sums over vertices, but one could rephrase in terms of sums over edges.
2. In continuous time, the terms “” disappear from the variance formulas—see xxx.
Proof of Theorem 5.20. Equations (5.81) and (5.82) are rephrasings of (5.3) and (5.4) from the essential edge lemma. Equation (5.84) and the first equality in (5.83) follow from (5.82) and (5.81) by summing over the edges in the path . Note alternatively that (5.84) can be regarded as a consequence of the commute interpretation of resistance, since the effective resistance between and is . To get the second equality in (5.83),consider the following deterministic identity (whose proof is obvious), relating sums over vertices to sums over edges.
Let be a function on the vertices of a tree, and let be a distinguished vertex. Then
where is the first vertex (other than ) in the path .
We prove (5.85) below. To derive (5.86) from it, sum over the edges in the path to obtain
(5.87) |
where denotes the sum over all for which contains both and . Given vertices and , there exist unique smallest values of and so that and . If , then the sum in (5.87) equals
as required by (5.86). If , then the sum in (5.87) equals
which again equals by a similar calculation.
So it remains to prove (5.85), for which we may suppose, as in the proof of Lemma 5.1, that is a leaf. By considering the first step from to we have
Now yyy of Chapter 2 gives a general expression for in terms of , and in the present setting this becomes
Using the second equality in (5.83), we may rewrite the sum as
Also,
Combining these expressions gives
But by (5.81), .
Here we discuss the five parameters of Chapter 4. Obviously by (5.84)
(5.88) |
where is the diameter of the tree. As for , it is clear that the sup in its definition is attained by for some edge . Note that
(5.89) |
This leads to
(5.90) | |||||
Obviously the max is attained by an edge for which is as close as possible to . This is one of several notions of “centrality” of vertices and edges which arise in our discussion—see Buckley and Harary [81] for a treatment of centrality in the general graph context, and for the standard graph-theoretic terminology.
On an -vertex tree,
where denotes the sum over all undirected edges .
Proof. Using the formula for the stationary distribution, for each
Appealing to Lemma 5.21 (with as the distinguished vertex)
where and , where is the first edge of the path . Taking the (unweighted) average over ,
Each term is the sum of terms along the edges of the path . Counting how many times a directed edge appears,
where we sum over directed edges . Changing to a sum over undirected edges, using and , gives
This simplifies to the assertion of the Proposition.
For we content ourselves with a result “up to equivalence”.
There exist constants such that
Of course the expectations can be computed by (5.83).
Proof. We work with the parameter
which we know is equivalent to . Write
Fix an attaining the minimum. For arbitrary we have (the first equality uses the random target lemma, cf. the proof of Chapter 4 Lemma yyy)
and so .
For the converse, it is elementary that we can find a vertex such that the size (, say) of the largest branch from satisfies . (This is another notion of “centrality”. To be precise, we are excluding itself from the branch.) Fix this , and consider the which maximizes , so that by definition. Let denote the set of vertices in the branch from which contains . Then
and so
But by (5.89) , so we have shown .
We do not know whether has a simple expression “up to equivalence” analogous to Proposition 5.23. It is natural to apply the “distinguished paths” bound (Chapter 4 yyy). This gives the inequality
where has the stationary distribution and where we got the equality by writing . The edge attaining the max gives yet another notion of “centrality.”
xxx further remarks on .
It is natural to think of the -path (Example 5.8) and the -star (Example 5.10) as being “extremal” amongst all -vertex trees. The proposition below confirms that the values of , , , , and in those examples are the exact extremal values (minimal for the star, maximal for the path).
For any -vertex tree with ,
(a)
(b)
(c) .
(d) .
(e) .
Proof. (a) is obvious from (5.88), because varies between for the -star and for the -path. The lower bound in (b) follows from the lower bound in (a). For the upper bound in (b), consider some path in the tree, where plainly . Now and so
because the left side decreases by at least as increases. So
To prove (c), it is enough to show that the sum in Proposition 5.22 is minimized by the -star and maximized by the -path. For each undirected edge , let
Let be the non-decreasing rearrangement of these values . The summands in Proposition 5.22 are of the form
with ranging over the .
One can check that this quantity is an increasing function of . Thus it is enough to show that the vector b on an arbitrary -tree dominates coordinatewise the vector b for the -star and is dominated by the vector b for the -path. The former is obvious, since on the -star . The latter needs a little work. On the -path . So we must prove that in any -tree
(5.91) |
Consider a rooted tree on vertices. Breaking an edge gives two components; let be the size of the component not containing the root. Let be the non-decreasing rearrangement of . For an -path rooted at one leaf, . We assert this is extremal, in that for any rooted tree
(5.92) |
This fact can be proved by an obvious induction on , growing trees by adding leaves.
Now consider an unrooted tree, and let b be as above. There exists some vertex , of degree , such that each of the branches from has size (excluding ) at most . Consider these branches as trees rooted at , apply (5.92), and it is easy to deduce (5.91).
For (d), the lower bound is easy. Fix a leaf and let be its neighbor. We want to apply the extremal characterization (Chapter 3 yyy) of to the function
For this function, ,
and by considering transitions out of
Since we have and hence .
qqq Anyone have a short proof of upper bound in (d)?
Finally, (e) is clear from (5.90).
Other extremal questions. Several other extremal questions have been studied. Results on cover time are given in Chapter 6. Yaron [340] shows that for leaves the mean hitting time is maximal on the -path and minimal on the -star. (He actually studies the variance of return times, but Chapter 2 yyy permits the rephrasing.) Finally, if we are interested in the mean hitting time or the hitting place distribution, we can reduce to the case where is the set of leaves, and then set up recursively-solvable equations for or for for fixed . An elementary treatment of such ideas is in Pearce [277], who essentially proved that (on -vertex trees) is minimized by the -star and maximized by the -path.