Processus Stochastiques -...

Processus Stochastiques

Jean-Yves Tourneret(1)

(1) Université of Toulouse, ENSEEIHT-IRIT-TéSA

Thème 1 : Analyse et Synthèse de l’Information

jyt@n7.fr

Cours Mastère, 2010 – p. 1/29

Plan du cours

Chapitre 1 : Chaînes de Markov à états discrets

Chapitre 2 : Chaînes de Markov à états continus

Chapitre 3 : Méthodes de Simulation

Chapitre 4 : Suites Stationnaires

Stationnarité, Autocorrélation, Densité Spectrale dePuissance

Filtrage linéaire invariant dans le temps

Suites ARMA, AR et MA

Innovations, Théorème de Wold, Prédiction

Cours Mastère, 2010 – p. 2/29

Bibliographie

Peter J. Brockwell and Richard A. Davis, Time Series:Theory and Methods, Springer Verlag, 2nd edition, 1998.

Athanasios Papoulis and S. Unnikrishna Pillai, Probability,Random Variable and Stochastic Processes, McGraw HillHigher Education, 4th edition, 2002.

B. Porat, Digital Processing of Random Signal. Theoryand Methods, Prentice Hall, Englewood Cliffs, 1994.

Bernard Lacaze, Processus aléatoires pourcommunications numériques, Hermes SciencesPublications, 2000.

Cours Mastère, 2010 – p. 3/29

Stationnarité

Définition

E [xn] = µ

E[xnx∗

n−m

]= rx (m) , r(m)

Moyenne et fonction d’autocorrélation indépendantesdu temps.

ExemplesBruit blancEchantillonnage périodique d’un processus aléatoirestationnaire à temps continu

Cours Mastère, 2010 – p. 4/29

Propriétés de la fonction d’autocorrélation

Symétrie hermitienne

r∗(−m) = r(m)

Valeur à l’origine|r (m)| ≤ r (0)

Suite définie non négative

n∑

j,k=1

aja∗kr(j − k) ≥ 0, ∀n, aj , ak

Cours Mastère, 2010 – p. 5/29

Propriétés de la densité spectrale de puissance

Théorème d’Erglotzr (m) définie non négative si et ssi

r (m) =

∫ 1/2

−1/2e2iπmfdS(f)

où S(.) est une fonction continue à droite, non décroissante, bornée sur [−1/2, 1/2]

et telle que S(−1/2) = 0.

Densité spectrale de puissance s(f)

Si S(f) =∫ f−1/2 s(u)du, on a

r (m) =

∫ 1/2

−1/2e2iπmfs(f)df et s(f) =

∞∑

m=−∞

r (m) e−2iπmf

Preuve : voir polycopié ou livre de Brockwell and Davis.Cours Mastère, 2010 – p. 6/29

Filtrage linéaire invariant dans le temps

Définition

xn =∞∑

k=−∞

hken−k = hn ∗ en

CNS de Stabilité BIBO

∞∑

k=−∞

|hk| < ∞

Transmittance

H(f) =

∞∑

k=−∞

hke−j2πkf = TFD [hk] , −

1

2≤ f ≤

1

2

Cours Mastère, 2010 – p. 7/29

Relations de Wiener-Lee

Densité spectrale de puissance

sx (f) = se (f) |H (f)|2 avec H(f) =∞∑

k=−∞

hke−j2πkf

Intercorrélation

rxe (k) = E[xne∗n−k

]= h(k) ∗ re(k)

Formule des Interférences

ryz (k) = E[ynz∗n−k

]

=

∫ 1

2

− 1

2

H (f) G∗ (f) ej2πkfse (f) df

Cours Mastère, 2010 – p. 8/29

Preuve

Autocorrélation

rx (k) = E

∑

i∈Z

hien−i

∑

j∈Z

h∗je

∗n−k−j

=∑

i∈Z

∑

j∈Z

hih∗jE[en−ie

∗n−k−j

]

=∑

i∈Z

∑

j∈Z

hih∗jre (k + j − i)

Cours Mastère, 2010 – p. 9/29

Preuve

Densité Spectrale de Puissance

sx (f) =∑

k∈Z

rx (k) e−j2πkf

=∑

i∈Z

∑

k∈Z

hih∗k

{∑

l∈Z

re (l + k − i) e−j2πlf

}

=∑

i∈Z

∑

k∈Z

hih∗k

{∑

m∈Z

re (m) e−j2π(m+i−k)f

}

=∑

i∈Z

∑

k∈Z

hih∗kse (f) e−j2π(i−k)f

= se (f) |H (f)|2

Cours Mastère, 2010 – p. 10/29

