Les Probabilités du Bonheur, et les Aplications des Processusde Markov et de Levy dans les Mathématiques financières, Files

d’attente et Fiabilité

Master Mathématiques, Modélisation et Simulation

Florin Avram, Université de Pau

1

Table des matières

1 Processus et champs aléatoires 51.1 Les processus de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Châınes de Markov 72.1 L’évolution de la loi de probabilité d’une châıne . . . . . . . . . . . . . . . . 72.2 Probabilités de transition en n étapes . . . . . . . . . . . . . . . . . . . . . . 82.3 Quelques exemples de modélisation par les châınes de Markov . . . . . . . . 92.4 Classification des états . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.5 Le comportement limite des châınes de Markov . . . . . . . . . . . . . . . . 11

2.5.1 Lois invariantes et lois asymptotiques . . . . . . . . . . . . . . . . . . 112.5.2 L’ergodicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.5.3 Le théorème ergodique . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.6 Marches aléatoires et relations de récurrence . . . . . . . . . . . . . . . . . . 142.6.1 Marches aléatoires sur Rd . . . . . . . . . . . . . . . . . . . . . . . . 152.6.2 Moments et cumulants des marches aléatoires . . . . . . . . . . . . . 162.6.3 La méthode du conditionnement sur le premier pas . . . . . . . . . . 172.6.4 La ruine du joueur pour la marche aléatoire simple . . . . . . . . . . 182.6.5 Probabilités du bonheur/fonctions harmoniques . . . . . . . . . . . . 232.6.6 Marches aléatoires sur les graphes : distributions stationnaires . . . . 242.6.7 Les espérances des temps d’atteinte, et les problèmes de Dirichlet non-

homogènes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.6.8 Temps esperés de retour . . . . . . . . . . . . . . . . . . . . . . . . . 272.6.9 Méthode des fonctions génératrices . . . . . . . . . . . . . . . . . . . 312.6.10 Problèmes de premier passage sur un intervalle semi-infini . . . . . . 332.6.11 Les fonctions harmoniques des marches aléatoires de réseau (*) . . . . 342.6.12 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.7 Ou on voit que les probabilités de premier passage interviennent dans le com-portement limite des châınes . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.7.1 Le cas purement absorbant : les probabilités d’absorbtion . . . . . . . 382.7.2 La distribution limite dans le cas faiblement ergodique . . . . . . . . 392.7.3 Echauffement pour le cas general . . . . . . . . . . . . . . . . . . . . 402.7.4 Le comportement limite des châınes, par la decomposition spectrale . 432.7.5 La structure probabiliste de la matrice de distributions a la longue . . 442.7.6 Le calcul de la distribution limite dans le cas général . . . . . . . . . 452.7.7 La périodicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482.7.8 Le théorème de Perron-Frobenius . . . . . . . . . . . . . . . . . . . . 492.7.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2

2.8 Exercices de révision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512.9 Contrôle continu 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572.10 Contrôle continu 2011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3 Programmation 663.1 Scilab et Logiciels symboliques (SAGE et maxima) . . . . . . . . . . . . . . 663.2 Projets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.3 Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

3.3.1 Algèbre et Analyse de base . . . . . . . . . . . . . . . . . . . . . . . . 713.3.2 Pourquoi utiliser des logiciels symboliques . . . . . . . . . . . . . . . 723.3.3 Algèbre linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4 Le processus de Poisson 774.1 La distribution de Poisson et exponentielle . . . . . . . . . . . . . . . . . . . 774.2 Le processus de Poisson multidimensionel . . . . . . . . . . . . . . . . . . . . 794.3 Processus de comptage et renouvellement en temps continu . . . . . . . . . . 804.4 Le processus de Poisson unidimensionel . . . . . . . . . . . . . . . . . . . . . 814.5 Le processus de Poisson comme limite des processus de Bernoulli . . . . . . . 834.6 Le processus de Poisson composé . . . . . . . . . . . . . . . . . . . . . . . . 834.7 La propriété de Markov du processus de Poisson composé . . . . . . . . . . . 854.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

5 Les processus markoviens de saut, en temps continu 885.1 La proprietè de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885.2 Les semigroupes de Markov homogènes ; calcul de l’exponentielle des operateurs 895.3 Premier exemple : le processus de Poisson . . . . . . . . . . . . . . . . . . . 925.4 Processus de naissance et de mort, marches aléatoires et files d’attente . . . 935.5 Les files d’attente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945.6 Distribution stationnaire et comportement asymptotique . . . . . . . . . . . 955.7 Ou sautera la sauterelle ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 975.8 Distributions de type phase/matrice exponentielle . . . . . . . . . . . . . . . 995.9 Les distributions de type phase discrètes . . . . . . . . . . . . . . . . . . . . 1025.10 Problèmes de Dirichlet/première passage . . . . . . . . . . . . . . . . . . . . 1045.11 Châınes et processus a espace d’états infini . . . . . . . . . . . . . . . . . . . 1065.12 Récurrence des châınes à espace d’états denombrable . . . . . . . . . . . . . 1065.13 Fiabilité pour les processus semi-markoviens de sauts . . . . . . . . . . . . . 1085.14 Réseaux de Jackson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1095.15 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1095.16 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

6 Résolution des èquations de Chapman-Kolmogorov (*) 1186.1 Le processus de Poisson ; le calcul de l’exponentielle des matrices triangulaires 1186.2 Résolution des èquations Chapman-Kolmogorov pour le processus de Markov

à deux états . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1206.3 Résolution des èquations de Chapman-Kolmogorov par la méthode de différences

finies de Newton (Putzer) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1206.4 Les probabilités transitoires des processus de naissance et mort . . . . . . . . . . 121

3

7 Processus de Levy : marches aléatoires en temps continu 1257.1 Définition et propriétés de linéarité de processus de Levy . . . . . . . . . . . 1257.2 Exemples de processus de Levy . . . . . . . . . . . . . . . . . . . . . . . . . 126

8 Marche aléatoire infinitesimale, mouvement Brownien et mathématiquesfinancières 1288.1 Le mouvement Brownien standard . . . . . . . . . . . . . . . . . . . . . . . . 1298.2 Problèmes de premier passage de Dirichlet et Poisson . . . . . . . . . . . . . 1308.3 La formule de Black-Scholes pour les options d’achat . . . . . . . . . . . . . 131

9 Laplace, Thiele, Levy et Bachelier 133

10 Qu’est ce qu’il y aura dans l’examen ? 13510.1 Examen d’entrâınement 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13510.2 Examen d’entrainement 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

4

Chapitre 1

Processus et champs aléatoires

Beaucoup de problèmes en physique, biologie, etc, ramène à l’étude des champsaléatoires, qui sont des collections des variables aléatoires Xt, t ∈ I, où l’ensemble desindices I peut-être Nd,Zd,Rd, un ensemble fini, etc. Pour le cas des indices unidimmensio-nels I = N(Z) et I = R on utilise aussi le nom processus stochastiques (à temps discret,respectivement continu).

Définition 1.0.1 Soit I un ensemble quelconque. On appelle processus aléatoire X indexépar I toute famille (Xt)t∈I, de vecteurs aléatoires définis sur un même espace de probabilité(Ω,A, P ) et à valeurs dans d’états E. Celui la peu-être E = Rp, Cp, ou même un espace desfonctions comme E = C[0,∞), C(p)[0,∞), etc.

Note : Lorsque E = Rp et p = 1, une seule valeur est observée à chaque ”instant” t,alors que lorsque p > 1, plusieurs variables sont observées et on parle de processus multidi-mensionnels ou multivariés.

L’espace I est souvent le temps, ainsi :I = N : instants successifs à partir d’un instant initial t0.I = Z : instants successifs avant et après un instant t0.I = R ou R+ : idem mais processus à temps continu.I = Z2 : images.I = Z3 : modèle de la matière.Nous allons considèrer ici seulement des processus à indices unidimmensionels N,Z,R

(les premièrs deux cas étant appellés aussi séries chronologiques en statistique). L’étude estfacilité alors par l’existence d’un ordre complet entre les indices.

Dans le cas des espaces d’états E finis ou dénombrables, les variables Xi, i ∈ I sontappellées discrètes ; pour E = Rd, on parle des variables continues. Le cas discret est le casplus simple, car il permet d’éviter plusieurs details téchniques (par exemple, dans ce cas,l’ensemble des evenements mesurables pour une variable Xi0 est simplement l’ensemble detoutes les parties de E).

Pour modéliser un champs/processus il est necessaire de spécifier de manière consistentel’ensemble de toutes ses distributions jointes d’ordre fini.

Définition 1.0.2 Soit X. = Xt, t ∈ I un champs aléatoire et soit J ⊂ I un sous ensemblefini. On dénotera par XJ la distribution jointe des variables Xt, t ∈ J . L’ensemble XJ : J ⊂I, |J |

Les processus à variables Xt indépendants sont simples à utiliser, mais peut-être tropsimples pour modéliser des phénomènes intéressants. dans ce cas, les distributions jointessont simplement des produits.

Le prochâıne degré de complexité est donné par les processus Markoviens. Ils incluentles marches aléatoires Sn =

∑ni=1 Zi, Zii.i.d., mais cette famille est aussi une trasformation

simple des processus à variables indépendants, et ça simplifie son étude (par exemple ladémonstration du CLT).

La classe des processus Markoviens est extremement riche, avec une complexité quidepend des ensembles E , I.

1.1 Les processus de Markov

Définition 1.1.1 -Proprietè de MarkovUn processus X = (Xt)t≥0, avec t unidimmensionel a la proprietè de Markov si, et

seulement si ses probabilités conditionelles ne depend pas du passé que par le passé imediat,i.e.∀ 0 ≤ t0 < t1 < · · · < tk < t , ti ∈ R, et ∀ ei0 , ei1 , ..., eik , ei ∈ E

P ([Xt ∈ A] | [Xt0 = ei0 , ..., Xtk = eik ]) = P ([Xt ∈ A] | [Xtk = eik ])

Interprétation de la propriété de Markov : si on considère que le processus est indicé parle temps, cette propriété traduit le fait que le présent ne dépend du passé qu’à travers lepassé immédiat.

Un processus ayant la proprietè de Markov s’apelle processus de Markov.Exemples : 2.3 et 2.1 de Ruegg, et les exemples de Belisle.

Définition 1.1.2 Matrice des transitionsPour tous 0 ≤ s ≤ t, pour tous i, j dans I, et pour chaque processus de Markov, on

définit les probabilités de transition par :

pij (s, t) = P ([Xt = ej] | [Xs = ei]) .

Définition 1.1.3 Homogeneité des transitionsUn processus est dit homogène si, et seulement si :

∀ i, j ∈ I , ∀ 0 ≤ s ≤ t , pij (s, t) = pij (0, t− s) .

On note alors pij (s, t)= pij (t− s), et la matrice pij (t) est appellée matrice de transitionaprès temps t.

Hypothèse de travail : (H1) On ne considérera ici que des processus homogènes.

L’exemple le plus simple des processus de Markov homogènes est fourni par les ”châınesde Markov” en temps discret et à espace d’états fini ou dénombrable.

6

Chapitre 2

Châınes de Markov

On considére maintenant le cas des processus Xn observés en temps discret : n =0, 1, 2, ....

La propriété de Markov a lieu quand la loi conditionnelle de Xn sachant (X0, X1, ..., Xn)est la même loi que la loi conditionnelle de Xn sachant Xn−1.

