Ce sujet comprend trois parties. Les résultats généraux du I.A sont utilisés dans la partie II et dans la souspartie III.A. Le III.B. 2 peut être traité indépendamment du III.B.1.
Notations
désigne l'ensemble des entiers naturels et l'ensemble des nombres réels.
Pour et deux entiers naturels, désigne l'ensemble des entiers tels que .
Pour un entier naturel non nul, désigne l'ensemble des matrices carrées d'ordre à coefficients réels et désigne l'ensemble des matrices orthogonales d'ordre . On note la matrice identité d'ordre .
Pour une matrice de , on note sa transposée.
Le module d'un nombre complexe est noté .
Définitions
Un graphe orienté est un ensemble où est un ensemble fini dont les éléments s'appellent les sommets du graphe et où . Les éléments de s'appellent les arêtes orientées du graphe .
Si , est l'arête orientée reliant le sommet au sommet . Si , on dit que est un sommet voisin de s'il existe une arête orientée reliant à , c'est-à-dire si .
On note que peut être un sommet voisin de lui-même ( ) et que peut être un voisin de alors que n'est pas un voisin de si alors que .
I Marche aléatoire sur un graphe
On considère un graphe orienté fini dont les sommets sont numérotés de 1 à .
Un point se déplace aléatoirement d'un sommet à un autre de ce graphe en suivant les arêtes orientées du graphe. Le nombre d'étapes de cette marche aléatoire peut tendre vers l'infini. À chaque étape, le point se déplace du sommet où il se trouve vers l'un de ses sommets voisins de façon équiprobable. Ceci entraine notamment que la probabilité de passer du sommet au sommet ne dépend pas du rang de l'étape.
Pour , on note , la probabilité que le point passe du sommet au sommet ; en particulier, s'il n'y a pas d'arête reliant à . La matrice dont le coefficient de la ligne et de la colonne est égal à est notée . Cette matrice s'appelle la matrice de transition du graphe.
Pour , on note le vecteur ligne , où, pour est la probabilité que le point soit sur le sommet à l'étape de rang .
I.A - Résultats généraux
Q 1. Justifier que, pour tout entier naturel .
Q 2. Montrer que, pour tout tout entier naturel .
Q 3. En déduire, pour tout entier naturel , une expression de en fonction de et .
Q 4. On suppose que la suite de vecteurs converge vers un vecteur . Montrer que , que pour tout et que .
I.B - Marche aléatoire sur un tétraèdre
Dans cette sous-partie, on considère le graphe orienté où
La figure 1 représente ce graphe en version complète à gauche et en version simplifiée à droite. Les sommets sont représentés par des cercles et l'arête orientée reliant le sommet au sommet , par une flèche de vers . Par la suite, nous utiliserons la représentation simplifiée dans laquelle si le graphe comporte les deux arêtes orientées ( ) et ( ) elles sont représentées par un seul trait avec une flèche à chaque extrémité.
Figure 1
On suppose que, lorsque le point est sur l'un des sommets du graphe, il a la même probabilité de se rendre sur chacun des trois autres sommets du graphe.
On pose
Q 5. Exprimer la matrice de transition en fonction de et .
Q 6. Démontrer qu'il existe une matrice telle que
Q 7. Montrer que la suite de matrices converge et identifier géométriquement l'endomorphisme canoniquement associé à la matrice limite.
Q 8. Montrer que, quel que soit le vecteur ligne , où pour est la probabilité que le point soit au départ sur le sommet , la suite converge vers le vecteur ligne .
I. - Marche aléatoire sur une pyramide tronquée à base carrée
Dans cette question, on suppose que est le graphe représenté figure 2.
On rappelle que, lorsque le point est sur l'un des sommets du graphe, il a la même probabilité de se rendre sur chacun des sommets à qui il est relié. On suppose qu'au départ, le point est sur le sommet 1 , de sorte que
On note et .
Q 9. Donner la matrice de transition de ce graphe et calculer
Figure 2
Q 10. Montrer que, si le point se trouve sur un sommet de la partie à une étape donnée, il se trouvera sur un sommet de la partie à l'étape suivante et que, s'il se trouve sur un sommet de à une étape donnée, il se trouvera sur un sommet de à l'étape suivante.
Q 11. La suite de vecteurs est-elle convergente ?
II Matrices stochastiques et distributions de probabilité
Définitions
Soit un vecteur de . On dit que est une distribution de probabilité si pour tout , et .
Soit une matrice de . On dit que est une matrice stochastique si chaque ligne de est une distribution de probabilité.
II.A -
Q 12. Soit , dont tous les coefficients sont positifs ou nuls. Montrer que est une matrice stochastique si et seulement si
Q 13. Montrer que la matrice de transition d'un graphe (définie dans la partie I) est une matrice stochastique et que, pour tout entier naturel , le vecteur , lui aussi défini dans la partie I , est une distribution de probabilité.
II.B -
Soient et deux matrices stochastiques, une distribution de probabilité et .
Q 14. Montrer que est une distribution de probabilité.
Q 15. Montrer que est une matrice stochastique.
Q 16. Montrer que est une matrice stochastique.
II. C -
Soit une matrice stochastique de et une valeur propre (réelle ou complexe) de . On note les composantes (réelles ou complexes), dans la base canonique, d'un vecteur propre associé à .
Q 17. Soit tel que . Montrer que . En déduire que .
Q 18. Soit . Montrer que . Donner une interprétation géométrique de ce résultat et montrer que, si tous les termes diagonaux de sont strictement positifs, alors 1 est la seule valeur propre de de module 1.
II.C.2)
On suppose désormais que tous les coefficients de la matrice stochastique sont strictement positifs.
Q 19. Démontrer que .
Si désigne les composantes (réelles) dans la base canonique d'un vecteur de , on pourra utiliser .
Q 20. En déduire qu'il existe au plus une distribution de probabilité invariante par , c'est-à-dire vérifiant .
On pose .
On s'intéresse à la suite des puissances de . On note le coefficient de la matrice situé à la ligne et la colonne .
Pour tout , on pose
Dans les quatre questions suivantes, est un entier fixé dans et est fixé dans .
Q 21. Démontrer les inégalités .
Q 22. Démontrer qu'il existe un couple tel que
Q 23. Démontrer qu'il existe un couple tel que
Q 24. En déduire que .
Q 25. Démontrer que la suite converge vers une matrice stochastique dont toutes les lignes sont égales.
On note la ligne .
Q 26. Démontrer que, .
Q 27. Démontrer que la suite converge vers , quelle que soit la distribution de probabilité initiale .
Q 28. Démontrer que est l'unique distribution de probabilité invariante par , c'est-à-dire vérifiant .
III Le graphe du web
On modélise le web par un graphe orienté à sommets représentant chacun une page du web et dont les arêtes orientées représentent les liens hypertextes entre celles-ci. Lorsque la page contient au moins un lien vers la page , on dit que la page pointe vers la page . Cette situation est modélisée par l'existence de l'arête orientée de vers , notée . On dit que est une arête sortante de et une arête entrante de . Si aucun lien de la page ne pointe vers la page , on note .
Pour tout entier désigne le nombre d'arêtes sortantes de la page , c'est-à-dire le nombre de pages vers laquelle elle pointe. On suppose qu'aucune page ne pointe vers elle-même.
Les moteurs de recherche effectuent un classement entre les différentes pages du web à partir d'une mesure d'importance attribuée à chacune d'elles. Cette mesure d'importance s'appelle la pertinence de la page. On se propose d'étudier deux algorithmes permettant de mesurer la pertinence de chaque page du web.
On appelle pertinences des pages du web les éléments de toute suite finie vérifiant les deux conditions suivantes :
(i) la pertinence de la page est une fonction croissante de la pertinence de chacune des pages qui pointent vers elle ;
(ii) la contribution de la page dans la pertinence de chacune des pages vers lesquelles elle pointe est une fonction décroissante de (voir définition ci-dessus).
III.A - Premier modèle de navigation sur le web
On suppose qu'un surfeur navigue sur le web de la manière suivante : lorsqu'il se trouve sur la page ,
si la page pointe vers d'autres pages, il se dirige au hasard, de manière équiprobable, vers l'une de ces pages ;
si la page ne pointe vers aucune page, il reste sur la page .
Q 29. Vérifier que la matrice de transition associée à ce modèle de navigation est la matrice avec
III.B - L'algorithme PageRank
Selon le modèle précédent, lorsque le surfeur arrive sur une page ne comportant aucun lien vers d'autres pages, il lui est impossible de quitter cette page. Ce modèle n'étant pas conforme à la réalité, on décide de remplacer la matrice par la matrice
où est la matrice de dont tous les coefficients sont égaux à 1, est la matrice stochastique décrite à la question 29 et est un réel de , appelé facteur d'amortissement.
III.B.1)
Q 30. Montrer que est une matrice stochastique dont tous les coefficients sont strictement positifs.
Q 31. Dans le modèle de navigation admettant pour matrice de transition, donner la probabilité de quitter une page ne contenant aucun lien vers une autre page.
Soit une distribution de probabilité. On définit la suite par pour tout entier naturel .
Q 32. Démontrer que la suite converge et que sa limite vérifie les conditons (i) et (ii) décrites dans l'introduction de cette partie. Elle fournit donc des pertinences pour les pages du web. On exprimera la
pertinence de chaque page en fonction de celles des pages qui pointent vers elle en distinguant les pages qui pointent vers une autre page et les autres.
Connu sous le nom de PageRank cet algorithme de calcul des pertinences a été inventé par Sergey Brin et Larry Page, fondateurs de Google.
III.B.2) Calcul de
Dans la pratique, on se contente d'approcher par pour une valeur de suffisamment grande.
On suppose que le module numpy de Python a été importé à l'aide de l'instruction import numpy as np. Ceci donne ainsi accès aux fonctions suivantes:
np.identity(n) crée , la matrice identité d'ordre n;
A. shape donne, sous forme de couple, la taille du tableau A, par exemple np.identity (5). shape ;
np. calcule, le produit matriciel de et si et sont deux tableaux à deux dimensions compatibles avec le produit matriciel.
L'algorithme naïf de calcul de repose sur sa définition, à savoir :
Q 33. Écrire une fonction Python puissance1 (B, k) qui prend en argument une matrice carrée B et un entier naturel k et renvoie la matrice calculée en utilisant l'algorithme naïf.
L'algorithme d'exponentiation rapide repose sur le principe suivant :
Q 34. Écrire une fonction Python puissance2(B, k) qui prend en argument une matrice carrée B et un entier naturel et renvoie la matrice calculée à partir de l'algorithme d'exponentiation rapide.
Q 35. On suppose que et on note l'unique entier tel que . Pour chacun des appels puissance1 ( ) et puissance2 ( ), calculer le nombre d'appels à la fonction np. dot, dans le pire et dans le meilleur des cas.
Centrale Mathématiques 1 PSI 2021 - Version Web LaTeX | WikiPrépa | WikiPrépa
