Atelier Matrices et Suites en Atelier Matrices et Suites en spécialité Sspécialité S

Regroupement inter académique.Regroupement inter académique.Décembre 2011 – MontpellierDécembre 2011 – Montpellier

Inspection régionale de MontpellierInspection régionale de MontpellierFrédéric LarocheFrédéric Laroche

Matrices, Graphes et SuitesMatrices, Graphes et Suites

Introduction des matrices et des graphes Introduction des matrices et des graphes dans l’enseignement de spécialité de dans l’enseignement de spécialité de terminale S, comment ?terminale S, comment ?

Des exemples de situations en lien avec les Des exemples de situations en lien avec les recommandations du programmerecommandations du programme

Doudou, un exemple commenté qui met en Doudou, un exemple commenté qui met en relation notions du programme et problèmerelation notions du programme et problème

1 2 3

1 0,9 0,05 0,05

2 0,7 0 0,3

3 0,8 0 0,2

Dormir

Manger P

Roue

1 0 0,884 0,044 0,072nn n P P

1 0 0,884 0,044 0,072nn n P P

Lien avec le programmeLien avec le programmeMatrices et suites : Matrices et suites : Il s’agit d’étudier des exemples de processus discrets, déterministes ou Il s’agit d’étudier des exemples de processus discrets, déterministes ou stochastiques, à l’aide de suites ou de matrices.stochastiques, à l’aide de suites ou de matrices.

On introduit le calcul matriciel sur des matrices d'ordre 2. Les calculs sur des matrices d'ordre 3 On introduit le calcul matriciel sur des matrices d'ordre 2. Les calculs sur des matrices d'ordre 3 ou plus sont essentiellement effectués à l'aide d'une calculatrice ou d'un logiciel.ou plus sont essentiellement effectués à l'aide d'une calculatrice ou d'un logiciel.

Programme TS spé maths Activités liées à Doudou

Matrices carrées, matrices colonnes : opérations. Ok : attention au « problème » des vecteurs ligne/colonne.

Matrice inverse d’une matrice carrée. Ok : on cherche la distribution stationnaire (a,b,c) en rajoutant l’équation a+b+c=1.

Exemples de calcul de la puissance n-ième d’unematrice carrée d’ordre 2 ou 3.

Ok : calcul à la main (!) ou avec un logiciel (Geogebra par exemple)

Écriture matricielle d’un système linéaire. Ok : voir l’utilisation du CAS GeoGebra

Suite de matrices colonnes (Un ) vérifiant une relation de récurrence du type Un+1 = AUn + B.

Non, quoique…

Étude asymptotique d’une marche aléatoire.Urnes d’Ehrenfest, modèle proie prédateur discrétisé, etc.

Ok : on peut remplacer le graphe initial par le graphe associé à une marche sur les arètes d’un tétraèdre par exemple (matrice 4*4).

Chaines de Markov homogènesChaines de Markov homogènes

On considèreOn considère

un espace d’état E = {1, 2 , … m} qui correspond aux un espace d’état E = {1, 2 , … m} qui correspond aux issues possibles d’une expérience aléatoire,issues possibles d’une expérience aléatoire,

à tout instant à tout instant nn, les variables aléatoires X, les variables aléatoires Xnn à valeurs à valeurs

dans E qui décrivent un système évolutif.dans E qui décrivent un système évolutif.

Si la loi de Si la loi de XXnn+1+1 ne dépend pas de l’histoire du système ne dépend pas de l’histoire du système

mais seulement de Xmais seulement de Xnn : :

on dit que (on dit que (XXnn))n n N N est une est une chaine de Markovchaine de Markov ; ;

si elle ne dépend pas non plus de l’instant si elle ne dépend pas non plus de l’instant nn elle est elle est homogène.homogène.

1 0 0 1 1 1, , ...,n n n n ijn nX j X i X i X i X j X i p P P

Ce qui compte finalement est la connaissance des Ce qui compte finalement est la connaissance des probabilités de passage d’un état i à un état j pour probabilités de passage d’un état i à un état j pour ii et et jj variant de 1 à variant de 1 à m m ::

D’où l’intérêt d’une représentation sous forme d’un D’où l’intérêt d’une représentation sous forme d’un graphe (pas toujours évident) dont les sommets sont les graphe (pas toujours évident) dont les sommets sont les états, ce qui permet d’écrire la matrice de transitionétats, ce qui permet d’écrire la matrice de transition

La probabilité de transition de passer en La probabilité de transition de passer en nn étapes de étapes de l’état l’état ii à l’état à l’état jj est le terme est le terme ijij de la matrice de la matrice PPnn..

11 1

1

m

m mm

p p

