Exercices sur le chapitre 5

Jean-Louis Poss

26 mai 2003

1 Exercice 3.27.
Une urne blanche et une urne noire contiennent chacune trois boules prises dans un ensemble de
trois boules blanches et de trois boules noires. Une transition consiste à prendre simultanément et au
hasard une boule dans chaque urne et à la placer dans l’autre. On dit que le système est dans l’état
Ej si l’urne blanche contient j boules blanches. (Elle contient donc aussi (3 − j) boules noires et le
contenu de l’urne noire est connu).
Soit Xn le nombre de boules blanches dans l’urne blanche après n transitions. On pose :
 
pi,n = P(Xn = i), Πn = p0,n p1,n p2,n p3,n , ai,j = P(Xn+1 = j | Xn = i).

1. Déterminer la matrice A dont l’élément placé à la (i+1)-ième ligne et à la (j +1)-ième colonne

est ai,j .
2. Déterminer la relation donnant Πn+1 en fonction de Πn .
3. Déterminer, si elle existe, la matrice Π∗ qui vérifie la relation Π∗ = Π∗ A. Que peut-on en
conclure ?
4. Calculer A∞ = lim An ; en déduire Π∞ = lim Πn en supposant que l’on part de l’état Ej
n→∞ n→∞
pour j = 0, 1, 2 et 3.
Avez-vous une remarque à formuler ?

1. On trouve « immédiatement » :
 
0 1 0 0
 1 4 4
0 
A= 9 9 9
 
 0 4 4 1 
9 9 9

0 0 1 0

2. D’après le cours : Πn+1 = Πn A.

1
 3. La matrice A a une valeur propre égale à 1 ; soit Π∗ = [x y z t] le vecteur propre associé tel
que x + y + z + t = 1. On résout le système linéaire
 1
 x = 9y

 y = x + 4y + 4z

9 9
4 4

 z = 9 y + 9z + t

 1
t = 9z

et on obtient
1 9 9 1
Π∗ = .
20 20 20 20
Si Πn a une limite Π∞ lorsque n tend vers l’infini on a Π∞ = Π∗ .
4. On calcule  4 41 32 4 
81 81 81 81
 41 328 328 32 
A3 =  729 729 729 729
 
32 328 328 41 
729 729 729 729
 
4 32 41 4
81 81 81 81

D’après le théorème 62 la matrice An a donc une limite A∞ lorsque n tend vers l’infini ; A∞ a
ses lignes égales et A∞  0.
En passant à la limite dans la relation Πn = Π0 An on voit que Πn a une limite Π∞ lorsque n
tend vers l’infini et que chaque ligne de A∞ est égale à Π∞ .
Donc  1  9 9 1
20 20 20 20
1 9 9 1  1 9 9 1 
20 20 20 20
Π∞ = et A∞ =  .
 
20 20 20 20 1 9 9 1
20 20 20 20
 
1 9 9 1
20 20 20 20

On remarque que la limite de Πn est indépendante de l’état initial Π0 : la chaîne est stationnaire.

2 Guetteur
Un guetteur surveille les abords du château depuis l’un des quatre postes de guet situés en haut d’une
tour. Toutes les heures il change de poste en se rendant aléatoirement dans un des deux postes voisins
du poste où il se trouve.
1. Déterminer les classes. Les états sont-ils récurrents ou transitoires ?
2. Déterminer le temps de récurrence moyen.

2
1. Tous les états communiquent : il y a donc une seule classe. C’est une classe finale : tous les
états sont récurrents.
La matrice de transition est : On en déduit immédiatement
   
0 1/2 0 1/2 1/2 0 1/2 0
 1/2 0 1/2 0   0 1/2 0 1/2 
A=  0 1/2 0
. A2 =  1/2 0 1/2 0  .

1/2 
1/2 0 1/2 0 0 1/2 0 1/2

puis
∀n ∈ N∗ , A2n = A2 et A2n−1 = A.
D’où :
(2p) 1 (2p−1)
∀i ∈ {1, 2, 3, 4}, ∀p ∈ N∗ , ai,i = , et ai,i = 0.
2
∞
(n)
X
Donc, pour tout i, la série ai,i diverge : ceci confirme que tous les états sont récurrents.
n=1
Les valeurs propres de A sont −1, 1 et 0 (double) : il y a une seule classe récurrente.
2. On a :
∞
X 1 2 − z2
Ai,i (z) = 1 + z 2p = si |z| < 1.
2 2(1 − z 2 )
p=1

D’où
∞
Ai,i (z) − 1 s2 X 1
Fi,i (z) = = = s2p
Ai,i (z) 2 − s2 2p
p=1

et
(2p) 1 (2p−1)
∀i ∈ {1, 2, 3, 4}, ∀p ∈ N∗ , fi,i = et fi,i = 0.
2p
On a
∞ ∞
X (n)
X 1
∀i ∈ {1, 2, 3, 4}, fi,i = =1
2p
n=0 p=1

ce qui confirme que tous les états sont récurrents.

Le temps de récurrence moyen de l’état i est :
∞ ∞
X (n)
X 1
nfi,i = p = 4.
2p−1
n=1 p=1