Ces processus sont entièrement characterisés par leur matrice de transition pi,j(1) =P ([Xn = ej] | [Xn−1 = ei]) après temps 1, qu’on denotera par pi,j.

Définition 2.0.4 Une châıne de Markov (Xn)n∈N est dite homogène si :

∀ ei, ej ∈ E , P ([Xn = ej] | [Xn−1 = ei]) ne dépend pas de n.

La matrice P = (pij)i,j∈I , appellée matrice de transition, est la plus importante cha-racteristique d’une châıne. Cette matrice P est une matrice stochastique, c’est-à-dire unematrice telle que :

1. ∀ i, j ∈ I , pij ≥ 0 et2. ∀ i ∈ I ,

∑j∈I

pij = 1 ; la somme des termes de chaque ligne égale à 1. En notation

vectorielle, on a P1 = 1, ou 1 denote un vecteur avec tous les composantes 1.

Rémarque : Même qu’on utilise parfois le terme ”matrice” si E est infini, la theorie dans cecas est un peu differente.

2.1 L’évolution de la loi de probabilité d’une châıne

Définition 2.1.1 Pour tout n de N et tout i de I, on note µi (n) = P [Xn = ei] et µ (n) =(µi (n))i∈I . Le vecteur µ (n) définit une probabilité sur (E,P (E)) appelée loi à l’instant n.On appelle loi initiale de la châıne (Xn)n∈N le vecteur µ (0) .

Exemple 2.1.1 Calculer les distributions µ (1) , µ (2) pour une marche sur le graphe pa-pillon, en sachant que :

a) le départ est surement à 0b) le départ est avec probabilités egales en 0 ou en U, i.e. µ (0) = (1/2, 0, 0, 0, 1/2).

En conditionnant sur la position k un pas en avant, on verifie que µ (1) = µ (0)P, et

µ (n+ 1) = µ (n)P (2.1)

7

O U

A

B

C

Figure 2.1 – Marche aléatoire simple sur le graphe papillon

et alors par induction on trouve

µ (n) = µ (0)P n (2.2)

Exemple 2.1.2 Soit (Xn)n∈N une châıne de Markov homogène sur l’ensemble {1, 2}, dedistribution initiale µ(0) = (µ1, µ2) et de matrice de transition P =

(1− a ab 1− b

)Calculez P{X0 = 2, X1 = 2}, c2(1) = P{X1 = 2}, P{X0 = 2|X1 = 2}, P{X0 = 2, X1 =

2, X2 = 1}, c2(2) et P{X0 = 2, X2 = 1}.

Ce dernier exercice nous sugère la necessité d’étudier la probabilité de transition aprèsn étapes.

2.2 Probabilités de transition en n étapes

Définition 2.2.1 Pour tout n de N , on définit la matrice des probabilités de transition en n étapes,elle est notée P (n) =

(p(n)ij

)i,j∈I

où p(n)ij = P ([Xn = ej] | [X0 = ei]) .

Note : La distribution de X1 en partant de X0 = i, est donné par la ligne i de la matriceP , et la distribution de Xn en partant de Xn−1 = i est donné par la ligne i de la matrice P

n.

Théorème 2.2.1 Les matrices de transition en n étapes ont une structure de semi-group,i.e.

P (m+n) = P (m)P (n) (2.3)

Ce resultat très important s’appelle l’equation de Chapman-Kolmogorov .Démonstration: Soit (Xn)n∈N une châıne de Markov homogène de matrice de transition

P et de loi initiale µ (0), à valeurs dans (E = {ei; i ∈ I} ,P (E)). En conditionnant sur laposition k après m pas, on a :

∀ i, j ∈ I , ∀ m,n ∈ N , p(m+n)ij =∑k∈I

p(m)ik p

(n)kj

QED

8

Corollaire 2.2.1 P (n) = P n , i.e. le semi-groupe des matrices de transition est ”generé”par la matrice P de transition après temps 1.

Demonstration : on montre ça par récurrence sur n, en partant de P (1) = P , et en tenantcompte que P (n+1) = P (n)P (par l’equation de Chapman-Kolmogorov (2.3)).

Rémarque Comme illustré dans les exemple ci-dessus, en utilisant la distribution initaleµ (0) et la matrice de transition P on peut calculer la distribution µ (n) a n’importe queltemps, par exemple µ (1) , µ (2) .... et aussi les distributions jointes pour n’importe quelensemble fini des temps (en utilisant la loi de multiplication des probabilités conditionnelles).En effet, on peut donner une formule explicite pour les distributions jointes d’ordre fini d’unechâıne, en fonction de la matrice de transition P et la distribution initiale µ(0).

Théorème 2.2.2 Pour une châıne de Markov, les distribution jointes sont données pour :∀t0 < t1 < · · · < tk , ti ∈ R, et ∀ ei0 , ei1 , ..., eik ∈ E explicitement par

P [Xt0 = ei0 , ..., Xtk = eik ] = µi0(t0)Pt1−t0i0,i1

...Ptk−tk−1ik,ik−1

(2.4)

Remarque 2.2.1 Il est convenable d’identifier une châıne de Markov avec sa matrice detransition P , qui est l’element principal du ”duo” (P, µ(0)).

Définition 2.2.2 La châıne de Markov associé à une matrice stochastique P est la familledes mesures Pµ(0) définies par (2.4), avec operateurs d’esperance associés Eµ(0) (donc pourobtenir une seule mesure, il faut encore specifiér la mesure initiale µ(0)).

2.3 Quelques exemples de modélisation par les châınesde Markov

Pour modéliser une situation par une châıne de Markov, on a besoin d’abord de choisirun espace d’états convenable tel que la proprieté de Markov est satisfaite, et ensuite dedéterminer la matrice de transitions.

Exemple 2.3.1 Un processus qui n’est pas une châıne de Markov a priori, mais qu’on peut”rendre” Markov par un bon choix de l’espace d’états . Soit (Xn)n∈N un processus à deuxétats, notés e1 et e2. On suppose que les transitions entre les étapes n et n + 1 s’effectuentselon le procédé suivant :{

Si Xn−1 = Xn alors P ([Xn+1 = e1] | [Xn = ei]) = 34Si Xn−1 ̸= Xn alors P ([Xn+1 = e1] | [Xn = ei]) = 12

a) Montrer que (Xn)n∈N n’est pas une châıne de Markov. b) Construire un espace d’étatspermettant de modéliser ce processus par une châıne de Markov et donner alors son graphe.

Solution : b) On construit l’espace d’états suivant : {e1 ∗ e1, e1 ∗ e2, e2 ∗ e1, e2 ∗ e2}. Surcet’espace, le processus devient Markovien, et la matrice de transition s’écrit :

P =

34

14

0 00 0 1

212

12

12

0 00 0 3

414

9

Exemple 2.3.2 Une companie d’assurance voiture a un système de bonus avec

cinq niveaux pour les assurés sans sinistres déclarés :

niveau 1 : 0% réductionniveau 2 : 25%réductionniveau 3 : 40% réductionniveau 4 : 50% réductionniveau 5 : 60% réduction

Pour un assuré, la probabilité de ne pas avoir de sinistre dans un an est de 0.8. Les reglesselon on passe d’un niveau (état)à l’autre sont :

Aprs̀ une année sans sinistre on passe au niveau supérieur suivant ou on reste auniveau 5Aprs̀ une année avec un ou plusieurs sinistres

on diminue d’un niveau si l’année précedente, il n’y a pas eu de déclaration desinistre.on diminue de deux niveaux si l’année précedente il y a eu au moins unedéclaration de sinistre.

1. Notons par X(t) le niveau,soit 1, 2, 3, 4 ou 5, de l’assuré pour l’année t. Expliquezpourquoi {X(t)}∞t=1 n’est pas une châıne de Markov.

2. En augmentant le nombre de niveaux, définissez un nouveau processus stochastique{Y (t)}∞t=1 qui soit Markov et de telle manière que Y (t) représente le niveau de réductionpour l’assuré dans l’année t.

3. Déduire la matrice de transition pour la châıne de Markov {Y (t)}∞t=1.Solution :

1. {X(t)} n’est pas Markov parce que, par exemple, P[Xt+1 = 3 | Xt = 4, Xt−1 = 3, . . .]ne peut pas se réduire à P[Xt+1 = 3 | Xt = 4].

2. Définition des nouveaux niveaux :3=40% réduction cette année, aprs̀ 25% l’année dernière4=50% réduction cette année, aprs̀ 40% l’année dernière

3a=40% réduction cette année, aprs̀ 50% l’année dernière4a=50% réduction cette année, aprs̀ 60% l’ann’ee dernière

3. La matrice de transition est alors1 2 3 4 5 3a 4a

1 0.2 0.8 0 0 0 0 02 0.2 0 0.8 0 0 0 03 0 0.2 0 0.8 0 0 04 0 0 0 0 0.8 0.2 05 0 0 0 0 0.8 0 0.23a 0.2 0 0 0.8 0 0 04a 0 0.2 0 0 0.8 0 0

Exemple 2.3.3 Supposons que une pluie eventuelle demain depend de la situation du tempsdans les trois jours précédents, ainsi : a) S’il y a eu de la pluie dans les deux jours précédents,alors il va pleuvoir avec probabilité .8. b) S’il y a pas eu de la pluie dans aucun des troisjours précédents, alors il va pleuvoir avec probabilité .2. c) Autrement, la situation va etrela meme comme dans le jour precedent avec probabilité .6. Modéliser cette situation par unechâıne de Markov, en donnant l’espace des états et la matrice de transition.

2.4 Classification des états

Définition 2.4.1 Soient ei et ej deux éléments de E. On dit que ei conduit à ej (on note

ei → ej ) ssi il existe n > 0 tel que p(n)ij > 0 et on dit que ei et ej communiquent (et on noteei ↔ ej ) si ei conduit à ej et ej conduit à ei .

10

Rémarque : la relation ” ↔ ” est clairement symétrique, reflexive et transitive. alors,elle partage l’espace d’états dans des classe d’équivalence.

Définition 2.4.2 On appelle classes de la châıne : les classes d’équivalence induites par larelation ”↔ ” sur E.Définition 2.4.3 Une classe d’equivalence dans une châıne de Markov finie qui n’a pas detransitions vers l’exterieur est dite récurente ; les autres classes s’appellent transitoires.

Rémarque : La distinction entre elements transients et recurents a une grande portéesur la valeur des limites limn→∞ P

n(i, j). On verra que pour j transient, elle est toujours 0.

Définition 2.4.4 Le graphe de communication d’une châıne est un graphe sur les états (in-diqués par des points du plan), avec des cotés représentant les transitions possibles (indiquéspar des flèches, avec la valeur de la probabilité de transition notée au dessus).

2.5 Le comportement limite des châınes de Markov

2.5.1 Lois invariantes et lois asymptotiques

Une question très importante pour les châınes de Markov est de déterminer les distribu-tions “asymptotiques/a la longue/limites” d’une châıne specifié par µ(0) et P :

π(∞)µ(0) = π(∞) = limn→∞

µ (n) = limn→∞

µ(0)P n (2.5)

A priori, il pourrait y exister une limite asymptotiques différente (2.5) pour chaquedistribution de départ µ(0). Plus précisement, on pourrait avoir des distributions limitedifférentes π(∞)i pour chaque point de départ sur µ(0) = δi.

Remarque 2.5.1 Comme δiPn est précisement la ligne i de la matrice P n, on trouve par

