Récurrence et transience d'une chaîne de Markov

Un état d'une chaîne de Markov est dit récurrent si une trajectoire « typique » de la chaîne de Markov passe par une infinité de fois, sinon l'état est dit transient. Ces propriétés de transience ou de récurrence sont souvent partagées par tous les états de la chaîne par exemple quand la chaîne est irréductible : en ce cas c'est la chaîne de Markov qui est dite transiente ou récurrente.

Temps de séjour et temps de premier retourModifier

Pour chaque état i d'une chaîne de Markov, on a les définitions suivantes :

Définition — 

  • Le temps de séjour (ou nombre de passages) en   est une variable aléatoire   à valeurs dans   définie par
 

La quantité

 

mesure le temps passé dans l'état   lors des   premiers pas de la chaîne de Markov. Les relations suivantes seront utiles :

 
  • Le temps de premier retour en   noté   est une variable aléatoire à valeurs dans   définie par
 

Récurrence et transience (définition informelle)Modifier

Informellement, pour une chaîne de Markov irréductible, un état   du système modélisé par la chaîne de Markov est dit récurrent si une trajectoire typique du système passe infiniment souvent par cet état. Il y a en fait dichotomie :

  • soit la probabilité que la trajectoire du système passe infiniment souvent par   vaut 1, et l'état   est dit récurrent,
  • soit cette probabilité vaut 0, auquel cas   est dit transient.
  • les états récurrents (ceux pour lesquels  ) se subdivisent en états récurrents positifs et récurrents nuls :
  • un état est dit récurrent positif si le système y passe une fraction non négligeable de son temps : bien sûr   mais   ne doit pas être trop petit devant  :
 
en notation de Landau,   Cela entraîne que les instants de passage en   sont, en un certain sens, régulièrement espacés, à une distance   les uns des autres en moyenne,
  • un état est dit récurrent nul si le système y passe une fraction négligeable de son temps :
 
i.e.   mais   Le système passe infiniment souvent par l'état   mais les instants de passage en   sont alors de plus en plus espacés au cours du temps.

Toujours dans le cas d'une chaîne de Markov irréductible, si un état est récurrent positif, tous les états le sont et la suite   est appelée probabilité stationnaire de la chaîne de Markov. La probabilité stationnaire joue un rôle très important dans l'étude de la chaîne de Markov.

Marche aléatoire sur   et   :

Par exemple, si   on parle de marche aléatoire sur   ou sur  

  • Si on est sur   alors, indépendamment de la valeur de   chaque état est récurrent positif et chaque   vaut  
  • Si on est sur   et si   chaque état   est transient : au bout d'un certain temps, aléatoire, une trajectoire typique ne passe plus jamais par  
  • Si on est sur   et si   chaque état   est récurrent nul :   et le  -ième passage a lieu, grosso-modo, au bout de   unités de temps.
Récurrence et théorie ergodique :

Il faut mentionner une notion très voisine : le théorème de récurrence de Poincaré (1890) dit que, pour presque toutes les « conditions initiales », un système dynamique conservatif dont l'espace des phases est de « volume » fini va repasser au cours du temps aussi près que l'on veut de sa condition initiale, et ce de façon répétée.

Critères de récurrence et de transienceModifier

Notations. Lorsqu'on étudie une chaîne de Markov particulière, sa matrice de transition est en général bien définie et fixée tout au long de l'étude, mais la loi initiale peut changer lors de l'étude et les notations doivent refléter la loi initiale considérée sur le moment :
  • si à un moment de l'étude on considère une chaîne de Markov de loi initiale définie par   alors les probabilités sont notées   et les espérances sont notées  
  • en particulier, si   on dit que la chaîne de Markov part de   les probabilités sont notées   et les espérances sont notées  

Définition — 

  • Un état   est dit récurrent si et seulement si l'une des conditions équivalentes ci-dessous est remplie :
  •  
  •  
  •  
  •  
  •  
  • Un état   est dit transient dans le cas contraire, i.e. si et seulement si l'une des conditions équivalentes ci-dessous est remplie :
  •  
  •  
  •  
  •  
  •  
  • L'état   est récurrent positif si
  • l'espérance du temps de premier retour en cet état, partant de cet état, est finie, i.e. si
 
