Université d’Angers Année 2008 - 2009

Master 1 MIM Processus stochastique

Série d’exercices N◦ 4
Chaı̂nes de Markov 1

Exercice 1

Soit une chaı̂ne de Markov possédant 5 états notés 1, 2, , 5 et donnée par sa matrice de transition
 
1 0 0 0 0
 0 1/2 1/2 0 0 
 
 1 0 0 0 0 
 
 0 1/2 0 1/2 0 
0 3/4 0 0 1/4

Dessinez le graphe de la chaı̂ne. Quelles sont les composantes connexes de ce graphe ? Qualifiez les
diffrents tats de la chaı̂ne ? L’état initial de la chaı̂ne est l’état 2. Quelle est la distribution des états
au bout d’un intervalle de temps, au bout de deux ? Combien de temps lui faut-il au minimum
pour parvenir dans l’état 1 ? Quelle est la probabilité de cet événement ? Donnez un autre exemple
de transitions d’états qui amènent de l’état 2 l’état 1. Combien de temps en moyenne faut-il pour
atteindre l’état 1 ?

Exercice 2

Soit X0 une v.a. à valeurs dans I. Soit Y1 , Y2 ,... une suite i.i.d. de v.a. uniformément
distribuées sur [0,1]. Soit G : I × [0, 1] → I une fonction à deux variables. On définit la suite
(Xn )n≥0 à l’aide de la relation de récurrence Xn+1 = G(Xn , Yn+1 ). Montrer que (Xn )n≥0 est une
chaı̂ne de Markov. Écrire sa matrice de transition en fonction de G. Peut-on réaliser toute chaı̂ne
de Markov sous cette forme ? En déduire une manière de simuler un chaı̂ne de Markov.

Exercice 3

Une puce saute au hasard sur les sommets d’un triangle. Trouver la probabilit qu’aprs n sauts,
la puce soit retourne au somet d’o elle est partie ?
Une seconde puce saute sur les sommet d’un triangle mais elle a deux fois plus de chance de
sauter dans le sens des aiguilles d’une montre. Trouver la probabilit qu’aprs n sauts, la puce soit
retourne au somet d’o elle est partie ?

Exercice 4

Soit une chaı̂ne de Markov possédant 5 états notés 1, 2,..., 5 et donnée par sa matrice de
transition  
1/2 0 0 0 1/2
 0 1/2 0 1/2 0 
 
 0 0 1 0 0 
 
 0 1/4 1/4 1/4 1/4 
1/2 0 0 0 1/2

1
 Identifier les classes de communiction. Quelles classes sont fermes ? Quels sont les tats rcurrents
et les tats transients ? Quelles sont les probabilits invariantes.

Exercice 5

Trois joueurs A, B et C jouent au jeu suivant: à chaque instant entier n, l’un des joueurs est
”leader”. On tire alors à pile où face et à l’instant n + 1 l’un des deux autres joueurs devient
leader, selon le résultat du tirage. On note Xn le joueur leader à l’instant n. On suppose enfin que
X0 = A, (donc A est leader au début du jeu).

1. Montrer que la suite (Xn )n≥0 est une chaı̂ne de Markov homogène (à valeurs dans l’ensemble
à trois éléments {A, B, C}). Calculer sa matrice de transition et sa loi initiale.

2. Quelles sont la (ou les) probabilités invariantes, (s’il en existe) ?

Exercice 6

Un joueur fréquente 3 casinos numérotés 1, 2 et 3. Chaque jour il choisit l’un des deux casinos
où il n’est pas allé la veille, avec probabilité 12 . Le premier jour, (n = 0), il choisit l’un des trois
casinos avec la loi de probabilité µ sur {1, 2, 3}.
On note Xn la v.a. égale au numéro du casino fréquenté le jour n par le joueur.

1. Montrer que (Xn ) est une chaı̂ne de Markov et calculer sa matrice de transition Q.

2. Calculer Qn , n ≥ 1, puis limn→+∞ Qn .

3. Calculer limn→+∞ Pµ (Xn = j), j = 1, 2, 3.

4. Montrer que si µ = ( 31 , 31 , 31 ) alors (Xn ) est une suite stationnaire.

