v2.11.0 (5308)

# Cours scientifique - MAA305 : Probability: Stochastic Processes

## 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.

Numérique sur 20

## Pour 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)
L'UE est acquise si Note finale >= 9
• 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

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. 