(2.5) que les limites asymptotiques π(∞)i pour chaque point de départ nonaléatoire possiblei = 1, ..., I sont précisement les lignes de la matrice

P = limn→∞

P n

. On appelera cette matrice la matrice de transition asymptotique. En plus, ces vecteurs deprobabilité sont les points extremaux de l’ensemble des toutes les distributions asymptotiquespossibles.

Alors, la question de l’ergodicité = existence + unicité de la distribution asymptotiquesest equivalente à la question :

Question (ERG) : Est-ce-que la limite matrice P = limn→∞ Pn existe et est-

ce-que elle a des lignes identiques, i.e. est-ce-que on a P = 1π ? (ici 1 denote unvecteur colonne et π un vecteur ligne).

Les reponses aux questions (E),(U) et (ERG) peuvent-être abordées par la structurespectrale (valeurs propres, vecteurs propres) speciale de la matrice P , en utilisant le théorèmede Perron-Frobenius pour les espace d’états finies.

et encore des autres limites données par l’ensemble convexe engendré par π(∞)i, i ∈ E .

Définition 2.5.1 L’ensemble des distributions limite π(∞)µ(0) d’une chaine P, obtenues envariant la distribution initiale µ(0), sera appellé l’ensemble des distributions asympto-tiques.

11

Équations d’équilibre/stationnarité/invariance

Req Remarque 2.5.2 En supposant que la limite (2.5) existe (ce qu’il n’y est pas toujours lecas), on voit par µ(n + 1) = µ(n)P que chacune de cettes distributions “a la longue” doitsatisfaire les équations π(∞) = π(∞)P

Définition 2.5.2 Les équations

π = πP (2.6)

sont appelées équations d’équilibre/stationnarité/invariance, et un vecteur des proba-bilités qui les satisfait est appelé distribution stationnaire ou invariante.

Autrement dit : une distribution stationnaire π est un vecteur de probabilités qui est aussivecteur propre a gauche de P associé à la valeur propre 1.

Remarque 2.5.3 Le nom stationnaire vient du fait que si µ(0) = π, alors on a µ(n) = πpour chaque n.

Par la rémarque (2.5.2), il suit que :

inc0 Corollaire 2.5.1 Les distributions asymptotiques d’une châıne de Markov homogène setrouvent parmi les distributions stationnaires.

Le système d’équilibre (2.6) est donc la clé du calcul des distributions asymptotiques. Deuxquestions fondamentales ici sont celles de l’existence d’au moins une solution, et de l’unicité.

Questions (E-U) : 1) Est-ce que c’est possible qu’il n’existent pas des vecteursdes probabilités qui satisfont le système d’équilibre (2.6) (i.e. est-ce que c’estpossible qu’il n’y ait pas des vecteurs propres pour la valeur propre 1 qui onttoutes les composants nonnégatives) ? 2) Est-ce que c’est possible qu’il existentplusieurs vecteurs des probabilités qui satisfont le système d’équilibre (2.6) ?

Une autre question fondamentale est si dans la presence d’une solution unique dusystème d’équilibre (2.6), elle sera forcement ”attractive”, donc il y aura de la convergencelimn→∞µ(0)P

n = π pour n’importe quel µ(0).Dans la términologie des systêmes dynamiques, cette situation correspond au cas quand

l’équation d’évolution µ(n + 1) = µ(n)P admet un seul point invariant stable, le basind’attraction du quel est tout l’éspace (donc toutes les orbites qui partent de n’importe quelµ(0) convergent vers π). Mais, il y a aussi des situations plus compliquées :

Exemple 2.5.1 L’inexistence de la limite P = limn→∞Pn pour les châınes cy-

cliques. La limite P n’existe pas toujours, comme on voit immediatement en examinantune châıne de Markov qui bouge cycliquement sur les noeuds d’un graphe. Par exemple, pourn = 3, avec la matrice de transition

P =

(0 1 00 0 11 0 0

), on a : P 3n = I3 , P

3n+1 = P et P 3n+2 = P 2 =

(0 0 11 0 00 1 0

).

On voit immediatement que la suite P, P 2, P 3 = I, P 4 = P, ... est cyclique et donc sanslimite.

Ici, la distribution stationnaire π = (1/3, 1/3, 1/3) est unique, mais instable, et toutl’espace se decompose dans des cycles invariants instables d’ordre 3.

12

Les équations d’équilibre local

Exemple 2.5.2 Pour une marche aléatoire Xt, t = 0, 1, 2, ... sur un graphe formé dedeux tetrahèdres superposés, calculer :

1. L’ésperance en partant de U du nombre de pas TO jusq’au coin opposé O.Indication :Utiliser la symmetrie.

2. L’ésperance en sortant de O du nombre de pas T̃O jusq’au premier retour à O.

3. La probabilité pA = PA{XT = U}, ou T = min[TU , TO].4. La probabilité pk en partant de O que la marche visite U exactement k fois (k =

0, 1, 2, ...) avant le premier retour à O. Vérifier la somme∑∞

k=0 pk.

5. Les probabilités stationnaires du chaque noeud. Indication : Devinez la rèponse etmontrez qu’elle satisfait le systême des équations d’équilibre.

2.5.2 L’ergodicité

Un cas trés fréquent dans les applications et quand il n’y a qu’une distribution sta-tionnaire π, qui coincide aussi avec la distribution limite pour toutes les points de départinitials possibles. Alors, par le corrollaire (2.5.1), la distribution limite est independante dela distribution de départ, est egale à π. Nous allons appeler ça le cas ergodique.

Définition 2.5.3 On appelle une châıne à matrice de transition P ergodique lorce’que ladistribution limite π(∞) = π(∞)(µ(0)) = limn→∞ µ (n) existe et est unique, independementde la distribution de départ.

Note : Dans le cas des espace d’états dénombrable, il est important de distinguerles deux cas quand la distribution limite satisfait πi > 0, ∀i et le cas quand elle satisfaitπi = 0, ∀i. Nous appelerons ces deux cas ergodique positive et ergodique nul (ce derniercas étant impossible pour des espace d’états finies). Dans la literature, le terme ergodiquesignifie d’habitude ce que nous appelons ici ergodique positive.

inc Remarque 2.5.4 Une châıne ayant des distributions limite en partant de chaque point i,et ayant une distribution stationnaire unique π est ergodique (i.e. toutes les distributionasymptotiques doivent coincider avec π).

L’abondance du cas ergodique est expliquée par la décomposition spectrale :

Lemme 2.5.1 Une matrice A de dimension n ayant un ensemble de n vecteurs propres àdroite independants di, et donc aussi un ensemble de n vecteurs propres à gauche indepen-dants l′i, calculés en prenant les lignes de la matrice D

−1, où D = (d1 | d2 | ... dn)peut-être decomposé :

A =∑i

λidi l′i

où λi sont les valeurs propres.

Ce cas a lieu par exemple quand tous les valeurs propres de P sont distincts (”le casgénérique”). Si en plus la seul valeur propre de module 1 est 1, et avec multiplicité 1 (”le casgénérique”), il suit immediatement que

limn→∞

P n = 1 π

Nous examinons maintenant pour ergodicité un exemple ou P n et π se calculent expli-citement :

13

Exemple 2.5.3 Châıne a deux ètats. Soient a, b ∈ [0, 1] et la matrice de transition :

P =(

1− a ab 1− b

)a) Montrer en calculant les valeurs et vecteurs propres que

P n =1

a+ b

(b ab a

)+

(1− a− b)n

a+ b

(a −a−b b

)b) Montrez que avec a, b ∈ (0, 1), la limite P = limn→∞ P n =

(b

a+ba

a+bb

a+ba

a+b

). En suite,

calculez cette limite dans tous les cas possibles.

En conclusion, on voit que avec a, b ∈ (0, 1), la limite matrice P = limn→∞ P n existeet qu’elle a des lignes identiques, donc la châıne est ergodique : la distribution limite

π = (b

a+ b,

a

a+ b) est unique. Elle est aussi l’unique distribution stationnaire.

2.5.3 Le théorème ergodique

Le cas ergodique est le plus important dans les applications, a cause du :

moy Théorème 2.5.1 Soit X(n) une châıne de Markov ergodique à distribution asymptotiquesπ, et soit une fonction ”coût” f tel que la ”moyenne spatiale” Eπf(X.) =

∑j∈E πjfj est bien

definie. Alors, la moyenne temporelle des coûts converge presque partout vers la moyennespatiale, for any initial distribution :

limn→∞

n−1n∑

i=1

f(Xn) =∑j∈E

πjfj

Nous examinons maintenant un exemple ou P n n’est pas disponible explicitement ; quandmême, la distribution stationnaire π est unique et donc la limite des coûts moyenne tem-porelles se calculent facilement :

Exercice 2.5.1 Montrez que la marche aléatoire sur le graph papillon a une distributionstationnaire unique π. Calculez l’esperance du coût moyenne de cette marche, si f(A) =10, f(B) = 1 et les autres coûts sont 0.

2.6 Marches aléatoires et relations de récurrence

Motivation : Les marches aléatoires sont parmi les modèles probabilistes les plus utiles(par exemple en physique, mathématiques financières, files d’attente, statistique, etc...). Ilssont aussi parmi les modèles les meilleurs compris, car ils permettent souvent des solutionsanalytiques.

14

2.6.1 Marches aléatoires sur Rd

Définition 2.6.1 Marches aléatoires sur Rd.Soit (Zn)n∈N une suite de variables aléatoires réelles i.i.d (i.e. indépendantes et de même

loi), à valeurs en Rd.Le processus Xn ∈ Rd, n = 0, 1, ... donné par la somme de ces variables

Xn = X0 + Z1 + Z2 + · · ·+ Zn, n ∈ N (2.7)

s’appelle marche aléatoire. Comme alternative, la marche aléatoire peut-être definierécursivement par la récurrence

Xn = Xn−1 + Zn (2.8)

Exemple 2.6.1 Marches aléatoires sur Zd Typiquement, on s’interesse au cas où l’espaced’états est un maillage régulier comme Zd, i.e. X0, Zn ∈ Zd ont une distribution discrètep = (pi, i ∈ Zd). Dans ce cas, nous avons à faire à une châıne à espace d’états dénombrable.

Exemple 2.6.2 Si en plus |Zn| = 1, i.e. pi ̸= 0 ssi i est un voisin de l’origine, le processus(2.7) est appelé une marche aléatoire simple.

Exemple 2.6.3 Marches aléatoires sur Z Pour les marches sur Z, la matrice de transi-tion

P = (pij = P{Xn = j/Xn−1 = i} = P{Zn = j − i})i,j∈N a aussi la propriété que Pi,j =pi−j, où pk = P{Zn = k} ; les matrices de cette forme, i.e. à “diagonales” constantes,s’appellent matrices Toeplitz.

Exemple 2.6.4 Pour une marche aléatoire simple en dimension d = 1, la distribution de Znest de la forme pδ1 + (1− p) δ−1, i.e. P [Zn = 1] = p et P [Zn = −1] = 1− p avec 0 < p < 1.Si p = q = .5 on parle d’une marche aléatoire symmetrique, et avec p ̸= q on parled’une marche aléatoire biaisée.

Extension : Si on remplace les probabilités pj par des probabilités pi,j := PXn−1=i[Xn−Xn−1 = j] on arrive à une chaine de Markov.

Théorème 2.6.1 Les marches aléatoires sur Rd ont la propriété de Markov.

