# Hitting Times of Walks on Graphs through Voltages

Authors: José Luis Palacios; Eduardo Gómez; Miguel Del Río
Journal: Journal of Probability
 (2014)

---

## Abstract

We derive formulas for the expected hitting times of general random walks on graphs, in terms of voltages, with very elementary electric means. Under this new light we revise bounds and hitting times for birth-and-death Markov chains and for walks on graphs with cutpoints, and give some exact computations on the necklace graph. We also prove Tetali’s formula for hitting times without making use of the reciprocity principle. In fact this principle follows as a corollary of our argument that also yields as corollaries the triangular inequality for effective resistances and the reversibility of the sum of hitting times around a tour.


---

## Body

## 1. Introduction

On a finite connected undirected graphG=(V,E) with |G|=n such that the edge between vertices i and j is given a resistance rij (or equivalently, a conductance Cij=1/rij), we can define the random walk on G as the Markov chain Xn, n≥0, that jumps from its current vertex v to the neighboring vertex w with probability pvw=Cvw/C(v), where C(v)=∑w:w~v‍Cvw and w~v means that w is a neighbor of v. There may be a conductance Czz from a vertex z to itself, giving rise to a transition probability from z to itself, though the most studied case of these random walks on graphs, the simple random walk (SRW), excludes the loops and considers all rij’s to be equal to 1.The hitting timeTb of the vertex b is the number of jumps that the walk takes until it lands on b, and its expected value when the walk starts at a is denoted by EaTb.The beginner’s handbook when studying random walks on graphs from the viewpoint of electric networks is the work of Doyle and Snell [1], which is both a mandatory reference in this area of research and a textbook suitable for undergraduate students. Notably absent from this remarkable monograph is the discussion of hitting times using electric tools. The first such description seems to be due to Chandra et al. [2], where they give the formula for thecommute time of the SRW:
(1)EaTb+EbTa=2|E|Rab,
where |E| is the number of edges of the graph G and Rab is the effective resistance, as computed by means of Ohm’s law, between vertices a and b.The commute timeEaTb+EbTa has a nice compact electric formulation, but the one-sided hitting time is a bit more complicated and it was first given by Tetali [3] through a clever use of the superposition principle and the reciprocity theorem for electric networks, yielding the following formula (here we give the simpler version for SRW):
(2)EaTb=12∑z‍d(z)[Rab+Rbz-Raz],
where d(z) is the number of neighbors of z.In this paper we want to depart from these expressions of expected hitting times in terms of effective resistances and give them instead in terms of voltages, using as tools the material in Doyle and Snell’s book, which relies on basic facts of electricity such as Ohm’s law and Kirchhoff’s law. We present this alternative expression for two reasons: on the one hand, this representation in terms of voltages leads to very simple proofs of many known results, giving also new insights into new results and computations which are simpler than those involving effective resistances; on the other hand, using Tetali’s formula means accepting the deep result of the reciprocity theorem for electric networks, which is outside the realm of Doyle and Snell. With voltages, we will prove Tetali’s result without making use of the reciprocity principle. In fact this principle will follow as a corollary of our argument that also yields as corollaries the triangular inequality for effective resistances and the reversibility of the sum of hitting times around a tour.


## 2. Expected Hitting Times of Walks on Graphs