P

p p

nijp

Si on note sous forme de vecteur ligne la loi de Si on note sous forme de vecteur ligne la loi de probabilité de Xprobabilité de Xnn : :

alors on aalors on a

Si on a une loi stationnaire Si on a une loi stationnaire , souvent limite des lois , souvent limite des lois nn, ,

elle vérifie les équationselle vérifie les équations

Le temps de retour moyen de l’état Le temps de retour moyen de l’état ii à l’état à l’état ii est est l’inverse de la probabilité l’inverse de la probabilité ppii. .

( 1), ( 2),..., ( )n n n np X p X p X m

11 0

nn nP P

P

1 21

, , ..., , 1m

m ii

p p p p

Introduire les matricesIntroduire les matrices

Quel temps fait-il à Brest ?Quel temps fait-il à Brest ?Aux mois de décembre, janvier et février, le temps à Brest est à peu Aux mois de décembre, janvier et février, le temps à Brest est à peu près le suivant : il n’y a que deux états : pluvieux ou beau. S’il pleut près le suivant : il n’y a que deux états : pluvieux ou beau. S’il pleut un jour alors il repleut le jour suivant avec la probabilité 2/3 ; s’il fait un jour alors il repleut le jour suivant avec la probabilité 2/3 ; s’il fait beau, alors il refait beau avec la probabilité 3/4. beau, alors il refait beau avec la probabilité 3/4.

1. Quelle est la proportion de beaux jours en hiver ?1. Quelle est la proportion de beaux jours en hiver ?

2. Aujourd’hui il fait beau (resp. il pleut) ; combien de temps en 2. Aujourd’hui il fait beau (resp. il pleut) ; combien de temps en moyenne attendrons nous un autre jour de beau temps ? (resp. moyenne attendrons nous un autre jour de beau temps ? (resp. mauvais temps.)mauvais temps.)

Solution :Solution :3/ 4 1/ 4

1/ 3 2/ 3P

3 144 3

, 1 2 734 3

1 7

a b aaa b

a b bP b

a b

1

11

4 41

7 7

kkX k b a

P 1 1

1

1 74/ 7 4

k

X k X k

E P

Introduire les matricesIntroduire les matrices

Matrices : Matrices : Jeunes et vieuxJeunes et vieuxOn distingue les jeunes et les vieux. Un « état » de la population est On distingue les jeunes et les vieux. Un « état » de la population est un point du plan (un point du plan (JJ, , VV).).

On observe la population : la période choisie est la moitié de la On observe la population : la période choisie est la moitié de la durée de vie moyenne, tous les jeunes sont devenus vieux avec un durée de vie moyenne, tous les jeunes sont devenus vieux avec un taux taux cc ou sont morts (taux 1 - ou sont morts (taux 1 - cc) et tous les vieux sont morts ; mais ) et tous les vieux sont morts ; mais chaque classe a « produit » une certaine quantité de jeunes avec chaque classe a « produit » une certaine quantité de jeunes avec les taux de natalité les taux de natalité aa (pour les jeunes) et (pour les jeunes) et bb (pour les vieux). (pour les vieux).

1. Représenter la situation par un graphe.1. Représenter la situation par un graphe.

2. (2. (JJnn) et ( ) et ( VVnn) sont les nombres de jeunes et de vieux lors du ) sont les nombres de jeunes et de vieux lors du nn-ième -ième

recensement. Ecrire les relations entre les vecteurs (recensement. Ecrire les relations entre les vecteurs (JJnn, , VVnn) puis ) puis

étudier les comportements des populations.étudier les comportements des populations.

On prendra par exempleOn prendra par exemple

a=0,1 ; b=0,8 ; c=0,9 a=0,1 ; b=1 ; c=0,9 a=1 ; b=1 ; c=0,9 a=0,5 ; b=1 ; c=0,6

Modélisation avec un grapheModélisation avec un graphe

Le problème du collectionneurLe problème du collectionneurDans chaque paquet de café BlackSabbath on trouve une figurine Dans chaque paquet de café BlackSabbath on trouve une figurine de collection. La série complète comprend 4 figurines : on note de collection. La série complète comprend 4 figurines : on note TT le le nombre de paquets qu’il faut acheter pour obtenir la collection nombre de paquets qu’il faut acheter pour obtenir la collection complète.complète.

1. Représenter le processus par une chaine de Markov (graphe).1. Représenter le processus par une chaine de Markov (graphe).

2. Établir la matrice de transition. Calculer le vecteur de distribution 2. Établir la matrice de transition. Calculer le vecteur de distribution de probabilité à la troisième transition.de probabilité à la troisième transition.

