随机算法 (Fall 2011)/Electrical Network
An undirected graph is called an electrical network, if
- Every edge is associated with resistance .
- The flow of current and the voltage at each vertex in the network follows Kirchhoff's Law and Ohm's Law.
In the following, we use to denote the current flow from to , to denote the voltage at vertex , to denote the difference of voltage between and , i.e. .
- Kirchhoff's Law: For every vertex , the sum of currents entering is equal to the the sum of currents leaving .
- Ohm's Law: For every edge in the graph, the currents across is equal to the difference of voltage between and over the resistance of , i.e. .
Definition (Effective Resistance) - Let , the effective resistance between and is defined to be the voltage difference between and while one unit current is injected into and removed from .
Now we use the idea of electrical network to analyze the cover time of random walk. Consider an undirected graph , we construct an electrical network whose underlying graph is and for every . If we inject units of currents into each vertex and remove all the units of currents from , where is the degree of in , then
Lemma - For every
- For every
Proof. We first compute , consider one step of random walk, we have
On the other hand,
The first and third equality follows from Kirchhoff's law and the second equality follows from Ohm's law.
Thus
The Equation (*) and Equation (**) are both linear systems with unique solution, thus .
Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) - Let , then
- Let , then
Proof. We now construct four electrical networks with underlying graph .
First, we inject units of currents into each vertex and remove units of currents from . Let denote this electrical network, then by the above lemma, we have .
Similarly, if we inject units of currents into every vertex , remove units of currents from and denote this electrical network by , then .
Now we change the direction of all the currents in , that is, units of currents are injected into and units of currents are removed from every vertex . In this electrical network , .
Since electrical networks are linear system, we can super-pose and (summing up the voltage and currents on corresponding vertices and edges) and let the resulting electrical network be . Then is an electrical network such that units of currents are injected into and units of currents are removed form . Furthermore, and thus by Ohm's law, .
Armed with this theorem, we can now give a better estimation of the cover time of random walk. Let be a spanning tree of , and be an Euler tour of , then