AnnalesÉcoles d'ingénieurs

Centrale-Supélec PSI 2021 — Maths 1

Marches aléatoires sur un graphe, matrices stochastiques et algorithme PageRank · 6 pages

Le sujet étudie les marches aléatoires sur un graphe orienté au moyen de leur matrice de transition, sur l'exemple du tétraèdre (convergence vers la loi uniforme) puis d'un graphe biparti où la loi ne converge pas. Il montre ensuite que les valeurs propres d'une matrice stochastique sont de module au plus $1$ et que, si tous ses coefficients sont strictement positifs, ses puissances convergent vers une matrice à lignes égales donnant l'unique distribution invariante. Il applique ce résultat à l'algorithme PageRank et compare deux calculs de $B^k$ en Python (naïf et exponentiation rapide).

Le sujet, partie par partie

Notations et Partie I — Marche aléatoire sur un graphe p. 1–3

Chaînes de Markov · Diagonalisation · Graphes · Théorème spectral · Matrices stochastiques et bistochastiques — matrice de transition, marche aléatoire sur un graphe, tétraèdre, graphe biparti, matrice $J$ , puissances d'une matrice

Partie II — Matrices stochastiques et distributions de probabilité p. 3–4

Matrices stochastiques et bistochastiques · Théorème de Perron-Frobenius · Chaînes de Markov · Suites numériques · Rayon spectral — matrice stochastique, distribution de probabilité, disques de Gershgorin, loi stationnaire, convergence des puissances, valeur propre $1$

Partie III — Le graphe du web et l'algorithme PageRank p. 5–6

Chaînes de Markov · Matrices stochastiques et bistochastiques · Informatique et algorithmique · Graphes — PageRank, facteur d'amortissement, exponentiation rapide, Python, complexité, numpy

Dans l'édifice

Indépendance d'événements et de tribus Matrices d'une application linéaire Espaces de Hilbert et théorème de projection Suites réelles et limites Théorème de Bolzano-Weierstrass Complétude de ℝ Applications linéaires continues et dual topologique Spectre premier d'un anneau Théorème de définition par récurrence