Lezione 7 Codifica e crittografia

X

qualcosa di diverso (Y) che varia nello spazio delle osservazioni

è chiamato meccanismo di transizione aleatorio, ci permette di

|

( )

P y x

∨X

Y

passare tra i 2 spazi. Osservo Y e la stima è una funzione deterministica

dell’osservazione : g è una funzione deterministica.

Y

^ =g (Y )

X ^

Possiamo dire quindi è una catena di Markov, cioè

( )

X →Y → X=g Y ^

deterministica. Questo implica che dato Y, questa quantità è

( )

=g

X Y

deterministica quindi è stat. Indipendente da ogni altra v.a, inclusa X.

Un esempio è il rumore additivo e la Il

|

( ) ( )

=P

P y x y−x ;

=N +

Y X ∨X

Y N

parametro che si adotta per valutare le prestazioni del decisore è “La

probabilità di errore”.

1.3.D F

ISUGUAGLIANZA DI ANO ^

[ ]

La disuguaglianza di Fano lega la e l’incertezza ( )

H X∨Y :

=P

P X ≠ X

e

(| | |

)

( ) ( )

+ −1

H P P log X ≥ H X Y

e e

Dimostrazione ^

v.a. indicatrice dell’evento errore . La parola indicatrice indica

E ]

P[ X ≠ X

che la v.a.

{ ^

1 sⅇ X ≠ X

E= ^ =

0 se X X

Scriviamo la regola della catena per l’entropia della coppia dato il

X,E

condizionamento in 2 espressioni equivalenti.

Y

|

( )=H ( )+ ( )

H X , E∨Y X Y H E∨X , Y

| |

( )=H ( ) ( )

∨Y +

H E , X E Y H X E , Y

Le 2 espressioni sono uguali.

1) Per il termine : è l’incertezza sull’evento errore E dati

(E∨X )

H ,Y ^

; questo implica che sono noti e , in quanto

( )

X , Y X =g

X Y

Xcappello è una funzione deterministica di X. Ma, di conseguenza, se

conosco X e Xcappello non c’è l’incertezza sull’evento errore, quindi si è

a conoscenza se l’errore c’è stato o meno; possiamo dunque dire che:

|

( )=0

H E X , Y

2) Per il termine che è l’incertezza sulla v.a. condizionata a

|

( ) E

H E Y

e sarà:

Y

|

( ) (

H E Y ≤ H E)

Perché il condizionamento riduce l’entropia. è l’entropia della

(E)

H

v.a. binaria con parametro

^

( )=P

=P [ ]

P E=1 X≠ X

e

( )

( )=H

H E P e

3) Per il termine si può scrivere come il condizionamento

|

( )

H X E , Y

rispetto agli Eventi E=0, E=1 :

| |

( ) ( )+ ( ) ( )

H X E=0 ,Y P E=0 H X E=1 , Y P E=1 ^

è l’incertezza su dato Y (quindi è noto ) e

|

( ) ( )

X

H X E=0 ,Y =g

X Y

dato il fatto che non c’è stato errore quindi possiamo dire che è

( )

E=0

noto anche , dunque:

X

|

( )

H X E=0 ,Y P( E=0)=0

4) Poi: ( )=P

P E=1 e

è l’incertezza su dato che c’è stato sicuramente errore

|

( ) X

H X E=1 , Y ^ ^

e dato , cioè è noto , ma è errato visto che c’è

( ) ( )

Y

E=1 =g

X Y X

l’errore; dunque, può variare tra possibili valori (cioè tutti i

| |

−1

X X

^

valori di escluso ). Allora possiamo dire che:

X X

| (| | )

( ) −1

H X E=1 , Y ≤ log X

Alla fine, possiamo dire che:

| (| | )

( ) −1

H X E , Y ≤ P log X

e

In definitiva otteniamo:

(| | |

)

( ) ( )

+ −1

H P P log X ≥ H X Y

e e

Questa relazione lega la probabilità di errore con l’incertezza su X

osservato . , quindi si può ancora scrivere che:

( )

H P ≤ 1

Y e

(| | (| | |

) )

( ) ( )

−1 + −1

1+ P log X ≥ H P P log X ≥ H X Y

e e e

E quindi si ottiene:

|

( )−1

H X Y

P ≥

e (| | )

−1

log X

Questo vale qualunque sia lo stimatore! Fissata dato la

X Y

disuguaglianza di Fano ci dice qual è la più piccola probabilità di errore che

si può sperare di ottenere fissata una qualsiasi regola di decisione, cioè per

qualsiasi funzione. Le prestazioni non possono essere migliori di queste.

Questo risultato è importante perché quando io nella pratica vado ad

individuare un decisore (uno stimatore), posso determinarlo in vari modi. Ma

questa regola mi dice qual è la prestazione massima che posso ottenere in

termini di probabilità di errore; quindi “migliorare” eccessivamente il mio

ricevitore, in determinati casi non ha senso, visto che ho un limite superiore.

Osservazione

Se nella disuguaglianza di Fano allora abbiamo che

=0

P e

| |

( ) ( )=0

⇒

0 ≥ H X Y H X Y

1.4.L EGGE DEBOLE DEI GRANDI NUMERI

{ }

Supponiamo di avere sequenza di v.a. indipendenti ed identicamente

Y i

distribuite (iid). Per l’indipendenza delle v.a. abbiamo che:

( ) ( ) ( )

=P

P y , … , y y … P y

Y , …, Y 1 n Y 1 Y n

1 n 1 n

Mentre per la condizione di identicamente distribuite, tutte le distribuzioni

coincidono, quindi la distribuzione congiunta anche di ordine elevato, si

fattorizza nel prodotto delle marginali:

( ) ( ) ( )

=P

P y , … , y y … P y

Y , …, Y 1 n Y 1 Y n

1 n

Le v.a. hanno tutte lo stesso valore medio .

{ }

E Y

La legge dei grandi numeri dice che:

n

1 ∑ { }

Y → E Y

i

n i=1

In probabilità. Quella sommatoria rappresenta proprio la media aritmetica;

Mentre la freccia vuol dire che “tende”: cioè una quantità aleatoria (membro

di sx) tende ad una quantità deterministica (termine di dx)Per la

n→∞

quantità aleatoria (sommatoria) diventa una quantità deterministica e { }

E Y