Calcul matriciel, modèles probabilistes

1Séquence 2 – MA03

Séquence 2

Dans cette séquence, il s’agit de donner les outils de calculs matri-ciels et le vocabulaire des graphes permettant de modéliser et d’étudier l’évolution de systèmes aléatoires à plusieurs états au cours du temps.

Calcul matriciel, modèles probabilistes

Sommaire

1. Pré-requis

2. Calcul matriciel, généralités

3. Calcul matriciel et résolutions de systèmes linéaires

4. Matrices d’ordre 2, systèmes dynamiques à deux états

5. Matrices d’ordre N, systèmes dynamiques à N états avec N ≥ 3

6. Synthèse

© Cned - Académie en ligne


1 Pré-requisProbabilités Conditionnement par un événement de probabilité non nulle

Soient A et B deux événements d’un univers Ω tels que P A( ) .≠ 0

On appelle probabilité de l’événement B, sachant que A est réalisé, le nombre

noté P BA( ), lu « P de B sachant A », défini par : P BP A B

P AA ( )( )

( ).= ∩

Définition

P BA B

AA( )( )

( )= ∩card

card lorsqu’il y a équiprobabilité.

P AA( ) ,= 1 0 1≤ ≤P BA( ) .

Si A et B sont deux événements incompatibles (c’est-à-dire si A B∩ = ∅), on a P A B( )∩ = 0 donc P BA( ) .= 0

Conséquences

Intersection de deux événements

Soient A et B deux événements tels que P A( ) ≠ 0 et P B( ) .≠ 0

P A B P A P BA( ) ( ) ( )∩ = × et P A B P B P AB( ) ( ) ( ).∩ = ×

Propriété

Complémentaire d’un événement

P B P BA A( ) = − ( )1 .Arbre pondéré

B : P(A ∩ B)= P(A) PA(B)

P ∩ = P(A) PAB :A

PA(B)

PA(B)

PA

PA P(A)

P(A) AP ∩ = P(A) PA(B)

P ∩ = P(A) PA

B :

B :B( )

B( )

B( )

B( )B)

B)A(A(

A(

B)

Propriété

A


4 Séquence 2 – MA03

Règles de construction d’un arbre pondéré

On indique sur chaque branche la probabilité du chemin correspondant (c’est éven-tuellement une probabilité conditionnelle).

La somme des probabilités inscrites sur les branches issues d’un même événe-ment (on dit aussi « d’un même noeud ») est égale à 1. Cette règle est parfois appelée « la loi des nœuds ». Elle est une conséquence de la propriété 2 : P B P BA A( ) = − ( )1 .

branches du chemin correspondant.

qui y aboutissent.

Règles d’utilisation d’un arbre pondéré

On dit que les n événements A A A An1 2 3, , ... , d’un univers Ω forment une par-tition de Ω lorsque les événements A A A An1 2 3, , ... , sont incompatibles deux à deux et lorsque leur réunion est égale à Ω.

Définition

On suppose que les événements A A A An1 2 3, , ... , forment une partition de l’univers et que chacun d’eux une probabilité non nulle.

Soit un événement B alors,

P B P A P B P A P BA A( ) ( ) ( )= ( ) + ( ) +…+1 21 2P A P Bn An( ) ( ) :

c’est la formule des probabilités totales.

Propriété

Indépendance

Soient A et B deux événements d’un univers Ω tels que P A( ) ≠ 0 et P B( ) .≠ 0

On dit que les événements A et B sont indépendants quand P A P AB ( ) ( ).==

Définition

Deux événements A et B sont indépendants si et seulement si :P A B P A P B( ) ( ) ( )∩ = × .

Propriété



Si deux événements A et B sont indépendants, alors

A et B sont indépendants,

A et B sont indépendants,

A et B sont indépendants.

Propriété

Cas particulier de la répétition d’expériences identiques

On a choisi une loi de probabilité adaptée. Cette loi consiste à faire le produit des probabilités de chacun des n résultats partiels qui constituent une liste de n résultats de la répétition d’expériences identiques.

On dit qu’il s’agit d’expériences identiques et indépendantes.

Dans ces répétitions, le mot indépendant au sens courant correspond au mot indépendant au sens probabiliste.

Il ne faut pas confondre les notions d’indépendance et d’incompatibilité qui interviennent dans des situations tout à fait différentes : l’incompatibilité de deux événements est utilisée lorsqu’on calcule la probabilité d’une union d’événe-ments alors que c’est dans le calcul de la probabilité d’une intersection que l’in-dépendance peut apparaître.

Union Intersection

Cas général P A B P A P B P A B( ) ( ) ( ) ( )∪ = + − ∩ P A B P A P BA( ) ( ) ( )∩ = ×

Cas particulier

Si les événements A et B sont incompatibles :

P A B P A P B( ) ( ) ( )∪ = +

Si les événements A et B sont indépendants :

P A B P A P B( ) ( ) ( )∩ = ×

Variable aléatoire (programme de 1re S)

On dit qu’on définit une variable aléatoire sur l’ensemble Ω lorsqu’on associe un nombre réel à chaque éventualité de l’expérience aléatoire.

Définition

La loi de probabilité d’une variable aléatoire X est donnée par :

x1, x2,…,xr prises par la variable aléatoire,

les probabilités P X xi( )= pour toutes les valeurs xi prises par X.

Définition



L’espérance de la variable aléatoire X est le nombre, noté E(X), défini par :

X x P X x x P X x x P X x

x p x p x p x p

E( ) ( ) ( ) ... ( )

= .

r r

r r i ii

i r1 1 2 2

1 1 2 2=1∑

= = + = + + =

= + +…+=

Définition

La variance V(X) et l’écart-type σ( )X d’une variable aléatoire X sont définis par :

V E E E( ) ( ) ...X x X p x X p x X pr r= −( ) + − ( )( ) + + − ( )( )12

1 22

22

== − ( )( )=

=∑ x X pi ii

i rE

2

1,

et σ( ) ( ).X X= V

Définition

Une épreuve de Bernoulli est une épreuve aléatoire comportant deux issues, l’une appelée « succès », l’autre appelée « échec ».

Soit X la variable aléatoire qui prend la valeur 1 en cas de réussite et la valeur 0 en cas d’échec.

La variable aléatoire X est appelée variable de Bernoulli et la loi de probabilité de X est appelée loi de Bernoulli.

On note p la probabilité de réussir et donc q p= −1 la probabilité d’échouer.

D’où P p( )X = =1 et P q p( ) .X = = = −0 1Loi de probabilité d’une variable de Bernoulli :

xi 1 0

P X xi( )= p 1− p

Définitions

Soit X la variable aléatoire définie par le nombre de succès dans la répétition n fois, de façon indépendante, d’une épreuve ayant deux issues, succès et échec, pour laquelle la probabilité du succès est égale à p.

La loi de probabilité de X s’appelle la loi binomiale de paramètres n et p, notée ( ).n p;

Définition



La variable aléatoire X prend les n + 1 valeurs 0, 1,… , n avec les probabilités :

P X knk

p pk n k( ) ( )= =

− −1 pour tout entier k tel que 0 ≤ ≤k n.

E( )X = np et V( ) ( ).X = −np p1

Le nombre nk

s’appelle un coefficient binomial.

Propriété

Pour tout entier naturel n, non nul, et tout entier k tel que 0 ≤ ≤k n, on a :

nn

= 1, n0

1

= , nk

nn k

=−

, et,

si 0 1≤ ≤ −k n ,

nk

nk

nk

++

=++

1

1

1.

Propriété

Suites

Suite convergente

On dit qu’une suite ( )un admet pour limite un réel lorsque tout intervalle ouvert contenant contient tous les termes de la suite à partir d’un certain rang.

On note alors lim .n

nu→+∞

=

Lorsqu’une suite ( )un admet une limite finie, on dit qu’elle est convergente (ou qu’elle converge).

Dans le cas contraire, on dit qu’elle est divergente.

Définition

Limites de suites convergentes usuelles

lim lim lim limn n n nn n n→+∞ →+∞ →+∞ →+∞

= = =10

10

102, , ,

1103n

= et plus généralement

lim .n kn

k→+∞

= ∈10 où *N

Toute suite constante de terme général égal à est convergente vers .

Propriété

B



Unicité de la limite d’une suite convergente

Si une suite converge alors sa limite est unique.

Propriété

Opération sur les limites de suites convergentes

Soient (un) et (vn) deux suites convergentes de limites respectives et ′ .

On admet les résultats suivants :

la suite de terme général u vn n+ est convergente et a pour limite + ′ ;

la suite de terme général u vn n× est convergente et a pour limite × ′ ;

la suite de terme général k un× où k est un réel est convergente et a pour limite k × ;

si vn ne s’annule pas à partir d’un certain rang et si ′ ≠ 0 alors la suite de terme

général uv

n

n est convergente et a pour limite

′.

Propriétés

Compatibilité avec l’ordre

Soient (un ) et (vn ) deux suites convergentes de limites respectives et ′ .

Si, à partir d’un certain rang, on a u vn n< (ou bien u vn n≤ ) alors ≤ ′.

Propriété

Si ( )un n n≥ 0est une suite croissante et convergente vers alors, pour tout

n n un≥ ≤0 , .

Conséquence

Des gendarmes

On considère trois suites un( ) , ( )vn et wn( ).Si ( )un et ( )wn sont convergentes vers un même réel et si, à partir d’un certain rang, u v wn n n≤ ≤ alors ( )vn est elle aussi convergente vers .

Théorème



Suites divergentes de limite infinie

On dit qu’une suite (un ) admet pour limite +∞ si tout intervalle de la forme A ; + ∞] [ où A est un réel, contient tous les termes de la suite à partir d’un certain

rang. On note alors lim .n

nu→+∞

= +∞

De façon analogue, on dit qu’une suite (un ) admet pour limite −∞ si tout intervalle de la forme −∞] [; A où A est un réel, contient tous les termes de la suite à partir d’un certain rang. On note alors lim .

nnu

→+∞= −∞

Dans un cas comme dans l’autre, on dit que la suite est divergente.

Définition

Limites de suites divergentes usuelles

On a : lim lim lim limn n n n

n n n→+∞ →+∞ →+∞ →+∞

= +∞ = +∞ = +∞, , ,2 nn3 = +∞ et plus

généralement lim .n

kn k→+∞

= +∞ ∈où *N

Propriété

Limite d’une somme

La limite de la somme u vn n+

limn

nv→+∞

limn

nu→+∞

+∞ −∞

+∞ +∞−∞ −∞

+∞ −∞

Propriété



Limite d’un produit

La limite du produit u vn n×

limn

nv→+∞

limn

nu→+∞

+∞ −∞

+∞ +∞ −∞

−∞ −∞ +∞0

( > 0 ) +∞ −∞

( < 0 ) −∞ +∞

Propriété

Inversion

limn

nv→+∞ lim

n nv→+∞

1

+∞ 0−∞ 0

( ≠ 0 )1

0+ +∞

0− −∞

Propriété

Limite d’un quotient

La limite du quotient

uv

n

n

limn

nv→+∞

limn

nu→+∞

+∞ −∞ 0+ 0− ′ ( ′ ≠ 0 )

+∞ +∞ −∞ +∞ ou −∞−∞ −∞ +∞ +∞ ou −∞0 0 0 0

( > 0 ) 0 0 +∞ −∞ / '

( < 0 ) 0 0 −∞ +∞ ′

Propriété



Comparaison en +

Les suites ( )un et ( )vn sont telles qu’à partir d’un certain rang, u vn n≤ .

Si limn

nu→+∞

= +∞ alors lim .n

nv→+∞

= +∞

Si limn

nv→+∞

= −∞ alors lim .n

nu→+∞

= −∞

Propriété

Cas des suites géométriques

Soit q un réel.

Si q > 1 alors la suite de terme général qn est divergente et on a lim .n

nq→+∞

= +∞

Si − < <1 1q alors la suite de terme général qn est convergente et on a lim .n

nq→+∞

= 0

Si q ≤ −1 alors la suite de terme général qn est divergente et n’a pas de limite.

Propriétés

Cas des suites monotones divergentes

Si une suite ( )un est croissante et non majorée alors lim .n

nu→+∞

= +∞

Si une suite ( )un est décroissante et non minorée alors lim .n

nu→+∞

= −∞

Propriétés

De la convergence monotone

Si une suite est croissante et majorée alors elle est convergente.

Si une suite est décroissante et minorée alors elle est convergente.

Théorème



Objectifs du chapitre

Sur un exemple, introduire la modélisation d’une situation à l’aide d’une matrice et la définition du produit matriciel. Utiliser cette modélisation pour résoudre des problèmes.

Définir les matrices et les opérations sur les matrices.

Ces outils seront utilisés dans les chapitres suivants pour étudier des marches aléatoires sur un graphe.

Notre exemple d’introduction utilise un graphe ; nous en profitons pour donner le vocabulaire sur les graphes, nécessaire pour la suite.

Pour débuter : Un réseau routier

On peut représenter le réseau routier du bourg d’un petit village par le graphe suivant :

1

Mairie

BarTabac-presseDépôt de pain

Église

École

2

3 4

Figure 1. Un réseau routier

A

B

2 Calcul matriciel, généralités



Le point 1 représente « la mairie », le 2 « l’école », le 3 « le bar tabac-presse et dépôt de pain » et le 4 « l’église ».

Un arc orienté de 1 vers 3, noté 1 3→ , signifie que la rue joignant les points 1 et 3 est circulable dans le sens 1 vers 3 ; l’absence d’arc orienté de 3 vers 1 signifie qu’elle n’est pas circulable dans l’autre sens : elle est à sens unique de 1 vers 3.

On peut représenter ce réseau routier par un tableau de nombres à deux entrées :

i

↵

j 1 2 3 4

1 0 0 1 1

2 1 0 1 0

3 0 1 0 1

4 0 1 0 0

Le nombre 1 situé ligne 1 et colonne 3 signifie l’existence d’un arc orienté 1 3→ . Le nombre 0 situé ligne 3 et colonne 1 signifie l’absence d’arc orienté de 3 vers 1. On dit que le tableau de nombres est la matrice associée au graphe du réseau routier, on le note :

A aij i j= ( )1 4, 1 4≤ ≤ ≤ ≤ .

Le nombre aij situé à l’intersection de la ligne i et de la colonne j s’appelle le coefficient ou terme d’indice ( )i j; de la matrice A.

La matrice A aij i j= ( )1 4, 1 4≤ ≤ ≤ ≤ associée au graphe est définie par :

ai j

ij =1

0 .

si

sinon

→

Compter les chemins

On cherche à compter le nombre de chemins de longueur deux pour se rendre d’un point à un autre.

Pour commencer, cherchons le nombre de chemins de longueur deux pour se rendre du point 1au point 2. On trouve deux chemins :

1 3 3 2

1 4 4 2

→ →→ →

puis

puis .

De manière générale, écrivons l’ensemble des chemins de i vers k (premier tableau) et l’ensemble des chemins de k vers j (deuxième tabeau).

i

↵

k 1 2 3 4

k

↵

j 1 2 3 4

1 0 0 1 1 1 0 0 1 1

2 1 0 1 0 2 1 0 1 0

3 0 1 0 1 3 0 1 0 1

4 0 1 0 0 4 0 1 0 0



Trouver le nombre de chemins de longueur deux pour se rendre du point 1 au point 2 revient à multiplier la ligne 1 du premier tableau par la colonne 2 du deuxième tableau :

0 0 1 1

0011

= 11 12 12 22 13 32( )

× + × + × +a a a a a a aa a14 42

= 0 0 0 0 1 1 1 1= 2

×

× + × + × + × .

Regardons le produit a a13 32 = 1× : il existe un arc 1 3→ et un arc 3 2→ donc il existe un chemin de longueur deux, de 1 vers 2 en passant par 3.

Cherchons à présent le nombre de chemins de longueur deux pour se rendre du point 4 au point 3 : on effectue le produit de la ligne 4 du premier tableau par la colonne 3 du deuxième tableau :

0 1 0 0

1100

= 41 13 42 23 43 33( )

× + × + × +a a a a a a aa a44 43

= 0 1 1 1 0 0 0 0 = 1

×

× + × + × + × .

Regardons le produit a a41 13 = 0 1= 0× × : il existe un arc de 1 3→ mais pas de 4 vers 1 donc il n’existe pas de chemin de longueur deux, de 4 vers 3 en passant par 1.

Par contre, a a42 23 = 1 1 1× × = : il existe un arc 4 2→ et un arc 2 3→ donc il

existe un chemin de longueur deux de 4 vers 3 en passant par 2.

De manière générale, pour déterminer le nombre de chemins de longueur deux pour se rendre du point i au point j, on effectue le produit de la ligne i du premier tableau par la colonne j du deuxième tableau :

a a a a

a

a

a

a

ai i i i

j

j

j

j

i1 2 3 4

1

2

3

4

=( )

11 1 2 2 3 3 4 4 =× + × + × + ×a a a a a a a mj i j i j i j ij .

On peut placer les nombres

mij obtenus dans un tableau à l’intersection des

lignes i et j :

i

↵k 1 2 3 4k

↵j 1 2 3 4i

↵

j 1 2 3 4

1 0 0 1 1 1 0 0 1 1 1 0 2 0 1

2 1 0 1 0 2 1 0 1 0 2 0 1 1 2

3 0 1 0 1 3 0 1 0 1 3 1 1 1 0

4 0 1 0 0 4 0 1 0 0 4 1 0 1 0

A A = M



On dit que M est le produit de la matrice A par elle même.

Pour aller plus loin

Sauriez vous déterminer le nombre de chemins de longueur 3, de longueur 4 dans ce réseau routier (voir exercice d’apprentissage) ?

Cours

1. Vocabulaire des graphes

L’exemple de réseau routier est ce que l’on appelle un graphe. Dans la suite de ce cours, nous manipulons ce type d’objet pour modéliser un grand nombre de situations. Nous donnons ci-dessous le vocabulaire nécessaire.

a) Définitions

Graphe

Un graphe est constitué d’un ensemble de points reliés par des arcs.

Sommet

Un point du graphe est appelé un sommet.

Arête

Un arc reliant deux sommets est appelé une arête.

Graphe orienté

Lorsque ces arêtes sont munies d’un sens, on dit que le graphe est orienté.

Graphe pondéré, poids d’une arête

Lorsque ces arêtes sont affectées de coefficients positifs, on dit que le graphe est pondéré et le coefficient associé à une arête est appelé le poids de l’arête.

Graphe probabiliste

Lorsque la somme des poids des arêtes issues de chaque sommet est égale à 1, on dit que le graphe est un graphe probabiliste.

Définition 1

Dans la suite, nous ne considérerons que des graphes probabilistes.

C



b) Exemples