Démonstration: Ce résultat est assez facile à démontrer en général, en partant de(2.8), mais nous allons considérer seulement les marches aléatoires sur Zd, pour rester dansle cadre des processus à espace d’états dénombrable. Dans ce cas, il est suffisant d’exhiberla matrice de transition .

Notes : 1) On a à faire ici à des sommes des v.a. i.i.d.. Donc, P n(0, :) la distributionde la somme

∑ni=1 Zi, est donnée par la n-ième convolution de la distribution p de Zi (et la

fonction génératrice des moments est la puissance n de la fonction génératrice des momentsde p). Le comportement des puissances P n pour n → ∞ est lié au théorème de la limitecentrale.

15

2.6.2 Moments et cumulants des marches aléatoires

Exercice 2.6.1 Les moments et cumulants de la marche simple. Soit X0 = 0 ∈ N lecapital initial d’un joueur. Au temps n = 1, 2, ..., le joueur gagnera Zn = 1 avec probabilité pet perdera Zn = −1 avec probabilité 1− p, où 0 < p < 1. Soit Xn = X0 +Z1 +Z2 + · · ·+Znson capital au temps n.

Calculez :

1. L’esperance du son gain en = EXn.

2. La variance du son gain vn = VarXn.

3. La fonction génératrice des moments M(u, n) = EeuXn.

4. La cumulant generating function κ(u, n) = log(EeuXn).

Notes : 1) Il est clair que ces propriétés de linéarité (de l’espérance , de la variance, etde la cumulant generating function ), sont vraies pour chaque marche aléatoire.

2) La connaissance de la distribution ou de la fonction génératrice des moments d’unevariable X sont typiquement equivalents. Mais, pour une somme

∑ni=1 Zi des v.a. i.i.d.,

pendant que la comme distribution est la n-ième convolution p∗,n de la p distribution de Zi,la fonction génératrice des moments Eeθ

∑ni=1 Zi est beaucoup plus simple à obtenir (ètant la

n-im̀e puissance de la fonction génératrice des moments EeθZ1).

Exercice 2.6.2 Soit mn = mn(X), n = 0, 1, 2, ... les moments d’une va X, soit κX(u) =logMX(u) = log(

∑n

un

n!mn) =

∑n

un

n!cn(X) la fonction génératrice des cumulants, où cn =

cn(X) =∂nκ(u)(∂u)n u=0

sont les cumulants.

a) Montrez (en utilisant eventuellement un logiciel symbolique) que ∀X, c0 = 0, c1 =m1, c2 = Var (X) = m2 −m21, c3 = m3 − 3m1m3 + 2m31, etc.

b) Montrez (en utilisant eventuellement un logiciel symbolique) que ∀X,m2 = c2 +c21,m3 = c

31 + 3c1c2 + c3.

Nt : 1) Le cumulant d’un ordre donné est un polynome dans les moments d’ordre pluspetit ou égal, et reciproquement.

2) Les coefficients de l’expansion des moments en fonction des cumulants sont donné pardes nombres des partitions.

3) Les cumulants d’une variable centré (m1 = 0) coincide avec les moments jusqu’autroisième ordre. C’est le quatrième cumulant, la ”kurtosis”, donné dans le cas centré parc4 = m4 − 3m22, qui joue un role important dans certaines tests statistiques (comme denonnormalité, par exemple).

Exercice 2.6.3 Pour la marche simple, calculez

1. Le premier, deuxième et troisième cumulants κi(n), i = 1, 2, 3 de Xn, i.e. les premierstrois coefficients dans l’expansion κ(u, n) =

∑i κi(n)u

i en puissances de u.

2. Le deuxième moment de Xn. Quelle est la particularité du cas p = 1/2 ?

3. Le troisième moment de Xn.

16

2.6.3 La méthode du conditionnement sur le premier pas

Exercice 2.6.4 La marche aléatoire symetrique. On cherche a trouver la probabilitéd’un joueur qui s’engage dans une série de parties (indépendantes) à un jeu où à l’issue dechaque partie il gagne 1F avec une probabilité 1/2 et perd 1F avec une probabilité 1/2, et quidécide de s’arrêter de jouer dès qu’il aura B francs en poche, ou dès qu’il n’a plus d’argent.Pour tout n ∈ N, on note Xn la fortune du joueur au bout de n parties, et X0 = i sa fortuneà l’entrée dans le Casino.

Ca revient a étudier la marche aléatoire symetrique

Xn = X0 + Z1 + Z2 + · · ·+ Zn, Xn ∈ Z

avec P [Zn = 1] = P [Zn = −1] = 1/2, jusqu’au ”temps d’arrêt/sortie” T = min[T0, TB]quand le process sort de l’interval [0, B] (en prenant 0 et B comme états absorbants). Ondénotera par Ei l’esperance en commençant de i (conditionnant sur X0 = i), et on designepar E l’événement que le joueur gagne, i.e.

E = {xT = B} = [∃n ∈ N tel que Xn = B,Xk > 0, k = 1, ..., n− 1] .Pour tout i de {0, ..., B}, on pose :

bi = P (E | [X0 = i])

(la probabilité du ”bonheur”).

1. En supposant B = 3, enumerer et esquisser l’espace de tous les chemins du bon-heur/ruine qui commencent avec X0 = 1, en developpant ”l’arbre de toutes les pos-sibilités”. Calculer la probabilité du chaque chemin, et verifier que leur somme vaut1.

2. Expliquer graphiquement sur ”l’arbre de toutes les possibilités” les équations b1 =1/2b2, b2 = 1/2b1 + 1/2, en assoc. Déduiser b0, b3, et en suite b1, b2.

3. En supposant B = 4, calculer b1, b2 et b3.

4. Calculer bi, i = 0, ..., B pour B quelconque.

5. Calculez l’espérance du nombre des pas du jeux, pour B quelconque.

R : On pourrait essayer de calculer bi en ajoutant les probabilités de tous les chemins dubonheur qui commencent avec X0 = 1 (en regardant l’arbre de toutes les possibilités). Maiscomme cet arbe est (typiquement) infini et très compliqué, cette analyse n’est pas facile. Parcontre, une approche ”diviser por conquérir” de décomposition de l’arbre dans ses branchesobtenues en conditionnent sur le premier pas ramm‘ene à des’équations linéaires faciles àrésoudre.

Cet exercice illustre trois idées :

1. La puissance de la méthode du conditionnement sur le premier pas.

2. Le calcul des esperances pour les châınes de Markov comporte des systèmes linéairesavec une inconnue pour chaque état initial possible.

3. Les systèmes associés avec un processus fixe implique toujours la même partie ho-mogène appellée ”operateur”. Dans le cas des châınes de Markov en temps discret età espace d’états fini ou dénombrable, l’ operateur est simplement P − I, où P est lamatrice de transition P .

Ces idées seront aprofondies dans les chapitres suivants, où nous regarderons quelquesautres problèmes résolubles par le conditionnement sur le(s) premier(s) pas.

17

2.6.4 La ruine du joueur pour la marche aléatoire simple

Nous généraliserons maintenant les resultats pour la marche unidimensionelle syme-trique au cas des marches simples asymetriques. En même temps, nous étudiérons d’autresproblèmes concernant l’absorbtion dans un ensemble d’arrêt pour la marche aléatoire simpleunidimensionnelle (les équations obtenues sont valables dans toute dimension,mais les solu-tions sont disponibles explicitement seulement dans le cas unidimensionnel).

Exemple 2.6.5 La ruine du joueur et autres ”problèmes de Dirichlet” pour lamarche aléatoire simple. Considérons la marche aléatoire simple

Xn = X0 + Z1 + Z2 + · · ·+ Zn, Xn ∈ Z

avec (Zn) une suite de variables aléatoires réelles indépendantes de même loi P [Zn = ±1] =p, q. Nous étudierons la marche jusqu’au ”temps d’arrêt/sortie” T = min[T0, TB] quand leprocess sort de l’interval [0, B] pour B donné, i.e. on prend 0 et B comme états absorbants.On appelle ce problème la ruine du joueur, a cause de l’interpretation d’un joueur quis’engage dans une série de parties (indépendantes) à un jeu où à l’issue de chaque partieil gagne 1F avec une probabilité p et perd 1F avec une probabilité q = 1 − p, et qui décidede s’arrêter de jouer dès qu’il aura B francs en poche, ou dès qu’il n’a plus d’argent. Pourtout n ∈ N, on note Xn la fortune du joueur au bout de n parties, et X0 = i représentesa fortune à l’entrée dans le Casino. On dénotera par Ei l’esperance en commençant de i(conditionnant sur X0 = i), et on designe par E l’événement que le joueur gagne, i.e.

E = {xT = B} = [∃n ∈ N tel que Xn = B,Xi > 0, i = 1, ..., n− 1] .Pour tout i de {0, ..., B}, on pose :

bi = P (E | [X0 = i]) .

1. Quelles sont les valeurs de b0 et bB ?

2. Montrer que :

∀ i ∈ {1, ..., B − 1} , bi = p bi+1 + q bi−1 (on rappelle que q = 1− p).

3. Obtener une expression explicite de bi pour tout i de {1, ..., B} . Indication : Remarquezque la solution satisfaisant b0 = 0 est de la forme :

bi =

{k (1− ( q

p)i) quand p ̸= q

k i quand p = q

et déterminer k tq la condition frontière de bB soit satisfaite.

4. Pour tout i de {0, ..., B} , on pose ai = P (F | [X0 = i]) où F est l’événement ”le joueurrepart ruiné” . En procédant comme auparavant, montrer que :

ai =

( qp)

i−( qp)

B

1−( qp)B si p ̸= 12

B−iB

si p = 12

Pour tout i de {0, ..., B} , calculer ai + bi. Que peut-on en déduire ?Calculez les probabilités de ruine quand B → ∞, pour p > q et pour p ≤ q. Expliquezla rélation avec le comportement de Xt, t→∞.

18

5. Obtenez un système d’équations pour l’espérance du gain final fi = EiXT . Calculezcette fonction pour p = q.

6. Obtenez un système d’équations pour l’espérance du temps de jeu : ti = EiT . Calculezcette fonction, pour p = q, et pour p < q, quand B →∞.

7. Obtenez un système d’équations pour l’espérance du ”coût cumulé d’inventoire” ci =Ei∑T−1

t=0 Xt. Calculez cette fonction, pour p = q, et pour p < q, quand B →∞.8. Obtenez un système d’équations pour wi = EiaT =

∑k=0 Pi[T = k]ak (qui est la

fonction génératrice des probabilités Pi[T = k]). Calculez cette fonction, pour p ̸= q.9. Obtenez les équations de récurrence et les conditions frontière satisfaites par ux =

ExaTg(XT ), a ∈ (0, 1) et par vx = Ex[aTg(XT ) +∑T−1

t=0 h(Xt)], a ∈ (0, 1).

Résolvons cet exercice en utilisant la méthode du conditionnement sur le premier pasZ1, l’idée de quelle est d’obtenir des relations de récurrence qui lient les valeurs de l’espéranceconditionnée à partir de tous les points de départ possibles.

Nous verrons, en examinant les questions 2)-8) de cet exercice, qu’ils utilisent toutes lemême opérateur

(Gf)n := (P − I)(f)n = p fn+1 + q fn−1 − fn (2.9) op

la seule difference étant dans les conditions frontière et dans la partie nonhomogène. En plus,ils se regrouperont en deux types de questions :

1. ”Gain final esperé”, satisfaisant :

fn = En[g(XT )] = pfn+1 + qfn−1 ⇐⇒ (Gf)n = 0, F (0) = g(0), F (B) = g(B)

