Recherche état stable

RIKI · November 2019

Bonjour,
je trouve tantôt le théorème 1, tantôt le théorème 2. Sont-ils équivalents ?
(je ne pense pas ... je pense que le théorème 2 implique le théorème 1 mais qu'on n'a pas forcément la réciproque).
Qu'en pensez-vous ?

Théorème 1 : pour tout graphe probabiliste "fortement" connexe à 2 ou 3 sommets, de matrice de transition M, il existe un unique état stable P=(x y) ou (x y z) solution de l'équation matricielle P*M=P.
Cet état stable est indépendant de l'état initial. Et si n tend vers l'infini, alors l'état probabiliste P_n tend vers l'état stable P.

Théorème 2 : pour tout graphe probabiliste d'ordre 2 ou 3 dont la matrice de transition ne comporte pas de 0, l'état Pn tend vers un état P indépendant de l'état initial P₀.
P vérifie P=P*M et est appelé état stable.

Merci !
C.

Titi le curieux · November 2019

Salut,
Je crois bien que le premier théorème implique le second, puisque une matrice strictement positive est fortement connexe. Il y a cependant un problème, le second théorème est vrai, mais il manque des conditions au premier pour qu'il soit vrai: exemple à deux sommets avec $M=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$
Une fois débarrassé de la "périodicité", qu'on trouve dans le contre-exemple, le théorème devient généralisable bien au-delà de 3 sommets.

RIKI · November 2019

Bonjour,
je dirais plutôt que le thm 2 implique le thm 1 puisqu'une matrice strictement positive est fortement connexe.
Par contre, si un graphe avait la matrice de transition M que vous indiquez(avec 2 zéros), il serait bien fortement connexe.
Mais vous me faites remarquer alors (merci) que le thm 1 vérifiant pourtant les bonnes hypothèses d'application admettrait comme état stable P=(0,5 0,5) ce qui est contradictoire avec la limite de Pn qui n'existerait pas si l'état initial était différent de (0,5 0,5).
Bref, le thm1 n'est pas valable dans ce cas. N'est-ce pas ?
Qu'appelez-vous "périodicité" ?
Merci d'avance,
C.

RIKI · November 2019

Je viens de comprendre mon erreur de raisonnement, excusez-moi !
C'est bien thm 1 => thm 2 car l'ensemble des graphes fortement connexes contient l'ensemble des graphes dont la matrice de transition est strictement positive.
Merci de m'aider pour le reste.
C.

malavita · November 2019

Bonsoir,

qu'entends tu par fortement connexe ?

A+

F.

Titi le curieux · November 2019

Salut,
A priori, ce n'est pas très canon, mais en ce qui me concerne, j'avais interprété: quelques soient les points A et B, il existe un chemin pour aller du point A au point B, ou de manière équivalente que tout sous-graphe est composante fortement connexe. Le terme conventionnel serait donc irréductible, mais en ce qui me concerne, je trouve l'expression vachement éloquente et si peut discuter le dictionnaire, je vote pour qu'on dise fortement connexe plutôt qu'irréductible, car j'aime les expressions très descriptives, ça permet de passer dessus sans même s'en rendre compte, et ce, dés la première lecture (et ne pas buter sur les mots, ça facilite l'apprentissage!).

malavita · November 2019

Ok, donc le graphe A->B est connexe mais pas fortement connexe ?

Du coup, tes théorèmes ne semblent pas équivalents, le premier concernant les graphes fortement connexes et le second les graphes "très fortement connexes": quelques soient $u,v$ sommet de $G$ il existe une arête de poids non nul reliant $ u$ à $v$.

A+

F.