1

2 3

54

1

20,4

0,2

0,1

0,5

0,1 0,7

1

1

0,3

0,7

3

54

Figure 2. Graphe orienté Figure 3. Graphe probabiliste

2. Matrice de transition d’un graphe

La matrice de transition associée à un graphe comportant p sommets est un tableau de nombres comportant p lignes et p colonnes.

Pour un graphe orienté non pondéré, le nombre situé à l’intersection de la ligne i et de la colonne j est 1 s’il existe une arête orientée de i vers j i j→( ),et est égal à 0 sinon.

Pour un graphe probabiliste, le nombre situé à l’intersection de la ligne i et de la colonne j est le poids de l’arête orientée de i vers j.

On appelle M1 et M2 les matrices de transition associées respectivement aux graphes de l’exemple précédent (Figure 2 et Figure 3) :

M1 =

1 1 0 1 0

0 0 1 1 1

0 1 0 0 0

0 0 0 0 1

0 0 1 0 1

et M2 =

0,1 0,4 0 0,5 0

0 0 0,2 0,1 0,7

0 1 0 0 0

0 0 0 0 1

0 0 0,77 0 0,3

.

La matrice M2 s’appelle une matrice stochastique car tous ses coefficients sont compris entre 0 et 1, et la somme des coefficients de chaque ligne est égale à 1.

Exemples



3. La notion de matrice

Matrices n p

Une matrice de dimension n p× est un tableau rectangulaire de nombres compor-tant n lignes et p colonnes. Ces nombres sont appelés les coefficients ou termes de la matrice.

Définition 2

La matrice A est une matrice 2 3× , B est une matrice 2 1× dite matrice colonne ou vecteur colonne et C est une matrice 1 3× dite matrice ligne ou vecteur ligne.

A B C=2 1 3

5 2 3 6, =

2

3= 4 5 2

−

− −

−

−( )et .

Le coefficient de la matrice A situé à l’intersection de la ligne i et de la colonne j se note aij .

Ai a

j

ij=

→

↓

.

Matrices carrées d’ordre p

C’est une matrice ayant le même nombre p de lignes et de colonnes.

Définition 3

La matrice A =1 2

1 4

−−

est une matrice carrée d’ordre 2.

La matrice B =

1 3 1

4 2 3

2 0 4

−

−

est une matrice carrée d’ordre 3.

Soit A une matrice carrée. on note ai,j le coefficient de A apparaissant à la i-ème ligne et j-ème colonne.

La diagonale de A est l’ensemble de ces coefficients ai,j tels que i = j. On dit que :

A est diagonale si tous ces coefficients sont nuls, sauf peut être ceux de sa diagonale ;

A est triangulaire supérieure (resp. inférieure) si tous ces coefficients sont nuls, sauf peut être ceux de sa diagonale et ceux qui sont au-dessus (resp. en dessous) de la diagonale.

Exemples

Exemples

Vocabulaire



A =

1 2 3 10 3 5 08

5

7

8

11 0

2

−

−

1

1 1 0

0

=−

B

5 3

0 0 1

est trianngulaire supérieure.

4. Opérations sur les matrices

a) Égalité de matrices

Deux matrices A et B sont égales si elles ont les mêmes dimensions et si chaque coefficient de A est égal au coefficient correspondant de B : pour toute ligne i et toute colonne j, a bij ij= .

b) Addition de matrices

La somme de deux matrices de même dimension est la matrice de même dimension dont chaque coefficient est la somme des deux coefficients situés à la même place.

Calculer A + B dans les cas suivants :

a) A =2 1

4 3

−−

et B =3 6

0 5

−−

.

b) A =2 3 0

12

0 6

−

−

et

B =0

23

8

1 3 6

.

a) On a : A B+ − − +− + −

=−− −

= 2 3 1 64 0 3 5

1 5

4 2

.

b) On a : A B+−

=2

73

8

32

3 0.

L’addition de matrices est commutative : A B B A+ += .

Propriété 1

La matrice opposée d’une matrice A aij i n j p= ( )1 , 1≤ ≤ ≤ ≤ est la matrice, notée −A définie par − − ≤ ≤ ≤ ≤A aij i n j p= ( )1 , 1 dont tous les coefficients sont les opposés des coefficients de A.

La matrice nulle de dimension n p× , notée 0 est la matrice dont tous les coeffi-cients sont nuls.

Définition 4

Exemples

Exemple 1

Solution

diagonale de A



Soit A =1 2

3 4−

. Déterminer son opposée.

On a −− −

−

A =1 2

3 4 et A A+ −( ) = 0.

La matrice A B+ −( ) se note A B− .

c) Multiplication par un nombre

Le produit d’une matrice par un nombre réel k est la matrice de même dimension notée k A⋅ dont les coefficients sont égaux au produit des coefficients de A situés à la même place par le nombre k.

Soient

A =2 0

1 4−

et

B =

2 1 5

4 3 2

1 2 4

−− −

.

Calculer 3 5⋅ ⋅A Bet .

On a :

3 =3 2 01 4

= 6 03 12

⋅ ⋅−

−

A ;

5 =52 1 54 3 21 2 4

=10 5 2520 15 105 10 20

⋅ ⋅−

− −

−− −

B

.

L’opposée de la matrice A est la matrice A multipliée par −1: − − ⋅A A= ( 1) .

On a : 0 ⋅ =A 0 et 1⋅ =A A.

d) Multiplication de matrices

Étude d’un exemple

Soient A =1 2

3 4

−

et B =3 5

1 6−

.

Le produit de ces deux matrices d’ordre 2 est une matrice d’ordre 2 :

A Bm m

m mM⋅

= =11 12

21 22.

Pour calculer m11, il faut prendre en compte la première ligne de A et la première colonne de B :

1 23

11 3 ( 2) ( 1)=5−( )

−

× + − × −et faire .

Exemple 2

Solution

Remarque

Exemple 3

Solution

Remarque



Pour calculer m12, il faut prendre en compte la 1re ligne de A et la 2e colonne de B :

1 25

61 5 ( 2) 6= 7−( )

× + − × −et faire .

Pour calculer m21, il faut prendre en compte la 2e ligne de A et la 1re colonne de B :

3 4 31

et faire 3 ( 3) 4 1=( )−

× − + × −

Pour calculer m22, il faut prendre en compte la 2e ligne de A et la 2e colonne de B :

3 45

63 5 4 6=39( )

× + ×et faire .

Finalement, A B⋅ −−

= 5 7

5 39.

Cas général

Le produit d’une matrice A de dimension n p× par une matrice B de dimension p q× est la matrice de dimension n q× , notée A B⋅ , dont le coefficient situé à l’intersection de la i-ème ligne et de la j-ème colonne est égal au produit de la i-ème ligne de la matrice A et de la j-ème colonne de la matrice B.

B

b

b

b

j

j

pj

=

1

2

A a a ai i ip=

1 2

ia b A Bik kjkp

=∑

=1 .

Autrement dit, si C est la matrice A . B et si ci ,j est le coefficient de la i-ème ligne et de la j-ème colonne de C alors :

ci, j = ai, 1× b1, j + ai,2 × b1, 2+…+ ai, p × bp, j.

Le produit de deux matrices ne peut s’effectuer que si le nombre de colonnes de la première matrice est égal au nombre de lignes de la seconde matrice.

On définit les matrices unités d’ordre 2, 3, ... par l l2 31 00 1

1 0 00 1 00 0 1

=

=

, .

Lorsqu’il n’y a pas d’ambiguïté sur l’ordre de la matrice identité, on note simplement I.

Définition 5

Dans chacun des cas suivants, calculer A B⋅ .

a) A =

4 7

1 2

et B =2 5

1 3

−−

.

Remarque

Exemple 4



b) A =

4 7

1 2

et B I=

2 =

1 0

0 1.

c) A =

5 3 2

4 0 1

−

et B =

2 4 0

4 1 5

1 3 2

−−

.

a) On a : A B⋅× + × − × − + ×× + × − × − + ×

=4 2 7 ( 1) 4 ( 5) 7 3

1 2 2 ( 1) 1 ( 5) 2 33=

1 1

0 1

.

b) On a : A I⋅× + × × + ×× + × × + ×

2 =

4 1 7 0 4 0 7 1

1 1 2 0 1 0 2 1= 4 7

1 2

= A.

c) On a :

A B⋅− × + × − + × − − × + × + × − × + × + ×

=5 2 3 ( 4) 2 ( 1) 5 4 3 1 2 3 5 0 3 5 2 2

4 ×× + × − + × − × + × + × × + × + ×

2 0 ( 4) 1 ( 1) 4 4 0 1 1 3 4 0 0 5 1 2

soit A B⋅− −

=24 11 19

7 19 2.

Dans ce dernier cas, B A⋅ est impossible à effectuer.

Pour toute matrice carrée A, on a A I I A A⋅ = ⋅ = et 0 . A = A . 0 = 0

Propriété 2

Le produit de matrices n’est pas commutatif. En général, A B B A⋅ ≠ ⋅ .

Lorsque A . B = B . A, on dit que A et B commutent. Donc pour toute matrice carrée A, A et I commutent.

Soient A =4 7

1 2

et B =2 5

1 3

−−

Calculer A B B A⋅ ⋅et .

On a A B⋅

=1 1

0 1 et B A⋅

− −

=3 4

1 1.

Cas de la multiplication d’un vecteur ligne par une matrice. Il faut placer le vecteur avant :

2 61 2

4 3= 26 22−( )⋅

−−

−( ).

Le produit 1 2

4 32 6

−−

⋅ −( ) est impossible à effectuer.

Solution

Remarque

Remarque

Exemple 5

Solution

Cas particulier : produit d’une matrice par un vecteur

Remarque



Cas de la multiplication d’une matrice par un vecteur colonne. Il faut placer le vecteur après :

5 1

0 2

2

3=

13

6

−

⋅−

−

.

Le produit −

⋅−

2

3

5 1

0 2 est impossible à effectuer.

Considérons le produit d’un vecteur ligne par un vecteur colonne suivant :

U V⋅ −( )

× + − ×= 2 132

= 2 3 ( 1) 2 = 4.

Chaque matrice colonne ou ligne peut être vue comme les coordonnées d’un vecteur du plan muni d’un repère orthonormé : on dit que l’on identifie les matrices colonnes ou lignes aux vecteurs du plan. La matrice U correspond au vecteur u

de coordonnées

(2 ; 1)− et la matrice V au vecteur v(3 ; 2). En

identifiant aussi les matrices 1 1× avec les nombres réels, le produit U V⋅ est alors le produit scalaire des vecteurs u

et v.

–1

–2

1

1

2

3

v

u

2 3 4

e) Calcul algébrique sur les matrices carrées

Soit A une matrice non nulle d’ordre p. Soit n un entier naturel ; on définit la matrice An par

A I

A A A A n

p

n

n

0 =

= 1.⋅ ⋅ ⋅ ≥

...fois

si

Définition 6

L’écriture A0 n’a pas de sens si A est la matrice nulle.

Soit A =2 1

1 3

−

. Calculer A2 et A3.

On a A2 =2 1

1 3

2 1

1 3=

3 5

5 8

−

−

−

et A3 =3 5

5 8

2 1

1 3=

1 18

18 19

−

−

−

.

Pour toutes matrices carrées A et B de même ordre, pour tous réels k et k , on a ( ) ( ) = ( ) ( )k A k B k k A B⋅ ⋅ ′ ⋅ × ′ ⋅ ⋅ .

Propriété 3

Remarque

Cas particulier : produit d’un vec-teur ligne par un vecteur colonne

Remarque

Exemple 6

Solution



Associativité

Pour toutes matrices A, B et C carrées de même ordre, on a A B C A B C⋅ ⋅ ⋅ ⋅( ) = ( ) . On écrit A B C⋅ ⋅ .

Propriété 4

On en déduit que pour tout entier naturel p et q, et toute matrice carrée non

nulle, A A A A Ap q p q pq p q+ = × = ( )et .

Distributivité

Pour toutes matrices A et B carrées de même ordre, pour tout réel k, on a k A B k A k B⋅ + ⋅ + ⋅( ) = .

Pour toute matrice A, pour tous réels k et k , on a ( ) =k k A k A k A+ ′ ⋅ ⋅ + ′ ⋅ .

Pour toutes matrices A, B et C carrées de même ordre, on a :

A B C A B A C B C A B A C A⋅ + ⋅ + ⋅ + ⋅ ⋅ + ⋅( ) = ( ) = .et

Propriété 5

Notation : comme dans on note AB pour A B⋅ .

Les règles de calcul sont celles du calcul littéral habituel mais il faut faire attention à la non commutativité du produit. Par exemple, regardons ce qu’il advient des identités remarquables : soient A et B deux matrices carrées de même ordre :

( ) ( ) ( )2 2 2 2 2A B A AB BA B A B A B A BA AB B+ = + + + + ⋅ − = + − −et .

En général, on ne peut pas simplifier davantage !

Soient A et B deux matrices carrées d’ordre .

Calculer I A+( )3 et I A I B I A I B+( ) +( )− +( ) +( )5

on a : I A I A I A

I A I A A I A I A A I A

I A I A A A

( ) ;

2 ( ) ; puisque

3 3 ;

3 2

3 2

3 2 3

( )( ) ( )( )

( )

+ = + +

+ = + + + ⋅ = ⋅ =

+ = + + +

