1. Time series

Fourier Analysis of Stochastic Processes

1. Time series

Given a discrete time process (X _n ) _n2Z , with X _n : ! R or X n : ! C 8n 2 Z, we de…ne time series a realization of the process, that is to say a series (x n ) _n2Z of real or complex numbers where x _n = X _n (!)8n 2 Z. In some cases we will use the notation x(n) instead of x n , with the same meaning.

For convenience, we introduce the space l 2 of the time series such that P

n2Z jx ⁿ j ² < 1. The …nite value of the sum can be sometimes interpreted as a form of the energy, and the time series belonging to l 2 are called …nite energy time series. Another important set is the space l 1 of the time series such that P

n2Z jx ⁿ j < 1. Notice that the assumption P

n2Z jx ⁿ j < 1 implies P

n2Z jx ⁿ j ² < 1, because P

n2Z jx ⁿ j ² sup _n2Z jx ⁿ j P

n2Z jx ⁿ j and sup _n2Z jx ⁿ j is bounded when P

n2Z jx ⁿ j converges.

Given two time series f (n) and g(n), we de…ne the convolution of the two time series as h(n) = (f g)(n) = X

k2Z

f (n k) g (k)

2. Discrete time Fourier transform

Given the realization of a process (x _n ) _n2Z 2 l 2 , we introduce the discrete time Fourier transform (DTFT), indicated either by the notation b x (!) or F [x] (!) and de…ned by

b

x (!) = F [x] (!) = 1 p 2

X

n2Z

e ^i!n x _n ; ! 2 [0; 2 ] :

Note that the symbol b is used to indicate both DTFT and empirical estimates of process parame- ters; the variable ! is used to indicate both the independent variable of the DTFT and the outcomes (elementary events) in a set of events. Which of the two meanings is the correct one will be always evident in both cases.

The sequence x _n can be reconstructed from its DTFT by means of the inverse Fourier transform x _n = 1

p 2 Z 2

0

e ^i!n x (!) d!: b

In fact, assuming that it is allowed to interchange the in…nite summation with the integration, we have p 1

2 Z 2

0

e ^i!n x (!) d! = b 1 2

Z 2 0

e ^i!n X

k2Z

x _k e ^i!k d! = 1 2

X

k2Z

x _k Z 2

0

e ^{i!(n k)} d! = 1 2

X

k2Z

x _k 2 (n k) = x _n Remark 1. In the de…nition using i!n as exponent, the increment of the independent variable between two consecutive samples is assumed to be 1. If the independent variable is time t and the

i

time interval between two consecutive samples is t, in order to change the time scale, the exponent becomes i!n t. The quantity 1

t is called sampling frequency.

Remark 2. The function b x (!) can be considered for all ! 2 R, but it is 2 -periodic or 2

t -periodic.

In the last case, ! is called angular frequency.

Remark 3. Sometimes (in particular by physicists), DTFT is de…ned without the sign at the exponent; in this case the sign is obviously present in the inverse transform.

Remark 4. Sometimes the factor ^{p 1} ₂ is not included in the de…nition; in our de…nition the factor

p 1

2 is included for symmetry with the inverse transform or the Plancherel formula (without p ¹ 2 , a factor ₂ ¹ appears in one of them).

Remark 5. Sometimes, it is preferable to use the variant b

x (f ) = 1 p 2

X

n2Z

e ^{2 if n} x _n ; f 2 [0; 1] :

where f = !

2 . When the factor t is present in the exponent, f 2 0; 1

t is called frequency.

In the following, we will use our de…nition of DTFT, independently of the fact that in certain applications it is customary or convenient to make other choices. The reader is warned!!

Of course, in practical cases, in…nite sampling times do not exist. Let us therefore introduce a sampling window of width 2N contaning 2N + 1 samples from time N to time N (also called boxcar window) 1 _{[ N;N ]} (n) =

