Chaînes de Markov récurrentes et transientes

Un chemin est une suite $a_0,\dots,a_n$ de sommets distincts du graphe orienté telle que $(a_{i},a_{i+1})$ est une flèche pour $i=0,\ldots,n-1.$ Et $a_0$ est l'origine et $a_n$ est l’extrémité du chemin.
On écrit $a\leq b$ s'il existe un chemin d'origine $a$ et d’extrémité $b$ ou bien si $a=b$.
Alors $aRb$ défini par $a\leq b$ et $b\leq a$ est une relation d’équivalence.
Si $\mathcal{C}$ est l'ensemble des classes d’équivalence, avec $A$ et $B$ dans $\mathcal{C}$, on écrit $A\leq B$ s'il existe $a\in A$ et $b\in B$ tels que $a\leq b$. Sur $\mathcal{C}$ la relation $\leq$ est une relation d'ordre.

Si le graphe a un nombre fini de sommets, les éléments de toute classe maximale sont récurrents positifs, les autres sont transients.

Prends un graphe à 12 sommets et mets des flèches n'importe comment (rappel la flèche (a,b) est différente de la flèche (b,a)) et exerce toi à trouver les classes et leur ordre partiel et à trouver la ou les classes maximales.

Si le graphe a un nombre infini d'éléments, tout élément d'une classe non maximale est transient. Les autres peuvent être transients, récurrents nuls ou positifs (mais même type pour chacun des éléments d'une même classe maximale).

Ton problème est de maîtriser la combinatoire d'un graphe orienté fini. Alors que c'est pour servir à comprendre une chaîne de Markov donnée par sa matrice de transition. Personne ne va perdre son temps sur internet à mettre des matrices de transition compliquées destinées à apprendre cette combinatoire. Internet va plutôt afficher de grandes matrices, mais avec de la structure supplémentaire. Commence par jouer seule avec un papier et un crayon pour choisir des graphes tordus et maîtriser les définitions plutôt que de dépendre d'internet et d'y gaspiller de l’énergie.