2. ”Coût total accumulé esperé”

fn = En[T−1∑0

h(Xi)] = h(n) + pfn+1 + qfn−1 ⇐⇒ (Gf)n = 0, f(0) = 0, f(B) = 0

Solution :

1. b0 = 0, bB = 1

2. Gain final esperé, g(x) = 1x=B.

En conditionnant, on trouve :

bn = Pn[X(T ) = B]= p Pn[X(T ) = B/X(1) = n+ 1] + q Pn[X(T ) = B/X(1) = n− 1]= p bn+1 + q n−1 1 ≤ n ≤ B − 1

car

Pn[X(T ) = B/X(1) = n± 1] = P[X(T ) = B/X(0) = n,X(1) = n± 1] =P[X(T ) = B/X(1) = n± 1] = P[X(T ) = B/X(0) = n± 1] = bn±1

en utilisant la proprieté de Markov et l’homogeneité.

19

3. Quand p = q = 1/2, bx = Px[X(T ) = B] satisfait :

bn =bn+12

+bn−12

for any 1 ≤ n ≤ B − 1

bB = 1

b0 = 0

La méthode de résolution des équations de récurrence homogènes à coefficients constantscommence en cherchant des solutions de la forme bn = r

n. Si les racines de l’équationauxiliaire sont distinctes, la solution générale est :

bn = k1rn1 + k2r

n2

où k1, k2 sont déterminés en utilisant les conditions frontière.

Ici, cherchant des solutions puissances rx ramène à l’équation r2 − 2r + 1 = 0 à deuxracines identiques r1,2 = 1. La solution générale est bx = A + Bx. Les conditionsfrontière donnent bx =

xB.

Solution finale si p ̸= q : bn = 1−(q/p)n

1−(q/p)B .

4. ai+bi = 1, et donc la marche sera eventuellement absorbé dans une des deux frontiéres(elle ne peut pas rester à l’intérieur indéfinimment).

Pour p = q, limB→∞ an = limB→∞B−nB

= 1. Autrement,

limB→∞

an = limB→∞

(q/p)n − (q/p)B

1− (q/p)B=

{(q/p)n, q < p

1, q > p.

5. fx = Ex[X(T )] (valeur finale ésperée) satisfait Gf(x) = 0, f(0) = 0, f(B) = B. Pourp = q, la solution fx = x est obtenue comme ci-dessus :

fx =fx+12

+fx−12

for any 1 ≤ x ≤ B − 1

fB = B

f0 = 0

(C’est aussi une fonction ”harmonique”, mais avec conditions frontière différentes.)

6. tx = Ex[T ] (temps de sortie ésperé) est un coût total accumulé esperé (obtenu enprenant h(x) = 1), qui satisfait le système inhomogène Gt(x) + 1 = 0, t(0) = 0, t(B) =0.

Pour p = q

tx =tx+12

+tx−12

+ 1 for any 1 ≤ x ≤ B − 1tB = 0

t0 = 0

La solution d’une équation nonhomogène est donnée par

tx = tp(x) + h(x)

20

où tp(x) est une solution particulière et h(x) est la solution générale de l’équationhomogène. Commençons par l’équation homogène.

La solution générale homogène (”fonction harmonique”) h(x) = A + Bx pour cetopérateur a été déjà obtenue ci-dessus.

Nous aimerions maintenant trouver une solution particulière tp(x) de l’équationGtp(x) =−1 de la même forme que la partie nonhomogène −1 de l’équation, donc tp(x) = C;mais, comme les constantes, et puis aussi les fonctions linéaires vérifient l’équationhomogène Gtp(x) = 0, nous devrons modifier deux fois cette forme en multipliant parx, en arrivant donc à t(x) = Cx

2. Comme Gx2 = 2x(p− q) + 1 = 1, on trouve C = −1et finalement la solution particulière tp(x) = −x2.La solution générale est donc t(x) = −x2+A+Bx et les conditions frontière ramènentà tx = x(B − x).Pour p ̸= q

tx = ptx+1 + qtx−1 + 1 for any 1 ≤ x ≤ B − 1tB = 0

t0 = 0

La solution generale homogène avec p ̸= q est h(x) = k1(q/p)n + k2 et le termenonhomogène 1 sugere une solution particulière constante k, mais comme ça satisfaitl’équation homogène, on modifie à kn. Finalement, k = 1

q−p .

La solution particulière est tp(x) =x

q−p ; elle satisfait deja tp(0) = 0. La partie homogène

h(x) = tx − tp(x) devra aussi satisfaire h(0) = 0 et donc elle sera de la forme h(x) =Ah̃(x) où h̃(x) = ((q/p)x − 1).En demandant que tn =

nq−p + A(q/p)

n − 1) satisfait la condition frontière tB = 0 ontrouve :

tn = tp(n)− tp(B)h̃(n)

h̃(B)=

n

q − p− Bq − p

(q/p)n − 1(q/p)B − 1

.

La limite quand B → ∞ est tn =

{∞ si p > qtp(n) =

nq−p si p < q

; on peut aussi obtenir ce

resultat en utilisant l’approximation détérmiste Xn − X0 ∼ nE(Z1), appellée aussilimite fluide.

7. cx = Ex[∑T−1

0 X(t)] (coût total d’inventaire ésperé) satisfait le système inhomogèneGc(x) + x = 0, c(0) = 0, c(B) = 0.

Pour p = q :

cx =cx+12

+cx−12

+ x for any 1 ≤ x ≤ B − 1cB = 0

c0 = 0

Une solution particulière est cp(x) =−x33. Finalement, on arrive à c(x) = x(B

2−x2)3

.

Pour p ̸= q, une solution particulière est cp(x) = x2

2(q−p) (elle satisfait deja cp(0) = 0).

La partie homogène satisfaisant h(0) = 0 sera toujours h(x) = Ah̃(x) où h̃(x) =((q/p)x − 1).

21

En demandant que cn = cp(n) +A(q/p)n− 1) satisfait la condition frontière cB = 0 on

trouve :

cn = cp(n)− cp(B)h̃(n)

h̃(B)

La limite quand B →∞ est cn =

{∞ si p > qcp(n) si p < q

.

8. On arrive a w(x) = A1zx1 + A2z

x2 , où zi sont les racines de pz

2 − a−1z + q = 0, et Aisatisfont A1z

B1 + A2z

B2 = 1, A1 + A2 = 1 et w(x) =

zx1−zx2+zx1 zx2 (zB−x1 −z

B−x2 )

zZ1 −zB2

9. On a ux = g(x), pour x ∈ {0, B}, et le conditionnement donne la relation : ux =Ex[aTg(Xτ )] = a(pux+1 + qux−1).vx = g(x), pour x ∈ {0, B}, et le conditionnement donne la relation : vx = a(pvx+1 +qvx−1) + h(x).

Conclusion : Nous avons vue dans ces exercices une des idées les plus importantes dela modélisation Markovienne : les ésperances, vues comme fonctions de l’état initial,satisfont certaines équations qui font toujours intervenir un opérateur associéfixe, appelé générateur du processus, même que les conditions frontière, termesnon-homogènes, et d’autre ”details” (comme la presence/absence d’une multiplede l’operateur identité) peuvent varier.

Les equations s’obtient facilement par la methode de conditionnement sur le premierpas, en utilisant la propriété de l’oubli du passé des processus de Markov ; mais, il y a desparties specifiques a chaque probléme, qui ne sont pas oubliées !

Il s’avère que les mêmes èquations décrivent la solution des problèmes analogues pourtoutes les châıne de Markov à espace d’états comptable, et avec des états absorbants – voirla prochâıne section.

Par exemple, pour les châınes de Markov, l’operateur associé est G = P − I, où P est lamatrice de transition, et pour le cas particulier d’une marche aléatoire Xt =

∑ti=1 Zi avec

pk = P [Zi = k], k ∈ [−c, d] on a encore G = P − I, où P =∑

k pkFk et F est l’operateur de

translation (Ff)k = fk+1, k ∈ Z.Alors, nous obtendrons des èquations similaires pour les problèmes respectives, juste en

remplaçant l’ancien operateur par le nouveau.

On rencontre la même situation pour toute la classe des processus ”de Markov”, Xt,différents qu’elles soient, vivant sur des espaces S considerablement plus compliqués, la seuledifference étant que l’operateur GX : F (S)− > F (S) associé a ces processus sera pluscompliqué !

Par exemple, les problèmes de cette section ont aussi des versions à espace d’états continu,obtenu en considérant des marches avec incréments infinitésimaux ϵ, et en prenant la limiteE → 0. La marche aléatoire devient ainsi un processus avec chemins continus, appelé mou-vement Brownien. Les équations resterons les mêmes, seul l’operateur G changera (dans unoperateur differentiel).

En conclusions, il existe une correspondance un á un entre les processus de Markov et unecertaine classe des operateurs deterministes associés ; nous l’appellerons ”Le Dictionnaire”.

22

2.6.5 Probabilités du bonheur/fonctions harmoniques

Nous considerons ici plus en detail les probabilités du bonheur, et devoilons leur nomscientifique.

Une fonction sur Zd/Rd est appellée harmonique si la valeur en chaque point x est egaleà la moyenne arithméthique des valeurs des ”voisins”. En Rd, par voisins on entend unesphère arbitraire avec centre x. Ces fonctions aparaissent beaucoup en physique.

En probabilités, les moyennes arithméthiques deviennent des moyennes ponderés.

Définition 2.6.2 Une fonction/vecteur f : E− > R s’apelle harmonique pour une châınede Markov à matrice de transition P s’il s’agit d’un vecteur propre à droite de P , i.e

f(x) =∑

P (x, y)f(y), ∀x ∈ E

Autrement dit, chaque point x verifie les valeurs f(y) de ses ”voisins” (definis parP (x, y) > 0, et choisi pour valeur une moyenne ponderée de valeurs voisines.

Rq : Le fait que chaque valeur est une moyenne ponderée des valeurs voisines suggèreun algorithm de calcul interessant.

Il est facile de montrer que :

Lemme 2.6.1 a) Pour une châıne avec une seule classe de communication (recurrente), lesseuls fonctions harmoniques sont les constantes f(x) = a.

b) Pour une châıne avec K classes de communication recurrentes C1, ...CK, et sans étatstransients (donc forcement reductible si K > 1), les fonctions harmoniques sont les fonctions

escalier∑K

k=1 ak1Ck(x).

Ind : a) Une fonction non constante prend des valeurs dans un interval [m,M ], oùM > m. Mais, l’equation d’equilibre pour un point xM tq f(XM) = M implique que ...m =M !

La situation devient beaucoup plus interessante dans la presence des états transients(”subordonnés”) et de plusieures classes de communication (”leaders”).

Exercice 2.6.5 Etant donnée une châıne finie avec deux états absorbants 0, B et le reste desétats transients, obtenez un système et une formule explicite pour le vecteur des probabilitésdu bonheur b = (bi = Pi[XT = B], i ∈ T ).

Sol : Soit

P =

1 0 0q0 Q qB0 0 1

où q0, qB sont les vecteur des probabilités d’absorbtion directe en 0 et B (i.e. après un pas).Soit n le nb des états transitoires (la taille de Q). On trouve que b = (bi)i∈T satisfait

b = P̃

0b1

où P̃ est la matrice P avec les lignes des états absorbants effacés. En developpant, on trouve :

b = Qb+ qB ⇐⇒ b = (I −Q)−1qB. (2.10)

