Module 6: Chaînes de Markov à temps discret PDF

Module 6: Chaı̂nes de Markov à temps discret 1 Définition Un processus stochastique est dit markovien (d’ordre 1) si l’évolution future du processus ne dépend que de sa valeur actuelle et non de ses valeurs passées. En d’autres termes, l’histoire passée du processus est entièrement résum...

Module 6: Chaı̂nes de Markov à temps discret 1 Définition Un processus stochastique est dit markovien (d’ordre 1) si l’évolution future du processus ne dépend que de sa valeur actuelle et non de ses valeurs passées. En d’autres termes, l’histoire passée du processus est entièrement résumée dans sa valeur actuelle. Plus précisément, si X(t) est à valeurs discrètes, il est markovien et est alors appelé chaı̂ne de Markov si et seulement si pour toute suite d’instants t1 < t2 <... < tk < tk+1 et toute suite de valeurs x1 , x2... , xk , xk+1 P (X(tk+1 ) = xk+1 | X(t1 ) = x1 , X(t2 ) = x2 ,... , X(tk ) = xk ) = P (X(tk+1 ) = xk+1 | X(tk ) = xk ). (1) L’ensemble des valeurs que X(t) peut prendre est appelé espace d’état. Pour une chaı̂ne de Markov, il est donc discret (fini ou non). Selon que le temps t est lui-même discret ou continu, on parlera de chaı̂ne de Markov à temps discret ou de chaı̂ne de Markov à temps continu. Si l’espace d’état est continu, X(t) est un processus de Markov si et seulement si pour toute suite d’instants t1 < t2 <... < tk < tk+1 P (xk+1 ≤ X(tk+1 ) < xk+1 + ∆xk+1 | X(t1 ) = x1 , X(t2 ) = x2 ,... , X(tk ) = xk ) = P (xk+1 ≤ X(tk+1 ) < xk+1 + ∆xk+1 | X(tk ) = xk ) ou encore fX(tk+1 ) | X(t1 )X(t2 )...X(tk ) (xk+1 | X(t1 ) = x1 , X(t2 ) = x2 ,... , X(tk ) = xk ) = (2) fX(tk+1 ) | X(tk ) (xk+1 | X(tk ) = xk ). A nouveau, selon que le temps t est discret ou continu, on parlera de processus de Markov à temps discret ou de processus de Markov à temps continu. Nous aborderons les chaı̂nes de Markov à temps continu dans le module suivant. Pour l’instant, nous rappelons seulement les concepts de chaı̂ne de Markov à temps discret. 119 2 Chaı̂nes de Markov à temps discret L’espace d’état, noté S, peut être soit fini, soit infini, mais dénombrable (par exemple N ou Z). 2.1 Probabilités d’état et de transition La probabilité que X(n) soit dans l’état i ∈ S est une des probabilités d’état πi (n) = P (X(n) = i), dont la somme vaut évidemment l’unité X πi (n) = 1, (3) i∈S tandis que les probabilités pij (n) = P (X(n+1) = j | X(n) = i) sont les probabilités de transition à une étape de l’état i à l’état j au temps n, satisfaisant à la relation X pij (n) = 1. (4) j∈S Dans la suite, on supposera qu’elles ne dépendent pas du temps n, la chaı̂ne est dite homogène. Ces probabilités de transition sont généralement écrites sous forme d’une matrice de transition (ou matrice stochastique)   p00 p01... poi...  p10 p11... p1i...    ........  P = ....   (5)  pi0 pi1... pii...   ............ dont la somme des éléments d’une même ligne valent l’unité à cause de (4). Les probabilités de transition à 2 étapes de l’état i à l’état j sont données par (2) pij = P (X(n + 2) = j | X(n) = i) X = P (X(n + 2) = j | X(n + 1) = k, X(n) = i)P (X(n + 1) = k | X(n) = i) k∈S X = P (X(n + 2) = j | X(n + 1) = k)P (X(n + 1) = k | X(n) = i) k∈S X = pkj pik , k∈S ce qui s’écrit sous forme matricielle P (2) = P P = P 2 120 On peut étendre ce résultat pour obtenir les probabilités de transition à m étapes de l’état i à l’état j par les équations de Chapman-Kolmogorov (m) pij = P (X(n + m) = j | X(n) = i) X = P (X(n + m) = j | X(n + m − l) = k, X(n) = i)P (X(n + m − l) = k | X(n) = i) k∈S X = P (X(n + m) = j | X(n + m − l) = k)P (X(n + m − l) = k | X(n) = i) k∈S (m−l) (l) X = pik pkj. k∈S En particulier pour l = 1, (m) (m−1) X pij = pkj pik k∈S ou encore sous forme matricielle P (m) = P (m−1) P = · · · = P m. (0) Notons que pii = 1. Les probabilités d’état sont également facilement calculables πj (n) = P (X(n) = j) X = P (X(n) = j | X(n − 1) = i)P (X(n − 1) = i) i∈S X = pij πi (n − 1) i∈S Si π(n) = [π0 (n) π1 (n) π2 (n)...], cette relation s’écrit sous forme matricielle π(n) = π(n − 1)P = · · · = π(0)P n. (6) On dit qu’une distribution de probabilité π est une distribution invariante de la chaı̂ne de Markov ssi π = πP (7) i.e. c’est un vecteur propre (à gauche) de la matrice P. Il s’en suit que si π(0) est une distribution invariante, alors π(n) = π(0) pour tout n ≥ 0. On peut même dire un peu plus. En effet, par application itérée des probabilités conditionnelles on trouve que: P(X(n) = in , X(n − 1) = in−1 ,..., X(1) = i1 , X(0) = i0 ) = πi0 (0)Pi0 ,i1 Pi1 ,i2...Pin−1 ,in (8) 121 ce qui montre au passage que la distribution initiale π(0) et la matrice de transition P définissent entièrement la loi de la chaı̂ne de Markov homogène. De la même manière: P(X(n+m) = in , X(n−1+m) = in−1 ,..., X(1+m) = i1 , X(m) = i0 ) = πi0 (m)Pi0 ,i1 Pi1 ,i2...Pin−1 ,in (9) et donc si π est invariante, les membres de gauche des équations 8 et 9 sont identiques, ce qui montre que X est stationaire au sens strict: Proposition 1 Une chaı̂ne de Markov homogène est stationaire au sens strict si et seulement si π(0) est une distribution invariante, i.e. π = πP. Notons à ce stade qu’une chaı̂ne de Markov sur un ensemble d’états fini possède au moins une probabilité invariante, mais que si l’ensemble d’états est infini il peut ne pas en exister. 2.2 Classification des états 2.2.1 Classe / chaı̂ne irréductible (m) Un état j est accessible à partir de l’état i si pij > 0 pour un certain m ∈ N0 , c’est-à-dire s’il existe une suite de transitions ayant une probabilité non nulle de passer de l’état i à l’état j. Deux états i et j communiquent s’ils sont accessibles l’un à l’autre, ce que l’on note i ↔ j. Cette relation est réflexive, symétrique et transitive (exercice 3). Elle définit donc des classes d’équivalence, qui sont l’ensemble de tous les états qui communiquent entre eux. Une chaı̂ne de Markov qui ne comporte qu’une seule classe est dite irréductible. Un état i est absorbant s’il est impossible de le quitter, c’est-à-dire si pii = 1. Un état absorbant forme donc une classe à lui tout seul. Une classe d’états est absorbante s’il est impossible de la quitter, et si ses états communiquent entre eux. 2.2.2 Etats (a)périodiques Un état i a une période d s’il ne peut être visité qu’à des instants multiples de d, c’est-à-dire (n) si pii = 0 pour chaque n qui n’est pas multiple de d, où d est le plus grand entier ayant cette propriété1. Tous les états d’une classe ont la même période. En effet, supposons que i et j communiquent, et que i soit périodique de période d. Comme i communique avec j, il existe (k) (m) k, m ∈ N0 tels que pij > 0 et pji > 0. Pour tout n ∈ N, (k+n+m) (k) (n) (m) (k) (n) (m) XX pii = pir prl pli ≥ pij pjj pji. l∈S r∈S (k+m) (k) (m) Si n = 0, cette inégalité devient pii ≥ pij pji > 0, ce qui n’est possible que si (k + m) est un multiple de d. Par conséquent, si n n’est pas un multiple de d, (k + n + m) n’est pas un multiple 1 (kd) Ou de manière équivalente, le plus petit d tel que pii > 0 pour tout k ∈ N 122  (n) (k) (m) de d non plus, et il s’ensuit que pjj doit être nul, puisque pij pji > 0. Ceci montre que j a une période multiple de d. En recommençant le même raisonnement, avec i et j intervertis, on montre que j a la même période que i. Si d = 1, l’état est dit apériodique. On appelle chaı̂ne apériodique une chaı̂ne irréductible dont tous les états sont apériodiques. 2.2.3 Etats récurrents/transitoires On désigne par Ti le temps de premier passage par l’état i: Ti = inf{n ∈ N0 : X(n) = i}. (10) Si cet ensemble est vide, on pose Ti = ∞. Le domaine de Ti est donc N0 ∪ {∞}. Si Ti est fini, le processus passera un jour ou l’autre par cet état. Par contre, si Ti est infini, cela signifie que le processus ne passera jamais par l’état i. Remarquons que pour tout m ∈ N0 P (Ti = m) = P (X(m) = i et X(n) 6= i pour tout 1 ≤ n ≤ m − 1). Soit fi la probabilité que le processus retourne après un certain temps à l’état i: fi = P (X(n) = i pour un certain n ∈ N0 | X(0) = i). (11) On a donc que X fi = P (Ti = m | X(0) = i) = P (Ti < ∞ | X(0) = i). m∈N0 Un état i est récurrent si la probabilité que le processus repasse par cet état après l’avoir quitté vaut l’unité, i.e. si fi = 1. Il est transitoire sinon, i.e. si fi < 1. (n) On peut établir qu’un état est récurrent ou transitoire directement à partir des probabilités pii en introduisant une variable aléatoire Vi , comptant le nombre de passages par l’état i. Notons par 1{X(n)=i} la fonction indicatrice de l’état i, qui vaut 1 si X(n) = i et 0 sinon (c’est donc une v.a. de Bernoulli). Alors Vi est exprimé par: ∞ X Vi = 1{X(n)=i}. (12) n=0 On calcule que ∞ X E[Vi | X(0) = i] = E[1{X(n)=i} | X(0) = i] n=0 ∞ ∞ (n) X X = P (X(n) = i | X(0) = i) = pii , (13) n=0 n=0 123 et que P (Vi < ∞ | X(0) = i) = P (∃n tel que X(n) = i et X(m) 6= i ∀m > n | X(0) = i) X∞ = P (X(n) = i et X(m) 6= i ∀m > n | X(0) = i) n=0 X∞ = P (X(m) 6= i ∀m > n | X(n) = i et X(0) = i)P (X(n) = i | X(0) = i) n=0 ∞ (n) X = P (X(m) 6= i ∀m > n | X(n) = i)pii n=0 ∞ (n) X = P (X(m) 6= i ∀m > 0 | X(0) = i)pii n=0 ∞ (n) X = (1 − fi )pii. (14) n=0 Dès lors, comme P (Vi < ∞ | X(0) = i) ≤ 1, on a que si i est transitoire, alors fi < 1 et par (14) ∞ X (n) 1 pii ≤. 1 − fi n=0 Dans le cas contraire, si i est récurrent, fi = 1 et (14) implique que P (Vi < ∞ | X(0) = i) = 0, ce qui veut dire que Vi est presque sûrement infini quand X(0) = i. Ainsi ∞ (n) X pii = E[Vi | X(0) = i] = ∞. n=0 On a donc le théorème suivant: Proposition 2 L’état i est récurrent si et seulement si ∞ (n) X pii = ∞ n=0 et transitoire si et seulement si ∞ (n) X pii < ∞. n=0 La propriété de récurrence est une propriété de classe: en effet, si i est un état récurrent, et si j communique avec i, alors j est aussi récurrent. Comme i communique avec j, il existe m, k ∈ N0 (m) (k) tels que pij > 0 et pji > 0. Pour tout n ∈ N, (k+n+m) (k) (n) (m) (k) (n) (m) XX pjj = pjr prl plj ≥ pji pii pij l∈S r∈S 124 d’où ∞ ∞ (k+n+m) (k) (m) (n) X X pjj ≥ pji pij pii = ∞, n=0 n=0 ce qui montre que j est aussi récurrent. Il s’ensuit que la propriété d’être transitoire est aussi une propriété de classe. Finalement, on fait une distinction supplémentaire entre états récurrents, lorsqu’on considère l’espérance du temps de premier retour. Si l’état i est récurrent, celle-ci s’écrit X X E[Ti | X(0) = i] = mP (Ti = m | X(0) = i) = mP (Ti = m | X(0) = i). m∈N0 ∪∞ m∈N0 Si cette espérance est finie, l’état est dit récurrent positif, sinon il est récurrent nul. On peut montrer que si X(n) est une chaı̂ne irréductible récurrente, alors tous ses états sont soit récurrents positifs, soit récurrents nuls. Si de plus son espace d’état est fini, alors tous ses états ne peuvent être que récurrents positifs. Plus précisément, on a: Proposition 3 (Espace d’Etat Fini) Soit X une chaı̂ne de Markov homogène sur un espace d’états S fini. 1. Une classe d’états est récurrente positive si et seulement si elle est absorbante 2. Une classe d’états est transitoire si et seulement si elle est non absorbante 3. Il existe au moins une classe d’états absorbante 4. Si la chaı̂ne est irréductible alors elle est récurrente positive 5. Aucun état n’est récurrent nul Une chaı̂ne de Markov homogène irréductible, apériodique et dont tous les états sont récurrents positifs est dite ergodique. (Il s’agit d’un ergodisme en distribution, pas seulement en moyenne). 2.3 Comportement asymptotique De même que la réponse d’un système déterministe linéaire et invariant dans le temps se compose d’un régime transitoire et d’un régime permanent, on peut étudier si la distribution de probabilité π(n) tend vers une distribution limite lorsque n → ∞. Une distribution de probabilité π ? est dite stationnaire (ou encore invariante) si elle satisfait à l’équation π? = π?P (15) c’est-à-dire, pour tout j ∈ S X πj? = πi? pij. (16) i∈S 125 Dans ce cas, si π(0) = π ? , (6) entraı̂ne que π(n) = π ? pour tout n ≥ 0. Le processus est donc stationnaire (au sens strict) car P (X(n + k) = ik ,... , X(n) = i0 ) = P (X(n + k) = ik |X(n + k − 1) = ik−1 )... P (X(n + 1) = i1 | X(n) = i0 )P (X(n) = i0 ) = pik−1 ik... pi0 i1 πi?0 ce qui ne dépend pas du temps initial n. Donc les probabilités sont indépendantes de l’origine de l’axe des temps, ce qui montre que le processus est stationnaire. Si une distribution limite existe, elle sera stationnaire. L’inverse n’est pourtant pas vrai. Grâce à la classification faite à la section précédente, on peut maintenant énoncer les conditions sous lesquelles une chaı̂ne de Markov à temps discret converge vers une distribution stationnaire: Théorème 1 Si X(n) est une chaı̂ne de Markov homogène ergodique alors il existe une seule distribution stationnaire donnée par (16) et (3), i.e. solution unique de X πj? = πi? pij (17) i∈S et X πi? = 1. (18) i∈S De plus, tout vecteur des probabilités d’état tend vers cette distribution stationnaire: π(n) → π ? lorsque n → ∞. Nous ne démontrons pas ce théorème (il faut utiliser la propriété forte de Markov non vue ici), mais indiquons la démarche à suivre. Si l’espace d’états est fini, le théorème peut être établi de manière ”algébrique”, en calculant la matrice P n , et en montrant qu’elle tend vers une matrice P ? dont toutes les lignes sont le vecteur π ?. Dans le cas général d’un espace d’états fini ou infini (mais dénombrable), il faut utiliser une approche astucieuse, qui consiste à ”coupler” la chaı̂ne X(n) avec une autre chaı̂ne Y (n), indépendante de X, de même matrice de transition P , et dont la distribution initiale de probabilité est la distribution invariante π ? (donc P (Y (n) = j) = πj? pour tout j ∈ S et n ∈ N). On montre alors que 1. le temps de premier passage simultané de X et Y par un état i ∈ S est presque sûrement fini, i.e. que P (T(i,i) < ∞) = 1 avec T(i,i) = inf{n ∈ N0 : X(n) = Y (n) = i}; 126  2. le processus  X(n) si n < T(i,i) Z(n) = Y (n) si n ≥ T(i,i) est une chaı̂ne de Markov de même matrice de transition P et même distribution initiale de probabilité π 0 que la chaı̂ne X, ce qui entraı̂ne en particulier que P (Z(n) = j) = P (X(n) = j) pour tout j ∈ S; 3. Pour tout j ∈ S, on a alors que |P (X(n) = j) − πj? | = | P (Z(n) = j) − P (Y (n) = j) | = | P (Z(n) = j et T(i,i) > n) + P (Z(n) = j et T(i,i) ≤ n) − P (Y (n) = j) | = | P (X(n) = j et T(i,i) > n) + P (Y (n) = j et T(i,i) ≤ n) − P (Y (n) = j) | = | P (X(n) = j et T(i,i) > n) − P (Y (n) = j et T(i,i) > n) | ≤ | P (T(i,i) > n) − 0 | = P (T(i,i) > n) et P (T(i,i) > n) → 0 si n → ∞ car P (T(i,i) < ∞) = 1. La réciproque suivante est souvent utile en pratique: Théorème 2 (Réciproque du Théorème 1) Soit X une chaı̂ne de Markov homogène irréductible (apériodique ou non). S’il existe un vecteur ligne π ∗ solution des Equations (17) et (18) alors 1. πi∗ > 0 pout tout état i, 2. la chaı̂ne est récurrente positive, 3. π ∗ est l’unique solution des Equations (17) et (18). Remarque: une chaı̂ne irréductible est soit récurrente positive, soit récurrente nulle, soit transi- toire. Le théorème dit que l’existence d’une solution aux équations qui définissent une probabilité stationaire suffit pour éliminer les deux derniers cas. Mentionnons aussi le résultat suivant pour le cas périodique. Théorème 3 (Cas périodique du Théorème 1) Si X est une chaı̂ne de Markov homogène récurrent positive périodique de période d alors il existe une seule distribution stationnaire donnée par (16) et (3), i.e. solution unique de X πj? = πi? pij (19) i∈S et X πi? = 1. (20) i∈S Pour tous états i et j, limn→∞ P(X(dn+r) = j|X(0) = i) = dπj? ou bien limn→∞ P(X(dn+k) = j|X(0) = i) = 0, selon la valeur de r ∈ {0, 1,..., d − 1}; de plus n−1 1 X lim πi (m) = πi∗ n→∞ n m=0 127 Nous mentionnons également, sans démonstration, l’important théorème suivant. Théorème 4 Si X(n) possède une distribution stationnaire unique π ? = [π0? π1?...] alors le temps moyen de retour à l’état i vaut 1 E[Ti | X(0) = i] =. (21) πi? Pour beaucoup de chaı̂nes, il est plus facile de calculer π ? à l’aide de la proposition suivante qu’en résolvant (16) directement. Proposition 4 Soit A ⊂ S un sous-ensemble des états de X(n). Si π ? est une distribution stationnaire, alors on a XX XX πi? pij = πj? pji. (22) i∈A j ∈A / i∈A j ∈A / La signification intuitive de cette proposition est que la somme des transitions de A vers l’extérieur de A doit être égale à la somme des transitions de l’extérieur de A vers A. Graphiquemnt, les sommes dans les membres de gauche et de droite de (22) parcourent respectivement les flèches sortant de A et les flèches entrant dans A. Démonstration: De (16) on a X XX πj? = πi? pij j∈A j∈A i∈S ! X X X X πj? = πi? pij + πi? pij j∈A j∈A i∈A i∈A / X X X XX πj? = πi? pij + πi? pij j∈A i∈A j∈A j∈A i∈A /   X X X XX πj? = πi? 1 − pij  + πi? pij j∈A i∈A j ∈A / j∈A i∈A / X X XX XX πj? = πi? − πi? pij + πi? pij j∈A i∈A i∈A j ∈A / j∈A i∈A / XX XX πi? pij = πi? pij i∈A j ∈A / j∈A i∈A / 2.4 Quelques chaı̂nes récurrentes classiques 2.4.1 Chaı̂ne de Markov à deux états Un modèle simple de source binaire est une chaı̂ne de Markov à deux états (l’état 0 et l’état 1: S = {0, 1} ), dont le diagramme de transition des états est représenté à la figure 1 et dont la 128 matrice de transition est   1−p p P = (23) q 1−q où 0 ≤ p, q ≤ 1 et 0 < p + q ≤ 2. Une telle chaı̂ne de Markov peut par exemple modéliser le tirage d’une pièce de monnaie à pile ou face: 0 et 1 représentent les côtés pile et face. Elle peut aussi modéliser une suite binaire dans lequel la probabilité d’apparition de chaque symbole binaire ne dépend que du précédent. Enfin elle peut modéliser un canal binaire bruité: dans ce cas, la probabilité p est la probabilité qu’un symbole 0 émis soit erroné à la réception, et 1 − p est la probabilité qu’il soit transmis correctement. De même, q représente la probabilité qu’un symbole 1 soit émis mais qu’un 0 soit erronément reçu, tandis que 1 − q est la probabilité qu’il soit transmis correctement. 1-p 1-q p 0 1 q X(n) 0 < p < 1/2 < q < 1 n X(n) 0 1/2 il y a une probabilité non nulle que le joueur ne perde pas toute sa fortune au jeu, même s’il n’arrête jamais. Par contre, si p ≤ 1/2, il perdra presque sûrement tout son avoir. Remarquons que même dans le cas ou les jeux du casino ne sont pas biaisés, le joueur perd toute sa fortune avec probabilité 1: c’est le paradoxe de la ruine du joueur. 2.6.3 Processus de branchement ou d’arborescence Les processus de branchement sont des processus Markoviens inspirés (et utilisés) par la biologie, pour modéliser la croissance de population de bactéries ou des problèmes de génétique. Ils peu- vent également modéliser la génération de particules par réaction en chaı̂ne dans des dispositifs physiques, comme l’effet d’avalanche dans la photodiode APD introduite au module précédent. 139 On considère une population d’individus capables de produire des descendants. On appelle (n+1) l’indice de la génération, et on étudie le nombre X(n) d’individus de la génération (n+1). On suppose que chaque individu i de la (n + 1)ième génération aura généré durant son existence Cin descendants, où les Cin forment une suite de v.a. i.i.d, de loi de probabilité P (Cin = k) = ck donnée pour tout k ∈ N. La première génération ne comporte qu’un seul individu (X(0) = 1), qui a C10 descendants, si bien que le nombre d’individus de la seconde génération est X(1) = C10. En continuant de la sorte, à la (n + 1)ième génération, il y aura donc X(n) = C1n−1 + C2n−1 +... + CX(n−1) n−1 individus. Ce processus est clairement une chaı̂ne de Markov, car X(n) ne dépend que de X(n − 1), et pas de X(n − 2),... , X(0). Si c0 = 0, l’état 0 ne sera jamais atteint à partir de X(0) = 1, et la population ne fera que croı̂tre. Dans la suite, nous supposerons toujours que c0 > 0. Dans ce cas, l’état 0 est absorbant et tous les autres sont transitoires, car pi0 = ci0. Dès lors tout sous-ensemble fini d’états {1, 2, 3,... , N } ne sera visité qu’un nombre (presque sûrement) fini de fois, et par conséquent, soit la population disparait entièrement, soit sa taille devient infinie. La probabilité d’extinction de la population sachant que sa taille initiale est i est hi0 = P (X(n) = 0 pour un certain n ∈ N | X(0) = i). Elle est par conséquent la solution minimale non négative de hi0 = 1P si i = 0 ∞ (42) hi0 = j=0 ij j0 si i ∈ N0 p h Dans notre cas, X(0) = 1 et la probabilité cherchée est donc h10. Maintenant, hi0 est la probabilité que tous les descendants de i familles différentes “meurent” un jour ou l’autre. Comme l’évolution du nombre de descendants est indépendante d’une famille à l’autre (car les Cin forment une suite de v.a. indépendantes pour tout i et pour tout n), cette probabilité est le produit des i probabilités que chaque famille s’éteigne. Comme les Cin sont identiquement distribuées, ces i probabilités sont identiques, et valent chacune h10. On a donc hi0 = hi10 pour tout i ∈ N0. D’autre part, p1j = P (X(n) = j|X(n − 1) = 1) = P (C1n−1 = j) = cj , si bien que la probabilité cherchée, h10 , est la solution minimale de ∞ ∞ cj hj10. X X h10 = p1j hj0 = j=0 j=0 Le dernier terme de cette équation n’est autre que la fonction génératrice de probabilité des variables Cin (celles-ci étant i.i.d., elles ont toutes la même fonction génératrice de probabilité) ∞ X ∞ X GC (z) = z k P (Cin = k) = z k ck , k=0 k=0 140 évaluée en z = h10. En notant F (z) = GC (z) − z, on conclut donc que h10 est la solution réelle minimale non négative de F (z) = 0. On calcule aisément que ∞ d2 F d2 GC X 2 (z) = 2 (z) = k(k − 1)ck z k−2 ≥ 0 dz dz k=2 pour tout 0 ≤ z ≤ 1, de sorte que F (z) est une fonction convexe sur [0, 1], qui vaut F (0) = GC (0) = c0 > 0 en z = 0 et F (1) = GC (1)−1 = 0 en z = 1. Dès lors, si F (z) atteint un minimum dans ]0, 1[, l’équation F (z) = 0 a une solution h10 < 1, comme indiqué à la figure 6(a). Sinon, la solution est h10 = 1, comme indiqué à la figure 6(b). Par conséquent, h10 = 1 si et seulement si dF (z)/dz < 0 pour tout 0 ≤ z < 1. Désignons par µC la moyenne des v.a. Cin. Comme ∞ ∞ dF dGC X X (z) = (z) − 1 = kck z k−1 − 1 < kck − 1 = µC − 1, dz dz k=1 k=1 pour tout z ∈ [0, 1[, on a que h10 = 1 si µC ≤ 1. Par contre, si µC > 1, dF (z)/dz → µC − 1 > 0 pour des valeurs de z proches de 1, et donc le minimum est atteint dans [0, 1[. En conclusion, le probabilité d’extinction de la population vaut l’unité si et seulement si le nombre moyen de descendants générés par individu est inférieur ou égal à 1. F(z) = GC(z)-z F(z) = GC(z)-z c0 c0 h10=1 h10 1 z z (a) (b) Figure 6: Solution minimale h10 de l’équation F (z) = z. 141 2.7 Chaı̂nes réversibles 2.7.1 Définition Supposons qu’on ait une chaı̂ne de Markov ergodique à l’état stationnaire, et qu’à partir d’un certain temps n, on considère la séquence d’états X(n), X(n − 1), X(n − 2),... , X(0), c’est-à- dire la chaı̂ne originelle en remontant le temps (backward chain). On peut montrer que cette séquence est elle-même une chaı̂ne de Markov en montrant que P (X(n) = j | X(n + 1) = i, X(n + 2) = k, X(n + 3) = l,...) P (X(n) = j, X(n + 2) = k, X(n + 3) = l,... | X(n + 1) = i) = P (X(n + 2) = k, X(n + 3) = l,... | X(n + 1) = i) P (X(n + 2) = k, X(n + 3) = l,... | X(n + 1) = i, X(n) = j)P (X(n) = j | X(n + 1) = i) = P (X(n + 2) = k, X(n + 3) = l,... | X(n + 1) = i) P (X(n + 2) = k, X(n + 3) = l,... | X(n + 1) = i)P (X(n) = j | X(n + 1) = i) = P (X(n + 2) = k, X(n + 3) = l,... | X(n + 1) = i) = P (X(n) = j | X(n + 1) = i). A partir de la formule de Bayes, on peut calculer les probabilités de transitions de la chaı̂ne “renversée”: p̃ij = P (X(n) = j | X(n + 1) = i) P (X(n + 1) = i | X(n) = j)P (X(n) = j) pji πj? = = (43) P (X(n + 1) = i) πi? où les {πi? , i ∈ S} sont les probabilités d’état stationnaires de la chaı̂ne. Si p̃ij = pij pour tout i, j ∈ S, alors la chaı̂ne de Markov est dite réversible (temporellement). A cause de (43), une chaı̂ne de Markov ergodique est donc réversible si pour tout i, j ∈ S πi? pij = πj? pji. (44) Cette condition signifie que le taux avec lequel le processus passe de l’état i à l’état j, à savoir πi? pij , est égal au taux avec lequel le processus passe de l’état j à l’état i, à savoir πj? pji. Pour cette raison, on appelle ces équations équations de balance. Cette condition permet de simplifier le calcul de la distribution stationnaire: si on trouve un ensemble de réels non négatifs {xi , i ∈ S} dont la somme fait 1 et tels que xi pij = xj pji alors ces quantités sont les probabilités d’état stationnaires πi?. En effet, en sommant cette dernière relation sur i, on obtient X X xi pij = xj pji = xj i∈S i∈S et d’autre part la distribution stationnaire d’une chaı̂ne ergodique est unique, d’où xi = πi?. 142 2.7.2 Exemples Marche aléatoire uni-dimensionelle à barrières bloquantes. Remarquons que pour toute trajectoire prise jusqu’à n’importe quel temps n, X(0), X(1), X(2), X(3),... , X(n − 1), X(n) le nombre de transitions de l’état i à l’état (i + 1) ne peut différer du nombre de transitions de l’état (i + 1) à l’état i que d’une unité au plus, car entre deux transitions de i à (i + 1), il doit nécessairement y avoir eu une transition de (i + 1) à i et vice-versa (en effet, la seule manière de revenir à l’état i à partir d’un état j ≥ i est de repasser par (i + 1)). Par conséquent, la proportion sur le long terme de transitions de i à (i + 1) est égale à la proportion de transitions de (i + 1) à i, et donc cette chaı̂ne est réversible. On vérifie de fait que les probabilités (26) satisfont à πi? pij = πj? pji. En fait le même argument s’étend à toute chaı̂ne de Markov à barrières bloquantes dans laquelle les transitions entre états sont limitées aux deux voisins immédiats, sans être nécessairement identiques pour tous les états i; i.e. pour toute chaı̂ne pour laquelle pi,i+1 = 1 − pi,i−1 pour 1 ≤ i ≤ N − 1 p01 = 1 − p00 (45) pN N = 1 − pN,N −1. Marche aléatoire sur un cercle. Ici par contre, la disitribution stationnaire est (27), et la condition de réversibilité devient pij = pji pour tout i 6= j, ce qui entraı̂ne que p = pi,i+1 = 1 − pi,i−1 et donc p = 1/2. Par conséquent, si p 6= 1/2, cette chaı̂ne n’est pas réversible. Urnes d’Ehrenfest. Les probabilités de transition satisfaisant (45), cette chaı̂ne est réversible. L’exercice 16 montrera comment cette propriété nous permet de calculer facilement la distribution (28),à partir des équations de balance ? πi−1 pi−1,i = πi? pi,i−1. 2.8 Ergodisme Nous avons déjà mentionné qu’une chaı̂ne de Markov homogène irréductible, apériodique et dont tous les états sont récurrents positifs est dite ergodique. Ce terme est à rapprocher du théorème suivant, que nous ne demontrons pas: 143 Théorème 7 Si X(n) est une chaı̂ne irréductible récurrente positive, dont la distribution sta- tionnaire est π ? = [π0? π1?...] alors pour toute fonction bornée f : S 7→ R, m−1 ! 1 X X P f (X(n)) → πi? f (i) pour m → ∞ = 1. (46) m n=0 i∈S En particulier, pour f (x) = 1{x=i} (i.e., f (x) = i si x = i et f (x) = 0 sinon), on a m−1 ! 1 X P 1{X(n)=i} → πi? pour m → ∞ = 1 (47) m n=0 ce qui montre que le proportion de temps passé dans chaque état avant un certain temps m tend vers πi? sur le long terme (m → ∞). D’autre part, si f (x) = x, on a m−1 m−1 1 X 1 X f (X(n)) = X(n) = < X(n) >m m m n=0 n=0 X X πi? f (i) = iπi? = µX i∈S i∈S où µX est l’espérance de la chaı̂ne X à l’état stationnaire, si bien que (46) devient P ( < X(n) >m → µX pour m → ∞) = 1. ce qui montre qu’une chaı̂ne de Markov irréductible récurrente positive est ergodique par rapport à sa moyenne. Notons que l’équation ci-dessus signifie que < X(n) >m converge vers µX avec probabilité 1, ce qui est une forme d’ergodisme différente (on peut montrer qu’elle est plus forte) que celle en moyenne quadratique considérée au module 4. Le théorème montre qu’une chaı̂ne de Markov irréductible récurrente positive est ergodique en distribution. Remarquons qu’on réserve traditionnellement la dénomination de chaı̂ne de Markov ergodique (tout court) pour une chaı̂ne de Markov irréductible récurrente positive et apériodique; la raison vient de la théorie ergodique et dépasse le cadre de ce cours. Dans le cas d’une chaı̂ne de Markov qui n’est pas nécessairement ergodique en distribution, on a le résultat suivant Théorème 8 Si X(n) est une chaı̂ne irréductible, alors pour toute fonction bornée f : S → 7 R, m−1 ! 1 X 1 P 1{X(n)=i} → pour m → ∞ = 1. (48) m E[Ti | X(0) = i] n=0 En effet, si la chaı̂ne est transitoire, le nombre de visites à l’état i est fini, si bien que m−1 1 X 1 1{X(n)=i} → 0 =. m E[Ti | X(0) = i] n=0 144 D’autre part, si la chaı̂ne est récurrente positive, le théorème 4 entraı̂ne que (48) est équivalent à (47). Enfin, dans le cas récurrent nul, la même raisonnement que dans le cas récurrent positif établit le théorème. 145  p11 = 1–p p12 = p p22 = 1–p p11 = 1 1 2 1 p21 = p b1(P) = p b1(F) = 1–p b1(P) = 1 b2(F) = 1 Pile Face Pile Face (a) (b) p11 = 1–p p12 = p p22 = 1–p 1 2 p21 = p b1(P) = p1 b1(F) = 1–p1 b2(F) = 1–p2 b2(P) = p2 Pile Face Pile Face (c) Figure 7: Chaı̂ne de Markov à deux états symétrique (a), chaı̂ne de Markov cachée à un état (b) et chaı̂ne de Markov cachée à deux états (c). 3 Chaı̂nes de Markov cachées 3.1 Définition On peut compliquer le modèle d’une chaı̂ne de Markov en le rendant doublement stochastique comme suit. Reprenons l’exemple de la chaı̂ne de Markov à deux états traitée comme premier exemple de la section précédente, mais dans le cas symétrique où p = q et dont le diagramme des transitions d’états est représenté à la figure 7 (a). Supposons que cette chaı̂ne de Markov représente un tirage d’une même pièce de monnaie à pile ou face: le processus se trouve dans l’état 1 lorsque le côté ”pile” (P) est tiré, et dans l’état 2 lorsque le côté ”face” (F) est obtenu. Par conséquent, si on observe la séquence de résultats successifs (qu’on appellera observations) [O(0), O(1), O(2),... , O(n)] = [P, P, F, P, P, P, P, F, F, F, P, P ] il est clair que les états successifs dans lesquels la chaı̂ne se trouvait étaient [X(0), X(1), X(2),... , X(n)] = [1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1] puisqu’à chaque état correspond une seule valeur observée (Pile pour l’état 1, face pour l’état 2). Un autre modèle tout aussi valable pour cette situation est le modèle dégénéré de la figure 7 (b), dans lequel il n’y a plus qu’un seul état, mais à partir duquel on peut obtenir deux observations différentes : pile avec une probabilité p et face avec une probabilité (1 − p). 146 A présent, on dispose de deux pièces de monnaies différentes. Une personne lance tantôt la première pièce, tantôt la seconde, mais elle ne dit pas laquelle des deux pièces elles utilise, elle communique seulement le résultat de chaque tirage, par exemple [o(1), o(2),... , o(n)] = [P, P, F, P, P, P, P, F, F, F, P, P ]. On peut modéliser ces expériences par le diagramme de la figure 7 (c): l’état 1 correspond à l’utilisation de la première pièce, et l’état 2 à l’utilisation de la seconde pièce. Lorsque la personne utilise la première pièce, la probabilité d’obtenir le côté pile vaut p1 et donc la probabilité d’avoir le côté face est (1 − p1 ), tandis que pour la seconde pièce ces probabilités sont respectivement p2 et (1 − p2 ). Outre la distribution de probabitité pile/face caractérisant chaque état, un autre ensemble de probabilités interviennent: la matrice des probabilités de transitions entre états. Ce processus est donc doublement stochastique, et la séquence des résultats observés ne permet pas de déterminer à coup sûr l’état dans lequel on se trouvait, c’est pourquoi on appelle ce modèle chaı̂ne de Markov cachée (en anglais: Hidden Markov Model (HMM)). Par exemple, supposons qu’en tirant n fois la première pièce seulement on ait la séquence d’observations [O0 (0), O0 (1), O0 (2),... , O0 (n)] = [P, P, F, P, P, F, P, P, P, F, F, P ], tandis qu’en tirant n fois la seconde pièce seulement on ait la séquence d’observations [O00 (0), O00 (1), O00 (2),... , O00 (n)] = [F, F, F, F, P, P, P, F, F, F, P, P ]. Alors si la séquence d’états successifs dans laquelle la chaı̂ne se trouve est [X(0), X(1), X(2),... , X(n)] = [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1] la séquence observée est [O(0), O(1), O(2),... , O(n)] = [P, P, F, P, P, P, P, F, F, F, F, P ]. De même, avec trois pièces de monnaie, on peut construire une HMM à trois états. Remarquons que le diagramme de la figure 7 (b) est une HMM dégénérée à un état. D’une façon générale, une chaı̂ne de Markov cachée fait intervenir deux paramètres: le nombre N d’états i, 1 ≤ i ≤ N , que peut prendre X(n), le nombre M de valeurs vk , 1 ≤ k ≤ M , que peut prendre l’observation O(n), (dans l’exemple des pièces de monnaie, N est le nombre de pièces différentes qui sont tirées et M = 2, car v1 = ”Pile” et v2 = ”Face”) et met en jeu trois ensembles de probabilité: la loi de distribution P = {pij } des probabilités pij = P (X(n + 1) = j | X(n) = i) de transition d’un état i à un état j, 1 ≤ i, j ≤ N , la loi de distribution B = {bi (vk )} des probabilités bi (vk ) = P (O(n) = vk | X(n) = i) des observations lorsque le processus est dans l’état i, 1 ≤ i ≤ N, 1 ≤ k ≤ M , la loi de distribution π(0) = {πi (0)} des probabilités d’état initiales πi (0) = P (X(0) = i). Une chaı̂ne de Markov cachée sera désignée de manière plus compacte par λ = (P, B, π(0)), notation qui spécifie l’ensemble complet des paramètres du modèle. 147 4 Application: reconnaissance de la parole Les chaı̂nes de Markov cachées sont très utiles pour la reconnaissance de la parole, car elles per- mettent de s’affranchir de la grande variabilité du signal de parole (la segmentation en phonèmes du même mot prononcé par deux locuteurs peut se produire a des intervalles de temps très différents). Nous allons brièvement exposer comment on utilise les HMMs dans un des cas les plus ”simples” de reconnaissance de la parole: la reconnaissance de mots isolés d’un vocabulaire fini de K mots. Le signal de parole est d’abord codé comme une séquence de symboles, par un prétraitement approprié, comme par exemple l’analyse LPC vue au module 4. Soit O le vecteur aléatoire représentant cette suite de symboles O = [O(0), O(1),... , O(n)] qui peut prendre une des valeurs v = [vk0 , vk1 ,... , vkn ] où 1 ≤ k0 , k1 ,... , kn ≤ M. Le problème de la reconnaissance est alors de retrouver le mot mr , 1 ≤ r ≤ K, qui est le plus susceptible de correspondre à cette séquence d’observations. Autrement dit, si W est la v.a. représentant les différents mots du vocabulaire, on cherche l’indice r du mot (1 ≤ r ≤ K) qui maximise la probabilité P (W = mr | O = v). Comme cette probabilité ne peut pas être évaluée directement, on utilise la règle de Bayes pour la mettre sous la forme P (O = v | W = mr )P (W = mr ) P (W = mr | O = v) =. (49) P (O = v) L’ensemble des probabilités a priori P (W = mr ) est assez facilement déterminé à partir de la fréquence d’apparition de chaque mot dans le vocabulaire limité. Les probabilités P (O = v) n’ont pas besoin d’être évaluées pour déterminer l’indice r qui maximise la proba- bilité (49), puisqu’elles ne dépendent pas de r. Il reste à calculer les probabilités conditionnelles P (O = v | W = mr ), c’est-à-dire les probabilités que la prononciation du mot d’indice r ait produit la séquence observée v. Dans une procédure d’apprentissage que nous n’expliquons pas ici, on construit un modèle de chaque mot mr , 1 ≤ r ≤ K, qui est ici une chaı̂ne de Markov cachée λr = (Pr , Br , π r (0)). Le problème de la reconnaissance revient alors à calculer pour chaque 1 ≤ r ≤ K la probabilité P (O = v | W = λr ) pour déterminer l’indice r qui maximise cette probabilité lorsqu’elle est multipliée par P (W = mr ). 148  HMM λ1 modélisant le mot m1 Calcul de la probabilité P(O| λ1) P(m1) P(O| λ1) P(m1) Indice r Signal de du mot parole O Sélection de l'indice reconnu Prétraitement r du maximum HMM λΚ modélisant le mot mΚ P(O| λΚ) P(mΚ) Calcul de la probabilité P(O| λΚ) P(mΚ) Figure 8: Reconnaissance de mots isolés d’un vocabulaire limité. Le système de reconnaissance est schématisé à la figure 8. Pour évaluer une des probabilités P (O = v | W = λ), il faut d’abord calculer la probabilité qu’aux temps 0, 1,... , n le processus représenté par le vecteur aléatoire X = [X(0), X(1),... , X(n)] se soit trouvé dans la séquence d’états particulière i = [i0 , i1 ,... , in ] (50) avec 1 ≤ i0 , , i1 ,... , in ≤ N. On trouve P (X = i | W = λ) = πi0 (0)pi0 i1 pi1 i2... pin−1 in. (51) Ensuite, calculons la probabilité qu’étant dans la séquence d’états particulière (50), on observe la séquence O. On suppose que les observations sont statistiquement indépendantes. Dès lors, n Y P (O = v | W = λ, X = i) = P (O(l) = vkl | W = λ, X = i) l=0 Yn = P (O(l) = vkl | W = λ, X(l) = il ) l=0 = bi0 (vk0 )bi1 (vk1 )... bin (vkn ). (52) Par conséquent, la combinaison des relations (51) et (52), et le théorème des probabilités totales 149 entraı̂nent que X P (O = v | W = λ) = P (O = v | X = i, W = λ)P (X = i | W = λ) tous les i X = πi0 (0)bi0 (vk0 )pi0 i1 bi1 (vk1 )... pin−1 in bin (vkn ) (53) i0 ,i1 ,...,in L’évaluation directe de (53) est extrêmement coûteuse en nombre d’opérations: il y a N n séquences d’états i différentes, et pour chacune d’elles il faut effectuer 2n − 1 multiplications et une addition, ce qui donne 2nN n opérations. A titre d’exemple, s’il y a N = 5 états et n = 100 observations, il y a environ 2 · 5 · 5100 ≈ 1072 opérations ! Heureusement, des algorithmes itératifs permettent d’évaluer (53) beaucoup plus efficacement. Une manière de procéder est d’introduire une variable auxiliaire αi (l) = P (O(0) = vk0 , O(1) = vk1 ,... , O(l) = vkl , X(l) = i | W = λ). (54) On a de la sorte un algorithme comportant trois parties: 1. Initialisation (l = 0): la valeur initiale de cette variable est, pour 1 ≤ i ≤ N , αi (0) = P (O(0) = vk0 , X(0) = i | W = λ) = P (O(0) = vk0 | X(0) = i, W = λ)P (X(0) = i | W = λ) = bi (vk0 )πi (0). 2. Induction: (0 ≤ l ≤ N − 1) Le calcul itératif des αi (l + 1) à partir des αi (l) fait l’objet de l’exercice 8, où on établit la récurrence pour 1 ≤ i ≤ N   XN αi (l + 1) =  αj (l)pij  bi (vkl+1 ). (55) j=1 3. Terminaison: (l = n) pour 1 ≤ i ≤ N , N X N X P (O = v | W = λ) = P (O = v, X(n) = i | W = λ) = αi (n). i=1 i=1 Le nombre d’opérations de cet algorithme n’est plus que de l’ordre de nN 2. Par exemple, pour N = 5 et n = 100, il y a environ 3000 opérations, au lieu des 1072 opérations nécessaires pour une évaluation directe. Une autre alternative est de ne plus faire l’évaluation de (53) pour toutes les combinaisons d’état possibles, mais seulement pour la plus vraisemblable, c’est-à-dire de remplacer (53) par P (O = v | W = λ) ≈ max πi0 (0)bi0 (vk0 )pi0 i1 bi1 (vk1 )... pin−1 in bin (vkn ) i0 ,i1 ,...,in ce qui diminue considérablement le nombre d’opérations. Il faut alors résoudre le problème de la détermination de la séquence d’états la plus probable. A nouveau dans ce cas, des procédures récursives sont efficacement utilisées (algorithme de Viterbi). Notons enfin qu’en pratique, la loi de probabilité bi (vk ) n’est pas discrète, mais continue (gaussi- enne). 150 5 Exercices 1. Soit un processus à moyenne mobile (MA) Y (n) = (X(n) + X(n − 1))/2 où X(n) est une suite de v.a. de Bernouilli indépendantes dont la probabilité de succès p = 1/2 (Donc P (X(n) = 1) = P (X(n) = −1) = 1/2. Le processus Y (n) est-il Markovien ? 2. Soit un processus auto-régressif (AR) Y (n) = αY (n − 1) + X(n) où Y (0) = 0 et où X(n) est une suite de v.a. de Bernouilli indépendantes dont la probabilité de succès p = 1/2 (Donc P (X(n) = 1) = P (X(n) = −1) = 1/2). Le processus Y (n) est-il Markovien ? 3. Soient trois états i, j, k d’une chaı̂ne de Markov. Démontrez que si i et j communiquent, et que si j et k communiquent, alors i et k communiquent. 4. Etablir la matrice (24). 5. Calculer la distribution invariante de probabilité d’état pour la marche aléatoire unidi- mensionnelle dont le diagramme des transitions est représenté en haut de la figure 3. 6. Une matrice P est dite doublement stochastique si tous ces éléments sont non négatifs, et si la somme de tous ses éléments le long d’une ligne et d’une colonne vaut 1. (a) Montrer que la marche aléatoire sur un cercle est décrite par une matrice P double- ment stochastique. (b) Montrer que si le nombre d’états est fini, une chaı̂ne de Markov dont la matrice de transition est doublement stochastique admet une distribution invariante. Laquelle ? 7. Pour les deux chaı̂nes de Markov définies par les deux matrices de transition suivantes, déterminer les classes d’états, et si celles-ci sont transitoires ou récurrentes:     3/4 1/4 0 0 0 0 0 1/2 1/2  3/4 1/4 0  1 0 0 0 0  0    P1 =    P2 =  0  0 3/4 1/4 0  . 0 1 0 0   0 0 3/4 1/4 0  0 1 0 0 1/4 1/4 0 0 1/2 8. Vu la météorologie de son pays, un Belge possède en général un stock de N parapluies, avec N > 1. Quand il se rend le matin à son bureau, il emmène un parapluie avec lui s’il pleut (et qu’un parapluie est disponible chez lui). Par contre, s’il ne pleut pas, il part sans parapluie. Au retour, il applique le même algorithme: il rentre avec un parapluie si et seulement si il pleut, et qu’un d’eux est disponible au bureau. On suppose qu’indépendamment de la météo des demi-journées précédentes, il pleut en début (ou en fin) de journée avec une probabilité p. (a) Quelle est la probabilité que notre Belge se fasse rincer ? (On suppose qu’il utilise ses parapluies de cette manière depuis (pratiquement) toujours.) Hint: soit n l’instant d’un départ (que ce soit de la maison ou du bureau) et soit X(n) le nombre de para- pluies disponibles à l’instant n. Calculer la distribution stationnaire de probabilité de cette chaı̂ne de Markov. 151  (b) La probabilité de pluie p = 1/2 en Belgique (ce chiffre est faux: en réalité, il ne pleut tout de même pas tant que ça) et notre Belge, bien qu’ayant déjà un stock de N = 10 parapluies, estime qu’il est trempé trop fréquemment. Il se dit qu’en déménageant dans n’importe quel pays moins pluvieux, il ne le sera plus aussi souvent. A-t-il raison ? Hint: calculer d’abord la probabilité p qui maximise la probabiité que le Belge soit trempé, et comparer avec 1/2. 9. Quelle est la distribution stationnaire d’états de la marche aléatoire à deux barrières réfléchissantes, dont le diagramme des transitions entre états est représenté à la figure 9 ? 1 p p p p 0 10 2 0 N-1 N q=1-p q=1-p q=1-p q=1-p 1 Figure 9: Marche aléatoire à deux barrières ‘réfléchissantes’. 10. On considère le processus de la ruine du joueur sur {0, 1,... , N }, pour lequel les proba- bilités que le joueur A remporte la partie sont données par (37) si son capital initial vaut i. Montrer qu’en prenant la limite pour N → ∞, on retrouve le résultat (41). 11. Etablir (39). 12. Un terrain de golf est, pour le besoin de l’exercice, discrétisé de sorte que la distance entre l’endroit ou se trouve la balle de golf au nième coup et le trou peut prendre les valeurs 0 (il a alors terminé), 1,... , N. La distance initiale est N. Un joueur adopte la tactique suivante: à chaque coup, il se rapproche du trou, et est suffisamment expérimenté pour ne jamais augmenter la distance entre la balle et le trou d’un coup au suivant. Néanmoins, cette tactique le pousse à frapper parfois trop doucement la balle. En fait, s’il est arrivé à une distance i du trou, son coup suivant l’amènera à envoyer la balle à une distance uniformément distribuée entre 0 et i − 1. (a) Cette partie est une chaı̂ne de Markov, dont l’espace des états est S = {0, 1,... , N }. Dessiner le diagramme des transitions entre les états. Quelles sont les probabilités de transition ? (b) Quelle est l’espérance du nombre de coups que doit jouer notre golfeur pour mettre la balle dans le trou ? 13. On peut facilement déterminer la nature des états (transitoires ou récurrents) de la marche aléatoire sur N, dont le diagramme des transitions entre états est représenté à la figure 10, à partir de létude faite sur la probabilité d’absorption pour la ruine du joueur sur N. En effet, désignons par X(n) la marche aléatoire sur N et par Y (n) la ruine du joueur sur N. 152  1 p p p p 0 10 2 03 q=1-p q=1-p q=1-p q=1-p q=1-p Figure 10: Marche aléatoire sur N. (a) Montrer que la probabilité de premier retour à l’état 0 de la marche aléatoire sur N X(n) f0 = P (X(n) = 0 pour un certain n ∈ N0 |X(0) = 0) et la probabilité d’absorption dans l’état 0 du processus Y (n) à partir de l’état 1 h10 = P (Y (n) = 0 pour un certain n ∈ N |Y (0) = 1) sont identiques: f0 = h10. (b) A partir des résultats de la section sur la ruine du joueur sur N, déterminer les valeurs de p pour lesquelles les états sont transitoires ou récurrents. (c) Calculez la distribution stationnaire de probabilité pour 0 < p < 1/2 (Hint: c’est une chaı̂ne réversible). Que se passe-t-il lorsque p = 1/2 ? 14. Calculer la probabilité d’extinction d’un processus de branchement, si les v.a. Cin décrivant le nombre de descendants du ième individu de la (n + 1)ième génération sont des v.a. géométriques de paramètre p. 15. On considère le processus de branchement de la section 2.6.3. Calculer E[X(n)] pour tout n ∈ N (Hint: conditionner sur X(n − 1), i.e. calculer E[X(n)|X(n − 1) = m] pour tout m ∈ N). Que vaut limn→∞ E[X(n)] si µC < 1 ? Vous attendiez-vous à ce résultat ? 16. Calculer la distribution stationnaire du problème des urnes d’Ehrenfest. 17. On considère la chaine de Markov à deux états de la section 2.4.1, avec 0 < p, q < 1. On va établir la distribution stationnaire de probabilité de cette chaine à partir du théorème 4 et du temps de premier passage par l’état 0, T0. (a) Déterminer P (T0 = m | X(0) = 0) pour tout m ∈ N0. (Hint : commencer par m = 1, 2,...). (b) Calculer l’espérance E[T0 | X(0) = 0] (Hint: calculer d’abord la fonction génératrice GT0 |X(0)=0 (z)). On a alors π0? = 1/E[T0 | X(0) = 0]. 153