Feuille d’Exercices III

Processus Stochastiques

Exercice 1. On considère la chaîne de Markov de matrice de transition

 
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 7
0 0 0 0
 8 8 
1 2
0 0 0 0 0 0 0 0
 
3 3
1 3
 
0 0 0 0 0 0 0 0
 4 4
1 0 0 0 0 1
0 0 1
0
P = 2 3 4 4
 
0 4 1 
0 0 0 4 0 0 0 0
 1 3

0 0 0 0 0 0 0 0
 4 4
0 0 1 0 0 0 0 0 0 0
 
2 1 1 1 
5 0 0 0 5 5 0 0 5 0
0 0 1 0 0 0 0 0 0 0
1. Dessiner le graphe de la chaîne.

0 1 2 3

8 7

4 5 6 9

Solution.

2. Donner les classes de la chaîne et dites si elles sont fermées et donner leur période.

Solution. On voit que les classes sont {0}, {1, 5}, {2, 3, 9, 6, 7}, {4, 8}.
{0} est de période 1 car il est absorbant. De même {1, 5} est depériode 1 car P11 , P55 > 0. {4, 8} est aussi
de période 1 car on peut faire le chemin 4 → 8 → 4 ainsi que 4 → 8 → 8 → 4 et pgcd(2, 3) = 1. Pour la
classe {2, 3, 9, 6, 7} on voit que tous les chemins pour aller de 2 à 2 par exemple sont de longueur 3k et ainsi
la période de cette classe est 3.
On voit que {0} est une classe fermée, {1, 5} aussi, {2, 3, 9, 6, 7} aussi mais {4, 8} ne l’est pas car on peut
aller de 4 vers 5 par exemple.

Exercice 2. On considère le jeu suivant: On pose une question à un joueur, avec probabilité p ∈ (0, 1), il donne
la bonne réponse et gagne $1 dollar, avec probabilité 1 − p, il donne la mauvaise réponse et perd toute sa fortune.
On suppose que les questions (et les réponses) sont toutes indépendantes entre elles. On dénote Xn sa fortune au
temps n et on suppose que X0 = 0.
1. Montrer que (Xn )n⩾0 est une chaîne de Markov, dessiner son graphe et donner sa matrice de transition.

Solution. On remarque que l’on peut écrire avec Rn la réponse au temps n + 1 qui est à valeurs dans {R, T }
pour raison ou tort,
Xn+1 = (Xn + 1)1Rn+1 =R .
Ainsi par le TP 2, on sait que c’est une chaîne de Markov car les Rn sont des variables indépendantes. Son
graphe est
 p p p p p
0 1 2 3 4 ···
1−p
1−p
1−p
1−p

2. Montrer que c’est une chaîne irréductible.

Solution. On remarque que l’on a un chemin entre 0 et n’importe quel entier, en passant par tous les entiers
intermédiaires, de plus tous les entiers sont reliés à 0, donc pour tout i, j ∈ N, nous avons i ↔ j.

3. Soit T0 = minn⩾1 {Xn = 0}. Calculer P (T0 = n|X0 = 0).

Solution. Le seul chemin pour atteindre pour la première fois 0 au temps n est d’aller de 0 ‘a n − 1 puis de
n − 1 à 0. Ainsi,

P (T0 = n|X0 = 0) = P (Xn = 0, Xn−1 = n − 1, . . . , X2 = 2, X1 = 1|X0 = 0)

= P0,1 P1,2 P2,3 · · · Pn−2,n−1 Pn−1,0
= pn−1 (1 − p).

4. En déduire que 0 est un état récurrent. Que dire des autres états?

Solution. 0 est récurrent veut dire que

P (∃n ⩾ 1, Xn = 0|X0 = 0) = 1.

Or nous avons
∞ ∞
X X 1−p
P (∃n ⩾ 1, Xn = 0|X0 = 0) = P (T0 < ∞|X0 = 0) = P (T0 = n|X0 = 0) = pn−1 (1 − p) = = 1.
n=1 n=1
1−p

Comme tous les autres états communiquent avec 0, nous savons que tous les états sont récurrents.
P∞ (n)
Exercice 3. On définit la fonction de Green G(x, y) = E [nombre de visites en y|X0 = x] = n=0 Pxy .
1. Montrer que si x ↛ y, alors G(x, y) = 0.

(n)
Solution. Si x ↛ y, alors il n’existe pas de chemin entre x et y ce qui veut dire que pour tout n ∈ N, Pxy = 0
et par définition de la fonction de Green, G(x, y) = 0.

2. Montrer que si x → y et y est transient alors G(x, y) < ∞, y est récurrent alors G(x, y) = ∞.
 P∞ (n)
Solution. L’idée est d’utiliser le fait que y est transient si et seulement si n=0 Pyy = G(y, y) < ∞. Pour
ce faire on va conditionner sur notre premier passage à y puis sur le reste de la chaîne. Par définition, nous
avons
∞
X
(n)
G(x, y) = δxy + Pxy
n=1
X∞
= δxy + P (Xn = y|X0 = x)
n=1
X∞ Xn
= δxy + P (Xn = y et la première visite en y est au temps ℓ |X0 = x)
n=1 ℓ=1
X∞ X n
= δxy + P (Txy = ℓ) P (Xn = y|X0 = x, Txy = ℓ)
n=1 ℓ=1
X∞ X ∞
= δxy + P (Txy = ℓ) P (Xn = y|Xℓ = y)
ℓ=1 n=ℓ
X∞ ∞
X
(n−ℓ)
= δxy + P (Txy = ℓ) Pyy
ℓ=1 n=ℓ
∞
X
(n)
= δxy + P (Txy < ∞) Pyy .
n=0