Rémarques :

23

1. Le vecteur etendu b̃ =

0b1

est une fonction harmonique/vecteur propre à droite deP. Comme le système etendu P b̃ = b̃ contient deux équations triviales, notre intérêtest surtout en le vecteur correspondant aux états transitoires b, donné explicitementen (2.10).

2. Rémarquez l’apparition en (2.10) de la matrice fondamentale

←−G := (I −Q)−1.

3. Une généralisation des probabilités du bonheur sont les ”prix finaux esperés” :

fg(x) := Eg(XT ), fg : V− > R

où gy, y ∈ ∂ est un ”prix” ou condition frontière donné. On vérifie par CPP (condi-tionnement sur le premier pas) qu’elles satisfont :

f(x) = g(x), x ∈ ∂, (Gf)x = 0⇐⇒ fx = (Pf)x, x ∈ T := V − ∂

et sont donc aussi des fonctions harmoniques. Ces fonctions harmoniques ”à condi-tions frontière données” sont en corréspondance biunivoques avec les conditions defrontière g : ∂− > R possibles. Cela rend les fonctions harmoniques sur Zd ou Rdbeaucoup plus simple quand d = 1 et la frontière contient que deux points ! Pour lamarche symmetrique par exemple, il s’agit des fonctions lineaires ! Par exemple, avecp = q = 1/2, g(0) = 3 et g(10) = 53, le pris final esperé est f(x) = 5x+ 3.

2.6.6 Marches aléatoires sur les graphes : distributions station-naires

L’étude des châınes de Markov sur un espace d’états fini nous rammène toujoursà un système linéaire impliquant la matrice P. Il se trouve quand même que des for-mules/approches algorithmyques plus simples sont disponible pour certains cas particuliers,comme celui des marches aléatoires sur les graphes non dirigés.

Définition 2.6.3 a) La matrices d’adjacence d’un graphe est la matrice définie par

D(x, y) ={1 si⇐⇒ j0 sinon

b) La marche aléatoire simple sur un graphe est la marche avec probabilités de transition

P (x, y) = D(x,y)dx

où dx =∑

yD(x, y) est le degré du sommet x.

L’inspiration de la generalisation qui suit nous vient d’electricité, du problème de calculerles voltages sur un réseau des resisteurs.

Considerons un réseau des resisteursR(x, y), modélisé par un quatrupleG = (V,E,C(., .), ∂)representant un graph avec sommets V , arrêtes E,, des poids C(x, y) = 1

R(x,y), (les ”conduc-

tances electrique”) associés aux arrêtes, et un sous-ensemble des sommets distingués ∂, oùdes voltages ou des courants electriques sont imposés. Les lois bienconnues des courantselectriques de Kirkhoff sont l’expression macroscopique de la marche aléatoire sur le réseaud’un electron, avec des poids C(x, y) associé à chaque arrête.

24

Définition 2.6.4 a) Une marche est appellée reversible si il existe un vecteur des poidsc(x) tq la matrice

C(x, y) := c(x)P (x, y)

est symmetrique, i.e. tqc(x)P (x, y) = c(y)P (y, x), ∀x ̸= y.

Ces équation sont appelées équations d’equilibre local.b) Inversement, a chaque matrice C(x, y) symmetrique avec des elements nonegatifs, on

peut associer une marche aléatoire reversible avec probabilités de transition P (x, y) = C(x,y)cx

,

où (forcemment) cx =∑

y C(x, y).

Rq : Les marches reversibles seront appellées aussi ”marches de réseau” ou ”marchessur un graphe ponderé”, car les elements de la matrice symmetrique C(x, y) peuvent-êtretojours vues comme des conductances d’un réseau electrique, ou comme des poids associésaux arrêtes d’un graphe.

Lemme 2.6.2 La distribution stationnaire d’une marche aléatoire reversible (en particuliersimple) est proportionelle au poids (degrés) cx des sommets, i.e.

π(x) =cx∑y cy

.

Dem : On verifie facilement que le vecteur des probabilites π(x) = cx∑y cy

satisfait les

équations d’équilibre local

π(x)P (x, y) = π(y)P (y, x),∀x ̸= y (2.11)

qui a leur tour impliquent les équations d’equilibre global par Lemme 2.6.3.Comme π(x) est un vecteur des probabilités, il suit qu’il est la distribution invariante.

eqgl Lemme 2.6.3 Une solution des équations d’équilibre local 2.11 satisfait toujours les équationsd’equilibre global πP = π.

Dem : Rémarquez que les équations d’équilibre local ne tiennent pas compte desboucles ! Ca suggère de commencer en donnant aussi des équations d’equilibre globalsans boucles. En effet,

πx =∑y

π(y)P (y, x)⇐⇒ πx(1− P (x, x)) =∑y ̸=x

π(y)P (y, x)

⇐⇒ πx(∑y ̸=x

P (x, y)) =∑y ̸=x

π(y)P (y, x) (2.12)

Il reste juste à observer que en ajoutant les équations d’équilibre local on obtient ladernière forme ”sans boucles” des équations d’equilibre global.

Remarque 2.6.1 Les équations π(x)P (x, y) = π(y)P (y, x) sont plus simples à resoudre queles équations d’équilibre global, mais comme typiquement il y a plus d’arrêtes (pairs) que desnoeuds, elles admettent de solutions seulement dans de cas particuliers.

25

Exercice 2.6.6 Calculer la distribution invariante de la marche aléatoire simple, symme-trique sur les entiers {0, 1, ..., B}, ”réfléchie” en 0, B.

Exercice 2.6.7 Est-ce que la marche simple asymmetrique sur {0, 1, ..., n} ”cyclique” (i.e.avec n + 1 := n,−1 := 0), avec Pi[X(1) = i+ 1] = p, Pi[X(1) = i− 1] = q, est reversible ?Calculer sa distribution invariante, ainsi que la matrice des conductances C(x, y).

Remarque 2.6.2 La reversibilité permet d’associer avec la marche un graphe non-dirigéavec des poids C(x, y), qui s’avère utile pour le calcul des fonctions harmoniques.

2.6.7 Les espérances des temps d’atteinte, et les problèmes de Di-richlet nonhomogènes

Exercice 2.6.8 Montrez que si N est une v.a. sur {0, 1, ..., }, alors

EN =∞∑k=1

P [N ≥ k] (2.13)

Verifiez cette formule pour la variable géométrique.

Nous avons deja vu que le ”pb du bonheur” (ou de Dirichlet) abouti à un systèmelinéaire. C’est le cas de tous les pb associés aux processus de Markov, comme par exemplele pb du temps d’atteinte/absorbtion esperé : étant donnée une châıne finie avec des étatsabsorbants, calculer le vecteur t = (ti = Ei[T ], i ∈ T ), où T est le temps (nb. des pas) esperéjusqu’à l’absorbtion.

t:Dir1 Théorème 2.6.2 a) Le vecteur t des espérances des temps d’absorbtion à partir des étatstransitoires satisfait le système d’absorbtion

t = Qt+ 1⇐⇒ G̃t+ 1 = 0 (2.14)ti = 0, ∀i ∈ ∂

où G̃ := Q− I est l’operateur restreint aux états transitoires.b) Elles sont données explicitement par :

t = (I −Q)−1 1 =∞∑k

Qk1.

c) Avec une distribution initiale β, l’espérance t̄ = EβN du temps d’absorbtion est :

t̄ = ET = β(I −Q)−11

Remarque 2.6.3 Rémarquez de nouveau l’apparition de la matrice fondamentale

←−G := (I −Q)−1.

Remarque 2.6.4 (2.14) est notre premier exemple de ”système de Dirichlet nonho-

mogène” faisant intervenir l’operateur G̃. Formulé comme ci-dessus, par rapport à G̃, il estvalable aussi en temps continu (et en fait pour tous les processus de Markov). En remplaceant1 par des fonctions arbitraires, on arrive aux pb. de Dirichlet nonhomogènes.

26

Demonstration : a) est équivalent au système

ti =∑j∈E

Pi,j(tj + 1) =∑j∈T

Qi,j(tj + 1) +∑j /∈T

P(T ,∂)i,j ∗ 1,

obtenu par un conditionnement sur le premier pas.b) La solution du système donné en a) est : t = 1+Qt⇐⇒ t = (I −Q)−11.

Remarque 2.6.5 La matrice G̃ a seulement des valeurs propres avec partie réelle negative,étant par conséquent inversible.

Remarque 2.6.6 La formule explicite

t = (I −Q)−1 1 =[ ∞∑

i=0

(Q)i]1

a une interprétation probabiliste importante, analogue à (2.13). Remarquons d’abord ladécomposition en indicateurs

T =∞∑k=0

Ik ⇒ ti =∞∑k=0

EiIk

où Ik est l’indicateur d’être dans la partie transitoire au temps k.Remarquons aussi la décomposition en indicateurs Ik =

∑j∈T Ik,j, où Ik,j est l’indicateur

d’être en position j ∈ T au temps k. Ces décompositions nous ramènent finalement à

ti =∞∑k=0

EiIk =∞∑k=0

∑j∈T

EiIk,j =∞∑k=0

∑j∈T

(Q)ki,j =∑j∈T

(I −Q)−1i,j =←−Gi,j

Les elements←−Gi,j de la matrice fondamentale, appellées aussi fonction de Green (ou

potentiel), fournissent le ”bilan de la vie”, i.e. les esperances de l’ensemble des tempspassés dans tous les endroits possibles j, pendant la ”vie transitoire”.

Remarque 2.6.7 Comme toujours, le système et la méthode donné au point a) sont plusimportants que la formule explicite donnée en b) ; en effet, l’inversion des matrices n’est pasla meilleure solution pour résoudre un système (la reduction à la forme échelon par exempleest preferable). Aussi, il existe beaucoup de variations de ce problème, ramènant a une grandediversité des formules explicites, pendant que le principe pour obtenir les systèmes et toujoursle même : conditionnement sur le premier pas. Ce problème fournit donc une illustrationdu fait que conceptuellement et numériquement, les systèmes d’équations sont plus utiles queleurs solutions explicites !

2.6.8 Temps esperés de retour

SoitT (x) := inf{t > S(x), Xt = x}

où S(x) := inf{t > 0, Xt ̸= x} le temps de la premí‘ere visite en x, ”après avoir été ailleurs”.Soit

P =

(Q qxsx px

)où qx, sx, px sont respectivement les vecteurs des probabilités de passage direct en x, desortir de x, et d’une boucle en x.

27

