Lemma: /u∈V,pu,u=Tu,v d(u) d(x) Dw.v uw∈E d(v) d(y) 2m Tww =E[mino=u w=应1-eo wu∈E 1 =1+ d(u) ∑ Tw,v wu∈ELecture 23: November 17 23-3 Figure 23.1: Graph as an electrical network Definition 23.5 The e↵ective resistance R(u, v) between two nodes u and v is the potential di↵erence between u and v that is required to send one unit of current from u to v. Now we prove a few useful lemmas about hitting times. Consider first Scenario A, in which we inject d(x) units of current into each node x, and remove all 2m = P x d(x) units of current from node v, where d(x) denotes the degree of x. (See Figure 23.2.) Lemma 23.6 The potential di↵erence u,v between v and any other node u in Scenario A satisfies u,v = Hu,v. Figure 23.2: Scenario A Proof: Consider any vertex u 2 V . Using Kircho↵’s Laws and Ohm’s Law, we have d(u) = X (u,x)2E (current u ! x) (K1) = X (u,x)2E u,x (Ohm) = X (u,x)2E (u,v x,v) (K2) = d(u)u,v X (u,x)2E x,v. Rearranging thus gives u,v =1+ 1 d(u) X (u,x)2E x,v. (23.1) On the other hand, consider the random walk starting from u. Thinking of just the first step of this walk, we see that the hitting time Hu,v satisfies Hu,v =1+ 1 d(u) X (u,x)2E Hx,v. But this is exactly the same system of linear equations as (23.1), satisfied by u,v. Since we know that this system has a unique solution (the potentials are uniquely determined by the current flows), we deduce that Hu,v = u,v 8u, v 2 V. Lemma: 8u 2 V, u,v = ⌧u,v u,v = E ⌅ min n > 0 ⇤ ⇤ Xn = v ⇥ ⇤ ⇤ ⇤ X0 = u ⇧ ⌧u,v = X wu2E 1 d(u) (1 + ⌧w,v) =1+ 1 d(u) X wu2E ⌧w,v u,v =1+ 1 d(u) X uw2E w,v