next up previous contents index
Next: Exercices Up: Rappels sur les chaînes Previous: Problème d'ensembles indépendantes   Contents   Index

Processus d'évolution

Dans tous les problèmes de recuit, on a introduit une chaîne de Markov inhomogène qui permet d'échantillonner selon une loi limite sur un ensemble restreint des configurations (l'ensemble des minima globaux). Tant la dynamique locale que la dynamique de refroidissement sont des dynamiques ficitives qui ne correspondent pas nécessairement à une description microscopique de l'évolution. Leur raison d'être est de fournir une méthode numérique efficace pour la simulation. Il y a néanmoins de problèmes où la modélisation par une chaîne de Markov inhomogène est dictée par la dynamique microscopique. Pour les processus d'évolution, on utilise traditionellement le formalisme à temps continu. Bien sûr, toute simulation numérique nécessitera une discrétisation qui est cependant triviale dans ce cas. On présente donc les fondements de la méthode, selon la tradition, en temps continu [#!Lig!#].

L'espace de configurations sera toujours noté et sera supposé compact et métrique avec une structure mesurable définie par ses boréliens. Soit


Cet espace est l'espace canonique des trajectoires d'un processus markovien avec espace d'états c'està-dire, à chaque instant , le processus .

L'espérance par rapport à sera notée


pour toute fonction mesurable sur qui est intégrable par rapport à . On munit l'espace des fonctions continues sur de la norme


et on écrit


Si l'opérateur laisse stable l'ensemble des fonctions continues , on parle de processus de Feller. Il est évident qu'un processus fellérien généralise faiblement la notion de chaîne de Markov au cas de temps continu.

Les propriétés suivantes, connues sous le nom de propriétés de semigroupe, découlent de la définition d'un processus fellérien :

  1. sur .
  2. L'application est continue à droite pour toute configuration .
  3. pour toute fonction et tout .
  4. .
  5. pour toute fonction positive.


À la place de l'opérateur , il est souvent plus commode d'utiliser le générateur infinitésimal du semigroupe, défini par


pour les fonctions pour lesquelles la limite existe. On se limite au cas habituel d'espace de configurations défini par un champs sur un graphe où est un graphe, habituellement et un espace compact (muni de sa tribu ). La dynamique locale est définie par la collection des noyaux de transition indexés par les parties finies . La quantité est une mesure finie sur tandis que est une fonction continue pour tout . Le noyau de transition représente le taux de changement local de la configuration.

Le générateur infinitésimal s'exprime en termes de . Définissons à cette fin la configuration transformée par sur  :


On a alors pour le générateur infinitésimal







next up previous contents index
Next: Exercices Up: Rappels sur les chaînes Previous: Problème d'ensembles indépendantes   Contents   Index
Dimitri Petritis 2003-07-03