0 (1).)
(On peut également calculer Fi,i

3
3 Promenades aléatoires
3.1 Promenades aléatoires sur une droite
Un point, initialement à l’origine, se déplace à chaque tran- p si j = i + 1,
sition d’une unité vers la droite avec la probabilité p ou vers ai,j = q si j = i − 1,
la gauche avec la probabilité q = 1 − p. 0 sinon.
1. Les états sont-ils transitoires ou récurrents ?
2. Déterminer le temps de récurrence moyen.

On a :  
(2n) 2n n n (2n+1)
∀n ∈ N, a0,0 = p q et a0,0 = 0.
n
√
D’après la formule de S TIRLING (n! ∼ 2πnnn e−n ) :
(2n) (4pq)n
a0,0 ∼ √ ·
nπ
Distinguons deux cas :
• p 6= q
∞
(k)
X
On a pq = p(1 − p) < 1/4 et donc 4pq < 1 : la série a0,0 converge, donc l’origine, comme
k=0
tous les autres états, est un état transitoire.

• p = q = 1/2
∞
(2n) √ X (k)
On a a0,0 ∼ 1/ nπ : la série a0,0 diverge, donc l’origine, comme tous les autres états, est un
k=0
état récurrent.
 
(2n) 2n 1
n
On a : a0,0 = . Donc :
n 4
∞ 
2n z 2
n

X 1
A0,0 (z) = =√ si |z| < 1.
n 4 1 − s2
n=0

D’où
∞ 2n


A0,0 (z) − 1 p
2
 X
n z
2n 
F0,0 (z) = =1− 1−z =1− 1−
A0,0 (z) 2n − 1 2
n=1
et
2n


(2n) n 1
2n (2n−1)
∀n ≥ 1, f0,0 = , f0,0 = 0.
2n − 1 2
∞
(2n) 1 X (2n)
En appliquant la formule de S TIRLING on obtient : f0,0 ∼ √ ; la série 2nf0,0 di-
2 πn3/2 n=1
verge, donc le temps de récurrence moyen est infini.

4
3.2 Promenades aléatoires dans un plan
On se limite au cas symétrique, c’est-à-dire au cas où à chaque transition le point, initialement à
l’origine, se déplace d’une unité dans l’une des quatre directions (Est, Nord, Ouest ou Sud) avec une
probabilité égale à 1/4.
1. Les états sont-ils transitoires ou récurrents ?
2. Déterminer le temps de récurrence moyen.

Une trajectoire ramenant à l’origine (pas nécessairement pour la première fois) après (2n) transitions
est représentée par une suite comportant i fois Est, i fois Ouest, (n − i) fois Nord et (n − i) fois Sud
pour toutes les valeurs de i entre 0 et n. On a donc :
n
(2n)
X (2n)! 1
2n
∀n ∈ N, a0,0 =
2 .
(i!)2 (n − i)! 4
i=0

Or :
n  n  
2n X n 2
  2
X (2n)! 2n

2 = = .
(i!)2 (n − i)! n i n
i=0 i=0

(On rappelle que ce dernier résultat peut être obtenu en développant par la formule du binôme les

2
deux membres de l’égalité (1 + t)2n = (1 + t)n et en identifiant le coefficient de tn .)
Finalement :  2
(2n) 2n 1
2n
a0,0 = .
n 4
La formule de S TIRLING donne :
√
2
(2n) 2π(2n)2n+1/2 e−2n 1
a0,0 ∼ √ ∼
( 2πnn+1/2 e−n )4 24n nπ
∞
(2n)
X
La série a0,0 diverge et l’origine, ainsi que tout point du plan, est donc un état récurrent.
n=0

3.3 Promenades aléatoires dans l’espace

On se limite au cas symétrique, c’est-à-dire au cas où à chaque transition le point, initialement à
l’origine, se déplace d’une unité dans l’une des six directions (Haut, Bas, Est, Ouest, Nord ou Sud)
avec une probabilité égale à 1/6.
Montrer que les états sont tous transitoires.
Une trajectoire ramenant à l’origine (pas nécessairement pour la première fois) après (2n) transitions
est représentée par une suite comportant i fois Haut, i fois Bas, j fois Est, j fois Ouest, (n − i − j)

5
fois Nord et (n − i − j) fois Sud pour toutes les valeurs de i et j positives ou nulles et telles que
i + j ≤ n. On a donc :
n X
n−i  
(2n)
X (2n)! 1
2n 2n 1
n
∀n ∈ N, a0,0 =
2 ≤ cn Sn
(i!)2 (j!)2 (n − i − j)! 6 n 12
i=0 j=0

où
n!
cn = max
i,j i!j!(n − i − j)!
et
n X
n−i n   n−i  
X n! 1
n X n 1
i X n − i 1
j 1
(n−i)−j
Sn = = = 1.
i!j!(n − i − j)! 3 i 3 j 3 3
i=0 j=0 i=0 j=0
| {z }

n−i
2
= 3

D’où :  
(2n) 2n 1
n
a0,0 ≤ cn .
n 12
Cherchons un équivalent de cn lorsque n tend vers l’infini. Soit (i0 , j0 ) un couple de valeurs de i et
n!
j tel que soit maximum ; en comparant avec les valeurs obtenues pour i = i0 − 1 et
i!j!(n − i − j)!
i = i0 + 1 on obtient

n − j0 − 1 ≤ 2i0 ≤ n − j0 + 1 et, de la même façon, n − i0 − 1 ≤ 2j0 ≤ n − i0 + 1.

D’où
n n n n
− 1 ≤ i0 ≤ + 1 et − 1 ≤ j0 ≤ + 1.
3 3 3 3
Étudiant les différents cas on obtient :
(3m − 1)! , (3m)! (3m + 1)!
c3m−1 = c3m = et c3m+1 = ·
(m!)2 (m − 1)! (m!)3 (m!)2 (m + 1)!

Appliquant la formule de S TIRLING on obtient dans tous les cas

√ √
3 3 3n
 
2n 1
n 3 6 1
cn ∼ et donc cn ∼ 3/2 3/2
·
2π n n 12 (2π) n
∞   ∞
X 2n 1
n X (2n)
La série cn est convergente, donc également la série a0,0 : l’origine, ainsi que
n 12
n=0 n=0
tous les points de l’espace, est transitoire.