3. Calculer l’espérance et la variance de 3. Calculer l’espérance et la variance de TT. . Interpréter.Interpréter.

Attention, Attention, TT représente le nombre de figurines représente le nombre de figurines distinctes… distinctes…

SolutionSolution

1. Graphe :1. Graphe :

2. Matrice de transition2. Matrice de transition

3. 3. XXii = nombre de paquets à acheter pour passer de l’état = nombre de paquets à acheter pour passer de l’état ii à l’état à l’état

ii+1 : on a +1 : on a

0,25 0,75 0 0

0 0,5 0,5 0

0 0 0,75 0,25

0 0 0 1

P

3

0,0156 0,3281 0,5625 0,0938

0 0,125 0,5938 0,2813

0 0 0,4219 0,5781

0 0 0 1

P

0 1, 0, 0, 0

3 0,016 ; 0,33 ; 0,56 ; 0,09

E P1

1 11 1

3 3 1 41

4 4 3 / 4 3

k

k k

X k X k k

E E E E1 2 3

1 2 3

22

3130

var var var var9

T X X X

T X X X

Transfert de bitsTransfert de bits

Un message codé de façon binaire est transmis à travers un Un message codé de façon binaire est transmis à travers un réseau. Chaque bit est transmis avec une probabilité d’erreur égale réseau. Chaque bit est transmis avec une probabilité d’erreur égale à à aa pour un passage de 0 à 1, égale à pour un passage de 0 à 1, égale à bb pour un passage de 1 à 0 pour un passage de 1 à 0 ((aa et et bb différents de 0 et 1). différents de 0 et 1).

Le résultat de la transmission au Le résultat de la transmission au nnee relais est à valeurs dans {0, 1} ; relais est à valeurs dans {0, 1} ; on suppose que les relais se comportent indépendamment les uns on suppose que les relais se comportent indépendamment les uns des autres et que les erreurs sur les bits sont indépendantes. des autres et que les erreurs sur les bits sont indépendantes.

On souhaite calculer la taille du réseau (la valeur de On souhaite calculer la taille du réseau (la valeur de nn) au delà de ) au delà de laquelle la probabilité de recevoir une erreur est supérieure à laquelle la probabilité de recevoir une erreur est supérieure à εε..

On note On note LL la longueur du message. la longueur du message.

SolutionSolution

LL = 1 : Matrice de transition = 1 : Matrice de transition

On pose d’avoir un 0 au On pose d’avoir un 0 au nnee relais : relais :

Point fixe : d’où Point fixe : d’où

Pour répondre à la Pour répondre à la question, on a la mêmequestion, on a la mêmeloi loi XXkk sur chaque bit d’où : sur chaque bit d’où :

Un algorithme pour conclure…Un algorithme pour conclure…

0 1

0 1

1 1

a aP

b b

0n np X P

1 1 1n n np a p b p

bp

a b

01

nnp p a b p p

On envoie un

Probabilité message pas erroné au ne relais

0 : p0 = 1

1 : p0 = 0

0 1n

nb a

r a ba b a b

1 1n

na b

r a ba b a b

0

1

Li

n ni

r r X

Échange de particulesÉchange de particulesUn récipient creux est divisé en deux chambres A Un récipient creux est divisé en deux chambres A (ou 0) et B (ou 1) par une paroi percée d'un trou. (ou 0) et B (ou 1) par une paroi percée d'un trou.

nn molécules se trouvent primitivement en A molécules se trouvent primitivement en A

Le système évolue Le système évolue irréversiblement irréversiblement vers un état vers un état d'équilibre dans lequel chaque chambre d'équilibre dans lequel chaque chambre contiendra finalement à peu près contiendra finalement à peu près nn molécules, ce molécules, ce qui est vérifié par l'expérience. qui est vérifié par l'expérience.

Le système est un mot de trois bits ; les 8 états possibles sont représentés par les sommets d'une boîte.

Les trois boules sont en 000 qui vont vers l'un des sommets voisins : à chaque instant, un des trois chiffres est inversé.

Promenade symétrique sur un cube. On peut facilement écrire la matrice P de transition, à 8 lignes et 8 colonnes.

Comme Comme PP est bistochastique (somme des termes de chaque ligne est bistochastique (somme des termes de chaque ligne et de chaque colonne égale à 1), on obtient la répartition et de chaque colonne égale à 1), on obtient la répartition stationnaire stationnaire

Après un temps très long tous les sommets auront reçu le même Après un temps très long tous les sommets auront reçu le même nombre de visites : l'intervalle moyen entre deux visites à un même nombre de visites : l'intervalle moyen entre deux visites à un même sommet est 8, d'où l'irréversibilité parfaite (avec sommet est 8, d'où l'irréversibilité parfaite (avec nn particules le particules le temps de retour à un sommet est 2temps de retour à un sommet est 2nn).).

