Centrale Maths 1 PSI 2021

Corrigé

(c'est payant, sauf le début) : - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


Mathématiques 1
PSI

4 heures Calculatrice autorisée

2021

Ce sujet comprend trois parties. Les résultats généraux du I.A sont utilisés 
dans la partie IT et dans la sous-
partie IIT.A. Le IIT.B.2 peut être traité indépendamment du III.B.1.

Notations
N désigne l'ensemble des entiers naturels et R 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 0 et que p, +. +p,, = 1.

M051/2021-01-05 16:44:53 Page 1/6 CIEL
I.B --- Marche aléatoire sur un tétraëèdre

Dans cette sous-partie, on considère le graphe orienté G = (5, A) où

{= {1,2,3,4),
A = {(1,2), (2,1), (1,3), (3,1), (1,4), (4,1), (2,3), (3,2), (2,4), (4,2), 
(3,4), (4,3)}.

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 5'.
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é.

(1 (1)

& &
5 LS

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

Jy =

HhH H
HhH H
HhH H
he

Q 5. Exprimer la matrice de transition T'en fonction de J, et 1,.

Q 6. Démontrer qu'il existe une matrice Q EUR O,(R) telle que

--1 0 0 O0
1 0 --1 O0 0 +
1-31 0 0 1 01%:
0 0 D 3
Q 7. Montrer que la suite de matrices (7) Len converge et identifier 
géométriquement l'endomorphisme

canoniquement associé à la matrice limite.

(0)

d

(0) ,,(0) ,,(0) ,,(0)

Q 8. Montrer que, quel que soit le vecteur ligne P(0) = (p}7,ps ,P3 ,Pa ), où 
pour 1 < i < 4, p; est la probabilité que le point soit au départ sur le sommet 2, la suite (PH) converge vers le vecteur ligne (1/4,1/4,1/4,1/4). kEN 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 à 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 P0) = (1,0,0,0,0,0,0,0). On note 5 -- {1, 3, 6, 8} et 5 -- {2,4, D, 7}. Q 9. Donner la matrice de transition T de ce graphe et calculer (1.1,11,1111)T. M051/2021-01-05 16:44:53 Page 2/6 (cc) BY-NC-SA eo (2) Le è 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. D D» Figure 2 Q 11. La suite de vecteurs (P)),.,, est-elle convergente ? II Matrices stochastiques et distributions de probabilité Définitions Soit X = (x,,...,x,,) un vecteur de R". On dit que X est une distribution de probabilité si pour tout à EUR ]1,nl], x; Z2V0etxr, +-+x,, = 1. Soit M une matrice de M,,(R). On dit que M est une matrice stochastique si chaque ligne de M est une distribution de probabilité. IT. À - Q 12. Soit M EUR M,(R), dont tous les coefficients sont positifs ou nuls. Montrer que M est une matrice stochastique si et seulement si 1 1 M :|-|: 1 1 Q 13. Montrer que la matrice de transition d'un graphe (définie dans la partie [) est une matrice stochastique et que, pour tout entier naturel k, le vecteur P(), lui aussi défini dans la partie L, est une distribution de probabilité. II1.B -- Soient M EUR M,(R) et N EUR M,(R) deux matrices stochastiques, À EUR KR" une distribution de probabilité et a EUR [0,1|. Q 14. Montrer que X M est une distribution de probabilité. Q 15. Montrer que M N est une matrice stochastique. Q 16. Montrer que a M + (1 -- a)N est une matrice stochastique. II. C - Soit M = (m; ;) une matrice stochastique de M,,(R) et À une valeur propre (réelle ou complexe) de M. On note (u,,...,u,,) les composantes (réelles ou complexes), dans la base canonique, d'un vecteur propre u associé à À. M051/2021-01-05 16:44:53 Page 3/6 (cc) BY-NC-SA II.C.1) Q 17. Soithe {1,..,n} tel que |u}| = max lu;|. Montrer que |À -- my, ,| < 1--m,, ,. En déduire que |A! < 1. LILN ? ? Q 18. Soit Ôd -- in m,;,. Montrer que |À-- | < 1--6. Donner une interprétation géométrique de ce résultat Lin ? 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; ;U  mi (8 ai).

Q 24. En déduire que gt? : ar < (1 -- 2e) (81° : a). bi by, Q 25. Démontrer que la suite (MF) converge vers une matrice stochastique B = | b, -... b, | dont toutes bi by, les lignes sont égales. On note P® la ligne (b,,...,b,,). Q 26. Q 27. Q 28. PM = P. M051/2021-01-05 16:44:53 Démontrer que, Vi EUR [1,n], b; > 0.

Démontrer que la suite (PM), = (PIWMF),., converge vers P®, quelle que soit la 
distribution de
probabilité initiale P(0).

Démontrer que P© est l'unique distribution de probabilité P invariante par M, 
c'est-à-dire vérifiant

Page 4/6

CETTE
ITIT 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 ? 
contient au moins un lien vers la
page 7, on dit que la page ? pointe vers la page 7. Cette situation est 
modélisée par l'existence de l'arête orientée
de à vers 7, notée à -- 7. On dit que à -- j est une arête sortante de à et une 
arête entrante de 7. Si aucun lien
de la page à ne pointe vers la page j, on note à À j.

Pour tout entier à EUR ]1,n], À, désigne le nombre d'arêtes sortantes de la 
page 4, 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 
(H;)1< jen Vériliant les deux conditions suivantes : (i) la pertinence u; 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 à dans la pertinence de chacune des pages vers lesquelles elle pointe est une fonction décroissante de À; (voir définition ci-dessus). TITI. À -- 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 2, -- si la page 2? 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 2. Q 29. Vérifier que la matrice de transition associée à ce modèle de navigation est la matrice À = (a avec ,j)1l.