We begin with some basic facts from Doyle and Snell that we state as a lemma. Consider a general random walk on a finite graph, letPx(Ta<Tb) be the chance that the walk started at x reaches a before reaching b, and let EaNxb be the expected number of times the vertex x is visited by the walk started at a before it reaches b. Then we have the following.Lemma 1.
One has(3)Px(Ta<Tb)=vx,
where vx is the voltage at x when a battery is placed between a and b such that va=1 and vb=0 (one will call this setup of the battery scenario 1). 							(4)EaNxb=C(x)Vx,
where C(x)=∑z~x‍Czx is the sum of all conductances emanating from x and Vx is the voltage at x when a battery is placed between a and b such that the current entering at a is 1 and the voltage at b is 0 (one will call this setup of the battery scenario 2).
One also has the relationship(5)Vx=Rabvx.Proof.
We refer the reader to the book for details, though we can sketch here the main ideas: for (3), we use the fact that both vx and Px(Ta<Tb) are harmonic functions on the graph (i.e., their values at a vertex x are equal to the average of their values over all neighbors of x) with identical boundary values (here the boundary is the pair of vertices a and b) and therefore they must be equal throughout the graph; likewise, to prove (4) we use the fact that both EaNxb/C(x) and Vx are harmonic functions with the same boundary values; and finally to prove (5) one notices that the voltages Vx and vx, both being harmonic functions on the same graph with the same 0 value at b, must be factors of one another, the factor being Rab.Now we can prove our first main result.Theorem 2.
LetG be a connected graph. For any a,b∈G we have
(6)EaTb=∑x∈G‍C(x)Vx,
under scenario 2. Also
(7)EaTb=Rab∑x∈G‍C(x)vx,
under scenario 1.Proof.
For (6) we use (4) to conclude that
(8)EaTb=∑x∈G‍EaNxb=∑x∈G‍C(x)Vx.
Now (7) is immediate from (6) using (5).We remark that the termRab in (7) can be expressed as a voltage; indeed Rab=Va. These expressions of the hitting times in terms of voltages (6) and (7), though immediate as they are from Doyle and Snell’s results, have not been explicitly used in the literature, and we think they lead to new insights and more elementary proofs of most results involving hitting times. Let us begin stressing that, in scenario 2, since the voltage drops from its maximum value Va=Rab to its minimum value Vb=0 through the network G, from (6) we can write
(9)EaTb=∑x≠b‍C(x)Vx≤Rab∑x≠b‍C(x)=Rab(2∑i<j‍Cij-∑i~b‍Cib).
Perhaps the strength of this seemingly innocent inequality can be seen as follows.Corollary 3.
For SRW onG and a,b∈G we have
(10)EaTb≤Rab(2|E|-d(b))≤d(a,b)(2|E|-d(b))≤(n-1)(2|E|-d(b)),
where d(b) is the degree of the vertex b and d(a,b) is the distance in the graph between a and b. In particular, if a~b one has
(11)EaTb≤(2|E|-d(b)).Proof.
We get (10) directly from (9) and we also get the fact that if there is a path of length d(a,b)≤n-1 from a to b, then Rab is bounded by the effective resistance of the path, by the monotonicity law (see [1, page 67]).The bound (11) is presented as a new result in Xu and Yau [4], and it is attained when b is a leaf of any tree and a is its neighbor. The middle bound in (10) can be seen, thus a generalization of that result; also, (10) implies immediately that for any a,b∈GEaTb=O(n3) and that if d(x)≤k for all x then EaTb=O(kn2). In case G is k-regular, that is, d(x)=k for all x, then (10) yields
(12)EaTb≤d(a,b)k(n-1).
It is well known (e.g., see [5]) that d(a,b)≤3n/k, and this inequality inserted into (12) shows that hitting times in regular graphs are at most quadratic.The next result, found in Xu and Yau [4], also has a simple electric proof.Corollary 4.
Ifd(b)=n-1 then for any a∈G one has EaTb≤max⁡x≠bd(x).Proof.
The unit current that exits atb comes from its n-1 neighbors; therefore 1=∑x≠b(Vx-Vb)=∑x≠b‍Vx. From (6) we have then
(13)EaTb=∑x≠b‍d(x)Vx≤max⁡x≠bd(x)∑x≠b‍Vx=max⁡x≠bd(x).Notice that in the previous corollary we haved(x,b)=1 for all x≠b. Its proof inspires the following generalization: let D=max⁡x∈G{d(x,b)} and let Sj={x∈G:d(x,b)=j}, 1≤j≤D, with a∈SD.Corollary 5.
For SRW, if the sizes of the setsSj, 1≤j≤D, form a nonincreasing sequence, then
(14)EaTb≤max⁡x≠bd(x)(D+12).Proof.
As in the proof of the previous corollary,(15)∑x:d(x,b)=1‍Vx=1.
Now, for x∈G with d(x,b)=2, let y=f(x) be such that x~y and d(y,b)=1, for some one-to-one function f (this is possible to do on account of the sizes of the Sjs). The current entering the set of vertices {y=f(x):d(x,b)=2}, which is bounded by the total unit current, can be expressed as
(16)∑x:d(x,b)=2‍(Vx-Vy)≤1,
and therefore
(17)∑x:d(x,b)=2‍Vx≤∑x:d(x,b)=2‍Vy+1≤∑y:d(y,b)=1‍Vy+1≤2.
It is plain to see by induction that for D≥j≥2 we have
(18)∑x:d(x,b)=j‍Vx≤j,
and so
(19)EaTb=∑x≠b‍d(x)Vx≤max⁡x≠bd(x)(1+2+⋯+D).The bound (14) is attained on the 2k+1-cycle, when we pick a and b so that d(a,b)=k. Then EaTb=k(k+1).For our next application, let us consider now the (possibly infinite) linear graph on the integers with conductancesCj-1,j for -∞≤j≤∞. We can prove the following corollary.Corollary 6.
In the linear graph one has(20)Ej-1Tj=1Cj-1,j∑i≤j-1‍C(i).Proof.
We use (6) and notice that all vertices to the left of j-1 share the same voltage Vj-1=Rj-1,j=1/Cj-1,j, whereas all the vertices to the right of j share the same voltage Vj=0.The corollary just proved dispatches all hitting times of birth-and-death Markov chains, as discussed in Palacios and Tetali [6], where the lengthier proof uses Tetali’s formula. The following is an interesting application of this corollary to a family of trees that generalizes n-ary trees.Corollary 7.
LetT be a tree such that every node at distance i from the root has exactly di descendants, for 0≤i≤N-1, so that there are ∏i=0N-1‍di leaves at distance N from the root. Then the expected time for the simple random walk started at the root to reach the leaves is
(21)1+∑j=1N-1‍2C0+2C1+⋯+2Cj-1+CjCj≤N2,
where Cj=d0d1⋯dj, for 0≤j≤N-1.Proof.
By symmetry, all vertices at the same distance from the origin share the same voltage and thus can be shorted. We get thus a (finite) linear graph whoseith vertex is the shorting of all vertices of the tree at distance i from the root. In that linear graph Cj=d0⋯dj, and we apply (20). The inequality is immediate because the Cjs are increasing.The boundN2 above is a particular case of the general bound (1/4)D2, shown by Pearce [7], for the hitting time of the leaves of a tree with diameter D.Now we look at SRW on graphs with cutpoints. We say thatc is a cutpoint of G if deleting c and its incident edges renders the resulting subgraph a disconnected graph. Take a,b∈G and let Gb=(Vb,Eb) and Gc=(Vc,Ec) be the subgraphs of G thus obtained: split the vertex c in two, obtaining two separate connected graphs Gb and Gc, where the former contains a and b. Then we have the following corollary.Corollary 8.
With the notation of the preceding paragraph one has(22)EaTb=2Rab|Ec|vc+EaTbGb,
where TbGb is the hitting time of the random walk restricted to the subgraph Gb.
In particular, ifa is the cutpoint then
(23)EaTb=2Rab|Ea|+EaTbGb.Proof.
All vertices inGc share the same voltage vc because there is no circulation of current in Gc when we place a battery between a and b. Therefore
(24)EaTb=Rab∑x∈G‍d(x)vx=Rab∑x∈Gc‍d(x)vx+Rab∑x∈Gb‍d(x)vx=Rab∑x∈Gc‍d(x)vc+Rab∑x∈Gb‍d(x)vx=2Rab|Ec|vc+Rab∑x∈Gb‍d(x)vx.
The second summand of (24) is clearly EaTbGb.Notice that (22) and (23) reduce the computation of EaTb in the original graph G to that of EaTbGb in the subgraph Gb. A useful particular case of the preceding corollary applies to the case of a cut-edge, whose removal renders the graph disconnected. Then we have the following corollary.Corollary 9.
Suppose that(a,b)∈E is a cut edge of G and that Ga=(Va,Ea) is the connected subgraph of G-(a,b) that contains a. Then one has
(25)EaTb=2|Ea|+1.Proof.
Use (23) with a the cutpoint, and notice that in this case Rab=1 and EaTbGb=1.Now we can give a compact expression for the expected hitting times on trees, with a compact proof perhaps simpler than the ones given by Haiyan and Fuji [8] and Palacios [9].Corollary 10.
LetG be a tree. For any a,b∈G, and P the unique path between a and b, one has
(26)EaTb=d(a·b)+2∑x∈P‍|Ex|,
where d(a,b) is the distance from a to b.Proof.
In a tree every edge is a cut edge, so we apply (25) and the fact that if P={a=x1,x2,…,xm=b} then EaTb=∑i=1m-1‍ExiTxi+1.