I A I B I A I B I A I B I B I A+( ) +( )− +( ) +( ) = + + − − = +5 5 4( )( ) ( ) ( ) .I I A= +4 4

Remarque

Exemple 7

Solution



5. Inverse d’une matrice

a) Définition

Soit A une matrice carrée d’ordre p. On dit que la matrice carrée B d’ordre p est

l’inverse de la matrice A si B A A B Ip⋅ ⋅= = .

La matrice B se note alors A−1.

S’il existe une matrice inverse de A, on dit que A est inversible.

Définition 7

L’inverse d’une matrice, s’il existe, est unique.

Propriété 6

Soit A une matrice inversible ; on suppose qu’il existe deux matrices B et C telles que B A A B I⋅ ⋅= = etC A A C I⋅ ⋅= = .

Montrons que B =C.

On a C C I C A B= ⋅ ⋅ ⋅= car A B I⋅ = , or C A I⋅ = d’oùC I B B= =⋅ .

Soient A B=4 7

1 2=

2 7

1 4

−−

et . Montrer que B est l’inverse de A.

On a A B I⋅

−−

=4 7

1 2

2 7

1 4=

1 0

0 1= 2

et

B A I⋅−

−

=2 7

1 4

4 7

1 2=

1 0

0 1= 2

donc B est la matrice inverse de A : B A= 1− .

Ou encore A est la matrice inverse de B : A B= 1− .

L’inverse de l’inverse d’une matrice est la matrice elle-même : A A− −( )1 1= .

Soient A et B deux matrices inversibles, alors AB est inversible et l’inverse de AB est

B A− −1 1 : ( ) 1 1 1AB B A−− −− −−== .

Propriété 7

Démonstration

Exemple 8

Solution

Remarque



On a B A AB B IB B B I− − − −= = =1 1 1 1 et ABB A A IA A A I− − − −= = =1 1 1 1 donc la matrice produit AB est inversible et B A− −1 1 est bien son inverse.

b) Inversibilité des matrices d’ordre 2

Déterminant d’une matrice

Le déterminant de la matrice A a bc d

=

est le nombre réel noté det( )A défini

par det .( ) =A ad bc− On note :

det( ) = =A a bc d

ad bc−− .

Définition 8

La matrice A est inversible si, et seulement si, det( ) 0A ≠ .

Théorème 1

La matrice A est inversible si, et seulement si, il existe une matrice M telle que AM MA I= = .

On cherche une matrice Mx xy y

=′′

telle que AM =1 0

0 1

. On calcule AM.

AMa bc d

x xy y

ax by ax bycx dy

= =

′′

+ ′ + ′+ ccx dy′ + ′

.

La condition AM I= équivaut aux deux systèmes linéaires suivants d’inconnues respectives ( ; )x y et ( ; )′ ′x y .

( )= 1

= 0( )

= 01

1

22

3Sax by Lcx dy L

et Sax by Lc

++

′ + ′′′ + ′

x dy L= 1 4

On suppose ( ; ) (0 ; 0)a b ≠ et ( ; ) (0 ; 0)c d ≠

(si l’un des deux couples étaient (0 ; 0), soit L1, soit L4 serait impossible et A ne pourrait pas être inversible).

Le vecteur u b a( ; )− est un vecteur directeur des droites d’équation aX+bY = 1

et aX+bY = 0.

Démonstration

Démonstration



Le vecteur v d c( ; )− est un vecteur directeur des droites d’équation cX+dY = 1

et cX+dY = 0.

Chacun des systèmes (S1) et (S2) caractérise l’intersection de deux droites de

vecteurs directeurs respectifs u

et v

Chacun des systèmes ( )1S et ( )2S possède donc une unique solution si, et seu-lement si, les vecteurs u

et v

ne sont pas colinéaires.

La condition de colinéarité des vecteurs u

et v

est ad bc− = 0, c’est-à-dire det( ) = 0A .

Montrons l’implication si det( ) 0A ≠ alors A est inversible.

Supposons det ,( ) 0A ≠ alors les systèmes ( )1S et ( )2S possèdent chacun une unique solution que l’on obtient en combinant les équations. Par exemple, d L b L× − ×1 2 donne det .( ) =A x d

De même, on obtient det ,( ) =A y c− det( ) =A x b′ − et det( ) =A y a′ d’où :

MA

d bc a

=1( )

.det

−−

On vérifie bien que MA AM I= = donc A est inversible et A M−1 = .

Montrons l’implication réciproque : si A est inversible alors det( ) 0A ≠ par contra-position, c’est-à-dire montrons que si det( ) = 0A alors A n’est pas inversible.

Si det( ) = 0A alors les vecteurs u b a( ; )− et v d c

( ; )− sont colinéaires.

Donc, les droites d’équations cartésiennes aX + bY = 1 et cX + dY = 0 sont paral-lèles ; alors, comme ces droites ne sont pas confondues (O appartient à la 2e mais pas à la 1re), le système ( )1S n’a pas de solution donc A n’est pas inversible.

Finalement, on obtient le théorème et la propriété ci-dessous.

Une matrice A est inversible si, et seulement si, ses vecteurs colonnes ac

et bd

ne sont pas colinéaires.

Si A a bc d

=

et det( ) = 0A ad bc− ≠ alors A est inversible et

AA

d bc a

− −−

1 =

1( )det

.

Propriété 8

Soit A =3 3

1 2

−

. Montrer que A est inversible et déterminer son inverse A−1.

On a det ( ) ;( ) = 3 2 1 3 9A × − − =x le déterminant de A est non nul, donc A est

inversible et A−−

1 =19

2 31 3

Remarque

Exemple 9

Solution



6. Suites de matrices

Les résultats de ce paragraphe nous serons utiles dans la suite du cours. Dans une copie de devoir ou d’examen, ces propriétés ne pourront être utilisées sans être redémontré(s).

a) Un 1er résultat

Le théorème suivant généralise un résultat concernant les suites géométriques.

Soient S une matrice carrée non nulle et X0 un vecteur ligne.

On considère la suite ( )Xn définie par X0 et pour n ≥ 1, X X Sn n= −1 .

Pour tout n de , X X Snn= 0 .

Propriété 9

Démontrons ce théorème par récurrence. Notons (n) la proposition « X X Snn= 0 ».

Initialisation

On a X X I X S0 0 00= = donc la proposition est vraie au rang n = 0.

Hérédité

Soit k un entier naturel. Supposons (k) vraie. Alors : X X Sk

k= 0 . On en déduit :

X X S X S Sk kk

+ = = ( )⋅ =1 0 X Sk0

1+ .

Ainsi (k+1) est vraie et la suite de propositions est héréditaire.

Conclusion

Ainsi, par récurrence, pour tout n de , X X Snn= 0 .

b) Convergence d’une suite de matrices

Soient Mn( ) une suite de matrices et M une matrice. On suppose que toutes les matrices de la suite et M ont les mêmes dimensions. On dit que la suite Mn( )converge vers M et on note lim

nnM M

→+∞=

si pour chaque ligne i et chaque

colonne j, la suite des coefficients de Mn( ) correspondants converge vers le coeffi-cient de M correspondant.

Définition 9

Démonstration



On a : lim

,n n

n→+∞

−

×

=

3 11

2 0 5 2

3 1

0 2 car

lim lim

lim ,

n n

n

n

n→+∞ →+∞

→+∞

= −

=

×(3 3 1

11

2 0 5 )) = =

→+∞0 2 2lim

.

n

Le résultat suivant nous sera utile dans la suite du cours.

Soient S une matrice carrée et X0 un vecteur ligne.


Si la suite ( )Xn converge vers un vecteur ligne X, alors X vérifie : X = XS.

Théorème 2

Démontrons ce théorème en dimension 3, mais la démonstration se généralise sans difficultés à un ordre quelconque.

On note : Sa a ab b bc c c

=′ ′′′ ′′′ ′′

et X x y zn n n n= ( ).

Alors la relation X X Sn n= −1 se traduit par le système

x ax by cz

y a x b y c z

z

n n n n

n n n n

n

= + += ′ + ′ + ′= ′

− − −

− − −

1 1 1

1 1 1

′′ + ′′ + ′′

− − −a x b y c zn n n1 1 1

.

La convergence de la suite Xn( ) vers un vecteur-ligne X = ( )α β γ , se tra-duit (règles opératoires sur les limites et unicité de la limite) par le système

α α β γβ α β γγ α β γ

= + += ′ + ′ + ′= ′′ + ′′ + ′′

a b c

a b c

a b c

, c’est-à-dire par l’égalité X XS= .

Exemple

Démonstration



7. Utilisation de la calculatrice

La TI-82 Stats.fr possède 10 variables de type matrice : [A] [B]……[I] [J].

La Casio Graph 35+ possède 26 variables de type matrice : A, B, ……, Z.

TI-82 Stats.fr Casio Graph 35+

On choisit de créer la matrice carrée A =

2 9 4

7 5 3

6 1 8

.

matrice On peut aussi faire

au lieu de

MENU (RUN) EXE F3 (MAT)

1 EXE

3 entrer 3 entrer

(indique la dimension de [A] )3 EXE 3 EXE EXE

2 entrer 9 entrer 4 entrer



2 EXE 9 EXE … 1

EXE 8 EXE

2nde quitter matrice EXIT EXIT

1 entrer

(affiche la matrice [A])

MENU (RUN) EXE

OPTN F2 (MAT) F1

(Mat) ALPHA A EXE

On choisit de créer la matrice carrée

B =

2 1 1

1 1 2

1 3 4

matrice

2

EXIT EXIT F3

( MAT) ∇



3 entrer 3 entrerEXE 3 EXE 3 EXE

EXE




2 EXE 1 EXE … 3

EXE 4 EXE

Addition de deux matrices On additionne [A] et [B]

2nde quitter matrice 1 +

matrice 2 entrer

EXIT EXIT MENU

(RUN) EXE OPTN F2

(MAT) F1 (Mat) ALPHA

A + F1 (Mat)

ALPHA B EXE

Multiplication par un réel On multiplie [A] par 3

3 matrice 1 entrer

(le n’est pas obligatoire)

3 F1 (Mat)

ALPHA A EXE

Matrices particulières

Matrice identité d’ordre 3

matrice 5 3

dim

) entrer

(en changeant le 3 en 2 on a I2 )

MENU (RUN) EXE

OPTN F2 (MAT) F6

( ) F1 (Iden) 3

dim

→ F6

( ) F1 (Mat) ALPHA I EXE

Noter les différences entre MAT ; MAT et Mat ; le 1er est obtenu à partir de F3, le 2nd à partir de F2, le 3e à partir de F1.



TI-82 Stats.fr Casio Graph 35+

Multiplication de deux matrices On multiplie [A] par [B]

matrice 1 matrice 2 entrer

MENU (RUN) EXE OPTN F2 (MAT) F1 (Mat)

ALPHA A F1

(Mat) ALPHA B EXE

On multiplie [B] par [A]

matrice 2 matrice 1 entrer

F1 (Mat) ALPHA B

F1 (Mat)

ALPHA A EXE

Élever une matrice à une puissance n On calcule [ ]A 3

matrice 1 ^ 3 entrer (pour n = 2 on peut faire

matrice 1 x 2 entrer )

F1 (Mat) ALPHA A ^

3 EXE

Inverse d’une matrice Inverse de [B]

matrice 2 x −1 entrer

(la touche permet de faire défiler

l’écran)

F1 (Mat) ALPHA B

SHIFT x −1 EXE

Puis, éventuellement, F D↔

pour le mode décimal.

Inverse de C =

2 6

3 9

matrice 3 x −1 entrer

(C n’est pas inversible)

F1 (Mat) ALPHA C

SHIFT x −1 EXE



On peut aussi utiliser le logiciel en ligne Xcas (voir exemple ci-dessous).

Exercices d’apprentissage

Produits

Lorsque cela est possible, calculer les produits A B⋅ et B A⋅ .

a) A =

2 4 1

1 2 3−

et B =

1 7

5 3

6 2

−

−

;

b) A = 3 4 1−( ) et B =

1

2

4

−

.

Nombre de chemins de longueurs données

Reprenons le réseau routier de l’introduction ; la matrice de transition de ce graphe est :

A =

0 0 1 1

1 0 1 0

0 1 0 1

0 1 0 0

.

a) Calculer A3 et A4.

b) Existe-t-il un chemin de longueur 3 reliant le sommet 4 au sommet 1 ?

c) Existe-t-il un chemin de longueur 4 reliant le sommet 4 au sommet 1 ?

d) Déterminer le nombre de chemins de longueur 3 et de longueur 4 du réseau routier.

D

Exercice 1

Exercice 2



Produit par une matrice diagonale

On considère la matrice diagonale D =

1 0 0

0 2 0

0 0 5

−

.

a) Calculer le produit D A⋅ dans les cas suivants :

A A=

1 2 4

2 1 3

7 2 5

=

1 1 1

1 1 1

1 1 1

−−

puis .

b) Que remarquez-vous ?

Combinaisons de lignes

On considère la matrice A =

1 2 3

1 4 2

3 4 5

−− −

−

. On appelle L1 sa première ligne,

L2 sa deuxième ligne et L3 sa troisième ligne.

a) Calculer le produit E A× avec E =

1 0 0

1 1 0

0 0 1

.

Que pouvez-vous dire des première et troisième lignes de E A⋅ ?

La deuxième ligne de E A⋅ est la somme de la première ligne de A et de sa deuxième ligne : on écrit L L L2 1 2← + .

b) Calculer le produit F A⋅ avec F =

1 0 0

0 1 0

3 0 1−

.

Que pouvez-vous dire des première et deuxième lignes de F A⋅ ?

On écrit L L1 1← et L L2 2← .

La troisième ligne de F A⋅ est la somme de la première ligne de A multipliée par −3 et de sa troisième ligne : on écrit L L L3 1 33← − + .

c) Donner une matrice G telle que la première ligne et la troisième ligne de G Ai soient celles de A, et telle que la deuxième ligne de G A⋅ soit 3 2 3L L+ .

d) Effectuer les produits F E A⋅ ⋅ et E F A⋅ ⋅ .

Que remarquez-vous ? Quelles sont les combinaisons effectuées sur les lignes de A ?

e) On considère la matrice B =

3 1 5

1 5 4

2 4 1

−− −

−

.

Exercice 3

Exercice 4



On veut effectuer les combinaisons suivantes sur les lignes de B :

L L1 1← , L L L2 1 23← + et L L L3 1 32 3← − .

Par quelle matrice faut-il multiplier B ?

Puissance de matrices diagonales

a) On considère la matrice diagonale A =

1 0 0

0 2 0

0 0 3

.

Calculer A A2 3et .

Quelle est l’expression de An ?

b) On considère la matrice diagonale Aa

bc

a b c=

0 0

0 0

0 0

∈où et, .R

Montrer par récurrence sur n entier naturel que A

a

b

c

n

n

n

n

=

0 0

0 0

0 0

.

Puissance de matrices diagonalisables

On considère les matrices :

A P=

3 1 2

1 5 2

1 1 4

, =

1 1 1

1 1 1

1 1 1

,−

−

−

etQ D=

12

1 0 1

1 1 0

0 1 1

=

2 0 0

0 4 0

0 0 6

−−

.

a) Vérifier que Q P= 1− et que A PDQ= .

On dit que l’on a diagonalisé la matrice A et que A est diagonalisable.

b) Montrer que pour tout n entier naturel, A PD Qn n= .

c) En déduire l’expression des neufs coefficients de An en fonction de n.

Puissance de matrices nilpotentes

a) On considère la matrice N =

0 1 2

0 0 1

0 0 0

−

.

1) Calculer N2 et N 3.

2) Soit n un entier naturel, que pouvez-vous dire de Nn ?

b) Soient M =− − −

1 0 1

1 2 3

1 2 3

et N I M= − .

1) Calculer M 3. Simplifier alors I M I M M−( )⋅ + +( )2 .

2) En déduire que N est inversible et déterminer N −1.

Exercice 5

Exercice 6

Exercice 7



Puissance de matrices J

a) On considère la matrice J =

