Devoir 4

MM011, télé-enseignement. Université Pierre et Marie Curie, le 21 Novembre 2012.

Ce devoir n’est pas obligatoire. Ceux qui désirent le faire ont jusqu’au lundi 05/12/2012
pour m’envoyer leur copie. Un corrigé vous sera communiqué dans l’envoi 7 (le dernier).

Exercice I. Soit Q = (p(i, j))i,j∈E , une matrice de transition. On suppose que Q est irréductible.
Montrer que Q est réversible ssi les deux conditions suivantes sont vérifiées.
(a) Pour tous i, j ∈ E, on a p(i, j) > 0 ssi p(j, i) > 0.
(b) Pour toute suite finie d’états i0 , i1 , . . . , in = i0 telle que p(i0 , i1 ) . . . p(in−1 , in ) > 0, on a
Y p(ik , ik+1 )
=1.
p(ik+1 , ik )
0≤k<n

Exercice II. Soit G = (S, A), un graphe simple, non-orienté, dénombrable, connexe et sans boucle.
On le munit d’un système de poids C = (Ca ; a ∈ A). On rappelle que 0 < Ca < ∞, pour toute arête
a ∈ A et on suppose que
X
∀s ∈ S , π(s) := C{s,s0 } ∈ ]0, ∞[ .
s0 ∈S:s0 ∼s

On considère une marche aléatoire sur G associée au système de poids C :

Ω ; F ; (Fn )n≥0 ; (Xn )n≥0 ; Q = (p(s, s0 ))s,s0 ∈S ; Pµ , µ ∈ M1 (S)

On rappelle que p(s, s0 ) = C{s,s0 } /π(s) si s ∼ s0 et p(s, s0 ) = 0 sinon. Puisqu’on a supposé G connexe
et que 0 < Ca < ∞, pour toute arête a ∈ A, on voit facilement que Q est irréductible. De plus, on
rappelle que la matrice de transition est réversible et que π est une mesure de réversibilité.
Chemins. On rappelle qu’une suite finie de sommets γ = (s0 , s1 , . . . , sn ) est un chemin dans le graphe
ssi s0 ∼ s1 ∼ . . . ∼ sn . On dit que le chemin γ relie le sommet s0 au sommet sn .
Domaine. On fixe un sous-ensemble D de sommets. On dit que D est un domaine du graphe G ssi D
est connexe, c’est-à-dire que pour toute paire de sommets distincts s et s0 de D, il existe un chemin
γ = (s0 = s, s1 , . . . , sn = s0 ) tels que s1 , . . . , sn ∈ D.
Problème de Dirichlet discret. On fixe un domaine D ⊂ S et pour éviter les trivialités, on suppose que
D est non-vide et distinct de S. On pose Dc = S\D, le complémentaire de D. On fixe g : Dc → R, une
fonction bornée. Le problème de Dirichlet associé à D et g consiste à trouver une fonction f : S → R
qui est Q-harmonique sur D et telle que f (s) = g(s), pour tout s ∈ / D. Autrement dit,

(Q.f )(s) = f (s) pour tout s ∈ D,
f : S → R résout Dirichlet(D, g) ssi
f (s) = g(s) pour tout s ∈ Dc .
On introduit
TDc = inf{n ≥ 0 : Xn ∈ Dc }
avec la convention inf ∅ = ∞, c’est-à-dire que TDc = ∞ ssi pour tout n ≥ 0, Xn ∈ D.

1. On pose
∀s ∈ S, f (s) = Es [g(XTDc )1{TDc <∞} ] .
Montrer que f : S → R est une fonction bien définie et bornée, qui résout le problème de Dirichlet(D, g).

2. Uniquement dans cette question, on suppose que pour tout s ∈ S, on a Ps (TDc < ∞) = 1.

1
 2.a. Montrer que cette hypothèse est vérifiée lorsque Q est récurrente, ou lorsque D est fini.
2.b. Soit f 0 , une solution bornée à Dirichlet(D, g). Montrer que pour tout s ∈ S, sous Ps ,
(f 0 (Xn∧TDc ))n≥0 est une (Fn )n≥0 -martingale bornée.
2.c. Montrer que le problème de Dirichlet(D, g) a une unique solution bornée et que cette solution
est donnée par la formule de la question 1.

3. On suppose que D est infini. On suppose que g est positive. Soit f 0 une solution problème de
Dirichlet (D, g) qui est positive également. Montrer que

∀s ∈ S , Es [g(XTDc )1{TDc <∞} ] ≤ f 0 (s) .

4. On suppose que D est infini. Soit h : S → R. On dit que lim∞ h = 0 dans D si

ε ∈ ]0, ∞[ , #{s ∈ D : |h(s)| > ε} < ∞ .

4.a. Soient f1 et f2 , des solutions à Dirichlet(D, g) telles lim∞ f1 = lim∞ f2 = 0, dans D. On sup-
pose qu’il existe s0 ∈ D tel que f1 (s0 ) < f2 (s0 ). Montrer que f2 −f1 est solution à Dirichlet(D, 0).
4.b. On pose C = {s ∈ S : f2 (s) − f1 (s) = sups0 ∈S f2 (s0 ) − f1 (s0 )}. Montrer que C 6= ∅. Montrer
que C ⊂ D.
4.c. Montrer que si s ∈ C et s0 ∼ s, alors s0 ∈ C. En déduire que C = D et montrer que cela est
absurde.
4.d. Montrer que Dirichlet (D, g) a au plus une solution f telle que lim∞ f = 0 dans D.

5. On considère la marche aléatoire simple dans Zd . On prend D = Zd \{0} et g(0) = 1, le problème de

Dirichlet admet au moins deux solutions bornées distinctes si d ≥ 3. Est-ce le cas lorsque d ∈ {1, 2} ?

Exercice III. Soit G = (S, A) un graphe simple, non-orienté, sans boucle. On rappelle que le graphe
G est connexe ssi toute paire de sommets distincts sont reliés par un chemin.
Longueur d’un chemin. Soit γ = (s0 , s1 , . . . , sn ), un chemin dans le graphe. Sa longueur est n et elle
notée |γ| := n.
Distance de graphe. La distance du graphe G est la fonction d : S × S → R+ donnée par

∀s, s0 ∈ S , d(s, s0 ) = min |γ| ; γ chemin joignant s à s0 } si s 6= s0 et d(s, s) = 0 si s = s0 .