( 1 if N n N

0 otherwise and the truncation x 2N (n) of the time series x n de…ned as x _2N (n) = x _n 1 _{[ N;N ]} (n) =

( x _n if N n N

0 otherwise . The DTFT of the truncated time series is de…ned as

b

x _2N (!) = 1 p 2

X

jnj N

e ^i!n x _n :

Remark 6. In order to de…ne properly the DTFT for a process, we must assure that it is possible to calculate the DTFT of “every” of its realization. Therefore the above de…nition, involving only a

…nite summation, can be used also to de…ne the truncated DTFT of a process:

X b 2N (!) = 1 p 2

X

jnj N

e ^i!n X n :

In fact, each realization x b 2N of a truncated process b X 2N is a …nite-energy time series that admits

DTFT. We underline that b X _2N (!) is a random variable for every ! 2 [0; 2 ], while b x _2N (!) is a

function of !. The de…nition of truncated DTFT for a process will be used in the proof of Wiener-

Khinchine theorem. Processes whose realizations are l ₂ or l ₁ time series are never stationary.

2. DISCRETE TIME FOURIER TRANSFORM iii

Properties of DTFT

1) The L ² -theory of Fourier series guarantees that the series P

n2Z e ^i!n x _n converges in mean square with respect to !, namely, there exists a square integrable function x (!) such that b

N !1 lim Z 2

0 jb x _2N (!) x (!)j b ² d! = 0:

2) Plancherel formula

X

n2Z

jx ⁿ j ² = Z 2

0 jb x (!)j ² d!

Proof.

Z 2

0 jb x (!)j ² d! = Z 2

0 b x (!) ( x (!)) d! = b 1 2

Z 2 0

X

n2Z

e ^i!n x _n

! X

m2Z

e ^i!m x _m

! d! = 1

2 Z 2

0

0

@ X

n;m2Z

x n x _m e ^i!n e ^i!m 1

A d! = 1 2

X

n;m2Z

x n x _m Z 2

0

e ^{i!(n m)} d! = 1 2

X

n;m2Z

x n x _m 2 (n m) = X

n2Z

x n x _n = X

n2Z

jx ⁿ j ² assuming that it is correct to interchange the in…nite summation with the inte- gration.

The meaning of Plancherel formula is that the energy “contained”in a time series and the energy

“contained” in its DTFT is the same (a factor 2 can appear in one of the two members when a di¤ernt detinition of DTFT is used).

3) If the time series g(n) is real, then bg ( !) = bg (!).

Proof. bg ( !)= 1 p 2

X

n2Z

g(n)e ^{i( !)n} = 1 p 2

X

n2Z

g(n) e ^i!n = 1 p 2

X

n2Z

g(n)e ^i!n

!

= g (!)

4) The DTFT of the convolution of two time series corresponds (a factor can be present,depending on the de…nition of DTFT) to the product of the DTFT of the two time series

F [f g] (!) = p

2 b f (!) bg (!) : Proof. F[f g] (!) = 1

p 2 X

n2Z

(f g)(n)e ^i!n = 1 p 2

X

n2Z

X

k2Z

f (n k)g(k)

!

e ^i!n = p 1

2 X

k2Z

g(k)e ^i!k X

n2Z

f (n k)e ^{i!(n k)} = 1 p 2

X

k2Z

g(k)e ^i!k X

m2Z

f (m)e ^i!m = X

k2Z

g(k)e ^i!k f (!) = b p 2 b f (!) bg(!), assuming that it is correct to commute the two in…nite summations. The p

2 is not present when the de…nition of DTFT without p ¹

2 is used.

6) Combining properties 4) and 5), we obtain F

"

X

k2Z

f (n + k) g (k)

#

(!) = F

"

X

k2Z

f (n k) g ( k)

#

(!) = b f (!) bg( !) = p

2 b f (!) bg (!), where

the last equality is valid only for a real time series g. This property is used in the calculation of DTFT of correlation function. Again, the presence of factor p

2 depends on the de…nition of DTFT adopted.

7) When X

n2Z

jx n j < 1, then the series P

n2Z e ^i!n x _n is absolutely convergent, uniformly in ! 2 [0; 2 ], simply because

X

n2Z

sup

!2[0;2 ]

e ^i!n x n = X

n2Z

sup

!2[0;2 ]

e ^i!n jx ⁿ j = X

n2Z

jx ⁿ j < 1:

In this case, we may also say that x (!) is a bounded continuous function, not only square integrable. b 3. Generalized discrete time Fourier transform

One can do the DTFT also for sequences which do not satisfy the assumption P

n2Z jx ⁿ j ² < 1, in special cases. Consider for instance the sequence

x _n = a sin (! ₁ n) : Compute the DFTT of the truncated sequence

b

x 2N (!) = 1 p 2

X

jnj N

e ^i!n a sin (! 1 n) : Recall that

sin t = e ^it e ^it 2i : Hence sin (! 1 n) = ^e

^i!1n

_2i ^e

^i!1n

X

jnj N

e ^i!n a sin (! 1 n) = 1 2i

X

jnj N