1 1 1

1 1 1

1 1 1

.

Calculer J 2 puis en déduire J 3.

Soit n un entier naturel. Quelle est l’expression de Jn en fonction de n et de J ?

b) On considère la matrice Aa a aa a aa a a

=

.

Soit n un entier naturel. Déterminer An en fonction de n et de J.

c) On considère la matrice carrée J4 d’ordre 4 dont tous les coefficients sont égaux à 1. Soit n un entier naturel. Quelle sera l’expression de Jn

4 ?

Généraliser sans démonstration à une matrice carrée Jp d’ordre p dont tous les coefficients sont égaux à 1.

Exercice 8




Écrire un système linéaire sous la forme matricielle AX B= . Lorsque la matrice est inversible, la solution est alors X A B= 1− .

Nous verrons que lorsque la matrice A est d’ordre 2 et inversible, on obtient les formules de Cramer (non exigibles).

Cependant, en général, l’inverse d’une matrice n’est pas simple à déterminer ou, dans certaines situations, la matrice A peut ne pas être inversible (en particulier, si elle n’est pas carrée).

Nous présentons la méthode de Gauss (non exigible) sur la résolution d’un sys-tème linéaire à trois inconnues et trois équations. Ses avantages sont de ne pas calculer l’inverse de la matrice A et de s’appliquer à des systèmes où les nombres d’inconnues et d’équations peuvent être différents (la matrice A n’est pas carrée).

On utilise cette méthode pour trouver des vecteurs stables. Nous serons ame-nés dans les chapitres suivants à étudier la convergence de suites de vecteurs lignes Xn( ) définies par récurrence par X X Sn n+ =1 avec X0 donné et S une matrice stochastique donnée. Lorsque cette suite converge, ce ne peut être que vers un vecteur stable (d’après le théorème 2 du chapitre 2), c’est-à-dire vérifiant X XS= d’où leur importance.

Pour débuter

1. ExempleOn considère le système linéaire suivant :

( )5 2 = 1

7 3 = 1S

x yx y

++ −

.

On pose A =5 2

7 3

, Xxy

=

et B =1

1−

.

On vérifie que le système ( )S est équivalent à AX B= .

On a det( ) = 5 3 2 7 = 1 0A × − × ≠ , donc la matrice A est inversible et X A B= 1−

d’où :

X =3 2

7 5

1

1=

5

12

−−

−

−

.

A

B

3Calcul matriciel et résolutions de systèmes linéaires



2. Activité : méthode de Gauss

On utilise à différentes reprises dans l’activité suivante la propriété suivante.

Soient A une matrice carrée et M et N deux matrices telles que les produits A.M et A .N aient un sens.Si A est inversible alors A .M = A .N M = NCette équivalence n’est plus vraie si A n’est pas inversible.

Méthode de Gauss Écriture matricielle

( )

2 2 = 3 13 = 2 22 = 7 3

S

x y z L

x y z L

x y z L

+ ++ − −− +

( )S équivaut à AX B= avec

A Xxyz

B=1 2 23 1 12 1 1

, = =32

7−

−

−

et

Triangularisation Factorisation dite « LU » de A

On élimine l’inconnue x des lignes L2 et L3 par combi-naison linéaire avec L1.

( )

2 2 = 3 15 7 = 11 2 3 1 25 3 = 1 3 2 1

S

x y z L

y z L L L

y z L L L

+ ++ ← −+ − ← − 33

On multiplie A et B par une matrice triangulaire inférieure (c’est-à-dire les coefficients sont nuls au dessus de la diagonale) E1.

( ) 1 = 1 1 =1 0 03 1 02 0 1

S E AX E B avec E⇔ −−

Question 1

Vérifier que E1 est inversible et que E E11

1=− . Expliquer pourquoi puis vérifier que :

E A E B1 =1 2 20 5 70 5 3

1 =311

1.

−

et

On remarque que calculer E1. A et E1. B revient à effectuer les mêmes opérations élémentaires sur les lignes.

On élimine l’inconnue y de la ligne L3 par combinai-son linéaire avec L2.

( )

2 2 = 3 15 7 = 11 2

4 = 12 3 2 3

S

x y z L

y z L

z L L L

+ ++

← −

On multiplie E A1 et E B1 par une matrice triangu-laire inférieure E2 .

( )

S E E A X E E B avec E⇔ = =2 1 2 1 1

1 0 0

0 1 0

0

.

1 1−

Remarque

Activité 1



Méthode de Gauss Écriture matricielle

Question 2

Vérifier que E E21

2=− .

On pose U E E A= 2 1 , vérifier que :

U E E B=1 2 20 5 70 5 3

2 1 =31112

.

et

La matrice U est triangulaire supérieure (upper).

On pose L E E E E= =11

21

1 2− − .

Le système est triangulaire supérieur.

Question 3

Vérifier que A LU= puis que L est triangulaire inférieure (lower).

Vérifier que :

( ) = 1S UX L B⇔ −

Remontée Résolution

Si U est inversible (c’est-à-dire ne comporte pas de zéro sur sa diagonale), alors on peut écrire X U L B= − −1 1 , mais, en pratique, on ne calcule pas U −1, on effectue la remontée.

Cours

1. Systèmes 2 2

On considère le système ( )=

=S

ax bycx dy

++

αβ

,

son écriture matricielle est AX B= avec

Aa bc d

Xxy

B= , = = .

etαβ

Si det( ) 0A ≠ alors A est inversible et X A B= 1− .

On sait que A−1 =A

d bc a

−−

1( )det

d’où

xA

d b yA

a c=1( )

( ) =1( )

( ).det det

α β β α− −et

( )

= 3

=15

(11 7 )= 2

= 3 2 2 =1

S

z

y z

x y z

− −

− −

C



On remarque que :

d bbd

α βαβ

−

= .det

On remplace la première colonne de A par le vecteur colonne B.

a cac

β ααβ

−

= .det

On remplace la deuxième colonne de A par le vecteur colonne B.

Finalement, on obtient les formules de Cramer.

Formules de Cramer (non exigible)

On considère le système ( )S AX B= avec A a bc d

=

, X

xy

=

et B =αβ

.

Si det( ) 0A ≠ alors xA

bd

=1( )det

detαβ

et y

Aac

=1( )det

detαβ

.

Théorème 3

A B−1 après avoir remarqué que det .A ≠ 0

la façon suivante :

x est égal à A

1det( )

multiplié par le déterminant de la matrice obtenue à

partir de A en remplaçant la 1re colonne par B ;

y est égal à A

1det( )

multiplié par le déterminant de la matrice obtenue à

partir de A en remplaçant la 2e colonne par B.

On considère le système ( )4 7 = 3

2 3 = 51Sx yx y

− +−

.

Montrer que ce système possède une unique solution puis la déterminer.

On considère les systèmes

( )4 3 = 7

8 6 = 52Sx yx y

− +−

et ( )4 3 = 7

8 6 = 143Sx yx y

− +− −

.

Déterminer le nombre de solutions de ces systèmes puis les solutions si elles existent.

Remarques

Exemple 10



On calcule le déterminant de la matrice A =4 7

2 3

−−

du système :

det .( ) = 4 ( 3) 7 2 = 2A − × − − × −

Ce déterminant est non nul donc le système ( )1S possède une unique solution

x y=12

3 7

5 3= 22 =

12

4−

−

−−

det et det

3

2 5= 13.

L’ensemble des solutions de S1( ) est donc S = (22 ; 13) .

On calcule le déterminant de la matrice A =4 3

8 6

−−

des deux systèmes :

det .( ) = 4 ( 6) 8 3 = 0A − × − − ×

Le déterminant est nul : les vecteurs lignes de A sont colinéaires ; il reste à déter-miner si les systèmes possèdent une infinité de solutions ou aucune.

On remarque que la deuxième ligne de la matrice A s’obtient en multipliant la première par –2 mais 5 2 7≠ − × donc le système S2 ne possède pas de solution.

Par contre, S3 possède une inifinité de solutions : tous les couples x x;43

73

+

où x décrit R, c’est-à-dire tous les points de la droite d’équation y x=43

73

+ .

2. Méthode de Gauss (non exigible)

Les résultats de ce paragraphe sont non exigibles mais leur étude peut être utile pour les manipulations de système linéaire d’équation.

Système AX = B

On considère le système ( )S AX B= .

Si la matrice A est inversible, alors le système possède une unique solution

X A B= −1 .

Théorème 4

Aucune notion concernant les déterminants de matrices carrées d’ordre N où N ≥ 3 n’est à connaître, mais pour savoir si une matrice A est inversible, on pourra utiliser la calculatrice ou un logiciel pour déterminer det (A). En effet, la notion de déterminant se généralise et une matrice carrée est inversible si, et seulement si, son déterminant est non nul.

Le problème est que le calcul de l’inverse d’une grande matrice est généralement difficile et coûteux. On préfère utiliser la méthode de Gauss.

Solution

Remarque



Factorisation LU

Tout système de la forme AX B= est équivalent à un système UX L B= −1 avec U matrice triangulaire supérieure et L matrice triangulaire inférieure inversible.

Théorème 5

Ce théorème est admis et n’est pas exigible. La méthode de Gauss consiste à écrire le système AX B= sous forme triangulaire UX L B= −1 puis à déterminer X par remontée. On illustre la méthode sur des exemples.

1) On considère le système ( )

2 = 3

2 2 = 2

= 1

1

2

3

Sx y z Lx y z Lx y z L

− + −− + −

− −

, soit AX B= avec

A Xxyz

B=

1 2 1

2 2 1

1 1 1

, =

− −− −

− −

et ==

3

2

1

.

Avec la méthode de Gauss, on effectue les mêmes transformations sur les lignes de A et sur celles de B, d’où l’idée de regrouper A et B dans une même matrice A1 :

A1 =

1 2 1 3

2 2 1 2

1 1 1 1

− −− −

− −

.

On triangularise cette matrice.

On effectue les opérations suivantes sur les lignes L L L2 1 22← − + et L L L3 1 3← + soit :

A2 =

1 0 0

2 1 0

1 0 1

1 2 1 3

2 2 1 2

1 1 1 1

−

− −− −

− −

− −− −

−

=

1 2 1 3

0 2 1 4

0 1 2 4

.

Puis on effectue L L L3 2 32← + soit :

A3 =

1 0 0

0 1 0

0 1 2

1 2 1 3

0 2 1 4

0 1 2 4

− −− −

−

− −− −

−

=

1 2 1 3

0 2 1 4

0 0 3 4

.

La matrice A3 est triangulaire, le système associé est :

− + −− + −

−

x y zy z

z

2 = 3

2 = 4

3 = 4

.



On effectue la remontée :

z yz

x y z X=43

, = 22

= 223

=43

= 2 3 = 1 ù =

1

4 / 3− + − − − ′et d o

−−

4 / 3

.

On vérifie les résultats : AX donne bien B.

2) On considère le système ( )

2 = 1

3 4 = 2

8 3 = 3

1

2

3


− + −− + −+ +

, soit AX B=

avec etA Xxyz

B=1 2 1

3 1 41 8 3

, = =− −

−

112

3−

.

On regroupe A et B dans une même matrice A1 :

A1 =

1 2 1 1

3 1 4 2

1 8 3 3

− −− −

.

On triangularise cette matrice.

On effectue les opérations suivantes sur les lignes L L L2 1 23← + et L L L3 1 3← + soit :

A2 =

1 0 0

3 1 0

1 0 1

1 2 1 1

3 1 4 2

1 8 3 3

− −− −

− −

=

1 2 1 1

0 5 1 1

0 10 2 4

.

Puis on effectue L L L3 2 32← − + soit :

A3 =

1 0 0

0 1 0

0 2 1

1 2 1 1

0 5 1 1

0 10 2 4−

− −

− −

=

1 2 1 1

0 5 1 1

0 0 0 2

.

La matrice A3 est triangulaire, le système associé est

− + −+

x y zy z

2 = 1

5 = 1

0 = 2.

On arrive à une impossibilité : ce système ne possède pas de solution.

3) Reprenons le système précédent en remplaçant le dernier coefficient de B par 1.

( )

2 = 1

3 4 = 2

8 3 = 1

1

2

3


− + −− + −+ +

.



On effectue les mêmes combinaisons, on arrive alors à :

A3 =

1 2 1 1

0 5 1 1

0 0 0 0

− −

−associée au système

xx y zy z

+ −+

2 = 1

5 = 1.

Après avoir vérifié que ces couples conviennent, on peut conclure que ce système possède une infinité de solutions : les triplets 7 2 ; ; 1 5y y y− −( ) où y décrit R.

Les élèves ayant étudié la séquence Géométrie dans l’espace (séquence 10) de l’enseignement de tronc commun remarquerons qu’il s’agit des points de l’es-pace situés sur la droite d’intersection des plans d’équations L1 et L2 (on a L L L3 2 1= 2 5+ donc L3 est vraie dès que L1 et L2 le sont).

3. Applications à la recherche de vecteurs stables

On s’intéresse à l’évolution au cours du temps d’un titre en bourse. Après obser-vation sur une longue période, on constate que : le jour suivant une hausse, dans 20 % des cas le cours continue d’augmenter,

dans 20 % des cas, il diminue et dans 60 % des cas, il stagne ; le jour suivant une baisse, dans 30 % des cas, le cours augmente, dans 50 %

des cas, il continue de regresser et dans 20 % des cas, il stagne ; le jour suivant une stagnation, dans 10 % des cas, le cours augmente, dans

60 % des cas il régresse et dans 30 % des cas, il reste stable.

On peut représenter cette situation par un tableau à 3 lignes et 3 colonnes

Augmentation Régression Stagnation

Augmentation 20 % 20 % 60 %

Régression 30 % 50 % 20 %

Stagnation 10 % 60 % 30 %

c’est-à-dire par la matrice stochastique S =1

10

2 2 6

3 5 2

1 6 3

.

On suppose que le jour 0, le cours du titre augmente : on pose X0 1 0 0= ( ) .

Le jour 1, le cours du titre suit la distribution suivante :

X X S1 0 0 2 0 2 0 6= = ( ), , , .

Le jour 2, on a X X S2 1 0 16 0 5 0 34= = ( ), , , .

De manière générale, le jour n, on a X X Sn n= −1 . On a défini par récurrence une suite de vecteurs lignes.

Exemple 11



Calculer les termes suivants jusqu’à n = 10. Qu’observe-t-on ?

On obtient :

X 0,216 0,486 0,2983 ( )= ;

X 0,2188 0,465 0,31624 ( )= ;

X 0,21488 0,46598 0,319145 ( )= ;

X 0,214684 0,46745 0,3178666 ( )= ;

X 0,2149584 0,4673814 0,31766027 ( )= ;

X 0,21497212 0,4672785 0,317749388 ( )= ;

X 0,214952912 0,467283302 0,3177637869 ( )= ;

X 0,2149519516 0,467290505 0,3177575434 .10 ( )= Il semble que la suite Xn( ) converge vers la distribution suivante :

(21,5 % 46,7 % 31,8 %).

Si la suite Xn( ) définie par récurrence par X X Sn n= −1 converge, ce ne peut être que vers un vecteur X * stable, c’est-à-dire tel que X S X* *= . Cherchons le ou les éventuels vecteurs stables.

On cherche X x y z* = ( ) tel que X S X* *= et tel que x y z+ + = 1. On dit

alors que X * est un vecteur stable à gauche pour S et que X * est stochastique. On obtient le système linéaire suivant :

( )

= 1

210

310

110

=

210

510

610

=

1

2

S

x y z L

x y z x L

x y z y L

+ +

+ +

+ + 33

46

102

103

10=x y z z L+ +

soit AX B= avec

A =

1 1 1

810

310

110

210

510

610

610

210

710

−

−

−

, = =

1

0

0

0

etXxyz

B

.

Question

Solution



On regroupe A et le second membre nul dans une même matrice A1 :

On multiplie les lignes L2 , L3 et L4 par 10 d’où :

A A2 1=

1 0 0 0

0 10 0 0

0 0 10 0

0 0 0 10

=

1 1 1 1

