Next: Le temps exponentiel d'auto-corrélation
Up: Aspects dynamiques des algorithmes
Previous: Aspects dynamiques des algorithmes
  Contents
  Index
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 .
- Écrivons
Or
.
Donc, en se servant de l'inégalité de Jensen pour
majorer
on obtient
Par conséquent,
.
- 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: Le temps exponentiel d'auto-corrélation
Up: Aspects dynamiques des algorithmes
Previous: Aspects dynamiques des algorithmes
  Contents
  Index
Dimitri Petritis
2003-07-03