Information theory for continuous systems

then h(Y)

= h(X)

+ log |det A\,

(1.3.12)

where u>i(x) = £ j O i y i j , i = 1,-..,<*, and A = ( a ; , k j = i *• (h.3) Let p ( x ) and g(y) be
h( ) = - /

p(x)logp(x)dx<^ /

P

JR."

p(x)log,(x)dx,

(1.3.13)

JR'

w i t h equality if and only if p(x) — g(x). n(A", Y) = h{Y)

(h.4)

+ h{X\Y)

h{X\Y Yi)

(h.5)

= h(X)

< h(X\Y,)

u

h{Y\X).

+

<

h'X).

The first inequality turns into equality i f and only if Y

2

is independent of X when

Y\ is given, and the second inequality turns into equality if and only i f V] is independent of X. n h(X ,...,X„)

(h.6)

1

n

=

Y H *\Xn-,Xk- )
The equality holds if and only i f X,,X„ (h.7)

Proof,

(h.l)

n

l

l l

l

h X

are mutually independent.

/ (x,,...,A- |y) = ^ / ( x | y x i

x

1

1

.*•*_,) < £ h ( x | r ) . t

Example 1.3.1 provides an example of a random variable w i t h

negative continuous entropy.

1.3 ENTROPY

(h.2)

FOR CONTINUOUS

19

DISTRIBUTIONS

For any Borel set V C R , we have d

P(Y e r ) = P{x

e
P

( x ) d x = / pW.y))\J(y)\ dy,

where i£(T) = {i/>(y); y € I"). This means that Y has the probability density function p(^>(y))j J(y)|. HY)

Consequently

= -

f

p(^(y))|/(y)|log[ W ))|J(y)|] f P

P X

=

y

x

h(X)-jp(x)\ \J(
Thus (1.3.11) is obtained. 1

I

j ( )\og\pW\J(
= -

detA"

y

X

I f

Then J"(y) —

= 1/det A, and (1.3.12) follows from (1.3.11).

Property (h.3) can be proved i n the same way as (H.6) of Theorem 1.2.1, replacing the summations w i t h the integrations. (h.4)

Noting that / r ( x , y ) d x = ?(y), we have h{X, Y) = - jj — h{X\Y)

r(x, y ) l o

g g

( y ) dxdy

4- h(Y).

The equation h(X, Y) — h(Y\X) (h.5)

d x d y - jj

r ( x , y ) log

+ h{X) can be shown in the same way.

Denote by ? i ( y i ) , « ( y i , y j ) , p ( x , y , ) , r ^ y , ^ ) the density functions

of Yi, (YuY,),

( - f , K , ) , {X,Y,,Y }. 2

Then using (h.3) we obtain
2

dyidy = -

=

ffpi^y^og^^dxdy,

hiXlY,)-

Here the equality holds if and only i f T-(x,yi,y )/q(y y ) 2

u

= p(x,yi)/si(yi).

2

condition is rewritten as r{x,yi,yg) 5i(yi)

=

g(yi,y2)p(x,y ) l

?i{yi)

2

5i(yi) '

This

20

ENTROPY

meaning that Y is conditionally independent of X when Yt is given. The second 2

inequality can be shown i n the same way. (h.6)

By (h.4), h(X X ,...,X ) u

2

= hiX )

n

+ k(X

1

X \Xt).

2

n

In the same manner as i n the proof of (h.4), we can show h{X ,....

X \X,)

2

a

= k(X \X ) 2

t

+

h(X ,X \X X ). 3

n

u

2

Repeating the same arguments, we have n

h(X, ,x ,...,x ) 2

n

= Yl ( *

The inequality of (h.6) is clear from (h.5). h{X \X -,X -i) t

u

X\,...,X„

-

k

h(X ) k

for all k =

)•

h x

The equality holds i f and only if l,...,n.

This occurs i f and only if

are mutually independent.

Finally (h.7) can be proved similarly to (h.6).

•

As was mentioned earlier, the difference of continuous entropies is a natural extension of that in the case of discrete distributions. The properties (h.3) - (h.7) are common w i t h (H.4), (H.6), (H.8), (H.9), (H.10). This is because (h.3) - (h.7) are properties concerning the difference of entropies. On the contrary, ( h . l ) and (h.2) are concerning the values of continuous entropy itself, and these properties do not hold in the case of discrete distributions. I n particular, (h.2) implies that the continuous entropy is not invariant under a coordinate transformation.

1.4 R E L A T I V E

ENTROPY

In the case of discrete probability distributions, the relative entropy was defined in Sec. 1.1. This section extends the definition to the case of general probability distributions. Intuitively speaking, the relative entropy is defined to measure how close two probability distributions are. I t will be shown that the discrete entropy and the continuous entropy studied in the preceding sections can be expressed as a relative entropy.

M

RELATIVE

ENTROPY

Let l i and v be probability measures on a measurable space ( X , B ( X ) ) .

We

say that /x is a b s o l u t e l y c o n t i n u o u s w i t h respect to e, i.e., h -< c, i f /i(A) = 0 for every ,4 e B ( X ) such that i/{A) = 0. I t is known as the Radon-Nikodym theorem that, i f \L is absolutely continuous w i t h respect to v, then there exists a i/-integrable function

V A € B(X).

The function tp{x) is called the Radon-Nikodym derivative and is written i n the form

D e f i n i t i o n 1.4.1. For probability measures fx and v on ( X , B ( X ) ) , the r e l a t i v e e n t r o p y H(p.\ u) of n w i t h respect to v is defined by j

r

^

^

i f

L oo,

( 1

if

The measure e is referred to as the reference

. . 4

1 }

/ c

measure.

Note that the relative entropy is defined in quite general cases, including the cases of discrete probability distributions and continuous probability distributions which are studied in the preceding sections. I n these cases the relative entropy can be expressed explicitly, using the discrete probability distributions or probability density functions. A t first we consider the discrete case. Let \i and w be probability measures on a finite set X = { O i , a } m

The measures ji and v are specified by f i ( { a , } ) = p;

and f ( { a i } } - qi (i — 1, ...,m). Note that >i is absolutely continuous w i t h respect to V i f pi = 0 whenever qi = 0, and the Radon-Nikodym derivative is given by —(x) dv

= — qi

if

x — ai

( i = l,...,m).

Now we can easily see that the relative entropy H(p; u) coincides w i t h the one introduced i n Sec. 1.1: ff(ii;*)

= X>l°g^.

(1.4.2)

This can be rewritten as m

H(p; u) = -H(p,,

...,p ) - £ p f m

log qi,

(1.4.3)

ENTROPY

22

If, as a reference measure, we take the uniform distribution Co which is given by "o({o0) — l /

m

i

!

=

l i —)' *i T

e n (1.4.3) is w r i t t e n as

t f l

H{(i; uo) = -H(pi,p ) m

+ log m.

Therefore, once i n is fixed, the entropy H(pi,...,p ) m

(1.4.4)

is essentially equal to the

relative entropy w i t h respect to the uniform distribution, ignoring the additive constant l o g m and the multiplicative constant — 1 . Next, we consider the continuous case. Let ft and u he continuous distributions on W w i t h density functions p ( x ) and g{x), respectively. d

Assume t h a t /i is ab-

solutely continuous with respect to v. Then i * ( { x £ R \ q ( x ) = 0 } ) = 0 and the d

Radon-Nikodym derivative is given by

The relative entropy H{ji\ u) is now given i n the form mm

f

")=

p( )\cg^\dx.

(1.4.5)

X

If the continuous entropy k(p) = — Jp(x) l o g p ( x ) ifx is finite, then H(p-; c) can be rewritten as H{n;v)

= -k(p}-

j

p(x)logs(x)dx.

(1.4.6)

JR'

We consider a special case where p ( x ) vanishes outside a domain G of I f

1

with

finite volume \G\ and FO is the uniform distribution on G. T h e density function 9o(x) of v is given by 0

?

0

(

X

)

1 0 ,

=

x*G.

The relative entropy H{p\ v ) is given i n the form a

"») = - (p) f t

/ P( ) Hloix) x

dx = -k{p) + log \G\.

(1.4.7)

Thus we see that the continuous entropy h(p) coincides w i t h the relative entropy with respect to the uniform distribution, except the additive constant log\G\ and the multiplicative constant — 1 . We t u r n to study some of the properties of relative entropy. theorem is of fundamental importance.

T h e following

l.f

RELATIVE

2:i

ENTROPY

T h e o r e m 1 . 4 . 1 . Let /j and u be probability measures on (X,/5(X)). Then ff(**;f)>0,

(1-4.8)

w i t h equality i f and only i f ji = v.

P r o o f . We may assume that /i is absolutely continuous with respect to V. Then using the inequality (1,2.3) we have

= j

dii(i)- J

du(x) = 1 - 1 = 0.

Since the equality holds in (1.2.3) if and only i f x = 1, the equality holds i n (1.4.8) if and only if d^/dp(i) — 1 for //-a.e. x (fi-a.e. stands for ^[-almost everywhere). Since ^t(X) — c ( X ) — 1, this condition is equivalent to fi — v. •

The non-negativity of relative entropy enables us to understand that the relative entropy expresses a " s i m i l a r i t y " or a "distance" of two probability measures. I n other words, the relative entropy can be considered as a measure of how different the two measures are. Since relative entropy is not symmetric and does not satisfy the triangle inequality, i t is not a metric at all. Even though relative entropy is not a metric i n the usual sense, the understanding interpreted above is quite helpful to have an insight into various problems concerning relative entropy. The concept of relative entropy was first introduced by Kullback for applications of information theory to statistics (see [83, 84]). Since then it has played important roles not only i n information theory but also i n probability theory and mathematical statistics. There are many names and notations for relative entropy used in various fields. Some names i n common use for this quantity are Kullback-Lei bier information number, information divergence, information for discrimination, information gain, and cross entropy. We call A = {A ,...,A } t

a finite partition of X , i f A; € B ( X ) , A; O Aj = tj>

m

( i / j ) and \J1L Ai = X . l

Let p and v be two probability measures.

partition A = { A ] , . . . , A } , we define the relative entropy H^(ii\u) m

Given a associated

w i t h A by Ha(W

= X>(^)

log

(1-4.9)

24

ENTROPY

{Bi, ...,B„]

We say that a p a r t i t i o n F = {Aj,A ] m

is a refinement of a p a r t i t i o n A

=

i f for each Bj g T there exists Ai e A such that Bj C -4,-. I n this case

we can rearrange the sets B\,S

'

n

n

such a way that r = {Ajy; t = 1, . . . , m , j —

1 , f c ; } where ( J j = i A f j = Ai. The relative entropy H&(ii; v) increases according to the refinement of partitions. L e m m a 1.4.2. Let A = {A\,A }

be a finite p a r t i t i o n of X and T = {Ay;

m

i =

1 , m , j = 1,.... ki} be a refinement of A . Then H^^^Hr^-u).

Proof.

For simplicity, we denote S t = 3 "•-.(Ai)'

Then, since £ • jCtiV^Aij)

b

-, u(Aij)'

" ~

= ^,i j ij '{Aij) a

(1.4.10)

l

y X!i j -

P* ' 1

i = l,...,m, j = — /i(X) — 1, i n the same way as i i

the proof of (H.6) we see that Y ^ii^{A. )lo {aMAij)} l

1)

S

<

^Qiji/fAijJlogtaijcfAij)}

On the other hand

Combining these two relations we obtain (1.4.10).

•

This lemma enables us to give a characterization of relative entropy. T h e o r e m 1.4.3. Let p and v be probability measures on ( X , £ f ( X ) ) .

Then

H(n\ u) = s u p t f a O * ; k ) , A where the supremum is taken over all finite partitions A of X .

Proof,

(1.4.11)

We denote the right-hand side of (1.4.11) by H. First we assume that p.

is not absolutely continuous w i t h respect to v. Then there exists a set A £ B ( X ) such that i/(A) = 0 and ii(A) M > H (m &

> 0. Hence, for a p a r t i t i o n A = {A,

V) = fiA)

log ^ |

+ rtA*) log f@

A ),

= cc,

c

1.1 RELATIVE

25

ENTROPY

meaning that (1.4.11) holds i n the sense of oo = oo. Next we assume that ji is absolutely continuous w i t h respect to v. Denote by tp — dji/dv the Radon-Nikodym derivative. Given an arbitrary partition A

=

{Aj,.... A } of X , we define a probability measure v& by m

VA(A)

=

A e 0(X),

^(x)<Mx),

where

Note that H&(fi\ v) can be written i n the form Ho.(p\v) =

/ log^ (x) Jx A

d)i{x).

Moreover i t can be shown that ji is absolutely continuous with respect to

and

the Radon-Nikodym derivative is given by P

d

I) x

-

By Theorem 1.4.1

This is equivalent to H (fi;v)=

/ log \b (x)dfi(x) Jx

A

A

< / logi^(i)d/i(i) = Jx

H(fi,v).

Since the partition A is arbitrary, we have H < H(ii-v).

(1.4.12)

We now proceed to prove the inverse inequality of (1.4.12). We put C„ = {x e X ; |logp(r)| > 7i}. Since Yim„ —

ao

n(C ) n

« ( c ) i o g 4£4 n

= 0, for any e > 0, there exists JV such that > M o i o g / i c c . ) > -e,

y» > m

(i.4.i3)

26

ENTROPY

