Feuille d’Exercices V

Processus Stochastiques

Exercice 1. On considère la chaîne de Markov de l’Exercice 2 de la Feuille III, qui nous fait gagner $1 avec
probabilité p et nous fait tout perdre avec probabilité 1 − p.

1. Trouver une probabilité stationnaire pour cette chaîne de Markov.

Solution. On essaye de résoudre le système πP = π avec

 
1−p p 0 ···
P = 1 − p 0 p · · ·

.. .. ..

..
. . . .

ce qui donne les équations ( P∞

i=0 πi (1 − p) = π0 ,
πi−1 p = πi pour i ⩾ 1.
P∞
La première équation nous donne π0 = 1 − p puisque que l’on a i=0 πi = 1. La deuxième équation nous
donne
πi = πi−1 p = πi−2 p2 = π0 pi = (1 − p)pi .
On remarque que cela est une loi géométrique de paramètre 1 − p.

2. En déduire ainsi que la chaîne est récurrente positive et donner le temps moyen de retour en 0 sachant que
la chaîne est partie de 0.

Solution. On sait que la chaîne est irréductible et admet une distribution stationnaire π ainsi on sait que
1
πi = .
E [Ti |X0 = i]

Puisque πi calculée en 1 est strictement positive pour tout i ∈ N, nous obtenons que pour tout i ∈ N,
E [Ti |X0 = i] < ∞ ou encore i est un état récurrent positif. De plus nous avons
1 1
E [T0 |X0 = 0] = = .
π0 1−p

3. Retrouver ces résultats directement avec les réponses à l’Exercice III.2.

Solution. On avait montré que la chaîne était irréductible et récurrente. De plus, nous avions calculé

P (T0 = n|X0 = 0) = pn−1 (1 − p)

et ainsi
∞ ∞ ∞
!
X X
n−1 d X n
E [T0 |X0 = 0] = nP (T0 = 0|X0 = 0) = (1 − p) np = (1 − p) x
n=1 n=1
dx n=1
|x=p
 
d 1
= (1 − p)
dx 1 − x |x=p
1−p 1
= 2
= .
(1 − p) 1−p
Exercice 2. On considère la chaîne de Markov donnée par le modèle d’Ehrenfest dans le cas général avec N
particules en total.
1. Déterminer une distribution réversible pour cette chaîne et en déduire la probabilité stationnaire.

Solution. On rappelle la matrice de transition

 
0 1 0 0 ... 0
1 N −1 
N 0 N 0 ... 0
 
N −2
0 N2 0 ... 0
 
P =  N 
. .. .. .. .. .. 
 .. . . . . .
 
0 0 0 ... 1 0

On cherche une distribution qui suit la règle πi Pij = πj Pji ce qui donne léquation

i N −i
πi Pi,i−1 = πi−1 Pi−1,i ⇐⇒ πi = πi−1 .
N N
En continuant la rećurrence on obtient
 
N −i (N − i)(N − i − 1) (N − i)(N − i + 1) . . . N N! N
πi = πi−1 = πi−2 = π0 = π0 = π0 .
i i(i − 1) i(i − 1) . . . 1 (N − i)!i! i

On peut retrouver π0 avec la condition d’être une distribution

N N  
X X N 1
1= πi = π0 = 2N π0 ⇐⇒ π0 = N .
i=0 i=1
i 2

Enfin, on obtient la distribution réversible

 
1 N
πi = N .
2 i

Comme l’on sait qu’une probabilité réversible est une distribution réversible, π est une distribution station-
naire. On remarque que c’est une distribution binomiale de paramètre (N, 21 ).

2. On suppose que l’on commence avec X0 = N2 (il y a la moitié des particules dans chaque compartiment).
Calculer le temps moyen pour revenir à cet état. Même question pour X0 = N (toutes les particules sont
dans un seul compartiment). Évaluer ces temps moyens pour N = 12.

Solution. Comme on a une chaîne de Markov irréductible qui admet une distribution stationnaire π, on sait
que
1
πi = .
E [Ti |X0 = i]
Ainsi, nous avons
2N
 
N 1
E T N X0 = = = N
.
2 2 πN N
2 2

Pour N = 12, on obtient  

N 4096
E T N X0 = = ≈ 4, 43.
2 2 924
 Et nous avons
1
E [TN |X0 = N ] = = 2N .
πN
Et pour N = 12, nous avons
E [TN |X0 = N ] = 4096.

Exercice 3. Un graphe sans boucle G = (V, E) est un ensemble fini de sommets V et de paires de sommets
(u, v) ∈ V 2 avec u ̸= v. On dit que {u, v} ∈ E est une arête du graphe. Le degré d’un sommet du graphe est donné
par
deg(u) = #{v ∈ V, {u, v} ∈ E}.
On définit la chaîne de Markov sur V donnée par la matrice de transition
 1
deg(u) si {u, v} ∈ E,
Puv =
0 sinon.

1. Sous quelles conditions sur le graphe G la matrice est-elle irréductible ? Même question pour apériodique.

Solution. La chaîne de Markov est irréductible si tous les états communiquent ainsi s’il existe un chemin dans
le graphe qui relie tous les états i et j. On dit que le graphe est connexe.
Pour l’apériodicité, on remarque que puisque le graphe n’est pas orienté, on a que si Pij > 0 alors Pji > 0 et
ainsi
Pii2 ⩾ Pij Pji > 0.
Ainsi, on a toujours un chemin de longueur 2 pour aller de i à i. Nous devons donc avoir un chemin de
longueur impair dans le graphe pour avoir une période de 1 pour létat i. Le rgaphe G est donc apériodique
s’il contient un cycle de longueur impair.
P
2. Expliquer pourquoi u∈V deg(u) = 2#E.

Solution. Comme le graphe est sans boucle, pour chaque sommet, le degré est le nombre d’arêtes qui lui est
connecté. Ainsi si on somme cela sur tous les sommets du graphe, on obtient toutes les arêtes comptées deux
fois puisque chaque arête est reliée à deux sommets.

3. On suppose que la chaîne est irréductible, trouver une probabilité réversible pour cette chaîne de Markov.

Solution. On cherche un distribution qui suit les règles πi Pij = πj Pji et ainsi si u est connecté à v,
πu πv
= .
deg(u) deg(v)
πx
On remarque donc que la fonction ϕ(x) = deg(x) est constante égale à C par exemple. Ainsi cela nous donne
que πx = Cdeg(x). Maintenant, nous pouvons utiliser le fait que l’on a une distribution et on obtient
X X
1= πu = C deg(u) = C2#E.
u∈V u∈V

Ainsi, nous obtenons la distribution réversible et donc stationnaire

deg(u) deg(u)
πu = =P .
2#E v∈V deg(v)
 x

4. On considère maintenant un cavalier sur un échiquer, c’est une pièce qui bouge de la façon suivante Donner
les degrés de chaque carrés de l’échiquier.

Solution. On obtient le tableau suivant des degrés

 
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
 
4 6 8 8 8 8 6 4
 
4 6 8 8 8 8 6 4
Degré de chaque sommet = 
4

 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
 
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

5. En déduire le temps moyen de retour dans un coin pour un cavalier qui fait une marche aléatoire sur l’échiquier
avec la matrice de transition P .

Solution. On a déjà calculé la distribution stationnaire π ainsi on sait que

P
1 deg(v) 336
E [T0 |X0 = 0] = = v∈V = = 168.
π0 deg(v) 2

Exercice 4. On considère une urne avec N1 balles blanches et N2 balles noires, et avec deux compartiments A et
B contenant respectivement a ⩾ 1 balles et b ⩾ 1 balles ; N1 + N2 = a + b, et chaque compartiment peut contenir
des balles blanches et des balles noires. On note Xn le nombre de balles blanches dans le compartiment A au temps
n; c’est une quantité entière entre max(0, a − N2 ) et min(N1 , a).

1. Donner en fonction de N1 , N2 , a, b, et de Xn le nombre de balles blanches ou de balles noires dans chaque

compartiment au temps n.

Solution. Par définition, nous avons le nombre de balles blanches au temps n dans le compartiment A qui
est Xn . Ainsi le nombre de balles blanches au temps n dans le compartiment B est N1 − Xn . Le nombre de
balles noires au temps n dans le compartiment A est a − Xn . Le nombre de balles noires au temps n dans le
compartiment B est b − N1 + Xn .

2. L’évolution de la chaîne est donnée de la façon suivante. Pour passer de Xn à Xn+1 :

 - On tire au hasard dans chaque compartiment une balle ; toutes les balles du compartiment A ou du
compartiment B sont équiprobables.
- On échange la position des deux balles tirées au hasard : celle du compartiment A va en B et vice-versa.
Donner la matrice de transition P de (Xn )n⩾0 . Donner l’espace d’états et montrer que la chaîne est irré-
ductible.

Solution. On voit que si Xn = n alors on a

P (Xn+1 = j|Xn = n)

n(N1 −n)+(a−n)(b−N1 +n)


 ab si j = n (deux boules blanches tirées ou deux boules noires tirées),

 (a−n)(N1 −n)

si j = n + 1 (une boule blanche tirée en B et une noire tirée en A),
ab
=
n(b−N1 +n)



 ab si j = n − 1 (une boule noire tirée en B et une blanche tirée en A),

0 sinon.


L’espace d’état est [[max(0, a − N2 ), min(N1 , a)]] (notation pour les entiers entre ces bornes). En effet, dans le
compartiment A on a a balles en total. Soit on a pas de balles blanches mais si il y a moins de balles noires
que la taille du compartiment, a − N2 > 0, alors on doit forcément remplir le reste avec des balles blanches.
De même au maximum il y a N1 balles blanches mais si cela rempli complètement le compartiment A alors
on ne peut qu’avoir au maximum a balles blanches.
On remarque que pour tout i et j dans l’espace d’état, on peut toujours soit augmenter ou diminuer
d’incrément de un en un et il y a donc un chemin entre ces entiers et la chaîne est irréductible.

3. On suppose que N1 ⩽ a ⩽ N2 . Trouver l’unique distribution stationnaire π pour P . Quelle mesure de

probabilité obtenons-nous ?

Proof. Solution Cherchons une mesure réversible, tout d’abord nous avons
P0,1 N1 ab N1
π1 = π0 = · π0 = a π0 .
P1,0 b b − N1 + 1 b − N1 + 1

De même, nous avons

P1,2 (a − 1)(N1 − 1) ab a(a − 1) N1 − 1

π2 = π1 = · π1 = · π1
P2,1 ab 2(b − N1 + 2) 2 b − N1 + 2
a(a − 1) N1 (N1 − 1)
= · π0 .
2 (b − N1 + 1)(b − N1 + 2)

Et on obtient par récurrence,

a(a − 1) · · · (a − k + 1) N1 (N1 − 1) · · · (N1 − k + 1)

πk = · π0
2 · 3···k (b − N1 + 1) · · · (b − N1 + k)
 
a N1 !(b − N1 )!
= π0
k (N1 − k)!(b − N1 + k)!
  b

a N1 −k
= b

π0 .
k N 1
 PN1
On obtient alors la valeur de π0 avec la condition i=0 πi = 1 qui nous donne
N1   a+b b



1 X a b N1 N1
1 = π0 b
= π0 b
⇐⇒ π0 = a+b

.
N1 − i



N1 i=0
i N1 N1

Finalement, cela nous donne

a b



k N1 −k
πk = a+b

.
N1
a
C’est une loi hypergéométrique de paramètres (N1 , a+b , a + b).

Exercice 5. Plus difficile. Soit P un polygone convexe avec au moins 3 côtés. On applique l’opération suivante:
on choisit uniformément au hasard deux côtés de P puis on joint les milieux de ces côtés, on garde ensuite l’un des
deux nouveaux polygones convexes que cela créer. On continue alors cette opération sur le nouveau polygone et on
note (Cn )n∈N la suite des nombres de côtés des polygones ainsi obtenus. On commence avec C0 = 3 et on admet
que cela donne une chaîne de Markov.

Figure 1: Dans cet exemple, nous avons C = (3, 4, 4, 5, . . . ).

1. Si Cn = k, montrer que Cn+1 = {3, 4, . . . , k + 1}. Montrer que C est irréductible sur l’espace d’état
{3, 4, 5, . . . }.

Solution. Si Cn = k, le polygone a k côtés que l’on numérote de 1 à k dans l’ordre. Dans cette discussion
nous supposons que l’on choisit le côté 1. Alors si le deuxième est le côté 2, nous créons un triangle et un
polygone à k + 1 côtés, dans le même raisonnement, choisir un côté j nous donnera un polygone de côté j + 1
et un polygone de côté k + 3 − j. Ainsi, on voit que l’on peut obtenir un polygone de côtés n allant de 3
à k + 1. Le même raisonnement nous donne bien que la chaîne est irréductible puisque tous les états sont
connectés à 3 qui est lui-même connecté à tous les autres états simplement en incrémentant le nombre de
côtés.

2. Soit Xn = Cn − 3. On admet que X est une chaîne de Markov, donner sa matrice de transition Q.

Solution. L’espace des états est maintenant l’ensemble des entiers naturels (y compris 0). On remarque que
la matrice de transition de la chaîne initiale est donnée par la mesure uniforme c’est-à-dire
( 1
i−1 si j ∈ {3, 4, . . . , k + 1},
Pij = P (Cn+1 = j|Cn = i) =
0 sinon.

Ainsi on obtient que

( 1
i+2 si j + 3 ∈ {3, . . . , k + 4}, ou j ∈ {0, . . . , k + 1}
Qij = Pi+3,j+3 =
0 sinon.

3. On remarque que X0 = 0. Calculer E [Xn |X0 = 0] pour tout n ⩾ 0 par récurrence.

 Solution. Dénotons un = E [Xn |X0 = 0]. Alors nous avons
∞
X
un+1 = E [Xn+1 |X0 = 0] = kP (Xn+1 = k|X0 = 0)
k=0
X∞ X∞
= kP (Xn+1 = k, Xn = j|X0 = 0)
k=0 j=0
∞
X
= kP (Xn+1 = k|Xn = j) P (Xn = j|X0 = 0)
j,k=0
∞ j+1
!
X X k
= P (Xn = j|X0 = 0)
j=0
j+2
k=0
∞
X (j + 1)(j + 2)
= P (Xn = j|X0 = 0)
j=0
2(j + 2)
∞ ∞
1 X 1X
= jP (Xn = j|X0 = 0) + P (Xn = j|X0 = 0)
2 j=0
2 j=0
1 1
= E [Xn |X0 = 0] +
2 2
1 1
= un + .
2 2
On remarque que
1 1 1
(un+1 − 1) = (un − 1) =⇒ un+1 = 1 + n+1 (u0 − 1) = 1 − n+1 .
2 2 2

4. On cherche
P∞une distribution stationnaire pour Q (qui peut-être n’existe pas). On définit la fonction génératrice
G(s) = n=0 π(n)sn . Montrer que si πQ = π alors
∞
X π(k) k+2
(s − 1)G(s) = (s − 1).
k+2
k=0

En dérivant cette équation, trouver la valeur de G.

Solution. On réécrit l’équation πQ = π par

∞
X πj
πn =
j=n−1
j+2

avec la convention π−1 = 0. Ainsi

∞ ∞ ∞ ∞ j+1 ∞
X X X πj n X πj X n X πj sj+2 − 1
G(s) = πn sn = s = s = .
n=0 n=0 j=n−1
j+2 j=0
j + 2 n=0 j=0
j+2 s−1

En multipliant par (s − 1) nous obtenons donc

∞
X πj
(s − 1)G(s) = (sj+2 − 1).
j=0
j + 2
 En dérivant de chaque côté, nous avons
∞
X
(s − 1)G′ (s) + G(s) = πj sj+1 = sG(s) ⇐⇒ G′ (s) = G(s) ⇐⇒ G(s) = λes .
j=0

Comme π est une distribution, nous avons G(1) = 1 et ainsi

G(s) = es−1 .

5. En déduire la distribution stationnaire, reconnait-on cette distribution ?

Solution. Il suffit maintenant de développer cette fonction en série entière, et l’on a

∞ ∞
1 X sn X
G(s) = es−1 = = πn sn .
e n=0 n! n=0

Ce qui nous donne finalement

1
πn =
en!
et π est une loi de Poisson de paramètre 1.

Jacob Bernoulli Pierre-Simon de Laplace

(1655–1705) (1749–1827)