This course is offered in the framework of the Fields Academy All students have to be registered. Contact me for waiving the registration fee.

Lecturer: Vadim Kaimanovich (University of Ottawa)

Schedule: Mondays 13:00-14:20, Wednesdays 11:30-12:50 (study break the week October 25-29). The first introductory and organizational lecture will be held live via Zoom on September 8. After that the content will be delivered in the asynchronous mode: the videos and notes for each week will be uploaded to this site the weekend before. Therefore, there will be no live sessions on Mondays, whereas Wednesday sessions will be entirely devoted to live discussions of current week's material. The last lecture will be held on December 8.

Overview: Random walks is an umbrella term for Markov chains on state spaces endowed with additional structures (e.g., on graphs or groups). This area is currently very active with numerous connections ranging from purely theoretical aspects of, say, group theory or hyperbolic geometry, to very applied topics such as data mining and machine learning. The purpose of the course is both to introduce the theory or random walks and to show how it illustrates a number of fundamental notions often neglected in applied expositions: Lebesgue (standard) probability spaces, conditional probabilities and martingales, entropy and Kullback-Leibler divergence, law of large numbers and subadditive ergodic theorem, etc. The course is based on lecture notes; additional references will be given whenever necessary.

Grading: assignments and a written report.

Content delivery: the cumulative file with lecture notes is available at this link; the video files and whiteboard notes are in the corresponding folders (use the top right navigation bar). For a better video quality it is recommended to download the video files rather than using the built-in player.

Assignments: those who are interested in having a grade for this course should submit their completed assignments to me by email by the due date with "Markov chains course" and the assignment number in the subject line. Submissions in LaTeX or other typesetting systems are most welcome; otherwise please make an effort to write legibly. Make sure that you present your arguments in a detailed and consistent way, so that I can understand your reasoning. It is not necessary to do every single exercise, as some of them are more difficult or require additional background. However, I expect you to do most of the exercises.

• Assignment 1: Exercises to Lectures 1-8 highlighted in the lecture notes.

• Final report: The deadline for submitting the final report is January 9. It is supposed to be in the form of notes similar to those taken by student scribes recording lectures. For an example see the samples of scribe notes of analogous courses offered at Princeton, MIT, or Georgia Tech. I expect you to submit the notes of at least 6 lectures chosen to provide a representative cross-section of the course.

Current status: all course content (lectures 1-24) uploaded. Those interested in having a grade for this course please let me know as soon as possible.