ou bien, de manière équivalente, si
  • il existe une probabilité stationnaire   telle que   i.e. une probabilité   telle que   et telle que   cette dernière relation s'écrivant aussi, coordonnées par coordonnées,
 
  • L'état   est récurrent nul s'il est récurrent et si, pourtant, l'espérance du temps de premier retour en cet état, partant de cet état, est infinie, i.e. si
  •  

ExemplesModifier

Marche aléatoire sur un groupe finiModifier

 
Graphe de 2 marches aléatoires élémentaires, respectivement sur le groupe cyclique   et sur le groupe diédral  
Marche aléatoire sur   :

Dans cet exemple,   La matrice de transition   s'écrit

 

  (resp.  ) est la matrice de la permutation circulaire   (resp.  ). Par conséquent   est une probabilité stationnaire, donc chaque état est récurrent positif, en vertu du 2e critère. Dans la figure ci-contre,   et  

Marche aléatoire sur   :

Dans cet exemple,   et    est la symétrie du carré par rapport à la diagonale (a,c), et où   est la symétrie du carré par rapport à son axe horizontal ;   est la rotation d'angle   La probabilité   est une probabilité stationnaire, donc chaque état est récurrent positif, en vertu du 2e critère.

Plus généralement, tous les états d'une marche aléatoire sur un groupe fini   sont récurrents positifs, car la loi uniforme discrète sur   est une probabilité stationnaire, indépendamment du pas de la marche : en effet, la matrice de transition   d'une marche aléatoire sur un groupe discret est bistochastique (i.e. non seulement la somme des termes d'une ligne vaut 1, quelle que soit la ligne, mais la somme des termes d'une colonne de   vaut 1, quelle que soit la colonne). Si tous les coefficients du vecteur ligne   valent 1, on vérifie alors sans peine que   Ainsi la mesure uniforme, qui est proportionnelle à   est stationnaire.

Marche aléatoire simple sur les entiers relatifsModifier

Dans cet exemple,   et   Si   la chaîne   est irréductible, donc tous les états ont même nature. Par exemple on a

 

alors que  

Marche aléatoire biaiséeModifier

  • Si on observe la forme de la fraction ci-dessus, comme   la marche est transiente si et seulement si   en vertu du quatrième critère de transience exprimé dans la partie « Critères de récurrence et de transience ».
  • On peut aussi voir que   entraîne la transience de la chaîne de Markov   en construisant cette chaîne à l'aide d'une suite de variables aléatoires i.i.d.   de la manière suivante : posons
 
Alors   a même loi que   mais la loi forte des grands nombres pour les suites de v.a. i.i.d. entraîne que, presque sûrement en  
 
donc, avec probabilité 1, la suite de nombres réels   converge vers   et visite la valeur 0, au plus, un nombre fini de fois : 0 est donc transient, et tous les entiers de sa classe (  en l'occurrence) avec lui.
  • Dans le cas où   la méthode précédente ne permet pas de démontrer la récurrence de 0, puisque la loi forte des grands nombres stipule alors la convergence de la suite   vers 0, ce qui n'entraîne pas nécessairement que la suite   prenne la valeur 0 une infinité de fois : pour aboutir à la conclusion d'une infinité de visites en 0, il faut invoquer un résultat plus précis que la loi forte des grands nombres, à savoir la loi du logarithme itéré.
  • Pour décider de la récurrence ou de la transience aussi bien dans le cas   que dans le cas   on peut aussi calculer explicitement la loi du premier temps T de retour en 0, partant de 0, pour la marche aléatoire simple, et trancher ainsi l'alternative :
 
En effet
 
  désigne le n-ème nombre de Catalan. On trouve alors que la série génératrice de T,   satisfait
 
Ainsi
 
est strictement inférieur à 1 si et seulement si  

Marche aléatoire symétriqueModifier

  • Par ailleurs, pour   la mesure de probabilité   est solution du système   si et seulement si
 
i.e. si et seulement si les   forment une progression arithmétique :
 
La contrainte de positivité sur les   impose   i.e.   est une suite constante. Ainsi   est infinie ou nulle, suivant la valeur de   strictement positive ou bien nulle, donc une mesure invariante ne peut en aucun cas être une mesure de probabilité, ce qui fait qu'il n'existe pas de probabilité stationnaire : tous les états sont récurrents nuls.
 
on peut aussi voir directement, grace la formule explicite de la loi du temps T de retour en 0, donnée à la section précédente, que
 
n'est pas le terme général d'une série convergente, et que, par conséquent,