Universit de Rennes 1 Prparation lagrgation de mathmatiques http://agreg-maths.univ-rennes1.

fr

Auteur : Franoise Guimier Juin 2004

Sur les matrices stochastiques.

Les matrices stochastiques (ou de transition) apparaissent dans ltude des cha e nes de Markov a espace dtats ni. Ce sont des matrices positives particuli`res. On peut leur ` e e attacher un graphe pondr et donc on les retrouve aussi en thorie des graphes. On tudie ee e e ici leurs proprits spectrales, qui permettent de dmontrer un rsultat de convergence de ee e e leurs itres. ee

1. Rappels sur les matrices positives.

Notations. Soit E = {1, . . . , d}. Un vecteur rel v = (vi )iE sera dit positif (respectivee ment strictement positif) si i E, vi 0 (resp. si i E, vi > 0). On notera v 0 (resp. v > 0). De mme pour une matrice relle A = (ai,j )(i,j)E 2 . On rappelle que le e e spectre S de A est lensemble de ses valeurs propres et que son rayon spectral (A) est (n) donn par (A) = sup{|| | S}. Pour n N, on notera An = (ai,j ). e Soit A = (ai,j )(i,j)E 2 une matrice relle positive. On peut attacher a la matrice A un e ` graphe orient G ayant pour sommets les points i de lensemble E = {1, . . . , d} et pour e (n) artes les couples (i, j) E 2 tels que ai,j > 0. On note alors i j si n 0, ai,j > 0, e cest-`-dire sil existe un chemin i = j0 , j1 , . . . , jn = j, aj0 ,j1 > 0, . . . , ajn1 ,jn > 0, allant a de i vers j sur le graphe. On vrie facilement que la relation i j et j i est une e relation dquivalence. e Dnition 1. On dit que A est irrductible sil ny a quune seule classe dquivalence e e e (n) (m) pour cette relation, cest-`-dire si (i, j) E 2 , n 0, ai,j > 0 et m 0, aj,i > 0. Elle a est rductible sinon. e Exemples. Une matrice A > 0 est irrductible. De mme, une matrice A ayant une puise e n sance A > 0. 1 0 La matrice est rductible. e 1 1 Il est facile de voir que A est rductible si et seulement si elle est, ` une permutation des e a B 0 indices pr`s, de la forme e o` B et D sont des matrices carres. u e C D Thor`me de Perron. (1907) Soit A une matrice relle strictement positive. Son e e e rayon spectral (A) est une valeur propre simple et dominante (i.e. de module strictement suprieur a celui des autres valeurs propres). Elle admet un vecteur propre strictement e ` positif. [Gan] Thor`me de Frobenius. Soit A une matrice relle positive irrductible. Son rayon e e e e spectral (A) est une valeur propre simple et admet un vecteur propre strictement positif. [Gan] Exemple. Soit A = 0 1 . La matrice A est positive et irrductible, les valeurs proe 1 0 pres sont 1 et 1. Cest un exemple o` (A) nest pas dominante. u 1

2. Matrices stochastiques.
Dnition 2. Une matrice stochastique (ou probabilit de transition) est une matrice e e positive P telle que i E, pi,j = 1.
jE

Autrement dit, chaque ligne de P est un vecteur de probabilit. e Remarques. ` Le vecteur v0 = (1, . . . , 1) est un vecteur propre de P correspondant a la valeur propre 1 et le rayon spectral de P est 1. En eet, soit une valeur propre de P de vecteur propre v et soit k tel que |vk | = sup |vj |. On a |vk | = | pk,j vj | pk,j |vj | pk,j |vk | = |vk |. Do` u || 1.
1jd j j j

Dapr`s le thor`me de Frobenius, si P est irrductible, 1 est une valeur propre e e e e simple de P . Dnition 3. Une matrice stochastique est ergodique si elle admet une puissance P n > 0. e Proposition 1. Une matrice stochastique ergodique est irrductible et admet 1 comme e valeur propre simple dominante. En eet, soit n tel que P n > 0. Dapr`s le thor`me de Perron appliqu ` P n , 1 est une e e e ea valeur propre simple et dominante de P n . Soit v un vecteur propre associ. Lespace care actristique de P associ ` la valeur propre 1 est contenu dans celui de P n , qui est Rv, e ea donc 1 est une valeur propre simple de P , de vecteur propre v. Si est une valeur propre de module 1 de P , on doit avoir n = 1 et de mme, lespace caractristique associ ` e e ea est gal a Rv, donc = 1. e `

