Consider an electrical network on n nodes with resistors rij between nodes i and j. Let Rij denote the effective resistance between the nodes. Then Foster’s Theorem 5 asserts thatwhere i ∼ j denotes i and j are connected by a finite rij. In 10 this theorem is proved by making use of random walks. The classical connection between electrical networks and reversible random walks implies a corresponding statement for reversible Markov chains. In this paper we prove an elementary identity for ergodic Markov chains, and show that this yields Foster's theorem when the chain is time-reversible.We also prove a generalization of a resistive inverse identity. This identity was known for resistive networks, but we prove a more general identity for ergodic Markov chains. We show that time-reversibility, once again, yields the known identity. Among other results, this identity also yields an alternative characterization of reversibility of Markov chains (see Remarks 1 and 2 below). This characterization, when interpreted in terms of electrical currents, implies the reciprocity theorem in single-source resistive networks, thus allowing us to establish the equivalence of reversibility in Markov chains and reciprocity in electrical networks.
%0 Journal Article
%1 tetali94
%A Tetali, Prasad
%C Cambridge, UK
%D 1994
%I Cambridge University Press
%J Combinatorics, Probability and Computing
%K circuit effective.resistance foster.theorem graph.theory physics
%N 3
%P 421-–427
%R 10.1017/S0963548300001309
%T An Extension of Foster’s Network Theorem
%V 3
%X Consider an electrical network on n nodes with resistors rij between nodes i and j. Let Rij denote the effective resistance between the nodes. Then Foster’s Theorem 5 asserts thatwhere i ∼ j denotes i and j are connected by a finite rij. In 10 this theorem is proved by making use of random walks. The classical connection between electrical networks and reversible random walks implies a corresponding statement for reversible Markov chains. In this paper we prove an elementary identity for ergodic Markov chains, and show that this yields Foster's theorem when the chain is time-reversible.We also prove a generalization of a resistive inverse identity. This identity was known for resistive networks, but we prove a more general identity for ergodic Markov chains. We show that time-reversibility, once again, yields the known identity. Among other results, this identity also yields an alternative characterization of reversibility of Markov chains (see Remarks 1 and 2 below). This characterization, when interpreted in terms of electrical currents, implies the reciprocity theorem in single-source resistive networks, thus allowing us to establish the equivalence of reversibility in Markov chains and reciprocity in electrical networks.
@article{tetali94,
abstract = {Consider an electrical network on n nodes with resistors rij between nodes i and j. Let Rij denote the effective resistance between the nodes. Then Foster’s Theorem [5] asserts thatwhere i ∼ j denotes i and j are connected by a finite rij. In [10] this theorem is proved by making use of random walks. The classical connection between electrical networks and reversible random walks implies a corresponding statement for reversible Markov chains. In this paper we prove an elementary identity for ergodic Markov chains, and show that this yields Foster's theorem when the chain is time-reversible.We also prove a generalization of a resistive inverse identity. This identity was known for resistive networks, but we prove a more general identity for ergodic Markov chains. We show that time-reversibility, once again, yields the known identity. Among other results, this identity also yields an alternative characterization of reversibility of Markov chains (see Remarks 1 and 2 below). This characterization, when interpreted in terms of electrical currents, implies the reciprocity theorem in single-source resistive networks, thus allowing us to establish the equivalence of reversibility in Markov chains and reciprocity in electrical networks.},
added-at = {2017-01-24T08:27:47.000+0100},
address = {Cambridge, UK},
author = {Tetali, Prasad},
biburl = {https://www.bibsonomy.org/bibtex/2031be1afefa878faed2063492c01b5a2/ytyoun},
doi = {10.1017/S0963548300001309},
interhash = {4d66b6493d41ea8e14251e0291b24dc6},
intrahash = {031be1afefa878faed2063492c01b5a2},
journal = {Combinatorics, Probability and Computing},
keywords = {circuit effective.resistance foster.theorem graph.theory physics},
month = sep,
number = 3,
pages = {421-–427},
publisher = {Cambridge University Press},
timestamp = {2017-02-01T04:27:21.000+0100},
title = {An Extension of {Foster’s} Network Theorem},
volume = 3,
year = 1994
}