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.