Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-03T01:31:59.683Z Has data issue: false hasContentIssue false

Random walk and electric currents in networks

Published online by Cambridge University Press:  24 October 2008

C. St J. A. Nash-Williams
Affiliation:
Department of MathematicsUniversity of Aberdeen

Abstract

Let G be a locally finite connected graph and c be a positive real-valued function defined on its edges. Let D(ξ) denote the sum of the values of c on the edges incident with a vertex ξ. A particle starts at some vertex α and performs an infinite random walk

in which (i) the ξj are vertices of G, (ii), λj. is an edge joining ξj–1 to ξj (j = 1, 2, 3, …), (iii) if λ is any edge incident with ξj, then

Let υ be a set of vertices of G such that the complementary set of vertices is finite and includes α. A geometrical characterization is given of the probability (τ, say) that the particle will visit some element of υ without first returning to α. An essentially equivalent problem is obtained by regarding G as an electrical network and c(λ) as the conductance of an edge λ; the current flowing through the network from α to υ when an external agency maintains α at potential I and all elements of υ at potential 0 is found to be τD(α).

A necessary and sufficient condition (of a geometrical character) for the particle to be certain to return to α. is obtained; and, as an application, a new proof is given of a conjecture of Gillis (3) regarding centrally biased random walk on an n–dimensional lattice.

Type
Research Article
Copyright
Copyright © Cambridge Philosophical Society 1959

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

REFERENCES

(1)Feller, W.An introduction to probability theory and its applications, vol. 1, 2nd ed. (New York and London, 1957).Google Scholar
(2)Foster, F. G.On Markov chains with an enumerable infinity of states. Proc. Camb. Phil. Soc. 48 (1952), 587–91.CrossRefGoogle Scholar
(3)Gillis, J.Centrally biased discrete random walk. Quart. J. Math. (2) 7 (1956), 144–52.Google Scholar
(4)Hardy, G. H., Littlewood, J. E. and Pólya, G.Inequalities (Cambridge, 1934).Google Scholar
(5)Jeans, J. H.The mathematical theory of electricity and magnetism, 5th ed. (Cambridge, 1933).Google Scholar
(6)Kendall, D. G.On non-dissipative Markoff chains with an enumerable infinity of states. Proc. Camb. Phil. Soc. 47 (1951), 633–4.CrossRefGoogle Scholar
(7)König, D.Theorie der endlichen und unendlichen Graphen (Leipzig, 1936).Google Scholar