(n)
Dans la première égalité, on a utilisé le fait que P (0) = Id, ensuite nous avons utilisé la définition de Pxy , nous
avons ensuite utilisé la formule des probabilités totales sur la première visite au site y ainsi que la formule
de Bayes où nous avons utilisé la notation Txy pour le temps de la première visite en y depuis x. Dans la
cinquième égalité nous avons utilisé la propriété de Markov pour voir que seulement le “présent” i.e. Xℓ est
important dans le conditionnement. Enfin nous avons utilisé la définition de P (n) ainsi qu’un changement
d’indice pour finir.

3. Montrer que la fonction de Green satisfait: G = P G + Id.

Solution. Nous avons

∞ ∞ ∞ X
∞ ∞
(n−1) (n)
X X X X X
(n) (n)
G(x, y) = Pxy = δxy + Pxy = δxy + Pxℓ Pℓy = δxy + Pxℓ Pℓy
n=0 n=1 n=1 ℓ=0 ℓ∈S n=0
∞
(n)
X X
= δxy + Pxℓ Pℓy
ℓ∈S n=0
X
= δxy + Pxℓ G(ℓ, y)
ℓ∈S
= (Id + P G)xy .

4. Prenons la chaîne de Markov  

0 1 0
P =  12 1
0
 
2
1 1 1
3 3 3
Dessiner le graphe de la chaîne et classifier les états.
 Solution. On dessine le graphe avec les probabilités sur chaque arête.

1
2

1
1 2
1
2
1 1
3 3
3

1
3

On remarque qu’on a les classes d’équivalence {0, 1} et {2}. Tous les états sont de période 1. 0 et 1 sont
récurrents car P11 > 0 et 0 ↔ 1. 2 est transient car nous avons par exemple P20 > 0 mais 0 ↛ 2.

5. Calculer la fonction de Green, en déduire la probabilité de ne jamais revenir en 3 sachant que l’on est parti
de 3.

Solution. On voit par les questions précédentes que

 
∞ ∞ 0
G = ∞ ∞ 0 
∞ ∞ G(3, 3)

Pour le dernier coefficient, on utilise la formule qui nous donne que

1 3
G(3, 3) = 1 + (P G)33 = 1 + G(3, 3) ⇐⇒ G(3, 3) = .
3 2

Dans l’égalité que nous avons trouvé dans la première question nous avons
1 1
G(3, 3) = 1 + P (T33 < ∞) G(3, 3) ⇐⇒ G(3, 3) = =
1 − P (T33 < ∞) P (T33 = ∞)

Ainsi nous avons

1 2
P (T33 = ∞) = = .
G(3, 3) 3

Exercice 4. Soit X = (Xn )n⩾0 une chaîne de Markov de matrice de transition P . Montrer que X est une chaîne
de Markov irréductible si et seulement si il n’existe pas de sous-ensemble strict non vide A ⊂ S tel que

∀x ∈ A, ∀y ∈ S \ A, P (x, y) = 0.

Solution. Soit X une chaîne irréductible, on va supposer l’existence d’un tel ensemble A ⊂ S tel que ∀x ∈ A, ∀y ∈
S \ A, P (x, y) = 0. Soit x ∈ A et y ∈ S \ A, alors comme la chaîne est irréductible, il existe un chemin entre x et
y que l’on dénote x1 , . . . , xn−1 . En particulier nous avons que P (xi , xi+1 ) > 0 pour tout i ∈ {0, . . . , n − 1} avec
x0 = x et xn = y.
Maintenant soit K = min{i ∈ {0, . . . , n − 1}, xi ∈ A et xi+1 ∈ S \ A}. Alors par définition nous avons
P (xK , xK+1 ) > 0 mais par hypothèse nous devons avoir P (xK , xK+1 ) = 0. Contradiction !
 Pour l’autre sens, on suppose qu’il n’existe pas de tel sous-ensemble strict, on va montrer que la chaîne irré-
ductible. Soit x ∈ S, on définit
Sx = {y ∈ S, x → y}.
On va montrer que Sx = S, ceci étant vrai pour tout x ∈ S, nous avons une unique classe d’équivalence et la chaîne
est donc bien irréductible.
Si Sx ̸= S, alors il existe au moins un y ∈ S \ Sx . Or par hypothèse, nous ne pouvons pas avoir P (x, y) = 0
pour tout z ∈ Sx et y ∈ S \ Sx , donc il existe un z ∈ Sx et un y ∈ S \ Sx tel que P (z, y) > 0 ce qui veut dire que
z → y, mais comme x → z par définition de Sx , nous avons x → y et y ∈ Sx ce qui donne une contradiction. Donc
Sx = S et la chaîne est irréductible.

George Green René Maurice Fréchet

(1793–1841) (1878–1973)