Marco Mattiucci

INFORMATICA - PROBABILITA' DI KOLMOGOROV

Si consideri una sequenza di 3 bit, le sue combinazione (in numero di 2³) sono ovviamente:
s₀ = 000
s₁ = 001
s₂ = 010
s₃ = 011
s₄ = 100
s₅ = 101
s₆ = 110
s₇ = 111
se si ammette che siano tutte equi-probabili classicamente si avrebbe che la probabilità di ogni singola configurazione P(s₁)=P(s₂)=...=P(s₇) = 1/(2³).

Generalizzando ad n bit: P(s_i) = 1/(2ⁿ)
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 s_i è molto complessa, ossia se K(s_i) è 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(s₀)
K(s₁)
.
.
.
K(s_n-1)
poi si ottiene il contenuto informativo totale:
KT = sommatoria(K(s_i)) per i = 0,1,...,n-1
e quindi la probabilità (di Kolmogorov) delle combinazioni risulterebbe:

P(s_i) = K(s_i) / 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(s_i)) 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

marcomattiucci.it

• Home

Informatica:

• Home(Informatica)

Sistemi complessi:

• Home(Complessità)
• K-Complessità
• K-Casualità
• K-Compressione
• K-Probabilità
• Micro e Macro Stato
• Emersione
• "The halting problem"
• Irriducibilità
• Il Determinismo