Algorithme Page Rank — Les-mathematiques.net The most powerful custom community solution in the world

Algorithme Page Rank

Modifié (11 Feb) dans Combinatoire et Graphes
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.

Réponses

  • 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.$$
  • Modifié (11 Feb)
    Bonsoir Rebellin
    J'ai commencé par dessiner un arbre, puis j'ai écrit ça, j'espère que c'est juste.





Connectez-vous ou Inscrivez-vous pour répondre.
Success message!