Exercice 2.6.9 Montrez que le vecteur de probabilités invariantes est proportionel au vec-teur (sx(I − q)−1, 1 et que

t̃x := ExT(x) = 1 + sx(I − q)−11 =

1

π(x)

Exercice 2.6.10 Pour une marche aléatoire Xt, t = 0, 1, 2, ... sur le graphe cubiqueci-dessous, calculer :

O

UB

A

Figure 2.2 – Marche aléatoire simple

1. La probabilité pA = PA{T (U) < T (0)} = PA{XT = U}, ou T = min[T (U), T (O)].Indication : Utiliser la symmetrie.

2. Comparer le résultat avec le potentiel electrique obtenu en 1 si les entiers sont connectéspar des résistances unitaires, et une tension égale à 1 est appliquée entre 0 et B.

3. L’ésperance du nombre de pas T = min[T (O), T (U)].

4. Les probabilités stationnaires du chaque noeud.5. L’ésperance en sortant de U du nombre de pas TO jusq’au noeud O.

6. L’ésperance en sortant de O du nombre de pas T̃O jusq’au premier retour à O.

7. La probabilité pk en partant de O que la marche visite U exactement k fois (k =0, 1, 2, ...) avant le premier retour à O. Vérifier la somme

∑∞k=0 pk.

R : X(t) représente une marche aléatoire simple sur le cube [0, 1]3, 0⃗ est l’origine (0, 0, 0),le coin oposé (1, 1, 1) est noté par u. On remarque que dans toutes les questions les voisinsde l’origine ont un role symetrique et cela nous permet de le noter par la même lettre a =(0, 0, 1), .... . De la même manière on appelle les voisins de u par b = (0, 1, 1), ....

1. Pa[X(T ) = u], s’obtient de la solution du système{pa =

23pb +

13p0 =

23pb

pb =23pa +

13pu =

23pa +

13

qui donne pb =35, pa =

25.

2. Même système !3. ta, tb sont la solution du système{

ta =23(1 + tb) +

13(1 + t0) =

23tb + 1

tb =23(1 + ta) +

13(1 + tu) =

23ta + 1

qui donne tb = ta = 3. Remarquez la similarité entre les deux systèmes.

28

4. π = (1/8, 1/8, ..., 1/8).

5. Pour trouver tu = Eu[T0], on résout le système :

tu = 1 + tb

tb = 1 +2

3ta +

1

3tu

ta = 1 +2

3tb

dont la solution est ta = 7, tb = 9, tu = 10.

6. E0[T̄0] où T̄0 représente le temps esperé jusqu’à la prochâıne visite de 0 en commencantde 0, est donné par 1 + ta = 1 + 7 = 8. A remarquer que c’est exactement l’inversede la probabilité ”de long parcour” d’être à 0,ce qui est un résultat bien connu sur lestemps de retour espérés.

7. Soit pk la probabilité d’avoir exactement k visites à U = (1, 1, 1) avant de retourner à0. Alors p0 c’est le même que la probabilité commencant en A que la marche revient à0 avant de visiter (1, 1, 1), qui est 3

5.

Pour k = 1 visites, ”le chemin” observé seulement en O, l’état aprés B et U” estA,U,B,0. Donc, p1 = PA[U,B, 0] = (

25)2, p2 = PA[U,B, U,B, 0] = (

25)2(3

5), et en général

pk =35pk−1 = (

25)2(3

5)k−1, k ≥ 2. La distribution pour k ≥ 1 est geometrique (verifiez

que∑∞

k=1 pk =25, comme il faut).

Exercice 2.6.11 Un spéolog est perdu dans une grotte, les chemins de la quelle forment legraphe papillon ci-dessous. Il se trouve à present dans le point A, et à cause de la manquede visibilité, est obligé a faire une marche aléatoire entre les sommets du papillon.

O U

A

B

C

Figure 2.3 – Marche aléatoire simple sur le graphe papillon

A) Calculer les probabilités stationnaires de chaque noeud, et l’espérance en sortant deO du nombre de pas ÑO jusqu’au premier retour à O.

B) Supposons que cette marche finira en U avec la liberté (sortie de la grotte) ou en Oavec la mort. Calculer :

1. la probabilité de survie du spéolog pA = PA{XN = U} = PA{NU < N0}, où N =min[NU , NO].

2. Les probabilités transitoires Q2, Q3, Qn.

3. La fonction gńératrice (I − xQ)−1, la matrice fondamentale et le nb. esperé des visitesen B,A et C, à partir de B.

4. L’espérance nA = EA[N ]. Indication : Utiliser la symmetrie.

29

Solution B) : 1) En résolvant le système d’absorbtion pour pA, pB, pC , on trouve pA =3/4, pB = 1/2, pC = 1/4

2) Calculons la puissance n de la matrice Q correspondant auc états transitoires B(centre), A,C. Le polynôme charactéristique est −λ3 + λ/4 = −λ

4(4λ2 − 1), avec racines

λ0 = 0, λ1,2 = ±1/2). Par Cayley-Hamilton,

Q2 =

14 0 00 18

18

0 18

18

, Q3 = Q/4 = 0 116 1161

80 0

18

0 0

, Q4 = Q2/4 = 116 0 00 1

32132

0 132

132

, ...

Qk =

2−k−1 (1 + (−1)k) −2−k−2 (−1 + (−1)k) −2−k−2 (−1 + (−1)k)−2−k−1 (−1 + (−1)k) 2−k−2 (1 + (−1)k) 2−k−2 (1 + (−1)k)−2−k−1

(−1 + (−1)k

)2−k−2

(1 + (−1)k

)2−k−2

(1 + (−1)k

)

3) La fonction génératrice est

(I − xQ)−1 =

1

1−x24

x

4(1−x2

4

) x4(1−x2

4

)x

2(1−x2

4

) 1−x281− x2

4

x2

8(1−x2

4

)x

2(1−x2

4

) x28(1− x2

4

) 1−x281−x2

4

la matrice fondamentale est :

(I −Q)−1 =

43 13 1323

76

16

23

16

76

Les nb. esperé des visites en B,A et C, à partir de B se trouvent dans la première ligne.

Exercice 2.6.12 Calculer Q2, Q3, Qn et (I −Q)−1 pour Q =

(1/2 1/4 1/41/2 0 01/2 0 0

).

R : Le polynôme charactéristique est −λ3+λ2/2+λ/4 = −λ4(4λ2−2λ−1), avec racines

λ0 = 0, λ1,2 = (1±√5)/4). Par Cayley-Hamilton, Q3 = Q2/2 +Q/4.

La solution la plus simple est par la decomposition spectrale. Une autre est de chercherdes scalaires tq Qn = anQ

2 + bnQ. On trouve an = an−1/2 + bn−1, bn = an−1/4 et

Qn = anQ2 + bnQ,n ≥ 2

où an = an−1/2 + an−2/4, a1 = 0, a2 = 1, an =λn−11 −λ

n−12

λ1−λ2 , et finalement

Qk =

Ak Bk/2 Bk/2Bk Ck CkBk Ck Ck

=

λk+11 −λk+12

λ1−λ2λk1−λk2

4(λ1−λ2)λk1−λk2

4(λ1−λ2)λk1−λk2

2(λ1−λ2)λ1λk2+(−λ2)λk1

2(λ1−λ2)λ1λk2+(−λ2)λk1

2(λ1−λ2)λk1−λk2

2(λ1−λ2)λ1λk2+(−λ2)λk1

2(λ1−λ2)λ1λk2+(−λ2)λk1

2(λ1−λ2)

30

3) Les formules pour les probabilités transitoires sont assez compliquées ; plus conve-nables sont les formules des fonctions gńératrices (I−xQ)−1, qui généralisent la matricefondamentale (I−Q)−1. En généralisant encore, remplaçons la première ligne par (z, z1, z2) :

(I − xQ)−1 = I + xQ+ x2Q2 + ... =1

− z1x2

2− z2x

2

2−zx+1

xz1

− z1x2

2− z2x

2

2−zx+1

xz2

− z1x2

2− z2x

2

2−zx+1

x

2(− z1x

2

2− z2x

2

2−zx+1

) − z2x22 −zx+1− z1x

2

2− z2x

2

2−zx+1

x2z2

2(− z1x

2

2− z2x

2

2−zx+1

)x

2(− z1x

2

2− z2x

2

2−zx+1

) x2z12(− z1x

2

2− z2x

2

2−zx+1

) − z1x22 −zx+1− z1x

2

2− z2x

2

2−zx+1

={z1=z2=1/4,z=1/2}

1

−x24−x

2+1

x

4(−x2

4−x

2+1

) x4(−x2

4−x

2+1

)x

2(−x2

4−x

2+1

) −x28 − x2+1−x2

4−x

2+1

x2

8(−x2

4− x

2+1

)x

2(−x2

4−x

2+1

) x28(−x2

4− x

2+1

) −x28 −x2+1−x2

4−x

2+1

={x=1} 4 1 12 3

212

2 12

32

Une expansion en series de puissances en x fournit les probabilités transitoires x54 + 5x416 + 3x38 + x22 + x2 + 1 5x564 + 3x432 + x38 + x28 + x4 5x564 + 3x432 + x38 + x28 + x45x532

+ 3x4

16+ x

3

4+ x

2

4+ x

23x5

64+ x

4

16+ x

3

16+ x

2

8+ 1 3x

5

64+ x

4

16+ x

3

16+ x

2

85x5

32+ 3x

4

16+ x

3

4+ x

2

4+ x

23x5

64+ x

4

16+ x

3

16+ x

2

83x5

64+ x

4

16+ x

3

16+ x

2

8+ 1

La généralisation (sans peine) peut fournir le nb. esperé des boucles en 1, et les nb.

esperés des passage 1− > 2 et 1− > 3 (en derivant par rapport à la ”variable de bilan”associée et en la faisant ensuite 1).

Exercice 2.6.13 Supposons que les chemins menant à U dans la grotte du speologueprennent deux heures, ceux menant à O trois heures, et les autres 5 heures.

1. Calculez l’espérance du temps T qu’il reste a passer dans la grotte.

2. La grotte contient aussi un génie, qui frappe le spéolog des nb. aléatoires, ayant unedistrbution de Poisson des coups, avec esperance 3 sur les chemins menant à U , 5 pourceux menant à O, et 2 pour les autres chemins. Calculez l’espérance du nombre descoups que le spéolog prendra dans la grotte.

3. (*) Calculez la variance et la distribution du nombre des coups que le spéolog prendradans la grotte.

4. Etant donnée une marche ponderé sur un graphe, avec des états absorbants, et destemps derministes Ti,j pour traverser l’arrête (i, j), calculer le vecteur T = (ti =Ei[T ], i ∈ T ).

R : 4. T = (I −Q)−1Q×H T̃ où T̃ est la matrice des temps T̃i,j pour traverser de i à jet ×H denote le produit composante par composante. �.

2.6.9 Méthode des fonctions génératrices

Exercice 2.6.14 Calculez, par la méthode des fonctions génératrices :a) T (z) =

∑n≥0 Tnz

n, où

T0 = 0, Tn = 2Tn−1 + 1, n ≥ 1

31

Trouvez Tn.b) Calculez T (z) =

∑n≥0 Tnz

n, où

T0 = 1, Tn = 2Tn−1 + n− 1, n ≥ 1

Trouvez Tn.

Sol : b) Par la méthode de decomposition des équations linéaires : Tn = 2n+1−(n+1). La

fonction génératrice de Tn est T (z) = 2/(1−2z)−1/(1−z)2 = (2z2−2z+1)/(1−2z)(1−z)2.En appliquant directement la méthode des fonctions génératrices à Tn = 2Tn−1 + n− 1

on trouve l’équation : T (z) = 1+2zT (z)+z/(1−z)2− (1/(1−z)−1) = 2zT (z)+(2z2−2z+1)/(1− z)2, et on retrouve la même reponse. L’avantage de cette méthode plus compliquéeest qu’elle reussit parfois quand la première méthode échoue.

Exercice 2.6.15 a) Obtenez une formule explicite pour la suite décrite par la relation derécurrence ci-dessous (et verifiez-la en utilisant les premiers termes de la suite)

Tn = 4Tn−1 − 3Tn−2 + n, n ≥ 1, T0 = a, T−1 = 0 (2.15)

b) Calculez la fonction génératrice T (z) =∑

n≥0 Tnzn

