Enseignement de spcialit en Terminale S compter de la rentre
2012 Acadmie de Crteil
Page 2
Extraits du nouveau programme : Introduction de Matrices et
suites Il sagit dtudier des exemples de processus discrets,
dterministes ou stochastiques, laide de suites ou de matrices. On
introduit le calcul matriciel sur des matrices d'ordre 2. Les
calculs sur des matrices d'ordre 3 ou plus sont essentiellement
effectus l'aide d'une calculatrice ou d'un logiciel .
Page 3
Extraits du nouveau programme
Page 4
Perspective de la prsentation Une entre spcifique par la
rsolution de problmes : les matrices comme outil, une liste
dexemples phares dans le libell du programme (liste non
exhaustive). Phnomnes stochastiques et marches alatoires sur un
graphe probabiliste : des ressorts communs et des variantes.
Page 5
Un exemple contextualis Une petite station de ski dispose de 3
remontes mcaniques (1), (2) et (3). Pour un skieur adoptant un
comportement alatoire, on note X n la variable alatoire donnant le
numro de la remonte utilise aprs n descentes. On note L n la
matrice ligne reprsentant la loi de X n : L n = (P(X n = 1), P(X n
= 2), P(X n = 3)) L n est appel ltat probabiliste linstant n.
Page 6
Donnes numriques
Page 7
Arbre de probabilits conditionnelles
Page 8
Graphe probabiliste La transition de n n+1 (indpendante de n)
peut se visualiser sur un graphe probabiliste. La somme des poids
des artes orientes issues de chaque sommet est gale 1.
Page 9
Matrice de transition A partir de larbre : - On note x 1, x 2,
x 3 les probabilits respectives que le skieur emprunte la remonte
(1), (2), (3) lissue de sa nime descente. - On note y 1, y 2, y 3
les probabilits pour quil se dirige vers la remonte (1), (2), (3)
aprs la descente suivante. - On a alors : y 1 = 0.3 x 1 + 0.4 x 2 +
0.5 x 3 Et les deux autres relations analogues.
Page 10
Matrice de transition Ces relations se traduisent
matriciellement par : L n+1 = L n. T O la matrice T = se lit
directement sur le tableau :
Page 11
Interprtation de T 2 Puisque L n+2 = L n. T 2 les coefficients
de T 2 sinterprtent comme les probabilits de passer dune remonte
une autre en 2 descentes. De mme pour T k.
Page 12
Etat probabiliste aprs n descentes Il est alors facile de
montrer par rcurrence que : L n = L 0. T n (L 0 reprsente les
probabilits de se diriger vers les remontes (1), (2) et (3) en dbut
de sjour).
Page 13
Calculs de T n sur logiciel Sur tableur : Ski T puissance
n.xlsxSki T puissance n.xlsx [Syntaxe : PRODUITMAT(plage;plage)
puis slectionner plage de rponse, puis f2, puis ctrl+maj+entre].
Avec Xcas, en mode calcul approch, on observe une stabilisation
partir de n=15 environ sur la matrice :
Page 14
Une CS de convergence de T n Une condition suffisante pour que
( T n ) converge : On peut dmontrer que, dans le cas des matrices
stochastiques, si T (ou une puissance de T) a tous ses coefficients
non nuls, alors (T n ) converge vers une matrice stochastique T
dont toutes les lignes sont gales entre elles [et gales un tat
stable de T (tat alors unique)].
Page 15
Convergence de ( L n ) En admettant la convergence de ( T n )
vers une matrice dont toutes les lignes sont gales entre elles : -
Par passage la limite dans L n = L 0. T n, ( L n ) converge vers L.
- Par passage la limite dans L n+1 = L n. T, L est stable pour T
(autrement dit, L est un vecteur propre associ la valeur propre 1
). - On peut montrer que, dans ce cas, L ne dpend pas de L 0.
Page 16
Convergence de L n
Page 17
Lessence de la dmarche
Page 18
Lessence de la dmarche Etude asymptotique Rappel : une CS pour
que ( T n ) converge. - Avec la CS : pas de zro (qui exige en
particulier que la probabilit de stationner sur un sommet du graphe
soit non nulle), on a la convergence vers une matrice aux lignes
gales entre elles. - Une condition suffisante moins restrictive :
matrice rgulire : il existe une puissance de T dont tous les
coefficients sont non nuls. Et sil ny a pas convergence ? Rle des
tats stables.
Page 19
Cas o ( T n ) converge L. T = L signifie que L est vecteur
propre de T associ la valeur propre 1. Si lespace propre est de dim
1, L est lunique vecteur propre stochastique. Pour dterminer L, on
cherche donc rsoudre lquation V. T = V, soit V. (T Id) = 0.
Autrement dit, on sintresse au noyau de la transpose de (T Id) en
gardant en tte que lon cherche des vecteurs stochastiques. Note :
le document ressource voque la diagonalisation ventuelle des
matrices dordre 2.
Page 20
Des cas o ( T n ) ne converge pas La condition suffisante de
convergence de ( T n ) portant sur labsence de 0 ne se rencontre
pas trs souvent dans la pratique mais nous allons voir que mme
labsence de convergence de ( T n ) nempche pas dexplorer le
comportement asymptotique de ( L n ).
Page 21
Des cas o ( T n ) ne converge pas Dans ce cas : - Lexistence
dun tat stable reste possible, ce qui autorise la convergence
occasionnelle de ( L n ), cest--dire pour certaines valeurs de L 0.
- On peut rencontrer des cas de convergence de suites extraites de
( T n ).
Page 22
Multiples applications de la dmarche Les marches alatoires sur
un graphe probabiliste peuvent tre dclines dans une multitude de
contextes : Marche alatoire dans un labyrinthe Surf alatoire sur un
mini-rseau intranet Le problme du collectionneur Le modle des urnes
dEhrenfest
Page 23
Page 24
La situation
Page 25
Les hypothses Un cochon dinde est lch dans le labyrinthe. Il se
dplace en changeant de compartiment et, pour un dplacement donn, on
note n le nombre de franchissements de porte quil a effectu depuis
son point de dpart. Pour changer de compartiment, on considre que
le cobaye choisit sa porte au hasard parmi celles qui lui sont
accessibles, indpendamment de son parcours antrieur.
Page 26
Traduction sur un graphe
Page 27
Traduction matricielle De nombreux zros
Page 28
Calcul de puissances de T Avec Xcas :
Page 29
Calcul de puissances de T En mode approch pour n grand :
Page 30
Ici ( T n ) ne converge pas, mais Si on pose : L 0 = (0.1 0.3
0.2 0.2 0.2) On a : L 0. T = L 0, autrement dit L 0 est stable et
la suite ( L n ) constante pour ce L 0. Ici, L 0 est obtenu en
cherchant un tat tel que la probabilit de prsence est
proportionnelle au nombre de porte(s) de chaque case.
Page 31
Page 32
Un mini rseau intranet Surf alatoire sur un micro-rseau de 4
pages. Ranger intuitivement ces 4 pages par ordre dcroissant de
frquentation
Page 33
Graphe probabiliste et matrice de transition associe On pondre
les arrtes orientes en supposant lquiprobabilit de choix des liens
prsents sur chaque page. On obtient comme matrice de transition
:
Page 34
Ici, ( T n ) converge, malgr les 0 En calcul approch avec Xcas,
on obtient une stabilisation sur :
Page 35
Recherche de ltat limite
Page 36
Interprtation La page 4 est donc plus frquente que la page 2
par notre surfeur alatoire. Ce modle fournit une quantification
possible de la pertinence de chacune des pages web du rseau. (Il
est ais de comprendre que cette pertinence ne peut pas tre mesure
par le nombre de liens pointant vers chaque page).
Page 37
Cas du surf avec saut Pour pallier la dshrence de la page 1, on
va maintenant autoriser notre surfeur alatoire interrompre nimporte
quel moment sa navigation prcdente pour la reprendre sur une page
alatoirement choisie. (On intercale une preuve de Bernoulli chaque
tape). Avec saut, on se ramne ltude dune rcurrence matricielle du
type : U n+1 = U n. A + B
Page 38
Page 39
Collection des figurines dune quipe de Volley-Ball Une marque
de crales propose ses clients de constituer une collection de
figurines de lquipe nationale Volley-Ball. La collection complte
consiste en 6 figurines leffigie de chaque titulaire de lquipe. On
a mis en place une stratgie pour viter tout change de figurines. On
souhaite dterminer le nombre dachats moyen de produits effectuer
pour esprer constituer une collection complte.
Page 40
Ici, on cherche une esprance On se ramne une marche alatoire
sur un graphe probabiliste 7 tats (nombre de figurines diffrentes
dj obtenues aprs n achats) du type : La matrice de transition (7 7)
est triangulaire. On sintresse ensuite au premier instant o on
obtient un nouvelle figurine. On calcule enfin lesprance de
complter la collection.
Page 41
Page 42
La situation n = 0
Page 43
Objectifs de modlisation Le modle construire demande de
respecter les proprits suivantes : - la probabilit pour une
particule donne de passer de A B (ou de B A) est la mme, gale 1/N.
- cette probabilit ne dpend pas du temps. - le comportement dune
particule est indpendant de celui des autres particules.
Page 44
Modle stochastique On considre deux urnes A et B, ainsi que N
boules, numrotes de 1 N. Initialement, toutes les boules se
trouvent dans l'urne A. Le processus stochastique associ consiste
rpter de faon indpendante l'opration suivante : Tirer au hasard un
numro i compris entre 1 et N, transfrer la boule ni dans l'urne o
elle n'tait pas. La VAR observe est X n, effectif de lurne A.
Page 45
Une simulation pour N = 10
Page 46
Un autre rsultat pour N = 10
Page 47
Dbut dtude pour N = 3 Graphe probabiliste : les probabilits
figurant sur les flches reprsentent les probabilits conditionnelles
de passage dune valeur de X une autre (indpendamment de n).
Page 48
Sur un arbre pour N = 3 (avec les probabilits conditionnelles
prcdentes)
Page 49
Loi de chaque X n pour N = 3 Pour tout n, on note L n ltat
probabiliste : L n = (P(X n = 0), P(X n = 1), P(X n = 2), P(X n =
3)) On note t ij = P(X n+1 = j | X n = i) indpendante de n. Ces
relations se traduisent par : L n+1 = L n. T O T est la matrice de
transition : T = Par rcurrence, L n = L 0. T n La suite (L n ) ne
dpend que de T et de ltat initial L 0
Page 50
Rle de la parit Ici, (T n ) ne converge pas. Cas N = 2
Page 51
Rle de la parit Pour N = 2, on a : - pour tout k impair, L k =
(0 1 0) - pour tout k pair diffrent de 0, L k+1 = (0,5 0 0,5) (Deux
suites extraites constantes distinctes) Limpact de la parit de k
nest pas li la parit de N. Dans le cas N = 3, on voyait bien sur
larbre que : - P(X k = 0) = P(X k = 2) = 0 pour k pair - P(X k = 1)
= P(X k = 3) = 0 pour k impair
Page 52
Cas N = 6 avec le logiciel Xcas Mme pour N petit, il nest pas
raisonnable deffectuer les calculs la main ds que n grandit. Ais :
L 0 = (0 0 0 0 0 0 1) L 1 = (0 0 0 0 0 1 0) L 2 = (0 0 0 0 5/6 0
1/6) L 3 = (0 0 0 25/36 0 11/36 0) Mais pour de plus grandes
valeurs de n, Xcas donne : (Xcas fournit les valeurs exactes).
Page 53
Premire exploration asymptotique Matrice utile B = T 2 Suite
des B k = T 2k L 2k = L 0. B k ; L 2k+1 = L 0. T. B k B = En mode
calcul approch, B k semble se stabiliser vers Binf :
Page 54
Premire exploration asymptotique On admet que (B n ) converge
vers Binf. = L0. Binf = L0. T. Binf B. Binf = B donc Z stable pour
B T. Binf est la matrice obtenue en dcalant les lignes de Binf ; U
est stable pour T. Binf On passe la limite dans L 2k = L 0. B k et
on obtient la convergence de L 2k vers Z. De mme L 2k+1 CV vers
U.