January 9, 2012
Jean-Michel Fourneau (UVSQ)On presente un nouvel algorithme de calcul de la distribution stationnaire de chaine de Markov en temps discret et sa preuve de convergence pour des matrices ayant une colonne strictement positive. Cet algorithme a plusieurs avantages par rapport aux algorithmes classiques : une faible complexite à chaque iteration, une vitessse de convergence qui n’est pas lie à la deuxieme valeur propre de l’operateur mais surtout il encadre à chaque iteration la distribution stationnaire et cet encadrement devient plus precis à chaque iteration. Il permet donc un compromis temps/precision et il est adapte à la verification de proprietes de comparaison sur les recompenses stationnaires. De plus, quand on lui fournit une borne par element de la matrice de la chaine, il retourne (sous des contraintes techniques que l’on precisera) une borne par element de la distribution stationnaire.
Travail en collaboration avec A. Busic (Inria TREC)