1/ 4 1/ 4 1/ 4 1/ 4 0 0 0 0

1/ 4 1/ 4 0 0 1/ 4 1/ 4 0 0

1/ 4 0 1/ 4 0 1/ 4 0 1/ 4 0

1/ 4 0 0 1/ 4 0 1/ 4 1/ 4 0

0 1/ 4 1/ 4 0 1/ 4 0 0 1/ 4

0 1/ 4 0 1/ 4 0 1/ 4 0 1/ 4

0 0 1/ 4 1/ 4 0 0 1/ 4 1/ 4

0 0 0 0 1/ 4 1/ 4 1/

000 001 010 100 011 101 110 111

000

001

010

100

011

101

110

4 1/ 4111

P

1 1 1, , ...,

8 8 8

Modèle macroscopiqueModèle macroscopique

Les boules ne sont plus discernables ; les sommets de la boîte Les boules ne sont plus discernables ; les sommets de la boîte ayant même somme de leurs trois chiffres sont regroupés, on utilise ayant même somme de leurs trois chiffres sont regroupés, on utilise la promenade aléatoire (les états sont le nombre de boules dans la promenade aléatoire (les états sont le nombre de boules dans B) : B) :

On a : avec On a : avec pp00==pp33, , pp11==pp22, , pp00++pp11++pp22++pp33=1, soit : =1, soit :

et les temps de retour : et les temps de retour :

En général on aura une loi binomiale…En général on aura une loi binomiale…

0 1 2 3, , ,p p p p 1 3 3 1

, , ,8 8 8 8

00 11 22 33

8 8, , , 8, , , 8

3 3m m m m m

Séries de 1Séries de 1

Soit Soit UUnn une suite de variables aléatoires valant 1 avec une suite de variables aléatoires valant 1 avec

probabilité probabilité pp et 0 avec probabilité 1 – et 0 avec probabilité 1 – p.p.

Appelons Appelons NNnn le nombre de 1 consécutifs avant le le nombre de 1 consécutifs avant le nn-ième -ième

tirage. Par convention tirage. Par convention NN00 = 0 et = 0 et NNmm = 0 si le = 0 si le mm-ième -ième

tirage est 0. tirage est 0.

Il est facile de vérifier que Il est facile de vérifier que

1. Déterminer la matrice de transition de 1. Déterminer la matrice de transition de NNnn..

2. Combien de piles consécutifs voit-on dans 100 2. Combien de piles consécutifs voit-on dans 100 tirages ?tirages ?

1 111n n Un

N N 1

SolutionSolution

Avec Avec LL coups : coups :1 0 ... 0 0

1 0 ... 0 0

... ... ... ... ... ...

1 0 0 ... 0

1 0 0 ... 0

0 0 0 ... 0 1

L

p p

p p

Pp p

p p

Histogramme F. de répartition

, 1

, 0

,

1

0 sinon

i i

i

i j

p p

p p

p

RéférencesRéférencesDartmouth College, Dartmouth College, Introduction to probabilityIntroduction to probability, AMS sd, AMS sd

http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/book.html

(+ programmes Mathematica, Maple V, Basic)(+ programmes Mathematica, Maple V, Basic)

  

Benaïm Michel, El Karoui Nicole, Benaïm Michel, El Karoui Nicole, Promenade AléatoirePromenade Aléatoire, Éd. de l’École Polytechnique, 2004, Éd. de l’École Polytechnique, 2004

Engel Arthur, Engel Arthur, L’enseignement des probabilités et de la statistiqueL’enseignement des probabilités et de la statistique , volumes 1 & 2, Cedic Nathan , volumes 1 & 2, Cedic Nathan 19791979

Engel Arthur, Engel Arthur, Mathématique élémentaire d’un point de vue algorithmiqueMathématique élémentaire d’un point de vue algorithmique , Cedic Nathan sd, Cedic Nathan sd

Foata Dominique, Fuchs Aimé, Foata Dominique, Fuchs Aimé, Processus StochastiquesProcessus Stochastiques, Dunod 2002, Dunod 2002

Frugier Gérard, Frugier Gérard, Exercices ordinaires de probabilitésExercices ordinaires de probabilités, Ellipses 1992, Ellipses 1992

Lefebvre Mario, Lefebvre Mario, Processus stochastiques appliquésProcessus stochastiques appliqués, Hermann 2005, Hermann 2005

Rényi Alfred, Rényi Alfred, Calcul des probabilitésCalcul des probabilités, Dunod 1966, Dunod 1966

FINFIN