Lezione 5 Codifica e crittografia

XY X Y XY X Y

¿

D

sono statisticamente indipendenti, quindi la mutua informazione è nulla.

X e Y

Abbiamo dimostrato che:

( )

I X ; Y ≥0

Possiamo inoltre affermare che:

| | |

( ) ( ) ( )

p x , y z p x z p y z

∨Z ∨Z

XY∨Z X Y

Corollario 1

La funzione di mutua informazione condizionata è:

( )

∨Z

I X ;Y ≥ 0

L’uguaglianza si ha se e solo se e sono condizionalmente

( )=0

∨Z X Y

I X ; Y

indipendenti dato , cioè

Z .

| | |

( )= ( ) ( )

p x , y z p x z p y z

∨Z ∨Z

XY∨Z X Y

Quando e sono statisticamente indipendenti abbiamo che ;

=

p p p

X Y XY X Y

inoltre possiamo affermare che e sono condizionalmente indipendenti dato

X Y

e quindi abbiamo che ; invece non possiamo dedurre il

=p

p p

Z ∨Z

XY∨Z X∨ Z Y

contrario. Tra le due proprietà non c’è nessuna correlazione. CHIARIRE MEGLIO 3

Corollario 2 X

La distribuzione di probabilità uniforme su un insieme da luogo al valore

massimo dell’entropia (per una fissata cardinalità |X|; nomenclatura adottata solo

se X è una v.a discreta; cardinalità=numero di elementi di X) e cioè alla massima

incertezza sulla v.a.

| |

( )

H X ≤ log X

L’uguaglianza si ottiene se e soltanto se ha distribuzione uniforme. Indichiamo

X

con: 1 la distribuzione uniforme; distribuzione uniforme e sia

∀

( ) =

u x ( )

∈ p x

x X

| |

X

una generica distribuzione su .

X

∑

( ) ( )−¿ ( ) (x)

p x log p x p x logu

ϵ

x X ( )

p x

∑ ∑

| ) ( )

≙ = ¿

p∨ u p x log ( )

u x

ϵ ϵ

x X x X

0 ≤ D¿

La prima sommatoria corrisponde all’entropia della v.a. rispetto alla

X ¿ X∨¿

distribuzione a meno del segno; nella seconda sommatoria

( )

p x )=−log ¿

log u( x

∑ ( )=1

p x

che non dipende da x e quindi esce fuori alla sommatoria; mentre :

ϵ

x X

¿ X∨¿

( ) + ¿

0 ≤−H X log

| |

( )

H X ≤ log X

L’uguaglianza la ottengo quando le distribuzioni coincidono e quindi quando la v.a.

è uniforme, ottengo la condizione di massima incertezza. Cosa vuol dire

X

questo? Vuol dire che la situazione di massima confusione la ho quando i simboli

sono equiprobabili;

Corollario 3

Ricordando il diagramma di Venn, possiamo scrivere che:

( ) ( )

H X∨Y ≤ H X

È possibile affermare ciò perché

( ) ( )−I ( ) ( )

=H

H X∨Y X X ; Y ≤ H X

L’uguaglianza si ha se e soltanto se la funzione di mutua informazione è 0, cioè se

sono statisticamente indipendenti.

X e Y 4

Interpretazione

Il condizionamento della v.a. riduce l’entropia, cioè viene ridotta la misura

Y

dell’incertezza associata alla v.a. proprio dell’informazione che porta su

X Y

; quanta più informazione porta su tanto maggiore sarà la riduzione

X Y X

dell’entropia. Ovviamente se e sono statisticamente indipendenti

X Y

allora .

( )=0 ( ) ( )

=H

I X ; Y H X∨Y X

Invece se considero il condizionamento all’evento e non alla v.a. Y

( ) ( )

⋚

=

H X∨Y y H X

L’entropia della v.a. condizionata alla v.a. si ottiene andando a mediare

X Y

l’entropia condizionata all’evento rispetto alla distribuzione di probabilità

∑ |

( ) ( ) ( ) ( )

= =

H X∨Y H X Y y p y ≤ H X

Y

∈Y

y

1.17. B ’ ’

OUND DELL INDIPENDENZA PER L ENTROPIA

Dal diagramma di Venn possiamo affermare che:

( ) ( )+ ( )

H X ,Y ≤ H X H Y

L’uguaglianza è verificata se e soltanto se e sono statisticamente

X Y

indipendenti.

Estenderemo il risultato a n v.a. Consideriamo n-upla di v.a. con

X , … , X

1 n

[ ]

distribuzione congiunta , allora per definizione:

( )=P =x =x

P x X ,… , X

X 1 1 n n

n

∑ ∑

( ) ( )

( ) ( )

≙−

H X ,… , X p x log p x ≤ H X

1 n X X i

i=1

n

x∈ X

L’uguaglianza si ha se e soltanto se sono statisticamente indipendenti.

X , … , X

1 n

Dimostrazione

Utilizziamo la regola della catena per l’entropia:

| )

¿ X X , … , X

i i−1 1

¿

H n

∑

( ) ( )

=H + ¿

H X ,… , X X

1 n 1 i=2

Sfruttiamo il fatto che il condizionamento riduce l’entropia

(¿ )

H X i n

∑

( ) + ¿

≤ H X 1 i=2 5

X

¿

L’uguaglianza è verificata se e soltanto se: dove . Quando

i=2 , … , n i=2

¿

H

¿

significa che è indipendente da , è indipendente da e e

X X X X X

2 1 3 1 2

così via, fino a è indipendente da , tutte le variabili sono

X X , … , X

n n−1 1

statisticamente indipendenti tra loro e quindi:

[¿ =x ]

P X i i n

∏

