Chapitre 4 — Les chaînes de Markov
Always buy an unowned property if it is an orange property (always block this group if you can).
Avant d’attaquer l’objet central de cette partie, à savoir le(s) PageRank(s), il nous semble nécessaire de faire un rappel théorique des techniques que nous allons utiliser tout au long des pages à venir.
Andreï Markov (1856-1922), mathématicien russe, est connu pour avoir défini et étudié les processus stochastiques discrets sans mémoire, également connu sous le nom de chaînes de Markov. Cet outil du début du siècle dernier est fondamental pour comprendre l’idée du PageRank, c’est pourquoi nous allons brièvement rappeler les résultats essentiels1.
4.1 Définitions
On appelle processus aléatoire, ou stochastique, discret un ensemble de variables aléatoires , avec . peut par exemple représenter la position sur le plateau de jeu d’un joueur de Monopoly à l’instant .
Les chaînes de Markov discrètes sont des cas particuliers de processus stochastique discret à valeur discrète dont le futur ne dépend que du présent (pas du passé) : les états précédant l’état présent ne jouent aucun rôle. Si on appelle l’ensemble des valeurs (ou états) que peuvent prendre les variable , la caractérisation mathématique d’une chaîne de Markov est l’égalité, pour tout ,
En d’autres termes, la probabilité d’être dans l’état à l’instant ne dépend que de la valeur prise à l’instant , et pas des valeurs antérieures. A priori, cette probabilité peut ne pas être la même selon l’instant considéré. La chaîne de Markov peut donc se définir par les probabilités de transition entre deux états à un instant :
Dans tout ce mémoire, nous nous restreindrons au cas où les probabilités de transitions ne dépendent pas de l’instant considéré. La chaîne de Markov correspondante est alors dite homogène.
Si est fini (nous prendrons alors ), il est commode de considérer la matrice des transitions . est une matrice stochastique par ses lignes, c’est-à-dire que . Ceci est dû au fait que le processus est complètement fermé, et que si l’on est dans l’état à l’instant , alors on sera dans à l’instant .
La matrice de transition permet d’obtenir l’évolution de notre processus. En effet, si on appelle le vecteur représentant la distribution des états à l’instant (), alors la proposition suivante donne en fonction de et de .
Proposition 4.1.
, où est l’opérateur de transposition.2
Preuve.
Il suffit de montrer que, pour un quelconque, on a ; Proposition 4.1 n’est alors que l’application d’une récurrence immédiate. Le résultat voulu vient du fait que :
□
4.2 Côté graphe, côté matrice
Nous venons de voir que les matrices stochastiques sont un moyen à la fois élégant et compact de rendre compte de l’évolution d’une chaîne de Markov, mais ce n’est pas le seul. La représentation en terme de graphe orienté pondéré est également très utile, et il est confortable de pouvoir passer de l’une à l’autre suivant les besoins.
À toute matrice de taille , il est possible d’associer un graphe orienté pondéré à sommets, dont les arêtes sont l’ensemble des couples tels que , pondérées chacune par leur coefficient associé.
Réciproquement, à tout graphe orienté pondéré peut correspondre la matrice définie par :
Dans le cas d’un graphe dont les arêtes sont non pondérées, en les considérant comme implicitement de poids , on retrouve la matrice d’adjacence.
Parfois, le passage de la vision matricielle à la représentation sous forme de graphe se limite à une simple réécriture : ainsi, si la caractérisation d’une matrice stochastique3 est
celle d’un graphe représentant une chaîne de Markov homogène est
Il arrive cependant que les deux approches correspondent vraiment à deux visions subtilement différentes d’un même problème. Ainsi, dire qu’une matrice positive est irréductible revient à dire que
Au niveau du graphe correspondant, cela revient à dire que pour tout couple de sommets , il existe un chemin (de longueur ) reliant à . En d’autres termes, le caractère irréductible de la matrice se traduit par la forte connexité du graphe.
Enfin, signalons qu’une chaîne de Markov est dite ergodique si la matrice correspondante est irréductible et apériodique.
4.3 Évolution d’une chaîne de Markov homogène
Afin d’étudier l’évolution à long terme d’une chaîne de Markov, on peut se demander s’il est possible d’avoir des propriétés de convergence. Or, ceci est acquis grâce au théorème suivant.
Théorème 4.1.
Soit une matrice stochastique.
- Le rayon spectral de est , et c’est une valeur propre.
- Si est irréductible, alors il existe un unique vecteur de probabilité vecteur propre de pour la valeur propre , et est strictement positif, c’est-à-dire que toutes ses composantes sont strictement positives.
- Si est irréductible et apériodique, alors toutes les valeurs propres autres que sont de module strictement inférieur à .
Preuve.
-
est valeur propre, associée au vecteur propre .
De plus, si l’on considère un vecteur quelconque, nous avons toujours
avec la convention .
Ceci implique que toute valeur propre de est inférieure à .
-
Si est irréductible, alors on entre dans le cadre du théorème de Perron-Frobenius (voir Annexe A), qui assure qu’il existe, à homothétie près, un unique vecteur propre4 de pour la valeur propre . Ce vecteur étant strictement positif, on peut après normalisation le considérer comme un vecteur de probabilité.
-
D’après le théorème de Perron-Frobenius, si est une valeur propre de vérifiant , alors est une racine -ième de l’unité, où est la cyclicité de . Si est apériodique, on a alors forcément . Toutes les valeurs propres de autres que ont donc une norme strictement inférieure à 1.
□
D’après le Théorème 4.1, il est maintenant possible de connaître le comportement asymptotique d’une chaîne de Markov homogène.
Théorème 4.2.
Soit une matrice stochastique irréductible apériodique de taille représentant une chaîne de Markov homogène. Si on appelle le vecteur de probabilité propre droit de pour la valeur (son existence ainsi que son unicité sont garanties par le théorème de Perron-Frobenius), alors
où est le vecteur ligne de taille ne comportant que des .
Preuve.
Il s’agit d’une simple application de la méthode de la puissance, ou méthode de Jacobi. En effet, comme est valeur propre de dimension , on peut décomposer sur l’espace propre engendré par d’une part et sur l’espace associé aux autres valeurs propres d’autre part (qui n’est pas forcément un espace propre). Ainsi, il existe une matrice de passage inversible telle que
où est une matrice de rayon spectral strictement inférieur à 1 (les valeurs propres de sont celles de sauf ). Le rayon spectral de implique que converge de manière géométrique vers . converge donc de manière géométrique vers :
Cette matrice, que nous appellerons , est de fait une projection, puisque . L’espace de projection est de dimension , car la matrice est de rang . Comme par passage à la limite, on a , la droite de projection est celle engendrée par . est également une matrice stochastique (car limite de matrices stochastiques). En particulier, si est le vecteur de probabilité sûre en , défini par , alors
d’où .
□
Le comportement asymptotique de la chaîne de Markov homogène associée est alors donné par le Corollaire 4.1 :
Corollaire 4.1.
Soit une distribution initiale de probabilité quelconque. La distribution des états à l’instant converge, quand tend vers l’infini, vers .
Preuve.
Pour toute distribution de probabilité , on a .
□
Pour le lecteur désireux de se familiariser avec les applications de l’étude asymptotique des chaînes de Markov, la section suivante est consacrée à une petite analyse des probabilités dans le jeu de Monopoly (marque déposée).
4.4 Intermezzo : Le Monopoly™ selon Markov
| N° | Nom | Groupe | N° | Nom | Groupe |
| 0 | Case Départ | 21 | Matignon | rouge | |
| 1 | Belleville | brun | 22 | Carte Chance | |
| 2 | Caisse de Communauté | 23 | Malesherbes | rouge | |
| 3 | Lecourbe | brun | 24 | Henri-Martin | rouge |
| 4 | Impôts | 25 | Gare du Nord | ||
| 5 | Gare Montparnasse | 26 | Saint-Honoré | jaune | |
| 6 | Vaugirard | bleu clair | 27 | Bourse | jaune |
| 7 | Carte Chance | 28 | Cie des Eaux | ||
| 8 | Courcelles | bleu clair | 29 | La Fayette | jaune |
| 9 | République | bleu clair | 30 | Allez en Prison | |
| 10 | Simple visite | 31 | Breteuil | vert | |
| 11 | La Villette | violet | 32 | Foch | vert |
| 12 | Cie Électricité | 33 | Caisse de Communauté | ||
| 13 | Neuilly | violet | 34 | Capucines | vert |
| 14 | Paradis | violet | 35 | Gare Saint-Lazare | |
| 15 | Gare de Lyon | 36 | Carte Chance | ||
| 16 | Mozart | orange | 37 | Champs-Élysées | bleu foncé |
| 17 | Caisse de Communauté | 38 | Taxe de Luxe | ||
| 18 | Saint-Michel | orange | 39 | La Paix | bleu foncé |
| 19 | Pigalle | orange | 40 | Prison | |
| 20 | Parc Gratuit |
Une question à se poser est : quelles sont les chances de tomber sur une case donnée ? Si certaines cases sont plus probables que d’autres, on comprend bien qu’elles auront un intérêt stratégique accru. On peut voir l’évolution de la position d’un joueur au fil des lancers de dés comme une chaîne de Markov. Ian Stewart [Ste96] associe à chaque état-case 11 transitions possibles correspondant aux résultats possibles d’un lancer de dés, de 2 à 12. La probabilité de chaque transition est celle d’obtenir le résultat avec deux dés. Ian Stewart conclut que la matrice stochastique représentant la chaîne de Markov est circulante, et que la distribution de probabilité asymptotique est la distribution uniforme. En fait, si on regarde de plus près les règles, on s’aperçoit que tous les états ne sont pas équivalents, et que la distribution de probabilité limite n’est pas forcément équiprobable.
4.4.1 Bref rappel des règles et notations
Par convention, on considérera qu’il y a 41 cases : cela va de la case Départ (numéro 0) à la case Rue de la Paix (numéro 39), la case Prison ayant le numéro 40, la case Simple Visite ayant le numéro 10. Le Tableau 4.1 récapitule les différentes cases, avec le nom et la couleur de lotissement éventuelle.
Une partie commence sur la case Départ. À chaque tour, le joueur lance deux dés. Au bout de trois doubles consécutifs, le joueur va en prison. S’il tombe sur une case Chance ou bien Caisse de Communauté, il tire une carte dans la pile correspondante, et ce tirage est éventuellement suivi d’un effet immédiat au niveau de la position. Quand on est en prison, on peut en sortir gratuitement en faisant un double dans les trois tours qui suivent celui de l’emprisonnement, sinon on doit payer pour sortir. On peut sortir avant la fin des trois tours en payant.
Voici la liste détaillée des cartes Chance : 1 envoie en prison, 1 envoie vers l’avenue Henri-Martin, 1 envoie vers boulevard de la Villette, 1 envoie vers la rue de la Paix, 1 envoie vers la gare de Lyon, 1 envoie sur la case Départ, 1 Reculez de trois cases. Il y a 9 autres cartes Chance qui n’ont aucune influence sur la position.
Voici maintenant la liste détaillée des cartes Caisse de Communauté : 1 Retournez à Belleville, 1 envoie en prison, 1 envoie sur la case Départ, 1 possibilité de tirer une carte Chance (alternative avec une amende). Il y a 12 autres cartes Caisse de Communauté qui n’ont aucune influence sur la position.
4.4.2 Matrice des transitions
À cause des règles, tous les états n’ont pas les même transitions : ainsi, toute transition vers la case 30 (Allez en Prison) doit en fait être remplacée par une transition vers la case 40 (Prison). De même, il faut considérer pour toute transition vers les cases Chance ou Caisse de Communauté, les éventuelles redirections. Il y a aussi le problème des doubles : le processus stochastique utilise une mémoire (nombre de tours en prison ou nombre de doubles consécutifs déjà faits) et n’est donc pas un vrai processus de Markov. Mais comme la mémoire est finie (3 lancers), on peut se ramener à un processus sans mémoire en considérant un espace à 123 états5 : 120 états du type représentant être sur la case en ayant déjà fait doubles consécutifs, et 3 états prison représentant les trois tours que l’on peut passer en prison. Il faut d’ailleurs noter que si l’on paie, comme on a souvent intérêt à le faire en début de partie, on ne passe qu’un tour en prison, et les transitions sont donc modifiées. Il faut donc considérer les transitions pour une stratégie prison et celle pour une stratégie liberté6.
On arrive ainsi à écrire, pour chacune des 2 stratégies considérées, une matrice stochastique décrivant la stratégie en question. La Figure 4.2 représente ainsi de manière graphique la matrice correspondant à la stratégie prison.
4.4.3 Probabilités asymptotiques et conclusion
Une fois la matrice des transitions calculée, grâce au Corollaire 4.1, on sait qu’il suffit d’itérer ( étant par exemple la distribution équiprobable) pour avoir une convergence vers la distribution asymptotique. Il n’y a alors plus qu’à revenir dans l’espace à cases pour avoir des résultats exploitables, lesquels sont représentés Figure 4.3. Pour compléter cette étude, il faudrait maintenant prendre en compte les prix de vente et les loyers pour avoir un temps moyen de retour sur investissement, sans oublier de considérer le pouvoir d’achat, mais cela n’est plus du ressort des matrices de Markov7. Contentons-nous pour conclure de ces quelques remarques :
- La case Allez en prison a une probabilité nulle, puisqu’on n’y reste pas.
- De même, les cases Chance et Caisse de Communauté ont une probabilité assez faible, à cause des cartes de déplacement immédiat.
- Les deuxième et troisième quarts du plateau ont globalement des probabilités plus grandes, à cause de la sortie de prison. Cela confère un intérêt certains aux propriétés qui s’y trouvent (les groupes orange et rouge en particulier).
- Paradoxalement, on a plus de chance d’atterrir sur la Compagnie d’Électricité en choisissant de rester en prison. Pourquoi ce résultat contre-intuitif ? Avec la stratégie liberté, la probabilité de tomber dessus en sortant de prison est de . Avec la stratégie prison, cette probabilité devient …
4.5 Matrices (sous-)stochastiques : cas général
Au cours des chapitres suivants, nous aurons parfois affaire à des matrices présentant une périodicité, ou qui sont non irréductibles, ou encore sous-stochastiques8, les ou n’étant pas forcément exclusifs. Nous nous proposons donc d’étudier la viabilité du Corollaire 4.1 sous ces différentes hypothèses.
4.5.1 Matrices non irréductibles
Intéressons-nous tout d’abord au cas où est stochastique, mais non irréductible. Cela veut dire que le graphe correspondant n’est pas fortement connexe. Considérons alors la décomposition en composantes fortement connexes de : . Chaque composante a exactement une des deux propriétés suivantes :
- Soit . La composante et ses états sont alors dits transitoires.
- Soit . La composante et ses états sont alors dits récurrents.
Si l’on quotiente selon ses composantes fortement connexes, le graphe réduit donne un ordre partiel sur les composantes (car il n’y a pas de circuit) dont les composantes récurrentes sont les maxima.
Par exemple, dans le graphe de la Figure 4.4, il y a quatre composantes fortement connexes, , , et . et sont transitoires, alors que et sont récurrentes.
Nous allons maintenant réordonner les états comme suit : d’abord les états transitoires (toutes composantes confondues), puis les états d’une première composante fortement connexe récurrente, …, jusqu’au états de la dernière composante fortement connexe récurrente. Dans ce réarrangement des états, la matrice stochastique associée (que nous continuerons d’appeler ) s’écrit maintenant :
où est une matrice sous-stochastique, non stochastique, de taille , une matrice positive non nulle de taille , et les des matrices stochastiques irréductibles de taille .
Théorème 4.3.
Soit une matrice stochastique réduite selon ses composantes fortement connexes transitoires et récurrentes. est de la forme
où est une matrice sous-stochastique, non stochastique, de taille , une matrice positive non nulle de taille , et
les étant des matrices stochastiques irréductibles de taille .
Si toutes les matrices sont apériodiques, alors les puissances itérées de convergent. Plus précisément, on a :
avec
où est le vecteur de probabilité de taille vérifiant , et
Corollaire 4.2.
Pour toute distribution de probabilité sur , converge quand tend vers l’infini, et le vecteur limite est une distribution de probabilité appartenant à l’espace à dimensions engendré par le plongement canonique des dans .
Remarque 4.1.
Quand tous les ne sont pas apériodiques, il n’y a pas a priori de convergence. La technique que nous allons voir en Section 4.5.2 permet quand même de s’assurer une convergence à moindre coût.
Preuve.
On constate tout d’abord que
Lemme 4.1.
et la convergence est géométrique. De plus, est inversible, et son inverse vaut .
En effet, étudions de plus près la structure de . Nous allons réordonner les états par composantes fortement connexes, en commençant par celles qui, dans le graphe quotient , n’ont pas d’arête entrante (composantes ultra-transitives), et en triant par éloignement selon la distance aux composantes ultra-transitives. La matrice est alors de la forme :
où les sont des matrices irréductibles sous-stochastiques, non stochastiques (par convention, la matrice unidimensionnelle est considérée comme irréductible). D’après la Section 4.5.3, chaque matrice de la diagonale principale a un rayon spectral strictement inférieur à . Comme la structure de est triangulaire, le rayon spectral de est . Ceci assure que converge géométriquement vers .
Comme n’est pas valeur propre de , est inversible. Or, pour tout , on a :
d’où
On en déduit que
ce qui achève la démonstration du lemme.
Revenons à notre démonstration. Il est maintenant acquis que . Avec l’hypothèse d’apériodicité des , nous avons aussi .
Il nous reste à prouver que
Or, on a
Le premier terme converge vers . Quant au deuxième, on a :
Le premier des deux termes de droite tend vers à cause de la convergence géométrique de vers , le deuxième à cause de la convergence (également géométrique) de . Ceci assure la convergence vers du terme de gauche. C.Q.F.D.
□
4.5.2 Matrices périodiques
Si une matrice stochastique est périodique, il n’y a a priori pas de convergence. On peut par exemple penser à la matrice circulante
Les différentes itérations de décrivent une orbite de taille correspondant aux racines -ièmes de l’unité, et il n’y a en particulier pas convergence au sens classique, bien qu’il existe une convergence au sens de Césaro ( converge).
La convergence au sens de Césaro pourrait nous permettre de retrouver la direction propre associée à la valeur propre positive maximale, mais ce n’est pas nécessaire : comme le montre le Théorème 4.4, il est possible de se ramener à une convergence «classique».
Théorème 4.4.
Soit une matrice stochastique irréductible de taille , éventuellement périodique. Soit l’unique vecteur de probabilité tel que . Pour tout , on a
Corollaire 4.3.
Soit un vecteur de probabilité quelconque. Si on pose , alors
Preuve.
La matrice définie par est stochastique, irréductible, et apériodique, à cause de la présence de circuits de longueur . converge donc vers , où est l’unique distribution de probabilité vérifiant . Comme , on a .
C.Q.F.D.
□
4.5.3 Matrices sous-stochastiques
Le cas des matrices strictement sous-stochastiques semble a priori simple à résoudre :
Théorème 4.5.
Soit une matrice sous-stochastique, non stochastique, irréductible de taille . Alors les puissances itérées de cette matrice tendent vers :
Preuve.
est inférieure et non égale à une matrice stochastique irréductible. D’après le (d) du théorème de Perron-Frobenius (voir Annexe A), son rayon spectral est strictement inférieur à , ce qui assure le résultat, à savoir, si on appelle le rayon spectral, une convergence dominée par une suite géométrique de raison .
□
Remarque 4.2.
Une matrice sous-stochastique mais non stochastique correspond à une chaîne de Markov mal définie, dans le sens où toutes les transitions possibles n’ont pas été données. Par analogie avec les automates, on parlera de chaîne de Markov incomplète9. Dans ce cas, pour toute distribution de probabilité, , résultat peu satisfaisant en termes d’informations utiles. Ce problème est crucial dans le cadre des calculs de PageRank, et les solutions pour «compléter» une matrice sous-stochastique seront données plus en détails au Chapitre 5.
Remarque 4.3.
Le Théorème 4.5 peut en fait s’appliquer à toute matrice sous-stochastique inférieure et non égale à une matrice stochastique irréductible. Nous appellerons de telles matrices des matrices sous-irréductibles.
Cependant, comme nous le verrons au Chapitre 5, l’étude de la valeur propre maximale d’une matrice sous-irréductible ainsi que de l’espace propre associé est importante pour l’étude du PageRank, c’est pourquoi nous allons développer un peu.
Valeur propre maximale et espace propre associé d’une matrice positive
Théorème 4.6.
Soit une matrice positive10.
Soient la décomposition en composantes fortement connexes du graphe associé à .
On définit le rayon spectral d’une composante comme étant le rayon spectral de . On appellera composante pseudo-récurrente de toute composante vérifiant :
- est maximal : , .
- les composantes accessibles à partir de ont un rayon spectral strictement inférieur : 11, .
Alors :
- Le rayon spectral de est égal au rayon spectral maximum des composantes fortement connexes de .
- Il existe une valeur propre maximale qui est positive (c’est la seule si les composantes pseudo-récurrentes sont apériodiques). La dimension de l’espace propre associé est alors égal au nombre de composantes pseudo-récurrentes.
- Si est une composante pseudo-récurrente de , il existe un vecteur propre positif de support associé à la valeur propre maximale.
Corollaire 4.4.
S’il existe une seule composante pseudo-récurrente , et si tous les sommets sont accessibles de cette composante (), alors les espaces propres associés aux valeurs propres maximales12 sont de dimension 1, et il existe un vecteur propre positif de support associée à la valeur propre maximale positive. On dira alors que est pseudo-irréductible.
Preuve.
La preuve est en fait très similaire à celle du Théorème 4.3 pour les matrices stochastiques non-irréductibles, même s’il n’est plus possible d’avoir un résultat de convergence des puissances de . Grâce à l’ordre partiel induit par le graphe quotient des composantes fortement connexes, il est possible de rendre triangulaire par blocs selon les composantes fortement connexes : quitte à se placer dans la bonne permutation, on peut écrire
où les sont les matrices de transition entre composantes et .
Cette décomposition triangulaire assure que le rayon spectral de est égal au rayon spectral maximum des différentes composantes . En fait, en appliquant le théorème de Perron-Frobenius sur chacune des composantes fortement connexes, il apparaît qu’il existe une valeur propre égale au rayon spectral, et que sa multiplicité est égale au nombre de composantes de rayon maximal.
Si est pseudo-récurrente, alors la multiplicité de dans est . Il existe donc à homothétie près un unique vecteur propre associé à dans . Comme est stable par , le plongement de dans est un vecteur propre de . Par construction, on a également . D’après le théorème de Perron-Frobenius appliqué sur , les composantes de sont strictement positives à homothétie près. De proche en proche, l’égalité montre que est strictement positif.
Pour chaque composante pseudo-récurrente de , il existe donc un vecteur propre positif de support associé à .
Il reste à montrer qu’il n’existe pas de vecteur propre associé à en dehors de l’espace engendré par les vecteurs propres associés aux composantes pseudo-récurrentes. Il suffit pour cela de constater que toute composante de rayon maximal non pseudo-récurrente génère une structure triangulaire dans l’espace associé à : s’il existe une composante pseudo-récurrente avec , alors contient (dans une base adaptée) un bloc de la forme , avec , ce qui montre qu’il n’est pas possible d’associer un vecteur propre de à .
C.Q.F.D.
□
4.5.4 Cas général : conclusion
Nous venons de voir qu’on peut s’arranger pour trouver un algorithme de convergence même si la matrice n’est ni apériodique, ni irréductible. Notons simplement que dans ce dernier cas, il n’y a pas unicité. En revanche, si la matrice est sous-stochastique, mais non stochastique, le vecteur asymptotique sera nul partout sauf sur d’éventuelles composantes fortement connexes récurrentes à l’intérieur desquelles la matrice est stochastique. La complétion canonique, qui consiste à rajouter un état «poubelle», n’est pas satisfaisante car elle ne change pas fondamentalement le résultat : l’état «poubelle» récupère les probabilités perdues au niveau des composantes sous-stochastiques, mais les valeurs sur les états autres que l’état poubelle ne sont pas modifiées. Heureusement, les divers algorithmes de calcul de PageRank que nous allons étudier maintenant vont nous fournir d’autres méthodes de complétion pour trouver à coup sûr un vecteur ayant toutes les propriétés désirées, qui s’appellera vecteur de PageRank.
- 1Pour une information plus complète sur l’œuvre de Markov, on pourra se reporter à [Sal96, She88].
- 2Dans tout ce mémoire, nous allons user et abuser de l’opérateur de transposition. Pourquoi ne pas travailler directement sur la matrice et ainsi ne pas faire intervenir ? D’une part parce qu’il est plus confortable de considérer qu’un coefficient représente l’action de sur que celle de sur . D’autre part parce que mes restes de classes préparatoires font que je préfère travailler sur les vecteurs colonne plutôt que sur les vecteurs ligne. Enfin parce que c’est généralement la notation d’usage dans la littérature existante.
- 3Lorsque cela n’est pas précisé, nous entendons par matrice stochastique une matrice stochastique par ses lignes, c’est-à-dire une matrice positive telle que la somme de chacune de ses lignes soit égale à .
- 4En fait, il y a deux vecteurs propres, un droit et un gauche, le gauche de étant le droit de et vice versa.
- 5Une solution alternative, proposée par [Col], consiste à estimer pour chaque case la probabilité d’y être arrivé par 2 doubles consécutifs.
-
6D’autres facteurs peuvent également altérer les probabilités de transitions :
- La carte Tirez une Carte Chance ou Payez une Amende de…, qui propose deux stratégies.
- Les cartes Sortez de prison, qui, si elles sont conservées par les joueurs, augmentent légèrement les probabilités de tirer une carte de déplacement.
L’effet de ces variations étant relativement faible, nous nous permettons de ne pas les prendre en compte ici.
- 7Pour avoir une idée des résultats que l’on obtient, voir [Col]. Attention, les résultats correspondent au jeu de monopoly international, qui comporte des cartes différentes de la version française.
- 8Dans ce cas, on ne peut a priori plus parler de chaîne de Markov associée.
- 9En effet, tout comme avec les automates, il est possible de compléter notre chaîne de Markov en rajoutant un état poubelle recevant le défaut stochastique des autres états, et pointant sûrement vers lui-même.
- 10Bien que l’étude que nous allons faire nous intéresse avant tout du point de vue des matrices sous-irréductibles, elle est en effet valable pour toute matrice positive.
- 11Pour , le filtre de , noté , est l’ensemble des pages de accessibles à partir de .
- 12Le pluriel est employé ici pour les éventuelles périodicités. En cas d’apériodicité, il n’y a bien sûr qu’une seule valeur propre maximale.