Q 33. Écrire une fonction Python puissancel(B, k) qui prend en argument une 
matrice carrée B et un
entier naturel k et renvoie la matrice B° calculée en utilisant l'algorithme 
naïf.

L'algorithme d'exponentiation rapide repose sur le principe suivant :

BO= I,
k
B% = (B°)? si & est pair,
k--1
B = B(B?) ? 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 4 et renvoie la matrice B° calculée à partir de l'algorithme 
d'exponentiation rapide.

Q 35. On suppose que 4 > 2 et on note p l'unique entier tel que 2? < k < 2P*1. Pour chacun des appels puissancel(B, k) et puissance2(B, k), calculer le nombre d'appels à la fonction np.dot, dans le pire et dans le meilleur des cas. ee eFINeee M051/2021-01-05 16:44:53 Page 6/6 (cc) BY-NC-SA

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Maths 1 PSI 2021 -- Corrigé
Ce corrigé est proposé par Julie Gauthier (professeur agrégé) ; il a été relu 
par
Angèle Niclas (ENS Lyon) et Benjamin Monmege (enseignant-chercheur à 
l'université).

Comment fonctionne Google ? Ce sujet décrit l'algorithme PageRank qui permet
d'identifier les pages web les plus populaires. Pour cela, on réduit le web à 
un graphe
orienté sur lequel on effectue une marche aléatoire. L'outil central est la 
notion de
matrice stochastique, c'est-à-dire dont tous les coefficients sont positifs et 
dont la
somme des termes d'une ligne vaut toujours 1.
· Dans la partie I, on établit des propriétés générales d'une marche aléatoire
sur un graphe en situation d'équiprobabilité. Puis on applique ce modèle à
deux exemples géométriques en explicitant les matrices de transition utilisées.
On s'intéresse en particulier à la stabilité du comportement sur le temps long.
· La partie suivante introduit la notion de matrice stochastique, dont les 
matrices de transition vues à la partie I constituent des cas particuliers. 
Après
avoir donné une condition nécessaire et suffisante pour qu'une matrice soit 
stochastique, et avoir constaté des résultats de stabilité de l'ensemble des 
matrices
stochastiques, on s'intéresse à leur spectre. Pour finir, on étudie la suite 
constituée des puissances d'une matrice stochastique. En établissant des 
inégalités
sur ses coefficients, on obtient des résultats de convergence.
· Dans la partie III, on travaille sur le graphe du web puis sur l'algorithme 
PageRank. Cette partie contient des questions de programmation Python et de
complexité algorithmique.
Ce sujet porte principalement sur l'algèbre linéaire. Il donne l'occasion de 
manipuler des suites de matrices. De manière inhabituelle, on multiplie le plus 
souvent
des matrices par des vecteurs ligne à gauche plutôt que par des vecteurs 
colonne à
droite.

Publié dans les Annales des Concours

Indications
Partie I
1 Utiliser la formule des probabilités totales.
2 Revenir à la définition de la matrice T et utiliser la formule des 
probabilités
composées.
3 Raisonner par récurrence et utiliser le résultat de la question 2.
4 Passer à la limite dans les formules des questions 1 et 2.
6 La matrice de transition T de la question 5 est symétrique réelle. Trouver ses
valeurs propres et les dimensions des sous-espaces propres associés pour 
conclure.
7 La matrice Q étant orthogonale, utiliser la formule de la question 6 pour 
calculer Tk puis passer à la limite pour k tendant vers +. Reconnaître alors la 
limite
obtenue comme une projection sur un sous-espace propre de T.
8 Appliquer le résultat de la question 3 dans cette situation puis passer à la 
limite
en utilisant la limite de la suite (Tk )kN obtenue à la question 7 ainsi que le
résultat de la question 4.
11 Raisonner par l'absurde.
Partie II
12 Exprimer comme une somme chaque coefficient de M (1, . . . , 1)T puis 
revenir à
la définition d'une matrice stochastique.
14 Écrire explicitement les coefficients du vecteur ligne XM comme des sommes.
Sommer ensuite tous les coefficients de XM. Conclure en permutant les sommes
finies.
15 Il y a deux méthodes possibles :
· appliquer le résultat de la question 14 à chacune des lignes de M ;
· utiliser la caractérisation de la question 12. Il faudra dans ce cas 
justifier la
positivité des coefficients de MN.
17 Écrire ( - mh,h )uh comme une somme. Majorer cette somme en module en
utilisant la définition de uh . Pour conclure, il faudra utiliser le fait que M 
est
stochastique. L'inégalité || 6 1 s'obtient à partir de celle sur | - mh,h |. 
Pour
cela, il suffit de décomposer  =  - mh,h + mh,h .
18 Utiliser une astuce similaire à celle de la question 17 pour obtenir 
l'égalité souhaitée. Faire un dessin de la situation en utilisant un disque de 
centre d'affixe .
Pour la dernière partie de la question, noter que si tous les termes diagonaux 
de M
sont strictement positifs alors  > 0 et se ramener au cas d'égalité de 
l'inégalité
triangulaire.
20 Noter que la transposée d'une distribution de probabilité invariante est un 
vecteur
propre de la transposée de M associé à la valeur propre 1. Que dire de la 
dimension
de Ker (MT - In ) en utilisant la question 19 ?
21 Écrire explicitement les coefficients de Mk+1 = M Mk .
(k)

22 Définir i0 à partir de j
(k)

24 Faire apparaître j
tions 22 et 23.

(k)

et j0 à partir de j .
(k)

et j

puis utiliser les inégalités obtenues dans les ques-

25 Traiter à part le cas n = 1. Dans l'autre cas, utiliser
 l'inégalitéobtenue à la
(k)
(k)
question 24 pour montrer que la suite des différences j - j
converge
kN

(k)

vers 0. Conclure en utilisant la définition des j
la limite obtenue est une matrice stochastique.

(k)

et j . Penser à montrer que

26 Noter que (jk )kN est croissante. On a supposé que les coefficients de M 
sont tous
(1)

strictement positifs. Que peut-on en déduire pour j ?
27 Appliquer le résultat de la question 25.
28 Utiliser les résultats des questions 20 et 27.
Partie III
30 Penser à appliquer les résultats des questions 13 et 16.
32 Appliquer les résultats de la partie II.C.2, en particulier ceux des 
questions 27
et 28, à la matrice B. Une des difficultés de cette question réside dans la 
compréhension des propriétés (i) et (ii). En voici une interprétation : pour 
tout couple
d'entiers (i, j)  [[ 1 ; n ]]2 tel que la page i pointe vers la page j,
(i) si µi augmente alors µj augmente ;
(ii) si i augmente alors la contribution de la page i dans µj diminue.
35 Pour la complexité, on peut raisonner par récurrence. En particulier, il 
faut montrer que les bornes proposées sont atteintes dans le pire et dans le 
meilleur des
cas pour l'algorithme d'exponentiation rapide.

I. Marche aléatoire sur un graphe
(k)

1 Soit k  N. Par définition, pour tout i  [[ 1 ; n ]], pi représente la 
probabilité
que le point soit sur le sommet i à l'étape de rang k. Comme il y a exactement n
sommets numérotés de 1 à n, l'ensemble constitué des événements
{Le point est sur le sommet i}
pour i  [[ 1 ; n ]] forme un système complet d'événements. Dès lors, la formule 
des
probabilités totales assure que
n
P

k  N

i=1

(k)

pi

=1

(k)

2 Soit k  N. Le vecteur ligne P(k) = (pi )i[[ 1 ; n ]] est constitué des 
probabilités
(k+1)

que le point soit sur le sommet i à l'étape de rang k. Pour i  [[ 1 ; n ]], pi
est
la probabilité que le point soit sur le sommet i à l'étape de rang k + 1. Or, 
pour
tout j  [[ 1 ; n ]], tj,i représente la probabilité que le point soit sur le 
sommet i à
l'étape k + 1 sachant qu'il était sur le sommet j à l'étape k.
La formule des probabilités composées couplée à la formule des probabilités 
totales, dans le système complet d'événements {Le point se situe sur le sommet 
j}
pour j  [[ 1 ; n ]], assure que la probabilité que le point soit sur le sommet 
i à l'étape
de rang k + 1 s'écrit
n
P
(k+1)
(k)
pi
=
pj tj,i
j=1

Ceci donne matriciellement
k  N

P(k+1) = P(k) T

3 Montrons par récurrence que la propriété
P(k) :

P(k) = P(0) Tk

est vraie pour tout k  N.
· P(0) est vraie car T0 = In .
· P(k) = P(k + 1) : Soit k  N. On suppose que P(k) = P(0) Tk . D'après le
résultat de la question 2 et P(k),
P(k+1) = P(k) T = P(0) Tk T = P(0) Tk+1
ce qui prouve que P(k + 1) est vraie.
· Conclusion :

k  N

P(k) = P(0) Tk

4 On passe à la limite pour k tendant vers + dans la formule de récurrence
obtenue à la question 2. Par continuité du produit matriciel, il vient
P = PT
De plus, par définition de P(k) , pour tout k  N, pour tout i  [[ 1 ; n ]], on 
sait
(k)
que pi > 0. Par passage à la limite quand k tend vers +,
i  [[ 1 ; n ]]

pi > 0