c) (*) Obtenez la fonction génératrice T (z) directement, en appliquant la méthode desfonctions génératrices à l’équation (2.15).

Sol : a)

(a+ 3/4) 3n − 14(3 + 2n)

a+ 3/4

1− 3z− 1/4

1− z− 1/2

(z − 1)2=

a(z − 1)2 + z(z − 1)2(3z − 1)

Exercice 2.6.16

a) Obtenez une formule explicite pour la suite décrite par la relation de récurrence ci-dessous(et verifiez-la en utilisant les premiers termes de la suite)

Tn = 2Tn−1 − Tn−2 + 2, n ≥ 2, T0 = T1 = 0 (2.16)

b) Calculez la fonction génératrice T (z) =∑

n≥0 Tnzn

c) Obtenez la fonction génératrice T (z) directement, en appliquant la méthode des fonc-tions génératrices à l’équation (2.16)

Exercice 2.6.17 a) Obtenez la fonction génératrice T (z) =∑

n≥0 Tnzn pour la récurrence

Tn = λTn−1 + λ2Tn−2, n ≥ 2, T0 = 1, T1 = λT0 (2.17)

b) Calculez (directement, ou par developpement limité) le premiers termes, et verifiezqu’ils sont des combinaisons lineaires de puissances des racines charactèristiques.

32

2.6.10 Problèmes de premier passage sur un intervalle semi-infini

Soit ψn := limB→∞ an(B) la probabilité de ruine sur [0,∞). On vérifie facilement, enpartant des recurrences sur un domaine borné [0, B], que :

ψn = limB→∞

ψn,B =

{(q/p)n, q < p

1, q ≥ p.

Cette solution peut être trouvée aussi directement, sans passer par la probabilité deruine sur [0, B], en s’appuyant sur des des arguments probabilistes. On remarque d’abordque cette fonction est multiplicative en n, i.e. ψn = ρ

n, et en suite on choisit ρ selon la limitede Xn quand n→∞.

La solution la plus simple est en effet de remarquer que l’absence des sauts strictementplus grands que 1 implique une propriété de multiplicativité, ce qui impose une solutionpuissance. Mais, bien-sur, cette approche ne peut pas contribuer à l’étude des marches ”non-simples” dans les deux directions.

Examinons maintenant la méthode de fonctions génératrices (analogues à la transformée deLaplace), qui n’est pas réellement necessaire pour la marche simple, mais qui est la méthode la pluspuissante pour la resolution des èquations de differences (différentielles).

On ajoute les équations ψn = pψn+1 + qψn−1 multipliées respectivement par zn, n = 1, 2, .. On

obtient ainsi une èquation pour la fonction ψ∗(z) :=

∑∞n=1 z

nψn :

ψ∗(z) =

pψ1Φ(z)− 1

où Φ(z) = EzZ1 = pz−1 + qzDe lors,

ψ∗(z) =1

1− z− zpψ1p+ qz2 − z

=p− qz − pzψ1(1− z)(p− qz)

=p− qz − z(p− q)(1− z)(p− qz)

=p

p− qz

car le numerator s’annule en 1 (”méthode du noyau”) et donc pψ1 = p− q.De lors, ψn = (q/p)

n.

Exercice 2.6.18 Calculer les probabilités de ruine ψx, x ∈ N, pour une marche sur lesnombres naturelles, avec la distribution de chaque pas donné par :

{p1 =

810, p−1 =

110, p−2 =

110

}.

Montrer qu’elles sont positives.

R : La moyenne est m1 = 1/2 > 0. Les probabilités de ruine satisfont ψx =810ψx+1 +

110ψx−1 +

110ψx−2, x ∈ N. Elles sont des combinaisons de puissances ρx, avec ρ une racine de

8

10ρ3 − ρ2 + 1

10ρ+

1

10= (ρ− 1)( 8

10ρ2 − 2

10ρ− 1

10) =

8

10(ρ− 1)(ρ− 1/2)(ρ+ 1/4)

ψx = A1(12)x + A2(

−14)x satisfait ψ0 = ψ−1 = 1 ssi A1 = 5/6, A2 = 1/6. Les probabilités

de ruine sont :

ψx =5

6

(1

2

)x+

1

6

(−14

)x≈ 5

6

(1

2

)xExercice 2.6.19 Calculer les probabilités de ruine pour une marche avec

{p2 =

38, p1 =

18, p−1 =

12

}33

2.6.11 Les fonctions harmoniques des marches aléatoires de réseau(*)

Exercice 2.6.20 Quelle est la fonction harmonique de la marche aléatoire simple non-symmetrique sur les entiers {0, 1, ..., B}, arrêtée en 0, B ?

Rq : La simplicité du graphe ”série” de cette marche permet un calcul explicite.Q : Est-ce des formules en termes de la structure du graphe sont aussi disponibles pour les

fonctions harmoniques des marches aléatoires sur des graphes ponderés, avec des structuresplus compliqués ? Cette question a été beaucoup étudié en electricité, en començant avecKirchhoff.

Pour chaque x ∈ T = V −∂, soit V (x), les potentiels induites dans les noeuds du réseau.Alors, la loi des courants de Kirchhoff affirme que∑

y

V (y)− V (x)R(x, y)

= 0, ∀x ∈ T

Il est alors facile de verifier que les potentiels sont une fonction harmonique pour lamatrice stochastique P (x, y) = C(x,y)

cx. L’unicité des fonctions harmoniques ( !) nous assure

qu’en fait les deux concepts coincident !La simplication principale apportée par l’approche de Kirchhoff vient du concept de

résistance équivalente (l’idée étant de remplacer un réseau des resisteurs par un seul resis-teur), qui est particulièrement facile a calculer pour les réseaux séries-parralèle.

Exercice 2.6.21 Recalculer la fonction harmonique de la marche aléatoire simple non-symmetrique sur les entiers {0, 1, ..., B}, arrêtée en 0, B, à partir des lois de Kirchhoff.

Il est aussi possible de transformer une étoile à résistances A,B,C dans un triangle àrésistances x = A+B + AB

C, .... La transformation inverse est A = yz

x+y+z, ...

Exercice 2.6.22 Calculer la fonction harmonique de la marche aléatoire simple ”avec deuxbonheurs à la fin” {0, 1, 2, B1, B2}, et des exemples de fig II.3, II.5 de Bollobas.

Finalement, une formule trés intéressante nous fournit la probabilité d’arriver dans unensemble d’états de bonheur {B}, avant de revenir dans un état de depart a :

P [a− > {B}] := Pa[τ{B} < τ+a ] =1

daR(a↔ {B})

où R(a↔ {B}) denote la resistance equivalente.

Exercice 2.6.23 Calculer la probabilité du ”bonheur avant retour” pour les marche aléatoiresimple des exemples 2.5,2.6, 2.7 de Lyons et Peres.

Rq : Il y a plusieurs résultats plutot subtiles concernant l’ergodicité des châınes à espaced’états dénombrable, où le concept de resistance equivalente s’est avèré utile ; par exemple,les marches simples sur Zd sont récurrents ssi d ≤ 2.

En conclusion, les méthodes developpes par les physiciens pour calculer des potentielsen utilisant les transformations series/parallel et ”etoile triangle” pourront nous servir enprobabilités pour calculer les probabilités du bonheur et les fonctions harmoniques.

34

2.6.12 ExercicesExercice 2.6.24 On lance une monnaie biaisée, avec la probabilité de sortir face égale à qet celle de sortir pile égale à p = 1− q, jusqu’à ce qu’on obtient une pile. Soit N le nombrede faces précedant la première pile (N = 0, 1, 2, ...). Par exemple, si X1 = F, ...Xj−1 = F etXj = P, j ≥ 1, la valeur de N est j − 1.

1. Calculez pk = P [N ] = k, k = 0, .... Quelle est la loi (distribution) de N ?

2. Trouvez le moment m1 = EN par la méthode du conditionnement sur le premier pas,en utilisant la relation L(N |X1 = F ) = L(1 + N) (qui est une conséquence de ladécomposition ”premier pas + le reste”

N = 1 +N ′

et du fait que les distributions conditionnées par le premier pas du ”reste” N ′ sontconnues : a) (N ′|X1 = P ) ≡ 0 et b) L(N ′|X1 = F ) = L(N) par le fait que la seuledifference entre les réalisations possibles de N ′ et ceux de N est le moment ”de départde la montre”, qui n’affecte pas la distribution d’une châıne homogène).

3. Trouvez l’espérance m = EN (2) du nombre des essais jusqu’à ce qu’on obtient deuxpiles consécutives. Ind : Sauf m, il faudra trouver en même temps m1 = E1N (2) dunombre des essais jusqu’à ce qu’on obtient deux piles consécutives, à partir du momentqu’on a obtenu la première.

4. Généraliser pour k = 3 piles consécutives, et pour k arbitraire.

5. ”Mieux que les moments :” Trouvez la fonction génératrice des probabilités φ∗N(z) =EzN =

∑∞k=0 pkz

k, et deduisez l’espérance EN (en calculant φ′(1)), et aussi m2 = EN2.6. Soit k = 2. Abordez les mêmes questions pour φ∗

N(k)(z), ainsi que pour φ∗

N(k)′ (z), où

la dernière variable représente le nombre des essais jusqu’à ce qu’on obtient k pilesconsécutives, en incluant la suite finale des piles.

Trouver les probabilités P [N (2) = k] pour q = 1/3.

7. Reabordez la question precedente pour k = 3.

Solutions :

1. L’espace des experiments est : E = {P, FP, FFP, FFFP, ...} = {P} ∪ FE.pk = pq

k, k = 0, 1, .... On a à faire avec une distribution bien connue (la géométrique ! !).

2. Il est quand même intéressant de remarquer que l’espérance peut aussi se calculer parun conditionnement sur le premier pas :

m1 = p× 0 + q(1 +m1)⇐⇒ m1 =q

p

Note : Pour l’autre définition d’une variable g’eométrique N (1)′:= N + 1 ∈ {1, 2, ...}

(en incluant la première face), on obtient par le résultat précedent

n := EN (1)+1 = E(N + 1) =1

p,

ou encore par conditionnement sur le premier pas :

n = E[N (1)+1] = P[X1 = P ]E[N (1)+1|{X1 = P}] + P[X1 = F ]E[N (1)+1|{X1 = F}]= P[X1 = P ]1 + P[X1 = F ](1 + E[N (1)+1]) = p ∗ 1 + q ∗ (1 + n) = 1 + q ∗ n

35

3. Remarquons que les trois evenements PP, PP, (∗)P fournissent une decomposition del’espace d’états . Par conséquant :

n = q(n+ 1) + pq(n+ 2) + 0p2 ⇐⇒ n = q(1 + 2p)1− q − pq

=1 + p

p2− 2

4. Remarquons que les quatre evenements PPP, PPP, (∗)PP, (∗∗)P fournissent une de-composition de l’espace d’états qui permet soit de constater que notre evenementd’arrêt est arrivé, soit de relancer le processus du debut. Le conditionnement ces evene-

ments donne : n = q(n+1)+pq(n+2)+p2q(n+3)+0p2 ⇐⇒ n = q(1+2p+3p2)

p3= 1+p+p

2

p3−3

(et pour inclure les derniéres trois piles, on ajoute 3).

5. La méthode des fonctions génératrices.

Formellement, le calcul de EzN a remplaçè chaque terme de l’espace des experimentspar pnP qnF znF (nP = 1). Soit p(z) le résulat obtenu en ajoutant tous les termes.Observons qu’en rajoutan