⋅−88 3 1 0

2 5 6 0

6 2 7 0

−−

.

On triangularise cette matrice.On effectue les opérations suivantes sur les lignes

L L L2 1 28← + , L L L3 1 32← − + et L L L4 1 46← − + soit :

A3 =

1 0 0 0

8 1 0 0

2 0 1 0

6 0 0 1

1 1 1 1

8 3 1 0

2−−

−−−

−

− −− −

5 6 0

6 2 7 0

=

1 1 1 1

0 11 9 8

0 7 4 2

0 4 133 6−

.

On effectue les opérations suivantes sur les lignes

L L L3 2 37 11← + et L L L4 2 44 11← − − soit :

A4 =

1 0 0 0

0 1 0 0

0 7 11 0

0 4 0 11

1 1 1 1

0 11 9

− −

88

0 7 4 2

0 4 13 6

=

1 1 1 1

0 11 9 8

0 0 107− −− − −

334

0 0 107 34

associée au système :x y z

y zz

+ ++

= 1

11 9 = 8

107 = 34

.

On effectue la remontée :

z yz

x y z=34

107, =

811

911

=50

107= 1 =

23107

et− − − .

d’où le vecteur stable stochastique cherché est :

X* =23

10750

10734

107

.

A1 =

1 1 1 1

810

310

110

0

210

510

610

0

610

210

710

0

−

−

−

.



La méthode de Gauss s’applique aussi lorsque le système ne comporte pas le même nombre d’équations et d’inconnues.

Dans notre système ( )S initial, on aurait pu remarquer que la ligne L4 était inutile car elle est l’opposé de la somme L L2 3+ .

Le vecteur stable obtenu correspond à la distribution limite observée :

X* (21,5 % 46,7 % 31,8 %).

Le plus fréquemment, le cours de ce titre baisse ou stagne.

Exercices d’apprentissage

Écrire sous forme matricielle : AX B= les systémes suivants et les résoudre.

( )3 4 = 2

5 8 = 3

( )0,8 = 0,6

76

1

2

Sx yx y

Sx yx

− +− + −

++

;

995 = 57y

.

Résolution de systèmes 3 3

Écrire sous forme matricielle AX B= les systèmes suivants et les résoudre.

( )

2 3 = 20

2 3 = 13

5 2 = 91

1

2

3

Sx y z L

x y z Lx y z L

+ −− + +

− − −

;

+ ++ ++ − −

( )

= 1

5 6 = 4

20 75 = 182

1

2Sx y z Lx y z Lx y z L33

.

Recherche d’un vecteur stable

On considère la matrice S =

0,58 0,3 0,12

0,3 0,1 0,6

0,1 0,1 0,8

.

On cherche X x y z* = ( ) tel que X S X* *= et tel que x y z+ + = 1.

a) Montrer que x, y et z doivent vérifier le système suivant :

( )

= 1

4,2 3 = 0

3 9 = 0

1,2 6

1

2

3S

x y z Lx y z Lx y z Lx

+ +− + +

− ++ yy z L−

2 = 0 4

.

b) Résoudre ce système.

Remarque

D

Exercice 9

Exercice 10

Exercice 11




À partir d’un exemple, on introduit la modélisation à l’aide d’un graphe proba-biliste d’un système à deux états A et B, qui évolue aléatoirement au cours du temps. On ne considère que des systèmes dont l’état futur ne dépend que de l’état présent et pas de son histoire.

On associe alors au graphe une matrice stochastique S dite « de transition », qui résume les passages d’un état à l’autre.

À l’instant n, on appelle état probabiliste du système le vecteur ligne P p qn n n= ( ) où pn est la probabilité que le système soit dans l’état A et q pn n= 1− est la probabilité que le système soit dans l’état B.

On montre à l’aide de la formule des probabilités totales que l’état probabiliste Pn à l’étape n du système est défini par récurrence par : P P Sn n+1 = d’où la relation P P Sn

n= 0 où P0 est l’état initial du système (d’après la propriété 9). L’étude de l’évolution du système se ramène donc au calcul des puissances de la matrice stochastique S.

Ensuite, on s’intéresse à la convergence de la suite des états probabilistes ( )Pn .

Enfin, on utilise les outils introduits pour déterminer l’évolution de différents sys-tèmes à deux états.

Pour débuter : Évolution des succès d’un joueur, modélisation

1. Présentation

Au départ, notre joueur a une probabilité égale à 0,3 de gagner sa partie de matrixis, ensuite : s’il gagne une partie (G), il a une probabilité de 0,7 de gagner la suivante ; s’il perd une partie (P), il a une probabilité de 0,5 de perdre la suivante.

A

B

4Matrices d’ordre 2, systèmes dynamiques à deux états



On peut représenter les trois premières parties par un arbre de probabilité :

G0,7

0,7

0,7

0,3

0,30,3

GP

GG

0,5

0,5

PP

G0,7

0,50,3

0,5

GP

GG

0,5

0,5

PP

Figure 4. Arbre de probabilité

Lorsque le nombre de parties devient important, cette représentation n’est plus très appropriée. On utilise alors un graphe probabiliste.

2. Modélisation par un graphe probabiliste

Une partie ne peut être que dans deux états : gagnée (G) ou perdue (P).

Si une partie est dans l’état gagné, la probabilité que la prochaine passe à l’état perdu est de 0,3 et celle de rester dans l’état gagné de 0,7.

Si une partie est dans l’état perdu, la probabilité que la prochaine passe à l’état gagnant est de 0,5 et celle de rester dans l’état perdant de 0,5 aussi.

On représente l’évolution des parties par le graphe probabiliste suivant :

0,3

0,5

0,7 0,5G P

Figure 5. Un exemple de graphe probabiliste



On associe à ce graphe une matrice S sij= ( ) de dimension 2 2× telle que le nombre sij situé sur la ligne i et la colonne j soit la probabilité de passer de l’état i à l’état j. L’état 1 correspond à l’état gagné (G) et l’état 2 à celui perdu (P).

Cette matrice s’appelle la matrice de transition du graphe. Cette matrice est une matrice stochastique, car tous ses coefficients sont des réels compris entre 0 et 1, et la somme des coefficients de chaque ligne est égale à 1. On a :

S

G P

GP

=

0 7 0 3

0 5 0 5

, ,

, ,

On peut considèrer la suite de variables aléatoires ( )Xn qui représente l’état de la partie n : Xn = 1 si la partie n est gagnée (G) et Xn = 2 si elle est perdue (P).

La probabilité de passer de l’état i à l’état j à l’étape n est la même pour chaque étape ; autrement dit, pour tout entier n ≥ 1 et pour tous i, j

[ ] [ ]= + =P X j P X j s( = ) = ( = ) = .X i n X i i j 1 1 ,n 0

La suite des variables aléatoires ( )Xn forme ce que l’on appelle une chaîne de Markov à deux états.

Andreï Andreïevitch Markov (1856-1922), mathématicien russe reconnu pour ses travaux en probabilités.

3. Modélisation de l’évolution par des matrices

Il s’agit de répondre aux problèmes suivants :

Problème 1 : Quelle est la probabilité pn de gagner la n-ième partie ?

Problème 2 : Comment se comporte la suite ( )pn ?

Nos problèmes consistent donc à définir la suite ( )pn en fonction de n et à étu-dier son comportement asymptotique (lorsque n tend vers l’infini).

On note Gn l’événement « gagner la n-ième partie » et Ln l’événement contraire « perdre la n-ième partie ».

On a p P Gn n= ( ) et donc 1 = ( )− p P Ln n . De plus, p1 = 0,3. Nos données conduisent à l’arbre des probabilités suivant.

Remarque

Point historique



G0,7

0,3

1 – pn

pnG

P

G0,5

0,5

PP

Figure 6. Arbre de probabilité du joueur (graphe de la figure 5)

La formule des probabilités totales donne :

P G P G P G P G P Ln Gn n n Ln n n( ) = ( ) ( ) ( ) ( )1 1 1+ + +× + ×

c’est-à-dire :

pour tout n p p pn n n≥ × + × −+1, = 0,7 0,5 (1 ) (1)1 .

De même, on obtient :

P L P L P G P L P Ln Gn n n Ln n n( ) = ( ) ( ) ( ) ( )1 1 1+ + +× + ×

soit :

pour tout n p p pn n n≥ − × + × −+1, 1 = 0,3 0,5 (1 ) (2)1 .

On note pour n ≥ 1, Pn le vecteur ligne p pn n1−( ). En particulier, P1 = 0,3 0,7( ).On dit que ces vecteurs lignes Pn sont stochastiques car leurs coefficients sont positifs et leur somme est égale à 1.

Le vecteur Pn donne l’état probabiliste de la n-ième partie.

Les relations (1) et (2) donnent P P Sn n+ ⋅1 = où S est la matrice stochastique définie précédemment et i est le produit matriciel.

On en déduit (propriété 9) que P P Snn= 1

1⋅ − où S S S Sn

n

−

−⋅ ⋅ ⋅1

1= ... .

fois

Notre problème 1 se ramène alors au calcul de puissances de matrices, ici au calcul de Sn avec n entier strictement positif.

Notre problème 2 se ramène à l’étude de la convergence de la suite de matrices lignes ( )Pn , définie par récurrence par P1 donné et P P Sn n+ ⋅1 = . Il s’agit :

d’une part, de trouver un « vecteur stable » (dans le langage matriciel, on parle de vecteur propre associé à la valeur propre 1) : c’est-à-dire le vecteur stochastique P* tel que P P S* *= : ceci revient à résoudre un système linéaire ;

d’autre part, de déterminer si la suite ( )Pn converge ou non ; si oui, on montrerait que cela ne peut être que vers P*d'après le théorème 2.



Dans la partie suivante, nous allons introduire les outils de calcul matriciel néces-saires pour résoudre ces deux problèmes. Nous reviendrons ensuite sur leur réso-lution.

Cours : Matrices stochastiques d’ordre 2

1. Définition, matrice stochastique

Matrice stochastique

Une matrice stochastique est une matrice dont les coefficients sont compris entre 0

et 1 et dont la somme des coefficients de chaque ligne est égale à 1.

Définition 10

Les matrices stochastiques de dimension 2 2× sont de la forme :

Sa a

b ba et b=

1

1[0 ; 1] [0 ; 1].

−−

∈ ∈avec

En effet, pour tout 1 , 2≤ ≤i j , sij ∈[0 ; 1] : les coefficients de S sont compris

entre 0 et 1 ; et S1

1=

1

1

: la somme des coefficients de chaque ligne est égale à 1.

2. Graphe probabiliste associé à une matrice stochastique

Toute matrice stochastique Sa a

b b=

1

1

−−

est une matrice de transition d’un

graphe probabiliste. Ce graphe définit l’évolution au cours du temps d’un sys-tème dynamique à deux états A et B, dont les probabilités de changement d’état sont indépendantes du temps.

1 – a

a

b

1 – bA B

Figure 7. Un graphe probabiliste à deux états

C



Il s’interprète de la manière suivante

Si à une étape de l’évolution, le système est dans l’état A, alors la probabilité de rester dans l’état A à l’étape suivante est 1− a et celle de passer à l’état B est a.

Si à une étape de l’évolution, le système est dans l’état B, alors la probabilité de rester dans l’état B à l’étape suivante est 1− b et celle de passer à l’état A est b.

4. Calcul des puissances de Sa) Un théorème utile (résultat non exigible)

Le théorème suivant est utile pour déterminer la puissance n-ième d’une matrice stochastique. Il est admis.

Ce résultat n’est pas une connaissance exigible du programme et lors des exer-cices « type-bac », le calcul de l’élévation à la puissance n d’une matrice stochas-tique 2 2× sera détaillé.

Soient a et b deux réels de ]0 ; 1[ et la matrice stochastique S a ab b

= 11

−−

.

Pour tout n ∈N*, S N Rn n= + λ où

λ = 1 ( ), =1

=1− +

+

+−

−

a b N

a bb ab a

Ra b

a ab b

et ..

Théorème 6

Si ( ; ) = (0 ; 0)a b alors S I= et pour tout n ,*N∈ S In = .

Si ( ; ) = (0 ; )a b b alors pour tout n ∈N*, Sb b

nn n=

1 0

1 1 1− −( ) −( )

.

Si ( ; ) = ( ; 0)a b a alors pour tout n ∈N*, S a ann n

= 1 1 1

0 1

−( ) − −( )

.

Si a b 1; ;( ) = ( )1 alors S =0 1

1 0

et λ = 1− .

Alors S I2 = . On en déduit pour tout k de ,N S S I Ik k k2 2= ( ) = = et

S S S I S Sk k2 1 2+ = ⋅ = ⋅ = .

On considère la matrice S = 2 / 5 3 / 51/ 5 4 / 5

.

Soit n un entier non nul. Calculer les coefficients de Sn .

Remarques

Exemple 12



La matrice S est une matrice stochastique car ses coefficients sont compris entre

0 et 1 et la somme des coefficients de chaque ligne est égale à 1 : 25

35

1+ = et 15

45

1+ = .

On peut appliquer le théorème avec a = 35

et b = 15

.

La matrice N est N =14

1 3

1 3

, la matrice R est R =14

3 3

1 1

−−

et λ =15

.

Pour tout n ∈N*, Sn

n n

n=

14

1 315

3 315

115

31

+

−

−

+

55

n.

b) Étude de l’évolution du système dynamique de matrice S

Revenons à notre système dynamique à deux états (Figure 7), de matrice de transition S.

1 – a

a

b

1 – bA B

On considère le vecteur ligne P p pn n n= 1−( ) où :

le nombre pn de [0 ; 1], est la probabilité de l’événement An « le système est dans l’état A à l’instant n » :

p P An n= ( ) et :

le nombre 1− pn est la probabilité de l’événement contraire Bn « le système est dans l’état B à l’instant n » :

1 = ( )− p P Bn n .

On a l’arbre des probabilités suivant :

A

1 – pn

1 – b

1 – a

pnA

B

AB

B

a

b

Figure 8. Arbre des probabilités (graphe de la figure 7)

Solution



La formule des probabilités totales donne :P A P A P A P A P Bn An n n Bn n n( ) = ( ) ( ) ( ) ( )1 1 1+ + +× + ×

P B P B P A P B P Bn An n n Bn n n( ) = ( ) ( ) ( ) ( )1 1 1+ + +× + ×

d’où les relations de récurrence sur p P An n= ( ) et 1 = ( )− p P Bn n :

p a p b p et p ap b pn n n n n n+ +− + − − + − −1 1= (1 ) (1 ) 1 = (1 )(1 )).

Elles se traduisent par l’égalité matricielle P P Sn n+1 = ; appelons (1) cette égalité.

On en déduit (propriété 9) que pour tout n ≥ 0, P P Snn= 0 .

On a donc montré le théorème suivant :

Soit un système dynamique à deux états A et B, de matrice de transition S.

Soit An l’événement « le système est dans l’état A à l’instant n » et Bn l’événement contraire « le système est dans l’état B à l’instant n ». On considère le vecteur ligne Pn = (pn 1 – pn) où pn = P (An ) et 1 – pn = P (Bn ).

Pour tout n ≥ 0, P P Snn= 0 .

Théorème 7

Or, d’après le théorème d’élévation à la puissance n des matrices stochastiques, S N Rn n= + λ donc P P N P Rn

n= 0 0+ λ .

Calculons P N0 d’abord et ensuite P R0 . On a :

P Na b

p p b ab a

a bp b p

0 0 0

0 0

=1

1

=1

(1

+−( )

++ − )) (1 ) =

1.0 0b p a p a

a bb a+ −( ) +

( )Quel que soit le vecteur ligne P0 , c’est-à-dire quel que soit l’état initial du sys-tème, P N0 ne dépend pas de P0 , on note : P P N*

0= .

Le vecteur stochastique Pa b

b a* =1+

( ) est stable par S : P S P* *= .

Propriété 10

On calcule P S* : P Sa b

b a a ab b

* =1 1

1+( ) −

−

.

Le premier coefficient de ce vecteur ligne est a b

b a bab

a b1

