• non sequential recursive pair substitution
• NSRPS
• sostituzioni di coppie
• Grassberger
• dinamica simbolica
• entropia di Kolmogorov-Sinai
• stima entropia

In questa tesi studiamo da un punto di vista computazionale un metodo di stima (Non Sequential Recursive Pair Substitution) dell'entropia di Kolmogorov-Sinai di sistemi dinamici ergodici e lo confrontiamo con altri metodi classici di stima. Il metodo in questione è stato proposto originariamente da Jimenez-Montaño, Ebeling e altri, ma è stato formalizzato nel linguaggio della teoria della probabilità e studiato più approfonditamente da Grassberger.

Per spiegare come funziona il metodo NSRPS, supponiamo di avere una sorgente M stazionaria e a stati finiti, ossia un dispositivo che emette stringhe di simboli estratti da un alfabeto finito, in modo tale che la probabilità di ricevere una data stringa finita non vari nel tempo. Data una successione estratta dalla sorgente, il metodo di Grassberger prescrive di individuare la coppia (o una delle coppie) di simboli di maggiore frequenza e di sostituirne tutte le occorrenze non sovrapposte, procedendo da sinistra verso destra, con un nuovo simbolo. Esemplificando, data la stringa s0 = 011010111011000111011010011, estratta da una sorgente stazionaria con alfabeto A = {0,1} per cui tra le probabilità delle coppie di simboli è massima quella della coppia '01', sostituiamo ogni occorrenza della sottostringa '01' con il nuovo simbolo '2', ottenendo s1 = 2122112100211212021.

Dopo la prima sostituzione abbiamo una nuova sorgente M1 con alfabeto A1 = {0,1,2}. Possiamo poi ripetere il procedimento introducendo nuovi simboli '3', '4', ..., (ottenendo nuove sorgenti M2, M3, ...

Il teorema principale riguardo al metodo NSRPS afferma che il procedimento delle sostituzioni di coppie di simboli trasforma, nel limite per il numero di sostituzioni che tende a infinito, qualunque sorgente ergodica in una sorgente 1-markoviana. Equivalentemente, si può dire che l'entropia di una sorgente ergodica M si può calcolare, nel limite per il numero n di sostituzioni che tende a infinito, conoscendo solo la distribuzione dei simboli e delle coppie di simboli dopo n sostituzioni.

In una sezione della tesi esponiamo nel dettaglio un esempio di processo stocastico a cui vengono applicate le sostituzioni di coppie, nel quale, pur non sostituendo ad ogni passo una coppia di frequenza massima, vale la conclusione del teorema principale, e anzi una condizione ancora più forte.

Abbiamo poi applicato il metodo NSRPS per ottenere una stima dell'entropia di trasformazioni ergodiche dell'intervallo [0,1]. Abbiamo a tal fine considerato quattro trasformazioni e confrontato su di esse il metodo NSRPS con altri tre metodi classici di stima: uno che applica direttamente la definizione di entropia; uno che mette in relazione l'entropia alla crescita esponenziale in n dei tempi di ritorno di blocchi simbolici lunghi n; il terzo è il calcolo dell'esponente di Lyapunov, il quale, sotto certe condizioni, è uguale all'entropia.

Dalle simulazioni al calcolatore, realizzate nel linguaggio di programmazione C con la libreria 'GMP - GNU Multiple Precision' per la gestione di numeri in virgola mobile con precisione arbitraria, traiamo conclusioni sull'efficienza del metodo NSRPS e sulla sua velocità di applicazione per la stima dell'entropia di Kolmogorov-Sinai, oltreché idee per direzioni di indagine future.