next up previous contents index
Next: Le temps exponentiel d'auto-corrélation Up: Aspects dynamiques des algorithmes Previous: Aspects dynamiques des algorithmes   Contents   Index

Corrélations

Soit une chaîne de Markov sur l'espace (dénombrable), irréductible, avec matrice de transition et probabilité stationnaire .







Par définition, la mesure n'est pas identiquement nulle ; il existe donc un état pour lequel . Par ailleurs, l'irréductibilité de la chaîne impose que pour tout , il existe un tel que . Finalement, par la sous-invariance, on a


Soit et . On note


la norme de et par l'espace de Banach


En particulier, est un espace de Hilbert avec produit scalaire


L'indice sera omis quand il s'agit de la norme ( ). Dans chaque on définit un opérateur de Perron et Frobenius, , par


où est la matrice de transition de la chaîne.



Si alors l'affirmation est correcte. Soit maintenant un tel que . Alors, par hypothèse, et pour tout




On écrit




Donc, . Mais, le lemme ([*]) garantit que pour tout . Il s'ensuit que .



Soit la fonction constante . Alors, pour tout . Posons . Alors et . Pour la partie positive de , on a , ce qui montre que . On vérifie alors aisément que et le lemme précédent garantit que . Donc soit , soit pour tout . Ceci équivaut à dire que soit , soit pour tout . En choisissant le paramètre arbitraire , on voit que est soit strictement positive, soit négative. Si est positif, elle ne peut être qu'une constante étant donné que est arbitraire. Si , on répète l'argument avec la fonction .



  1. Écrivons


    Or . Donc, en se servant de l'inégalité de Jensen pour majorer


    on obtient




    Par conséquent, .
  2. Il est clair que 1 est valeur propre. On va montrer qu'elle est la seule dont le module soit égal à 1. Soit tel que avec . Ceci implique que . Donc, en vertu du lemme [*] et donc , où est une constante, en vertu du lemme [*]. Par applications successives de l'opérateur , on obtient pour tout ou .

    Donc,


    et par l'inégalité de Schwartz


    Donc . Mais l'inégalité de Schwartz devient une égalité si est une constante. Dans le cas présent, ceci signifie qu'il existe des constantes , telles que


    D'où


    c'est-à-dire


    Or, la chaîne est irréducitble et apériodique ; il existe donc un entier tel que pour tout . En particulier, il existe un tel que et . Donc, d'où .

On introduit un autre opérateur de projection sur  :


Il est facile de voir que est idempotent et commute avec .



next up previous contents index
Next: Le temps exponentiel d'auto-corrélation Up: Aspects dynamiques des algorithmes Previous: Aspects dynamiques des algorithmes   Contents   Index
Dimitri Petritis 2003-07-03