Electrical network

An electrical network is a weighted graph whose edge weights are interpreted as electrical conductances. Random-walk hitting quantities can then be expressed through voltages, currents, and effective resistance.

Electrical current from stopped random-walk traversals ( $i (x, y) = w_{x y} (G (s, x) / w_{x} - G (s, y) / w_{y})$ )

In a finite connected electrical network, run the conductance random walk from

s

until its first visit to a distinct vertex

t

. Let

G (s, x)

be the expected visits to

x

before stopping, and

w_{x} = \sum_{y} w_{x y}

. The expected signed number of traversals of

{x, y}

is the displayed expression. Its divergence is

1_{x = s} - 1_{x = t}

by telescoping each path, and its resistance-weighted sum around a cycle is zero because

G (s, x) / w_{x}

is a voltage. Uniqueness follows by summing

\sum_{{x, y}} w_{x y} (v_{x} - v_{y})^{2}

: a zero-divergence voltage flow has zero energy. Thus the expected net traversals are exactly the unit source-to-sink current.

Voltage ( $u : V \to R$ )

A voltage is a scalar potential on the vertices of an electrical network. Away from prescribed boundary vertices it is harmonic, and its difference across an edge drives current through that edge.

Current flow ( $i (x, y)$ )

A current flow is an antisymmetric function on oriented edges satisfying Kirchhoff's node law away from its sources and sinks. For conductance

c (x, y)

u

, Ohm's law gives

i (x, y) = c (x, y) (u (x) - u (y))

.

Kirchhoff cycle law

The Kirchhoff cycle law says the directed sum of voltage drops around every graph cycle is zero. For unit edge resistance this is the sum of signed currents around the graph cycle. With unit edge resistance, the current is a voltage gradient: define the voltage difference by summing drops along a graph path. The difference of the sums along two graph paths is a sum around closed walks; decomposing these into graph cycles makes it zero. Together with the Kirchhoff node law, the resulting Graph Laplacian equation determines current uniquely on a finite connected network.

Kirchhoff node law

The Kirchhoff node law says the sum of outward currents at a graph vertex is zero unless that graph vertex is a source or sink. In an electrical network, it is flow conservation; a unit flow has divergences

+ 1

and

- 1

at its terminals.

Effective resistance ( $R_{eff} (a, z)$ )

The effective resistance between vertices

a

and

z

is the voltage difference required to send one unit of current from

a

to

z

.

Return probability from effective resistance ( $P_{x} (T_{x}^{+} < T_{y}) = 1 - (d (x) R (x, y))^{- 1}$ )

For the conductance-weighted random walk on a graph, set

d (x) = \sum_{v} c_{xv}

h (u) = P_{u} (T_{x} < T_{y})

has boundary values one and zero. The total electric current is

\sum_{v} c_{xv} (1 - h (v)) = 1/ R (x, y)

. The first-step analysis therefore gives the displayed positive-return-time formula. Wiring the exterior of finite sets and taking limits gives

P_{x} (T_{x}^{+} = \infty) = 1/ (d (x) R (x, \infty))

.

Foster's theorem ( $\sum_{e} c_{e} R_{eff} (e) = ∣ V ∣ - 1$ )

For a finite connected unweighted loopless graph with

n

graph vertices,

\sum_{e \in E} R_{eff} (e) = n - 1.

The edge-inclusion formula for a uniform spanning tree gives the left-hand side as

E ∣ T ∣

, and every spanning tree has

n - 1

edges. On the same finite connected graph with positive edge conductances

c_{e} > 0

, the corresponding identity is

\sum_{e} c_{e} R_{eff} (e) = n - 1

.

Effective resistance to infinity ( $R_{eff} (o \leftrightarrow \infty)$ )

The effective resistance to infinity is the limit of the effective resistance from a fixed vertex to the wired complement of increasing finite sets. It is finite exactly when the finite-energy flow criterion for transience holds.

Rayleigh monotonicity principle

Increasing edge resistances, including deleting edges, cannot decrease effective resistance. Decreasing resistances or identifying vertices cannot increase effective resistance. These statements also follow from the Thomson principle.

Effective conductance ( $C_{eff} = 1/ R_{eff}$ )

The effective conductance between two terminals is the reciprocal of their effective resistance. Under a unit voltage difference it equals the total current flowing from one terminal to the other.

Thomson principle

Thomson principle says that effective resistance is the minimum energy among unit flows from

a

to

z

:

R_{eff} (a, z) = in f_{θ} \sum_{e} \frac{θ ( e ) ^{2}}{c ( e )} .

Nash-Williams inequality

If

Π_{1}, \dots, Π_{m}

are pairwise edge-disjoint cutsets separating

a

from

z

in an electrical network, then

R_{eff} (a, z) \geq \sum_{k = 1}^{m} (\sum_{e \in Π_{k}} c (e))^{- 1} .

Commute time identity

For a random walk on a finite electrical network,

E_{a} T_{z} + E_{z} T_{a} = 2 (\sum_{e \in E} c (e)) R_{eff} (a, z) .

Directed edge occupation in a random-walk commute ( $E S (u, v) = R_{eff} (a, z)$ )

Let simple random walk travel from

a \neq = z

to its first visit to

z

, then stop on its subsequent first hit of

a

in a finite connected unweighted loopless graph. Every directed edge

u \to v

has expected traversal count

E S (u, v) = R_{eff} (a, z) .

The Strong Markov property splits the count into the two killed legs. By killed-walk occupation voltage, their contributions are

v_{a z} (u)

and

v_{z a} (u)

. Their Laplacians cancel, so the harmonic maximum principle on a finite graph makes the sum constant, with value

v_{a z} (a) + v_{z a} (a) = R_{eff} (a, z)

. Summing over all directed edges recovers the commute time identity.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version