Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Yongwe Jean-Luc Travail d’Initiative Personnel Encadré : Chaines de Markov et

1 Yongwe Jean-Luc Travail d’Initiative Personnel Encadré : Chaines de Markov et protocole de gestion des communications radios par satellite relais. (Système ALOHA) (Sous la tutelle de Madame Anne Perrut) Semestre d’Automne 2011 2 Table des matières I. Introduction……………………………………………………………………………………………………………...3 Loi binomiale…………………………………………………………………………………………………………….3 Loi de Poisson ………………………………………………………………………………………………………….4 Probabilité conditionnelle ……………………………………………………………………………………….4 Loi géométrique………………………………………………………………………………………………………5 Formule de probabilité totale ou formule de bayes………………………………………………..5 II. Chaîne de Markov…………………………………………………………………………………………………6 III. Application des chaines de Markov………………………………………………………………………14 3 I. Introduction Avant de commencer à expliquer ce que sont les chaines de Markov, nous allons introduire des outils tels que la loi binomiale et la loi de Poisson, mais aussi des notions telles que probabilité conditionnelle, loi géométrique et la formule des probabilités totales seront introduites pour une meilleure compréhension ; et nous donnerons en fin du document un exemple d’application des chaines de Markov avec le système ALOHA. La loi binomiale Une épreuve de Bernoulli est une expérience où la réussite et l’échec sont les seules issues possibles. Considérons une expérience aléatoire (c’est-à-dire une expérience dont on ne peut prévoir le résultat) à deux issues possibles ; notons la probabilité de réussite et la probabilité d’échec. Répétons fois cette épreuve de Bernoulli où les réalisations sont indépendants les unes des autres. Posons une variable aléatoire comme étant égale au nombre de succès ; on dira alors que suit la loi binomiale de paramètres et 1. Définition Soit , et une variable aléatoire. On dit que suit la loi binomiale de paramètres et , noté B ( ) lorsque : - Où Exemple de calcul utilisant la loi binomiale (simulation sous R) Considérons un texte contenant 20000 mots et dans lequel chaque mot à une probabilité de 1/10000 d’être mal écrit. Selon la loi binomiale, on aura alors une probabilité de trouver 2 mots comportant des fautes dans ce texte qui s’élèvera à : > dbinom (2, 20000,1/10000) [1] 0.2706841 4 Loi de Poisson La loi de Poisson s’utilise lorsqu’on étudie un phénomène rare dans des conditions spécifiques. Par exemple le nombre de fautes de frappes d’un cours de mathématiques (évènement extrêmement rare) 1. Définitions et propriétés Soit un réel strictement positif et une variable aléatoire. On dit que suit la loi de Poisson de paramètre et on note lorsque : En fait la loi de Poisson est un cas limite de la loi binomiale lorsque Où . (D’où l’équivalence entre la loi binomiale et la loi de Poisson pour des nombres très grand) Exemple de calcul utilisant la loi de Poisson (simulation sous R) En considérant le même exemple que plus haut mais cette fois le calcul étant fait selon la loi de Poisson on obtient : > dpois(2,2) [1] 0.2706706 Il est visible que dpois(2,2) ~dbinom(2,20000,1/10000) Probabilité conditionnelle Soit , A, , un espace de probabilité et un événement de probabilité strictement positif. La probabilité conditionnelle de sachant (ou par rapport à ) est définie conditionnellement par la formule : « Probabilité de » ou (« probabilité de est réalisé»). On appellera probabilité conditionnelle l’application =0 - 5 C’est là une notion très intéressante lors de l’étude de phénomènes se déroulant dans le temps et faisant intervenir le hasard à chaque étape. Loi géométrique Etant donnée une épreuve de Bernoulli dont la probabilité de réussite est et d’échec et qu’on renouvelle jusqu’à la première réussite, nous noterons la variable aléatoire donnant le rang de cette réussite. Les valeurs de sont les entiers 1, 2,3…. La probabilité que est alors pour Formule de probabilités totales ou formule de Bayes Soit { une partition de ( en événements tels que . Alors pour tout événement : Si on se ramène à un exemple concret cela donne : Soit un panier de 3 boules rouges et 4 boules vertes. Nommons A l’événement « je pioche une boule rouge » et B « je repioche une boule rouge » sans remise de la précédente, alors l’événement de piocher une boule rouge au bout des deux tirages devient : (Où est la probabilité de l’événement « tiré une boule non rouge » autrement dit une boule verte) , Donc = = La probabilité de « j’ai tiré une boule rouge au bout des deux tirages » est de 6 II. Chaine de Markov De façon intuitive, une chaine de Markov se définit classiquement comme étant une suite de variables pour laquelle la meilleure prédiction que l’on puisse faire à l’étape est la même lorsque l’on se limite à la connaissance de la valeur à l’étape que si l’on connaissait toutes les valeurs aux étapes précédentes. 1. Définition Soit E un ensemble fini d’entiers naturels, et P . Une chaine de Markov homogène (mécanisme de transition invariant au cours du temps) à valeurs dans E est une suite de variables aléatoires définies sur un espace de probabilité à valeurs dans E et qui a la propriété suivante : Soit une suite de variables aléatoires ; quel que soit n, Autrement dit pour tout entier n et pour tout (n+2)-uplet de points de E. Il est remarquable de voir que les nombres sont représentables par une matrice carrée, appelé «matrice de transition »de la chaine. De fait l’étude d’une chaine de Markov se ramène alors parfois à un problème d’algèbre linéaire. 2. Graphe d’une chaine de Markov La matrice de transition d’une de Markov peut être représentée par un graphe orienté (i.e. les arcs entre les sommets ont un sens) dont les sommets sont les états de la chaine. Les arcs relient les sommets associés aux états et si la probabilité de transition de à est positive c’est-à-dire . Le graphe est appelé « graphe représentatif » ou « graphe de transition », de la chaine de Markov. 7 Exemple : Quelqu’un qui visite un musée en partant de la pièce centrale, en se déplaçant au hasard. (Schématisation de la situation) (Graphe représentatif) 1/3 1/3 1/3 1/4 1/3 1/4 1/3 1/3 1/3 1/3 1/3 1/4 1/4 1/3 1/3 1 1 1 2 4 3 5 4 2 5 3 1 8 La matrice de transition se transcrit alors : (utilisation du Logiciel R) > vec1=c(0,1/4,1/4,1/4,1/4) > vec2=c(1/3,0,1/3,1/3,0) > vec3=c(1/3,1/3,0,0,1/3) > vec4=c(1/3,1/3,0,0,1/3) > vec5=c(1/3,0,1/3,1/3,0) > a=matrix(c(vec1,vec2,vec3,vec4,vec5),nrow=5,byrow=T) > a [,1] [,2] [,3] [,4] [,5] [1,] 0.0000000 0.2500000 0.2500000 0.2500000 0.2500000 [2,] 0.3333333 0.0000000 0.3333333 0.3333333 0.0000000 [3,] 0.3333333 0.3333333 0.0000000 0.0000000 0.3333333 [4,] 0.3333333 0.3333333 0.0000000 0.0000000 0.3333333 [5,] 0.3333333 0.0000000 0.3333333 0.3333333 0.0000000 On appelle matrice Markovienne une matrice carrée dont chaque élément est un réel compris entre 0 et 1 et dont la somme des éléments de chaque ligne vaut 1. 3. Probabilité de transition et matrices de transition Pour une chaine de Markov homogène. Soit S un ensemble fini S d’entiers naturels et ( est un espace d’états). Traduction : la probabilité dans la matrice de transition , est égale à la probabilité conditionnelle que le système se retrouve dans l’état à l’étape suivante sachant qu’il se trouve actuellement dans l’état . Si la chaine possède états, les probabilités précédentes peuvent être rangées dans une matrice de transition de taille dont les lignes et colonnes sont indexés par les éléments de 9 Propriété : Soit une matrice markovienne de taille , alors toute puissance , de est une matrice Markovienne. Preuve : Le résultat est vrai pour , On a = , := et . Pour pour tout et Pour tout 4. Classification des états 4.1. Classification et réduction des graphes. Soit une matrice de transition d’une chaine de Markov et le graphe représentatif de . L’état est accessible depuis s’il existe un chemin de . Propriété : L’état est accessible de l’état si et seulement si il existe Les états et communiquent s’ils sont accessibles l’un à partir de l’autre. Propriété : Les états et communiquent (c’est-à –dire qu’il est possible de passer de l’état à l’état ) si et seulement si il existe et tels que et . La relation communiquer (↔) est une relation d’équivalence. 10 { La relation communiquent est une relation d’équivalence dont les classes correspondent aux composantes fortement connexes de . Les états communiquent si et seulement s’ils appartiennent à la même composante fortement connexe. On appelle « classes de la chaine » les classes d’équivalence induites par la relation (↔) sur l’espace de probabilités. 4.2. Classes -Une classe est récurrente si elle correspond à un sommet sans successeur dans le graphe des composantes connexes. Les états d’une classe récurrente sont récurrents. -Les états d’une classe transitoire sont transitoires. -Une classe récurrente composée d’un seul état est absorbante. Propriété : L’état est dit absorbant si et seulement ) .Une chaine de Markov est dite irréductible si elle ne compte qu’une seule classe, elle est dite réductible dans le cas contraire. Propriété : -Une chaine de Markov est irréductible si et seulement si son graphe représentatif est fortement connexe : tous ses états communiquent. 4.3. Période La période de l'état d'une chaine de Markov est égale au plus grand commun diviseur de tous les pour lesquels . L'état est périodique lorsque et apériodique lorsque Propriété : Si >0 alors uploads/Geographie/ jean-luc-yongwe.pdf