CCP Maths PSI 2016

Thème de l'épreuve Puissances d'une matrice stochastique
Principaux outils utilisés réduction, diagonalisation, probabilités, suites numériques
Mots clefs matrice stochastique

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


SESSION 2016 PSIMA02 ! ! ! EPREUVE SPECIFIQUE - FILIERE PSI! !!!!!!!!!!!!!!!!!!!!" ! MATHEMATIQUES Mardi 3 mai : 14 h - 18 h! !!!!!!!!!!!!!!!!!!!!" N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.! ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" ! ! ! Les calculatrices sont autorisees ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 1/7 ! Notations et definitions ­ R designe l'ensemble des nombres reels et C l'ensemble des nombres complexes. ­ Si n, m sont deux entiers naturels non nuls, on designe par Mn,m (R) [respectivement Mn,m (C)] l'espace vectoriel des matrices a n lignes et m colonnes a coefficients dans R [respectivement dans C]. Comme Mn,m (R) est contenu dans Mn,m (C), une matrice a coefficients reels est aussi a coefficients complexes. ­ Si n = m, on note Mn (R) [respectivement Mn (C)] pour Mn,n (R) [respectivement Mn,n (C)]. ­ In designe la matrice identite de Mn (R) [respectivement Mn (C)]. ­ Si (Mn )nN est une suite de matrices de Mn (R), on dit que cette suite converge vers une matrice L Mn (R) si, pour tout couple (i, j) 1, n2 , la suite (Mn (i, j))nN des coefficients d'indice (i, j) de Mn converge vers le coefficient, note L(i, j), d'indice (i, j) de L. x1 . . ­ Un vecteur (x1 , · · · , xn ) de Rn [respectivement de Cn ] est identifie a l'element . de xn Mn,1 (R) [respectivement Mn,1 (C)]. ­ Pour tout vecteur x = (x1 , · · · , xn ) Cn , on note x = max {|xi | ; 1 i n} . ­ Pour toute matrice A Mn (C) , on designe par Sp (A) l'ensemble de toutes les valeurs propres complexes de A et on note : (A) = max || . Sp(A) On rappelle que (A) est le rayon spectral de A. ­ Si X est une variable aleatoire definie sur un espace probabilise (, A, P) P(X X() = {x1 , · · · , xn } R, on identifie la loi PX de X au vecteur colonne P(X telle que = x1 ) .. . . = xn ) Objectifs L'objet de ce probleme est d'etudier la suite des puissances d'une matrice stochastique. La premiere partie est consacree a cette etude dans le cas ou n = 2. Dans la seconde partie, on etudie le spectre des matrices stochastiques. Dans la troisieme partie, on etudie l'existence d'une probabilite invariante par une matrice stochastique et la derniere partie est consacree a l'etude des puissances d'une telle matrice. 2/7 Partie I Cas n = 2 On suppose dans cette partie que n = 2 et, pour [0, 1] et [0, 1] avec (, ) = (0, 0), on note : A(, ) = 1- 1- . Il pourra etre utile de noter = 1 - ( + ). I.1 Puissances de A(, ) Q1. Montrer que 1 est valeur propre de A(, ) et determiner le sous-espace propre associe. Q2. Montrer que A(, ) est diagonalisable dans M2 (R) et la diagonaliser. Q3. Calculer, pour tout entier p N, la matrice A(, )p . Q4. Montrer que, pour (, ) = (1, 1), la suite (A(, )p )pN converge vers une matrice L(, ) que l'on precisera. Que se passe-t-il pour (, ) = (1, 1) ? I.2 Application Soient et deux reels de ]0, 1[. Un message binaire de longueur , c'est-a-dire une suite finie (a1 , a2 , · · · , a ) ou pour tout i {1, · · · , }, ai {0, 1}, est transmis dans un reseau forme de relais. On suppose que, a chaque relais, un element x {0, 1} est transmis avec une probabilite d'erreur egale a pour un passage de 0 a 1 et pour un passage de 1 a 0. On note X0 la variable aleatoire definissant le message initial de longueur et, pour n N , au n-ieme relais, le resultat du transfert est note Xn . On suppose que les relais sont independants les uns des autres et que les erreurs sur les bits constituant le message sont independantes. Q5. Cas = 1 Montrer que pour tout entier n 0 : 1- P (Xn = 0) P (Xn+1 = 0) = . 1- P (Xn = 1) P (Xn+1 = 1) Calculer, pour n > 0, P(Xn = 0|X0 = 0) et P(Xn = 1|X0 = 1). , montrer que la probabilite pour que Xn soit conforme a X0 est , Si r = min + + superieure ou egale a : r + (1 - r)(1 - - )n . 3/7 Q6. Cas > 1 On pose Xn = Xn1 , · · · , Xn ou, pour k {1, · · · , }, Xnk est le resultat de la transmission du k-ieme bit au n-ieme relais. Soit Qn la probabilite pour que le message Xn soit conforme au message initial. Montrer que Qn verifie : Qn (r + (1 - r) (1 - - )n ) . Q7. On suppose dans cette question que = . Que peut-on dire dans ce cas de l'inegalite precedente ? Pour tout ]0, 1[, determiner un entier nc tel que la probabilite d'obtenir un message errone au n-ieme relais soit superieure ou egale a (on dit que nc est la taille critique du reseau). Partie II Spectre des matrices stochastiques Dans cette partie, les matrices considerees sont carrees et d'ordre n 2. On dit qu'une matrice A = (ai,j )1i,jn Mn (R) est stochastique [respectivement strictement stochastique] si et seulement si elle est a coefficients positifs [respectivement strictement positifs] et : i {1, · · · , n} , n aij = 1. j=1 II.1 Coefficients Q8. Soit A = (ai,j )1i,jn Mn (R) une matrice stochastique [respectivement strictement stochastique]. Montrer que pour tous i, j compris entre 1 et n on a : 0 aij 1 [respectivement 0 < aij < 1]. Q9. Montrer qu'une matrice A a coefficients reels positifs est stochastique si et seulement si 1 est valeur propre de A et le vecteur e de coordonnees (1, · · · , 1) est un vecteur propre associe. Q10. Montrer que le produit de deux matrices stochastiques [respectivement strictement stochastiques] est une matrice stochastique [respectivement strictement stochastique]. II.2 Valeurs propres Soit A Mn (R) une matrice stochastique. Q11. Montrer que x Cn , p N, Ap x x . 4/7 Q12. Montrer que (A) = 1. II.3 Diagonale strictement dominante Une matrice A Mn (C) est dite a diagonale strictement dominante si et seulement si i {1, · · · , n} , |aii | > n |aij | . j=1 j=i Q13. Soit A une matrice quelconque dans Mn (C) et soit C une valeur propre de A. Montrer qu'il existe un indice i {1, 2, · · · , n} tel que : | - aii | n |aij | . j=1 j=i Q14. Montrer qu'une matrice A Mn (C) a diagonale strictement dominante est inversible. II.4 Valeur propre de module maximal Soit A = (ai,j )1i,jn Mn (R) une matrice strictement stochastique. Q15. On designe par A1 = (ai,j )1i,jn-1 Mn-1 (R) la matrice extraite de A en supprimant sa derniere ligne et sa derniere colonne. Montrer que la matrice A1 - In-1 est a diagonale strictement dominante. Que peut-on en deduire quant au rang de A - I ? Q16. Montrer que ker (A - In ) est de dimension 1. Q17. Soit Sp (A) \ {1} . Montrer que || < 1. Partie III Probabilite invariante On considere quatre points dans le plan numerotes de 1 a 4. Une particule se deplace chaque seconde sur l'ensemble de ces points de la facon suivante : si elle se trouve au point i, elle reste au 1 ou passe en un point j = i de facon equiprobable. point i avec une probabilite egale a 10 III.1 Une suite de variables aleatoires On note X0 une variable aleatoire de loi position du point en l'instant n = 0, Xn P0 donnant la P(Xn = 1) .. la loi de Xn . la position du point a l'instant n et Pn = . P(Xn = 4) 5/7 Q18. Montrer qu'il existe une matrice Q, que l'on determinera, telle que : P1 = QP0 . Calculer Pn en fonction de Q et de P0 . p1 p2 Q19. Montrer qu'il existe un unique vecteur = p , que l'on determinera, tel que : 3 p4 4 i {1, · · · , 4}, pi 0 pi = 1 et = Q. i=1 III.2 Rapidite de convergence Q20. Montrer sans calcul que Q est diagonalisable sur R. Q21. Determiner les valeurs propres et les sous-espaces propres de Q. Q22. En deduire que (Qp )pN converge vers une matrice R que l'on precisera en fonction de et qu'il existe r ]0, 1[ tel que : Qp - R = O (rp ) . En deduire que (Pn )nN admet une limite independante de la loi de X0 et interpreter le resultat obtenu. Partie IV Puissances d'une matrice stochastique Soit A = (ai,j )1i,jn Mn (R) une matrice strictement stochastique. On note : m = min aij . 1i,jn (p) Pour tout entier naturel non nul p, on note ai,j le coefficient d'indice (i, j) de Ap : (p) p . A = ai,j 1i,jn Enfin, pour tout entier j compris entre 1 et n, on note : (p) (p) (p) mj = min ak,j , Mj 1kn 6/7 (p) = max ak,j . 1kn Q23. Encadrement Montrer que, pour tout entier naturel non nul p et tout entier j compris entre 1 et n, on a : (p) (p+1) 0 < mj mj Q24. (p+1) Mj (p) Mj . Minoration Montrer que, pour tout entier naturel non nul p et tout entier j compris entre 1 et n, on a : (p+1) (p) (p) (p) (p) (p+1) (p) (p) et Mj - Mj - mj m Mj - mj m Mj - mj . mj Q25. Majoration Montrer que, pour tout entier naturel non nul p et tout entier j compris entre 1 et n, on a : (p+1) (p+1) (p) (p) - mj (1 - 2m) Mj - mj . Mj Q26. Convergence de ces suites (p) En deduire que, pour tout entier j compris entre 1 et n, les suites mj et pN (p) Mj pN sont adjacentes. Q27. Conclusion En deduire que la suite (Ap )pN converge vers une matrice L stochastique dont toutes les lignes sont identiques. FIN 7/7

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


 CCP Maths PSI 2016 -- Corrigé Ce corrigé est proposé par Sélim Cornet (ENS Cachan) ; il a été relu par Tristan Poullaouec (Professeur en CPGE) et Antoine Sihrener (Professeur en CPGE). L'épreuve est constituée d'un seul problème, portant sur l'étude des puissances d'une matrice stochastique. Les matrices stochastiques sont les matrices réelles à coefficients positifs dont la somme des coefficients de chaque ligne vaut 1. Ces matrices apparaissent notamment en modélisation de phénomènes aléatoires (d'où leur nom, stochastique étant synonyme d'aléatoire). · La partie I propose de calculer explicitement le terme général de la suite des puissances d'une matrice stochastique de taille 2 × 2. On applique ensuite ce résultat au calcul de la probabilité de bonne transmission d'un signal binaire à travers un ensemble de relais. · Dans la partie II, on démontre plusieurs résultats portant sur les éléments propres d'une matrice stochastique, notamment que 1 est valeur propre et que toute valeur propre est de module inférieur ou égal à 1. On affine ces résultats dans le cas d'une matrice stochastique à coefficients strictement positifs, en montrant que 1 est valeur propre simple et que toute autre valeur propre est de module strictement inférieur à 1. · Les résultats de la partie II sont mis en application dans la partie III. On y étudie une certaine marche aléatoire sur un graphe à 4 sommets, et en particulier son comportement après un temps très long. · Enfin, on prouve dans la partie IV que la suite des puissances d'une matrice stochastique à coefficients strictement positifs converge vers une matrice stochastique dont toutes les lignes sont égales. Les parties sont indépendantes, à l'exception de la partie III qui nécessite d'utiliser certains résultats obtenus dans la partie II. Ce sujet balaie une vaste partie du programme (algèbre linéaire, probabilités, suites numériques) et constitue une bonne occasion d'entraînement et de révision. Attention toutefois, les questions sont de difficultés assez inégales : certaines ne demandent que des raisonnements classiques, d'autres requièrent plus de recherche et d'initiative. Indications Partie I 1 Déterminer le noyau de A(, ) - I2 . 2 Il se pourrait qu'une deuxième valeur propre soit donnée par l'énoncé... 3 Utiliser la diagonalisation obtenue à la question précédente. 5 Appliquer la formule des probabilités totales pour obtenir la première relation. En déduire par récurrence une relation entre la loi de Xn et celle de X0 . Appliquer à nouveau la formule des probabilités totales pour calculer la probabilité de bonne transmission des messages 0 et 1. Pour l'inégalité, distinguer les cas 6 et > . On écrira la probabilité de bonne transmission comme la somme de r + (1 - r)(1 - - )n et d'une quantité positive. 6 Tirer parti du fait que les variables aléatoires X1n , · · · , Xn sont indépendantes. Partie II 10 Utiliser la caractérisation donnée par la question 9. 11 Remarquer que la question 10 autorise à ne traiter que le cas p = 1. Majorer alors chacune des composantes du vecteur Ax. 12 En exploitant les résultats des questions 9 et 11, montrer successivement que (A) 6 1 et (A) > 1. 13 Considérer un vecteur propre x associé à , et choisir i comme l'indice de la coordonnée de x de plus grand module. 14 Utiliser la question 13 pour montrer que 0 n'est pas valeur propre de A. 15 Vérifier que la définition d'une matrice à diagonale strictement dominante est satisfaite, en notant que l'inégalité stricte provient du fait que les coefficients de A sont strictement positifs. 16 Utiliser les questions 9 et 15. 17 Considérer une valeur propre de module 1 et utiliser la question 13. Partie III 18 Appliquer la formule des probabilités totales pour calculer P(X1 = i) pour tout i. 19 Utiliser les questions 9 et 16. 21 On peut observer qu'il existe µ R tel que Q-µI4 soit de rang 1. Le déterminer. 22 Considérer une base orthonormée de vecteurs propres et appliquer les formules de changement de base. Pour la seconde partie, calculer Qp - R pour p N et utiliser l'homogénéité de la norme. Partie IV 23 Les deuxième et quatrième inégalités s'obtiennent en comparant les coefficients de Ap+1 à ceux de Ap . 24 Exprimer les coefficients de Ap+1 en fonction de ceux de Ap en faisant apparaître le terme correspondant au minimum ou au maximum. 25 Utiliser la question 24. 26 Utiliser les questions 23 et 25. I. Cas n = 2 1 Par définition, A(, ) - I2 = - - Remarquons que la deuxième colonne est l'opposée de la première, et comme (, ) est non nul, la matrice est donc de rang 1. D'après le théorème du rang, dim(Ker (A(, ) - I2 )) = 2 - rg (A(, ) - I2 ) = 1 Cela montre que 1 est valeur propre et comme le sous-espace propre associé est de dimension 1, il suffit de déterminer un de ses vecteurs non nuls pour en obtenir une base. Si t (x, y) R2 , on a ( -x + y = 0 x Ker (A(, ) - I2 ) y x - y = 0 x = y car (, ) 6= (0, 0) Ceci prouve que Le réel 1 est valeur propre de A(, ), de sous-espace propre associé Ker (A(, ) - I2 ) = Vect {t (1, 1)}. Le calcul du polynôme caractéristique est inutile ici car il ne donne aucune information sur les sous-espaces propres. Cette méthode est à réserver aux cas où on ne connaît pas a priori les valeurs propres. 2 La notation = 1-(+) introduite dans l'énoncé incite à penser que pourrait être valeur propre de A(, ). Vérifions-le. 1- 1 - ( + ) 0 A(, ) - I2 = - = 1- 0 1 - ( + ) Remarquons que les deux lignes sont identiques, et non nulles car (, ) 6= (0, 0). La matrice A(, ) - I2 est donc de rang 1, par suite est valeur propre de A(, ) et le sous-espace propre associé est de dimension 1 d'après le théorème du rang. De plus, comme et sont positifs non tous deux nuls, + > 0 d'où 6= 1. Finalement, A(, ) possède deux valeurs propres distinctes, elle est donc diagonalisable. Si l'on ne remarque pas que est valeur propre, le calcul du polynôme caractéristique s'avère alors nécessaire. = X2 - Tr (A(, ))X + det(A(, )) = X2 - (2 - ( + ))X + (1 - ( + )) Son discriminant vaut = (2 - ( + ))2 - 4(1 - ( + )) = ( + )2 = | + | = + , on retrouve bien les valeurs propres p p 2 - ( + ) + ( + )2 2 - ( + ) - ( + )2 r1 = = 1 ; r2 = = 2 2 et puisque Pour obtenir les matrices de passage, il reste à déterminer un vecteur propre associé à . Si t (x, y) R2 , on a ( x + y = 0 x Ker (A(, ) - I2 ) y x + y = 0 x = -y Le vecteur non nul t (, -) est donc un vecteur propre associé à . Si l'on pose 1 1 0 P= et D = 1 - 0 A(, ) = PDP-1 alors Calculons P-1 par opérations élémentaires. Pour calculer l'inverse d'une matrice P, on effectue des opérations élémentaires soit sur les lignes, soit sur les colonnes, mais pas les deux, au risque d'obtenir des résultats erronés. 1 1 0 On part de 1 - 0 1 1 1 0 Effectuons L1 L2 - L1 0 -( + ) -1 1 Continuons avec Terminons par On obtient finalement P-1 = 1 0 1 1 0 0 1 1 + 0 1 - + + + 1 1 - + + , avec + 6= 0, et 1 -1 1 1 + L2 - L2 + L1 L1 - L2 Pour tout couple de réels (, ) [0, 1]2 \{(0, 0)}, 1 0 la matrice A(, ) est égale à P P-1 avec 0 1 1 P= et P-1 = 1 - + 1 -1 3 Pour tout p N, on a A(, )p = (PDP-1 )p = PDp P-1 . La matrice D étant diagonale, on trouve directement que pour tout p N, 1 0 Dp = 0 p En calculant le produit matriciel PDp P-1 , on en déduit p N 1 (, ) [0, 1] \{(0, 0)} A(, ) = + 2 p + p (1 - p ) (1 - p ) + p 4 Pour (, ) 6= (1, 1), on a -1 < 1 - ( + ) < 1, autrement dit || < 1. Il s'ensuit que la suite (p )pN converge vers 0. Finalement, il vient d'après la question 3