(1 )[ ]+

× − + =+

et le deuxième est a b

ba a ba

a b1

(1 )[ ]+

+ × − =+

. On vérifie bien que P S P* *= .

Démonstration



On peut démontrer que si a et b sont non nuls, P* est le seul vecteur stochastique stable, c’est-à-dire tel que P P S* = * .

Calculons P R0 . On a :

P Ra b

p p a ab b

a bp a p

0 0 0

0

=1

1

=1

(1

+−( ) −

−

+− − 00 0 0

0 0

) (1 )b ap p b

pb

a bp

ba b

− + −( )= −

+− +

+

.

La matrice ligne P R0 dépend de P0 . On obtient P P P Rnn= *

0+ λ et :

pb

a bb

a bP p

aa b

ba b

P= et 1 = .nn

nn

0 0+− λ

+−

−

++ λ

+−

On suppose que a b, ]0 ; 1[∈ donc λ = 1 ] 1 ; 1[− − ∈ −a b et lim ,n

n

→+∞λ = 0

donc :

lim lim .n

nn

npb

a bp

aa b→+∞ →+∞+

−+

= 1 =et

Chaque coefficient de Pn converge vers les coefficients de P* ; on écrit lim .

nnP P

→+∞= *

Finalement, on obtient le résultat suivant :

Soient a et b deux réels de ]0 ; 1[ et la matrice stochastique Sa a

b b=

1

1

−−

.

Soit P p pn n n= 1−( ) l’état à l’étape n du système en évolution de matrice de transition S. La suite de matrices lignes Pn( ) converge vers un état P* stationnaire indépendant de l’état initial P0 . On a :

limn nP P P

a b b a P P S→+∞

=+ ( )* * * *=1

= .avec et

Théorème 8

On a lim .n

nS N→+∞

= Pour n suffisamment grand, les lignes de Sn sont donc

quasiment identiques à celles de N, c’est-à-dire à P*.

Si ( ; ) = (0 ; 0)a b alors S I= , donc le système reste dans l’état initial.

Si ( ; ) = (0 ; )a b b avec b ≠ 0 (respectivement, ( ; ) = ( ; 0)a b a avec a ≠ 0),

alors l’état du système converge vers P* 1 0= ( ) (respectivement P* = 0 1( ) ) : quel que soit l’état initial, le système finit dans l’état A (respectivement B).

Remarques

Remarque

Remarques



Si a b 1; ;( ) = ( )1 alors S =0 1

1 0

et λ = 1− .

On a vu (remarque suivant le théorème de 6) que pour n pair : n = 2k, on a

S Ik2 = et pour n impair : n = 2k+1, on a S Sk2 1+ = .

Donc pour n pair, on a P P S Pkk

2 02

0= = et pour n impair, on a

P P S P Skk

2 1 02 1

0++= = .

On distingue alors deux cas :

a) Si le vecteur stochastique P p p0 1 2= ( ) est tel que p p1 212

= = alors

P S P0 0= . Le vecteur P0 est stable par S et la suite ( )Pn est constante égale à P0, donc converge vers cet état stable.

b) Sinon, P S p p P0 2 1 0= ( ) ≠ et donc la suite ( )Pn des états est alternée, elle ne converge pas.

Pour conclure

1. Évolutions des succès d’un joueur, résolution

Revenons sur notre problème du joueur.

Pour n ≥ 1, Pn est le vecteur ligne p pn n1−( ). La suite ( )Pn est définie par :

P P P S Snn

1 11= 0,3 0,7 = =

0,7 0,3

0,5 0,5( )

−et avec

.

Calcul de Sn

a) Vérifier que S N R= 0,2+ où N =18

5 3

5 3

et R =18

3 3

5 5

−−

.

b) Calculer N R N R R N2 2, , .et⋅ ⋅

c) Calculer S2 et S 3.

d) Montrer par récurrence sur n que pour tout n ≥ 1, S N Rn n= 0,2+ .

Probabilité de gagner la n-ième partie

a) On sait que P P Snn= 1

1− . En déduire que pnn=

58

2,68

0,2 1− × − .

b) Quelle est la probabilité de gagner la 3e partie, la 5e, la 8e, la 9e, la 10e ?

c) Que semble-t-il se passer pour les grandes valeurs de n ?

Comportement asymptotique de (Pn)

a) Montrer que lim .n

np→+∞

=58

D

Exercice 12



b) Déduire que lim .n

np→+∞

−1 =38

On pose p* =58

et P p p* = 1* *−( ) ; chaque coefficient de Pn converge donc

la suite de vecteurs ( )Pn et on écrit que lim *.n

nP P→+∞

=

c) Vérifiez que P S P* *.i =

On admet que la matrice ligne P* est l’unique état stable du graphe probabiliste, il est indépendant de l’état initial P1 .

La suite ( )pn est une suite arithmético-géométrique définie par récurrence par :

p n p pn n1 1= 0,3 1, = 0,2 0,5.et pour tout ≥ ++

Le point fixe de cette suite est le nombre P* tel que p p* * ;= 0,2 0,5+ on

trouve : p* =58

.

On définit alors la suite ( ) 1un n≥ par u p pn n= − *.

La suite ( ) 1un n≥ est géométrique de raison 0,2.

En effet, pour tout entier n ≥ 1,

u p p p p p pn n n n+ + − = + − +( ) = −( ) =1 1= 0,2 0,5 0,2 0,5 0 2* * , * 00 2, .un

Donc, pour tout entier n ≥ 1, u unn= −

110 2( , ) d’où p p p pn

n− = −( ) −* * ( , )110 2

soit pnn=

58

2,68

0,2 1− × − .

2. Exercices d’apprentissage

Graphe probabiliste, matrice, état stationnaire

On considère le graphe probabiliste suivant :

2/5

1/5

3/54/5 1 2

Figure 9. Un graphe probabiliste

Donner sa matrice de transition S.

Déterminer son état stationnaire P*.

Remarque

Exercice 13



Les lancers francs d’Arthur

Lors de matchs de basket, Arthur se comporte de la manière suivante :

S’il réussit un lancer franc, il a une probabilité de 0,8 de réussir le suivant.

S’il rate un lancer franc, il a une probabilité de 0,6 de rater le suivant.

a) Représenter la situation à l’aide d’un graphe probabiliste.

b) Donner la matrice de transition de ce graphe.

Arthur n’a pas réussi son premier lancer franc. Quelle est la probabilité qu’il réussisse le troisième ?

Quel est le taux de réussite de lancers francs d’Arthur ?

On pourra remarquer que la matrice de transition est la même que pour l’exer-cice 13.

Exercice 14




À partir d’exemples, on étudie des systèmes à plusieurs états qui évoluent aléa-toirement au cours du temps. On ne s’intéresse qu’à des systèmes où la proba-bilité de changement d’état est indépendante du temps et ne dépend que de la situation à l’instant précédent. Il s’agit d’observer que les méthodes développées pour les systèmes à deux états se généralisent à des systèmes à N états.

Tout d’abord, en ce qui concerne la modélisation : ces systèmes dynamiques sont modélisés par des graphes probabilistes. La matrice de transition S associée à ces graphes est alors une matrice stochastique d’ordre N, le nombre d’états du système.

L’état probabiliste Pn du système à un instant n est un vecteur ligne dont les coefficients représentent la probabilité d’être dans un état i N∈ 2 ; ; ... ; à l’instant n.

Il est encore défini par récurrence à l’aide de la formule des probabilités totales, ce qui conduit à la formule explicite P P Sn

n= 0 où P0 est l’état initial.

L’étude de l’évolution de ces systèmes nécessite alors le calcul de puissance des matrices stochastiques S. Nous ne developpons pas ici de méthodes générales de calcul de puissance de matrice. Nous nous limitons à une approche expérimen-tale en utilisant des logiciels de calcul ou la calculatrice.

Enfin, il s’agit d’observer différents comportements de la suite des états du sys-tème ( )Pn . Existe-t-il toujours un unique état stable ? A-t-on toujours conver-gence vers un état stable ? La recherche d’états stables du système est faite expérimentalement ou par résolution d’un système linéaire. L’étude de la conver-gence des lois de probabilité reste expérimentale.

Pour débuter

1. Marche aléatoire sur le tétraèdre

On considère une sentinelle sur une tour carrée. Lors de sa ronde, à intervalles de temps réguliers, elle choisit aléatoirement d’aller à l’un des trois coins de la tour qu’elle n’occupe pas au moment de changer. L’évolution de sa position est modélisée par le graphe probabiliste suivant.

A

B

5Matrices d’ordre N, systèmes dynamiques à N états avec N 3



N

1/3

1/3

1/3

1/3

1/31/3

1/3

1/31/31/3

O

E

S

Figure 10. Graphe probabiliste, marche aléatoire sur un tétraèdre (1)

La matrice de transition associée à ce graphe est la matrice stochastique suivante :

S

NESO

N E S O

=

0 1 3 1 3 1 3

1 3 0 1 3 1 3

1 3 1 3 0 1 3

1 3

/ / /

/ / /

/ / /

/ 11 3 1 3 0/ /

.

Considérons le déplacement aléatoire, à des intervalles de temps réguliers, d’une fourmi sur un tétraèdre suivant la règle : pour sa position à l’instant n + 1, elle choisit équiprobablement l’un des trois sommets autre que celui qu’elle occupe à un instant n. Cette marche aléatoire sur un tétraèdre se modélise par le même graphe que celui de la sentinelle.

Pour un système dynamique à quatres états, on parle alors de marche aléatoire sur un tétraèdre.

On note Nn l’événement la sentinelle est au Nord à l’étape n, de même on défi-nit les événements E S On n n, .et

On note Pn le vecteur ligne stochastique donnant l’état probabiliste du système à l’étape n :

P P N P E P S P On n n n n= ( ) ( ) ( ) ( )( ). Expression de Pn en fonction de n

a) Montrer à l’aide de la formule des probabilités totales que pour tout entier naturel n, P P Sn n+1 = .

b) En déduire que pour tout n ≥ 0, P P Snn= 0 .

Remarque

Activité 2



Étude expérimentale

a) À l’aide d’un logiciel de calcul, calculer S S S S2 3 4 10, , .et

b) Qu’observez-vous ?

Étude théorique

a) Vérifier que le vecteur stochastique P* = 1 4 1 4 1 4 1 4 / / / /( ) est stable, c’est-à-dire que P P S* *= .

b) Vérifier que S QDQ= 1− (on pourra utiliser la calculatrice ou un logiciel de calcul pour obtenir Q–1) où :

D =−

−−

1 0 0 0

0 1 3 0 0

0 0 1 3 0

0 0 0 1 3

/

/

/

et Q =

− − −

1 1 0 0

1 0 1 0

1 0 0 1

1 1 1 1

.

On dit que S est diagonalisable.

c) Montrer que pour tout n ≥ 1, S QD Qn n= −1.

d) En déduire que pour tout n ≥ 1, S N Rnn

=13

+ −

où :

N1/ 41/ 41/ 4

1/ 4 1/ 4 1/ 41/ 4 1/ 4 1/ 41/ 4 1/ 4 1/ 4

=

et R =

− − −− − −− −

3 4 1 4 1 4 1 4

1 4 3 4 1 4 1 4

1 4 1 4 3 4

/ / / /

/ / / /

/ / / −−− − −

1 4

1 4 1 4 1 4 3 4

/

/ / / /

.

e) En déduire que ( )Pn converge et que lim .n

nP P→+∞

= *

Le vecteur ligne P* correspond à la loi uniforme sur un univers à 4 éléments. La sentinelle a autant de chances de se trouver à un des quatre coins de la tour.

2. Deuxième marche aléatoire sur le tétraèdre

À présent, lors de sa ronde, à intervalles de temps réguliers, notre sentinelle choi-sit à pile ou face de se déplacer vers sa droite ou vers sa gauche ; elle ne peut plus aller en diagonale. L’évolution de sa position est alors modélisée par le graphe probabiliste suivant :

Remarque



N

1/2 1/2 1/21/2

1/2

1/2

1/2

1/2O

E

S

Figure 11. Graphe probabiliste, marche aléatoire sur un tétraèdre (2)

La matrice de transition associée à ce graphe est la matrice stochastique sui-vante :

S

NESO

N E S O

=

0 1 2 0 1 2

1 2 0 1 2 0

0 1 2 0 1 2

1 2 0 1 2 0

/ /

/ /

/ /

/ /


a) À l’aide d’un logiciel de calcul, calculer S S S S2 3 4 5, , .et

b) Qu’observez-vous?

Etude théorique

a) Montrer par récurrence que pour tout k ≥ 1, S S N Rk2 1 = =− − et S N Rk2 = +avec :

N =

1 4 1 4 1 4 1 4

1 4 1 4 1 4 1 4

1 4 1 4 1 4 1 4

1 4 1

/ / / /

/ / / /

/ / / /

/ / 44 1 4 1 4/ /

et R =

− −− −

− −

1 4 1 4 1 4 1 4

1 4 1 4 1 4 1 4

1 4 1 4 1 4 1

/ / / /

/ / / /

/ / / / 44

1 4 1 4 1 4 1 4− −

/ / / /

.

On pourra commencer par vérifier que SN = N et SR R= − .

b) En déduire que pour tout n ≥ 1, S N Rn n= ( 1)+ − .

c) Vérifier que le vecteur stochastique P* = 1/ 4 1/ 4 1/ 4 1/ 4( ) est stable, c’est-à-dire que P P S* *= .

d) On considère la suite des états du système ( )Pn définie par P P Snn= 0 avec P0

un vecteur stochastique quelconque et P P N P E P S P On n n n n= ( ) ( ) ( ) ( )( ). La suite ( )Pn converge-t-elle ?

La convergence dépend-elle de P0 ? Vous pourrez distinguer plusieurs cas.

Activité 3



Cours Dans ce paragraphe, nous présenterons plusieurs exemples de systèmes dyna-miques à N états avec N supérieur ou égal à 3 traités sous forme d’activités.

Aucune connaissance n’est exigible sur ces systèmes ; il s’agit d’illustrer la grande variété de problèmes que l’on peut modéliser à l’aide de graphes probabilistes et étudier à l’aide du calcul matriciel. Les attentes concernent la maîtrise des bases du calcul matriciel vues au chapitre 2 pour étudier, au moins expérimentalement, divers problèmes.

1. Urnes d’Ehrenfesta) Modélisation

On considère deux urnes A et B contenant au total N boules, numérotées de 1 à N. À chaque instant n (n entier naturel), on tire au hasard, de façon équiprobable, un numéro entre 1 et N, et on change la boule correspondante d’urne. On s’intéresse à l’évolution au cours du temps de ce système.

On note Xn la variable aléatoire qui donne le nombre de boules dans l’urne A à l’instant n (c’est-à-dire après n tirages).

On étudie le cas où N = 4 : les deux urnes contiennent au total 4 boules.

L’urne A à un instant n peut contenir soit 0, soit 1, soit 2, soit 3 ou soit 4 boules.

Elle peut être dans 5 états ; 1 ; 2 ; 3 ; 4. Le passage d’un état à un autre se fait de la manière suivante :

si l’urne A contient 0 boule à l’instant n, on tire nécessairement une boule de B que l’on place dans A ;

si l’urne A contient 1 boule à l’instant n, on a une probabilité de 14

de tirer

cette boule et de la placer dans B et une probabilité de 34

de tirer une boule

dans B et de la placer dans A ;

si l’urne A contient 2 boules à l’instant n, on a une probabilité de 12

de tirer

cette boule et de la placer dans B et une probabilité de 12

de tirer une boule

dans B et de la placer dans A ;

...

On peut modéliser l’évolution du nombre de boules dans l’urne A par le graphe probabiliste suivant :

1

1/4

0 1

3/4

1/2

2

1/2

3/4

3

1/4

1

4

Figure 12. Graphe probabiliste, urnes d’Ehrenfest

C



Sa matrice de transition est la matrice stochastique S de dimension 5 5× sui-vante :

S =

0 1 0 0 0

1/ 4 0 3 / 4 0 0

