Graduate course in Random Walks and its Discrete Potential Theory counterpart

Mondays and Fridays 10.00 - 11.45, MVL15

Two ordinary lecure times goes away (Sept. 21 and Oct. 15), but those will be compensated by another more practical activity September 28.

Organization meeting MVL14 Sept. 3, 12.30-13.00

We discuss possible time slots for the course. And I give a very short overview of  some of the suggested contents. I will also inform you about the literature and the examination in more detail.


Some more of the historical background to random walks and discrete potential theory.
RW in one dimension, discrete harmonic functions, the maximum principle, the uniquness principle,
Friday Sept. 7, 10-12

2D random walks, the continuous heat equation, Monte Carlo solutions.
Electrical networks, see
for the PC-program (student version) and
for a Swedish introduction.
Monday Sept. 10, 10-12
Markov Chains, random walks on more general networks, ergodic- and regular Markov chains.

Dead-line 1 för uppgifterna: 1.1.2-1.1.11 (all these are related).
Friday Sept. 14, 10-12
Grattis Ida!
More general networks. A probabilistic interpretation of voltages and currents. Effective resistance and escape probability. Energy minimization - Thompson's principle.
Måndag 17/9, 10-12, MVL15
Rayleigh's monotoniciy law and its probabilistic interpretation.

Måndag 24/9, 10-12, MVL15
Dead-line 2 for: 1.2.5, 1.2.7, 1.3.1, 1.3.2, 1.3.5, 1.3.8, 1.3.11, 1.3.12.

You will work  with real (and artificial) circuits with some problems related to the book under the supervision of docent Magnus Karlsteen, Physical Electronics and Photonics at Göteborg University.

Pictures from the lab! 1, 2, 3, 4, 5, 6,7,8,9
Fredag 28/9, 9.00-12.30 (please observe the time)
Elektroniklabbet, F7105A i forskarhuset på fysik.
Polya's recurrence problem on infinite lattices. Polya's Theorem. Electrical formulation. 1D.
Måndag 1/10
Completion of the proof of Polya's Thm, for 2D and 3D.
A classical proof of Polya's Theorem.
Fredag 5/10
Random walks on more general infinite networks. The k-fuzz.
Måndag 8/10
More on the k-fuzz. (End of part I)
Fredag 12/10
Superharmonic functions, Green kernel, Harnack inequality
 Dead-line 3: 2.1.2, 2.1.3, 2.1.5, 2.1.6, 2.3.3, 2.3.4, 2.3.6,
plus these two final more open problems:
  1. Use the Monte Carlo method to give a rough estimate of the escape probability in Z^3, which we already know should be about 1-0.34. Try to come up with an alternative method (i.e. not brute force) if you can.
  2. Design your own graphs (i.e. a graph that is unlikely to be found in the literature). One which is recurrent and one that is transient. Give proofs that they indeed are of those kinds.
Fredag 19/10
Isoperimetric inequalities
Måndag 22/10
TBA, (possible buffer time)
Fredag 26/10

Oral examination Friday Nov. 2nd

Random Walks is a widely studied field, not at least here in Göteborg. It is both aesthetically appealing and has many useful different
applications such as in finance, how infections spread, and material sciences.

Discrete Potential Theory is an offspring from classical potential theory, which in turn has a long history from problems in physics.
In the classical theory, there is a connection to probability via the solution to the Dirichlet problem using Brownian motions. In the discrete setting, the connection is on the other hand evident and there is no real difference between the theories of random walks and discrete potential theory.

I will, in principle, follow parts of  the presentations in:
Random Walks and Electric Networks, Doyle and Snell, 1984 and 2000.
ii) The Art of Random Walks, Andras Telcs, LNM 1885, 2006.

But I also plan to add some text from a few of the reference books listed below.
iii) Random walks on infinite graphs and groups, Wolfgang Woess, Cambridge University Press, 2000.

Here is a short list of some of the concepts that will be discussed in the course, but I am of course open to other paths on request:

Reference books
Random Walks and Discrete Potential Theory, Ed. Picardello and Woess, Cambridge University Press, 1999.
Potential Theory on Infinite Networks, LNM 1590, 1994.
Dirichlet problem at infinity for harmonic functions on graphs, Lecture Notes by Wolfgang Woess, Quaderno n. 38/1994.

Transfiniteness for Graphs, Electrical Networks and Random Walks, A.H. Zemanian, Birkhäuser,1996. (See also)

There will be two lectures a week during this period:

There will be home-assignments, and an oral examination at the end.

Torbjörn Lundh