Cycles. Un chemin γ = (s0 , s1 , . . . , sn ) est un cycle ssi

– sa longueur est plus grande ou égale à 3 : |γ| = n ≥ 3 ;
– son point de départ est aussi son point d’arrivée : s0 = sn ;
– il ne se recoupe qu’en son point d’arrivée, c’est-à-dire que s0 , . . . , sn−1 sont des sommets distincts.
Arbre. Un arbre est un graphe connexe et sans cycle.
On suppose que G = (S, A) est un arbre infini. On distingue un sommet r ∈ S que l’on appelle la
racine. On suppose que l’arbre G est à symétrie sphérique, c’est-à-dire qu’il existe une suite (am )m≥1
d’entiers strictement positifs tel que

∀m ≥ 0 , ∀s ∈ S tel que d(r, s) = m, on a deg(s) = am + 1 .

On fixe λ ∈ ]0, ∞[ et on considère la marche aléatoire

Ω ; F ; (Fn )n≥0 ; (Xn )n≥0 ; Q = (p(s, s0 ))s,s0 ; Pµ , µ ∈ M1 (S)

2
associée au système de poids Cλ = (Caλ ; a ∈ A) donnés par C{r,s0 } = 1/a0 , pour tout s0 ∼ r et

λd(r,s) si d(r, s0 ) = d(r, s) + 1,


∀s, s0 ∈ S tels que s ∼ s0 et s 6= r, C{s,s0 } =
λd(r,s)−1 si d(r, s0 ) = d(r, s) − 1.

On voit que si λ < 1 la marche a tendance à de rapprocher de la racine. Comme c’est surtout ce cas
qui est intéressant, on donne à ce modèle le nom de marche nostalgique.

1. Soit s ∈ S. On note m = d(r, s). Calculer p(s, s0 ), pour tout s0 ∈ S, en fonction de am et de λ.

2. On pose Yn = d(r, Xn ), n ≥ 0. Montrer que (Yn )n≥0 est distribué comme un processus de naissance
et de mort irréductible dont on calcule la matrice de transition.

3. Montrer que
– Si n≥1 λn a01...an = ∞, alors la marche nostalgique est récurrente.
P

– Si n≥1 λn a01...an < ∞, alors la marche nostalgique est transiente.

P

(Indication : étudier le lien entre la transience/récurrence de (Yn )n≥0 et de (Xn )n≥0 .)

4. Pour tout n ≥ 0, on pose Ln = #{s ∈ S : d(r, s) = n} et

1
λ∗ = ,
lim inf n→∞ (Ln )1/n

avec la convention que 1/∞ = 0. Montrer que pour tout λ < λ∗ , la marche nostalgique est récurrente.
Montrer que pour tout λ > λ∗ , la marche nostalgique est transiente. On suppose que λ = λ∗ > 0.
Dans ce cas, trouver des exemples pour lesquels la marche nostalgique est récurrente et des exemples
pour lesquels elle est transiente.

Exercice IV. On note chaque jour la quantité d’argent liquide présent dans les coffres d’une banque
à son ouverture. Cette quantité évolue de la manière suivante.
– A la fin d’une journée, ou bien 1 kilo-euro a été déposé par les clients avec probabilité 1/2, ou
bien 1 kilo-euro a été retiré avec probabilité 1/2.
– Si à la fin de la journée, il n’y a plus d’argent liquide dans les coffres, le banquier appelle une
compagnie de transport de fonds qui, durant la nuit, apporte s kilo-euros (ici, s ≥ 3). La banque
ouvre le lendemain avec s kilo-euros d’argent liquide dans ses coffres.
– Garder de l’argent sous forme liquide est coûteux, car il n’est pas investi. C’est pour cette raison
qu’à la fin d’une journée, s’il y a S kilo-euros (ici, S ≥ s + 3), le banquier appelle une compagnie
de transport de fonds qui, durant la nuit, emporte S − s kilo-euros et les apporte à la maison-
mère (qui place cet argent) : la banque ouvre le lendemain avec s kilo-euros d’argent liquide
dans ses coffres.
On note Xn la quantité d’argent liquide à l’ouverture de la banque au n-ième jour.

1. Expliquer pourquoi (Xn )n≥0 est une chaîne de Markov dont l’espace d’états est {1, . . . , S − 1} et
dont la matrice de transition est donnée par p(i, i + 1) = p(i, i − 1) = 1/2, pour tout 2 ≤ i ≤ S − 2 et

p(1, 2) = p(1, s) = p(S − 1, S − 2) = p(S − 1, s) = 1/2 .

2. Montrer que la chaîne est irréductible. Calculer sa période en fonction de la parité de s et de S.

3. Calculer sa probabilité invariante, qui est notée π (attention : elle n’est pas réversible).

3
4. On pose Yn = (Xn , Xn+1 ), n ∈ N. Montrer que (Yn )n≥0 est une chaîne de Markov dont on précise
l’espace d’états et la matrice de transition. Montrer que c’est une chaîne irréductible et calculer sa
probabilité invariante.

5. Chaque kilo-euro immobilisé en liquide pendant une journée à la banque coûte r euros par jour.
Par ailleurs la compagnie de transport de fonds facture c euros par kilo-euro transporté. On note Cn
le coût pour la banque de sa gestion de l’argent liquide du matin du jour 0 au matin du jour n + 1.
Montrer qu’il existe une fonction C(s, S, r, c) telle que

P-p.s. lim Cn /n = C(s, S, r, c) .

n

Exercice V. Soit E un espace d’états fini. On suppose que Q = (p(i, j))i,j∈E est une matrice de
transition qui est réversible

1. Montrer qu’il existe une mesure de probabilité π telle que π(i) > 0, pour tout i ∈ E et telle que
π(i)p(i, j) = π(j)p(j, i), pour tous i, j ∈ E.

2. On rappelle que les fonctions de E dans R sont vues comme des vecteurs colonne et que les mesures
sur E sont vues comme des vecteurs ligne. On introduit pour toutes fonctions f et g : E → R, la
quantité X
(f, g)π = f (i)g(i)π(i) .
i∈E

2.a. Montrer que ( · , · )π est un produit scalaire sur l’espace vectoriel des fonctions de E dans R
(qui est un R-espace vectoriel de dimension #E).
2.b. Montrer que Q est une matrice diagonalisable dans R et que ses valeurs propres sont réelles
à valeurs dans [−1, 1].
2.c. Montrer que 1 est valeur propre associée la fonction constante égale à 1, fonction notée f1 .

3. On indexe les valeurs propres (avec répétitions possibles) de façon décroissante :

1 = β1 ≥ β2 ≥ . . . ≥ β#E ≥ −1 .

3.a. Montrer que si Q est irréductible alors 1 est valeur propre simple et que l’on a

1 = β1 > β2 ≥ . . . ≥ β#E ≥ −1 .

3.b. Montrer que si Q est irréductible et apériodique, alors −1 n’est pas valeur propre et dans ce
cas montrer que
1 = β1 > β2 ≥ . . . ≥ β#E > −1

4. On suppose que Q est irréductible et apériodique. On rappelle que f1 est la fonction constante égale
à 1. Montrer qu’il existe #E − 1, fonctions de E dans R, notées f2 , . . . , f#E telles que d’une part

∀ k, ` ∈ {1, . . . , #E} , (fk , f` )π = 0, si k 6= ` et (fk , fk )π = 1

et d’autre part pour toute fonction f : E → R et pour tout n ∈ N∗ , on ait

X
(Qn .f ) − hπ, f i = βkn (f, fk )π fk .
2≤k≤#E

4
5. On suppose que Q est irréductible et apériodique. On considère la chaîne (globale) (Xn )n≥0 de
matrice de transition Q, avec les notations habituelles. Montrer que pour toute loi d’entrée µ ∈ M1 (E),
il existe une constante C ∈ ]0, ∞[ , (qui ne dépend que de µ et de Q) et une constante ρ ∈ ]0, 1[ (qui
ne dépend que de Q) telles que
X
|Pµ (Xn = i) − π(i)| ≤ Cρn ,
i∈E

ce qui donne une nouvelle preuve de la convergence vers la loi stationnaire dans le cas des chaînes
réversibles, irréductibles et apériodiques sur un espace d’états fini. Observer que la convergence est
rapide.