0 1/ 2 0 1/ 2 0

0 0 3 / 4 0 1/ 4

0 0 0 1 0

.

On note Pn le vecteur stochastique donnant la loi de probabilité de la variable aléatoire Xn : le coefficient de la colonne j +1 est la probabilité que l’urne A contienne j boules à l’instant n, soit P X jn( = ), j entier variant de 0 à 4.

On peut supposer que P0 = 0 0 0 0 1( ), c’est-à-dire qu’initialement toutes les boules sont dans l’urne A.

b) Étude de l’évolution de la répartition des boules

On s’intéresse aux problèmes suivants.

Problème 1. Déterminer la loi de probabilité Pn du nombre de boules de l’urne A, à l’instant n.

Problème 2. Existe-t-il une loi stable P* c’est-à-dire telle que P P S* *= ? Est-elle unique ?

Problème 3. Est-ce que les lois ( )Pn du nombre de boules dans l’urne A convergent ?

-chien. Tatiana Alexeyevna Afanaseva (1876, Kiev - 1964, Leiden), mathémati-cienne russe et danoise.

-fest en 1907 afin d’illustrer certains « paradoxes » dans l’évolution de molé-cules de gaz à l’intérieur d’un récipient partagé en deux compartiments. Au début de l’expérience, toutes les molécules du gaz sont confinées dans le compartiment de gauche. Lorsque l’on retire la paroi séparant les deux com-partiments, les molécules se répartissent uniformément dans tout le volume disponible. Il y a irréversibilité : on n’observe jamais un retour à l’état initial. Ils se sont alors intéressés au problème 4.

Pour travailler en dimension finie, on suppose que l’on étudie le phénomène de diffusion sur 2n étapes et on appelle Tn le temps de premier retour qui est une variable aléatoire qui compte le nombre d’étapes pour revenir à l’instant initial.

Problème 4. Est-ce que le temps moyen de premier retour à l’état initial où toutes les boules se trouvent dans l’urne A est fini ? Si oui, quelle est sa valeur ?

On admet que le temps moyen de premier retour à l’état initial est la limite lorsque n tend vers l’infini de l’espérance de la variable aléatoire Tn .

Ce problème est difficile, pour un nombre de boules N = 4, on admet que ce temps moyen est égal à 16 étapes.

L’activité suivante se propose de répondre aux trois premiers problèmes.

Point historique



Réponse au problème 1. Déterminons Pn .

Déterminons Pn+1 en fonction de Pn .

La formule des probabilités totales donne pour j entier variant de 0 à 4,

P X j P X j P X ini

n nXn i( ) .+

=+= = =( ) × =( )=

∑10

4

1

Interpréter chacun des termes et en déduire que P P Sn n+1 = .

En déduire que pour tout entier n, P P Snn= 0 .

Réponse au problème 2. Recherche d’une loi stable.

a) Déterminer la loi P * stable par S, c’est-à-dire le vecteur stochastique tel que P P S* * .=

b) Vérifier que la loi définie par P * est la loi binomiale 412

;

.

c) Calculer l’espérance de P*. Interpréter.

Réponse au problème 3. Étudions expérimentalement la convergence de (Pn ).

À l’aide d’un logiciel de calcul formel, calculer P S P S P S P S02

04

06

020, , et , puis

P S P S P S P S0 03

05

021, , et .

Qu’observez-vous? Est-ce que la suite ( )Pn semble converger ?

Cas général : N boules.

On admet que la loi stable est alors la loi binomiale N ;12

, on sait que

l’espérance de cette loi est N2

, c’est-à-dire qu’en moyenne, il y a N2

boules dans

l’urne A (et donc aussi dans l’urne B).

Pour le problème 4, on admet que le temps moyen du 1er retour à l’état initial P0 est 2N.

Lorsque N est petit (comme dans notre exemple où N = 4 ), le phénomène de diffu-sion des molécules est réversible (pour N = 4, en moyenne toute les 16 étapes, les boules se retrouvent toutes dans l’urne A), mais pour N grand (par exemple si N est le nombre d’Avogadro N ≈ ×6.02214 1023 ), le temps moyen de premier retour à l’état initial est si grand (plus grand que l’âge de l’univers) que l’on n’observe jamais de retour à l’état initial : on dit que le phénomène de diffusion est irréversible.

2. Comment fonctionne Google ?

Cette partie cite des passages de différents articles de Michael Eisermann que vous pourrez consulter dans leur version intégrale sur internet (par exemple, en tapant Michael Eisermann Google sur votre moteur de recherche).

Activité 4



« Google [est] un moteur de recherche généraliste qui a eu un succès fulgurant depuis sa création en 1998. Le point fort de Google est qu’il trie par ordre d’im-portance les résultats d’une requête, c’est-à-dire les pages web associées aux mots-clés cherchés. L’étonnante efficacité de cette méthode a fait le succès de Google et la fortune de ses fondateurs, Sergey Brin et Lawrence Page. L’idée est née lors de leur thèse de doctorat, puis publiée dans leur article1».1 S. Brin et L. Page, « The Anatomy of a Large-Scale Hypertextual Web Search Engine », Stanford University, 1998.

a) Que fait un moteur de recherche ? Quels sont les défis ?

« À première vue, le principe d’un moteur de recherche est simple : on copie d’abord les pages web concernées en mémoire locale, puis on trie le contenu (les mots-clés) par ordre alphabétique afin d’effectuer des recherches lexico-graphiques. Une requête est la donnée d’un ou plusieurs mots-clés ; la réponse est une liste des pages contenant les mots-clés recherchés. [...] la quantité des documents à gérer est énorme et rien que le stockage et la gestion efficaces posent des défis considérables. Et cela d’autant plus que les requêtes doivent être traitées en temps réel : on ne veut pas la réponse dans une semaine, mais tout de suite.

[...] L’énorme quantité des données entraîne un deuxième problème, plus délicat encore : les pages trouvées sont souvent trop nombreuses : il faut donc choisir les plus pertinentes. La grande innovation apportée par Google en 1998 est le tri des pages par ordre d’importance. Ce qui est frappant est que cet ordre correspond assez précisément aux attentes des utilisateurs.

Selon les informations fournies par l’entreprise elle-même, l’index de Google porte sur plus de 8 milliards de documents web. Une bonne partie des informa-tions répertoriées, pages web et documents annexes, changent fréquemment. Il est donc hors de question de les faire classer manuellement, par des êtres humains : ce serait trop coûteux, trop lent et jamais à jour. L’importance d’une page doit donc être déterminée de manière automatisée, par un algorithme. Comment est-ce possible ? »

b) Quel est le secret de Google ? Une judicieuse modélisation mathématique !

Le web est un graphe.

L’ensemble des pages contenant les mots-clés forme un graphe : les états sont les pages web W W WN1 2, , ...., On trace un arc orienté de Wi vers Wj si la page Wi cite la page Wj ; on considère alors que c’est un vote en faveur de la page Wj . On note l’existence de cet arc par i j→ .

Il faut maintenant mesurer la pertinence d’une page : c’est-à-dire associer à une page Wj un nombre µ j qui est plus ou moins grand suivant la pertinence de la page.

Première idée



Mesurer la pertinence par une marche aléatoire sur le graphe.

On considère la marche aléatoire du surfeur suivante. À une étape, si le surfeur se trouve sur la page Wi qui comporte i liens, à l’étape suivante, il a une probabi-

lité uniforme de 1i

d’être sur l’une des i pages citées.

Une page Wj sera la plus pertinente si quel que soit le point de départ (n’importe quelle page du graphe), la marche aléatoire sur le graphe converge vers une loi de probabilité P N

*1 2= ( )µ µ µ; ; ... ; où µ j est la plus forte probabilité.

Se pose alors le problème de l’unicité de cet état stable (on admet qu’il en existe toujours au moins un pour les matrices stochastiques) et de la convergence vers cet état stable.

La « téléportation » sur le graphe.

On modifie la marche aléatoire précédente afin de contourner les pages ou groupes de pages sans issue (pour supprimer les états absorbants du graphe probabiliste) et afin d’assurer la convergence.

c) Modélisation mathématique

Prenons l’exemple de Michael Eisermann : une requête donne N = 12 pages web à hiérarchiser.

La structure du graphe suggère la hiérarchie suivante :

Figure 13. Exemple graphe de hiérarchisation de pages web

« Parmi les pages W W W W1 2 3 4, , ,et la page W1 sert de référence commune et semble un bon point de départ pour chercher des informations. Il en est de même dans le groupe W W W W9 10 11 12, , , où la page W9 sert de référence commune [observer la symétrie du graphe]. La structure du groupe W W W W5 6 7 8, , , est similaire, où W7 est la plus citée. À noter toutefois que les pages W1 et W9 , déjà reconnues comme importantes, font référence à la page W5. On pourrait ainsi soupçonner que la page W5 contient de l’information essentielle pour l’en-semble, qu’elle est la plus pertinente. »

Une idée est de compter le nombre de votes en faveur d’une page : µ j est le nombre de pages qui citent Wj , c’est-à-dire le nombre d’arc i j→ . Avec l’exemple, on obtient :

Deuxième idée

Troisième idée

Activité 5



J 1 2 3 4 5 6 7 8 9 10 11 12µ j 4 2 2 2 3 1 3 1 4 2 2 2

Les pages W1 et W9 sont alors classées avant W5 et W7. Le problème est que certaines pages émettent beaucoup de liens, ce qui diminue la valeur de leur vote. Plus grave, on peut truquer le vote en ajoutant des pages sans intérêt qui recommande une page que l’on veut valoriser.

Une première marche aléatoire

On considère la marche aléatoire du surfeur suivante : à une étape, si le surfeur se trouve sur la page Wi qui comporte i liens, alors à l’étape suivante, il a une

probabilité uniforme de 1i

d’être sur l’une des i pages citées.

Appelons Xn la variable aléatoire qui représente le numéro de la page atteinte par notre surfeur à l’étape n. Pour tout entier naturel n,

P X j P X j si

Xn i n X i ij i = 1

0 = 1( = ) = ( = ) = =1

+

→

si jj

0 .sinon

La matrice S si

j

ij=

obtenue est la matrice de transition du graphe.

Notons Pn le vecteur stochastique représentant la loi de Xn : pour j variant de 1 à N, le coefficient de la colonne j est la probabilité que le surfeur se trouve sur la page numéro j à l’étape n, soit P X jn( = ).

Par la formule des probabilités totales, on a P X j s P X in iN

ij n( = ) = ( = )1 =1+ ∑ c’est-à-dire P P Sn n+1 = . Un raisonnement par récurrence montre alors que P P Sn

n= 0 où P0 est la position initiale du surfeur, par exemple s’il commence sur la page W7,

on a P0 = (0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 1 ; 0 ; 0 ; 0 ; 0 ; 0).

Déterminons la matrice S de notre exemple ; pour cela commençons par détermi-ner les nombres i , le nombre de liens i j→ partant de Pi :

i 1 2 3 4 5 6 7 8 9 10 11 12

i 4 2 2 2 3 2 1 2 4 2 2 2



Supposons que le surfeur parte de la page W7, c’est-à-dire que P0 = (0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 1 ; 0 ; 0 ; 0 ; 0 ; 0).

a) À l’aide d’un logiciel de calcul, calculer P S P S P S05

010

020, .puis


Supposons maintenant que le surfeur parte de la page W1, c’est-à-dire que P0 = (1 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0).

a) À l’aide d’un logiciel de calcul, calculer P S P S P S05

040

070, .puis


Vérifier que P* =1

17(2 ; 1 ; 1 ; 1 ; 3 ; 1 ; 2 ; 1 ; 2 ; 1 ; 11 ; 1) est un vecteur

stochastique stable par S.

Le souci est que l’on n’a pas forcément unicité d’un état stable, ni convergence vers cet état stable, ou que cet état stable n’est pas pertinent (cas d’un état absorbant : une page sans issue qui ne se cite qu’elle-même).

Les mathématiciens allemands Ferdinand Georg Frobenius (1947-1917) et Oskar Perron (1880-1975) ont montré le résultat suivant :

Si une matrice stochastique S est strictement positive (c’est-à-dire tous ses coeffi-cients sont strictement positifs) alors :

S possède un unique vecteur stochastique P* strictement positif et stable, soit P P S* *= ;

P0 , la suite ( )Pn définie par P P Snn= 0 converge

vers P*.

Théorème 9 (non exigible)

Leur résultat est plus fort, il suffit que Sk soit strictement positive pour un entier k donné.

S sP P

1

2

3

4

5

6

7

8

9

10

11

12

0

1/ 2

1/ 2

1/ 2

0

1/ 2

0

0

0

0

0

0

1/ 4

0

0

1/ 2

0

0

0

0

0

0

0

0

1/ 4

1/ 2

0

0

0

0

0

0

0

0

0

0

1/ 4

0

1/ 2

0

0

0

0

0

0

0

0

0

1/ 4

0

0

0

0

0

1

0

1/ 4

0

0

0

0

0

0

0

1/ 3

0

0

0

0

0

0

0

0

0

0

0

1/ 3

1/ 2

0

1/ 2

0

0

0

0

0

0

0

0

1/ 3

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1/ 2

0

1/ 2

1/ 2

1/ 2

0

0

0

0

0

0

0

0

1/ 4

0

0

1/ 2

0

0

0

0

0

0

0

0

1/ 4

1/ 2

0

0

0

0

0

0

0

0

0

0

1/ 4

0

1/ 2

0

avec

probabilit

de passer

de à ij

i j

=

=

Compléments

Remarque

i / j 1 2 3 4 5 6 7 8 9 10 11 12



D’où l’idée d’introduire une deuxième marche aléatoire sur le graphe des pages sélectionnées, de sorte que la matrice de transition soit strictement positive.

On suppose que le surfeur se trouve sur la page Wi qui comporte i liens. À l’étape suivante,

avec une probabilité c, il abandonne sa page actuelle Wi pour passer de manière équiprobable vers l’une des N pages sélectionnées (Michael Eiser-mann parle alors de « téléportation » sur une page selectionnée quelconque) ;

avec une probabilité 1−c , il suit un des i liens de la page Wi .

Appelons Xn la variable aléatoire qui représente le numéro de la page atteinte par notre surfeur à l’étape n.

On admet que pour tout entier naturel n,

P X j P X j s

cN

ci j

cN

Xn i n X i iji

= 1 0= 1= = ( = ) = =

1

+( )+ − → si

sinnon.

À partir de l’exemple précédent, on obtient pour les premières colonnes de la matrice de transition :

Le nombre 1/ c s’interprète comme le nombre moyen de pages visitées avant de se téléporter ; un choix admis est c = 0,15 correspondant à la visite en moyenne de 6 pages avant de recommencer sur une page aléatoire.

Avec cette deuxième marche aléatoire, le problème de la pertinence des pages sélectionnées se ramène au calcul de l’état stable d’une matrice stochastique strictement positive, donc à la résolution d’un (gros, très gros...) système linéaire.

Pour conclure

Graphe probabiliste et matrice de transition

Pour chacun des graphes probabilistes ci-dessous, donner la matrice de transition S.

1

1/2

1/4

2

1/3

2/31/2

3/4

3

Figure 14. Exercice 15, graphe 1

Une deuxième marche aléatoire

D

Exercice 15



1

0,8

0,9

0,7

2 0,10,2

30,3


1

0,6

0,2

0,2

2 0,50,1

3 0,8

0,30,3


Graphe probabiliste et matrice de transition

Pour chacun des graphes suivants, déterminer les valeurs manquantes x, y et z pour que le graphe soit un graphe probabiliste. Puis donner la matrice de tran-sition.

1

y

x 2 2/7

3/4


1

0,7

0,5

y z

x20,4

30,3


Exercice 16



1z

z

0,5

0,2

2

0,6

0,5

0,2

340,3

yxy


La souris dans le labyrinthe

Une souris se déplace dans le labyrinthe ci-contre. À chaque minute, elle change de case en choisissant, de manière équiprobable, l’une des cases adjacentes. Dès qu’elle atteint soit la nourriture (case 5), soit sa tanière (case 1), elle y reste.

