L3 – Probabilités – 2013-2014 Guillaume Aupy – Vincent Neiger TD n◦13 : Markov
L3 – Probabilités – 2013-2014 Guillaume Aupy – Vincent Neiger TD n◦13 : Markov Polov. Exercice 1 - Analyse (simplifiée) de l’algorithme du simplexe L’algorithme du simplexe résout le programme linéaire min Ax = b x ≥0 cx où b est de taille m, et où c et x sont de taille n > m. Les solutions x sont des points extrêmes du domaine, avec n−m composantes nulles. L’algorithme du simplexe passe d’un point extrême à un autre, meilleur en terme de la fonction objective. Il y a N = n m points extrêmes, si bien qu’on s’attend à un nombre d’itérations exponentiel. On modélise le passage de l’algorithme d’un point extrême à un autre à l’aide d’une chaîne de Markov. On suppose que si on se trouve au j-ème meilleur point, après l’itération on se trouvera à l’un des (j −1)-èmes meilleurs points de manière équiprobable. En d’autre termes, on a une matrice de transition P de taille N avec P11 = 1 et Pij = 1 i−1 pour i > 1 et 1 ≤j ≤i −1. Soit Ti le nombre d’itérations pour aller de l’état i à l’état 1. 1. Donner une formule liant E[Ti] et les E[Tj] pour j < i 2. Calculer E[TN]. Donner une estimation de E[TN]. 3. Donner une estimation de E[TN], et en déduire que pour une certaine constante c, on a pour N suffisamment grand P[TN ⩾2 log(N)] ⩽1 2 + c log(N). 4. Calculer V ar[TN], en écrivant TN comme une somme de variables indépendantes (il faut trouver les variables et montrer l’indépendance). 5. Donner une estimation de V ar[TN] et en déduire que pour une certaine constante c′, on a pour N suffisamment grand P[TN ⩾2 log(N)] ⩽ 1 log(N) + c′ log(N)2 . 6. Que peut-on en déduire pour l’algorithme du simplexe ? Exercice 2 - Installateur d’ascenseurs Un installateur d’ascenseurs dispose d’une seule équipe dont tous les membres travaillent sur le même chantier. Les demandes d’installations des clients qui lui parviennent peuvent être réparties en 2 classes : — travaux de moyenne importance, durant une semaine (désignés par A). 1 L3 – Probabilités – 2013-2014 Guillaume Aupy – Vincent Neiger — travaux plus importants durant 2 semaines (désignés par B). L’installateur ne reçoit pas de demandes de travaux qui n’entrent pas dans cette classification. Il n’y a pas de liste d’attente. Les demandes d’installation parviennent à l’entrepreneur au début de chaque semaine. Une observation statistique a montré que les probabilités pour recevoir un lundi donné, au moins une demande de travaux du type A, ou au moins une demande de travaux du type B valent respectivement p = 0,5 et q = 0,6. Ces probabilités sont indépendantes. Certaines semaines, des travaux sont refusés, l’équipe étant déjà occupée sur une installation de type B : dans ce cas le client s’adresse à un concurrent. D’autres semaines l’équipe reste inactive faute de demande d’installation. Lorsque l’installateur reçoit simultanément 2 demandes : une du type A et une du type B, il donne suite à celle du type B. L’installation du type A procure un bénéfice de 5000F, celle du type B 12000F, et l’inactivité de l’équipe pendant une semaine engendre une perte de 2500F 2.1 On désire représenter par une chaîne de Markov l’évolution de l’activité de l’équipe d’une semaine sur l’autre. Quels sont les 4 états ? Dessinez le graphe associé à cette chaîne et donnez sa matrice de transition. 2.2 En supposant que l’entreprise fonctionne depuis plusieurs semaines, trouver la probabilité de chacun des états, justifier la validité de ce calcul. 2.3 En déduire l’espérance mathématique du gain relatif a une semaine de fonctionnement. Exercice 3 - Temps de séjour dans un état On considère la chaîne de Markov à deux états : 1 −p p 0 1 Soit T le temps aléatoire pendant lequel le processus séjourne dans l’état 0. 3.1 Montrez que ce temps T est une v.a. distribuée selon la loi géométrique 3.2 Calculer le temps moyen de séjour dans l’état 0. On étudie le fonctionnement d’une imprimante. Celle-ci peut être dans 3 états distincts : — e1 attente d’un caractère à imprimer, — e2 impression d’un caractère, — e3 interruption après avoir reçu un caractère de contrôle. Lorsque l’imprimante est en attente, elle reçoit un caractère à imprimer avec la probabilité 0, 80. Lorsqu’elle est en impression elle reçoit : — un caractère normal avec la probabilité 0, 95 (caractère courant du fichier à imprimer) ; — un caractère de fin de fichier avec la probabilité 0, 04 (l’imprimante retourne dans l’état d’attente) ; — un caractère d’interruption avec la probabilité 0, 01 (l’imprimante passe alors dans e3). Lorsque l’imprimante est dans l’état 3, elle retourne dans l’état d’attente avec la probabilité 0, 3 sinon elle reste dans l’état e3. 3.3 Montrez que ce système se modélise par un chaîne de Markov à 3 états. 3.4 Dessinez le graphe associé à cette chaîne et donnez sa matrice de transition. 3.5 Quel est le temps moyen d’une interruption ? 2 L3 – Probabilités – 2013-2014 Guillaume Aupy – Vincent Neiger 3.6 Écrivez les équations d’équilibre et montrez que cette chaîne est ergodique. Calculez les probabilités stationnaires associées. 3.7 En régime stationnaire, quel est le taux d’utilisation de l’imprimante ? Exercice 4 - CNS d’existence de distribution invariante L’objet de cet exercice est de donner une condition nécessaire et suffisante d’existence d’une distribution invariante pour les chaînes de Markov à temps discret et espace d’états fini ou dénombrable. On considère (Xt)t∈N une chaîne de Markov sur E, homogène de matrice de transition P = (pij). Notation : soient i, j ∈E, t ∈N, — Proba d’aller de i en j en t pas : pij(t) = Pi(Xt = j). — Temps de retour en j : Tj = inf{t ≥0|Xt = j}, = +∞si ∀t, Xt ̸= j. — Proba de visiter j après être parti de i : fij = Pi(Tj < +∞). — Nombre de visites en i (ormis le départ) : Ni = P+∞ t=1 1Xt=i. Définitions : soit i ∈E, — i est transitoire si Pi(Ti = +∞) > 0, — i est récurrent si Pi(Ti < +∞) = 1, — i est récurrent nul s’il est récurrent et Ei(Ti) = +∞, — i est récurrent positif s’il est récurrent et Ei(Ti) < +∞. Une chaîne de Markov est dite récurrente (resp. récurrente positive) si tous les états sont récur- rents (resp. récurrents positifs). 4.1 Pour tout i, j ∈E et r ∈N, exprimer de Pi(Nj = r) en fonction des probabilités fkℓ. 4.2 Démontrer les équivalences suivantes : i récurrent ⇐ ⇒fii = 1 ⇐ ⇒Pi(Ni = +∞) = 1 ⇐ ⇒Ei(Ni) = +∞ i transitoire ⇐ ⇒fii < 1 ⇐ ⇒Pi(Ni < +∞) = 1 ⇐ ⇒Ei(Ni) < +∞ 4.3 En déduire le "critère de la matrice de potentiel" : i récurrent si et seulement si P+∞ t=1 pii(t) = +∞. 4.4 Montrer que deux états qui communiquent, càd qui sont dans une même composante fortement connexe, sont soit récurrents tous les deux, soit transitoires tous les deux. Fixons maintenant un état arbitraire 0 ∈E, soit T0 le temps de retour en 0. Pour tout état i ∈E, posons Zi = P+∞ t=1 1Xt=i1t≤T0 le nombre de visites en i entre le temps 0 exclu et le temps T0 inclus. On note alors xi = E0(Zi) le nombre moyen de visites en i entre deux passages en 0. 4.5 Montrer que si la chaîne de Markov est irréductible et récurrente, x = (xi)i∈E est une mesure invariante telle que ∀i ∈E, 0 < xi < +∞. 4.6 Montrer que si la chaîne de Markov est irréductible et récurrente, l’état 0 est récurrent positif si et seulement si P i∈E xi < +∞. En déduire que dans ce cas, il existe une distribution invariante. 3 uploads/Management/ 2014-proba-td13.pdf
Documents similaires
-
17
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Aoû 23, 2021
- Catégorie Management
- Langue French
- Taille du fichier 0.1620MB