Preuve

Intercorrélation

rxe (k) = E

[(∞∑

l=−∞

hlen−l

)e∗n−k

]

=∞∑

l=−∞

hlE[en−le

∗n−k

]

=∞∑

l=−∞

hlre(k − l)

= h(k) ∗ re(k)

Cours Mastère, 2010 – p. 11/29

Retour sur les chaînes de Markov

Le spectre d’une chaîne de Markov est une fractionrationnelle en e−2iπf . En effet, pour k ≥ 0, on a

r(k) = E [xnxn+k]

=∑

a,b

abP [xn = a, xn+k = b]

=∑

a,b

abP [xn+k = b|xn = a] P [xn = a]

=∑

a,b

(aP [xn = a]) bp(k)ab = [...]P k[

...]

=l∑

i=1

aiλ|k|i

Cours Mastère, 2010 – p. 12/29

Exemple

Chaîne de Markov stationnaire de matrice de transition

P =

1/3 2/3 0

1/3 0 2/3

2/3 0 1/3

associée à trois états {0, 1,−1} de probabilités initialeségales aux probabilités limites

[37 , 2

7 , 27

].

Cours Mastère, 2010 – p. 13/29

Suite ARMA

Définition

p∑

k=0

akxn−k =

q∑

k=0

bken−k

où ak et bk, k = 0, ..., n sont des nombres réels et où en

est un bruit blanc (E(en) = 0 et E(e2n) = σ2

e ).

Remarquesa0 = b0 = 1

Suites AR et MAOn suppose que B(z) et A(z) n’ont pas de zéroscommuns, ou alors on simplifie.Approximation du spectre d’une suite stationnaire

Cours Mastère, 2010 – p. 14/29

Densité spectrale de puissance

Transmittance

H(z) =X(z)

E(z)=

∑qk=0 bkz

−k

∑pk=0 akz−k

Wiener-Lee

sx(f) = σ2e

∣∣∣∣∣

∑qk=0 bke

−j2πkf

∑pk=0 ake−j2πkf

∣∣∣∣∣

2

La densité spectrale de puissance d’une suite ARMAest une fraction rationnelle en e−j2πf .

Cours Mastère, 2010 – p. 15/29

La solution

Expression de xn en fonction de en

AR(1)xn = axn−1 + en avec |a| < 1

AR(1)xn = axn−1 + en avec |a| > 1

Cas généralOn montre qu’il existe une solution stationnaireinversible, i.e., x(n) =

∑∞k=0 hke(n − k) si et ssi H(z)

a tous ses pôles à l’intérieur du cercle unité.Lorsqu’il n’y a pas de pôle sur le cercle unité, ilexiste une solution stationnaire de la forme

x(n) =∞∑

k=−∞

hke(n − k)Cours Mastère, 2010 – p. 16/29

Autocorrélations dans le cas causal

Équations de Yule-Walker

p∑

k=0

akr (i − k) =

q∑

k=0

bkE [xn−ien−k] ,

avec xn =∑∞

j=0 hjen−j.

i ≥ q + 1p∑

k=0

akr (i − k) = 0 ⇔ r(i) =

p∑

k=1

akr (i − k)

i ∈ {0, ..., q}

r(i) =

p∑

k=1

akr (i − k) + σ2e

q∑

k=i

bkhk−i

Cours Mastère, 2010 – p. 17/29

Autocorrélations d’une suite AR causale

i ≥ 1

r(i) =

p∑

k=1

akr (i − k)

i = 0

r(0) =

p∑

k=1

akr (−k) + σ2e

=

p∑

k=1

akr (k) + σ2e

Cours Mastère, 2010 – p. 18/29

Autocorrélations d’une suite MA causale

i ≥ q + 1

r(i) = 0

i ∈ {0, ..., q}

r(i) = σ2e

q∑

k=i

bkbk−i = σ2e (b0bi + b1bi+1 + ... + bq−ibq)

On notera en particulier que r(q + 1) = 0 et que

r(q) = b0bq = bq 6= 0

Ces deux dernières relations seront pratiques pourdéterminer l’ordre du modèle MA.

Cours Mastère, 2010 – p. 19/29

Résumé Suites Stationnaires

Autocorrélation-Densité spectrale

r (m) =

∫ 1/2

−1/2e2iπmfs(f)df et s(f) =

∞∑

m=−∞

r (m) e−2iπmf

Filtrage LinéaireRelation entrée-sortie X(f) = H(f)E(f)

DSP sortie sx(f) = se(f)|H(f)|2

Intercorrélation rxe(k) = h(k) ∗ re(k)

