Lezione 10 Codifica e crittografia

1. TASSO DI ENTROPIA DI UN PROCESSO STOCASTICO

Il processo stocastico è una funzione di due variabili, una è la variabile dello

spazio campione e l'altra è una variabile temporale

Ω n

{ }

( ) ∈ ={ }

X ω , ω Ω , n∈ Z X

n n

Fissato (che può essere sia un numero intero reale o positivo) abbiamo

n

una funzione di e quindi una variabile aleatoria; mentre fissato ,

Ω Ω

quindi fissato un punto nello spazio campione abbiamo una funzione di n

deterministica che è la realizzazione del processo aleatorio.

Il processo aleatorio si dice stazionario

 {X }

n

[ ] [ ] n

∀ ∀(

=x =x =P =x =x )∈

P X , … , X X , … , X l∈ Z , x , … , x X

1 1 n n 1+l 1 n+l n 1 n

Dove e l’indice di è un indice temporale mentre l’indice di

X x

n+l n n

indica la posizione nel vettore .Tale espressione indica che la

(x )

, … , x

1 n

distribuzione di probabilità congiunta delle v.a. in un certo punto

X , … , X

1 n

e si ottiene lo stesso risultato considerando però le v.a.

x , … , x X , … , X +l

1 n 1+ l n

nello stesso punto .

x , … , x

1 n

Il processo aleatorio si dice processo di Markov o catena di Markov

{X }

n

[ ] [ ]

=x ∨X =x =x =x =P =x ∨X =x

P X , X , … , X X

+1

n+1 n n n n−1 n−1 1 1 n+1 n+1 n n

+1

n

∀ ( )∈

x , … , x , x X

1 n n+1

Il futuro dato il presente è indipendente dal passato

(n+1) (n)

,

.

(n−1, n−2 , … ,1)

Tale definizione generalizza la regola della catena per un processo di

Markov.

[ ]

=x =x =x

P X , X , … , X

n n n−1 n−1 1 1

Applichiamo la regola di Bayes

[ ] [ ]

=x ∨ =x =x =x =x

P X X , … , X P X , … , X

n n n−1 n−1 1 1 n−1 n−1 1 1

Sfruttando la proprietà di Markovianetà, l’unico condizionamento che conta è

=x

X n−1 n−1

[ ] [ ]

=x ∨ =x =x =x

P X X P X , … , X

n n n−1 n−1 n−1 n−1 1 1

[ ]

Ripeto gli stessi procedimenti per che corrisponde a:

=x =x

P X , … , X

n−1 n−1 1 1

[ ] [ ]

=x ∨X =x =x =x =x

P X , … , X P X , … , X

−2

n−1 n−1 n n−2 1 1 n−2 n−2 1 1

[ ] [ ] [ ] [

=x ∨ =x =x ∨X =x =x ∨X =x =x =x

P X X P X P X , … , X P X , … , X

n n n−1 n−1 n−1 n−1 n−2 n−2 n−2 n−2 n−3 n−3 1 1 n−3 n−3 1

Alla fine ottengo la regola della catena:

[ ] [ ] [ ] [ ] [

=x =x =P =x ∨ =x =x ∨X =x =x ∨ =x =x ∨

P X , … , X X X P X … P X X P X X

n n 1 1 n n n−1 n−1 n−1 n−1 n−2 n−2 3 3 n 2 2 2 2

La distribuzione di ordine n, con n qualsiasi, si può determinare dalla

distribuzione del 2° ordine.

[ ]

=x =x

P X , X

i i j j

[ ]

=x ∨X =x =

P X [ ]

i i j j =x

P X j j

∑

[ ] [ ]

=x = =x =x

P X P X , X

j j i i j j

∈

x X

i

Nel caso di v.a. congiuntamente gaussiane per scrivere la densità di

probabilità congiunta (pdf) di ordine n comunque elevato serve la matrice di

covarianza e il vettore della media delle n v.a. congiuntamente gaussiane; la

caratterizzazione congiunta di ordine n la esprimo dalla caratterizzazione

statistica del 2° ordine, tutto questo in generale non è vero. Nel caso dei

processi di Markov ho un risultato simile, serve anche la distribuzione di 2°

ordine per poter scrivere la distribuzione di ordine n.

La catena di Markov si dice stazionaria o tempo invariante se la

 {X }

n

distribuzione di probabilità condizionata non dipende dal tempo:

[ ] [ ] 2

∀

=a∨ =b =P =a∨X =b (a

P X X X , b)∈ X

n+1 n 2 1

Se è una catena di Markov allora è lo stato della catena

 {X } X

n n

all’istante n.

Una catena di Markov stazionaria è completamente caratterizzata

 statisticamente se è nota la distribuzione di probabilità dello stato iniziale (

) ed è nota la matrice delle probabilità di transizione dove

]

X P=[P

1 ij

(la matrice è indipendente da n)

| |

∈{1 }

ij , … , X

[ ] [ ]

| |

=P = =i =P =x =x

P X j X X X

ij n+1 n n+1 j n i

Se è noto la distribuzione di probabilità di ordine n

 [ ]

( )=P =x =x

p x X , … , X

X n n 1 1

Posso scrivere, usando la regola della catena, la probabilità di qualunque

evento ∑

[ ] ( )

∈ =

P X A p x

X

x∈ A

3.1.R M

APPRESENTAZIONE DI UNA CATENA DI ARKOV STAZIONARIA MEDIANTE

DIAGRAMMA DEGLI STATI

Una rappresentazione è la seguente: La P_12 rappresenta la probabilità di

passare dallo stato 1 allo stato 2.

Se qualche probabilità è 0 allora il ramo non si disegna.

è una catena di Markov irriducibile vuol dire che è possibile andare

 {X }

n

con probabilità non nulla da ogni stato della catena ad un altro stato della

catena in un numero finito di passi.

È un esempio di catena irriducibile; dallo stato 4 posso andare a finire allo

stato 1 con 3 passi.

Questa catena è non irriducibile, ci sono stati in cui non posso andare a finire

a partire da altri stati.

3.2.T EOREMA DELLA PROBABILITÀ TOTALE

La probabilità di probabilità all’istante si può determinare attraverso la

n+1

distribuzione di probabilità all’istante e la matrice di probabilità di

n

transizione. ∑

[ ] [ ] [ ]

=x = =x ∨X =x =x

P X P X P X

+1

n+1 n n+1 n+1 n n n n

∈

x X

i

È di interesse sapere se ci sono delle distribuzioni per cui la catena si trova

nella distribuzione stazionaria degli stati, cioè al passare del tempo la

distribuzione rimane sempre la stessa:

[ ] [ ] ∀ ∈

=x =P =x

P X X x X

n+1 n

Come primo passo modifichiamo la regola della catena nel seguente modo:

M

∑

[ ] [ ]

= = = =i =i]

P X j P X j∨X P[ X

+1

n+1 n n n

i=1

Le etichette degli stati sono stati indicati con interi da , mentre il

{1 }

, … , M

pedice indica il tempo.

n

Determinare la distribuzione stazionaria per una catena stazionaria.

]

[ [ ] [ ]

=1 =¿

P X ,… , P X=M