Home

Welcome to the webpage of the class Markov Chains at HSE, 2025/26.

• Schedules of the lectures: On Thursday, 16:20-17:40. September 4th 2025 – December 18th 2025.

• Location: Room 109, Ulitsa Usacheva 6, Moscow.

• Keep in touch: On the class telegram channel, you can ask questions and receive real-time updates in case of any last-moment schedule change.

• In the calendar, you see the lectures schedule, the preliminary schedules for the intermediate controls and assignments, the oral exam dates.

• Upcoming dates: October 24th, first assignment.

• Upcoming dates: October 30th, Fall Session control work.

• Upcoming dates: December 18th, second assignment.

• Upcoming dates: around December 22th, retake of the written control work.

• Upcoming dates: around December 25th, oral exam.

Syllabus

Lectures

(Updated after each lecture)

• Lecture 1: History, motivations, examples. First definitions of Markov Chains (probabilities on the space of trajectories, the Markov property, transition probabilities, initial distribution) Up to the section Markov chains: Definitions, but the measure-theoretic remarks can be ignored (Kolmogorov, filtrations). You are strongly encouraged to solve the exercises in the lectures.
• Lecture 2: Review of the notation. Markov property and strong Markov property. Examples (content to the end of the first chapter excluding the abstract formulation, including exercises).
• Lecture 3: Markov operator. Hitting probabilities and linear equations. We did not prove the statement about the trace in chapter2, but it helps you for the assignment in any case.
• Lecture 4/5: Equivalent definitions of Communicating classes and recurrence/transience.
• Lecture 6: Transience and recurrence of simple walks in \(\mathbb{Z}^d\). At this point the first four chapters of the lectures notes are covered.
• Lecture 7/8: Invariant measures and recurrence. Coupling argument for convergence of positive-recurrent aperiodic irreducible chains. At this point the first five chapters of the lectures notes are covered.
• Lecture 9: Perron-Frobenius Theorem and exponential convergence.
• Lecture 10: Another look at linear equations (uniqueness for ergodic chains). In-arborescences formalism: last-passage Markov chain on arborescences and invariant measure.
• Lecture 11/12: The Galton-Watson tree.
• Lecture 12/13/14: Quantitative limit theorems: fluctuations of empirical measures on vertices and edges.
• Lecture 15: MCMC and Metropolis Hastings.

Original plan

(Flexible, depending on students background and interest)

• Markov chains with finite and countable state space.
• Stationary states and their existence
• Perron–Frobenius theorem.
• Ergodic theorems for Markov chains (lattice and non-lattice).
• Applications of the ergodic theorem. The law of large numbers for Markov chains.
• Notable examples: The Galton-Watson tree, The Google’s Page Rank.
• Derived Markov Chains (permutations, spanning trees).

References

Related Preliminaries

• A short, self-contained modern introduction to Measure Theory. It contains far more than needed in this class, and it is a good read if you need to refresh your knowledge of Measure Theory.
• A short, non-self-contained reference about Probability Theory. It contains far more than needed in this class, and you may check it when you have some doubts.
• L.Koralov , Y.G.Sinai (2007). Theory of Probability and Random Processes [EN|RU] A general introduction to Probability Theory, available in Russian and English.

Books

• J.R.Norris (1997). Markov Chains. A classic and widely used textbook, known for its clear explanations and solid theoretical foundation. Still highly relevant today.

• T.Konstantopoulos (2009). Markov Chains and Random Walks. A solid lectures note.

• P.Brémaud (2017). Discrete Probability Models and Methods: Probability on Graphs and Trees, Markov Chains and Random Fields, Entropy and Coding. A modern perspective on some aspects of Markov Chains, with a gentle introduction.

• R.Douc, É.Moulines, P.Soulier (2018). Markov Chains: Theory and Applications. A solid advanced theoretical foundation.

• D.A.Levin, Y.Peres (2017). Markov Chains and Mixing Times. A highly regarded resource, particularly for its in-depth coverage of mixing times, a crucial concept for understanding the convergence of Markov chains.

