Mines Maths 1 PC 2017

Thème de l'épreuve Marche aléatoire dans un labyrinthe
Principaux outils utilisés algèbre linéaire, probabilités
Mots clefs matrices stochastiques

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


A2017 ­ MATH I PC

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT Atlantique (ex Télécom Bretagne),
ENSAE PARISTECH.
Concours Centrale-Supelec (Cycle International),
Concours Mines-Télécom, Concours Commun TPE/EIVP.
CONCOURS 2017
PREMIÈRE ÉPREUVE DE MATHÉMATIQUES
Durée de l'épreuve : 3 heures
L'usage de la calculatrice et de tout dispositif électronique est interdit.

Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :
MATHÉMATIQUES I - PC
L'énoncé de cette épreuve comporte 5 pages de texte.
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur
d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant 
les
raisons des initiatives qu'il est amené à prendre.

Marche aléatoire dans un labyrinthe

Un labyrinthe est constitué de cinq salles, numérotées de 1 à 5, qui 
communiquent par des tubes selon le schéma ci-dessous :

2

3

1

5

4

Un rat se déplace dans ce labyrinthe, et on relève sa position en des instants
numérotés 0, 1, 2, · · · , k, · · · (k  N). On admet que, si le rat se trouve à 
l'instant k
(k  N) dans la salle numéro i (1  i  5), alors il empruntera aléatoirement l'un
des tubes de la salle i et se trouvera donc, à l'instant k + 1, avec 
équiprobabilité,
dans l'une quelconque des salles communiquant avec la salle i. On admet que l'on
peut introduire, pour tout k entier naturel, une variable aléatoire Sk donnant 
le
numéro de la salle où se trouve le rat à l'instant k. À titre d'exemple, on 
aura donc
k  N,
1
P (Sk+1 = 1 | Sk = 2) = P (Sk+1 = 3 | Sk = 2) = P (Sk+1 = 5 | Sk = 2) = ·
3
Pour tout k  N, on introduit la matrice-colonne

P (Sk

P (Sk

Xk = 
P (Sk

P (Sk
P (Sk

= 1)

= 2)

= 3)
  M5,1 (R).
= 4)

= 5)

Pour une matrice B, tB représente sa matrice transposée.
1

I

Premiers pas
1. En utilisant la formule des probabilités totales, montrer que P (Sk+1 = 1)
s'écrit comme une combinaison linéaire des (P (Sk = i), i = 1, · · · , 5).
2. Expliciter la matrice carrée B  M5 (R) telle que Xk+1 = BXk pour tout k
entier naturel.
3. En observant les colonnes de la matrice B, montrer que le réel 1 est valeur
propre de tB et expliciter un vecteur propre associé.

On suppose que la loi de la variable S0 est donnée par

1/4

3/16

X0 = 
3/16 .

3/16
3/16

(1)

4. Montrer qu'alors les variables aléatoires Sk ont toutes la même loi.
5. Est-ce que S0 et S1 sont indépendantes ?

II

Convergence dans Mn(R)

Soit u un endomorphisme d'un R-espace vectoriel E de dimension finie. On
suppose qu'il existe une norme "·" sur E telle que l'inégalité suivante soit 
satisfaite
pour tout x  E,
"u(x)"  "x".
Pour tout entier naturel k non nul, on considère l'endomorphisme
'
1 k-1
1
rk =
ul = (IE +u + u2 + · · · + uk-1 ),
k l=0
k

où IE représente l'endomorphisme identité de E.
6. Soit x  ker(u - IE ). Déterminer limk rk (x).
7. Soit x  Im(u - IE ). Montrer que limk rk (x) = 0E .
8. En déduire que E = ker(u - IE )  Im(u - IE ).
2

!

"

9. Soit x  E, un vecteur quelconque. Montrer que la suite rk (x)
converge
kN
vers un vecteur de E, que l'on notera p(x). Interpréter géométriquement
l'application p : E - E ainsi définie.
Soit A  Mn (R) une matrice carrée d'ordre n à coefficients réels. On suppose
qu'il existe une norme, aussi notée $ · $, sur l'espace vectoriel Mn,1 (R) 
identifié à
Rn , telle que, pour tout X  Mn,1 (R), on ait $AX$  $X$. Pour tout k entier
naturel non nul, on considère la matrice
Rk =

#
1 k-1
1
Al = (In + A + A2 + · · · + Ak-1 ),
k l=0
k

(2)

où In est la matrice identité dans Mn (R).
10. Montrer que la suite de matrices (Rk )kN converge dans Mn (R) vers une
matrice P , telle que P 2 = P .

III