Autocorrélations d’une chaîne de Markov

r(k) =l∑

i=1

aiλ|k|i

Cours Mastère, 2010 – p. 20/29

Résumé Suites ARMA

Définitionp∑

k=0

akxn−k =

q∑

k=0

bken−k

Transmittance

H(z) =B(z)

A(z)

Densité spectrale de puissance

sx(f) = σ2e

∣∣∣∣∣

∑qk=0 bke

−j2πkf

∑pk=0 ake−j2πkf

∣∣∣∣∣

2

Cours Mastère, 2010 – p. 21/29

Résumé Suites ARMA

Solutionpôles à l’intérieur du cercle unité ⇔ solutionstationnaire causalepôles à l’extérieur du cercle unité ⇔ solutionstationnaire anti causale

Autocorrélations dans le cas causalpeuvent se déterminer à l’aide des équations deYule-Walkerpermettent d’estimer les paramètres de la suiteARMA

Cours Mastère, 2010 – p. 22/29

Innovations d’une suite stationnaire (E[xt] = 0)

DéfinitionHn le sous espace engendré par {xt,t ≤ n} (le passé etle présent de xn). L’ innovation de xn est définie par

un = xn − PHn−1(xn) = xn − x̂n.

Propriétésun ∈ Hn

La suite des innovations {un, n ∈ Z} est constituéede variables aléatoires non-corrélées (orthogonales)la suite {un, n ∈ Z} est une suite stationnaire demoyenne nulle et de variance finie

Cours Mastère, 2010 – p. 23/29

Suites déterministes et régulières

Suites déterministes

σ2 = E[|xn − x̂n|

2]

= 0 ⇒ un = 0 p.s.

Suite parfaitement prédictible à partir de son passé

xn = x̂n = −∞∑

k=1

αkxn−k

Ex. : xn = A cos(2πf0n + θ) = 2 cos(2πf0)xn−1 − xn−2.

Suites régulières

σ2 = E[|xn − x̂n|

2]6= 0.

Normalisation : E[u2(n)] = 1, Exemple : suite ARMA.Cours Mastère, 2010 – p. 24/29

Décomposition de Wold

Toute suite stationnaire de moyenne nulle s’écrit

xn = yn + vn =∞∑

s=0

βsun−s + vn, où

(a) un et vn sont des suites décorrélées

E [vmun] = 0, ∀n,m

(b) un est l’innovation appartenant à Hn

(c) vn est une variable aléatoire appartenant à H−∞,

(d) vn est une suite déterministe

(e) yn est une suite régulière

Cours Mastère, 2010 – p. 25/29

Cas particuliers

Suites déterministes (xn = vn)xn = α ⇒ x̂n = E [xn| xn−1, xn−2, ...] = α = xn, i.e.,un = 0.xn = A cos (2πf0n + θ) = 2 cos (2πf0) xn−1 − xn−2, i.e.,un = 0.

Bruit blanc

x̂n = E [xn| xn−1, xn−2, ...] = E [xn] = 0 ⇒ un = xn−x̂n = xn

Cours Mastère, 2010 – p. 26/29

Décomposition de Wold d’une suite ARMA

Résultat fondamental

xn =

∞∑

s=0

βsun−s

i.e., filtrage causal des innovations (donc les pôles deβ(z) sont tous à l’intérieur du cercle unité).

InversibilitéSi les pôles et zéros de β(z) ne sont pas sur le cercleunité, alors

un =∞∑

s=0

αsxn−s

avec pôles de α(z) (zéros de β(z)) à l’intérieur du cercleunité.

Cours Mastère, 2010 – p. 27/29

Exemples de décompositions de Wold

Suites AR(1)xn = axn−1 + en avec |a| < 1

xn = axn−1 + en avec |a| > 1

Suites MA(1)xn = en − aen−1 avec |a| < 1

xn = en − aen−1 avec |a| > 1

Cours Mastère, 2010 – p. 28/29

Prédiction

On observe une suite stationnaire aux instants t ≤ 0 et oncherche à estimer xn avec n > 0 à l’aide du meilleurestimateur linéaire à partir des éléments {x0, x−1, ...}. Lasolution de ce problème est immédiate dans le cas oùvn = 0 dans la décomposition de Wold (e.g., suites ARMA).En effet, à partir de

xn =

∞∑

s=0

βsun−s

puisque les innovations sont orthogonales, on a

x̃n = PH0(xn) =

∞∑

s=n

βsun−s.

Erreur de prédiction : σ2n = E

[|xn − x̃n|

2]

=∑n−1

s=0 β2s .

Cours Mastère, 2010 – p. 29/29