Random walks are basic models of dynamics subject to random fluctuations, with wide-ranging applications in different areas such as physics (Brownian motion) and biology (microbe locomotion). The most classical example is the simple symmetric random walk on the d-dimensional integer lattice, in which a particle moves at each step from its current position to one of its 2d neighbouring sites chosen uniformly at random.
A celebrated theorem of Pólya 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. By considering a resistor network of 1-Ohm resistors along each of the unit-length line segments of the lattice, one can reformulate Pólya's result and come to the conclusion that the random walk returns to its starting point infinitely often if and only if the corresponding resistor network has infinite effective resistance.
This project will involve investigating aspects of random walks from the lens of electrical networks and potential theory, and there will be opportunities to explore different applications (e.g. gambling problems) or connections to other topics in probability theory.
There will also be scope for simulation and numerical computations.
Note: this project will be jointly supervised with Dr Nicholas Georgiou.
2H Markov chain and 2H Probability are essential.
(If you can remember a little basic electrical network theory from school physics, that will also help!)
3H Stochastic Processes is not necessary but strongly recommended.
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).
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 but you might want to search for other references.
Random walks and electric networks, P.G. Doyle and J.L. Snell, 2000.
Probability on Trees and Networks, R. Lyons and Y. Peres, 2016. Chapter 2 gives a similar (but more advanced account) of the electrical network theory.
Reversible Markov Chains and Random Walks on Graphs, D. Aldous and J. Fill. Section 3.3 discusses elements of electrical network, based on Chapter 2 of the above book.
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.