e ^{i(! !}

¹

⁾ⁿ 1 2i

X

jnj N

e ^i(!+!

¹

⁾ⁿ :

The next lemma makes use of the concept of generalized function or distribution, which is outside the scope of these notes. We still given the result, to be understood in some intuitive sense. We use the generalized function (t) called Dirac delta (not to be confused with the dircrete time de…ned in example 1 for white noise), which is characterized by the property

(3.1)

Z ₁

1

(t t ₀ ) f (t) dt = f (t ₀ )

for all continuous compact support functions f . No usual function has this property. A way to get intuition is the following one. Consider a function _n (t) which is equal to zero for t outside _2n ¹ ; _2n ¹ , interval of length _n ¹ around the origin; and equal to n in _2n ¹ ; _2n ¹ . Hence _n (t t ₀ ) is equal to zero for t outside t 0 1

2n ; t 0 + _2n ¹ , equal to n in t 0 1

2n ; t 0 + _2n ¹ . We have Z ₁

1

n (t) dt = 1:

3. GENERALIZED DISCRETE TIME FOURIER TRANSFORM v

Now, Z ₁

1

n (t t ₀ ) f (t) dt = n

Z t

0

+

_2n¹

t

0 1

2n

f (t) dt

which is the average of f around t ₀ . As n ! 1, this average converges to f (t 0 ) when f is continuous.

Namely. we have

n!1 lim Z ₁

1

n (t t ₀ ) f (t) dt = f (t ₀ )

which is the analog of identity (3.1), but expressed by means of traditional concepts. In a sense, thus, the generalized function (t) is the limit of the traditional functions n (t). But we see that n (t) converges to zero for all t 6= 0, and to 1 for t = 0. So, in a sense, (t) is equal to zero for t 6= 0, and to 1 for t = 0; but this is a very poor information, because it does not allow to deduce identity (3.1) (the way n (t) goes to in…nity is essential, not only the fact that (t) is 1 for t = 0).

Lemma 1. Denote by (t) the generalized function such that Z ₁

1

(t t ₀ ) f (t) dt = f (t ₀ )

for all continuous compact support functions f (it is called the delta Dirac distribution). Then

N !1 lim X

jnj N

e ^itn = 2 (t) : From this lemma it follows that

N !1 lim X

jnj N

e ^i!n a sin (! ₁ n) =

i (! ! ₁ )

i (! + ! ₁ ) : In other words,

Corollary 1. The sequence

x n = a sin (! 1 n) has a generalized DTFT

b

x (!) = lim

N !1 x b _2N (!) = p

p 2i ( (! ! ₁ ) (! + ! ₁ )) :

This is only one example of the possibility to extend the de…nition and meaning of DTFT outside the assumption P

n2Z jx ⁿ j ² < 1. It is also very interesting for the interpretation of the concept of DTFT. If the signal x _n has a periodic component (notice that DTFT is linear) with angular frequency

! 1 , then its DTFT has two symmetric peaks (delta Dirac components) at ! 1 . This way, the DTFT reveals the periodic components of the signal.

Exercise 1. Prove that the sequence

x _n = a cos (! ₁ n) has a generalized DTFT

b

x (!) = lim

N !1 x b _2N (!) = p

p 2 ( (! ! ₁ ) + (! + ! ₁ )) :

4. Power spectral density

Given a stationary process (X n ) _n2Z with correlation function R (n) = E [X n X 0 ], n 2 Z, we call power spectral density (PSD ) the function

S (!) = 1 p 2

X

n2Z

e ^i!n R (n) ; ! 2 [0; 2 ] : Alternatively, one can use the expression

S (f ) = 1 p 2

X

n2Z

e ^{2 if n} R (n) ; f 2 [0; 1]

which produces easier visualizations because we catch more easily the fractions of the interval [0; 1].

Remark 7. In principle, to de…ne properly the PSD, the condition P

n2Z jR (n)j < 1 should be required, or at least P

n2Z jR (n)j ² < 1. In practice, on a side the convergence may happen also in unexpected cases due to cancellations, on the other side it may be acceptable to use a …nite-time variant, something like P

jnj N e ^i!n R (n), for practical purposes or from the computational viewpoint.

A priori, one may think that S (f ) may be not real valued. However, the function R (n) is non- negative de…nite (this means P n

i=1 R (t _i t _j ) a _i a _j 0 for all t ₁ ; :::; t _n and a ₁ ; :::; a _n ) and a theorem states that the Fourier transform of non-negative de…nite function is a non-negative function. Thus, at the end, it turns out that S (f ) is real and also non-negative. We do not give the details of this fact here because it will be a consequence of the fundamental theorem below.

4.1. Example: white noise. We have

R (n) = ² (n) hence

S (!) =

2

p 2 ; ! 2 R:

The spectra density is constant. This is the origin of the name, white noise.

4.2. Example: perturbed periodic time series. This example is numeric only. Produce with R software the following time series:

t <- 1:100

y<- sin(t/3)+0.3*rnorm(100)

ts.plot(y)

4. POWER SPECTRAL DENSITY vii

The empirical autocorrelation function, obtained by acf(y), is

and the power spectral density, suitable smoothed, obtained by spectrum(y,span=c(2,3)), is

4.3. Pink, Brown, Blue, Violet noise. In certain applications one meets PSD of special type which have been given names similarly to white noise. Recall that white noise has a constant PSD.

Pink noise has PSD of the form

S (f ) 1 f : Brown noise:

S (f ) 1 f ² : Blue noise

S (f ) f 1 : Violet noise

S (f ) f ² 1 :

where, chosen such that 0 < < 1, 1 (f ) = 1 if 0 f

0 otherwise

5. A fundamental theorem on PSD

The following theorem is often stated without assumptions in the applied literature. One of the reasons is that it can be proved under various level of generality, with di¤erent meanings of the limit operation (it is a limit of functions). We shall give a rigorous statement under a very precise assumption on the autocorrelation function R (n); the convergence we prove is rather strong. The assumption (a little bit strange, but satis…ed in all our examples) is

(5.1) X

n2N

R (n) ^p < 1 for some p 2 (0; 1) : This is just a little bit more restrictive than the condition P

n2N jR (n)j < 1 which is natural to impose if we want uniform convergence of p ¹

2

P

n2Z e ^i!n R (n) to S (!).

Theorem 1 (Wiener-Khinchin). If (X (n)) _n2Z is a wide-sense stationary process satisfying as- sumption (5.1), then

S (!) = lim

N !1

1

2N + 1 E X b _2N (!) ² :

The limit is uniform for ! 2 [0; 2 ]. Here X ^2N is the truncated process X 1 _{[ N;N ]} . In particular, it follows that S (!) is real an non-negative.

Proof. Step 1. Let us prove the following main identity:

(5.2) S (!) = 1

2N + 1 E X b _2N (!) ² + r _N (!) where the remainder r _N is given by

r N (!) = 1 2N + 1 F

2

4 X

n2 (N;t)

E [X (t + n) X (n)]

3 5 (!)

and (N; t) is a subinterval of [ N; N ] to be de…ned later. Since R (t) = E [X (t + n) X (n)] for all n, we obviously have, for every t,

R (t) = 1 2N + 1

X

jnj N

E [X (t + n) X (n)] : Thus

(5.3)

S (!) = b R (!) = 1 2N +1 F

2

4 X

jnj N

E [X (t + n) X (n)]

3

5(!)= 1 2N +1

X

jnj N

X

t2Z

[E [X (t + n) X (n)]] e ^i!t To invert the in…nite sum over t with the calculation of mean value, we need to introduce truncated process X _2N (n) = X(n) 1 _{[ N;N ]} (n), for which we have, for 0 t 2N

X

n2Z

X _2N (t + n) X _2N (n) =

N X t n= N

X (t + n) X (n) ;

5. A FUNDAMENTAL THEOREM ON PSD ix

for 2N t < 0 ve have X

n2Z

X _2N (t + n) X _2N (n) = X N n= N t

X (t + n) X (n) ;

for t > 2N or t < 2N , we have X _2N (t + n) X _2N (n) = 08n. In general, X

n2Z

X _2N (t + n) X _2N (n) = X

n2[N

t

;N

_t⁺

]

X (t + n) X (n) :

with

[N _t ; N _t ⁺ ] = 8 >

> <

> >

:

; if t < 2N

[ N t; N ] if 2N t < 0 [ N; N t] if 0 t 2N

; if t > 2N Therefore, remembering property 6) of DTFT,

F 2 4

N

_t⁺

X

n=N

_t

X (t + n) X (n) 3

5 (!) = F

"

X

n2Z

X _2N (t + n) X _2N (n)

#

(!) = b X _2N (!) b X _2N (!) = b X _2N (!) ² :

Taking the mean value of …rst and last term, we obtain

F 2 4

N

_t⁺

X

n=N

_t

E [X (t + n) X (n)]

3

5 (!) = E 2 4F

2 4

N

_t⁺

X

n=N

_t

X (t + n) X (n) 3 5 (!)

3

5 = E X b 2N (!) ² :

Now, it is possible to decompose the sum running from N to +N into a sum running from N _t to N _t ⁺ and a remainder r _N containing the other terms, from N to N _t or from N _t ⁺ to N .

S(!) = 1

2N + 1 F 2

4 X

jnj N

E [X (t + n) X (n)]

3

5 (!) = 1

2N + 1 F 2 4

N

_t⁺

X

n=N

_t

E [X (t + n) X (n)]

3 5 (!) +

1 2N + 1 F

2

4 X

n2 (N;t)

E [X (t + n) X (n)]

3

5 (!) = 1

2N + 1 E X b _2N (!) ² + r _N (!) ; with

(N; t) = 8 >

> >

> >

> <

> >

> >

> >

:

[ N; N ] if t < 2N [ N; N t 1] if 2N t < 0

; if t = 0

[N t + 1; N ] if 0 < t 2N

[ N; N ] if t > 2N

Step 2. The proof is complete if we show that lim _{N !1} r N (!) = 0 uniformly in ! 2 [0; 2 ]. Let

" _n = R (n) ^{1 p} . As P

n2N R (n) ^p < 1, we have R (n) ^p ! 0, and therefore also " n ! 0. Moreover, X

n2N

R (n)

" _n = X

n2N

R (n) ^p < 1:

We can write

X

n2 (N;t)

E [X (t + n) X (n)] = X

n2 (N;t)

R (t) = " _jtj R (t)

" _jtj j (N; t)j

where j (N; t)j denotes the cardinality of (N; t). If (2N + 1)^jtj denotes the smallest value between (2N + 1) and jtj, we have

j (N; t)j = (2N + 1) ^ jtj hence

1 2N + 1

X

n2 (N;t)

E [X (t + n) X (n)] = jR (t)j

" _jtj

((2N + 1) ^ jtj) " _jtj

2N + 1 :

Given > 0, let t 0 be such that " _jtj for all t t 0 . Then take N 0 t 0 such that _{2N +1} ^t

⁰

for all N N 0 . It is not restrictive to assume " _jtj 1 for all t. Then, for N N 0 , if t t 0 then

((2N + 1) ^ jtj) " jtj

2N + 1

t 0 " _jtj 2N + 1

t 0

2N + 1 and if t t ₀ then

((2N + 1) ^ jtj) " jtj

2N + 1

((2N + 1) ^ jtj)

2N + 1 :

We have proved the following statement: for all > 0 there exists N 0 such that ((2N + 1) ^ jtj) " jtj

2N + 1 for all N N ₀ , uniformly in t. Then also

1 2N + 1

X

n2 (N;t)

E [X (t + n) X (n)] jR (t)j

" _jtj for all N N ₀ , uniformly in t. Therefore

jr N (!)j = 1 2N + 1

p 1 2

X

t2Z

e ^i!t 2

4 X

n2 (N;t)

E [X (t + n) X (n)]

3 5

1 2N + 1

p 1 2

X

t2Z

X

n2 (N;t)

E [X (t + n) X (n)] 1 p 2

X

t2Z

jR (t)j

" _jtj = C p 2 where C = P

t2Z jR(t)j

"

_jtj

< 1. This is the de…nition of lim N !1 r _N (!) = 0 uniformly in ! 2 [0; 2 ].

The proof is complete.

5. A FUNDAMENTAL THEOREM ON PSD xi

This theorem gives us the interpretation of PSD. The Fourier transform b X T (!) identi…es the frequency structure of the signal. The square X b _T (!) ² drops the information about the phase and keeps the information about the amplitude, but in the sense of energy (a square). It gives us the energy spectrum, in a sense. So the PSD is the average amplitude of the oscillatory component at frequency f = ₂ ^! .

Thus PSD is a very useful tool if you want to identify oscillatory signals in your time series data and want to know their amplitude. By PSD, one can get a "feel" of data at an early stage of time series analysis. PSD tells us at which frequency ranges variations are strong.

Remark 8. A priori one could think that it were more natural to compute the Fourier transform X (!) = b P

n2Z e ^i!n X _n without a cut-o¤ of size 2N . But the process (X _n ) is stationary. Therefore, it does not satisfy the assumption P

n2Z X _n ² < 1 or similar ones which require a decay at in…nity.

Stationarity is in contradiction with a decay at in…nity (it can be proved, but we leave it at the obvious intuitive level).

Remark 9. Under more assumptions (in particular a strong ergodicity one) it is possible to prove that

S (!) = lim

N !1

1

2N + 1 X b 2N (!) ²

without expectation. Notice that _{2N +1} ¹ X b _2N (!) ² is a random quantity, but the limit is deterministic.