3. Probabilit invariante. e
Dnition 4. Soit P une matrice stochastique. Une probabilit invariante pour P est un e e vecteur de probabilit tel que P = . e Autrement dit, pour la valeur propre 1, le vecteur de probabilit est un vecteur propre e gauche de P , cest-`-dire un vecteur propre de la transpose P t . a e Thor`me 1. Soit P une matrice stochastique irrductible. Alors, P admet une unique e e e probabilit invariante et on a > 0. e Dmonstration. Le thor`me de Frobenius appliqu ` P t montre que lespace propre e e e e a associ ` sa valeur propre 1 est engendr par un vecteur propre v > 0. En le normalisant, ea e on obtient un vecteur de probabilit > 0 et est la seule probabilit invariante. e e

4. Itres dune matrice stochastique irrductible. e e e

2

Dans la suite, P dsignera une matrice stochastique irrductible. e e Remarque. Supposons que (P n ) converge vers une matrice P . Alors P est une matrice stochastique et puisque pour tout n, P P n = P n+1 = P n P , on a P P = P = P P. Comme 1 est une valeur propre simple de P de vecteur propre v0 , pour tout j E il existe un rel j tel que (Pi,j )i = j v0 t . Pour tout (i, j) E 2 , Pi,j = j , donc = (j )jE est un e vecteur de probabilit. Dautre part, puisque P = P P , est la probabilit invariante, e e qui est strictement positive. Pour une matrice ergodique, les itres convergent eectivement et on a : ee Thor`me 2. Soit P une matrice stochastique ergodique et sa probabilit invariante. e e e (n) Alors (i, j) E 2 , Pi,j converge vers j et la vitesse de convergence est exponentielle, plus prcisment, il existe r ]0, 1[ tel que lim rn sup |pn j | = 0. e e i,j
n (i,j)E 2

Dmonstration. e

Pour x Rd et f L(Rd ), on notera ||x|| = sup |xi | et ||f || =

i

sup{||f (x)|| | ||x|| = 1}. On rappelle que le rayon spectral (f ) de f est alors gal a e ` 1 n n lim ||f || . n On a vu que 1 est une valeur propre simple et dominante de P , de vecteur propre e e v0 = (1, . . . , 1). Considrons lapplication linaire f de matrice P dans la base canonique d (e1 , . . . , ed ) de R . On note V un supplmentaire de Rv0 stable par f et p la projection e sur Rv0 parall`lement ` V (pour x = av0 + v, a R, v V , on a p(x) = av0 ). Si g est la e a restriction de f ` V , le rayon spectral (g) est < 1. a Il est facile de voir que si x = av0 +v o` a R, v V , on a f n (x) = p(x)+g n (v) pour tout u n N, do` ||f n (x) p(x)|| ||g n || ||v|| o` ||g n || (g)n . Fixons r tel que < r < 1. On u u d n n a alors, x R , lim r ||f (x) p(x)|| = 0. Soit Rd tel que j, p(ej ) = j v0 . On obtient rn sup |pi,j j | = rn sup ||f n (ej ) p(ej )|| 0.
i,j n (n) j (n) pi,j

En particulier, pour tout i, j, j ; la remarque pralable au thor`me permet e e e den dduire que = et le rsultat. e e Remarques. On peut aussi dmontrer ce rsultat en utilisant une forme de Jordan de P , mais cest e e plus calculatoire. Voir par exemple [Foa] ou [Ser]. (En fait, cette mthode aboutit e 1 n n e aussi a la relation (f ) = lim ||f || ; les calculs sont cachs dans cette formule.) `
n

Ce rsultat particularise la mthode classique des puissances pour le calcul e e numrique dun vecteur propre dominant. ([Ser]) e Si on supprime lhypoth`se dergodicit, les choses sont plus compliques, car il peut y e e e avoir plusieurs valeurs propres de module 1. On peut quand mme voir que les itres de e ee P sont encore des matrices stochastiques et comme lensemble des matrices stochastiques est ferm et born, il y a des sous-suites de (P n ) qui convergent et leurs limites sont e e 0 1 stochastiques. Par exemple, si P = , les sous-suites (P 2n ) et (P 2n+1 ) convergent, 1 0 e mais (P n ) ne converge pas. Avec des raisonnements du mme style que ci-dessus (voir [FoF]), on obtient : 3

Thor`me 2. Soit P une matrice stochastique irrductible et sa probabilit invarie e e e (n) 2 ante. Alors (i, j) E , Pi,j converge en moyenne de Csaro vers j . e

5. Crit`res dergodicit. e e
Dnition 5. Soit P une matrice stochastique, i E et Si = {n 0 | pi,i > 0}. La e priode de i est di = p.g.c.d (Si ). On dit que i est apriodique si di = 1. e e Proposition 2. Si P est irrductible, tous les tats i E ont la mme priode. e e e e En eet, soit (i, j) E 2 , (n, m) N tels que pi,j > 0 et pj,i > 0. Si k Sj , on a (m+k+n) (m) (k) (n) pi,i pi,j pj,j pj,i > 0, donc m + k + n Si et di divise m + k + n. En particulier di divise m + n et donc di est un diviseur commun a tous les lments k de Sj . Par suite di ` ee divise dj . Par symtrie, di = dj . e Si par exemple, P = 0 1 , la matrice est irrductible mais pas ergodique, les tats 1 e e 1 0 et 2 sont de priode 2, les valeurs propres sont 1 et 1, 1 nest pas dominante. e En gnral, il peut y avoir plusieurs valeurs propres de module 1, qui sont les h racines e e h-`me de lunit pour un certain entier h et on peut montrer que la priode est h. Le cas e e e h = 1 est explicit par le thor`me : e e e Thor`me 3. Soit P une matrice stochastique irrductible. Il y a quivalence entre : e e e e (i) La matrice P est ergodique. (ii) La matrice P admet 1 comme valeur propre dominante. (iii) La suite (P n ) converge vers une matrice strictement positive. (iv) Pour tout i E, i est apriodique. e (v) Il existe i E qui est apriodique. e Dmonstration. e On a dj` vu que (i) = (ii) (Proposition 1). ea Pour montrer (ii) = (iii), il sut de reprendre la dmonstration du thor`me 2 qui e e e nutilise en fait que lhypoth`se (ii). e (n) Supposons (iii) et soit i E. La suite (pi,i ) converge vers une limite strictement positive. (n) Pour n assez grand, on a donc pi,i > 0 et i est donc apriodique. e Limplication (iv) = (v) est vidente. e Supposons (v). On peut dabord remarquer que Si est un sous-semi-groupe de N. En eet, (n+m) (n) (m) supposons que n et m soient dans Si . On a alors pi,i pi,i pi,i > 0, donc n + m Si . On va utiliser un lemme darithmtique, dont la dmonstration est donne plus bas : e e e Lemme. Soit S un sous-semi-groupe de N tel que p.g.c.d S = 1. Alors, il existe N S tel que [N, +[ S.
(m) (n) (n)

Soit donc N tel que [N, +[ Si . Puisque la cha est irrductible, pour tout ne e (mj ) (n ) 2 (i, j) E , il existe des entiers mj et nj tels que pi,j > 0 et pj,ij > 0. Pour tout u (j, k) E 2 , si n = nj + n + mk o` n N , on a pj,k pj,ij pi,i pi,k k > 0. Soit 2 N = sup{nj + N + mk | (j, k) E }. Comme E est ni, N est ni et on obtient P N > 0 et (i). Dmonstration du lemme. On peut trouver k N et des lments s1 , . . . sk S tels e ee que p.g.c.d (s1 , . . . , sk ) = 1. Puis, en utilisant lidentit de Bezout et quitte a faire une e ` permutation des indices, on peut trouver p, 1 p k et des entiers positifs n1 , . . . nk tels que n j sj nj sj = 1. Les deux sommes sont dans S. On trouve donc a, b S,
1jp p<jk (n) (n ) (n ) (m )

tels que a b = 1. Si b = 0, on obtient S = N. Sinon, pour n N tel que n b2 on peut crire n = bq + r, 0 r < b q, soit n = bq + r(a b) = ra + (q r)b, donc n S. Do` e u 2 [b , +[ S.

Bibliographie.
[FoF] D.Foata, A. Fuchs : Processus stochastiques. Processus de Poisson, chanes de Markov et martingales. Cours et exercices corrigs. Dunod, Paris, 2002. e [Gan]F. R. Gantmacher : Thorie des matrices. Tome 2. Questions spciales et e e applications. Paris : Dunod , 1966. [Agusu et 65] [Ser] D. Serre. Les matrices. Thorie et pratique - Paris. Dunod. 2001 e