v1.17.9 (1335)

Cours scientifique - PRB201 : Chaînes de Markov

Domaine > Mathématiques et leurs applications.

Descriptif

La théorie des chaînes de Markov fournit un cadre mathématique rigoureux pour décrire la classe d'évolutions aléatoires pour lesquelles (la loi) du futur de la chaîne ne dépend que de son état présent. 

Si on raisonne à temps discret et à espace d’état finis, une telle chaîne est caractérisée par la donnée d’une matrice stochastique, et on montre grâce aux outils de l’algèbre linéaire que, sous des conditions peu restrictives, on a existence et unicité d’une mesure invariante vers laquelle la loi de la chaîne converge en temps long.

Hormis cette notion de loi limite, on s’intéressera aussi aux probabilités et aux temps d’atteinte de sous-ensembles de l’espace d’états. Dans le cas de chaînes dites réversibles, il existe une connection riche avec la théorie des réseaux électriques, qui permet de ramener ces questions à des calculs de résistances équivalentes.

Dans un article de l'American Mathematical Monthly de 1989, Herbert Wilf a décrit sa surprise en constatant le temps (long!) mis par une marche aléatoire pour visiter chaque pixel de son écran d’ordinateur. Ce temps est le temps de couverture du tore de dimension 2, jolie application de la théorie des chaines de Markov qui sera étudiée à la fin du cours si le temps le permet.

Les pré-requis pour les étudiants sont les suivants: une bonne maîtrise du cours de probabilités de première année et de l’algèbre linéaire de classe préparatoire. 

Référence: Le cours s'appuiera sur (un sous-ensemble de) l'ouvrage Markov Chains and Mixing Times par Levin, Peres et Wilmer, seconde édition, dont plusieurs exemplaires papier sont disponibles à la bibliothèque.

Remarque: ce cours compte pour 3 ECTs pour l'obtention du M1-Mathématiques Appliquées”

Objectifs pédagogiques

Être capable, grâce à la connaissance des principaux éléments de la théorie des chaînes de Markov :
  • d’analyser ce type de modèle (discrets en temps et en espace);
  • d’apporter des résultats qualitatifs et quantitatifs, ces derniers de façon exacte ou approchée.

nombre d'heure en présentiel

21

nombre de blocs

7

Volume horaire par type d'activité pédagogique : types d'activité

  • Petite classe : 12
  • Contrôle : 3
  • Cours magistral : 6

effectifs minimal / maximal

10/90

Diplôme(s) concerné(s)

Parcours de rattachement

Pour les étudiants du diplôme Master 1 Mathématiques et Applications - site Orsay

MA101

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole nationale supérieure de techniques avancées

Avoir suivi le cours MA101 en 1ère année.

 

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Master 1 Mathématiques et Applications - site Orsay

Vos modalités d'acquisition :

F=note finale, TD=Travaux dirigés, E=Examen final

Session 1 : F=0,5TD+0,5E  - Session 2 : F=1E

Le rattrapage est autorisé (Note de rattrapage conservée)
  • le rattrapage est obligatoire si :
    Note initiale < 7
  • le rattrapage peut être demandé par l'étudiant si :
    7 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 3 ECTS

Le coefficient de l'UE est : 3

La note obtenue rentre dans le calcul de votre GPA.

Pour les étudiants du diplôme Master 1 Mathématiques et Applications - site Palaiseau

Vos modalités d'acquisition :

F=note finale, TD=Travaux dirigés, E=Examen final

Session 1 : F=1E - Session 2 : F=1E

Le rattrapage est autorisé (Note de rattrapage conservée)
  • le rattrapage est obligatoire si :
    Note initiale < 7
  • le rattrapage peut être demandé par l'étudiant si :
    7 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 3 ECTS

Le coefficient de l'UE est : 3

La note obtenue rentre dans le calcul de votre GPA.

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole nationale supérieure de techniques avancées

Vos modalités d'acquisition :

Examen écrit.

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2 ECTS
  • Scientifique acquis : 2

Le coefficient de l'UE est : 2

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

Programme détaillé

  1. Amphi + TD
  2. Amphi + TD
  3. Amphi + TD
  4. Amphi + TD
  5. Amphi + TD
  6. Amphi + TD
  7. Examen écrit.

Mots clés

Chaînes de Markov

Méthodes pédagogiques

"Markov Chains and Mixing Times" par Levin, Peres et Wilmer.
Veuillez patienter