[ ]

=x =x = ¿

P=P X , … , X

1 1 n n i=1

( )

q X

E p ( )

p X

x

1.18. C M

ATENA DI ARKOV

,Y,Z

Le v.a. formano una catena di Markov nell’ordine se dato

X X →Y → Z

è condizionalmente indipendente da , cioè:

Y , allora X Z

| |

( )=P ( )

P z x , y z y

Z∨ X ,Y Z∨Y y, quella a x no! Questo perché X è condizionalmente

Conta solo il condizionamento a

indipendente da Z.

Proprietà

1) Utilizzando la regola di Bayes si può scrivere:

|

( ) ( )

(

P z , y , x)=P z x , y P x , y

ZXY Z∨ XY XY

Applicando per il primo termine la catena di Markov e per il secondo

nuovamente la regola di Bayes si può scrivere:

|

( ) ( ) ( )

∨x

P z y P y P x

∨X

Z∨Y Y X

Quest’ultima espressione prende il nome di regola della catena. Posso

esprimere la distribuzione del terzo ordine mediante distribuzioni

condizionate e distribuzioni del primo ordine. Questa cosa è molto particolare

in quanto di solito se conosco la caratterizzazione di un processo del primo

ordine non conosco quella del secondo ordine (tranne se siamo nel caso iid o

gaussiano); quindi questo è un processo molto importante!

( )

P z , y , x

2) ZYX

|

( )=

P x , z y

XZ∨Y ( )

P y

Y

Usando la regola della catena possiamo scrivere: 6

( ) ( ) ( )

P z∨ y P y∨x P x

∨X

Z∨Y Y X

|

( )= ( ) ( )

=¿

P x , z y P z∨ y P x∨ y

∨Y

XZ∨Y Z∨Y X

( )

P y

Y

Z X

e sono condizionalmente indipendenti dato Y.

3) Se è la catena di Markov allora anche è una catena di

X →Y → Z Z →Y → X

Markov.

Z Y,

4) Se è una funzione deterministica di allora è una

( )

=f X →Y → Z

Z Y ,

catena di Markov. Infatti, dato , è deterministico (è una costante,

=f (Y )

Y Z

è una v.a. che assume con probabilità 1 sempre lo stesso valore), ed è

statisticamente indipendente da ogni v.a. Cioè se diamo una v.a di solito ha

una distribuzione di probabilità; ma noi consideriamo anche il caso limite che

una v.a assuma un unico valore con probabilità costante; di fatti è una costante

e quindi è indipendente da qualsiasi altra v.a

è una catena di Markov, cioè che è statisticamente

( )

(Y ) f Y dato Y

X →Y → f

indipendente da .

X

1.19. D ISUGUAGLIANZA DEL TRATTAMENTO DATI

Supponiamo di avere è una catena di Markov allora la mutua

X →Y → Z

informazione:

( ) ( )

I X ;Y ≥ I X ;Z

L’informazione che porta su è maggiore o uguale dell’informazione che

X Y

porta su .

X Z

Dimostrazione

Consideriamo la mutua informazione tra e la coppia , , applicando la

X Y Z

regola della catena per la mutua informazione tra e , condizionata a

X Y Y

(l’ordine tra Y e Z in questa relazione non è importante):

|

( )=I ( ) + (X )

I X ; Y , Z X ; Z Y I ; Y

Inverto i ruoli di Y e Z

|

( )=I ( ) + (X )

I X ; Z , Y X ; Y Z I ; Z

Le due espressioni sono uguali: ( )=I ( )

I X ; Y , Z X ; Z ,Y

Inoltre:

|

( )=0

I X ; Z Y

Perché se sono una catena di Markov allora condizionatamente a ,

X →Y → Z Y

e sono condizionalmente indipendenti. Mentre:

X Z

|

( )

I X ;Y Z ≥ 0 7

Perché è una mutua informazione. Quindi data l’uguaglianza ,

( )=I (X )

I X ; Y , Z ; Z∨Y

posso scrivere che:

| ) ( )

+ ( )

X ; Y Z I X ; Z ≥ I X ; Z

( )=I ¿

I X ; Y

L’uguaglianza è verificata se e sono condizionalmente

( )=I (

I X ; Y X ; Z) X Y | )=0

X ; Y Z

indipendenti dato , cioè se è catena di Markov:

Z X → Z → Y ¿

I

Corollario

| )

X ;Y Z

( ) ¿

I X ;Y ≥ I

Il condizionamento alla v.a. riduce l’informazione che porta su e

Z Y X

viceversa. [vale solo per le catene di Markov]. Cioè guardando Z mi può solo

“confondere le idee” da un punto di vista informativo. Questo potrebbe andare

contro a quanto detto prima: il condizionamento riduce l’entropia; in questo caso

invece è diverso ed è diverso perché ho una catena di Markov!

Si nota la differenza con il risultato che il condizionamento riduce l’incertezza

( ) ( )

H X∨Y ≤ H X

Corollario

se con deterministica, è una catena di Markov, quindi posso

( ) f

X →Y → Z=f Y

scrivere la disuguaglianza: sostituendo a 

( ) ( ) ( )

Z

I X ; Y ≥ I X ; Z f Y

( )

( ) ( )

I X ; Y ≥ I X ;f Y

Ipotizziamo per esempio che X è una v.a. Y è una misura, mentre f(Y) è

un’elaborazione di questa misura. Nessuna elaborazione deterministica di può

Y

aumentare l’informazione che porta su . In particolare, se rappresenta

Y X Y

una misurazione di nessuna elaborazione di aumenta l’informazione

X Y

portata su . Cioè Y già conteneva tutta l’informazione su X; io posso elaborare la

X

Y per re