The first lecture discusses simple random walk in one dimension
and is anything but contemporary. It leads to a derivation of Stir-
ling's formula. The second lecture discusses random walk in several
dimensions and introduces the notion of power laws. Standard results
about probability of return to the origin and the intersection exponent
are discussed. The latter is a simply stated exponent whose value is
not known rigorously today, and it is a natural exponent to study by
simulation. The third lecture discusses the self-avoiding walk, which
is a very good example of a simply stated mathematical problem for
which most of the interesting questions are still open problems. The
fourth lecture considers the continuous limit of random walk, Brown-
ian motion. This topic was included to help those students who were
involved in simulations related to finance.
The next two lectures consider the problem of shuffling a deck of
cards. Lecture 5 discusses the general idea of random permutations
and introduces the notion of a random walk on a symmetric group.
The case of random riffle shuffles and the time (number of shuffles)
needed to get close to the uniform distribution was analyzed in a paper
of Bayer and Diaconis [BD], and Mann's paper [M] is an exposition
of this result. We give a short discussion of this result, although we do
not give all the details of the proof. This topic leads naturally to the
discussion of Markov chains and rates of convergence to equilibrium.
Lecture 7 is a standard introduction to Markov chains; it outlines a
proof of convergence to equilibrium that emphasizes the importance
of the size of the second eigenvalue for understanding the rate of
convergence. Lecture 8 disucsses a recent important technique to
sample from complicated distributions, Markov Chain Monte Carlo.
Lecture 9 discusses a very beautiful relationship between random
walks and electrical networks (see [DS] for a nice exposition of this
area). The basic ideas in this section are used in more sophisticated
probability; this is basically the discrete version of Dirichlet forms.
The work on electrical networks leads to the final lecture on uniform
spanning trees. We discuss one result that relates three initially quite