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