Matrices stochastiques

On fixe dans cette partie, un entier n  2.
Définition 1 On notera U  Mn,1 (R), la matrice-colonne dont tous les 
coefficients sont égaux à 1.
Définition 2 Une matrice carrée A = (ai,j )  Mn (R) est dite stochastique si
elle vérifie les conditions suivantes :
(i, j)  !1, n"2 , ai,j  0;
i  !1, n",

n
#

ai,j = 1.

(3)
(4)

j=1

Nous dirons aussi qu'une matrice-ligne L = (1 , · · · , n )  M1,n (R) est 
stochastique lorsque ses coefficients i sont tous positifs ou nuls, et de somme 
égale à
1.

11. Vérifier que la condition (4) équivaut à la condition AU = U .
12. En déduire que l'ensemble E des matrices stochastiques (carrées d'ordre n)
est stable par le produit matriciel.
13. Montrer que cet ensemble E est une partie fermée et convexe de l'espace
vectoriel Mn (R).
3

On munit
l'espace Mn,1 (R) de la norme ! · ! définie par !X! = max1in |xi |
 
x1
 . 

si X =  .. 
.
xn

14. Montrer que, si A  Mn (R) est stochastique, alors on a !AX!  !X!
pour tout X  Mn,1 (R).

Dans les questions 15 à 22, on note A  Mn (R) une matrice stochastique, et
on suppose qu'il existe un entier naturel non nul p tel que la matrice Ap ait 
tous
ses coefficients strictement positifs. Pour tout k entier naturel non nul, on 
posera
'
1 k-1
Al .
Rk =
k l=0

15. Montrer que ker(Ap - In ) est de dimension 1.

x1
 . 
p

Indication : soit X =  .. 
  ker(A - In ), soit s  !1, n" un indice tel que
xn
xs = max1jn xj , on montrera que xj = xs pour tout j  !1, n".
16. En déduire que ker(A - In ) = Vect(U ).
17. Montrer que, pour tout k  N , la matrice Rk est stochastique.
18. Montrer que la suite (Rk )kN converge dans Mn (R) vers une matrice P ,
stochastique, de rang 1.
19. En déduire que l'on peut écrire P = U L, où L = (1 , · · · , n )  M1,n (R)
est une matrice-ligne stochastique.
20. Montrer que P A = P . En déduire que L est la seule matrice-ligne 
stochastique vérifiant LA = L.
21. Montrer que les coefficients de la matrice-ligne L sont tous strictement 
positifs.
22. Montrer que le réel 1 est valeur propre simple de la matrice A.
On pourra utiliser le résultat de la question 8.

4

IV

Application au labyrinthe

On approfondit l'étude commencée dans la partie I en exploitant les résultats
de la partie III.
On pose A = tB où B est la matrice construite dans la partie I.
Un calcul qui n'est pas demandé, montre que les coefficients de la matrice A2
sont tous strictement positifs.

23. Expliciter la limite P de la suite de matrices (Rk )kN définie en (2) ?
24. Montrer qu'il existe une unique loi de probabilité sur l'ensemble !1, 5" 
telle
que, si la variable aléatoire S0 suit cette loi, alors les variables Sk suivent
toutes la même loi (autrement dit, telle que la probabilité de présence du rat
dans une salle soit la même à tous les instants k, k  N).

Fin du problème

5

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



