Random walks and the effective resistance sum rules

In this paper, using the intimate relations between random walks and electrical networks, we first prove the following effective resistance local sum rules: c i Ω i j + ∑ k ∈ Γ ( i ) c i k ( Ω i k − Ω j k ) = 2 , where Ω i j is the effective resistance between vertices i and j , c i k is the conduct...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2010-08, Vol.158 (15), p.1691-1700
Main Author: Chen, Haiyan
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Conductance
Effective resistance
Electric networks
Exact sciences and technology
Hitting time
Mathematical analysis
Mathematics
Random walk
Sciences and techniques of general use
Subdivision network
Sum rules
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, using the intimate relations between random walks and electrical networks, we first prove the following effective resistance local sum rules: c i Ω i j + ∑ k ∈ Γ ( i ) c i k ( Ω i k − Ω j k ) = 2 , where Ω i j is the effective resistance between vertices i and j , c i k is the conductance of the edge, Γ ( i ) is the neighbor set of i , and c i = ∑ k ∈ Γ ( i ) c i k . Then we show that from the above rules we can deduce many other local sum rules, including the well-known Foster’s k -th formula. Finally, using the above local sum rules, for several kinds of electrical networks, we give the explicit expressions for the effective resistance between two arbitrary vertices.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2010.05.020