随机算法 (Fall 2011)/Electrical Network

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

1. Every edge [math]\displaystyle{ e=\{u,v\} }[/math] is associated with resistance [math]\displaystyle{ R_{uv} }[/math].
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 [math]\displaystyle{ C_{uv} }[/math] to denote the current flow from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math], [math]\displaystyle{ V_u }[/math] to denote the voltage at vertex [math]\displaystyle{ u }[/math], [math]\displaystyle{ \phi_{uv} }[/math] to denote the difference of voltage between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math], i.e. [math]\displaystyle{ \phi_{uv}=V_u-V_v }[/math].

• Kirchhoff's Law: for every vertex [math]\displaystyle{ v }[/math], the sum of currents entering [math]\displaystyle{ v }[/math] is equal to the the sum of currents leaving [math]\displaystyle{ v }[/math].
• Ohm's Law: for every edge [math]\displaystyle{ e=\{u,v\} }[/math] in the graph, the currents across [math]\displaystyle{ e }[/math] is equal to the difference of voltage between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] over the resistance of [math]\displaystyle{ e }[/math], i.e. [math]\displaystyle{ C_{uv}=\frac{\phi_{uv}}{R_{uv}} }[/math].

Definition (Effective Resistance)

Let [math]\displaystyle{ u,v\in V }[/math], the effective resistance [math]\displaystyle{ R(u,v) }[/math] between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] is defined to be the voltage difference between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] while one unit current is injected into [math]\displaystyle{ u }[/math] and removed from [math]\displaystyle{ v }[/math].

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

Lemma

For every [math]\displaystyle{ u,v\in V }[/math] [math]\displaystyle{ \phi_{uv}=H_{uv} }[/math] where [math]\displaystyle{ \phi_{uv} }[/math] is the difference of voltage between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math].

Proof. We first compute [math]\displaystyle{ H_{uv} }[/math], consider one step of random walk, we have [math]\displaystyle{ \begin{align} H_{uv}&=\sum_{xu\in E}\frac{1}{d_u}(1+H_{xv})\\ &=1+\frac{1}{d_u}\sum_{xu\in E}H_{xv} \qquad(*) \end{align} }[/math] On the other hand, [math]\displaystyle{ \begin{align} 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{align} }[/math] The first and third equality follows from Kirchhoff's law and the second equality follows from Ohm's law. Thus [math]\displaystyle{ \phi_{uv}=1+\frac{1}{d_u}\sum_{\{u,x\}\in E}\phi_{xv} \qquad(**) }[/math] The Equation (*) and Equation (**) are both linear systems with unique solution, thus [math]\displaystyle{ H_{uv}=\phi_{uv} }[/math]. [math]\displaystyle{ \square }[/math]

Theorem (Chandra-Raghavan-Ruzzo-Smolensky-Tiwari 1989)

Let [math]\displaystyle{ u,v\in V }[/math], then [math]\displaystyle{ H_{uv}+H_{vu}=2|E|\cdot R(u,v) }[/math]

Proof. We now construct four electrical networks [math]\displaystyle{ A,B,C,D }[/math] with underlying graph [math]\displaystyle{ G }[/math]. First, we inject [math]\displaystyle{ d(w) }[/math] units of currents into each vertex [math]\displaystyle{ w }[/math] and remove [math]\displaystyle{ 2|E| }[/math] units of currents from [math]\displaystyle{ v }[/math]. Let [math]\displaystyle{ A }[/math] denote this electrical network, then by the above lemma, we have [math]\displaystyle{ H_{uv}=\phi_{uv}^A }[/math]. Similarly, if we inject [math]\displaystyle{ d(w) }[/math] units of currents into every vertex [math]\displaystyle{ w }[/math], remove [math]\displaystyle{ 2|E| }[/math] units of currents from [math]\displaystyle{ u }[/math] and denote this electrical network by [math]\displaystyle{ B }[/math], then [math]\displaystyle{ H_{vu}=\phi_{vu}^B }[/math]. Now we change the direction of all the currents in [math]\displaystyle{ B }[/math], that is, [math]\displaystyle{ 2|E| }[/math] units of currents are injected into [math]\displaystyle{ u }[/math] and [math]\displaystyle{ d(w) }[/math] units of currents are removed from every vertex [math]\displaystyle{ w }[/math]. In this electrical network [math]\displaystyle{ C }[/math], [math]\displaystyle{ H_{vu}=\phi_{uv}^C }[/math]. Since electrical networks are linear system, we can super-pose [math]\displaystyle{ A }[/math] and [math]\displaystyle{ C }[/math] (summing up the voltage and currents on corresponding vertices and edges) and let the resulting electrical network be [math]\displaystyle{ D }[/math]. Then [math]\displaystyle{ D }[/math] is the electrical network such that [math]\displaystyle{ 2|E| }[/math] units of currents are injected into [math]\displaystyle{ u }[/math] and [math]\displaystyle{ 2|E| }[/math] units of currents are removed form [math]\displaystyle{ v }[/math]. Furthermore, [math]\displaystyle{ H_{uv}+H_{vu}=\phi_{uv}^D }[/math] and thus by Ohm's law, [math]\displaystyle{ H_{uv}+H_{vu}=2|E|\cdot R(u,v) }[/math]. [math]\displaystyle{ \square }[/math]

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

[math]\displaystyle{ C_u\le \sum_{i=1}^{2n}H_{v_i v_{i+1}}=\sum_{\{u,v\}\in T}(H_{uv}+H_{vu})\le 2mn }[/math]