MATH V3951
Undergraduate Seminar: Random walks and circuit theory
Fall 2006

[ Announcements ] - Updated 9.13

[ Schedule of lectures ] - Updated 11.28

Office: 408 Mathematics
Office Phone: x45881 (try my email first ... I don't answer the phone in the office)
Email: Look at the status bar at the bottom of your browser.
Homepage: www.math.columbia.edu/~xander/index.html
Office Hours: By appointment.

---

Prerequisites: An intuitive understanding of probability and expectation as well as a course in linear algebra.

Course description: We will study the beautiful connection between random walks on graphs and electrical circuit theory. Roughly speaking, a random walk is an assignment of probabilities to each edge of the graph that allows one to decide how likely s/he is to move to another vertex of the graph. If we interpret the vertices of the graph as nodes and the edges as wires of an electrical circuit, then these probabilities can be interpreted as currents when one attaches a battery to the graph. This interpretation can be used to give a very insightful proof of a theorem of Polya about how often one is likely to return to the starting point during a random walk. If time permits, we will try to move to introduce Brownian motions -- the continuous version of random walks.

References: Peter G. Doyle and J. Laurie Snell. Random walks and electric networks. GNU General Public License. You can download it from the mathematics arXiv.

Grading: You will be graded on your preparation and presentation of the selected material. If you communicate the mathematics well,
then you'll get a good grade. If you are ill prepared for your lecture and your presentation goes poorly as a result, your grade
won't be as impressive. There will also be a few exercies assigned along the way to motivate the upcoming lectures.

Attendance: It should go without saying that attendance is mandatory. Please contact me if you need to miss a meeting.

---

Announcements:

• 10.25--Here are two more papers of interest. They describe a technique for inverting certain matrices using Monte Carlo and random walk methods.
  
  • Forsythe and Leibler. "Matrix Inversion by a Monte Carlo Method."
  • Wasow. "A Note on the Inversion of Matrices by Random Walks."
• 9.13--Here are some papers of potential interest; all of them were published in the American Mathematical Monthly. Presenting one of these papers would entail explaining the main theorems or main ideas, sketching some of the proof techniques, and perhaps going through an interesting example:
  
  • Billera, Brown, and Diaconis. "Random Walks and Plane Arrangements in Three Dimensions."
  • Billingsley. "Prime Numbers and Brownian Motion."
  • Burton. "On a Particular One-Dimensional Random Walk."
  • Kac. "Random Walk and the Theory of Brownian Motion."
• 9.11--Please send me an email if you are interested in attending the seminar. I need to compile a mailing list. Disregard this if you have already done it.
• 9.8--Start reading the notes by Doyle and Snell. I'll give the first lecture, and then we'll organize the schedule of talks.

---

Tentative Schedule:

This schedule will be altered as needed during the semester.

Day	Speaker	Topic
Sept 12	Xander	Polya's Theorem
Sept 19	Alex	Chapter 1.1
Sept 26	John	Chapter 1.2
Oct 3	Sam	Chapter 1.3
Oct 10	Susie	Chapter 1.3
Oct 17	Aditi	Chapter 1.4
Oct 24	Peter	Martingales and Stopping Times
Oct 31	Jonathan	Chapter 2.1
Nov 7	Election Day	Vote! It is your responsibility!
Nov 14	Sa	Matrix Inversion via Monte Carlo methods
Nov 21	TC	Chapter 2.2
Nov 28	Jonathan	Sterling's Formula and Teaching Discussion
Dec 5	Sam and Peter	Philosophy and Finance (in that order)
Dec 12	.	No meeting



Home