Fix an integer n > N and define a partition A = {An i = 0, ± 1 , ± m ] At = ix e X ; ( A_ A_

m + i

m

=

( l

- ^ " < logv(i) < — } , m mj

by

- m + 2 < i <m,

= { z 6 X; - r . < log^(z) <

,

C„.

Then lo =(r) < -

< log 444

g ¥

xGA

+ -.

iy

~m
(1.4.14)

Thus, using (1.4.13) and (1.4.14), we have

/ ^ l o g ^ w ^ J ^ ^ o i o g ^ ^ < Sofa

u) + e + - < H m

+ e + —. m

Letting m —• oo first, and then e —» 0, we finally obtain the desired inequality B(m»)=

(\o (x)dtix)<x. SV

J X

The proof is complete.

•

Relative entropy has an alternative expression which has played i m p o r t a n t roles in the large deviation theory (see e.g.

Theorem 3.2.4). We shall show that the

relative entropy is equal to D{n\v)

= sup j

# ( * ) d t f s ) - l o g / exp(#[>J) dv'x)

(1.4.15)

where the supremum is taken over the set B of all bounded measurable functions defined on X . In the large deviation theory, D(fi, v) is called the entropy function or the rate function. T h e o r e m 1.4.4. Let fi and V be the probability measures on ( X , S ( X ) ) . Then H(p,i>) =

D(r,»).

(1.4.16)

1.4 RELATIVE

27

ENTROPY

To prove the theorem, we introduce auxiliary notations. Define classes U U ( f ) and V = \(u)

=

by

U = {u G Z ^ ) ;

> 0 (>-a. .), e

f u(x)dt>(x) = 1}, Jx

V = { u € U ; logueB}, where L ' ( f )

is the class of all v-integrable functions.

And define D(p;v)

and

D (ft; u) by 0

5 ( / i ; e ) = sup / l o g u ( x ) d u ( r ) , u€U J x D ( u ; c ) = s u p / logii{x)d/i(x). aev *ev J x 0

For every # € B , there corresponds a function u 6 V given by -l

«(*) =

exp(#(x)).

[^exp(
(1.4.17)

Then i t is easily seen that j

$(x) d/i(x) - log J

exp(
logu(x)dp(x).

Jx

Therefore we know that D(ti-,v) = D (fi;u).

(1.4.18)

0

P r o o f o f T h e o r e m 1.4.4. To show (1.4.16) i t is enough to prove the following three assertions. 1°)

I f D{fi; V) < co, then B(p\ v) < 5 ( u ; v).

2")

I f D (/i; u) < oo, then D(p\ u) < D (ii; v).

3")

I f ff(fi\ v) < oo, then D (y.;

V) p-iv.

0

0

0

Assume that D(fi;v) Let v(A)

Noting that v(A)

= 0(Ae

u) < H(j*l

v).

< oo. First we shall show the absolute continuity

S ( X ) ) . For any fixed k > 0, we put k,

x £ A,

0,

x$A.

= 0, we know that the function u(x) e V

(1.4.17) coincides w i t h exp(
logv(t)M*)

< D(it;i/)

< oo.

C U defined by

28

ENTROPY

Since k is arbitrary, ji{A) should be zero. Consequently /i -i v. We p u t

and ff&qv}-

2°)

/ logv(*)«^(*)<5( i/). Jx Assume that DQ(fi\f) < oo. I t suffices to show W

logu(x)d/i(z) < Dot/*! " ) ,

Vti e U .

(1.4.19)

ix Let u £ U . We may assume that (\ogu(x))~ — — m i n ( l o g u ( i ) , 0 ) € L ^)1

We

define «»(>) = f«$pJvijfMh

n = l,2,....

Then - f ( z ) = l o g u ( i ) £ B and n

n

/ # ( a : ) 4 ( * ( * ) < l < « / exp(#,,(ir))<M») + Z>o(ii;i'). (1.4.20) Jx Jx Since 0 < u „ ( i ) = e x p ( # „ ( z ) ) < u ( i ) + 1 for all n and lim„_oo exp(!f„(x)) = u ( i ) B

(i<-a.e. x), using Lebesgue's convergence theorem, we have

n

l i m / e x p { # „ ( i ) ) di/(i) = / u ( i ) d i / { i ) = 1. -°°Jx Jx

Noting that 0 < ( # ( * ) ) n

+

< (* +i(x)) n

and 0 < ( # „ ( » ) ) " < ( # „ + i ( s ) )

-

+

< (log (x)) U

+

(u(x)

Assume that H(LL;U)

= max(t,(x), 0))

< ( l o g u ( i ) ) - , we obtain

l i m / #„(x)d/x(x) = j l o g u ( i ) d o ( i ) . ™ Jx Jx The inequality (1.4.19) follows from (1.4.20) - (1.4.22). 3")

+

(1.4.21)

(1.4.22)

< oo. Then /i - I if. For any u £ V , we define a

probability measure 0 (c-a.e. x). We can easily show that 0 < f f ( / i ; < r ) = j^\og^{x)dp{x) = -

= ^ ( l o g ^ i j + log^fz))^*)

/ logii{x)<^(a:) + /r(/ ji*). Jx t

Thus we have Oof/'; *) = / l o g « ( x ) ^ ( x ) < / f ( ; i/). Jx The proof is complete. • U

1.5 PROPERTIES

OF RELATIVE

1.5 P R O P E R T I E S O F R E L A T I V E

ENTROPY

29

ENTROPY

This section is devoted to studying properties of relative entropy. Throughout the section we denote the set of all probability measures on a measurable space (X,B(X])byM, M,(X,I!(X)). =

First we shall show the convexity of relative entropy. For probability measures (j], fi-2 € M j and a constant 0 < a < 1, a probability measure ji — api + ( 1 — a)/*2 is defined by f*{A) = am'A) + ( 1 - a)ii,(A),

A 6 0(X).

T h e o r e m 1.5.1. 1°) The relative entropy H(fi; u) is convex in (p,v). precisely, for any m, i/j e M , {i = 1,2) and constant 0 < or < 1, Hfav)

< « f f ( ( * , i * , ) + ( l - o)Jf{/i ;c ), 2

2

More

(1.5.1)

where jx = afX\ + (1 — a ) f i j and i/ = ai/, + (1 — Ot)v$, 2°)

The relative entropy H{ji\v)

is strictly convex in ji. More precisely, i f

f/{/i]; i/) and H{ix \ v) are finite, ^i] ^

and 0 < o < 1, then

2

mm where 3")

") < * * G » i ; " ) + ( ! -

(1-5.2)

= ar/ii + (1 — a)y.i. I f // (^]; f ) and H(^2\ v) are finite, then inequalities 0 < aH{ii,-u)

+ {l -a)H(fi ;v)2

Bffcv)

< h{a)

(1.5.3)

hold for any 0 < a < 1, where ^ = oifii + (1 — or)>i2 and k{a) = —a log a — (1 — o ) l o g ( l - a).

To prove the theorem, we need the following lemma. L e m m a 1.5.2. Let at and i ; ( i = l , . . . , m ) be non-negative numbers. Then the inequality m

5>l*>g£>al°gp i

1

(1.5.4)

30

ENTROPY

holds, where a = YT=l <*i and 6 = £ ™ ,

T

m

m

equality holds i n (1.5.4) i f and

m

P r o o f . We may assume that a, b > 0. t

e

a /b .

only i f a, /6) = • • • =

u = (a /a,...,a /a)

h

For discrete probability distributions

and v = (b,/b,...,b /b),

from Theorem 1.4.1, we know that

m

Clearly this inequality is equivalent to (1.5.4). Moreover from Theorem 1.4.1 we know that the equality holds i n (1.5.5) and (1.5.4) if and only i f aj/o — h/b for all i , or equivalently a,/b\ = • • - = a / 6 . m

P r o o f o f T h e o r e m 1.5.1.

1°)

^

m

To prove (1.5.1) we may assume that m is

absolutely continuous w i t h respect t o i>, ( i = 1,2). We p u t

^ ' j j g w ,

P W - f W

(x € X , i = 1,2). Then a/, ( z ) + ( l - a ) / i ( s ) =

andaj7,(x)+(l-ft)s (s) = L s

Using Lemma 1,5,2, we have afi{x)log
+ {l -

a)f (x}\ogifi {x) 2

2

= « / i ( x ) l o g ^W + f l - «)/a(*)log 9\\x)

/,( )+(l- )/ ( )

fl

>(a/ (z) + (l-o)/ (z))log. l

^ ffs(i)

I

Q

!

I

2

O f f l ( l ) + (1 -

<*)?2(Z)

= ¥>(x)log^(x).

(1-5.6)

Integrating both sides of (1,5,6), on the space X , by the measure f , we obtain the inequality (1.5.1). 2°)

Since U] ^ /i

2

and 0 < a < 1, the strict inequality holds i n (1.5.6) on a

set w i t h V positive measure. Thus the inequality (1.5.2) can be shown i n the same way as i n 1°). 3°)

The first inequality of (1.5.3) has been shown. By assumption,

(t = 1,2)

is absolutely continuous w i t h respect to v. We use the same notations as above. Since (s + t)log(s + t) > slogs + t l o g t , s,t > 0, ¥>(*) log fix)

> a / i ( * ) l o g ( a / i f ; x ) ) + (1 - o ) / i ( x ) l o g ( ( l - a ) / ( x ) ) 2

=af ( )iagfi(x) l X

+

(l- )f (x)\ogh(x) a

2

+ a/i(x)logo+(l -a)/j(e)log(l

-a).

I.S PROPERTIES

OF RELATIVE

ENTROPY

31

The second inequality of (1.5.3) is now obtained by integrating b o t h sides by the measure v.

•

As we have mentioned, relative entropy can be considered as a "distance" between two probability distributions. Here we investigate convergence of probability distributions. Let ft, c, ji

n

that the sequence {/!„}

£ M ] ( n = 1,2,...) be probability measures. We say

c o n v e r g e s t o /i i n e n t r o p y , if l i m /Y(^ ;^) = 0. n

The

t o t a l v a r i a t i o n of p — v is defined by m

- " I I = s u p X J HfU)

- K*)l<

(1-5-7)

where the supremum is taken over all finite partitions A = { A ] , . . . , A ) m

is easily seen that \\ti —

of X . I t

defines a metric on the space M i . It is said that

(u ) n

c o n v e r g e s t o (i i n v a r i a t i o n , if

lim ||fi„ - H| = 0. By definition, i t is clear that if {fi„} l i m fi (A) n

converges to ji i n variation then

= >,(A),

V A £ S(X).

In the case where X is a metric space and B ( X )

(1.5.8)

is the topological Borel

field,

namely the m i n i m u m
It is said that {/j„} c o n v e r g e s t o j i i n l a w , or

weakly

c o n v e r g e s t o ft, i f

l i m / f{x)dfi {x)= "— J x n

00

I

f{x)dii{x),

J X

for all bounded continuous functions /. It is known that { J I „ } converges to u i n law i f and only i f lim

u (G)>^(G), n

for all open sets G. Therefore, if ( u „ ) converges to fi in variation, then i t converges to ji in law.

32

ENTROPY

L e m m a 1.5.3. I f measures p e M i and e £ M i are absolutely continuous w i t h respect to a measure a € M i , then

Jx where ^

= g(*3

and

0(x)=gf>),

P r o o f . For any p a r t i t i o n A = {A\,...,A },

i t is easily seen that

m

T\v(A )-v{A )\ i

= Y,\

i

/

< £ / i =

Mz)-V>(>)I<M*)

i

= / |^>-^)1<M*)Jx Therefore <

/ |v(*)-*(*)l
To prove the converse, we put s =

{xeX

; ¥

Kx)>^(x)}.

Then (fJ, B } is a partition of X , and c

= /i(B)-«{S) + " ( 5 ) - M » 1 B

m

^sup^l^AO-KA,)!. Thus the proof is complete.

•

Here we show that the total variation of /i — f is dominated by their relative entropy.

1.5 PROPERTIES

T h e o r e m 1.5.4.

OF RELATIVE

Si

ENTROPY

Let ft, V G M , . Then

1°)

|| -c|| <2tf( ;c). i

H

2")

(1.5.9)

u

I f { f i } converges to /i i n entropy, then i t converges to u i n variation.

Proof.

n

1*)

There exists a measure a e M ] such that w -< a and v < a. For

example we may take a = 1/1 + \v as such a measure. Denoting as
and 0 0 ) = dv/do, we put S = { i £ X ; y j ( x ) > ${x)}.

M-B) + ti(B ) c

= v{B)

&-H=

+ v(B ) c

Noting that

= 1, we have

f iv(?)-'K*))M*)

+ j

= , i ( S ) - v{B) + v(B')

-

U

Mx)-
(B<)

= 2{MB)-"(5)).

(1-5.10)

By Theorem 1.4.3, i t is clear that fffj.;

„ ) > ,i(B)log

^ l o g ^ l .

+

(1.5.11)

For any numbers 0 < s, t < 1, the following holds slogy + { l -

3

>2( -tf.

) l o g ^

S

(1.5.12)

Combining (1.5.10) - (1.5.12) we have

ff( i,)£20i(S)-^fl)) >^ll^-HI 1

W

1

Thus (1.5.9) is obtained. Assertion 2°) is an easy consequence of 1°).

•

Lower semi-continuity is an important property of relative entropy. T h e o r e m 1.5.5. I f {ii„} and [u ) n

converge to ii and v, respectively, i n the sense

of (1.5.8), then H((*\v)<

l i m H(p ;u ). n

a

(1.5.13)

ENTROPY

3*

In particular, if {/!„} and {u }

converge to n and v i n variation, then (1.5.13) is

n

true.

Proof.

A t first, we assume that H(fi;v)

< co. Then, for any e > 0, there is a

partition A = {A\, —, -<4 } such that m

H (p\v)> A

H{p\v)-e.

(1.5.14)

See (1.4.9) for the definition of H&(ti; v). By the assumption, for each A

i:

l i m ft (Ai) n

= p{Ai),

l i m f„(Ai)

n—-co

we have

=

TJ—-co

Therefore, i f n is large enough, then |Jf (/i;i/)i/„)| a

< e,

and

This means that lim

H& -,v„)>H((ii»)-2e. n

n—-co

Since e > 0 is arbitrary, we have (1.5.13). Next, we assume that H(/i\ v) = oo. Then, for any fixed positive number M , i n place of (1.5.14), we have S a O ; V) >

M.

Using the same arguments as above, we can show that lim H(flni "n) = oo = ff(u; v). n—-co

The proof is complete.

•

1.6 MUTUAL

1.6 M U T U A L

35

INFORMATION

INFORMATION

Shannon successfully introduced the concept of mutual information as a measure of information. I t may not be too much to say that this made i t possible to build up information theory, a mathematical theory of communication. I n this section we shall define m u t u a l information and study most of the properties of mutual information. Let X be a random variable taking values a , , a

w i t h probabilities p j , . . . , p .

m

m

Suppose that we cannot observe the outcome of X directly, and what we can observe is another random variable Y. w i t h probabilities qi,...,q

n

We assume that Y takes values bt,.... b

n

The entropy H{X)

respectively.

uncertainty of X before the observation.

of X expresses the

Suppose we are informed that Y = bj

occurred. Then the uncertainty of X is now reduced to the conditional entropy H(X\Y

= bj).

We can say that the amount of information w i t h respect to X,

contained i n the information ¥ — bj", is equal to H{X)-H(X\Y

= bj).

(1.6.1)

The average value £ { t f ( . Y ) - H(X\Y

= bj))P(Y

= by) = H(X)

-

H(X\Y)

of (1.6.1) is the amount of information w i t h respect to X we may expect to obtain by observing Y

We denote this quantity by I{X,Y)

Using (1-2.2) and (1.2.8), I(X,Y)

= H(X)

I(X,Y):

- H(X\Y).

can be written as n

m

j = l i=l where r,j = P{X

= a„Y

(1.6.2)

y , H

>

= bj). Therefore, we have I(XX)

=

I(Y,X),

meaning that the information about X contained in Y is equal to the information about Y contained i n X.

This allows us to call I(X,

or the average m u t u a l information between X and V".

Y) the mutual information

ENTROPY

36

We denote by px

the probability distribution of X.

In the same way we denote by pxY

Then fix ~ (pi.•••>Pm)-

— {>",j; ' = l,...,m,j

probability distribution of X and Y. A n d denote by fix

l , . . . , n } the joint

=

PY the product of y.

x

x

and /iy: P-x x w ( { ( « < A ) j ) = Pi!fcThen from (1.6.3) and (1.4.2) we know that the mutual information I(X,

Y)

can

be expressed as a relative entropy: I(X,Y)

= H(HXY;IIX

x py).

(1.6.4)

This suggests to us how to extend the definition of mutual information to continuous random variables or stochastic processes. Let ( X , B ( X ) ) and ( V , 6 ( Y ) ) be measurable spaces, and let X and Y be random variables defined on a basic probability space (ft, B, P) taking values in X and Y , respectively. We denote by ji

and jiy the probability d i s t r i b u t i o n of X and Y:

x

p (A)

= P(X

x

Let B(X)xB(Y)

e A),

A£B(X).

be the product of S ( X ) and B(Y),

theo-field of the product space

X x Y = { ( * , » ) ; i € X , j i e Y } generated by {Ax

B- A e B(X),

B € B(Y)}.

The joint probability distribution /ixv of X and K is now defined as a probability measure on ( X x Y , f J ( X ) x B(Y)) = P({X,

PXY(C)

The product fix x /iy of /i

x

( X x Y , B ( X ) x B(Y))

fix x M

A

such that Y)

eC),

G € 0(X)

k

B(Y).

and p.y is also defined as a probability measure on

satisfying

* ) 5

= MA)/MB),

A e B(X), B e 0(Y).

Note that X and F are mutually independent if and only i f fx Y X

D e f i n i t i o n 1.6.1. The m u t u a l i n f o r m a t i o n I(X,

Y)

— P-X X f l y .

between X and Y is de-

fined by (1.6.4).

Note that, since we may take ( X , B ( X ) ) and ( Y , B ( Y ) ) arbitrarily, the mutual information I(X, stochastic processes.

Y)

is well denned even if X and Y are random vectors or

1.6 MUTUAL

37

INFORMATION

By the definition of relative entropy, the mutual information is w r i t t e n as I(X,

Y) =

log ,

/

( « , y) dfixvix, V%

d t l X Y

(1-6-5)

if CXY ri. t*X x fiy \ otherwise I(X, Y) is infinite. Throughout the text we denote by E\ £ ] the mathematical expectation of a random variable £:

Then, i n tenns of the integral on the space f i , (1.6.5) can be rewritten as I(X,Y)=

f fag

X

=

(X(u) Y(»))dP{w)

^ dll X /l

t

Y

£ | i o ^ - ( x , F ; d/ix x u y g

(1.6,6)

J

M u t u a l information plays a central role in the theory of information transmission. Let {A\,A )

and {Bi,B„}

m

be finite partitions of X and Y , respectively.

Then A = {Ai x By, i = l , . . . , m , j = l , . . . , n ) is a partition of X x Y .

(1.6.7)

Choosing points a; £ A , 6j £ £7, arbitrarily, define f

discrete random variables X& and 1 a by

x

A

=

if

ai

X £ Aj,

Kb = iy

if

y £ Bj.

Note that, by taking fine partitions, one can approximate X and Y by discrete random variables X& and 1 ^ . We shall show that the mutual information I(X, is approximated by I{X ,Y ), &

meaning that the definition (1.6.4) of I{X,Y)

a

Y) is a

natural extension of (1.6.3). T h e o r e m 1 . 6 . 1 . The following holds I(X,Y)

= sup I(X ,Y*),

(1.6.8)

A

A

where the supremum is taken over all the finite partitions A of the form (1.6.7), P r o o f . For discrete random variables X& and K a , i t is clear that I(X ,Y ) A

&

=

Hinx^Yi.Px*

x nvt)

= H&(PXY;I*X

x

p )Y

(1.6.9)

38

ENTROPY

Hence (1.6.8) follows from (1.6.4), Theorem 1.4.3 and (1.6.9). Here we should note that the supremum i n (1.6.8) is taken, not for all, but only for all partitions by means of rectangles of X x Y . However i t is known that this restriction is not necessary (see Dobrushin [31]).

•

For discrete random variables, the mutual information is given by (1.6.3). For continuous random variables, i t is calculated as follows. T h e o r e m 1.6.2. Let X = (X ...,X ) it

and Y -

k

(*,,...,Y|) be, respectively, k

and / dimensional random variables such that (X, Y) has continuous distribution w i t h density function r ( x , y ) ( ( x , y ) £ R * ' ) . Denote by p ( x ) = J " r ( x , y ) d y and +

q(x)

= jr(x,y)dx

the density functions of X and Y, respectively.

mutual information I(X,Y)

T h e n the

is given by = f

I(X,Y)

r f x . y j l o g - ^ ^ x d y .

(1.6.10)

= h(X) + h(Y) - h(X,Y).

(1.6.11)

Moreover the following holds I(X,Y)

Proof. 0, lixY

= h{X) - h{X\Y)

Since fix X py has the density p(x)
^

i

y

(

X

•

y

,

p(x) (y)' 9

l*,y)€H

"

Now (1.6.10) follows from (1.6.5). We can easily show (1.6.11), using (1.3.1) and (1.3.9).

•

We proceed to define conditional mutual information. Let X, Y, Z be random variables taking values on measurable spaces ( X , f J ( X ) ) , ( Y , B{Y)} and (Z, 0 ( Z ) ) , respectively. Given a condition that Z — z occurred, we denote by /ix|z("l )> z

PY\Z{-\ ),

PXY\Z(-\Z)

Z

(X,Y).

the conditional p r o b a b i l i t y distributions of X,

Y and

Then the quantity l(X

t

Y\Z = z) = H(LL ^{ xy

• \z);fix\z( • |f} x fi \z( • \4) Y

(1-6.12)

expresses the conditional mutual information between X and V when Z = z occurred. Taking the average o f I(X,Y\Z conditional mutual information.

= z) w i t h respect t o Z , we define the

1.6 MUTUAL

39

INFORMATION

D e f i n i t i o n 1.6.2. The quantity = J

I(X,Y\Z)

I(X,Y\Z

= z)dp (z)

(1.6.13)

z

is called the c o n d i t i o n a l m u t u a l i n f o r m a t i o n between X and Y given Z.

We collect most of the properties of mutual information. T h e o r e m 1.6.3. (Properties of M u t u a l Information)

Let X, Y, Z, X , Y (i = s

f

1, ...,n) be random variables. The following properties hold. I(X,Y)

(1.1)

=

(1.2)

I{Y,X).

T(X,Y)>0,

w i t h equality if and only i f X and Y are mutually independent. (1.3)

I f Z is a function of Y, namely Z is given by Z(w) = f(Y(uj)),

us € ft, where

/ is a measurable mapping from Y into Z . Then I(X,Y)>I(X,Z). If / is a bisection and the inverse mapping /

- l

(1.6.14) is also measurable, then the equality

holds i n (1.6.14). I(X,Y\Z)>0.

(1.4)

The necessary and sufficient condition for I(X,Y\Z)

= 0 is that X and Y are

independent when Z is given, in other words X, Z, Y forms a Markov chain. (1.5)

I f (X, Y) is independent of 2 , then I(X,Y\Z)

(1.6) (1.7)

KX,{Y,Z))

=

= I(X,

I(X,Y).

Z) +

HX,Y\Z).

I f A\ Y, Z are discrete random variables, then I(X,Y\Z)

=

H(X\Z)-H(X\Y,Z)

= H(X\Z)

+ H(Y\Z)

- H(X,

Y\Z).

10

ENTROPY

(1.8)

I f X, Y, Z are continuous random variables, then I(X,Y\Z)

h(X\Z)-h{X\Y,Z)

=

= h(X\Z)

(1.9) (1.10)

7(x,(r ,...,y )|2) = 1

-

h{X,Y\Z).

^/(x,y;]2,(r ,...,F -.)).

n

I f (Xi,Yi),...,(X ,Y„)

+ h{Y\Z)

1

i

are mutually independent, then

n

n

I((X ...,X»),(Y ...,Y )) u

1}

=

n

Y- '^ I(

Xi Y

i=i

P r o o f . We shall prove assuming that the mutual informations and the conditional informations are finite. Otherwise we can show that the equalities hold i n the sense of oo = oo. The symmetry ( L I ) is clear by definition. Since I(X,Y)

is a relative entropy,

(1.2) follows from Theorem 1.4.1. (1.3)

For each finite partition A = { A ; x Cj)

of X x Z by means of rectangles,

there corresponds a finite partition T = ( A ; x f i j } of X x Y , where Bj = f~ {Cj) {y e Y ; f(y)

e Cj}.

Clearly I(X ,Y ) r

from Theorem 1.6.1. I{X,Z) (1.4)

= I{X^Z^).

r

I f / is a bijection and

> I{X,f~'(Z))

= I(X,Y),

is measurable, then we have

and consequently I(X,Y)

' W)

' \ ) = Px\zl Z

x

=

I(X,Z).

PY\z{ * \ ): Bnd we know from Theorem 1.4.1, z

(1.6.12) and (1.6.13) that this is equivalent to I(X,Y\Z) Let (X, Y)

be independent of Z.

PY\Z( * |*) and HXY\Z(

Px\z{'

equal to px, HY and fi YLet I(X,

Z) and I(X,

= 0.

Then the conditional distributions

• l»0 do not depend on z, and are respectively

Thus I(X,Y\Z)

X

(1.6)

=

follows

The inequality is clear by definition. X, Z, Y forms a Markov chain i f and

only i f IIXY\Z( (1.5)

i

Thus (1.6.14)

=

I(X,Y).

Y\Z) be finite. Then there exist the Radon-Nikodym

derivatives ,

Consequently jixYZ

>

dpxz

.

,

< P-X * PYZ and

dpx

*

(x, ,z) V

PYZ

= a(x, )ft*,y,*)V

(1.6.16)

1.7 RATE-DISTORTION

FUNCTION

41

It follows from (1.6.5), (1.6.15) and (1.6.16) that I(X,

(K, 2 ) ) =

log a{x, z) diixvzix,

/

y, z)

JXxYxZ

+ -

/

\ogff(x,y,z)dp z{x,y,z) XY

JX-YxZ

I(X,Z)

+

I(X,Y\Z).

Properties (1.7) and (1.8) are easily shown by using (1.6), (1.6.2) and (1.6.11), and (1.9) is proved by using (1,6) repeatedly. Put Xi = (X

(1.10)

,X„)

aadYi=(Yi,...,Y ).

Then by (1.6)

n

/((x ,...,x ),(r ,...,y„)) = /{(ji£- ,^ ),(y ,? )) 1

-

I1

I(X,

1

,Y,)

1

+ I(Xi,Yi

[Yi) + I(X ,

2

1

Y\ \X ) + I(X ,

2

t

By (1.4), (1.5) and the assumption, we see that I(X , l

and I(%S,%lXuYi')

= i(Xl>%%

n

2

%\Yi)

Y 1*, 2

,Yi).

= I(X ,Y,\Xj)

= 0

2

so that

/((x ,...,x ),(y ,...,y„)) = /((x,, X ),(Y Y )) 1

1

1

2

U

= I(X Y,)

2

Repeating the same argument we obtain (1.10).

U

+I(X Y ). 2}

2

•

The properties (1.7) - (1.10) are immediate consequences of (1.6). I n this sense (1.6) is fundamental. Properties (1.6) and (1.9) are referred to as chain rules for mutual information. Moreover, since (1.6) is equivalent to (1.6.13), we have an alternative expression I(X,Y\Z)

= / ( X , ( y , Z ) ) - I(X,Z)

(1.6.17)

of the conditional mutual information.

1.7 R A T E - D I S T O R T I O N

F U N C T I O N

In practice, since information transmission over a communication channel is perturbed by noise, we may not expect exact recovery of messages at the o u t p u t of the channel. Practically speaking, we are not interested i n exact transmission, but only i n transmission w i t h i n a fidelity of reproduction. To discuss information transmission w i t h fidelity, we introduce the concept of rate-distort ion function.

ENTROPY

42

Mathematically speaking, messages t o be transmitted a n d the corresponding received messages are represented by random variables. Denote by X a message to be transmitted and by Y the received message. The fidelity of the communication is evaluated by using a function d(X, Y), which is called the r e p r o d u c t i o n e r r o r or the d i s t o r t i o n . The distortion d(X, Y) should be determined corresponding to the joint probability distribution of X and Y, The distortion needs not have metric properties b u t should be defined i n such a way that smaller distortion corresponds to better performance of the communication. Let us see some important examples o f distortions to measure the reproduction error. I f the messages X and Y are discrete random variables, then one of the natural ways to evaluate the reproduction error is to use the e r r o r p r o b a b i l i t y P(XjLY)

(1.7.1)

of reproduction of the message X. Mean square error is another useful measure to evaluate the reproduction error. Let X = (X^, ...,Xiv)

and Y — (Y\,...,Ys)

be N-dimensional

random variables.

Then the mean square error is given by f 1

1

N

1 / 2

More generally, i f X is a metric space w i t h metric p(x,y) and Y = (Y\,...,YN)

and X =

(X ,XN) t

are JV-dimensional X valued random variables, then the

reproduction error can be measured by I

N

d(X,Y)=^~Y, {p( -' -) )\ E

x

Y

•

2

Let ( X , X) be a measurable space. A d i s t o r t i o n m e a s u r e p(x,y)

(1-7-3) is a function,

defined on X x X , which satisfies the following properties (a) and (b): (a)

p(x,y)

= (y,x), P

Vx,y € X .

(b)

p(x,y)

> 0,

V x , y € X , and p(x,y)

Note that p(x,y)

= 0 i f and only i f x = y.

is not necessarily a metric, because the triangular inequality is

not assumed. And the d i s t o r t i o n d{X,Y)

is defined by

d(X,V) = { £ [ p ( X , n ] } 2

1 / 2

.

We can easily see that (1.7.2) and (1.7.3) are special cases of (1.7.4).

(1.7.4) Moreover,

the error probability (1.7.1) can also be considered as a special case of (1.7.4). I n

1.7 RATE-DISTORTION

43

FUNCTION

fact, i f we define a distortion measure by / 0,

if .

1,1,

if

•*=& ijiy,

then P{X?Y)

=

E\p(X Y?}=d(X,Y)\ l

I n this section, we shall be concerned w i t h the relationship between mutual information and reproduction error. We are interested i n the minimum quantity of the m u t u a l information we need to send for information transmission w i t h i n a required fidelity. Definition

1.7.1.

R(D;X)

For a given message X, a function R(D; X)

= in{{I(X,Y);

d{X,Y)
defined by

0 < D < co,

(1.7.5)

is called the r a t e - d i s t o r t i o n f u n c t i o n of X, where the infimum is taken for all Y satisfying d(X,Y)

< D. The d i s t o r t i o n - r a t e f u n c t i o n D{R,X)

of X is defined

by D(R\ X)

= i n f { d ( X , K ) ; I{X,Y)

0 < R < co,

< ft},

where the i n f i m u m is taken for all Y satisfying I(X,Y) occurs, we simply denote R(D)

and D(R)

Note that the rate-distort ion R(D,X)

for R{D;X)

< R.

(1.7.6) If no confusion

and D(R\X)

respectively,

is the minimum mutual information we

have to transmit i n order to reproduce X w i t h distortion not greater than D. Moreover the distortion-rate D(R\X)

is the minimum distortion attainable by

sending m u t u a l information not greater than R. For a Gaussian random variable X we can find an exact expression of R(D\

X)

as a function of D (see Theorem 1.8,7). I n general it may be a difficult task to find an exact expression of the rate-distort ion function. By definition, we know that the inequalities I(X,

Y)

> R(d(X, Y); X),

d(X,Y)

> D(I(X,Y);

X)

(1.7.7)

hold. Let a message X be fixed and denote by /IXY the joint probability distribution of X and Y. Then i t is seen that the distortion d(X Y) 1

1

= E\p(X,Y) \= 1

f f p(x,y? Jx Jx

dn y{ ,y) X

X

(1.7.8)

44

ENTROPY

is determined by ji YX

mined by pxY

Recall that the mutual information I(X,Y)

is also deter-

(see (1.6.4)). Denote by Lty\x the conditional probability distri-

bution of Y given X.

Then, since (txY

= l*x * PY|X> 1 ( ^ , 1 ' ) and d(.X, Y )

are

determined by iiy\X once the distribution /ix of X is specified. Let c( • | •) be a conditional probability distribution, namely v(B\x) satisfies the properties (a) and (b): (a)

For each fixed i e X , c( • |i) is a probability measure on X ;

(b)

For each fixed measurable set B, v(B\• ) is a measurable function denned

on X . Denoting by Q the class of all conditional probability distributions on X , we define

where Co is a measure given by = J

MB)

v(B\x) dnx(x)

(1.7.9)

and dc( - |i}/di
Then by (1.6.5) and (1.7.8) I(X,Y)

= /(n

v l x

),

Therefore, if we define classes Qj(Z?) C d p ) = (c e Q; d(u) < D],

d(X,Y)

= dfjiy,*).

(1-7.10)

Q/(/i) by Q,(R)

= {u€Q;

/(c) <

R],

then we obtain alternative expressions of the rate-distortion function and the distort ion-rate function: R(D)

= i n f { / ( c ) ; c € Qd(D)),

JJ(fl) = mi{d(v)-

c g C/(B)}-

(1.7.11) (1.7.12)

Fundamental properties of rate-distort ion function and distortion-rate function are given i n the following theorem.

1.1 RATE-DISTORTION

T h e o r e m 1.7.1. The functions R(D) decreasing, and the function r(D)

FUNCTION

= R(D;X)

and D{R)

45

= D(R;X)

are non-

= R(\f~D) is convex i n D. The function

R[D)

is continuous on (0, oo), and continuous on [0, oo) i f R{0) < oo. Proof.

I t is evident that R{D)

and D(R)

positive constants such that A] + A Di and D ,

5

are non-decreasing. Let Ai and A

a

be

= 1. For arbitrary non-negative numbers

we put D = A i D , 4- A J D J . By (1.7.11), for any e > 0, there exists

2

v, e Q i t v ^ ) (' = 1,2) such that I[v )
+ e.

i

(1.7.13)

Define u £ Q by u(B\x) ^ ^MBlx) then i t is easily seen that v € Qi{sfD). r(D)

+

X^(B\x),

Therefore, by (1.7.11),

= R(y/D)

<

(1.7.14)

Define |r« ( i = 1,2) by (1.7.9) replacing v by i/j. Then J { f ) can be written as

(1.7.15) Substituting dc( • |i) dc ^ ^ ^ d ^ T l i ) ^ i0

into the inequality logt < t — 1, we obtain

from (1.7.15). Since i/ = Ai*^o + A i d o , i t follows from (1.7.16) and (1.7.13) that 0

I{v)

< A i J ( " i ) + AJ/(I/ ) < A , r ( O ) + A r ( D ) + c. 2

l

2

2

(1.7.17)

Since £ > 0 is arbitrary, from (1.7.14) and (1.7.17), we obtain r(\iDi

+ A j D ) < A , r ( D i ) + >,!•(£,), a

meaning that r ( D ) is a convex function. Note that a bounded convex function is continuous. Since r{D)

= R( \/D) is non-increasing, i t is bounded on the outside

A6

entropy

of a neighbourhood of D — 0 and continuous on (0,oo). I f ft(0) < oo, then r ( D ) is bounded and consequently continuous on [0, oo).

•

R

0

Om«

F i g u r e 1.2.

D

Rate-distort ion function

For a random variable X, define D „ M

by

= D (X)

D ™ , = [ i n f jj^

MII

<<Mx); v e

x

Then i t is seen that i t ( I > „ ) = 0, m

If D „ , „ D > S

= oo, then (1.7.18) is obvious. B U

|

there exists y

0

D(0) = D „ „ .

(1.7.18)

Suppose that D

is finite.

MILL

e X satisfying /

p ( r , s/o) d u x ( x ) < O 2

x

a

be a conditional probability distribution such that K i l f o } ) * )

=

Then d(c) < D and /(f) = 0. Hence R(D)

< D ( 0 ) < d(c) <

= 0 and D „ m

Since K ( D ) is continuous, letting D tend to D

m l I

1 f°

For any

Let v £ Q

r

every

i£X. D.

, we obtain (1.7.18).

Summarizing the properties stated above, we see t h a t the rate-distort ion function is as sketched i n Fig. 1.2. Finally we shall show that rate-distortion function and distortion-rate function are mutually inverse functions of one other. T h e o r e m 1.7.2. The following relations are satisfied. R(D(R))

= R,

D{R{D))

= D,

Q
0 < D < D

m

i

l

.

(1.7.19) (1.7.20)

1.8

P r o o f . I f ft = D{I(X,X))

ENTROPY

FOR

GAUSSIAN

47

DISTRIBUTIONS

If R = I{X,X),

0, then (1.7.19) is dear from (1.7.18).

= 0 and (1.7.19) is evident. Let 0 < R < I(X,X).

e > 0, there exists v 6 Q i ( R ) such that d(i/) < D{R)+e.

then

Then, for any

Since c € Qj(i)(fl)-l-£),

A ( D ( i I ) - r £ • ) < / ( * ) < ft.

(1.7.21)

Note that J(c) > f t i f d(y) < D { R ) - e. This means that (1.7.22)

R < R ( D ( R ) - E ) .

Since J t ( D ) is continuous, (1.7.19) follows from (1.7.21) and (1.7.22). The equation (1.7.20) can be shown i n the same way.

•

1.8 E N T R O P Y F O R G A U S S I A N

DISTRIBUTIONS

The Gaussian distribution is known as the most important continuous distribution. Its mathematical structure allows a much more thorough analysis than is possible w i t h many other distributions. Indeed for Gaussian distributions the information functions, such as continuous entropy, relative entropy, mutual information, and rate-distort ion function, can be calculated exactly.

I n this section

the formulas are derived to calculate these quantities for Gaussian distributions. Moreover, we give various characterizations of Gaussian distributions i n terms of entropy and mutual information. These results suggest to us that the Gaussian distribution occupies a quite important position i n the development of information theory. Definition

1.8.1. If X

= (JSj,Xj)

is a d-dimensional continuous random

variable w i t h probability density function

9

{

x

)

= (

2

, ) ' / W / s

e

x

p

H

(

x

-

a

)

r

_

i

(

x

-

a

)

,

| •

x

e

r

j

'

( i

-

8 i

»

then we say that X is a d - d i m e n s i o n a l G a u s s i a n r a n d o m v a r i a b l e (or v e c t o r ) , or that X is w i t h i f - d i m e n s i o n a l G a u s s i a n d i s t r i b u t i o n N(a, F). Here a = ( a i , . . . , a j ) £ R*, r = (7i>)i,j=i,...,
48

ENTROPY

that X has mean E\Xi\ — a; and covariance E\(Xi — at){Xj

—
The

distribution iV(a, T) is called a Gaussian distribution w i t h mean vector a and covariance m a t r i x V. Especially, in case of d — 1, the density function of (1.8.1) is of the form x e R (a e R , a > 0).

(1.8.2)

I n this case, we say that A" is a (one-dimensional)

random variable w i t h distribution N(a,c ),

Gaussian

where a is the mean and a

2

2

is the

variance of X.

If [X\,X )

is a fc-dimensional Gaussian random vector and X +\,X&

k

are

K

linear combinations of X\,...,X

(k < d), then we say that X

k

is a degenerate Gaussian random vector.

—

(Xjt...,Xj)

I t is known that X = (Xi,Xj)

is

Gaussian (including the degenerate case) i f and only i f every linear combination of Xi,Xi

is a Gaussian random variable.

The importance of Gaussian distribution i n applied probability is usually attributed to a fundamental result, known as the central limit theorem, which states, roughly speaking, that if a random variable X is generated by adding together a large number of mutually independent random variables then X w i l l always have an approximate Gaussian distribution, irrespective of the form of the distribution of the individual component random variables. I n view of this remarkable result, it is reasonable to suppose that the errors involved i n the measurement of most physical quantities would have distributions very close to Gaussian distributions, because such errors would generally arise as the combined effect of a large number of independent sources of error. I t is also reasonable to employ a Gaussian random variable as a mathematical model of a physical noise i n communication system. Let us start w i t h the calculation of the continuous entropy of a Gaussian distribution. T h e o r e m 1.8,1, Let X — (X),Xd)

be a d-dimensional Gaussian random vec-

tor w i t h distribution iV(a, T). Then the continuous entropy of X is given by h(X)

= ±\og{(2« ) \r\}. e

(1.8.3)

d

In particular, i f X is a one-dimensional Gaussian random variable w i t h distribution N(a,o- ), 2

then (X)=

h

-log(27re<7 ). 2

(1.8.4)

1.8

ENTROPY

FOR

GAUSSIAN

49

DISTRIBUTIONS

P r o o f . Since the density function g(x) of X is given by (1.8.1),

= \ log{(2^) |r|} + | j (x) {(x - a ) r - ' (x - a ) ' } dx i

fl

(1.8.5)

Noting that the covariance is given by T.j = jff(*){*,

- ai)(ij -

and denoting by vjj the ( i , j ) component of T

- 1

a,)dx

, we can see that

(1.8.6) where Tr(A)

denotes the trace of a matrix A. The formula (1.8.3) follows from

(1.8.5) and (1,8,6). The equation (1.8.4) is obtained as a special case of (1.8.3), where d = 1 and |r| = a . 2

•

It is noticed that the entropy h(X) does not depend on mean vectors. The relative entropy of Gaussian distributions is calculated as follows. T h e o r e m 1.8.2. Let ji and u be d-dimensional Gaussian distributions N(a.,T) and N(b,

A ) , respectively. Then

In particular, i f y. and v are one-dimensional Gaussian distributions N(a,a } 2

and

JV(fc,r ), then 2

(1.8.8) P r o o f . Denote by p ( x ) and q(x) (1.4.5), H(ji\f)

the density functions of ft and v.

Then, by

is given by

(1.8.9)

ENTROPY

50

Since g(x) is given i n the form (1.8.1) (replacing a and F by b and A respectively), we have

- Jp(x)}ogq(x.)dx = ^\og(2w) + ^log\A + I Jp(x){(x

- b ) A - ( * - b ) ' } dx.

(1.8.10)

l

Note that |p(x){(x-b)A-'(x-b)'}dx =

/ ( x ) { ( ( x - a) - (a - b ) ) A " ' ( ( x - a ) - (a - b ) ) ' } dx

=

/ p(x){(x - a J A - ' O " < 0 ' } * t + ( » - b ) A " ' ( a - b)'.

P

(1.8.11) I n the same manner as i n (1.8.6) we have J p ( x ) { ( x - a ) A " ' ( x - a)'} dx = TV ( r A " ) .

(1.8.12)

1

Combining (1.8.10) - (1.8.12) we obtain -

f p ( x ) l o g g f x ) dx = | log(2x) + - log |A| l

+ -Tr ( r A " ) 1

l

+ i((a-b)A- (a-b)'}.

(1.8.13)

1

Since, using (1.8.3) or similarly as above, we have - j P ( X ) l o g ( x ) d x = ± i o ( 2 ^ ) + \ bs |r| + \ T T ( r r - ) , P

1

g

the equation (1.8.7) follows from (1.8.9) and (1.8.13). The equation (1.8.8) can be obtained as a special case of (1.8.7).

•

We now proceed t o calculate the mutual information. T h e o r e m 1.8.3. Let X = (Xi,...,X % k

Y = (Y ...,Y,), U

{X,Y)

be, respectively

k, I, k + l dimensional, Gaussian vectors w i t h covariance matrices A, B, C. Then « « - f i « B f f i .

( 1

. .„, 8

1.8

ENTROPY

FOR

GAUSSIAN

51

DISTRIBUTIONS

In particular, i f k = I = 1, then I(X,Y)

= - -log(l-p(X,Y) ), l

(1.8.15)

2

where p(X, Y) is the correlation coefficient of X and Y. P r o o f . The equation (1.8.14) is an immediate consequence of (1.6.11) and (1.8.3). Assume that k=

I = 1. Then the covariance matrix C is given by r - (

°

(" \ T

2

where a and T are the variances of X and Y, respectively, and p = Thus (1.8.15) is obtained by substituting 2

2

\A\ = a , 2

into (1.8.14).

\B\=r ,

\C\ =

2

p(X,Y).

* r\l-p ) 2

2

•

It is shown t h a t , among all continuous distributions w i t h given covariance matrix, the Gaussian distribution has the maximum entropy. We may say that this fact is one of the major reasons why the Gaussian distributions play so important roles i n information theory. T h e o r e m 1.8.4. Let g(x)

be the density function of a d-dimensional Gaussian

distribution JV(a, F) and p ( x ) be an arbitrary density function of a continuous distribution w i t h the same covariance matrix T. Then h( )
(1.8.16)

P

P r o o f . Since the entropy h(g) assume that g(x)

does not depend on the mean vector, we may

and p ( x ) are of zero mean. Then I x xj (x)dx

J i i p ( x ) d x = 0,

{

P

= 7,y,

where 7,j is the ( i , j ) component of T. Using (h.3) and (1.8.1), we have h(p) <-J

p(x)logg(x)dx P

( x ) i o g { ( 2 T ) / | r | / } dx +1 ' 1,

1

2

1

f p{x))xr-V}

2

i

J

dx. (1.8.17)

ENTROPY

52

Since p ( x ) and s ( x ) have the common covariance matrix, i t is clear that the righthand side of (1.8.17) is not changed by the replacement of p ( x ) by g(x) equal to h(g). Thus we have obtained (1.8.16).

and is

•

Another characterization of a Gaussian distribution is given i n terms of relative entropy. If a reference measure is Gaussian, then the Gaussian distribution minimizes the relative entropy over the set of all continuous distributions w i t h a specified mean vector and a covariance matrix. T h e o r e m 1.8.5. Let p and v be d-dimensional Gaussian distributions

N(a,F)

and JV(b, A ) , respectively. Assume that T is an arbitrary continuous distribution w i t h the same mean vector a and covariance matrix I " as p. T h e n H{n;v)<

P r o o f . We denote by g(x), g(x)

(1.8.18)

H{T;U).

and p(x) the density functions of u, ft and T ,

respectively. Then we have H(p; u) = -h(q)-

Jg(x)log (x)dx

(1.8.19)

9

and H(r-u)

= -h(p)

- j p ( x ) l o g ( x ) dx

(1.8.20)

g

(cf. (1.8.9)). Let us recall the proof of Theorem 1.8.2. Since p and T have the same mean vector and covariance matrix, we see that (1.8.13) is valid not only for Gaussian density g(x) but also for p ( x ) , so that j (x)logq(x)dx = J p(x)log (x)dx. 3

(1.8.21)

9

As we have already shown i n Theorem 1.8.4, the entropy h(p) is not greater than h(g). Therefore (1.8.18) follows from (1.8.19) - (1.8.21).

•

From the viewpoint of mutual information, Gaussian random variables have an interesting property. Given a fc-dimensional Gaussian vector X° =

(Xf,X®)

and a /-dimensional covariance m a t r i x , i t will be shown that the mutual information I(X°,Y)

is minimized by choosing the Gaussian random vector over the set

of all random vectors w i t h the given covariance matrix.

l.S ENTROPY

T h e o r e m 1.8.6. Let A"

FOR GAUSSIAN

= (X?, ...,X%) be a fc-dimensional Gaussian random

0

vector. A n d let Y = (Yj,Y,) (X ,Y) a

53

DISTRIBUTIONS

and Y° = (Y?,Y,°)

= (X°,...,Xt,Y ,...,Y,)

and (X"^)

1

be random vectors such that

are (fc + I)-dimensional continuous

random vectors w i t h covariance m a t r i x T = (fij)ijmi„..,k+l

and that { X ° , y ° ) is

Gaussian. Then I(X ,Y°)
Proof.

(1.8.22)

0

We may assume that X ,Y

and Y°

sue with mean zero. x)

5 W , 9 ( y ) , ?°(y), r ( x , y ) , r°(x,y) (x = f>,

e R * , y = (yi,...,y,)

t

the probability density functions of X", Y, Y°, (X ,Y), 0

Since g(x),

Denote by

(X°,y°),

6

R ) 1

respectively.

and r°(x, y ) are density functions of zero mean Gaussian distri-

q°(y)

butions, we know that l o g r ° ( x , y ) / { f f ( x ) g ° ( y ) ) is a quadratic function of ( x , y ) : r°(x,y)

log

(1.8.23)

?(x)?°(y)

i,J=l

where Z{ = n for 1 < i < k, Z{ = y i - k for k < i < fc+1, and o,j and 4 are constants depending only o n the matrix T. By assumption, / J R . '

/

z z r°(x,y)dxdy i

/

=

j

J R *

J R '

(1.8.24)

2 , Z j r ( x , y ) dxdy = 7,

J R *

Thus i t follows from (1.8.23) and (1.8.24) that (1.8.25)

jt»f°(y) O n the other hand, using (1.6.11) and (h.3), we obtain I{X°,Y)

= h(X°) , , M

'JJ

X

,

y

)

Jj

+ u

+

r(x,y) • «(y)

Kxpr) ?(y)

s

//[Kx,y),

yy

i^(y7

r (x,y) B

l

o

E

^(yr

q{y)dxdy q(y)dxdy

r fx v l D

(1.8.26)

'fl(x) °(y) g

The inequality (1.8.22) is now clear from (1.8.25) and (1.8.26).

•

This theorem enables us to calculate the rate-distortion function of a Gaussian random variable under the mean square error. We treat here only the one-

si

ENTROPY

dimensional case. The multi-dimensional case will be studied later. Under the mean square error, the rate-distortion function of a real random variable X is given by R(D)

= R(D;

X) = i n f { / { X , Y ) ;

E[(X

- Y) ]

< D },

2

(1.8.27)

2

where the infimum is taken over all real random variables Y satisfying the condition E\(X - Y) ] 2

< D

2

D(R)

(cf. Def. 1.7.1). The distort ion-rate function is given by X) = inf{<,/E[(X

= D(R-

-Y) \;

I{X,Y)

2

< R}.

(1.8.28)

T h e o r e m 1.8.7. Assume that X is a Gaussian random variable w i t h distribution N(a,
Then _3 '

D(R)

D > 0,

g log max ( 1,

fi(D)= =


(1.8.29)

R > 0.

R

(1.8.30)

P r o o f . We may assume that a = 0. If D > tr, noting that a random variable Y s 0 satisfies E[(X The error E\(X

- Y) }

= o

2

— Y) \ 2

< Ef,

2

we see that R(D)

0. Let D < a.

-

is determined by the covariance m a t r i x of (X, Y).

On the

other hand, once covariance matrix is specified, by Theorem 1.8.6 we see that the mutual information I(X,

Y) is minimized i f (X, Y) is Gaussian. Hence the infimum

in (1.8.27) is achieved by a Gaussian random variable. So we may assume that Y is a zero mean random variable such that E\(X

— Y) ) 2

< D

2

and (X,Y)

is

Gaussian. I t is known that the o p t i m a l mean square predictor of X based on the observation of Y is given by the conditional expectation X = E\X\Y]

=

^

Y

(see Sec, A.2), and the error is bounded by E[(X Denote by p — p(X,X) E[XX]

= E[X ], 2

- X) }

< E[(X

2

- Y) ] 2

< D. 2

the correlation coefficient of X and X.

one can show that ,

=

{E\XX\}

2

E[X }E[X } 2

2

=

E\&) E[X*Y

(1.8.31) Then, noting

1-8

ENTROPY

FOR

GAUSSIAN

DISTRIBUTIONS

55

so that ,

,2_E[X*)-B[X'\

E\{X-X) } 2

E[X \

P

<J<

2

Therefore, using (1.8.15) and (1.8.31), we have AX

Y) = / < * )

= \ log - J K J _ > l log

(1.8.32)

meaning that R(D)

> ^log^.

(1.8.33)

Let Z be a Gaussian random variable w i t h distribution iV(0, Z> (1 2

D a~ )) 2

2

and

independent of X , and define V by

Then i t is easily shown that £[(Jf - y ) j = / J and X = Y s

Therefore, i n this

2

case, inequalities (1.8.31), (1.8.32) and consequently (1.8.33) turn into equalities. Thus (1.8.29) is proved. By definition, D(R)

< a. Using (1.7.19) and (1.8.29) we

obtain

Solving this equation we have (1.8.30).

•

Here, using this theorem, we derive a lower bound for the mean square error which is given i n terms of mutual information. This result will play an important role to show the optimality of codings. T h e o r e m 1.8.8. Let X be a zero mean Gaussian random variable w i t h variance (7

2

Then, for any real random variable Y, the mean square error is bounded by E[(X

P r o o f . Put R = I(X,Y). y/E\(X

yielding (1.8.34).

•

-

> a

Y} } 2

2

e

-

2

,

l

x

^

(1.8.34)

Then by (1.8.28) and (1.8.30), -

Yf)

a

D

W

=

a

t

~

R

=

<**~

,

KX,Y)

ENTROPY

56

HISTORICAL

NOTES

Most part of the concepts and results here (as i n the other chapters) are due to Shannon (103, 106]. There are a number of excellent references on information theory. Some of them are Fano [38], Gallager [43], Pinsker [97], Blahut [15], Gray [47], and Cover and Thomas [23]. Most of the rather general concepts i n information theory, treated in this text, are also contained in these texts. The characterization of entropy, Theorem 1.2.3, was given by Shannon [103] i n a heuristic manner, and was proved by Khinchin [78] in a rigorous way. The proof given here is due to Faddeev [37] (see also [113]) which is different from Khinchin's proof. Fano's inequality, Theorem 1.2.4, was obtained by Fano [38]. Axiomatic treatment of various kinds of entropy is given i n [1]. Relative entropy was introduced by Kullback and Leibler [84] (see also [83]), The properties of relative entropy, given in Sees. 1.4 and 1.5, are found i n [24, 97). Theorem 1.4.4 is given i n [30, 115], Rate-distortion function was first introduced by Shannon [105] and has been studied i n detail by Berger [8]. Rate-distort ion function is also called e-entropy. Kolmogorov [79] and Pinsker [96] have studied e-entropy of stochastic processes, they have been especially interested i n the asymptotic behavior of s-entropy when e tends to zero because i t expresses the complexity of the processes. The asymptotic behavior of f-entropy of finite-dimensional random variables has been examined by Lin'kov [85]. Theorems 1.8.6, 1.8.7 and 1.8.8 are due to Pinsker [96], Shannon [105], Ihara [58], respectively.

Chapter 2 Stochastic Processes and E n t r o p y 2.1 E N T R O P Y

RATE

In this section, we introduce important classes of stochastic processes, like Gaussian processes, Markov processes, and stationary processes.

Then we dis-

cuss how to define entropy, relative entropy and mutual information for stochastic processes. A real (or complex) stochastic process is a system '{Xti t £ T } of real (or complex) random variables w i t h time parameter I f T .

If the time parameter space

T is equal to the set Z = (0, ± 1 , ±2,...} of all integers or a subset of Z, then {Xt',t

{Xt\t

(E T )

is called a discrete time stochastic process.

On the other hand,

e T } is called a continuous time stochastic process, if T is equal to the set

R of all real numbers or a subinterval of R. I n the following we assume that each X i is a complex random variable defined on a probability space (£1,8,/*), unless otherwise stated. D e f i n i t i o n 2 . 1 . 1 . A system { X ; t £ T } of real random variables is said to be a t

G a u s s i a n s y s t e m , if the joint distribution of finite set {f j , f „ }

(Xt , t

X

lrl

)

is Gaussian for every

C T . I n particular, if T is a time parameter set, a Gaussian

system is called a G a u s s i a n process.

For a Gaussian system X = { X , ; t EE T } , since the probability distribution of 57

STOCHASTIC

58

AND

ENTROPY

is determined by the mean vector and the covariance m a t r i x , the

(X, ,...,X, } l

PROCESSES

n

distribution of X is determined by m(t)

-

E[X,\

dP(u),

/ X,{w)

=

Jn

t £

T,

and 7

( f , a) - £ ( ( * " « - M ( f f t i & i - m(s))],

*, t € T .

As functions of t £ T and ((, s) £ T , m ( t ) and 7(1, s) are called the expectation 2

function and the covariance function of X, respectively. D e f i n i t i o n 2.1.2. A stochastic process ( X , ; t £ T } is called a M a r k o v process, if P(X,

£A\X ,

u<s)

U

=

(2.1.1)

P(X,€A\X,)

holds for every s < t and every Borel set A, where P{X

t

conditional probability of {X

£ A ) given Y (see Sec.

t

£ A \ Y ) denotes the

A.2 for the definition of

conditional probability).

To be precise, (2.1.1) holds i n the sense w i t h probability one.

We shall not

repeat such a remark i n the sequel. D e f i n i t i o n 2.1.3. Let T = Z or T = R . 1°)

A (strictly) s t a t i o n a r y process X = { X t \ t £ T ) is a stochastic process

whose distribution is shift invariant; that is, the distribution of ( J f ,

] + J

,Xt„+ ) a

is independent of s for any positive integer n and f i , ...,(„ £ T . 2°)

A stochastic process

X

—

{Xiit

£ T } is said to be w e a k l y s t a t i o n a r y ,

if £[|X,| ] is finite, and E [ X ] = m and E \ ( X , + , - m)(X, 2

S

- m)] = ( ( ) do not 7

depend on s, where z denotes the complex conjugate of a complex number z. We call the function 7 ( t ) , £ £ T , the auto covariance function, or simply the covariance function of X.

If E[|X,| ] is finite, then a strictly stationary process is clearly weakly stationary. 2

If a Gaussian process is weakly stationary, i t is also strictly stationary because the distribution of the Gaussian process is determined by its mean and covariance functions.

I n this book, both strictly and weakly stationary processes w i l l be

referred to as stationary processes.

S.l ENTROPY

59

RATE

E x a m p l e 2 . 1 . 1 . A B r o w n i a n m o t i o n is a Gaussian process such that

E\B(t)]

= 0 and

E[B(t)B(s)\

= t/\s

E[\B(t)-B(s)\ }

=

2

min(t,

(-

B = {B(t)\t

>

0}

I t is easily seen that

s)).

\t- \.

(2.1.2)

s

I t is also seen t h a t , i f Si < s < d < i , then 2

2

E{(B(t )-B(t ))(B( 2

namely B

=

-•£?(([) is independent of

B(t ) 2

{B(t)}

l

3

2

)-B( ,))]

= Q,

3

B ( s i ) . Thus the Brownian motion

B(s }2

is a Gaussian Markov process w i t h independent increments.

E x a m p l e 2.1.2. A n O r n s t e i n - U h l e n b e c k B r o w n i a n m o t i o n is a stationary Gaussian process {X,\ t € R.} w i t h zero mean and covariance function 7

( ( - s ) =
(2.1.3)

J

where c > 0 and a / 0 are constants. I t can be shown that the Ornstein-Uhlenbeck Brownian m o t i o n is a Markov process (see Sec. 2.5). Let X — {X„}

Even if each X„ is a

be a discrete time stochastic process.

discrete random variable, i n most cases, the entropy

diverges to

H(Xi,...,Xn)

infinity as N —» oo. I n this sense, the process X — {X„}

has infinitely large

entropy. This observation suggests that a quantity which plays an important role is, not the l i m i t of

H ( X \ , X

growth of the entropy. [X\,

...,X„)

N

b u t the rate l i m / j „ j V

) ,

—

of

H(X\,Xn)

We define the entropy rate as this rate of growth. I f

has a continuous distribution, limjv—oo

replaced by l i m w - . c N~ h{X\,..., x

D e f i n i t i o n 2.1.4.

- 1

(a)

N~ H(Xi ..., l

t

XN)

should be

Xfj).

Assume that each X

n

(n g Z

+

= { n 6 Z; n > 0 } ) is a

discrete random variable. Then the e n t r o p y r a t e or the p e r u n i t t i m e e n t r o p y of the process X — { A } is defined by n

H~(X)

= J '

m

^H(X ...,X ), it

N

(2.1.4)

N—»oo iV

when the l i m i t exists. (b)

Assume that

(X\,...,XN)

>s continuously distributed for each N

£ Z

Then the e n t r o p y r a t e or the p e r u n i t t i m e e n t r o p y of the process X =

+

{X„}

is defined by k(X}=

lim I f i ^ , , , , - ^ } ,

(2.1.5)

STOCHASTIC

60

PROCESSES

AND

ENTROPY

when the l i m i t exists. Here we shall show that the limits in (2.1.4) and (2.1.5) exist for any stationary processes. T h e o r e m 2 . 1 . 1 . Let X = ( X „ ; n e Z ) be a strictly stationary process. 1°)

I f each X „ is a discrete random variable, then the l i m i t i n (2.1.4) exists

and lim ± (V—oo iV

H ( X ) =

where X " =

( X

0

0

, X - i , X -

2

2°) it

If

( X , , . . . , X

N

1

, . . . , X

) =

N

1

0

T

(2.1.6)

H(X \XQ),

and r / ( X , | A " ) =

, - )

is the conditional entropy of X h(X ...,X ),

H ( X

timx-*,

given the past X$ of X =

H ( X , \ X

0

,

. - , X ^

N

)

{X„}.

n £ Z , has a continuous distribution w i t h finite entropy

) ,

+

then the l i m i t i n (2.1.5) exists and

n

£(*)= where /i(Xj |

X$)

lim

~ h ( X

N—oo JV

lim,v—oo fi.(JT] |

=

P r o o f . We shall prove only 2"). stationarity,

i

k 1

N

(2-1.7)

= h(,Xi\Xe%

)

X(,,X—Jf)-

Part 1") can be shown i n the same way. =

k(X \X ,...,X - ) k

, . . . , X

1

1

k+2l

By

Thus, using (h.6), we

h(X \X^ ...,X ). 0

have h(X ...,X ) u

Since h{Xi)

mean j V

=

N

> h(Xi\X )

_ 1

0

h(Xi\Xo,

h[X,)

+ h(X \X )+ 1

-

0

+

h(X \X ,...,X_ ). l

> ••• > h(Xi\X(,,...,X-. + ) N

0

N+2

(cf. (h.5)), the arithmetic

2

. . . j X - k + a ) monotonically converges to h(X j | X Q ) , as

N —• oo. Thus we have lim — - f t f j E i , X ) n—-cc iV The proof is complete. • N

=

Urn iV—»oo

| X ,X_w) a

This theorem states that the entropy rate h(X)

= n(A"! | X^).

is equal to the conditional

entropy of one step "future'' X i when the "past" X$ is known. Let us introduce the relative entropy rate and the m u t u a l information rate which w i l l play important roles i n the sequel. These quantities are also defined as the rates of growth of the relative entropy and the mutual information, respectively. Let X = {X„} ^

(

y

W

and Y = {Y„)

be discrete time processes, and denote by f i ^ ' and

' the probability distributions of

{ X , , X

N

)

and ( K i , Y ) , N

respectively.

S.I ENTROPY Definition 2.1.5.

61

RATE

The r e l a t i v e e n t r o p y r a t e H { p

1°)

x

\ o f

X w i t h respect

to Y is defined b y fejfWrfPi&l

StftXipr) =

(2.1.8)

when the l i m i t exists. 2°)

The m u t u a l i n f o r m a t i o n 7(X,Y)

=

r a t e 7(X,Y)

l i m ±I{(Xu.~,X UYl.~,X )), iV—-co JV N

when the l i m i t exists. T h e quantity mutual

between X and Y is defined by (2.1.9)

N

is also called the p e r u n i t

I(X,Y)

time

information.

It is noticed that the limits in (2.1.8) and (2.1.9) do not always exist, even i f X

= \X„) and Y = {Y„} are stationary.

For stationary Gaussian processes,

we shall give explicit formulas of entropy rate and relative entropy rate later (Sec. 2.4). The m u t u a l information rate will be investigated i n Chap. 5. The distribution fix

of the process X — { X } is a probability measure on X = R . Let p and z

n

v be shift invariant probability measures on X and denote by pfj the marginal distribution of p on W . The relative entropy rate H ( p ; v) of p with respect to v N

is defined similarly by ffO^J-KiD

lfffjw*»).

(2.1.10)

N—-oo JV

The relative entropy rate possesses the following properties. T h e o r e m 2.1.2. Let p, p ' , p " , v, i/', v" be stationary probability measures on X = R

Z

1°)

(Positivity)

The relative entropy rate H ( p ; u) is non-negative.

2°)

(Convexity)

If p = ap' + (1 - ot)p" and v = a v ' + (1 - a ) u " , then Hip;

u) < a f f f j l ' j f ' ) + (1 - a)H(p";

*"),

(2.1.11)

where 0 < a < 1 is a constant. 3")

(Affine property) H(p-

I f p = ap' + (1 - a ) p " and 0 < a < 1, then v) = oH(p';

i/) + ( l - <>)#(/."; c).

(2.1.12)

P r o o f . Properties 1°) and 2°) are clear from Theorem 1.4.1, Theorem 1.5.1 and the definition (2.1.10).

02

STOCHASTIC

3°)

PROCESSES

AND

ENTROPY

"w) "

ff0*ffi»w3

By 3°) of Theorem 1.5.1, 0 < V; " « ) + 0 ~

^ Mai-

Dividing by iV and letting N tend to infinity, we obtain (2.1.12).

For continuous time processes X = {X(t);t

•

6 R } and Y = {Y{t);t

ER},

the relative entropy rate and the mutual information rate are denned i n a similar f Ti {T\ i_ • • manner as i n the discrete time case. We denote by p and p the probability x

distributions of {X(t};0


D e f i n i t i o n 2.1.6.

The r e l a t i v e e n t r o p y r a t e

1")

and {Y{t)\0

x

Y

< t < T } , respectively. H{HX\I>-Y)

<&X ' w

t

n

respect

to Y is defined by

Bfarw)- J "

i'O^Pi^ ). 7

(2.1-13)

when the l i m i t exists. 2°)

r a t e I(X,

The m u t u a l i n f o r m a t i o n

7(X,K)=

Y)

between X and Y is defined by

Urn i / T C * . n

(2-1-14)

when the l i m i t exists, where I {X,Y) T

= niXffilQ

< t < T},iF(i);0 < t < r } ) .

The quantity 1{X, Y) is also called the p e r u n i t t i m e m u t u a l

(2.1.15) information.

In general i t is a difficult task to calculate the relative entropy rate and the mutual information rate for continuous time processes, even i f they are stationary Gaussian. Some results w i l l be given i n Chap. 6 when the processes are Gaussian. Note that we can define the relative entropy rate H ( p ; v ) for stationary probability measures ft and v a a X =• R

( _ 0 0 , O O )

in the same way as (2.1.13). Then we

can show that the relative entropy rate for continuous time case also possesses the properties stated i n Theorem 2.1.2.

8.S DISCRETE

TIME

STATIONARY

PROCESSES

63

2.2 DISCRETE T I M E STATIONARY PROCESSES This section is devoted t o studying the spectral representation, the canonical representation and the moving average representation of discrete time stationary processes. These representations are important tools to analyze stationary processes. In the following, we consider a discrete time weakly stationary process X = ( X , | n £ Z } . T o study spectral analysis, it is rather convenient to treat complex stochastic processes. So each X„ may be a complex random variable. Note that our discussions can be applied t o real stochastic processes without any changes. Since the process X — {X„} is stationary, the mean m = E[X ]

(2.2.1)

k

and the covariance „

r

= E[(X

- m)(X

n+k

k

- m)j

(2.2.2)

do not depend on k £ Z. We may assume, without loss of generality, that m = 0. Recall that, as a function of n £ Z , f„ is called the covariance function of X. B y definition, i t is clear that 7n = 7 - „ ,

" G Z.

(2.2.3)

The covariance function can be represented i n the form „ = J

T

e

i n A

dF(A),

neZ,

(2.2.4)

where F ( A ) (— IT < X < it) is a non-decreasing right continuous function with F(—7f) = 0, F(ir) = 7o- The function F(X) is uniquely determined by the covariance function. The expression (2.2.4) is called the s p e c t r a l d e c o m p o s i t i o n of the covariance function and F(X) is called the s p e c t r a l d i s t r i b u t i o n f u n c t i o n . I n particular, i f F(A) is absolutely continuous, then the function /(A) (-rr < A < TT) such that F(A) = j

f(t) dt,

- T < A < 7T,

(2.2.5)

is called the s p e c t r a l d e n s i t y f u n c t i o n ( S D F ) , or the p o w e r s p e c t r a l d e n s i t y of X. I n this case (2.2.4) turns to l n

= j\-»*f(X)dX,

n€Z.

(2.2.6)

6-1

STOCHASTIC

PROCESSES

AND

ENTROPY

Note that the SDF /(A) is non-negative and satisfies /(A)dA =


7 o

(2.2.7)

Furthermore, i t is known that the process X = {X }

itself can be expressed i n

n

the form X„=

f

e

i n A

d<(A),

neZ,

(2.2.8)

J-n

which is called the s p e c t r a l r e p r e s e n t a t i o n of X. We need t o note that neither d£ is a measure i n the usual sense nor the integral i n (2.2.8) is the usual one. The set (C(A); - w < A < TT) is a system of zero mean complex random variables C(A) s < ( A , u ) such that £[C(A!X(A )) = 0

if

2

A,nA

where A ; is a subinterval of [ - I T , JT] and ( ( A )

2

= ^,

(2.2.9)

= C(6) — ( ( a ) for A =

(a,b\.

In

general, if a system {£(A);— 7r < A < TT) of random variables satisfies the property (2.2.9), then

< A < T } is called a random measure. We denote by

{d({\);-TT

the class of all random variables £ such that / |£(w)|

L (Q,P) 2

2

n

and similarly denote by L {[ — jr, jr], F) such that jf_

|i^(A)| d F ( \ ) 2

ip £ £ ([—jr, IT], F).

<

oo,

< oo. Then, similarly to the Wiener integral (see

Sec. A.3), we can define the stochastic integral ?

dP(u)

the class of all measurable functions ip

2

J2

*fi(X)

V

dC(A) for each function

The right-hand side of (2.2.8) is the stochastic integral i n

this sense. For each ip, ip £ L ([—t, 2

T], F),

J _
belonging to £ ( f i , P ) and i t holds that 2

j
E

In particular, for each interval

^(AK(A)j =j A=

(2.2.10)


(ft,6]i we have

la(A)d^(A) — C(A)

J2

W

and

F[|C(A)|] = F(A) = Fib) - F(a), 2

where 1&(A)

is the indicator function;

' We denote by H (X) n

H (X) n

if

C

H +\(X). n

I

A $ A.

0,

the subspace of L (Q,

P) spanned by X ,

2

A stationary process

X

k

=

{X } n

k < n . Clearly

is said to be d e t e r m i n i s t i c ,

S.S

DISCRETE

TIME

STATIONARY

PROCESSES

On the other hand, i f

then X is said to be p u r e l y n o n d e t e r m i n i s t i c . I f X is purely nondeterministic, then H (X)%H ^{X), n

meaning t h a t , at each time n , X

provides new information not contained in the

n

past { X t ; k < n } of X.

neZ,

n

Every weakly stationary process X — {X„}

is uniquely

decomposed into the sum of a purely nondeterministic process X' = {X' } n

deterministic process X"

=

X =X'„

+ X';,

n

where X' and X"

and a

{X„}: n g Z,

(2.2.12)

are mutually orthogonal. If X is Gaussian, then X' and A " are

mutually independent Gaussian processes. The decomposition (2.2.12) is known as the W o l d d e c o m p o s i t i o n .

Using the decomposition we can remove the de-

terministic part which is less interesting.

Consequently we may always assume

that stationary processes to be discussed are purely nondeterministic. I t is known that a weakly stationary process X is purely nondeterministic i f and only if the spectral d i s t r i b u t i o n function is absolutely continuous and its SDF f(X)

I/:

log/(A)dA < oo.

satisfies (2.2.13)

For later use we denote by S the family of all SDF's of purely nondeterministic stationary processes. Noting (2.2.7) and (2.2.13), we can show that S = {/ e £ ' [ - » , » ) ; / ( \ ) > 0 and / satisfies (2.2.13)),

(2.2.14)

where £ ' [ — T , T ] is the space consisting of all measurable functions such that Denote by

H*(X)&H*-1

that is the subspace of to

H„.\(X).

Then

(X)

the orthogonal complement of K „ _ , (A") i n

n

H„(X)

exists a random variable £„

9

H (X), n

consisting of all elements which are orthogonal

Ti (X)

is a one-dimensional subspace and there

W„-,(X)

€ H (X) n

6

H*-i{X)

such that £[|t;„| ] = I . Clearly 3

n € Z } is a sequence of mutually orthogonal random variables. Especially, i f X

is Gaussian, then

G Z ) is a sequence of independent random variables

w i t h standard Gaussian d i s t r i b u t i o n N(0

1). I t is clear that X„ belongs to the

STOCHASTIC

66

PROCESSES

AND

ENTROPY

subspace W„(£) of L ( f l , P) spanned by £*, k < n. Using the stationarity we see 2

that X

n

is expanded i n the form

- = Y -*£*-

x

" '

c

-- >

e z

(2 2 15

k=-oo

where c*, k > 0, are constants such that {ck}

|cjtj < oo. Note that the constants 2

are uniquely determined except multiplicative constants of modulus one. The

expression (2.2.15) is known as the m o v i n g a v e r a g e r e p r e s e n t a t i o n of A*. From the definition of { £ „ } and (2.2.15), i t is seen that a significant equivalence H (X)

= H ((),

n

holds.

We denote by B„{X)

n e Z,

n

(2.2.16)

the o-field generated by {X ;k

< n).

k

Then, if

X = { X ) is Gaussian, (2.2.16) is equivalent to n

B (A)

= 0 (O,

n

n

«EZ.

(2.2.17)

The relation (2.2.17), or (2.2.16), indicates the causality of the representation (2.2.15).

It may be said that the significance of the representation is primarily

becav e of the causality. Let X = {X„}

be a Gaussian process but not necessarily stationary. If X is

represented in the form n

*=-oo

(£!!=_oo |a ,*| < oo), where { £ „ } is a sequence of independent Gaussian random n

a

variables w i t h identical distribution N{0,1),

and the causality (2.2.17) holds, then

(2.2.18) is called the c a n o n i c a l r e p r e s e n t a t i o n of the process X.

The moving

average representation (2.2.15) for a stationary Gaussian process X is nothing but the canonical representation. Intuitively speaking, (2.2.17) means that, at each instance n ,

< n ) and {Xk',k

< n ] contain exactly the same information.

Moreover £„ is independent of {£*; k < n - 1} and consequently of {X ;k k

n — 1}. Therefore £„ expresses the new information provided by X„.

<

W i t h these

implications, the process £ = { £ „ } is called the i n n o v a t i o n p r o c e s s of A". Let { „ be a random variable w i t h mean zero and variance a

2

> 0, and £„'s be

mutually orthogonal. Then £ = { £ „ } is a weakly stationary process w i t h

E[tn k£k] +

=

(2.2.19)

2.S

DISCRETE

TIME

STATIONARY

67

PROCESSES

Therefore f has the SDF 2 fW

=

< A <

-t

Since £ has a fiat spectrum, i t is called a discrete time w h i t e noise. I f

is

Gaussian then i t is called a Gaussian white noise. I f £ 's are mutually independent n

and w i t h an identical probability distribution n, then ( = {f } n

is called an i . i . d .

process w i t h distribution ft. Obviously a Gaussian white noise is an i.i.d. process. Canonical representation has been successfully applied to solve the problem of prediction.

Let X

=

be a purely nondeterministic stationary Gaussian

{X„}

process. One of the most important problems of prediction is to predict the i : step " f u t u r e " A "

n +

t , based upon the observation of the "past" Xj, j < n. I f the

prediction error is measured by mean square error, then the problem is equivalent to finding a random variable X which minimizes the error E{\X

-

n+k

over the set of all functions of {Xj\j

X\ ]

< n).

2

The random variable which mini-

mizes the error is said to be the best p r e d i c t o r and the minimum error is called the m i n i m u m p r e d i c t i o n e r r o r . It is known that the best predictor of

X„

+k

based on the observation of X ; , j < n, is equal to the conditional expectation E[X \Xj,j n+k

(see Sec.


A.2).

The canonical representation is useful to solve the mean square prediction problem. T h e o r e m 2 . 2 . 1 . Let X = {X„}

be a purely nondeterministic stationary Gauss-

ian process w i t h canonical representation (2.2.15). Then the best predictor A"„,j, is given by n

X,

n k


= E\X \X„j n+k

£ )=-oo

Cn+k-jti,

(2.2.20)

and the m i n i m u m prediction error t\ is equal to (2.2.21)

£l=£[\X + -X rf\^fl\c,\\ n

k

n

P r o o f . We put Xn.k

= X+ n

k

- X .k = n

>

Cn+fc-ifi.

68

STOCHASTIC

Since

X_

since

X„,

n

k

k

£ W„(f) -

PROCESSES

H„(X),

Hence, for any

X

n k

H (£)

=

n

H (X),

is independent of

X,

n

n k

Xj,

< n.

}

< n ) , we have

= X(Xj;j

E[\X + n

ENTROPY

is a Function of A j , j < n . On the other hand,

X,

is orthogonal to

AND

-

k

X\ }

= E[\X , \ }

2

+ E[\X

2

n k

-

ntk

>£flA ,,| ] = £ | 2

n

The equality holds i n (2.2.22) if and only i f

X

=

C i

|

X\ } 2

(2.2.22)

2

This means that X „ , » is

X„ . lk

the best predictor and the minimum prediction error is given by (2.2.21).

•

The m i n i m u m prediction error is directly related to the m u t u a l information between the past

I(X ,X~) n+k

X~

=

and the future

{X„,X -\,...} n

X

n

+

k

-

T h e o r e m 2.2.2. Let X = {X„} be the same stationary Gaussian process as i n Theorem 2.2.1. Then i t holds that I ( X

a

+

,X-)

k

=

I{X

where e\ is given by (2.2.21) and

X„

k

, X

) =

n
11*3,

(2-2.23)

n

is independent of

+k

+

= £[|A" p] is the variance of X„.

7 o

P r o o f . Since

n

if

X

n

is given, using (1.4), (1.6) and

X„

ik

(1.8.15), we have I(X ,X;}

= I(X ,X , )

n+k

where

7=

-y(X , n+i

n+k

= -ilog(l -

n k

7

3

),

(2.2.24)

is the correlation coefficient. I t is easily seen that

X„ ) :k

,

,.i

=

,

E[\X»M*] E[\X , \ \ n k

Thus (2.2.23) follows from (2.2.24).

2

ill

_

70 4-

•

Concerning the coefficients in the moving average representation, the following result has been known. The proof is omitted.

S.3 DISCRETE

TIME

MARKOV

STATIONARY

PROCESSES

69

T h e o r e m 2.2.3. Let X = { X } be a purely nondeterministic stationary process. n

Then the coefficients {c,-} i n the representation (2.2.15) are given as the coefficients of the Taylor expansion of an analytic function i n the unit disc:

g c j V s V S e x p j - ; j '

where /(A) is the SDF of X.

C^log/(A)<&J,

|*|<1,

(2.2.25)

I n particular, substituting z = 0 into (2.2.25), we

have c

a

2.3 D I S C R E T E

J"

= v^exp

TIME MARKOV

log/(A)dAj .

(2.2.26)

S T A T I O N A R Y PROCESSES

Among the stationary processes autoregressive processes and moving average processes are fundamental and important. In this section we shall give a characterization of these processes in terms of their SDF. I t will also be shown that these processes have multiple Markov property. Let X = {X ; n

n <E Z } be a zero mean weakly stationary process.

Definition 2.3.1.

1°)

The process A" is called an a u t o r e g r e s s i v e

o f o r d e r I, or simply an AR(/) j = 1.

process

process, if A" is a linear combination of n

X'n—fo

and £„: l X„

where £ = {( \ n

2°)

n

= Y , i J=I a

X

» - i

+

"

e

Z

-

(«i

0)

(2.3.1)

€ Z} is a white noise such that (.„ is orthogonal to X j , j < n - 1 .

The process X is called a m o v i n g average process o f o r d e r m ( M A ( m )

process), if the moving average representation of X is given i n the form

k=0

where £ =

n € Z ) is a white noise w i t h variance one.

70

STOCHASTIC

3")

PROCESSES

AND

ENTROPY

If X is represented i n the form I

m

the process A" is called an a u t o r e g r e s s i v e - m o v i n g (;,m)

a v e r a g e process o f o r d e r

( A R M A ( l , m ) process), where £ = {£„] n 6 Z ) is a white noise w i t h

variance one such that (2.2.16) holds and that £„ is orthogonal to X j , j < n — 1.

I t should be noted that the white noise £ = { £ „ } i n 1", 2"), 3°) are the innovation process of the process X, which appeared in the moving average representation (2.2.15). For example, let X = {X ) a

be the ARMA(/, m) process given by (2.3.3).

Then i t is clear from (2.3.3) that x„ e H -i(X)

u w»(0.

n

Ue

n (X) n

u

H -i(0n

From these relations, inductively we can show that X„ € K ( 0 , B

£« e H „ ( A - ) ,

so that (2.2.16) holds. Hence £ = { £ „ } is the innovation process. Roughly speaking, the A R part (all the first terms on the right-hand side of (2.3.1) and (2.3.3)) indicates the dependence on the past of the process. As mentioned above, the M A part (the right-hand side of (2.3.2) and the second terms on the right-hand side of (2.3.1) and (2.3.3)) corresponds to the innovation, namely it indicates the new information brought by X

n

at each time n.

As w i l l be studied later, the mathematical structure of A R M A processes is considerably simple. Especially A R processes can be analyzed rather easily. On the other hand, since every purely nondeterministic stationary process can be represented as (2.2.15), i t can be approximated by M A ( m ) processes by taking the order m large enough.

This allows us to employ an A R M A process as a

mathematical model for a random phenomenon w i t h stationarity. Therefore we can say that A R M A processes play important roles not only i n theoretical study but also i n practical applications. Historically speaking, Yule [117] analyzed a series of annual Wolfer sunspot numbers, and he has shown that i t can be regarded as an AR(2)

process.

Here we give a classification of M A , A R and A R M A processes i n terms of SDF.

2.3

DISCRETE

TIME

MARKOV

STATIONARY

71

PROCESSES

T h e o r e m 2 . 3 . 1 . Denote by /(A) the SDF of the stationary process X. 1°)

I f A" is the A R ( ' ) process of (2.3.1), then

/

where A(z)

(

A

)

=

2 T 1 W -

is a polynomial of order / given by I A(z)

= Y *<-i* J

(<*> = - 1 ) ,

>

(2.3.5)

j=o

and a is the variance of £„. 2

2°)

I f X is the M A ( m ) process of (2.3.2), then

/(A) = ^\B{e< )\\

(2.3.6)

x

where f?(:) is a polynomial of order m given by

SW = ^ L V .

(2.3.7)

t=0

3")

I f X is the A R M A ( / , m ) process of (2.3.3), then

(2.3.8)

where A{z)

and B ( z ) are the polynomials given by (2.3.5) and (2.3.7).

Conversely, i f X has the SDF /(A) of (2.3.8) then X is an A R M A ( ( , m )

4°) process.

I n this case the coefficients i n (2.3.3) do not necessarily coincide with

those of the polynomials A(z)

and B{z).

I f we choose A(z)

and B(z)

as i n the

Remark given below, then the coefficients of the polynomials coincide w i t h those in (2.3.3). The same assertion is valid also for M A and A R processes.

Remark,

(i)

We may assume that the polynomials -4(2) and B { z ) have no

roots outside the unit disc. (ii)

A(z)

has no roots on the unit circle. Because, if A(z)

has a root a with

\a\ = 1, then this is in contradiction to rj[|A" | j = 70 = /__ /(A) dA < 0 0 . n

2

72

STOCHASTIC

PROCESSES

AND

ENTROPY

(iii) We may assume i n 3°) that A(z) and B(z) have no common roots. Because, if A ( Z ) and B{z) have common roots, then the process is an A R M A process of lower order.

P r o o f of T h e o r e m 2.3.1.

1°)

Denote by F { X ) the spectral distribution func-

tion of the AR(() process of (2.3.1). Since f = { ( „ ; « G Z ) is a white noise w i t h variance (Tg, using (2.2,19), the covariance function p

n

of £ is given by (2.3.9)

On the other hand, i t follows from (2.3.1) that Pn =

E\f t \ n+t k

r '

=

'

S

E

_

p -+k-pY°1 -'i

a

Lp=0

X

Xk

1=0

-i:

(2.3.10)

Since (2.3.9) and (2.3.10) hold for all n, the function F ( A ) should be absolutely continuous and the density /(A) should be given by (2.3.4). A R case 1°) and A R M A case 3°) can be proved i n the same manner. 4°)

Assume that X has the SDF of (2.3.8), and that A(z)

and B(z)

satisfy the

properties (i) - (iii) of Remark. We p u t

In = X

n

Then

rj =

Efon'lj]

=

- y^OjA" -j, /=1 n

n G Z.

{)?„} is a stationary process satisfying

E[i)„X -j]

0.

Using this fact, we can con-

\

n

— j\ >

m

,

and

E\r)n~n-m]

7* °-

=

n

struct a white noise £ = (£,,} w i t h variance one such that

r)„

B[{,,X,-] = 0, J < n - 1. Hence A" is represented as (2.3.3).

=

0,

Y^T=o

j

<

n -

m,

&*fn-t

•

Since the right-hand side of (2.3.8) is a rational function of e' , the SDF of the A

form (2.3.8) is said to be a rational SDF. For an AR(/) process, the covariance function is uniquely specified by the first ; + 1 covariances, T o . T i i — i 7 l -

A

t

first,

suppose that A" is an A R { 1 ) process of

S.3 DISCRETE

(2.3.1). Since £ [ { „

Y

n

TIME

MARKOV

STATIONARY

PROCESSES

73

, J = 0 (Jfc > 0), multiplying both sides of (2.3.1) by A%_*

and taking expectation, we have i k>0.

7* = £ « i 7 * - i >

(2.3.11)

Especially we have a set of equations, known as the Y u l e - W a l k e r e q u a t i o n , - 7 2

+ «i7i

+

i27o +

r (7,-2 Q

=0 (2.3.12)

-7i+i

+ " i 7 i +

Q

2 7 i - i

+

aa\

• ••+

=

0-

Here we have used (2.2.3). This means that, since the simultaneous linear equation 7i*o + 7 o 2 i +

7 i * 2 + ••- r 7 , _ j x j = 0

72^0

70^2 +

+ 7 i

I

i +

=0

\-Jt-2 < x

(2.3.13) 71+1^0 +

7 i ^ i + 7 i - i ^ 2 H

has a non-zero solution ( z , x , , n ) 0

+

T i ^ i -

0.

= (—l,ai,...,«(), the determinant of the

matrix consisting of the coefficients of (2.3.13) should be zero:

Therefore

71+1

71

70

7i

••

7 i - i

72

7i

70

••

7 , - 2

73

72

7i

7(+i

ii

= 0.

7 i _ i

is determined from

...

70,71,...,71

(2.3.14)

71

by solving (2.3.14), Similarly one

can see that n + y f* > 1) is a function of t _ i , . . . , 7 i + t _ i , and consequently of 7

7o,7t>—.71-

Next, suppose that we are given definite. Here we say (7_

t

( 7 0 , 7 1 , 7 1 )

7o.7i.---.7l

= 7 ^ ) is positive definite.

k = 1,2,..., as functions of

s u c n

that

(70i7l»—«7l)

' positive s

is positive definite if the matrix ( 7 m - n ) o i , « = a

1

Using (2.3.14), successively we define 7 1 + * ,

7o,7i,

7i-

Then

(70,7i,

7i+t)

l s

positive

definite for every k > 0, and we can show that there exists uniquely a weakly stationary process X = [X„] (-l,a ...,ai) u

w i t h „ , n £ Z , as the covariance function. Let 7

be a solution of the Yule-Walker equation (2.3.12). Then (2.3.11)

holds and one can show that X is an A R process of order at most I with expression (2.3.1). Note that, i f a\ ^ 0, then the order is exactly equal to I. Thus we have obtained the following theorem.

71

STOCHASTIC

PROCESSES

AND

ENTROPY

T h e o r e m 2 . 3 . 2 . Let 7 0 , 7 1 , . . . , 7 1 be constants such that ( 7 0 , 7 1 1 —> 7 i ) is positive

definite. Then there exists uniquely a zero mean A R process X = {X ; n G Z } of a

order at most / having covariances

7*,

70,71,—,7)

as the first

k > J, are determined from

I

+ 1 covaxiances. The remaining

70,71,—>7i

by solving the equations of

type (2.3.14). The coefficients a],...,aj of the A R expression (2.3.1) are determined from (2.3.11). Multiple Markov property of stationary processes is also an i m p o r t a n t concept to analyze A R M A processes. I n the following, for simplicity, we shall consider only real processes. A discrete time Markov process A" = { X } is also called a simple n

Markov process or a Markov chain. We introduce here the concept of multiple Markov property as a natural generalization of that of simple Markov property. There are two different ways to define multiple Markov process. Definition 2.3.2.

1°)

A stochastic process X = { X } is called an a t m o s t n

JV-ple M a r k o v process i n t h e s t r i c t s e n s e , if P ( X

n

+

<x\X„,X _ ...)

l

n

u

= P ( X

n

+

< x \ X

1

n

, . . . , X

n

-

N

+

l

) ,

(2.3.15)

holds for all n and x; I f X is at most JV-ple Markov b u t not at most { N — l)-ple Markov, then X is called an JV-ple M a r k o v p r o c e s s i n t h e s t r i c t s e n s e . A process X — {X„;n G Z } is called an JV-ple M a r k o v process i n t h e

2°)

w i d e sense, i f

successive conditional expectations

N

E[X +i\X -j, n

j

n

>

k,...,k+N

— l, are linearly independent b u t JV+1 successive J3[A" j| X„-j,

t =

+ N, are linearly dependent for any n G Z and k > 0.

n+

fc,k

0], t = j > 0],

I t is clear that a simple Markov process is nothing b u t an at most 1-ple Markov process.

From (2.3.15) i t is easily seen that an at most JV-ple Markov process

satisfies P(X„ <x\X ,X _ ,...) +k

n

n

1

= P(X» <x\X ...,X - ), +h

ni

n N+1

(2.3.16)

for all x, n and k — 1,2,.... Obviously (2.3.16) is a natural extension of (2.1.1). A n d the multiple Markov property i n the strict sense seems to be a concept of a natural generalization of simple Markov property. However, in some cases, the strict sense Markov property is rather restrictive and the wide sense Markov property seems to be more reasonable.

2.3 DISCRETE

TIME

MARKOV

STATIONARY

PROCESSES

75

Let us investigate the multiple Markov property of Gaussian processes. X

=

be a Gaussian process.

{X„}

Then, given

distribution of X „ * (k > 0) is Gaussian.

X

n

, X

N

Let

the conditional

- N ,

Hence we see that, if A" is JV-ple

+

Markov i n the strict sense, then i t is JV-ple Markov i n the wide sense. Moreover, we shall show that, while a Gaussian A R ( J Y ) process is nothing but an JV-ple Markov process i n the strict sense, a Gaussian A R M A ( JV,M) (M

< JV)

process is an JV-ple Markov process i n the wide sense. T h e o r e m 2.3.3. Let X = {X„}

be a purely nondeterministic stationary Gauss-

ian process. 1°)

The following equivalent relations hold. X is an JV-ple Markov process i n the strict sense •4=^ X is an AR(JV) process X has a SDF of the form (2.3.4) w i t h I = JV

2°)

Put X *

-

E[X \X , k

j

}

(2.3.17)

< 0], k > 0. Then the following equivalent relations

are also true. A" is an JV-ple Markov process i n the wide sense The subspace of L (Sl,P)

spanned by X t , k > 0, is jV-dimensional

2

X is an ARMA(JV, M)

{ M < JV) process

X has a SDF of the form (2.3.8) w i t h I = N, m = M < N. (2.3.18)

Proof.

1°)

Let X = {X„}

be an AR(JV) process w i t h expression (2.3.1) (re-

placing i by JV). Then, since (,

= P(€ +i B

= P(X

n + 1

<* <

is independent of X j , j < n, i t is true that

n+i

N

Y, > "+i-j\x ...,x - )

x\X

a

n

,...,X

x

n

ni

-

N

+

l

a N+l

),

so that A" is JV-ple Markov in the strict sense. Conversely, let A be an JV-ple Markov process i n the strict sense. Then i t can be shown that X

n

is expressed i n

the form (2.3.1) (replacing / by JV) w i t h a random variable £„ which is independent

76

S T O C H A S T I C

of X

n

P R O C E S S E S

- j , } > 0. Therefore X is an A R ( N )

AND

E N T R O P Y

process. The second equivalence i n

(2.3.17) has been shown i n Theorem 2.3.1. 2")

Let X

be an ARMA(JV, Jlf )(Jlf < JV) process w i t h expression (2.3.3)

(replacing ( f , m ) by

Then, since

(N,M)).

(k

>

is independent of

—M)

( j < — M ) , noting M < N and using (2,3.3) we know that every X a linear combination of

XQ, X - t ,

Therefore

...,X-pi+i.

wide sense. Conversely, let X — { X „ }

X

K

Xj

, k > 0, is

is ./V-ple Markov in the

be an JV-ple Markov process in the wide

sense. Then, since JV + 1 random variables

are linearly dependent, there

X Q , ...,Xfj

exist constants a , k = 0 , J V , such that ( a , a w ) ^ ( 0 , 0 ) k

0

and

TV

£ a * A V * = 0.

(2.3.19)

1=0

Here

a a^/ a

^ 0, since

and

Xn,Xpj-i

X ,...,Xpj l

a stationary process TJ = {T)„} by T?„ = - £ ) " F(nnA"(c) = 0 for k < n — N.

are linearly independent. Define = 0

a

**--*-

Then, by (2.3.19),

I n the same argument as i n the proof of 4°) of

Theorem 2.3.1, we can show that X is an ARMA(JV, M ) process. Here the order M

is equal to the maximum integer m such that £[rj,,rf _ ] / 0.

M

< N. The first equivalent relation i n (2.3.18) is clear by definition and the last

n

one has been shown i n Theorem 2.3.1.

m

Moreover

•

2.4 E N T R O P Y R A T E O F A S T A T I O N A R Y G A U S S I A N P R O C E S S Entropy rate and relative entropy rate are defined i n Sec. 2.1. For stationary Gaussian processes they can be calculated exactly, and be expressed i n terms of their SDF. Let us start w i t h the calculation of entropy rate. For convenience we put

Mf)

l ° g { 4 » V ( A ) }
=

for every f g S. B y the definition of S (see (2.2.14)), h(f)

(2.4.1) is finite.

T h e o r e m 2 . 4 . 1 . Let A" = { X ; n 6 Z } be a stationary Gaussian process and n

let X

n

= X ' + X%, ft € Z, be the Wold decomposition, where X ' = { X ' J is the n

S.i

ENTROPY

RATE

A GAUSSIAN

OF

PROCESS

purely nondeterministic part and X" = {X%} is the deterministic one. Then the entropy rate h(X)

of X is given by h(X)

= h(X') = H(f),

(2.4.2)

where / is the S D F of X'. P r o o f . A t first we prove (2.4.2) assuming that X is purely nondeterministic, so that X has the moving average representation (2.2.15). Then, i n particular, o Xi

= c i,

+

0

Y

ci-itj-

j«-oo Note that £, is independent of X j , j < 0, and that X3>
E

^ a ( X ) is

a function of X j , j < 0. Hence, the conditional probability distribution of Xj given X

0

= (Xg, X i , X , ••-) is a Gaussian distribution with mean S;
2

and variance £l|cofi| ] = c\. Therefore, using (2.1.7), (1.8.4), (2.2.26), we have 2

h(X)

= k(X \X^)

= h ^ )

x

T\ f_

=

= I log(2»e ) C o

log{4^e/(A)}dA =

h(f).

Next we prove (2.4.2) i n the general case. Decompose X as (2.2.12). Then, for = n H (X")

every fc, i t holds that H (X")

ne2:

k

n

= n z~H {X) n£

n

C

n < 7i„(X). n

D

Hence, i f XQ is given, then X' \ k £ Z, and consequently X' = X t — X' , k < 0, k

h

k

are known. Therefore, using (2.1.7), we have h(X)

= h(X \X ~) 1

= h(X[\X«)

a

= h(X[](X%)

We have already shown that h(X') is equal to h{f).

=

h(X').

•

I t may be interesting to note that the entropy rate does not depend on the deterministic p a r t , and especially that h(X) = 0 if X is deterministic. The entropy rate of a Gaussian A R M A process is calculated more simply. Let X be a Gaussian ARMA(Z, m ) process w i t h SDF /(A) of (2.3.8). Denote by a the roots of A(z)

and by p\, ...,0

m

the roots of B(z).

x

, a

t

As we have remarked in Sec.

2.3, we may assume that |crj| < 1, \Q \ < 1 and there are no common roots. Now k

/(A) can be w r i t t e n as m

=

a

nr-i«"-ftr.

M

78

STOCHASTIC

Theorem

PROCESSES

2.4.2. Let I b e i

AND

ENTROPY

Gaussian A R M A ( i , m ) process w i t h SDF /(A) of

(2.4.3). Then the entropy rate of X is given by (2.4.4)

h{X) = \\ g{2^bl). 0

P r o o f . I t follows from (2.4.2) and (2.4.3) that k(X)

log|e- - & | dX

= i log(27rei ) 2

A

a

I' log^-atfdX. ,=i«-*

-iT, ™

(2.4.5)

B y Poisson's integral formula we have j

l o g | e - « | d A = 0, a

(2.4.6)

,

if |a| < 1. The equation (2.4.4) is now clear from (2.4.5) and (2.4.6).

•

For each SDF / e S , the JV x JV m a t r i x f

To

7-{«-l)\

7-1

7-(N-2)

7i

?M/) = ( 7 - ) m

n

m i

„ i =

(2.4.7)

=

N

\7/V-l

To

IN-2

/

e' f(X)dX,

7 n = J"

BX

is called the Toeplitz m a t r i x corresponding to /. I n order to calculate the entropy rate and the relative entropy rate, we need to study the asymptotic behavior of Toeplitz matrices. Here we briefly summarize known facts concerning the asymptotic behavior of eigenvalues, inverses, and products of the Toeplitz matrices. For an

N

x N

matrix

UN

=

("mn), we define a norm

H M ^

£

\\Upi\\

K. | .

by

2

(2-4.8)

\\U \\\\V \\,

(2.4.9)

n

tn,u—1

Then SchwarVs inequality yields the inequality \Tr(U V )\ N

where

V

N

= (u

m n

N

<

N

) is also an JV x JV m a t r i x and

N

T T ( U

N

)

denotes the trace of

UN-

2 j ENTROPY

RATE

OF A GAUSSIAN

79

PROCESS

L e m m a 2.4.3. Let /, g € S be SDF's. Then we have Km^ilpglT^/)! = £

/ " lc.g{2 /(A)}dA

(2.4.10)

w

and ±Tr(T (f)T (g))

lim

N

= 2*

N

("

f(\)g(\)d\.

(2.4.11)

Moreover, if / € L [ - T , 7 r ] and /(A) > a, VA £ [—TT,TT), for some a > 0, then 2

i*r*pr3K/jr

Jirn^ where Tjv ( / ) -1

Proof.

- f i » ( i T l f = 0,

(2.4.12)

is the Toeplitz m a t r i x corresponding to 1//(A).

Let A" = {X„} be a stationary Gaussian process w i t h SDF /. Then T\(f)

is the covariance m a t r i x of (A*i,..., A*jv). Hence, by Theorem 1.8.1, the entropy rate h ( X ) is given by MAT) =

lim !*<*,,...,3V}

= I

lim ilog{(2 re)' |T (/)|}. v

7

w

Combining (2.4.2) and (2.4.13), we obtain (2.4.10). We put 7n = f

e


/(A)«/A

and /.„ = |

e'" (A)rfA. A

s

Then 7V(/)

= (7r»-i»)m,»-J,...,W I

?*(&*) = ( P m - n ) „ , „ = ]

and i t is easily seen that |V Tr(T (f)T (g)) N

=

N

Y,

7m- />nn

m

m n=l h

JV

fc=-JV + l

Consequently we have 1

lim -Tr(T (f)T (g}) fV—oo JV N

N

=

°°

T , —

k=~oo

%%,

N•

(2.4.13)

80

STOCHASTIC

PROCESSES

AND

ENTROPY

By the Parsevai equality T

ftfe-fl*

f(A)g(\)dX.

f

-«

*=-»

J

Hence we have obtained (2.4.11). The assertion (2.4.12) has been proved i n Gray [45], under the assumption H ^ L - o o l T n l < °°-

Even i f this condition is not satisfied, we can choose /„ €

5n£ [-7r,7r] i n such a way that £ ™

| J * . e * / „ ( A ) d\\ < oo, /.(A) > a, VA,

2

iB

and Hm ||/-/„|| = 2

where

lim

;

|ja denotes the norm of L [ — t t . t ] . N o w (2.4.12) is satisfied by /„: 2

£ H^fT^A))-

- T

1

(2.4.14)

(/-»)|| = 0. 3

N

Moreover we can show that, for any fixed E > 0, there exists n such that jt\\(T (f)r N

1

-(T (f )y

l

n

N

||TiV ( / " ' ) - T ( / w

113

(2.4.15)

U

(2.4.16)

:

for every JV. Finally (2.4.12) follows from (2.4.14) - (2.4.16). We denote by X ,„, N

•

n = 1,...,JV, the eigenvalues of T (f).

Then |T (/)| = W

N

n £ = i ^N,n and (2.4.10) can be rewritten as

i

N

i

J ™ , N £ '°

S A w

'

n

=

r

27 /

l

o

^ "^ 2

dX

-

Although we omit the proof, more generally, the following formula has been known. If 'p(i)

is a continuous function, then J ™ , Jr E

v(Af/,n) = 5 -

n=l

/

V f > / ( A » dA.

•' ' -

(2.4.17)

r

We now turn to calculate the relative entropy rate for stationary Gaussian processes. For convenience we put

for SDF's / and g. We see that 0 < H(f; x > 0.

g) < oo, since x - 1 - log x > 0 for all

S.i ENTROPY

RATE

T h e o r e m 2.4-4. Let X — {X ;n

OF A GAUSSIAN

e 2 } and Y = {Y \n

n

81

PROCESS

n

e Z ) be zero mean purely

nondeterministic stationary Gaussian processes w i t h SDF's / and <j, respectively. Then the relative entropy rate W{jtx\ P Y ) is given by F(«x;ny)=S (/;g),

(2.4.19)

r

provided that at least one of the following conditions is satisfied, (a)

/(A)/<j(A) is bounded.

(6)

g(X)

> a > 0 for a l l A S | - J T , T ] and / €

L [-W,TI]. 2

P r o o f . We shall prove (2.4.19) i n the case ( i ) . probability distributions of (A*j,..., A*jv) and

Denote by o ^

(Yi,V/v),

W)

and u

(

y

N )

the

respectively. Then, by

Theorem 1.8.2,

j^pjj + Tr {T (/) ( ( T ^ ) ) " |Tw(/)l

= log

1

N

- (T^/))" ) } 1

(2.4.20)

Using (2.4.10), we have (2.4.21) Obviously

i T r { r ( / ) ( r ( / ) r ' } = i. w

(2.4.22)

w

Applying (2.4.11), we have J » > { ^ W ) T

W

( r n } =

2 . £ ^ d A -

(2.4.23)

B y (2.4.9), TrlTvifHTNigjf^-^TriTMWNig-')} (TN(9))-

- T ^ T

1

<

N

(2.4.24)

( g - ' )

\\TN(/)\\

Note that lim v-o Af- ||3«(/)|| = 2TT / % / ( * ) < * * is finite. Then, using (2.4.12) J

0

1

a

(replacing / by g) and (2.4.24), we know that l i m T f { T ^ / K I M s ) ) - ' } - ^ T r {T {f)T N—oo N

( a " ) ] - 0. 1

N

(2.4.25)

STOCHASTIC

82

PROCESSES

AND

ENTROPY

It follows from (2.4.23) and (2.4.25) that

l i m l 7 V {T

} = £

( W

N(f)

£

g§

dA.

(2.4.26)

Finally, combining (2.4.20), (2.4.21), (2.4.22) and (2.4.26), we obtain (2.4.19). I n case (a), (2.4.19) has been proved i n Pinsker [96j.

•

Here we present a result on the relative entropy rate o f a non-Gaussian process w i t h respect to a Gaussian process. T h e o r e m 2.4.5. Let X = { X ; n n

e Z } and Y — {Y»;n e Z } be stationary

Gaussian processes w i t h SDF / and g, and Z = {Z„;n 6 Z ) be a stationary process w i t h the same SDF f as X. T h e n , under the same assumption of Theorem 2.4.4, the l i m i t =

K m ^ H U

z

N

- , p

)

)

m

Y

(2.4.27)

exists and = H ( P X \ P Y )

H(PZ\PY)

H(f-,g)

=

H(ii ;/ix)

+

z

+

H{p ;p $ z

x

>~3(f;g).

P r o o f . We may assume that H(n

z

(2.4.28)

] /Xy

) ' finite, so that the distribution p s

has a probability density function p/v(x) ( x £

Denote by

R ). N

p° {x) N

and

z

q%(x)

the density functions o f Gaussian distributions / J ^ ' and ( i ^ ' , respectively. Since and / i ^ '

have a common covariance matrix, and l o g f p ^ f x j / ^ j x ) )

quadratic function of x = ( j r j ,

H ^ P ; ^ ) = f

= =

P

i

w

w

( x ) l o

g

^ d x

P , ( x ) l o g ^ | d x

Bi$hp$h

By Theorem 2.1.1, the l i m i t

is a

£ R , we see that

+

+

B($hpP%

/

p ? v

(x)log4^dx (2.4.29)

S.S CONTINUOUS

TIME

STATIONARY

PROCESSES

83

exists, and we see that

-N^hJ „ n

=

PN{x)logp

^

jf

L

-

x)dx

P » ( X > 1 ° 6 p M X ) dx =

k(X).

Consequently we have H(

f

l

Z

l

l

i

x

)

= ^ m ^ H { ^ P ; ^ )

= h{X)-h{Z).

(2.4.30)

Since X and Y are Gaussian, by Theorem 2.4.4, the l i m i t N-o*

^

H

^

l

x

}

^ Y

N

>

) - * W ; M -

K/vff)

(2.4.31)

exists. Therefore we know that the l i m i t (2.4.27) exists and that the assertion (2.4.28) is obtained from (2.4.29) - (2.4.31).

•

2.5 C O N T I N U O U S T I M E S T A T I O N A R Y P R O C E S S E S This section is devoted to studying continuous time stationary processes. Spect r a l representation, canonical representation and multiple Markov property are to be discussed. Let

X

— {X{t);t

G R ) be a continuous time weakly stationary process. I n

Gaussian case we assume that X is a real stochastic process, otherwise we assume that A"(t) =

X(t,w)

(t

G R ) is a complex random variable defined on a probability

space (ft, B, P). Throughout the section we assume, without loss of generality, that the expectation E\X{t)\=

j

X(t,u>)dP(u)

is zero. We denote by (t)

1

= E\X{t

+ s)XlJ)),

1ER,

the covariance function of X. Similarly as i n the discrete time case we denote by H(X)

and Ht(X),

t £ R, the subspaces of L (9.,P)

X(s),

s
2

spanned by X(s),

s G R , and

S4

STOCHASTIC

PROCESSES

AND

ENTROPY

As for the spectral decomposition, we have analogous representations as i n the discrete time case. The spectral decomposition of the covariance function 7 ( t ) is given i n the form 7(0= where F(A) linu

/

e

i , A

dF(A),

teR,

(2.5.1)

is a non-decreasing right continuous function such that f ( — o o ) =

^F(X)

= 0 and F(oo)

= l i m i - a , F ( X ) = -y(Q).

I f the function F(\)

is

absolutely continuous, then (2.5.1) is rewritten in the form 7(0=

where f(X)

e f(X)d\,

f°° J

t

i,x

(2.5.2)

R,

G

—OO

is the density function defined by F(X)

— f_ f(x)dx.

The functions

x

F and / are called, respectively, the s p e c t r a l d i s t r i b u t i o n f u n c t i o n and the spectral density function (SDF)

of X . Note that, while the spectrum is dis-

tributed on the finite interval [ — ir, IT] i n the discrete time case, i t is distributed on the whole line R = ( — 0 0 , 0 0 ) in the continuous time case. The stationary process X itself has the spectral representation i n the form

x(0 = f

t <E R,

(2.5.3)

J —c

with a random measure {d(|(A); X G R ) satisfying (2.2.10).

The integral on the

right-hand side of (2.5.3) is a stochastic integral i n the same sense as i n (2.2.8). The process X is said to be purely nondeterministic i f n R ? f , ( X ) = ( 0 ) , and I 6

deterministic i f H,(X)

— Ht{X)

for all s, t € R. Similarly as i n the discrete time

case, X has the Wold decomposition. I t is known that X is purely nondeterministic if and only i f X has a SDF / satisfying

£

log/(A) dX 1 + A*

(2.5.4)

< CO.

The SDF / w i t h this property is known as a function of Hardy class. Among the SDF's, rational SDF's are important. A SDF / is called a rational SDF, i f i t is given i n the form

/(A)

where A(z)

=

B{i\)

2

A(iX)

= a [ j J L i t ? + « j ) and B(z) 0

n£.iiA+fti'

(2.5.5)

"0 = b I l j L t C * + &i) 0

M

e

polynomials w i t h

no common roots. We may assume that Say < 0 and Si/3, < 0 (ftz denotes the real

2.5 CONTINUOUS

part of z). Note t h a t , since /

TIME

STATIONARY

II

PROCESSES

/(A) dX - -y(0) < oo, the order M of the polynomial

R

A(z) should be less than the order j V of B{z).

Analogously as i n the discrete time

case, the stationary process X w i t h SDF f of (2.5.5) is said to be an autoregressive moving average process of order (JV, M ) , or simply an A R M A ( J V , M ) process. I n particular, if the SDF / is given i n the form

where

A{z)

=

a

0

\\f (z =1

a,) is a polynomial of order

+

N

such that Ret, < 0,

then the process X is said to be an autoregressive process of order N, or simply an AR(N) Let

X

process. =

{X(t);t

g R ) be a purely nondeterministic stationary Gaussian pro-

cess. I t is known that, using a Brownian motion

B

=

{B{t}\t

6 R),

X

can be

represented i n the form A-(t) =

/'

G(t-u)dB(t),

<eR,

(2.5.7)

J—o

w i t h equality H,{X)

= n,(B),

teR.

(2.5.8)

This representation w i t h causality property (2.5.8) is called the c a n o n i c a l r e p r e s e n t a t i o n i n the sense of Levy-Hida-Cramer. called the canonical kernel. Since crements,

{dB(t)\t

B

=

{B{t))

I n (2.5.7) G(i)

is a real function

is a process w i t h independent in-

£ R ) is a random measure and the integral on the right-hand

side of (2.5.7) is a stochastic integral which is known as the Wiener integral (see Sec. A.3). Intuitively speaking, (2.5.8) means that { S ( s ) ; s < t] contains the same information as { X ( s ) ; s < (}.

Hence

{dB(t))

can be regarded as the innovation

process of X. The canonical representation enable us to solve the problem of prediction. We are required to predict A"(t) (( > 0) based upon the observation of {A"(s);s < 0). The prediction error is evaluated by the mean square error. Similarly as i n the discrete time case, we denote by X(t)

the best predictor that minimizes the mean

square prediction error. T h e o r e m 2 . 5 . 1 . Let X be a purely nondeterministic stationary Gaussian process canonically represented as (2.5.7).

Given {A"(s);s < 0 } , the best predictor A"(t)

for X { t ) (t > 0) is given by X(t)=

f J-DO

G((-u)d5(u).

(2.5.9)

8fi

STOCHASTIC

PROCESSES

The corresponding prediction error e(t) (i)

=

2

E[\X(t)

-

ENTROPY

is given by

2

£

AND

= / ' |G(u)f

X{t)\ ] 2

(2.5.10)

du.

P r o o f . It is known that the best predictor is given by the conditional expectation: X{t)

= E[X(t)\X{ ),

s < 0).

S

(2.5.11)

G ( t - u) d B ( u )

From (2.5.7) and (2.5.8) we know that

£ H (B)

==

0

H (X) 0

and that /„' G ( t - u) d B ( u ) is independent of B { s ) , s < 0, and of X ( s ) , s < 0. Consequently ELY(t)| X ( ) , s < 0] = s

G(( - u ) d B ( u ) .

/

(2.5.12)

J —oo

The equation (2.5.9) follows from (2.5.11) and (2.5.12). Since

Xm

-

X U =

f Jo

G(t-u)dB(u),

using (A.3.3) we have

z(t?

f\G(t-u)\ du=

= E[\X(t}-X(t)\ )= 2

2

Jo

Thus the proof is complete.

/'|G(u)| du. 2

Jo

•

By the use of canonical representation (2.5.7) one can derive a formula for the mutual information

(f

I(X(t),Xg)

"past" A"^" = {A"(s);s < 0}.

>

0) between the " f u t u r e "

X(t)

and the

It is given i n terms of the m i n i m u m prediction

error. Unfortunately, no explicit formulas for the mutual information I{Xf, between X ,

+

= (A"(s);s > (} and X^

X ) 0

-

have been obtained, except the case where

X is the process w i t h rational SDF. T h e o r e m 2.5.2. Let X be the purely nondeterministic stationary Gaussian process w i t h canonical representation (2.5.7). Then

1

°^-i*$-f*jjfc

,>0

'

(2

-

513)

2.5 CONTINUOUS

TIME

STATIONARY

H7

PROCESSES

where 7 ( 1 ) is the covariance function of X. P r o o f . I f the conditional expectation

X(t)

= E[X(t)\X(s),

s

< 0] is given,

X{t)

is independent of X^. Hence, using (1.4) and (1.6), we can show that I(X(t),X;)

Since X(t) is given by

-

= I(X(t),(X{t),X^))

is independent of

X(t)

= I(X(t),X{t)).

(2.5.14)

the correlation coefficient

X(t),

p ( X ( t ) J { t ) f =

l

W

-

{

*

t

)

2

.

p{X(t),

X(())

(2.5.15)

The equation (2.5.13) follows from (2.5.14), (1.8.15), (2.5.15) and (2.5.10).

•

We now proceed to study multiple Markov property. Similarly as in the discrete time case we can define multiple Markov property, b o t h in the strict sense and in the wide sense. Let

X

=

{X(t);t

£

R ) be a Gaussian process, not necessarily

stationary. We say that X is differentiable i n L ( f l , P ) at ( i f there exists X ' ( t ) e 2

L (Sl,P) 2

such that

lim

fc—

0

E

±.{X(t

+

h ) - X ( t ) } - X ' ( t )

= 0.

A n d X ' ( t ) is called the derivative i n i ( S l , / * ) . 2

Definition 2.5.1.

1°) The Gaussian process

X = {X(t)}

is called an a t m o s t

JV-ple M a r k o v process i n t h e s t r i c t sense, if X is JV — 1 times differentiable in

L (Q,P) 2

at every i 6 R and i f P(X(s =

+ t)<x\X(u), P{X(s

u < i )

+t)<x\X(t),

X ' ( t ) , * < " - " ( ( ) ) ,

(2.5.16) holds for any x, t 6 R, where X^-' denotes the k-th derivative. I f X is at most JV-ple Markov b u t not at most (JV - l)-ple Markov, then X is called an JV-ple M a r k o v p r o c e s s i n t h e s t r i c t sense. 2°)

The Gaussian process

X

=

{X(t);t

€

R } is called an 7V-ple M a r k o v

process i n t h e w i d e sense, i f for any f < ij < ••• < t u < f/v+i the conditional a

STOCHASTIC

88

expectations E [ X ( t i ) \ X ( u ) , i n H(X)

butE[X(ti)\X(u),

PROCESSES

AND

ENTROPY

u < („}, t = l , . . . , i V , a r e l i n e a r l y i n d e p e n d e n t u < t ] , i = 1,...,JV + 1, a r e l i n e a r l y d e p e n d e n t . 0

Note that a Markov process is an at most 1-ple Markov process (see Def. 2.1.2). I n principle, Markov property should be a property concerning the dependency on the past of the process. However i t should be noted that, to define the Markov property i n the strict sense, we are required to assume the differentiability which seems to be unrelated to Markov property. The multiple Markov property of a stationary Gaussian process is characterized by its SDF. Although we omit the proof, we can prove the following theorem which corresponds to Theorem 2.3.3 for the discrete time processes. T h e o r e m 2.5.3. Let 1°)

X

£ R ) be a stationary Gaussian process.

— {X{t);t

The process X is an A^-ple Markov process in the strict sense i f and only

if X is an A R ( i V ) process. A n d X is an jV-ple Markov process i n the wide sense if and only if X is an A R M A ( j V , M) 2°)

process.

I f X is an JV-ple wide sense Markov process w i t h S D F / of (2.5.5), then the

canonical kernel G ( t ) i n the canonical representation (2.5.4) is determined from

Finally we give three examples. E x a m p l e 2 . 5 . 1 . Let X — ( X ( ( ) } be a stationary Gaussian process with canonical representation X(t)

e— —

= bf

(t

1

(2.5.17)

dB{xt)

J-co

(a > 0 and 6 ^ 0 are real numbers). Then the covariance function 7 ( 1 ) and the SDF /(A) are given by 7(0 =

m

-

^exp(-a|t|),

27r(A *+ a ) 2

J

2jr|iA-a| ' 2

Therefore we see that A" is a Markov process and is an Ornstein-Uhlenbeck Brownian motion (see Example 2.1.2). I t is known that, for almost all w € 11, the sample path

B(t)

— B(t,w)

of the Brownian motion is not differentiable i n the usual

S.S CONTINUOUS

sense.

TIME

STATIONARY

However there exists the derivative B(t)

PROCESSES

89

i n the Schwartz's distribution

sense. Formally speaking, (2.5.17) can be w r i t t e n as e"B(u)du.

X ( t ) = 6
+ aX(t)

=

bB{t).

This (formal) stochastic differential equation can be regarded as an autoregressive representation of the continuous time process X. It is interesting to compare this equation w i t h the A R representation (2.3.1) in the discrete time case. E x a m p l e 2.5.2. Let X be a process with canonical representation X(i)=

{e-"-

I

u |

-e

2 ( ,

- }d-B(u). u )

J-oo

Then X has the SDF /(A)

=

27r(A2 + l)(A2 + 4 ) '

Thus X is a double Markov process both i n the strict and wide sense. Similarly as in Example 2.5.1 i t is seen that X satisfies a. (formal) stochastic differential equation

JT"(0 + 3A"(0 +

2X(t) =

B(t).

E x a m p l e 2.5.3. Let X be a process with canonical representation X(t)=

{2e-"-

I

u )

-e

2 | [

- >}d£(u). u

J-co

Then X has the SDF f ( X ) n

>

_

A

'+

9

2x(A + l ) ( A 2

3

+ 4)'

and A" is a double Markov process i n the wide sense, but not i n the strict sense.

90

STOCHASTIC

PROCESSES

AND

ENTROPY

2.6 B A N D L I M I T E D P R O C E S S E S In practical systems of communication, the frequency of signals is often limited w i t h i n a finite interval. I n this section we study the processes w i t h frequency-band limited spectrum. One of the advantages of the band limited model is t h a t we can use a sampling expansion to generate the signal. Let X = {X(t);

t €

R } be a zero mean weakly stationary process w i t h covariance

function 7(f) and spectral distribution function F ( X ) . D e f i n i t i o n 2.6.1. The process X is said to be b a n d l i m i t e d to \X\ < KW', i f the spectral distribution F ( X ) satisfies the condition

For the band limited process X

=

the spectral decompositions (2.5.1)

{X(t)}

and ( 2 . 5 . 3 ) turn into 7

(t)

=

e dF(X),

t e a

e" d<(A),

teR-

/ /I-*W -.IV

itX

and x

(2.6.2)

Note t h a t , i f X has a S D F /, then (2.6.1) is equivalent to f(X)

= 0,

\X\ > TTW.

(2.6.3)

In this section we develop the sampling theorem which provides a link between continuous time processes and discrete time processes.

The sampling theorem

states that the process X = {A"(t)f, limited to the band —KW to TrW, is completely determined by giving the values X{n/W),

n

£

Z, of the process at a

series of points spaced 1/W seconds apart. We define the discrete time process X

=

{X neZ}by n]

X

n

=

x

( w ) '

n

€

Z

-

{

2

-

6

4

)

Then clearly X is stationary and its covariance function 7 „ , n £ Z, is given by 7Concerning the spectra of X and A", we shall show the following theorem.

(2-8-5)

2.6

T h e o r e m 2 . 6 . 1 . Let A" =

BAND

LIMITED

91

PROCESSES

be aweakly stationary process of band limited

{X(t)}

to |A| < i r i y . T h e n the spectral distribution function F ( \ ) of X is related to the spectral distribution function F ( A ) of X by F ( A ) = F(W\),

-n<\<w.

(2.6.6)

In particular, i f A" has a SDF /, then X also has a SDF / such that /(A) = Wf(W\),

< A < TT.

(2.6.7)

P r o o f . By (2.6.5) we have

jrW

/ =

•itW

/

e *dG(A), in

neZ,

J—it

where G(A) — F{W\).

Using the uniqueness of the spectral distribution function,

we obtain (2.6.6). Since /(A) = ward of (2.6.6).

j^F(X)

and /(A) = ^ F ( A ) , (2.6.7) is straightfor-

•

Since the spectrum of the process X vanishes outside the interval [—irW, JrlF], Theorem 2.6.1 means that F (resp. /) is completely determined by F (resp. /). Therefore i t is a natural consequence that all the values of { A ( t ) J are reconstructed from { A n } . The precise formula of the sampling expansion is given i n the following theorem which is known as the s a m p l i n g t h e o r e m . T h e o r e m 2.6.2. Let A = { A ( t ) ; t 6 R ) be the same band limited process as in Theorem 2.6.1, and assume that the spectral distribution function F ( X ) is continuous at A =

±ir\V.

Then, for each ( £ R,

X

¥i

=

fej^

*

X(t)

W

is represented i n the form

( t - n W - i )

X

n

'

(

2

' ' 6

8

)

where A = (AT„} is the process defined by (2.6.4) and the l i m i t is taken i n the sense of mean convergence. Proof.

For notational convenience, we put

y2

STOCHASTIC

PROCESSES

AND

ENTROPY

By ( 2 . 5 . 1 ) , i t is easily seen that

E n--N f

TT Wl

e

i

J-nW

,

x

- Y f A t y - ^

dF(X).

(2.6.10)

-N

For every fixed [, as a function o f A 6 [ — t W , v W \ i

the function e " * can he

expanded i n the Fourier series s

= lim Y

ia