随机算法 (Fall 2011)/Electrical Network

An undirected graph ${\displaystyle G=(V,E)}$ is called an electrical network, if

1. Every edge ${\displaystyle e=\{u,v\}}$ is associated with resistance ${\displaystyle R_{uv}}$.
2. 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 ${\displaystyle C_{uv}}$ to denote the current flow from ${\displaystyle u}$ to ${\displaystyle v}$, ${\displaystyle V_{u}}$ to denote the voltage at vertex ${\displaystyle u}$, ${\displaystyle \phi _{uv}}$ to denote the difference of voltage between ${\displaystyle u}$ and ${\displaystyle v}$, i.e. ${\displaystyle \phi _{uv}=V_{u}-V_{v}}$.

• Kirchhoff's Law: For every vertex ${\displaystyle v}$, the sum of currents entering ${\displaystyle v}$ is equal to the the sum of currents leaving ${\displaystyle v}$.
• Ohm's Law: For every edge ${\displaystyle e=\{u,v\}}$ in the graph, the currents across ${\displaystyle e}$ is equal to the difference of voltage between ${\displaystyle u}$ and ${\displaystyle v}$ over the resistance of ${\displaystyle e}$, i.e. ${\displaystyle C_{uv}={\frac {\phi _{uv}}{R_{uv}}}}$.
 Definition (Effective Resistance) Let ${\displaystyle u,v\in V}$, the effective resistance ${\displaystyle R(u,v)}$ between ${\displaystyle u}$ and ${\displaystyle v}$ is defined to be the voltage difference between ${\displaystyle u}$ and ${\displaystyle v}$ while one unit current is injected into ${\displaystyle u}$ and removed from ${\displaystyle v}$.

Now we use the idea of electrical network to analyze the cover time of random walk. Consider an undirected graph ${\displaystyle G=(V,E)}$, we construct an electrical network whose underlying graph is ${\displaystyle G}$ and ${\displaystyle R_{e}=1}$ for every ${\displaystyle e\in E}$. If we inject ${\displaystyle d(w)}$ units of currents into each vertex ${\displaystyle w\in V}$ and remove all the ${\displaystyle 2|E|}$ units of currents from ${\displaystyle v}$, where ${\displaystyle d(w)}$ is the degree of ${\displaystyle w}$ in ${\displaystyle G}$, then

 Lemma For every ${\displaystyle u,v\in V}$ ${\displaystyle \phi _{uv}=H_{uv}}$
Proof.
 We first compute ${\displaystyle H_{uv}}$, consider one step of random walk, we have {\displaystyle {\begin{aligned}H_{uv}&=\sum _{\{x,u\}\in E}{\frac {1}{d(u)}}(1+H_{xv})\\&=1+{\frac {1}{d(u)}}\sum _{\{x,u\}\in E}H_{xv}\qquad (*)\end{aligned}}} On the other hand, {\displaystyle {\begin{aligned}d(u)&=\sum _{\{u,x\}\in E}C_{ux}\\&=\sum _{\{u,x\}\in E}\phi _{ux}\\&=\sum _{\{u,x\}\in E}(\phi _{uv}-\phi _{xv})\\&=d(u)\phi _{uv}-\sum _{\{u,x\}\in E}\phi _{xv}\end{aligned}}} The first and third equality follows from Kirchhoff's law and the second equality follows from Ohm's law. Thus ${\displaystyle \phi _{uv}=1+{\frac {1}{d(u)}}\sum _{\{u,x\}\in E}\phi _{xv}\qquad (**)}$ The Equation (*) and Equation (**) are both linear systems with unique solution, thus ${\displaystyle H_{uv}=\phi _{uv}}$.
${\displaystyle \square }$
 Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989) Let ${\displaystyle u,v\in V}$, then ${\displaystyle H_{uv}+H_{vu}=2|E|\cdot R(u,v)}$
Proof.
 We now construct four electrical networks ${\displaystyle A,B,C,D}$ with underlying graph ${\displaystyle G}$. First, we inject ${\displaystyle d(w)}$ units of currents into each vertex ${\displaystyle w}$ and remove ${\displaystyle 2|E|}$ units of currents from ${\displaystyle v}$. Let ${\displaystyle A}$ denote this electrical network, then by the above lemma, we have ${\displaystyle H_{uv}=\phi _{uv}^{A}}$. Similarly, if we inject ${\displaystyle d(w)}$ units of currents into every vertex ${\displaystyle w}$, remove ${\displaystyle 2|E|}$ units of currents from ${\displaystyle u}$ and denote this electrical network by ${\displaystyle B}$, then ${\displaystyle H_{vu}=\phi _{vu}^{B}}$. Now we change the direction of all the currents in ${\displaystyle B}$, that is, ${\displaystyle 2|E|}$ units of currents are injected into ${\displaystyle u}$ and ${\displaystyle d(w)}$ units of currents are removed from every vertex ${\displaystyle w}$. In this electrical network ${\displaystyle C}$, ${\displaystyle H_{vu}=\phi _{uv}^{C}}$. Since electrical networks are linear system, we can super-pose ${\displaystyle A}$ and ${\displaystyle C}$ (summing up the voltage and currents on corresponding vertices and edges) and let the resulting electrical network be ${\displaystyle D}$. Then ${\displaystyle D}$ is an electrical network such that ${\displaystyle 2|E|}$ units of currents are injected into ${\displaystyle u}$ and ${\displaystyle 2|E|}$ units of currents are removed form ${\displaystyle v}$. Furthermore, ${\displaystyle H_{uv}+H_{vu}=\phi _{uv}^{D}}$ and thus by Ohm's law, ${\displaystyle H_{uv}+H_{vu}=2|E|\cdot R(u,v)}$.
${\displaystyle \square }$

Armed with this theorem, we can now give a better estimation of the cover time of random walk. Let ${\displaystyle T}$ be a spanning tree of ${\displaystyle G}$, and ${\displaystyle u=v_{1}\to v_{2}\to \ldots \to v_{2n}=u}$ be an Euler tour of ${\displaystyle T}$, then

${\displaystyle C_{u}\leq \sum _{i=1}^{2n-1}H_{v_{i}v_{i+1}}=\sum _{\{u,v\}\in T}(H_{uv}+H_{vu})\leq 2mn}$