Exercice 7 Soit (Xn ) une chaı̂ne de Markov dont l’espace d’états est E = {1, 2, 3, 4} et de

matrice de transition :  
0 1 0 0
 1/2 0 1/4 1/4 
Q=
 1/2 1/2 0

0 
0 0 1 0
Montrer que (Xn ) est irréductible, récurrente, positive et calculer sa probabilité invariante.

Exercice 8 Une souris effectue une suite de déplacements aléatoires, indépendants les uns

des autres entre trois pièces numérotées 1, 2 et 3. La règle des déplacements est alors la suivante :
1
· Lorsque la souris est dans la pièce 1, elle y reste avec la probabilité 3 ou bien passe dans l’une
des deux autres pièces suivant la même probabilié 31 .
1
· Lorsque la souris est dans la pièce 2, elle y reste avec la probabilité 2 ou passe dans la pièce
3 avec la probabilité 12 .

· Lorsque la souris est dans la pièce 3, elle y reste.

2
On note X0 le numéro de la pièce initialement occupée par la souris, (X0 peut être aléatoire), Xn ,
n ≥ 1, le numéro de la pièce occupée par la souris après son n-ième déplacement.

1. Justifier que Xn est une chaı̂ne de Markov à valeurs {1, 2, 3} et donner sa matrice de transition
Q.

2. Diagonaliser Q.

3. En déduire les limites des P (Xn = j), 1 ≤ j ≤ 3, quand n → +∞.

4. On pose τ = inf{n ≥ 0 : Xn = 3}. Montrer que P (τ < +∞) = 1.

Exercice 9 Une chaı̂ne de Markov à valeurs dans {0, 1} a toujours une matrice de transition

de la forme  
1−p p
M=
q 1−q
1) Décrire la chaı̂ne dans le cas où p = q = 0 puis dans le cas où p = q = 1. On supposera par la
suite que (p, q) 6= (0, 0).
2) Calculer M n .
3) Montrer qu’il y a une seule probabilité invariante µ = (µ0 , µ1 ). Calculer µ0 et µ1 .
4) Vérifier que
lim M n (0, 0) = lim M n (1, 0) = µ0 ,
n→+∞ n→+∞
et que
lim M n (0, 1) = lim M n (1, 1) = µ1 .
n→+∞ n→+∞

5) On suppose que (p, q) 6= (1, 1). Soit Nn (i, j) le nombre moyen de passages en j partant de i
pendant les n premiers pas. Montrer que
Nn (i, j)
lim = µj .
n→+∞ n

Exercice 10 Soient d balles (d > 1) numérotées de 1 à d, réparties dans deux urnes A et B.

On tire un nombre i au hasard entre 1 et d et la balle numérotée i est changée d’urne. Soit Xn le
nombre de balles dans l’urne A après n tirages indépendants. On note Φn la fonction génératrice
de Xn .

1) Montrer que (Xn ) définit une chaı̂ne de Markov homogène. Déterminer sa matrice de transition,
M.
2) Si X0 suit une loi binomiale de paramètres d et 1/2, déterminer la loi de X1 . Qu’en déduit-on ?
3) Calculer directement la probabilité stationnaire, µ.
4) Montrer que pour tout s ∈ [0, 1],

1 − s2 0
Φn+1 (s) = sΦn (s) + Φn (s) .
d
5) On suppose que d = 3. Soit T0 le nombre de tirages nécessaires pour vider A.
a) Déterminer, pour tout état x et pour tout n = 1, 2 ou 3, P (T0 = n | X0 = x).
b) Calculer M et M 2 . Si la loi initiale de la chaı̂ne est : µ0 = (1/4, 1/4, 1/4, 1/4), calculer les
lois µ1 et µ2 de X1 et X2 .

3
 Exercice 11 Soit (Xn )n≥0 une chaı̂ne de Markov de matrice de transition sur l’espace d’états

{0, 1, 2, 3} :  
0 1 0 0
 1/3 0 2/3 0 
M = 
 0 2/3 0 1/3 
