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é

 : (gratuite si tu crées un compte) - - - - - - - - - - - - - - - - - - - - - - - - -

É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