Prep@s.org

Le site de l'UPS pour les Classes Préparatoires aux Grandes Écoles

IMT Atlantique, site de Brest Chaines de Markov et applications : modélisation de files d’attente et simulation de phénomènes aléatoires du Jeudi 27 avril 2017 au Vendredi 28 avril 2017

Contact

Annie Gravey annie.gravey@telecom-bretagne.eu

Intervenants

Sandrine Vaton sandrine.vaton@telecom-bretagne.eu
Thierry Chonavel thierry.chonavel@telecom-bretagne.eu

INSCRIPTION

ICI

IMT Atlantique, Bretagne, Pays de Loire, site de Brest
Dates : 27 et 28/04/2017
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 oeuvre : 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.