Random Paths and Cuts, Electrical Networks, and Reversible Markov Chains

Abstract

Let G be a graph representing an electrical network having source a and sink b, where edge e has conductivity $C( e )$ and resistance $R ( e )( R ( e ) = 1/C ( e ) )$. Let $C_{\text{eff}} $ and $R_{\text{eff}} $ denote the effective conductivity and effective resistance of G, respectively, $(R_{\text{eff}} = 1/C_{\text{eff}} )$. Let $\mathcal{P}$ denote the set of all paths joining a and b, and $\mathcal{K}$ denote the set of all cuts separating a and b. Let P be a random path from $\mathcal{P}$ having probability function p, and K be a random cut from $\mathcal{K}$ having probability function q. Denote by $\pi ( e )( \kappa ( e ) )$ the expected number of paths (cuts) containing edge e. For w a weighting defined on E and H a subset of E (or subgraph ), let $| H |_w = \sum_{e \in H} w ( e ) $. In this paper it is shown that $C_{\text{eff}} $ equals the maximum expected value of $1/ | P |_{R\pi } $ over all probability functions p. Further, the maximum is achieved when p is chosen so that $\pi $ is the current weighting. An immediate corollary of this result is Thomson’s Principle which characterizes the effective resistance as the minimum energy dissipation among all unit flows through the network. It is also shown that $R_{\text{eff}} $ equals the maximum expected value of $1/| K |_{C\kappa } $ over all probability functions q. Furthermore, the maximum is achieved when q is chosen so that $\kappa $ is the voltage weighting. This result yields Nash–Williams’ condition [5] for recurrence of reversible Markov chains.