0 0 1 0
Monter que cette chaı̂ne est irréductible. Déterminer sa période. Calculer les valeurs propres, la
limite de M n quand n → +∞. Rechercher le probabilité invariante. Conclusion.

Exercice 12 Soit (Xn )n≥0 une chaı̂ne de Markov de matrice de transition sur l’espace d’états

{0, 1, 2, 3} :  
1/2 1/2 0 0
 1/6 1/2 1/3 0 
M =
 0 1/3 1/2 1/6  .


0 0 1/2 1/2
Montrer que (Xn ) est irréductible et déterminer sa période.
2) Vérifier que les valeurs propres sont 1/3, 2/3, 0 et 1.

Exercice 13 Soit (Xn )n≥0 une chaı̂ne de Markov de matrice de transition sur l’espace d’état

{0, 1, 2, 3, 4} :  
0 1/3 2/3 0 0

 0 0 0 1/4 3/4 

M =
 0 0 0 1/4 3/4 
.
 1 0 0 0 0 
1 0 0 0 0
1) Monter qu’elle est irréductible.
2) Déterminer la probabilité invariante.
3) Trouver la période. Etudier M n .

Exercice 14 1) Soit (Xn )n≥0 une chaı̂ne de Markov sur un espace I fini de matrice de
P P
transition Q bistochastique, c’est à dire que i Q(i, j) = 1 pour tout j ∈ I et j Q(i, j) = 1 pour
tout i ∈ I. Prouver que la mesure πi = 1/|I| pour tout i ∈ I est la mesure invariante.
2) Une particule se déplace entre les 8 sommets d’un cube le long de ses arêtes : à chaque instant,
en partant d’un sommet, elle choisit une des 3 arêtes adjacentes avec la probabilité 1/3. Soit i le
sommet initial occupé par la particule, j le sommet opposé à i. Calculer le temps moyen de retour
dans i et le temps moyen passé dans j avant de rentrer dans i.

Exercice 15 Ruine du joueur On considère un chaı̂ne de Markov (Xn )n≥0 sur N avec p0,1 = 1,

pi,i+1 = pi , pi,i−1 = qi , pi + qi = 1, pour i = 1, 2, . . . .

4
1) Calculer la probabilité h0i d’atteindre 0 à partir de l’état i.
2) Soit Hj = inf{n ≥ 0 : Xn = j}. On pose φ(s) = E1 (sH0 ). En utilisant la propriété de Markov
forte, calculer φ(s). En déduire la loi de la v.a. H0 sous P1 puis E1 (H0 ).

Exercice 16 Soit (Xn )n≥1 une chaı̂ne de Markov de matrice de transition M et d’espace

d’états E. Pour x ∈ E on définit la période de x comme : pgcd {n ≥ 1 : M n (x, x) > 0}. On la note
dx .

1)Montrer que si x et y communiquent alors dx = dy .

2) Si la chaı̂ne (Xn ) est irréductible, tous les états ont la même période d’après 1), et on parle
alors de la période de la chaı̂ne. Montrer que si (Xn ) est irréductible et s’il existe x ∈ E tel que
P (x, x) > 0, alors (Xn ) est de période 1 (on dit alors que (Xn ) est apériodique).

Exercice 17 On rappelle qu’un état x d’une chaı̂ne de Markov (Xn )n≥0 est dit récurrent si

P (Tx < ∞ | X0 = x) = 1, où Tx = min {n > 0 : Xn = x}. Le but de cet exercice est de montrer
qu’une chaı̂ne de Markov dont l’espace d’états est fini possède au moins un point récurrent.

1) Soit b un état. Soient N (b) = ∞

P
n=1 1I{b} (Xn ), F (a, b) = E(N (b) | X0 = a), G(b, b) = P (Tb <
∞ | X0 = b). Supposons b transient, c’est à dire G(b, b) < 1. Montrer que P (N (b) = m | X0 = a) =
F (a, b)G(b, b)m−1 (1 − G(b, b)).
2) Déduire de ce qui précède que si b est transient alors F (a, b) < ∞ pour tout a ∈ E et
limn→∞ F n (a, b) = 0.
3) Conclure que l’espace d’états est fini en considérant a∈E F n (a, b).
P