Algorithme Page Rank

lorentz · February 2022

Bonsoir
Je cherche à déterminer la matrice d'un algorithme, j'ai commencé par établir la matrice du graphe orienté en espérant l'avoir bien écrite.
Par contre je bloque pour calculer les probabilités P(Xn+1=k) sachant que k appartient {1,2,3,4}, je pense que c'est lié à la formule des probabilités totales.
Je ne sais pas comment m'en sortir.
Cordialement, Lorentz.

rebellin · February 2022

Quand tu es en position 1, tu as une chance sur 2 d'aller en position 2 et une chance sur 2 d'aller en position 3, donc la "matrice de transition" $M$ du problème vérifie

$$M_{1,1}=\frac{1}{4}p,~M_{1,2}=\frac{1}{4}p+\frac{1}{2}(1-p)=\frac{1}{2}-\frac{1}{4}p,~M_{1,3}=\frac{1}{4}p+\frac{1}{2}(1-p)=\frac{1}{2}-\frac{1}{4}p,~M_{1,4}=\frac{1}{4}p.$$ Autrement dit :

$$P(X_{n+1}=1|X_n=1)=\frac{1}{4}p,~P(X_{n+1}=2|X_n=1)=\frac{1}{2}-\frac{1}{4}p,~P(X_{n+1}=3|X_n=1)=\frac{1}{2}-\frac{1}{4}p,~P(X_{n+1}=4|X_n=1)=\frac{1}{4}p.$$

Je te laisse écrire les autres lignes de la matrice (c'est-à-dire les autres probabilités conditionnelles). Ensuite tu as la relation de récurrence $$\pi_{n+1}=\pi_n M.$$

lorentz · February 2022

Bonsoir Rebellin
J'ai commencé par dessiner un arbre, puis j'ai écrit ça, j'espère que c'est juste.

Algorithme Page Rank

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 20