Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-25T04:29:54.715Z Has data issue: false hasContentIssue false
  • English
  • Français

An Extension of Foster's Network Theorem

Published online by Cambridge University Press:  12 September 2008

Prasad Tetali
Prasad Tetali
Affiliation:
AT & T Bell Labs, Murray Hill, NJ 07974. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 that

where 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.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 3 , September 1994 , pp. 421 - 427
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R. and Tiwari, P. (1989) The electrical resistance of a graph captures its commute and cover times. Proc. of the 21st Annual ACM Symp. on Theory of Computing 574–586.Google Scholar
[2]Coppersmith, D., Doyle, P., Raghavan, P. and Snir, M. (to appear) Random Walks on Weighted Graphs, and Applications to On-line Algorithms. Jour. of the ACM.Google Scholar
[3]Coppersmith, D., Tetali, P. and Winkler, P. (1993) Collisions among random walks on a graph. SIAM J. on Discrete Math. 6 363–374.CrossRefGoogle Scholar
[4]Doyle, P. G. and Snell, J. L. (1984) Random Walks and Electric Networks, The Mathematical Association of America.CrossRefGoogle Scholar
[5]Foster, R. M. (1949) The Average impedance of an electrical network. Contributions to Applied Mechanics (Reissner Anniversary Volume), Edwards Bros., Ann Arbor, Mich. 333–340.Google Scholar
[6]Foster, R. M. (1961) An extension of a network theorem. IRE Trans. Circuit Theory 8 75–76.CrossRefGoogle Scholar
[7]Hayt, W. H. Jr, and Kemmerly, J. E. (1978) Engineering Circuit Analysis, McGraw-Hill, 3rd ed.Google Scholar
[8]Kemeny, J. G. and Snell, J. L. (1983) Finite Markov Chains, Springer-Verlag.Google Scholar
[9]Kemeny, J. G., Snell, J. L. and Knapp, A. W. (1976) Denumerable Markov Chains, Springer-Verlag.CrossRefGoogle Scholar
[10]Tetali, P. (1991) Random Walks and the effective resistance of networks. J. Theoretical Probability 4 101–109.CrossRefGoogle Scholar
[11]Tetali, P. (1994) Design of on-line algorithms using hitting times. Proceedings of the 5th annual ACM-SIAM Symp. on Discrete Algorithms, Virginia402–411.Google Scholar