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