## 3. An Example of Exact Calculations

We consider now the necklace graph, an example of a 3-regular graph with dimension 1 which is useful for providing extreme parameters of random walks on graphs (see [5]). All the “beads” of the necklace are identical except for the two extreme beads, as seen in Figure 1. We will compute E1T8 assuming there are n beads to the left of the bead containing 1 and m beads to the right of the bead containing 8, and n≥m≥1.Figure 1
Necklace graph.For that purpose we place a battery between vertices 1 and 8 so thatv1=1 and v8=0; that is, we work under scenario 2. It is rather simple to find R18=9/4 and the other voltages:
(27)v2=1718,v3=1618,v4=1318,v5=518,v6=218,v7=118.It is worth remarking that, in this graph, as in other symmetric graphs, there is a kind of Noetherian principle, whereby symmetry implies conservation, namely, conservation of the sum of voltages at symmetric vertices:(28)v1+v8=v2+v7=v3+v6=v4+v5=1.
An application of (7), bearing in mind the conservation principle just mentioned, yields a simple computation:
(29)E1T8=274∑x∈G‍vx=27[m+54+1718(n-m)].It is not entirely clear how the computation ofE1T8 with formula (2) could have given such a closed form.


## 4. Tetali’s Formula

In this section we prove Tetali’s result (2) using only the superposition principle for electric networks (stating that the voltage of a node due to the presence of several batteries equals the sum of all voltages due to each individual battery) and the voltage expression of hitting times (6).We will show that the reciprocity principle, used in Tetali’s original proof, in fact follows as a corollary of the superposition principle, and we will obtain also as corollaries the triangular inequality for effective resistances and the reversibility of the sum of hitting times around a tour, in a formula that generalizes (1). All these results are known, but their proofs are more involved than the ones given here in the following theorem.Theorem 11.
For anya,b,c∈G,
(30)EaTb+EbTc+EcTa=EaTc+EcTb+EbTa=12(Rab+Rbc+Rca)∑x‍C(x),(31)Rab+Rbc≥Rac.
Also
(32)EaTb=12∑x∈G‍C(x)(Rab+Rbx-Rax).Proof.
Install three batteries: one betweena and b so that a unit current enters a and exits through b, and the voltages generated are V1(x), for x∈G, with V1(b)=0. Then another between b and c so that a unit current enters b and exits at c, and the voltages generated are V2(x), for x∈G, with V2(c)=0. Also another between c and a so that a unit current enters c and exits at a, and the voltages generated are V3(x), for x∈G, with V3(a)=0.
Since there is no net flow of current through the network, the voltage at every node due to the superposition of the three batteries is the same:V1(x)+V2(x)+V3(x)=K, and therefore, using (6) we have
(33)EaTb+EbTc+EcTa=∑x∈G‍C(x)(V1(x)+V2(x)+V3(x))=K∑x∈G‍C(x).
Now if we reverse the polarity of the three batteries and call the respective voltages thus generated V1′(x), V2′(x), V3′(x), then we have
(34)EaTc+EcTb+EbTa=∑x∈G‍C(x)(V1′(x)+V2′(x)+V3′(x))=K′∑x∈G‍C(x).
But K=K′ because as a circuit, G is receiving the same input from the original batteries and the reversed ones: three unit currents entering at a, b and c and three unit currents exiting at the same sites. So the first equality in (30) is proven, and we only need to identify the value of the constant K.
It is clear that(35)K=V1(c)+V2(c)+V3(c)=V1(c)+Rac.
Also, if we look at the batteries with their polarities reversed we have
(36)K=V1′(c)+V2′(c)+V3′(c)=V1′(c)+Rbc.
Now from (35) and (36) we get
(37)V1(c)+Rac=V1′(c)+Rbc.
But if we look at battery 1 with both the original and the reverse polarities we have that
(38)V1(c)+V1′(c)=Rab.
Now (37) and (38) imply that
(39)V1(c)=12(Rab+Rbc-Rca).
Inserting (39) into (35) finishes the proof of (30).
Since the voltage is a nonnegative quantity, (39) proves (31). Also, using the voltage form of the hitting time (6) and letting c run in (39) over all values x∈G proves (32).It is plain to see that in the proof of the above theorem we have only used the superposition principle for electric networks. With the arguments in our proof we can in fact prove the reciprocity principle that was used in Tetali’s original proof of his result (32).Corollary 12.
For anya,b,c∈G, if one sets a battery between a and b so that a unit current enters a and exits at b and the voltage at b is 0, then the value of the voltage at c is the same as the value of the voltage at a when one disconnects the battery cable at a and reconnects it at c.Proof.
Translating the words into formulas, we want to show that(40)V1(c)=V2′(a),
but this is clear because both these voltages are equal to
(41)12(Rab+Rbc-Rca),
as can be seen from (39) and the facts that
(42)V2′(a)=Rbc-V2(a),V2(a)=12(Rbc+Rca-Rab),
which is again (39) with the roles of batteries 1 and 2 exchanged.Remarks. The argument in the proof of Theorem 11, beside being a most compact way to prove Tetali’s formula, yields itself to an obvious generalization of (30) when we choose not just a triangle, but a tour of vertices a1,a2,…,an=a1 in the graph. The quantity in the right hand side of (39) is identified by Tetali [10] as the (a,c) entry of a matrix that is the inverse of a matrix of conductances, but it is not identified as a voltage due to the superposition of three batteries, as we do here. Perhaps the connection merits a second look.



---

*Source: 852481-2014-05-20.xml*