Chapitre 5 • Pro ces sus sto chas tiques et pro gram ma tion…
216
5.10 notion de Pro gram ma tion dyna mique
sto chas tique
Nous avons étu dié au cha pitre 4 la pro gram ma tion dyna mique se rap por tant à des
situa tions où le hasard n’inter vient pas. Ici, au contraire, nous nous inté res se rons
aux cas où le hasard joue un rôle. Bien entendu, de ce fait, nous ne pour rons plus
com pa rer direc te ment les résul tats de telle ou telle poli tique, mais seule ment des
espé rances mathéma tiques de gain ou de coût. L’intro duc tion de cette mesure des
résul tats impose un cer tain nombre de pré cau tions et, notam ment, ne peut don ner
des indi ca tions valables que si la loi des grands nombres s’applique dans le contexte
du pro blème.
Nous don ne rons d’abord un exemple simple de la manière dont peut se pra ti quer
le cal cul, en pré sence d’évé ne ments sou mis au hasard.
Exemple. Sup po sons que nous ayons affaire à un joueur qui connaît, au début du
jeu, la posi tion qu’il occupe : A, B ou C et reçoit, en phase 1, l’auto ri sa tion de chan
ger de posi tion ou de rester dans sa position selon les flèches (arcs) pleines du des sin
(fig. 5.3). Le hasard inter vient ensuite en imposant au joueur un déplacement aléatoire, sui vant les flèches (arcs) des si nées en poin tillés sur lesquelles sont indiqués le
gain correspondant à chaque déplacement puis la probabilité de celuici. À la fin de
la phase 1, le joueur se trouve donc dans une des trois posi tions A, Β ou C et reçoit
de nou veau – c’est la phase 2 – le droit de se dépla cer à son gré, puis de par ti ci per à
un nou veau tirage (fig. 5.4).
Figure 5.3
Figure 5.4
Étu dions quelles doivent être les stra té gies opti males de ce joueur dans un jeu
com por tant de nom breuses par ties de même type.
Appe lons z 2 (y 2 , x 2 ) l’espé rance mathéma tique du joueur qui, se trou vant en y 2 ,
décide d’aller en x 2 (cf Fig. 5.4) ; on a, en pre nant y 2 5 A :
z 2 1 A, A2 5 2 3 0, 8 1 4 3 0, 2 5 2, 4
z 2 1 A, B2 5 3 3 0, 5 1 4 3 0, 5 5 3, 5
216
5.10 notion de Pro gram ma tion dyna mique
sto chas tique
Nous avons étu dié au cha pitre 4 la pro gram ma tion dyna mique se rap por tant à des
situa tions où le hasard n’inter vient pas. Ici, au contraire, nous nous inté res se rons
aux cas où le hasard joue un rôle. Bien entendu, de ce fait, nous ne pour rons plus
com pa rer direc te ment les résul tats de telle ou telle poli tique, mais seule ment des
espé rances mathéma tiques de gain ou de coût. L’intro duc tion de cette mesure des
résul tats impose un cer tain nombre de pré cau tions et, notam ment, ne peut don ner
des indi ca tions valables que si la loi des grands nombres s’applique dans le contexte
du pro blème.
Nous don ne rons d’abord un exemple simple de la manière dont peut se pra ti quer
le cal cul, en pré sence d’évé ne ments sou mis au hasard.
Exemple. Sup po sons que nous ayons affaire à un joueur qui connaît, au début du
jeu, la posi tion qu’il occupe : A, B ou C et reçoit, en phase 1, l’auto ri sa tion de chan
ger de posi tion ou de rester dans sa position selon les flèches (arcs) pleines du des sin
(fig. 5.3). Le hasard inter vient ensuite en imposant au joueur un déplacement aléatoire, sui vant les flèches (arcs) des si nées en poin tillés sur lesquelles sont indiqués le
gain correspondant à chaque déplacement puis la probabilité de celuici. À la fin de
la phase 1, le joueur se trouve donc dans une des trois posi tions A, Β ou C et reçoit
de nou veau – c’est la phase 2 – le droit de se dépla cer à son gré, puis de par ti ci per à
un nou veau tirage (fig. 5.4).
Figure 5.3
Figure 5.4
Étu dions quelles doivent être les stra té gies opti males de ce joueur dans un jeu
com por tant de nom breuses par ties de même type.
Appe lons z 2 (y 2 , x 2 ) l’espé rance mathéma tique du joueur qui, se trou vant en y 2 ,
décide d’aller en x 2 (cf Fig. 5.4) ; on a, en pre nant y 2 5 A :
z 2 1 A, A2 5 2 3 0, 8 1 4 3 0, 2 5 2, 4
z 2 1 A, B2 5 3 3 0, 5 1 4 3 0, 5 5 3, 5