Stage Liesse 2017-4

Texte

STAGE 4 (27-28 avril)

CHAINES DE MARKOV ET APPLICATIONS : MODELISATION DE FILES D’ATTENTE ET SIMULATION DE PHENOMENES ALEATOIRES

Pré-requis : notions de probabilités et de programmation avec Python

Mots-clés : Probabilités et statistiques, méthodes de Monte-Carlo, MCMC, processus aléatoires, simulation informatique, Python.

Présentation

L'objectif de ces deux jours de formation est de proposer une introduction aux chaînes de Markov à temps discret et à temps continu et à leur application à l'étude des phénomènes de files d'attente et à la simulation des phénomènes aléatoires.
Les cours et le travail sur les implémentations seront imbriqués tout au long des deux jours de stage.

Programme

Probabilités et processus stochastiques

•    Rappels de probabilité : loi exponentielle, processus de Poisson, formule de Bayes
•    Chaînes de Markov à temps discret (et états discrets): propriété de Markov faible, diagramme de transition d'états, matrice de transition, équations d'équilibrage de charge et distribution stationnaire
•    Chaînes de Markov à temps continu (et états discrets):  définition, diagramme de transition d'état, générateur infinitésimal, équations d'équilibrage de charge et distribution stationnaire
•    Chaînes de Markov à temps discret et état continu : noyau de transition, caractérisation de la distribution stationnaire
•    Les chaînes de Markov cachées ou fonctions aléatoires d'une chaîne de Markov

Théorie des files d'attente (markoviennes)

  • Caractérisation des arrivées, des départs
  • Nombre de serveurs, buffer d'attente
  • Notation de Kendall
  • Un exemple simple, la file M/M/1 : caractérisation, distribution stationnaire, performances moyennes (délai, taux d'utilisation du serveur)
  • Une file multi-serveurs avec blocage, la file M/M/C/C : caractérisation, distribution stationnaire, probabilité de blocage (formule d'Erlang-B)

Simulation de phénomènes aléatoires et méthodes MCMC (Monte Carlo par Chaînes de Markov)

  • Rappels sur les théorèmes limites : loi forte des grands nombres, théorème Central Limite
  • Estimation de probabilités par la Méthode de Monte Carlo
  • Méthodes directes de simulation de variables aléatoires : inversion de la fonction de répartition, algorithme de Box Müller
  • Algorithme d'Acceptation-Rejet
  • Algorithmes de Hastings Metropolis et du Recuit Simulé
  • Algorithme d'échantillonnage de Gibbs

Mise en œuvre : programmation avec Python

  • Présentation l'environnement de travail et de quelques librairies scientifiques Python (Numpy, Scipy, Matplotlib, Sympy, Mayavi)
  • Simulation d'une chaîne de Markov à temps discret, simulation d'une chaîne de Markov cachée
  • Simulation de la file M/M/1, évaluation empirique de la stabilité et des performances moyennes
  • Estimation de la valeur de la constante Pi par Monte Carlo
  • Simulation du modèle d'Ising par échantillonnage de Gibbs
  • Optimisation d'une fonction par recuit simulé

Compléments : MOOC “Understanding Queues” de l'Institut Mines-Télécom sur EDX, première session massive en mai 2017.

> Retour au sommaire Formations Liesse 2017