INFORMATICA - PROBABILITA' DI KOLMOGOROV

Si consideri una sequenza di 3 bit, le sue combinazione (in numero di 23) sono ovviamente:
s0 = 000
s1 = 001
s2 = 010
s3 = 011
s4 = 100
s5 = 101
s6 = 110
s7 = 111
se si ammette che siano tutte equi-probabili classicamente si avrebbe che la probabilità di ogni singola configurazione P(s1)=P(s2)=...=P(s7) = 1/(23).

Generalizzando ad n bit: P(si) = 1/(2n)
per qualsiasi i = 1,2,...,n.

Purtroppo questo concetto classico di probabilità non descrive molto bene il fenomeno nelle sue manifestazioni (considerando ad esempio ogni bit come uscita di un lancio testa/croce di una moneta perfetta). Se ad esempio si considera il super-enalotto, chi di noi in cuor suo giocherebbe la sestina 1,2,3,4,5,6? Sono sicuro nessuno! Eppure classicamente ha una probabilità identica di uscita di una 12,34,44,56,78,86...

Siamo intuitivamente portati a pensare che, sebbene fisicamente equiprobabili, le manifestazioni 1,2,3,4,5,6 e 12,34,44,56,78,86 abbiano probabilità (pratiche) diverse. A ben vedere poi, anche la seconda 12,34,44,56,78,86 è piuttosto "improbabile" perchè i numeri sono tutti pari... e nello storico delle uscite non sono frequenti...

Questo concetto intuitivo e pratico di probabilità si può "ingabbiare" formalmente mediante la teoria della complessità algoritmica di Kolmogorov (vedere le altre pagina di questo sito sull'argomento). Il concetto di base è semplice, è lo stesso della casualità di Kolmogorov (vedere la pagina relativa): se una sequenza si è molto complessa, ossia se K(si) è maggiore, la sua probabilità deve essere maggiore (perchè più alta la sua aderenza al concetto di casualità).

La normalizzazione può avvenire in questo modo:
si calcola innanzitutto per ogni sequenza il suo reale contenuto informativo in bit (pari alla complessità di Kolmogorov):
K(s0)
K(s1)
.
.
.
K(sn-1)
poi si ottiene il contenuto informativo totale:
KT = sommatoria(K(si)) per i = 0,1,...,n-1
e quindi la probabilità (di Kolmogorov) delle combinazioni risulterebbe:

P(si) = K(si) / KT

Un esempio è il seguente che ho elaborato su 6 bit (n=6), potete vedere che le probabilità di Kolmogorov che ho stimato NON sono affatto uguali tra loro; siete interessati a capire come le ho calcolate? (in pratica come ho stimato le K(si)) contattatemi :-) :

si
000000
000001
000010
000011
000100
000101
000110
000111
001000
001001
001010
001011
001100
001101
001110
001111
010000
010001
010010
010011
010100
010101
010110
010111
011000
011001
011010
011011
011100
011101
011110
011111
100000
100001
100010
100011
100100
100101
100110
100111
101000
101001
101010
101011
101100
101101
101110
101111
110000
110001
110010
110011
110100
110101
110110
110111
111000
111001
111010
111011
111100
111101
111110
111111
P(si)
0,01056338
0,017605634
0,017605634
0,014084507
0,017605634
0,014084507
0,014084507
0,017605634
0,017605634
0,014084507
0,014084507
0,017605634
0,014084507
0,017605634
0,017605634
0,014084507
0,017605634
0,014084507
0,014084507
0,017605634
0,014084507
0,01056338
0,017605634
0,014084507
0,014084507
0,017605634
0,017605634
0,014084507
0,017605634
0,014084507
0,014084507
0,017605634
0,017605634
0,014084507
0,014084507
0,017605634
0,014084507
0,017605634
0,017605634
0,014084507
0,014084507
0,017605634
0,01056338
0,014084507
0,017605634
0,014084507
0,014084507
0,017605634
0,014084507
0,017605634
0,017605634
0,014084507
0,017605634
0,014084507
0,014084507
0,017605634
0,017605634
0,014084507
0,021126761
0,017605634
0,014084507
0,017605634
0,017605634
0,01056338