Random Walk on Graph undirected graph G(V,E) ●walk:v1,v2,.∈V that vi+1~vi random walk:vt1 is uniformly chosen from N(vi) u n v ud v adjacency matrix A P-DA d(u) pu,)=0 u=U u卡U
Random Walk on Graph • undirected graph G(V, E) • walk: • random walk: v1, v2,... ⇥ V that vi+1 vi P = D1A adjacency matrix A D(u, v) = d(u) u = v 0 u = v P(u, v) = 1 d(u) u v 0 u ⇥ v vi+1 is uniformly chosen from N(vi)
Hitting and Covering consider a random walk on GV,E) hitting time:expected time to reach v from u Tw=min {n=Xo=u cover time:expected time to visit all vertices Cu=E minn.v Xo=u C(G)=max Cu u∈V
Hitting and Covering • hitting time: expected time to reach v from u • cover time: expected time to visit all vertices u,v = E ⌅ min n > 0 ⇤ ⇤ Xn = v ⇥ ⇤ ⇤ ⇤ X0 = u ⇧ Cu = E ⌅ min n ⇤ ⇤ {X0,...,Xn} = V ⇥ ⇤ ⇤ ⇤ X0 = u ⇧ C(G) = max uV Cu consider a random walk on G(V,E)
G-Kn C(G)=Θ(n log n) G:path or cycle C'(G)=Θ(n2)〉 G:1 lollipop” K号 0 02 C(G)=Θ(n3)
C(G) = (n log n) G = Kn C(G) = (n2) C(G) = (n3) G : path or cycle G : “lollipop” K n 2 n 2
Electric Network edge uv:resistance Ruv vertex v:potential edge orientation u→w: current flow Cu-→v potential difference Pu,v Pu-pv Kirchhoff's Law:V vertex v,flow-in flow-out Ohm's Law:V edge uv,Cu= ①u, Ruv
23-2 Lecture 23: November 17 Notes 1. The above two algorithms demonstrate a time-space tradeo↵, in that the product of space and time remains constant. In fact, it turns out that there is a whole spectrum of randomized algorithms spanning this tradeo↵ [F97]: 8s 9 algorithm using space s and time O˜(|V ||E| s ) that visits all (reachable) vertices w.h.p. (The notation O˜ hides logarithmic as well as constant factors.) 2. In an important breakthrough, Reingold [R05] showed that the above random walk algorithm could be derandomized, thus obtaining a deterministic O(1) space algorithm for graph searching (phrased more precisely as testing whether there is a path between a given pair of vertices u, v. More correctly this is a O(log n) space algorithm, since O(log n) space is needed to record the label of a vertex in an n-vertex graph, and to keep track of the number of steps taken so far.) Since the connectivity problem is a canonical problem solvable in randomized log-space, this seems like a major step towards proving that every randomized log-space algorithm can be derandomized with only a constant factor penalty in space. However, this question remains open (see, e.g., [RTV06] for some interesting approaches). We should also observe that the analogous question for directed graphs is much more challenging, since testing connectivity in this case is a complete problem for non-deterministic log-space. Thus a deterministic (or even randomized) log-space algorithm for it would show that even non-determinism buys us nothing in the world of log-space algorithms. One problem here is that the naive random walk approach breaks down because the cover time on directed graphs can be exponentially large. The bound on the cover time comes from the following theorem, originally due to Aleliunas et al. [AKLLR79]. Theorem 23.4 For any connected graph G, C(G) 2|E||V |. We will follow a di↵erent route due to Chandra et al. [CRRST89], which is based on an intriguing connection between random walks and electrical networks. Along the way, we will also obtain bounds on hitting times. 23.2 Hitting time and commute time To prove theorem 23.4, we start by proving some properties of the hitting time for a vertex. To do this, we will view the graph as an electrical network, where each edge has unit resistance. (For a detailed treatment of the relationship between random walks and electrical networks, see the classic book by Doyle and Snell [DS84].) When a potential di↵erence is applied between nodes of this network from an external source, current flows in the network in accordance with Kircho↵’s Laws and Ohm’s Laws: • K1: The total current into and out of a vertex is equal to zero. • K2: The sum of potential di↵erences around any cycle is zero. • Ohm’s Law: The current flowing along any edge is equal to pot. di↵erence resistance . Electric Network edge uv : resistance Ruv vertex v : potential v edge orientation u ! v: current flow Cu!v Kirchhoff’s Law: ∀ vertex v, flow-in = flow-out Ohm’s Law: ∀ edge uv, Cu!v = u,v Ruv potential difference u,v = u v
Effective Resistance electrical network: MM effective resistance R(u,v): potential difference between u and v required to send 1 unit of flow current from u to v
Effective Resistance 23-2 Lecture 23: November 17 Notes 1. The above two algorithms demonstrate a time-space tradeo↵, in that the product of space and time remains constant. In fact, it turns out that there is a whole spectrum of randomized algorithms spanning this tradeo↵ [F97]: 8s 9 algorithm using space s and time O˜(|V ||E| s ) that visits all (reachable) vertices w.h.p. (The notation O˜ hides logarithmic as well as constant factors.) 2. In an important breakthrough, Reingold [R05] showed that the above random walk algorithm could be derandomized, thus obtaining a deterministic O(1) space algorithm for graph searching (phrased more precisely as testing whether there is a path between a given pair of vertices u, v. More correctly this is a O(log n) space algorithm, since O(log n) space is needed to record the label of a vertex in an n-vertex graph, and to keep track of the number of steps taken so far.) Since the connectivity problem is a canonical problem solvable in randomized log-space, this seems like a major step towards proving that every randomized log-space algorithm can be derandomized with only a constant factor penalty in space. However, this question remains open (see, e.g., [RTV06] for some interesting approaches). We should also observe that the analogous question for directed graphs is much more challenging, since testing connectivity in this case is a complete problem for non-deterministic log-space. Thus a deterministic (or even randomized) log-space algorithm for it would show that even non-determinism buys us nothing in the world of log-space algorithms. One problem here is that the naive random walk approach breaks down because the cover time on directed graphs can be exponentially large. The bound on the cover time comes from the following theorem, originally due to Aleliunas et al. [AKLLR79]. Theorem 23.4 For any connected graph G, C(G) 2|E||V |. We will follow a di↵erent route due to Chandra et al. [CRRST89], which is based on an intriguing connection between random walks and electrical networks. Along the way, we will also obtain bounds on hitting times. 23.2 Hitting time and commute time To prove theorem 23.4, we start by proving some properties of the hitting time for a vertex. To do this, we will view the graph as an electrical network, where each edge has unit resistance. (For a detailed treatment of the relationship between random walks and electrical networks, see the classic book by Doyle and Snell [DS84].) When a potential di↵erence is applied between nodes of this network from an external source, current flows in the network in accordance with Kircho↵’s Laws and Ohm’s Laws: • K1: The total current into and out of a vertex is equal to zero. • K2: The sum of potential di↵erences around any cycle is zero. • Ohm’s Law: The current flowing along any edge is equal to pot. di↵erence resistance . electrical network: u effective resistance R(u,v): 1 1 potential difference between u and v required to send 1 unit of flow current from u to v
△M each edge e resistance Re =1 Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) Vu,V,E V,Tu,v To,u =2mR(u,U)
Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) 8u, v, 2 V, ⌧u,v + ⌧v,u = 2mR(u, v) 23-2 Lecture 23: November 17 Notes 1. The above two algorithms demonstrate a time-space tradeo↵, in that the product of space and time remains constant. In fact, it turns out that there is a whole spectrum of randomized algorithms spanning this tradeo↵ [F97]: 8s 9 algorithm using space s and time O˜(|V ||E| s ) that visits all (reachable) vertices w.h.p. (The notation O˜ hides logarithmic as well as constant factors.) 2. In an important breakthrough, Reingold [R05] showed that the above random walk algorithm could be derandomized, thus obtaining a deterministic O(1) space algorithm for graph searching (phrased more precisely as testing whether there is a path between a given pair of vertices u, v. More correctly this is a O(log n) space algorithm, since O(log n) space is needed to record the label of a vertex in an n-vertex graph, and to keep track of the number of steps taken so far.) Since the connectivity problem is a canonical problem solvable in randomized log-space, this seems like a major step towards proving that every randomized log-space algorithm can be derandomized with only a constant factor penalty in space. However, this question remains open (see, e.g., [RTV06] for some interesting approaches). We should also observe that the analogous question for directed graphs is much more challenging, since testing connectivity in this case is a complete problem for non-deterministic log-space. Thus a deterministic (or even randomized) log-space algorithm for it would show that even non-determinism buys us nothing in the world of log-space algorithms. One problem here is that the naive random walk approach breaks down because the cover time on directed graphs can be exponentially large. The bound on the cover time comes from the following theorem, originally due to Aleliunas et al. [AKLLR79]. Theorem 23.4 For any connected graph G, C(G) 2|E||V |. We will follow a di↵erent route due to Chandra et al. [CRRST89], which is based on an intriguing connection between random walks and electrical networks. Along the way, we will also obtain bounds on hitting times. 23.2 Hitting time and commute time To prove theorem 23.4, we start by proving some properties of the hitting time for a vertex. To do this, we will view the graph as an electrical network, where each edge has unit resistance. (For a detailed treatment of the relationship between random walks and electrical networks, see the classic book by Doyle and Snell [DS84].) When a potential di↵erence is applied between nodes of this network from an external source, current flows in the network in accordance with Kircho↵’s Laws and Ohm’s Laws: • K1: The total current into and out of a vertex is equal to zero. • K2: The sum of potential di↵erences around any cycle is zero. • Ohm’s Law: The current flowing along any edge is equal to pot. di↵erence resistance . u each edge e resistance Re = 1
graph G(V,E) construct an electrical network: d(u)】 d(x) for every edge e Re =1 each vertex u d() d(y) inject d(u)units 2m current flow into u a special vertex v: remove all 2m units current flow from v Lemma: /u∈V,φu,v=Tu,w
Lecture 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. for every edge e : each vertex u : Re = 1 inject d(u) units current flow into u remove all 2m units current flow from v Lemma: 8u 2 V, u,v = ⌧u,v graph G(V,E) construct an electrical network: a special vertex v :
Lemma: u∈V,φu,u=Tu,w d(u) d(x) d(u）=∑Cu→ (Kirchhoff) uw∈E d(v) d(y) =∑pu,w(Ohm) 2m uw∈D =(ou,-u,u） uw∈E =d(u)ouo->w, uw∈E 1 > u,w=1+ d(u) u,u心 uw∈E
Lecture 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 d(u) = X uw2E Cu!w (Kirchhoff) (Ohm) = X uw2E (u,v w,v) = X uw2E u,w = d(u)u,v X uw2E w,v u,v =1+ 1 d(u) X uw2E w,v
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∈E
Lecture 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
Lemma: u∈V,0u,v=Tu,u du)】 d(x) 袋效 d(v)- d(y) 2m Bw.v uw∈E has the same unique solution wu∈E
Lecture 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 =1+ 1 d(u) X wu2E ⌧w,v u,v =1+ 1 d(u) X uw2E w,v ⌧u,v ) has the same unique solution