Description

Random walks are basic models of dynamics subject to random fluctuations, with wide-ranging applications in, for instance, physics (Brownian motion), finance (market models), and biology (microbe locomotion). In simple symmetric random walk on the d-dimensional integer lattice, a particle moves at each step from its current position to one of its 2d neighbouring sites, with equal probability of each.

A celebrated theorem of Polya says that the walk will return to its starting point again and again when d is 1 or 2, but not when d is 3 or more. One way to prove this theorem is to exploit a beautiful connection between the simple random walk problem and the theory of electrical networks. The random walk can be studied by considering the resistor network formed by wiring a 1 Ohm resistor along each of the unit-length line segments of the lattice. Roughly speaking, the random walk returns to its starting point in nitely often if and only if the corresponding resistor network has in finite eff ective resistance (calculated using the usual Kirchoff laws).

The project will involve investigating aspects of random walks (with scope for simulation), including the connection to the theory of electrical networks, and applications, for example, to gambling problems.

There will also be scope for simulation.

Prerequisites

2H Probability is essential.

3H Stochastic Processes is strongly recommended.

Students taking the 4H Probability course may find it helpful, but it is not essential for the project.

If you can remember a little basic electrical network theory from school physics, that will help!

Resources

For some background on what may be involved, you should:

• revise material on random walks and Markov chains from previous courses;
• look at some of the recommended literature (or other literature you find) to see which look most helpful; look at resources e.g. on the web;
• read the introductory material in Doyle and Snell, and look at Chapters 3 and 14 of Feller (see below).

Reading list. Most books on probability will have something on random walk and gambler's ruin. A classic treatment is in Feller's book. The connection with electrical networks is explored thoroughly in Doyle and Snell's notes. Several of these books say something about applications (to finance etc.) but you might want to search for other references.

• Random walks and electric networks, P.G. Doyle and J.L. Snell, 2000. Available here.
• Introduction to Probability Theory and Its Applications, Volume I, W. Feller, 3rd ed., 1968. Chapters 3 and 14 for random walks and gambler's ruin; also Chapters 15 and 16 are relevant.
• Probability and Random Processes, G. Grimmett and D. Stirzaker, 3rd ed., 2001.
• Lectures on Contemporary Probability, G.F. Lawler and L.N. Coyle, 1999. Chapters 1 and 2 give a streamlined discussion of simple random walk.
• Problems and Snapshots from the World of Probability, G. Blom, L. Holst, and D. Sandell, 1994. Chapter 10.

Get in touch if you would be interested in probability, doing some simulations and/or have any questions!