Marches aléatoires sur un graphe, matrices stochastiques et algorithme PageRank
Afficher ou masquer la section
Épreuve de mathématiques 1 du concours Centrale-Supélec 2021 en filière PSI. Le problème étudie des marches aléatoires sur un graphe et le comportement asymptotique des lois de probabilité associées. Il établit un résultat de type Perron-Frobenius pour les matrices stochastiques, puis l'applique au classement des pages du web.
1Partie I : marche aléatoire sur un grapheRésultats généraux sur la matrice de transition, puis deux exemples : le tétraèdre, traité par diagonalisation, et une pyramide tronquée où la suite des lois ne converge pas.
2Partie II : matrices stochastiques et distributions de probabilitéLocalisation des valeurs propres d'une matrice stochastique, dimension du sous-espace propre associé à 1 et convergence des puissances de la matrice.
3Partie III : le graphe du webModèle de navigation, algorithme PageRank avec facteur d'amortissement, puis calcul des puissances d'une matrice en Python par méthode naïve et exponentiation rapide.
Difficulté moyenne. Le jury juge le sujet plutôt long mais progressif, ce qui a permis à tous les candidats de traiter de nombreuses questions, la partie II étant réussie de façon plus contrastée.
Deux tiers des copies environ (moyenne ± écart-type)
Votre note sur 20 à ce sujet, en conditions de concours.
Source : document officiel du concours, épreuve du 20 avril 2021. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.
Ce qu'a observé le jury
6 erreurs relevées
Événements confondus avec des probabilités · Formule des probabilités totales mal citée · Passage à la limite sans continuité
Afficher ou masquer la section
La partie I a été abordée presque entièrement par tous, la partie II largement étudiée avec moins de succès, la partie III moins abordée. Le jury relève des résultats de cours mal cités et un manque de rigueur ponctuel, mais note une meilleure maîtrise de la rédaction que les années précédentes.
Les erreurs les plus sanctionnées
1
Événements confondus avec des probabilitésQ1
Un système complet d'événements est une famille d'événements. La formule des probabilités totales doit être nommée explicitement sur la copie.
« un système complet d’événements est une famille d’événements et pas de probabilités »
2
Formule des probabilités totales mal citée
Les résultats portant un nom doivent être cités, avec leurs hypothèses. Les abréviations peu usuelles sont à éviter.
« on doit également lire les mots-clés « système complet d’événements »
3
Passage à la limite sans continuitéQ4
Pour obtenir l'égalité vérifiée par la limite, le jury attendait un argument de continuité explicite.
« un argument de continuité était attendu et pas un simple passage à la limite »
4
Inégalité triangulaire et valeur propre complexeQ17, Q18
L'inégalité triangulaire renversée est souvent écrite à l'envers. La valeur propre étudiée est complexe : son module inférieur à 1 ne se traduit pas par un encadrement réel.
« des candidats commettent des erreurs sur les inégalités triangulaires »
5
Positivité oubliéePartie II
Une distribution de probabilité doit avoir des coefficients positifs. De plus, une limite de réels strictement positifs n'est pas forcément strictement positive.
« Beaucoup de candidats ont oublié la positivité dans la définition d’une distribution de probabilités. »
6
Questions d'informatique délaisséesQ33, Q34, Q35
Les fonctions Python de calcul des puissances d'une matrice, pourtant classiques, ont rarement été correctement écrites.
« peu de candidats aient répondu de manière correcte aux questions d’informatique, qui étaient pourtant assez classiques »
Ce qui a été bien réussi
Certaines questions de la partie I ont été très bien traitées.
Beaucoup de très bonnes réponses en partie II, et quelques candidats ont réussi les questions plus difficiles.
Une majorité de copies est clairement présentée, et une part non négligeable allie rigueur, justesse et clarté.
Conseils du jury
Numéroter les questions, les traiter dans l'ordre en laissant des blancs si besoin, et encadrer les résultats.
Articuler les raisonnements avec des mots de liaison et identifier clairement hypothèses et objectifs.
Justifier une formule proposée par l'énoncé au lieu de la recopier, et lire attentivement les questions d'existence et d'unicité.
Utiliser un brouillon avant de rédiger pour éviter les erreurs grossières.
Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.
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 m et n deux entiers naturels, [ [m, n] ] désigne l'ensemble des entiers k tels que m ⩽ k ⩽ n.
Pour n un entier naturel non nul, M_n(ℝ) désigne l'ensemble des matrices carrées d'ordre n à coefficients réels et O_n(ℝ) désigne l'ensemble des matrices orthogonales d'ordre n. On note I_n la matrice identité d'ordre n.
Pour une matrice A de M_n(ℝ), on note A^⊤ sa transposée.
Le module d'un nombre complexe z est noté |z|.
Définitions
Un graphe orienté G est un ensemble G = (S, A) où S est un ensemble fini dont les éléments s'appellent les sommets du graphe G et où A ⊂ S^2. Les éléments de A s'appellent les arêtes orientées du graphe G.
Si a = (s, s^′) ∈ A, a est l'arête orientée reliant le sommet s au sommet s^′. Si (s, s^′) ∈ S^2, on dit que s^′ est un sommet voisin de s s'il existe une arête orientée reliant s à s^′, c'est-à-dire si (s, s^′) ∈ A.
On note que s peut être un sommet voisin de lui-même ( si(s, s) ∈ A ) et que s^′ peut être un voisin de s alors que s n'est pas un voisin de s^′( si (s, s^′) ∈ A alors que (s^′, s) ∉ A).
I Marche aléatoire sur un graphe
On considère un graphe orienté fini dont les sommets sont numérotés de 1 à n.
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 i au sommet j ne dépend pas du rang de l'étape.
Pour 1 ⩽ i, j ⩽ n, on note t_(i, j), la probabilité que le point passe du sommet i au sommet j; en particulier, s'il n'y a pas d'arête reliant i à j, t_(i, j) = 0. La matrice dont le coefficient de la ligne i et de la colonne j est égal à t_(i, j) est notée T. Cette matrice s'appelle la matrice de transition du graphe.
Pour k ∈ ℕ, on note P^((k)) le vecteur ligne (p_1^((k)), p_2^((k)), …, p_(n − 1)^((k)), p_n^((k))), où, pour 1 ⩽ i ⩽ n, p_i^((k)) est la probabilité que le point soit sur le sommet i à l'étape de rang k.
I.A - Résultats généraux
Q 1. Justifier que, pour tout entier naturel k, p_1^((k)) + ⋯ + p_n^((k)) = 1.
Q 2. Montrer que, pour tout tout entier naturel k, P^((k + 1)) = P^((k))T.
Q 3. En déduire, pour tout entier naturel k, une expression de P^((k)) en fonction de T, k et P^((0)).
Q 4. On suppose que la suite de vecteurs (P^((k)))_(k ∈ ℕ) converge vers un vecteur P = (p_1, …, p_n). Montrer que PT = P, que pour tout i ∈ [ [1, n] ], p_i ⩾ 0 et que p_1 + ⋯ + p_n = 1.
I.B - Marche aléatoire sur un tétraèdre
Dans cette sous-partie, on considère le graphe orienté G = (S, A) 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 s au sommet s^′, par une flèche de s vers s^′. Par la suite, nous utiliserons la représentation simplifiée dans laquelle si le graphe comporte les deux arêtes orientées ( s, s^′ ) et ( s^′, s ) 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.
Q 7. Montrer que la suite de matrices (T^k)_(k ∈ ℕ) converge et identifier géométriquement l'endomorphisme canoniquement associé à la matrice limite.
Q 8. Montrer que, quel que soit le vecteur ligne P^((0)) = (p_1^((0)), p_2^((0)), p_3^((0)), p_4^((0))), où pour 1 ⩽ i ⩽ 4, p_i^((0)) est la probabilité que le point soit au départ sur le sommet i, la suite (P^((k)))_(k ∈ ℕ) converge vers le vecteur ligne (1/4, 1/4, 1/4, 1/4).
I. C - Marche aléatoire sur une pyramide tronquée à base carrée
Dans cette question, on suppose que G 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
P^((0)) = (1, 0, 0, 0, 0, 0, 0, 0).
On note S_1 = {1, 3, 6, 8} et S_2 = {2, 4, 5, 7}.
Q 9. Donner la matrice de transition T de ce graphe et calculer
(1, 1, 1, 1, 1, 1, 1, 1)T.
Figure 2
Q 10. Montrer que, si le point se trouve sur un sommet de la partie S_1 à une étape donnée, il se trouvera sur un sommet de la partie S_2 à l'étape suivante et que, s'il se trouve sur un sommet de S_2 à une étape donnée, il se trouvera sur un sommet de S_1 à l'étape suivante.
Q 11. La suite de vecteurs (P^((k)))_(k ∈ ℕ) est-elle convergente ?
II Matrices stochastiques et distributions de probabilité
Définitions
Soit X = (x_1, …, x_n) un vecteur de ℝ^n. On dit que X est une distribution de probabilité si pour tout i ∈ [ [1, n] ], x_i ⩾ 0 et x_1 + ⋯ + x_n = 1.
Soit M une matrice de M_n(ℝ). On dit que M est une matrice stochastique si chaque ligne de M est une distribution de probabilité.
II.A -
Q 12. Soit M ∈ M_n(ℝ), dont tous les coefficients sont positifs ou nuls. Montrer que M est une matrice stochastique si et seulement si
M(1; ⋮; 1) = (1; ⋮; 1).
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 k, le vecteur P^((k)), lui aussi défini dans la partie I , est une distribution de probabilité.
II.B -
Soient M ∈ M_n(ℝ) et N ∈ M_n(ℝ) deux matrices stochastiques, X ∈ ℝ^n une distribution de probabilité et α ∈ [0, 1].
Q 14. Montrer que XM est une distribution de probabilité.
Q 15. Montrer que MN est une matrice stochastique.
Q 16. Montrer que αM + (1 − α)N est une matrice stochastique.
II. C -
Soit M = (m_(i, j)) une matrice stochastique de M_n(ℝ) et λ une valeur propre (réelle ou complexe) de M. On note (u_1, …, u_n) les composantes (réelles ou complexes), dans la base canonique, d'un vecteur propre u associé à λ.
Q 17. Soit h ∈ {1, …, n} tel que |u_h| = max_(1 ⩽ i ⩽ n)|u_i|. Montrer que |λ − m_(h, h)| ⩽ 1 − m_(h, h). En déduire que |λ| ⩽ 1.
Q 18. Soit δ = min_(1 ⩽ i ⩽ n)m_(i, i). Montrer que |λ − δ| ⩽ 1 − δ. Donner une interprétation géométrique de ce résultat et montrer que, si tous les termes diagonaux de M sont strictement positifs, alors 1 est la seule valeur propre de M de module 1.
II.C.2)
On suppose désormais que tous les coefficients m_(i, j)(1 ⩽ i, j ⩽ n) de la matrice stochastique M sont strictement positifs.
Q 19. Démontrer que dim(ker(M − I_n)) = 1.
Si (u_1, …, u_n) désigne les composantes (réelles) dans la base canonique d'un vecteur de ker(M − I_n), on pourra utiliser min_(1 ⩽ i ⩽ n)u_i.
Q 20. En déduire qu'il existe au plus une distribution de probabilité X invariante par M, c'est-à-dire vérifiant XM = X.
On pose ε = min_(1 ⩽ i, j ⩽ n)m_(i, j).
On s'intéresse à la suite (M^k)_(k ∈ ℕ) des puissances de M. On note m_(i, j)^((k)) le coefficient de la matrice M^k situé à la ligne i et la colonne j.
Pour tout j ∈ [ [1, n] ], on pose
{α_j^((k)) = min_(1 ⩽ i ⩽ n)m_(i, j)^((k)),; β_j^((k)) = max_(1 ⩽ i ⩽ n)m_(i, j)^((k)).
Dans les quatre questions suivantes, j est un entier fixé dans [ [1, n] ] et k est fixé dans ℕ.
Q 21. Démontrer les inégalités α_j^((k)) ⩽ α_j^((k + 1)) ⩽ β_j^((k + 1)) ⩽ β_j^((k)).
Q 22. Démontrer qu'il existe un couple (i_0, j_0) ∈ [ [1, n] ]^2 tel que
Q 24. En déduire que β_j^((k + 1)) − α_j^((k + 1)) ⩽ (1 − 2ε)(β_j^((k)) − α_j^((k))).
Q 25. Démontrer que la suite (M^k) converge vers une matrice stochastique B = (b_1, ⋯, b_n; b_1, ⋯, b_n; b_1, ⋯, b_n) dont toutes les lignes sont égales.
On note P^∞ la ligne (b_1, …, b_n).
Q 26. Démontrer que, ∀i ∈ [ [1, n] ], b_i > 0.
Q 27. Démontrer que la suite (P^((k)))_(k ∈ ℕ) = (P^((0))M^k)_(k ∈ ℕ) converge vers P^∞, quelle que soit la distribution de probabilité initiale P^((0)).
Q 28. Démontrer que P^∞ est l'unique distribution de probabilité P invariante par M, c'est-à-dire vérifiant PM = P.
III Le graphe du web
On modélise le web par un graphe orienté à n 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 i contient au moins un lien vers la page j, on dit que la page i pointe vers la page j. Cette situation est modélisée par l'existence de l'arête orientée de i vers j, notée i → j. On dit que i → j est une arête sortante de i et une arête entrante de j. Si aucun lien de la page i ne pointe vers la page j, on note i↛j.
Pour tout entier i ∈ [ [1, n] ], λ_i désigne le nombre d'arêtes sortantes de la page i, 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 (μ_j)_(1 ⩽ j ⩽ n) vérifiant les deux conditions suivantes :
(i) la pertinence μ_j de la page j est une fonction croissante de la pertinence de chacune des pages qui pointent vers elle ;
(ii) la contribution de la page i dans la pertinence de chacune des pages vers lesquelles elle pointe est une fonction décroissante de λ_i (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 i,
si la page i pointe vers d'autres pages, il se dirige au hasard, de manière équiprobable, vers l'une de ces pages ;
si la page i ne pointe vers aucune page, il reste sur la page i.
Q 29. Vérifier que la matrice de transition associée à ce modèle de navigation est la matrice A = (a_(i, j))_(1 ⩽ i, j ⩽ n) avec
{a_(i, i) = {1, si la page i ne pointe vers aucune autre page; 0, sinon; a_(i, j) = {0, si i↛j; 1/λ_i, si i → j pour i ≠ j
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 A par la matrice
B = (1 − α)A + α/nJ_n
où J_n est la matrice de M_n(ℝ) dont tous les coefficients sont égaux à 1, A est la matrice stochastique décrite à la question 29 et α est un réel de ]0, 1[, appelé facteur d'amortissement.
III.B.1)
Q 30. Montrer que B est une matrice stochastique dont tous les coefficients sont strictement positifs.
Q 31. Dans le modèle de navigation admettant B pour matrice de transition, donner la probabilité de quitter une page ne contenant aucun lien vers une autre page.
Soit Q une distribution de probabilité. On définit la suite (Q^((k)))_(k ∈ ℕ) par Q^((k)) = QB^k pour tout entier naturel k.
Q 32. Démontrer que la suite (Q^((k)))_(k ∈ ℕ) converge et que sa limite Q^∞ vérifie les conditons (i) et (ii) décrites dans l'introduction de cette partie. Elle fournit donc des pertinences pour les n pages du web. On exprimera la
pertinence de chaque page j 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 B^k
Dans la pratique, on se contente d'approcher Q^∞ par Q^((k)) = QB^k pour une valeur de k 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 I_n, la matrice identité d'ordre n;
A. shape donne, sous forme de couple, la taille du tableau A, par exemple np.identity (5). shape → (5, 5);
np. dot(A, B) calcule, le produit matriciel de A et B si A et B sont deux tableaux à deux dimensions compatibles avec le produit matriciel.
L'algorithme naïf de calcul de B^k repose sur sa définition, à savoir :
{B^0 = I_n; B^k = BB^(k − 1) ∀k ⩾ 1
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 B^k calculée en utilisant l'algorithme naïf.
L'algorithme d'exponentiation rapide repose sur le principe suivant :
{B^0 = I_n; B^k = (B^2)^(k/2), si k est pair; B^k = B(B^2)^((k − 1)/2), si k est impair.
Q 34. Écrire une fonction Python puissance2(B, k) qui prend en argument une matrice carrée B et un entier naturel k et renvoie la matrice B^k calculée à partir de l'algorithme d'exponentiation rapide.
Q 35. On suppose que k ⩾ 2 et on note p l'unique entier tel que 2^p ⩽ k < 2^(p + 1). Pour chacun des appels puissance1 ( B, k ) et puissance2 ( B, k ), calculer le nombre d'appels à la fonction np. dot, dans le pire et dans le meilleur des cas.
Questions fréquentes
3 questions
Sur quels chapitres porte le sujet de maths 1 Centrale PSI 2021 ?
Afficher ou masquer la section
Sur quels chapitres porte le sujet de maths 1 Centrale PSI 2021 ?
+
Le sujet mobilise les probabilités, la réduction des endomorphismes et des matrices, les suites de vecteurs, les nombres complexes et un peu d'algorithmique en Python.
Quelles erreurs le jury a-t-il le plus relevées en maths 1 Centrale PSI 2021 ?
+
La confusion entre événements et probabilités, la formule des probabilités totales mal citée, des inégalités triangulaires écrites à l'envers et l'oubli de la positivité dans la définition d'une distribution de probabilité.
Le sujet maths 1 Centrale PSI 2021 est-il long ?
+
Le jury le juge plutôt long, mais sa progressivité a permis à tous les candidats de traiter de nombreuses questions. La partie III a été moins abordée.
Pas de description pour le moment
Commentaires• Centrale Mathématiques 1 PSI 2021
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même année, CCINPCCINP Mathématiques PSI 2021CCINP · 2021Corrigé
Même chapitre : Algèbre linéaire (+3)E3A Mathématiques 1 PSI 2019E3A · 2019Corrigé
Même année, MinesMines Mathématiques 2 PSI 2021Mines · 2021Corrigé
Même année, X-ENSX ENS Mathématiques PSI 2021X-ENS · 2021Corrigé
