Centrale Maths 1 PSI 2021

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