Solutions
482
Solu tionS deS exer ciceS du cha pitre 5
5.1 1) État E k : depuis le der nier bit trans mis cor rec te ment, k bits faux ont été trans mis.
Ré ini tia li sation : arc (N, 1) ; si cet arc n’exis tait pas (p N = 1), on aurait affaire à un graphe
d’un pro blème de renou vel le ment.
2) a)
0
0
0
0
0
0
0
0
0
0 0, 95 0, 05
0, 80
0, 85
0, 90
0, 10
0, 15
0, 20
1
1
2
2
3
3
M 
b) P(0) = [l ; 0 ; 0 ; 0] , P(1) = [0,95 ; 0,05 ; 0 ; 0] = P(0) # M
P(2) = [0,91 ; 0,05 ; 0,04 ; 0] = P(1) # M
La pro ba bi lité cherc hée est p 2 (2) = 0,04.
(En fait, c’est q 0 # q 1 : on pou vait ainsi l’obte nir plus rapi de ment.)
3)  a) Cette chaîne de Markov est régu    lière. En effet, son graphe est fini for    te    ment connexe 
(il com porte un cir cuit hamiltonien (0, 1, 2, 3, 0)) : la chaîne com porte une seule classe d’états,
donc récur rents ; de plus cette classe est a pério dique car le graphe com porte une boucle en E 0 .
D’où : P
* 5 P
* # M, soit en posant P
* 5 3a, b, c, d4 :
0,95a +
0,2b +
0,15c +
0,1d = a
(1)
0,05a
+
0,9d = b
(2)
0,8b
= c
(3)
0,85c
= d
(4)
a +
b +
c +
d = 1
(5)
d’où c = 0,8b, puis d = 0,68b ; en repor tant dans (2) :
0,05a = b(1 – 0,612) = 0,388 d’où a = 7,76b.