Mines Maths 1 PC 2017 -- Corrigé
Ce corrigé est proposé par Maël Mevel (professeur agrégé) ; il a été relu par
Antoine Sihrener (professeur en CPGE) et Céline Chevalier (enseignant-chercheur 
à
l'université).

Ce problème utilise la marche aléatoire d'un rat dans un labyrinthe comme point
de départ puis établit quelques propriétés des matrices dites stochastiques (du 
grec
stokhastês : « lié au hasard »).
· La partie I propose de démontrer que sous certaines conditions initiales, la 
loi
de la position du rat dans le labyrinthe ne varie pas avec le temps. On associe
une matrice au graphe probabiliste présenté dans le sujet, matrice dont il sera
montré plus tard que sa transposée est stochastique.
· La partie II s'intéresse à la convergence de la suite (rk ) des moyennes de 
Césaro
des puissances d'un endomorphisme u. On justifie notamment que lorsque u est
tel que ku(x)k 6 kxk pour tout x dans E, la suite converge vers un projecteur
bien particulier. Le point de vue matriciel est également abordé.
· La partie III porte sur l'étude des matrices stochastiques en elles-mêmes ;
on montre que les matrices Rk considérées dans la partie II sont stochastiques,
et que ces dernières ont notamment la valeur propre évidente 1 pour valeur
propre simple.
· Dans la partie IV, on applique les résultats des parties précédentes à l'étude
de la loi de la variable aléatoire Sk donnant la position du rat à l'instant k.
On montre en particulier qu'il existe une unique valeur pour S0 qui rende la
suite (Sk )kN constante.
Ce problème peut être vu comme l'étude d'une chaîne de Markov (à espace d'états
finis), c'est-à-dire une marche aléatoire dans laquelle un état au temps n ne 
dépend
que de l'état au temps n - 1 (et du hasard). Il fait appel aux probabilités 
bien sûr,
mais aussi à l'algèbre linéaire. Quelques questions demandent de savoir bien 
jongler
entre le point de vue des endomorphismes et le point de vue matriciel.
Remarquons enfin que les matrices stochastiques figuraient déjà dans l'épreuve 1
des Mines, filière MP, en 2016, et qu'elles sont présentes dans de nombreux 
sujets
d'oraux. Il s'agit d'un thème très à la mode depuis la réforme introduisant les 
probabilités en classe préparatoire il y a 3 ans.

Indications
Partie I
I.1 Montrer que (Sk = i)i[[ 1 ; 5 ]] est un système complet d'événements.
I.2 Généraliser la question précédente à P (Sk+1 = i) pour i  [[ 1 ; 5 ]].
I.4 Raisonner par récurrence sur k.
I.5 Considérer par exemple P (S0 = 1  S1 = 1).
Partie II
II.6 S'intéresser à u (x) pour x  Ker (u - IE ).
II.7 Justifier qu'il existe y  E tel que x = u(y) - y, puis injecter cela dans 
rk (x),
et majorer la norme de cette dernière quantité.
II.8 En utilisant les T
questions II.6 et II.7, étudier la limite de rk (x) lorsque
x  Ker (u - IE ) Im (u - IE ). Conclure ensuite par dimension.
II.9 Traduire ce que signifie, pour un x  E, la décomposition de E en somme
directe démontrée précédemment.
II.10 Utiliser les résultats de la question II.9 en jonglant entre 
endomorphisme et
matrice. Penser à une caractérisation de l'application p.

Partie III
III.13 Utiliser la caractérisation séquentielle des fermés.
n
n
P
P
III.14 En tentant de majorer kAXk , faire apparaître
|ai,j | =
ai,j = 1.
j=1

j=1

III.15 Remarquer que la matrice Ap est stochastique, puis raisonner par 
l'absurde
en supposant l'existence d'un indice i0 tel que xi0 < xs et en utilisant 
l'égalité
Ap X = X.
III.16 En exploitant le résultat de la question précédente, montrer que si AX = 
X
alors Ap X = X, puis X  Vect U.
III.18 Combiner les résultats des questions III.10 et III.14 pour montrer que Rk
converge vers une matrice P telle que P2 = P. Conclure en utilisant les
questions III.13, III.16 et III.17.
III.19 S'intéresser aux lignes (ou aux colonnes) de P et exprimer un lien de 
multiplicité entre ces dernières à l'aide du rang de P. Utiliser la 
stochasticité de P
(condition 4).
III.20 Pour tout k  N , exprimer Rk A en fonction de Rk+1 et de la matrice 
identité,
puis passer à la limite. En ce qui concerne l'unicité de L, appliquer le 
théorème

du rang à deux matrices bien choisies, en remarquant que t L  Ker t A -In ,
puis utiliser la question III.16.
III.21 Raisonner par l'absurde. Utiliser l'hypothèse sur les coefficients de Ap 
faite
dans le sujet.
III.22 Établir une relation entre le polynôme caractéristique de u et ceux des 
endomorphismes uK et uI induits par u sur les sous-espaces vectoriels Ker (u - 
IE )
et Im (u - IE ). Etudier alors uK .
Partie IV
IV.24 L'existence d'une telle loi provient de la partie I. L'unicité est une 
conséquence
de la question III.20.

I. Premiers pas
I.1 Soit k  N. Afin d'utiliser la formule des probabilités totales comme 
conseillé
dans l'énoncé, montrons que la famille (Sk = i)i[[ 1 ; 5 ]] constitue un 
système complet
d'événements.
Comme le rat se trouve forcément dans une pièce à un instant donné,
5
[

(Sk = i) = 

i=1

et puisque le rat ne peut se trouver en deux pièces au même instant, les 
événements
(Sk = i)i[[ 1 ; 5 ]] sont deux à deux incompatibles. Ainsi, la famille (Sk = 
i)i[[ 1 ; 5 ]]
constitue un système complet d'événements.
Appliquons alors la formule des probabilités totales. Il vient
P (Sk+1 = 1) =

5
P

P (Sk+1 = 1|Sk = i) P (Sk = i)

i=1

et ainsi

La quantité P (Sk+1 = 1) est une combinaison linéaire des P (Sk = i)

i[[ 1 ; 5 ]]

.

La manière dont cette question est posée est quelque peu étrange : en effet,
on demande de montrer qu'un réel (P (Sk+1 = 1)) est combinaison linéaire
d'autres réels (les (P (Sk = i))i[[ 1 ; 5 ]] )... Or, c'est toujours vrai dès 
l'instant
où ces derniers ne sont pas tous nuls, ce qui est évident dans le cas présent !
Sans présumer des intentions des auteurs, on peut supposer qu'une formulation 
plus précise de la question serait « En utilisant la formule des probabilités
totales, exprimer P (Sk+1 = 1) en fonction des P (Sk = i)i[[ 1 ; 5 ]] . »
I.2 En raisonnant de manière analogue à la question I.1, écrivons pour tout k  N
et pour tout i  [[ 1 ; 5 ]],
P (Sk+1 = i) =

5
P

P (Sk+1 = i|Sk = j) P (Sk = j)

j=1

ce qui équivaut, en passant à l'écriture matricielle, à l'égalité
Xk+1 = BXk
où les coefficients de la matrice B sont donnés par
(i, j)  [[ 1 ; n ]]2

bi,j = P (Sk+1 = i|Sk = j)

Enfin, comme le rat se déplace de salle en salle avec équiprobabilité, on en 
déduit, en
notant nj le nombre de salles adjacentes
à la j e salle, que pour tout (i, j)  [[ 1 ; n ]]2 ,
(
1/nj si les salles i et j sont adjacentes
bi,j = P (Sk+1 = i|Sk = j) =
0 sinon

0 1/3 1/3 1/3 1/3

1/4 0 1/3 0 1/3

0
0
et ainsi
B=

1/4 0 1/3 0 1/3

1/4 1/3 0 1/3 0

Si l'on souhaite se placer du point de vue des chaînes de Markov évoqué
dans la présentation, c'est alors le moment d'évoquer le lien très particulier
entre B et ladite chaîne : en effet, B est dite matrice de transition de la 
chaîne
de Markov associée, et conjointement à la loi initiale, elle caractérise la 
chaîne.
C'est par l'étude des puissances successives de la matrice de transition que
l'on étudie la loi limite de la chaîne, et c'est d'ailleurs en quelque sorte la
démarche qui est mise en oeuvre dans ce sujet.
De plus, il existe différents moyens de définir cette « matrice de transition » 
: il est en effet possible de la définir par la relation plus naturelle
Bi,j = P (Sk = j|Sk-1 = i), ce qui permet d'obtenir directement une matrice
stochastique, mais on passera alors d'un état du système à l'autre en multit
pliant B par le vecteur ligne Xk à gauche, ce qui est bien moins pratique.
I.3 En s'intéressant aux coefficients de B, on remarque que pour tout j  [[ 1 ; 
5 ]],
5
P

bi,j = 1

i=1
t

Ainsi, en notant V = (1, 1, 1, 1, 1), il vient pour tout i  [[ 1 ; 5 ]],
5

P
t
t 
BV i =
B i,j vj
=

j=1
5
P

bj,i

car vj = 1 pour tout j  [[ 1 ; 5 ]]

j=1
t

BV

t

Par suite, B V = V et

i

=1

par la remarque précédente

Le réel 1 est valeur propre de t B, associée au vecteur propre V = t (1, 1, 1, 
1, 1).
C'est un résultat classique que si la somme de chaque ligne d'une matrice M
vaut 1, alors t (1, 1, . . . , 1) est un vecteur propre de M pour la valeur 
propre 1.
I.4 Les Sk ont toutes la même loi si pour tout n  N, Xn = X0 . Montrons donc par
récurrence que la propriété :
P(n) :

Xn = X0

est vraie pour tout n > 0.
· P(0) est vraie car X0 = X0 .
· P(n) = P(n + 1) : Soit n  N. Supposons P(n) vraie et montrons qu'alors
P(n + 1) l'est aussi. D'après la question I.2 et l'hypothèse de récurrence,
Xn+1 = BXn = BX0
Calculons alors BX0 :

0 1/3 1/3 1/3 1/3

1/4 0 1/3 0 1/3 3/16 3/16

 3/16 = 3/16 = X0
0
0
BX0 = 

1/4 0 1/3 0 1/3 3/16 3/16

1/4 1/3 0 1/3 0