fromage

tanière

32

4

5

1

Représenter la situation par un graphe probabiliste.

Vérifier que sa matrice de transition S est :

S =

1 0 0 0 0

1/ 3 0 1/ 3 1/ 3 0

0 1/ 2 0 0 1/ 2

0 1/ 2 0 0 1/ 2

0 0 0 0 1

.

On suppose que la souris se trouve initialement dans la case 2.

On note P0 le vecteur stochastique 0 1 0 0 0( ) et P P Snn= 0 .

a) À l’aide d’un logiciel, calculer Pn pour n entier variant de 1 à 10.

b) Interpréter ces vecteurs. Qu’observez-vous ?

Exercice 17



Synthèse de la séquence

1. Matrices et opérations sur les matrices

a) Matrices

Une matrice de dimension n p× est un tableau de nombres à n lignes et p colonnes.

A

a a a

a a a

a a a

= .

p

p

n n np

11 12 1

21 22 2

1 2

…

…

…

Si n p= la matrice est dite carrée.

La matrice unité d’ordre n est une matrice carrée à n lignes et colonnes dont la diagonale principale est composée de 1 et dont les autres coefficients sont nuls. Généralement, elle est notée I.

I I2 3=1 0

0 1, =

1 0 0

0 1 0

0 0 1

.

Une matrice stochastique d’ordre n est une matrice carrée dont les coefficients sont compris entre 0 et 1, et dont la somme des coefficients de chaque ligne est égale à 1. C’est une matrice de transition d’un graphe probabiliste.

b) Opérations

Multiplication par un réel k d’une matrice : on multiplie par k chaque coeffi-cient.

Addition de matrices de mêmes dimensions : on ajoute les coefficients corres-pondants.

Multiplication de deux matrices A et B : lorsque le nombre de colonnes de A est égal au nombre de lignes de B, le produit de la ligne i de A par la colonne j de B donne le coefficient du produit A B× correspondant.

En général, le produit n’est pas commutatif : A B B A⋅ ≠ ⋅ .

A

6 Synthèse



Puissance n-ième d’une matrice carrée non nulle A :

A Ip0 = et A A A A nn

n= 1⋅ ⋅ ⋅ ≥... .

foissi

Inverse d’une matrice carrée : s’il existe une matrice B telle que A B B A I⋅ ⋅= = alors A est inversible et son inverse notée A−1 est B.

c) Matrices 2 2

Si Aa bc d

=

et det( ) = 0A ad bc− ≠ alors A est inversible et

AA

d bc a

− −−

1 =1( )det

.

d) Suites de matrices

Soient S une matrice carrée et X0 un vecteur ligne.


Pour tout n de N, X X Snn= 0 .

Si la suite ( )Xn converge vers un vecteur ligne X alors X vérifie : XS =X.

2. Écriture matricielle d’un système linéaire et résolution

Un système ( )

=

=11 12 13 1 1

21 22 23 2 2

3

Sa x a y a z b La x a y a z b La

+ ++ +

11 32 33 3 3=x a y a z b L+ +

s’écrit AX B= avec

Aa a aa a aa a a

X= , =11 12 13

21 22 23

31 32 33

xxyz

Bbbb

et =1

2

3

.

Si la matrice A est inversible, alors le système admet une unique solution X A B= 1− .

La méthode de Gauss s’applique même lorsque A est non inversible. Elle consiste à :

AX B UX L B U= = 1⇔ − avec triangulaire supérieure ;



3. Marche aléatoire sur un graphea) Graphes à deux sommets

L’évolution au cours du temps d’un système dynamique à deux états A et B, dont les probabilités de changement d’état sont indépendantes du temps, est modélisée par un graphe probabiliste de matrice de transition, une matrice stochastiquue S.

A

b

a

1–a 1–bBS

a ab b

=1

1

−−

Graphe probabiliste Matrice de transition

Soit An l’évenement « le système est dans l’état A à l’instant n » et Bn l’évé-nement contraire le système est dans l’état B à l’instant n. L’état probabiliste à l’instant n du système est donné par le vecteur ligne :

P p pn n n= 1−( ) où p P An n= ( ) et 1 = ( )− p P Bn n .

Pour tout n ≥ 0, P P Snn= .0

Si a b, ]0 ; 1[∈ alors la suite des états probabilistes ( )Pn converge vers un état P* stationnaire indépendant de l’état initial P0. On a :

limn

nP P Pa b

b a P SP→+∞ +

( )= =1

= .* * * *avec et

b) Graphes à N sommets

L’évolution au cours du temps d’un système dynamique à N états, dont les probabilités de changement d’état sont indépendantes du temps, est modélisée par un graphe probabiliste à N sommets de matrice de transition, une matrice stochastique S carrée d’ordre N.

L’état probabiliste à l’instant n du système est donné par le vecteur ligne P P jn n j N= ( ) 1( ) ≤ ≤ où P jn ( ) est la probabilité que le système soit dans l’état j

à l’instant n. Pour tout n P P Snn≥ 0, = .0

Compléments

Si la matrice stochastique S est strictement positive (c’est-à-dire que tous ses coefficients sont strictement positifs) alors la matrice S possède un unique vec-teur stochastique P* strictement positif et stable, soit P P S* *= , et quel que soit l’état initial P0 , la suite des états probabilistes ( )Pn converge vers P*.



Exercices de synthèse

Préparation au ROC

Soient Aa bc d

=

. On se propose de démontrer que A est inversible si, et seu-

lement si, ad bc− ≠ 0. Soient Bd bc a

=−

−

.

a) Montrer que AB BA ad bc I= = −( )⋅ .

b) Montrer que si ad bc− ≠ 0 alors A est inversible.

c) On suppose que A est inversible et que ad bc− = 0. Montrer que B = 0. Conclure.

Puissances de matrices

On considère la matrice A =

1 3 6

6 8 12

3 3 4

−−−

.

a) Montrer que A A I2 = 2− + .

b) Montrer par récurrence que pour tout entier naturel n,

A a A a Inn n=

13

23

−

+ +

où an( ) est la suite géométrique de raison −2

et de premier terme a0 =13

.

c) En déduire une expression de An en fonction de n et de A.

D’Alexandre Pouchkine à Markov…

Andrei Andreevich Markov, en 1913, considèra une suite de 20 000 caractères russes pris dans Eugène Oneguine d’Alexandre Pouchkine. Il distingue entre les voyelles et les consonnes. Il note que :

La probabilité qu’une voyelle soit suivie d’une consonne est de 0,872, et celle qu’elle soit suivie d’une voyelle est de 0,128 ;

La probabilité qu’une consonne soit suivie d’une voyelle est de 0,663, et celle qu’elle soit suivie d’une consonne est de 0,337.

On peut représenter la situation par le graphe suivant :

V0,128 0,337

0,663

0,872

C

Figure 20. Graphe probabiliste des occurrences de voyelles et consonnes

B

Exercice I

Exercice II

Exercice III



Donner la matrice S de transition associée à ce graphe.

On note Pn le vecteur ligne p pn n1−( ) où pn est la probabilité que la n-ième

lettre du texte soit une voyelle, donc 1− pn est celle que ce soit une consonne.

Montrer que pour tout n ≥ 1, P P Snn= 1

1− .


a) À l’aide de la calculatrice, calculer S S S S5 10 20 50, , .et

b) Qu’observe-t-on ? La suite ( )Pn semble-t-elle converger ? Quel serait le vec-teur limite P* ?

Étude théorique

a) Déterminer le vecteur ligne stochastique P x x* = 1−( ) stable, c’est-à-dire tel que P P S* *= .

b) Montrer que pour tout n ≥ 1, S N Rn n= ( 0,535)+ − où

N R=1

1,535

0,663 0,872

0,663 0,872=

11,53

et55

0,872 0,872

0,663 0,663.

−−

c) En déduire que ( )Pn converge et que lim .n

nP P→+∞

= *

Le vecteur limite P* = 0,432 0,568( ) correspond aux fréquences de voyelles (43,2 %) et de consonnes (56,8 %) dans un texte russe. Pour un texte en français,

on a P* = 0,456 0,544( ) et en allemand P* = 0,385 0,615( ).

Évolution du phosphore dans un écosystème

Pour étudier l’évolution de molécules de phosphore dans un écosystème, on considère quatre états possibles : La molécule est dans le sol (état s) ; La molécule est dans l’herbe (état h) ; La molécule est absorbée par du bétail (état b), et La molécule est sortie de l’écosystème considéré (état e).

La matrice de transition S de ce système dynamique à quatre états est

S

shbe

s h b e

=

3 5 3 10 0 1 10

1 10 2 5 1 2 0

3 4 0 1 5 1 2

/ / /

/ / /

/ / / 00

0 0 0 1

.

On note :

Sn l’événement « la molécule est dans le sol à l’étape n » ;

Hn l’événement « la molécule est dans l’herbe à l’étape n » ;

Remarque

Exercice IV



Bn l’événement « la molécule est absorbée par du bétail à l’étape n » et

En l’événement « la molécule est sortie de l’écosystème considéré à l’étape n ».

On note Pn le vecteur ligne stochastique donnant l’état probabiliste du système, soit :

P P S P H P B P En n n n n= ( ) ( ) ( ) ( )( ).

a) Tracer le graphe probabiliste modélisant la situation.

b) Quelle est, selon ce modèle, la probabilité que la molécule de phosphore passe de l’herbe au bétail ? du sol à l’herbe ? de l’herbe à l’extérieur de l’écosys-tème ?

c) Quelle est la probabilité que la molécule de phosphore passe de l’herbe à l’extérieur du système en deux étapes? (Vous pouvez vous aider d’un arbre de probabilité.)

a) Entraînement aux (ROC) Montrer, à l’aide de la formule des probabilités totales, que P P Sn n+1 = . Puis, par récurrence, montrer que pour tout entier n, P P Sn

n= 0 .

b) On suppose que la répartition initiale est P0 = (0,4 ; 0,2 ; 0,2 ; 0,2). Calculer P1 puis P2. Interpréter ces vecteurs.

a) Calculer Sn pour n = 10, puis n = 20 puis n = 50.

b) Qu’observe-t-on ?

c) Que peut-on en conclure ?

Supposons que lorsque la molécule sort de l’écosystème, on réintroduit du phosphore dans le sol, ce qui conduit à la matrice suivante :

S

shbe

s h b e

=

3 5 3 10 0 1 10

1 10 2 5 1 2 0

3 4 0 1 5 1 2

/ / /

/ / /

/ / / 00

1 10 0 0 9 10/ /

.

a) Calculer Sn pour n = 10, puis n = 20 puis n = 50.

b) À présent, qu’observe-t-on ?

c) Que peut-on en conclure ?



Problème d’endémie

On s’intéresse à l’évolution de l’état d’une population par rapport à une maladie.

Un individu de la population peut être dans l’un des trois états suivants : Immu-nisé (I), Malade (M) ou non malade et non immunisé (S). D’un mois à l’autre, son état peut changer suivant les règles suivantes : Étant immunisé, il peut le rester avec une probabilité 0,9 ou passer à l’état (S)

avec une probabilité 0,1 ; Étant dans l’état (S), il peut le rester avec une probabilité 0,5 ou passer à l’état

(M) avec une probabilité 0,5 ; Étant malade, il peut le rester avec une probabilité 0,2 ou passer à l’état (I) avec

une probabilité 0,8.

Modélisation

a) Représenter la situation par un graphe probabiliste.

b) Vérifier que la matrice de transition est :

SI

MS

I M S

=

0 9 0 0 1

0 8 0 2 0

0 0 5 0 5

, ,

, ,

, ,

.

Évolution à court terme

On suppose qu’au départ l’individu est immunisé. On note P0 le vecteur stochas-tique P0 = 1 0 0( ) et on note Pn le vecteur P P Sn

n= 0 .

On admet que Pn est « l’état probabiliste de l’individu » au bout de n mois.

a) Calculer S2 puis P2.

b) En déduire la probabilité que l’individu soit malade au bout de 2 mois.

Évolution à long terme

a) On suppose qu’au départ l’individu est immunisé. Déterminer, à l’aide d’un logi-ciel de calcul, la probabilité qu’il soit malade dans un an, puis dans deux ans.

b) On suppose maintenant qu’au départ l’individu est non malade et non immu-nisé. Déterminer la probabilité qu’il soit malade dans un an, puis dans deux ans.

c) Q u’observe-t-on ?

d) On veut déterminer le vecteur stochastique P x y z* = ( ) stable, c’est-à-dire tel que P P S* *= . Montrer que P* est la solution du système linéaire suivant :

x y zx z

y z

+ +−

− +

= 1

0,1 0,5 = 0

0,8 0,5 = 0.

Exercice V



Résoudre ce système.

On admet que, quelles que soient les conditions initiales P0 , la suite ( )Pn converge vers P*.

e) En déduire la proportion d’individus malades dans la population étudiée.

La ruine du joueur

Deux joueurs A et B se lancent dans un jeu à plusieurs manches, chaque manche étant équitable. On suppose que la somme de leur fortune est N euros. À chaque manche, le joueur gagnant reçoit 1€ de l’autre joueur. Le jeu s’arrête lorqu’un des joueurs est ruiné.

On note Xn la variable aléatoire qui donne la fortune du joueur A à l’instant n (c’est-à-dire après n manches).

Prenons N = 4 : la fortune de A à un instant n est un entier entre 0 et 4.

On peut modéliser l’évolution de la fortune de A par le graphe probabiliste sui-vant :

1/2

1 10 1

1/2

1/2

1/2

1/2 1/2

2 3 4

Figure 21. La ruine du joueur

On note Pn le vecteur stochastique P P P P Pn n n n n(0) (1) (2) (3) (4)( ) où P jn ( ) est la probabilité qu’à l’instant n, la fortune de A soit de j euros, c’est-à-dire P j P X jn n( ) = ( = ). Autrement dit, le vecteur Pn est la loi de probabilité de la variable Xn .

Donner la matrice de transition S.

Montrer que pour tout entier n, P P Snn= 0 .

À l’aide d’un logiciel de calcul, calculer S S S10 20 50, .et Qu’observez-vous ?

On admet que la suite de matrice ( )Sn converge vers la matrice :

S∞

=

1 0 0 0 0

3 / 4 0 0 0 1/ 4

1/ 2 0 0 0 1/ 2

1/ 4 0 0 0 3 / 4

0 0 0 0 1

.

On suppose qu’initialement chacun des joueurs met en jeu 2 €, c’est-à-dire P0 = 0 0 1 0 0( ).

a) Calculer P P S∞ ∞= 0 .

b) Interpréter ce résultat.

Exercice VI



On suppose maintenant que le joueur A met en jeu 1 €, c’est-à-dire : P0 = 0 1 0 0 0( ).

a) Calculer P P S∞ ∞= 0 .

b) Interpréter ce résultat.

On est ici dans une situation où la suite ( )Pn avec P P Snn= 0 converge mais la

limite dépend de l’état initial P0. Vous pouvez vérifier qu’il existe une infinité d’états stables, ils sont de la forme P p p* = 0 0 0 1−( ) avec p ∈[0 ; 1]. Au final, l’un des deux joueurs sera ruiné, et ce avec une probabilité qui dépend de la répartition initiale des 4 €.

Bistochasticité et loi uniforme

On considère une matrice stochastique S telle que la somme des coefficients de chaque colonne soit aussi égale à 1 ; on dit alors que la matrice S est bistochas-tique. Par exemple, les matrices suivantes sont bistochastiques :

SBD

B D

=

0 7 0 3

0 3 0 7

, ,

, ,

Microcrédit avec a b= = 30 %

S

NESO

N E S O

=

0 1 3 1 3 1 3

1 3 0 1 3 1 3

1 3 1 3 0 1 3

1 3

/ / /

/ / /

/ / /

/ 11 3 1 3 0/ /

Sentinelle sur une tour carrée - 1er cas

Montrer dans le cas général que la loi uniforme est toujours un vecteur stable pour une matrice bistochastique.

Exercice VII


Documents

Calcul matriciel, modèles probabilistes