• N.Privault (2018). Markov Chains: Examples and Applications. A good collection of theory, examples and case studies to illustrate the practical utility of Markov chains across various domains.

• Б.В.Гнеденко (1988). Курс теории вероятностей. A classic, although dated, book in Russian.

• М.Я.Кельберт, Ю.М.Сухов (2001). Вероятность и статистика в примерах и задачах: Марковские цепи как отправная точка теории случайных процессов и их приложения. An older book, in Russian, with exercises.

Lectures notes

Lectures notes are available on the sidebar, in English and Russian.

Exercises

• Exercises are integrated in the lectures (some in the text, some at the end of chapters). There are many exercises in there, some solved, some not. There are more exercises than we have time to see during the lectures, please take your time to try to solve as many as you can. Feel free to ask for help or solutions.

Assignments

• First assignment, due on October 24th.
• Second assignment, due on December 18th.

Midterm

• An example with solutions.
• A midterm control took place on October 30th.
• A retake of the midterm.

Grading

The grade is defined by the following values:

• K: One major control, on October 30th, graded in \([0,10]\). You can retake this test on December 20th (date to be confirmed) if you could not participate or something went wrong.
• L1: First assignment due on October 15th, graded in \([0,10]\).
• L2: Second assignment due on December 18th, graded in \([0,10]\).
• B: Bonus for active participation, graded in \(\{0,1,2\}\).
• M: Minimal test graded in \(\{0,1\}\). (not compulsory for all students, see below).
• U: Oral exam, graded in \([-2,11]\). \(U> 10\) and \(U<0\) should be considered exceptional. (not compulsory for all students, see below).
• I: The final grade you will receive for the class, graded in \(\{4,5,6,7,8,9,10\}\).

The semester grade is \(S=K/2+(L1+L2)/4+B\).

1. If \(S< 3.5\) (after the \(K\) retake), you need to repass the exam in January.
2. If \(S \in [3.5,5.0)\), you need to pass the minimal test. If \(M=1\), then \(I=\lfloor S+0.5 \rfloor\).
3. If \(S\ge 10.5\) and \(B=2\), then \(I=10\).
4. In all the other cases, you may take the oral exam (not taking the oral exam means \(U=0\)) and the final grade is \(\min(10, \lfloor 0.65*S+0.35*U +0.5 \rfloor)\).

Topics for the oral exam

This is the list of subjects to prepare. You can skip the exercises in the lecture notes for the oral exam (even if some of them may help you to understand the theory).

Basic subjects

These are considered basic subjects, and you are supposed to know them to pass the exam.

• Chapter 1: Definitions, Markov Operators, Markov chains: Notation.
• Chapter 2: Entire Chapter 2.
• Chapter 3: Entire Chapter 3, except the last “Abstraction” section.
• Chapter 4: Entire Chapter 4.
• Chapter 5: Entire Chapter 5, except the last “Abstraction” section. There is a graphical resume of the main connection between recurrence and invariant measure, you are supposed to understand and prove the implications there. Notice that Chapter 5 includes and generalizes a good part of Chapter 3 (and includes proof of uniqueness). So this includes Chapter 3, but the notation of Chapter 3 is still useful.
• Chapter 6: Entire Chapter 6, except the last “Abstraction” section.

Additional Topics

These are considered more advanced subjects. You are supposed to know them to get a high grade at the exam. Students of the second year of bachelors, can consider Chapter 7.1 and 7.3 as optional.

• Chapter 7.1: Entire Chapter 7.1.
• Chapter 7.2: Only the section Definitions and Results.
• Chapter 7.3: Entire Chapter 7.3.
• Chapter 7.4: Only the sections Metropolis-Hastings dynamics and Perfect Simulations.

Website navigation

If you are having troubles with the html website, you can download the pdf version (link on the sidebar) of each page containing Mathematics. On the top right you have a search function that allows searching for math symbols code (in latex), and a theme-switching button. Video playback and download speed is optimized for relatively recent browsers (>2022). Some pages contain interactive shinylive elements, which may take some time to load (if you cleaned your browser history since your last shinylive page).