From a Weighted Graph to a Random Walk
A finite connected graph can be viewed in two ways at once. As a random walk, it describes how a particle moves from vertex to vertex. As an electrical network, its edges carry conductances, and voltage differences drive currents. The connection between these viewpoints is quantitative: the expected time to travel from one vertex to another and back is determined by effective resistance.
The factor in this identity depends on the graph's total weight. Keeping track of whether one sums conductances over vertices or edges prevents a common factor-of-two error.
Conductances, Transition Probabilities, and Total Weight
Each edge can be treated as a resistor with resistance \(r_{vw}=1/c_{vw}\). For a function \(f:V\to\mathbb R\), define its weighted graph Laplacian by $$ (Lf)(v)=\sum_{w\in V}c_{vw}\bigl(f(v)-f(w)\bigr). $$ This is the net current flowing out of \(v\) when \(f\) is the voltage at each vertex. Since contributions from the two ends of every edge cancel, \(\sum_{v\in V}(Lf)(v)=0\).
To see why the definition is well posed, the Laplacian is symmetric and satisfies $$ \sum_{v\in V} f(v)(Lf)(v) =\sum_{\{v,w\}\in E}c_{vw}\bigl(f(v)-f(w)\bigr)^2. $$ The right side is zero exactly when \(f\) is constant, because the graph is connected. Thus the kernel of \(L\) consists of constants, and its image is the subspace of vectors whose entries sum to zero. The vector \(\delta_x-\delta_y\) belongs to that subspace. These facts give existence and uniqueness up to a constant.
The Commute-Time Identity
Proof. Let \(h_y(v)=\mathbb E_vT_y\). These expectations are finite: from each vertex there is a path to \(y\), and, because the graph is finite, there is a positive lower bound on the probability of following a path to \(y\) within at most \(|V|-1\) steps. Repeating blocks of that length bounds the tail of \(T_y\) by a geometric tail.
For \(v\ne y\), conditioning on the first step gives \(h_y(v)=1+\sum_w P(v,w)h_y(w)\). Multiplying by \(c(v)\) yields $$ (Lh_y)(v)=c(v),\qquad v\ne y. $$ Because \(\sum_v(Lh_y)(v)=0\), it follows that \((Lh_y)(y)=-\sum_{v\ne y}c(v)\). The same equations hold for \(h_x(v)=\mathbb E_vT_x\), with \(x\) as the target.
Set \(g=h_y-h_x\). At every \(v\notin\{x,y\}\), the two Laplacian values are both \(c(v)\), so \((Lg)(v)=0\). At \(x\), the first-step equation for \(h_y\) gives \((Lh_y)(x)=c(x)\), while summing the Laplacian of \(h_x\) gives \((Lh_x)(x)=-(\operatorname{vol}(G)-c(x))\). Hence \((Lg)(x)=\operatorname{vol}(G)\). Likewise, \((Lg)(y)=-\operatorname{vol}(G)\). Therefore \(g/\operatorname{vol}(G)\) is a unit-current voltage from \(x\) to \(y\), and $$ g(x)-g(y)=\operatorname{vol}(G)R_{\mathrm{eff}}(x,y). $$ Since \(h_x(x)=h_y(y)=0\), the left side is \(h_y(x)+h_x(y)=\mathbb E_xT_y+\mathbb E_yT_x\). This proves the identity.
\(\square\)
If \(x=y\), both hitting times are zero and the resistance between a vertex and itself is taken to be zero, so the identity holds in that case as well.
Worked Example: A Path
Worked Example: A Path
Consider a path with \(n\geq2\) vertices and unit conductance on every edge. The two endpoints are joined by \(n-1\) resistors, each of resistance \(1\), in series. Thus $$ R_{\mathrm{eff}}=n-1. $$ There are \(n-1\) edges of conductance \(1\), so \(\operatorname{vol}(G)=2(n-1)\). The theorem gives $$ \mathbb E_1T_n+\mathbb E_nT_1=2(n-1)^2. $$ Reflection of the path exchanges the endpoints and preserves the transition probabilities, so the two expectations are equal. Each is therefore \((n-1)^2\), and their sum agrees with the commute-time identity.
The same calculation applies to any two vertices at distance \(d\) along this path: their effective resistance is \(d\), while the graph's volume remains \(2(n-1)\). Their commute time is consequently \(2d(n-1)\). Edges outside the segment between the chosen vertices still contribute to the total volume.
Worked Example: A Cycle
Worked Example: A Cycle
Take a cycle with \(n\geq3\) vertices, unit conductance on every edge, and vertices \(x,y\) separated by \(k\) edges in one direction, where \(1\leq k\leq n-1\). Between \(x\) and \(y\) there are two paths in parallel, with resistances \(k\) and \(n-k\). Their equivalent resistance is $$ R_{\mathrm{eff}}(x,y) =\left(\frac{1}{k}+\frac{1}{n-k}\right)^{-1} =\frac{k(n-k)}{n}. $$ The cycle has \(n\) edges of conductance \(1\), so its volume is \(2n\). Therefore $$ \mathbb E_xT_y+\mathbb E_yT_x =2n\cdot\frac{k(n-k)}{n} =2k(n-k). $$ Reflection across the axis exchanging \(x\) and \(y\) preserves the cycle and the walk. The two directed hitting expectations are equal, so each is \(k(n-k)\). For adjacent vertices, \(k=1\), giving commute time \(2(n-1)\); for opposite vertices on an even cycle, \(k=n/2\), giving \(n^2/2\).
Worked Example: A Weighted Star
Worked Example: A Weighted Star
Consider a star with center \(o\) and leaves \(a,b,c\). Let the edge conductances \(c_{oa},c_{ob},c_{oc}\) be \(1,2,3\), respectively. The total edge conductance is \(6\), so \(\operatorname{vol}(G)=12\). The unique path from \(a\) to \(b\) uses resistances \(1\) and \(1/2\), giving $$ R_{\mathrm{eff}}(a,b)=1+\frac12=\frac32. $$ The theorem predicts a commute time of \(12\cdot\frac32=18\).
Check this directly. From a leaf, the walk must first move to \(o\). Let \(H_b(v)=\mathbb E_vT_b\). At the center the transition probabilities to \(a,b,c\) are \(1/6,2/6,3/6\), respectively. Thus \(H_b(a)=1+H_b(o)\), \(H_b(c)=1+H_b(o)\), and $$ H_b(o)=1+\frac16H_b(a)+\frac36H_b(c) =1+\frac46\bigl(1+H_b(o)\bigr). $$ Solving gives \(H_b(o)=5\), hence \(H_b(a)=6\).
For the reverse direction, let \(H_a(v)=\mathbb E_vT_a\). Now \(H_a(b)=H_a(c)=1+H_a(o)\), and $$ H_a(o)=1+\frac26H_a(b)+\frac36H_a(c) =1+\frac56\bigl(1+H_a(o)\bigr). $$ Solving gives \(H_a(o)=11\), hence \(H_a(b)=12\). The sum is \(6+12=18\), as predicted. The leaf \(c\) is not on the path from \(a\) to \(b\), but its edge contributes to the graph's volume and changes the expected commute time.
Why the Total-Weight Factor Matters
The effective resistance describes how difficult it is to send current between two specified vertices. The total vertex weight accounts for the random walk's movement throughout the whole graph. Consequently, adding branches away from the connecting path can change commute times even when the resistance between the chosen pair remains unchanged.
The most common normalization mistake is to use the sum of edge conductances instead of the sum of weighted degrees. These quantities differ by a factor of two: $$ \operatorname{vol}(G)=2\sum_{\{v,w\}\in E}c_{vw}. $$ Thus the identity can be written using either total, but the matching formula must be used. For unit-conductance graphs, it is \(2|E|R_{\mathrm{eff}}(x,y)\), not \(|E|R_{\mathrm{eff}}(x,y)\).
On a tree there is exactly one path between any two vertices, so their effective resistance is the sum of the edge resistances along that path. The commute-time identity then gives $$ \mathbb E_xT_y+\mathbb E_yT_x =2\left(\sum_{e\in E}c_e\right) \left(\sum_{e\text{ on the path from }x\text{ to }y}\frac{1}{c_e}\right). $$ The path determines the resistance, while every edge contributes to the total weight. This separation is often useful when interpreting or checking a calculation.
Check Your Understanding
Use the definitions and identity to answer these questions.
- Why is the total vertex weight twice the sum of edge conductances?
- For a unit-conductance path with \(n\) vertices, what is the commute time between vertices at distance \(d\)?
- Why do the two arcs of a cycle act as parallel routes when calculating effective resistance?
- In the weighted-star example, why does the edge to \(c\) affect the commute time between \(a\) and \(b\)?
- State the Laplacian equations for \(h_y(v)=\mathbb E_vT_y\) at a vertex \(v\ne y\) and at the target \(y\).