Descriptif
Prerequisites: MAA203
MAA305 presents the basic theory of discrete Markov chains. It starts by introducing the Markov property and then moves on to develop fundamental tools such as transition matrices, recurrence classes and stopping times. With these tools at hand, the strong Markov property is proven and applied to the study of hitting probabilities. In the second part of the course, we introduce the notion of stationary distribution and prove some basic existence and uniqueness results. Finally, the long time behavior of Markov chains is investigated by proving the ergodic Theorem and exponential convergence under Doblin's condition. The course is concluded by surveying some stochastic algorithm whose implementation relies on the construction of an appropriate Markov Chain, such as the Metropolis-Hastings algorithm.
Diplôme(s) concerné(s)
Parcours de rattachement
Format des notes
Numérique sur 20Littérale/grade américainPour les étudiants du diplôme Bachelor of Science de l'Ecole polytechnique
Le rattrapage est autorisé (Note de rattrapage conservée écrêtée à une note seuil de 10)- Crédits ECTS acquis : 3 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Programme détaillé
This course is an introduction to the theory of discrete time Markov chains.
Structure of the course:
Lecture 1: Discrete time Markov chains: Definitions examples and basic properties
Lecture 2: Stopping times and strong Markov property
Lecture 3: Recurrence classes and invariant distributions part I
Lecture 4: Invariant distributions part II and Birkhoff's Ergodic Theorem
Lecture 5: Exponential ergodicity: Doeblin's Theorem
Lecture 6: Stochastic algorithms: Metropolis-Hastings and stochastic gradient descent
Course material
- Lecture notes will be provided every week
- Courses 1-4 largely follow Capter I in the book "Markov Chains" by James Norris, Cambridge University Press, 1998.
The maximum rule will be applied
Final grade = Max((0.5 * final exam grade + 0.5 * coursework grade), final exam grade)
Coursework evaluation
The coursework evaluation consists of two written tests of 20 mins and of an homework assignment. The coursework grade is composed adding together the tests grades with the assignment grade.
- First test: during third tutorial, covering the material of the first two lectures. The test grade is a number ranging from 1 to 7.
- Second test: during the fifth tutorial, covering the material of the first four lectures. The test grade is a number ranging from 1 to 7.
- The homework assignment will be handed out on December 3 and has to be turned in by December 12 at 1PM. Late submissions will have consequences on the grade. The assignment grade is a number ranging from 1 to 7.
Final exam
The final exam consists of a 2 hours long written test consisting of three or four exercises and it is given a numerical grade ranging from 0 to 20.
The instructor keeps the possibility to modify these rules after the beginning of the course according to the pedagogical needs.
