logo
v2.11.0 (5725)

Cours scientifiques - APM_3S005_EP : Probability: Stochastic Processes

Domaine > Mathématiques appliquées.

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.

Pour les étudiants du diplôme Bachelor of Science de l'Ecole polytechnique

Vous devez avoir validé l'équation suivante : UE APM_2F010_EP

Format des notes

Numérique sur 20

Littérale/grade américain

Pour les étudiants du diplôme Programmes d'échange internationaux

Pour les étudiants du diplôme Bachelor of Science de l'Ecole polytechnique

Vos modalités d'acquisition :

L'examen final consiste en une épreuve écrite de 2 heures comprenant trois ou quatre exercices et est assorti d'une note numérique allant de 0 à 20.

L'instructeur se réserve la possibilité de modifier ces règles après le début du cours en fonction des performances de la classe.

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 : 4 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.

    Veuillez patienter