Università degli Studi di Pisa

Facoltà di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea in Matematica

Tesi di Laurea Specialistica 30 novembre 2007

Entropia di Kolmogorov-Sinai: dinamica simbolica e sostituzioni di Grassberger

Candidato Lucio M. Calcagnile

Relatori Dr. Stefano Galatolo Dr. Giulia Menconi Università di Pisa

Controrelatore Dr. Carlo Carminati

Università di Pisa

Anno Accademico 2006/2007

Indice

Ringraziamenti iii

Introduzione v

1 Teoria ergodica 1 1.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Spazi di misura e t.c.m. . . . . . . . . . . . . . . . . . . . . . 2 1.3 Esempi di t.c.m. . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Isomorfismo di t.c.m. . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Dinamica simbolica . . . . . . . . . . . . . . . . . . . . . . . . 5

1.5.1 Processi e spazi di successioni . . . . . . . . . . . . . . 5 1.5.2 Trasformazioni di shift . . . . . . . . . . . . . . . . . . 7 1.5.3 Dalle t.c.m. alla dinamica simbolica . . . . . . . . . . . 8

1.6 Ergodicità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Entropia 13 2.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Teoria ergodica . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Informazione e condizionamento . . . . . . . . . . . . . . . . . 17 2.4 Il teorema di Kolmogorov-Sinai . . . . . . . . . . . . . . . . . 20

3 Il metodo NSRPS 21 3.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 La trasformazione di stringhe e misure . . . . . . . . . . . . . 22

3.2.1 Stringhe . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.2 Misure . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.3 La trasformazione delle entropie per simbolo . . . . . . . . . . 25 3.4 Il teorema principale . . . . . . . . . . . . . . . . . . . . . . . 26 3.5 Un esempio interessante . . . . . . . . . . . . . . . . . . . . . 30 4 Metodi di stima dell’entropia 37

4.1 Frequenze empiriche . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Tempi di ritorno . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.3 Esponente di Lyapunov . . . . . . . . . . . . . . . . . . . . . . 41

5 Simulazioni al calcolatore 45 5.1 Trasformazioni dell’intervallo [0, 1] . . . . . . . . . . . . . . . . 45 5.2 Simulazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.3 Risultati delle simulazioni . . . . . . . . . . . . . . . . . . . . 50

5.3.1 Mappa logistica Λ . . . . . . . . . . . . . . . . . . . . . 51 5.3.2 Mappa espandente a pezzi E . . . . . . . . . . . . . . . 53 5.3.3 Mappa di tipo Lorenz L . . . . . . . . . . . . . . . . . 58 5.3.4 Mappa di Manneville M con esponente \frac{3}{2} . . . . . . . . 61

5.4 Tempi di esecuzione delle simulazioni . . . . . . . . . . . . . . 67

Conclusioni 69

A Risultati tecnici sul metodo NSRPS 73 A.1 Trasformazioni delle misure . . . . . . . . . . . . . . . . . . . 73 A.2 Trasformazioni delle entropie . . . . . . . . . . . . . . . . . . . 77

Bibliografia 83

Ringraziamenti

Ringrazio tutti coloro che in un modo o nell’altro mi hanno aiutato mentre lavoravo alla tesi e quando ho dovuto risolvere problemi con il L^{A}TEX.

Ringrazio la mia famiglia e i miei amici, in particolare Alessandra (φ), Giovanni, Margherita, Riccardo, per l’ospitalità a Pisa, l’aiuto per la programmazione in C e i problemi di stampa su file dei grafici, il supporto morale.

Infine, oltre che ai miei relatori Stefano e Giulia, sono grato ai professori Dario Bini del Dipartimento di Matematica dell’Università di Pisa ed Emanuele Caglioti del Dipartimento di Matematica dell’Università di Roma “La Sapienza” per la disponibilità e la cortesia con le quali mi hanno offerto il loro aiuto.

Introduzione

Questa tesi si propone di studiare da un punto di vista teorico e computazionale un metodo di stima dell’entropia di serie temporali simboliche ovvero di sistemi dinamici ergodici e di confrontarlo con altri metodi classici di stima.

Il metodo in questione è stato proposto originariamente da Jimenez-Montaño, Ebeling e altri [EJM], ma è stato formalizzato nel linguaggio della teoria della probabilità e studiato piú approfonditamente da Grassberger [Gr] prima (2002) e Benedetto, Caglioti, Gabrielli [BCG] poi (2006). In [Gr] l’autore propone alcune dimostrazioni di fatti teorici e i risultati di applicazioni del metodo alla stima dell’entropia della lingua inglese. In [BCG] gli autori dimostrano molte questioni lasciate in sospeso da Grassberger e ne lasciano aperte delle altre.

Nella tesi chiameremo il metodo con l’acronimo NSRPS (da Non-Sequential Recursive Pair Substitution) o metodo delle sostituzioni di Grassberger.

Per spiegare come funziona il metodo NSRPS, supponiamo di avere una sorgente stazionaria a stati finiti, ossia un dispositivo che emette stringhe di simboli x_{0}x_{1}x_{2} …, dove ogni x_{i} è un elemento di un alfabeto finito A = {a_{1}, a_{2}, …, a_{n}}, 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 sostituire tutte le occorrenze non sovrapposte, procedendo da sinistra verso destra, con un nuovo simbolo α ∉ A. Esemplificando, data la stringa

s^{0} = 011010111011000111011010011,

estratta da una sorgente stazionaria μ con alfabeto A = {0, 1} per cui μ(01) è massima tra le probabilità delle coppie di simboli, sostituiamo ogni occorrenza della sottostringa 01 con il nuovo simbolo 2, ottenendo

s^{1} = 2122112100211212021.

Nel caso in cui la coppia da sostituire sia costituita da due simboli uguali, non vengono sostituite tutte le occorrenze della coppia, ma solo quelle non sovrapposte, partendo da sinistra. Esemplificando, se la sostituzione da eseguire è xx → y, con y ∉ A, una sottostringa costituita da 2k simboli x consecutivi viene sostituita da k simboli y, mentre una sottostringa di 2k + 1 simboli x consecutivi viene sostituita dalla stringa formata da k simboli y e un simbolo x. Se A = {0, 1} e la sostituzione è 00 → 2, si ha ad esempio

00110100001010001000001100001 → 211012210120122011221.

Se si parte da una sorgente μ con alfabeto A = {0, 1}, dopo la prima sostituzione abbiamo una nuova sorgente con alfabeto A_{1} = {0, 1, 2} e una misura μ_{1} sulle stringhe finite ereditata da μ. Possiamo poi ripetere il procedimento introducendo nuovi simboli 3, 4, … (ottenendo nuove sorgenti μ_{2}, μ_{3}, …), fino a quando per qualche motivo non sia ragionevole concludere che ulteriori sostituzioni non siano utili.

Per esempio, se si ha a che fare con stringhe finite e la trasmissione di esse, si potrebbe ritenere di arrestare il processo delle sostituzioni quando le coppie di simboli piú frequenti non contano piú di una occorrenza, giacché in tal caso non vi sarebbe guadagno nel proseguire con un’altra sostituzione xy → z, dovendo poi trasmettere oltre alla stringa accorciata anche la regola di decodifica z → xy. Se le sostituzioni di coppie si attuano per motivi diversi (vedi capitolo 5) si dovrà determinare caso per caso quale ne sia il numero piú opportuno.

Il teorema principale riguardo al metodo NSRPS (teorema 3.4.1) afferma che l’entropia h di una sorgente ergodica μ, definita mediante le misure di tutte le stringhe finite \underline{x} ∈ ∪_{i∈ℕ}A^{i} da

h(μ) = lim_{k→∞} −\frac{1}{k} ∑_{\underline{x}∈A^{k}} μ(\underline{x}) log_{2} μ(\underline{x}),

si può calcolare, nel limite per il numero n di sostituzioni che tende a infinito, conoscendo solo le probabilità μ_{n}(a) e μ_{n}(ab), a, b ∈ A_{n}, dei singoli simboli e delle coppie di simboli. Equivalentemente, si può dire che il procedimento delle sostituzioni di coppie di simboli descritto poco sopra trasforma, nel limite per il numero di sostituzioni che tende a infinito, qualunque processo ergodico in un processo 1-markoviano (vedi sezione 3.4).

La condizione di sostituire ad ogni passo una delle coppie di simboli con probabilità massima è una condizione sufficiente ma non necessaria perché valga la tesi del teorema 3.4.1. Sarebbe interessante capire quali sono le condizioni che il processo e le sostituzioni debbono necessariamente soddisfare affinché valga la conclusione del teorema 3.4.1. Ciò potrebbe essere una direzione di indagine futura.

Dal punto di vista teorico abbiamo studiato approfonditamente proprio un esempio di processo in cui, pur non valendo l’ipotesi sufficiente del teorema 3.4.1, vale la conclusione del medesimo teorema, e anzi una condizione ancora piú forte. L’esempio è stato proposto da Benedetto, Caglioti, Gabrielli nell’articolo [BCG], dove gli autori elencano solo i risultati omettendo del tutto i calcoli espliciti. Esponiamo con dovizia di particolari i dettagli di tale processo nella sezione 3.5.

Per quanto riguarda il punto di vista computazionale, abbiamo applicato il metodo di Grassberger per ottenere una stima dell’entropia di trasformazioni ergodiche dell’intervallo [0, 1] con la σ-algebra dei boreliani. Abbiamo a tal fine considerato quattro tipi di trasformazioni: la mappa logistica (figura 1(a)), una mappa espandente a pezzi con due rami suriettivi e derivata uniformemente maggiore di uno (figura 1(b)), una mappa di tipo Lorenz con due rami non suriettivi e derivata uniformemente maggiore di uno (figura 1(c)), una mappa di Manneville con due rami suriettivi e derivata maggiore di uno fuori da 0 e uguale a uno nell’origine (figura 1(d)).

Per poter giudicare la precisione e la velocità dell’algoritmo di stima suggerito dal metodo NSRPS, abbiamo applicato alle stesse trasformazioni altri tre metodi di stima dell’entropia: uno è il metodo delle frequenze empiriche dei blocchi simbolici, un altro è il metodo dei tempi di ritorno, il terzo è il calcolo dell’esponente di Lyapunov.

È importante osservare che vi è una sostanziale differenza fra il metodo di stima dell’entropia basato sul calcolo dell’esponente di Lyapunov e gli altri tre. Il primo infatti presuppone la conoscenza esplicita della mappa, mentre gli altri si applicano a successioni simboliche, le quali in generale possono essere ottenute senza che sia nota la definizione della mappa ovvero rilevate empiricamente. Da tale osservazione segue che il confronto tra la stima dell’entropia come esponente di Lyapunov e mediante l’algoritmo delle sostituzioni di Grassberger ha significato solo negli ambiti di applicazione comuni ad entrambi. Riprenderemo tale questione nelle Conclusioni, dove discuteremo il confronto fra i vari metodi essendo in possesso dei risultati delle simulazioni al calcolatore.

Tutti i programmi per le simulazioni sono stati realizzati nel linguaggio di programmazione C, utilizzando la libreria GMP - GNU Multiple Precision per la gestione di numeri in virgola mobile con precisione arbitraria. Si veda a tal proposito il sito Internet http://gmplib.org/ dove si trova la documentazione completa.

Nel Capitolo 1 diamo una presentazione generale della teoria ergodica, introducendo gli endomorfismi di spazi di misura che la teoria ergodica considera, cioè le trasformazioni che conservano la misura (t.c.m.), il concetto di ergodicità, la dinamica simbolica con le trasformazioni di shift.

viii  INTRODUZIONE

(a) La mappa logistica, definita da Λ(x) = 4x(1 − x).

(b) Una mappa espandente a pezzi, definita da E(x) = \frac{4x}{3−2x} per 0 ≤ x ≤ 1/2 e E(x) = E(x − 1/2) per 1/2 < x ≤ 1. Per essa vale E′ > 0 uniformemente.

(c) Una mappa di tipo Lorenz, definita da L(x) = (\frac{6x−3}{4})^{3/4} per 1/2 ≤ x ≤ 1 e L(x) = 1 − L(1 − x) per 0 ≤ x < 1/2. La derivata è uniformemente maggiore di 1.

(d) La mappa di Manneville con esponente \frac{3}{2}. M(x) = x+x^{\frac{3}{2}} (mod 1). La derivata è uguale a 1 in 0 e maggiore di 1 altrove.

Figura 1: I quattro tipi di trasformazioni dell’intervallo [0, 1] su cui verranno applicati i vari metodi di stima dell’entropia.

Nel Capitolo 2 presentiamo il concetto di entropia di una trasformazione che conserva la misura e il teorema piú importante riguardo ad essa, il teorema di Kolmogorov-Sinai.

Nel Capitolo 3 illustriamo approfonditamente il metodo delle sostituzioni di Grassberger, discutendo e dimostrando il risultato fondamentale (teorema 3.4.1). Le dimostrazioni tecniche di lemmi e proposizioni sono rimandate all’appendice A per far sí che il lettore non perda di vista il filo conduttore. Quando nel corso del capitolo è stato fatto uso di equazioni ottenute nelle dimostrazioni tecniche e riportate in appendice, esse vengono preliminarmente richiamate. Nella sezione 3.5 esponiamo nel dettaglio un esempio di processo in cui vale la tesi del teorema centrale 3.4.1 pur non valendone l’ipotesi.

Nel Capitolo 4 diamo una presentazione dei fatti teorici alla base degli altri tre metodi di stima dell’entropia con i quali confrontiamo il metodo di Grassberger.

Nel Capitolo 5 presentiamo le trasformazioni dell’intervallo [0, 1] considerate, illustriamo le simulazioni realizzate al calcolatore e ne riportiamo i risultati anche in forma di grafici.

Nelle Conclusioni infine operiamo una sintesi dei risultati ottenuti ed evidenziamo pregi e difetti dei vari metodi di stima considerati, con particolare attenzione al confronto fra il metodo delle sostituzioni di coppie e gli altri. Concludiamo indicando le direzioni di indagine piú interessanti riguardo al metodo NSRPS.

Capitolo 1

Generalità sulla teoria ergodica

1.1 Introduzione

Un sistema dinamico è definito da uno spazio X e dall’azione di un gruppo G su X. Lo spazio X è detto spazio delle fasi e rappresenta l’insieme degli stati possibili del sistema. L’evoluzione del sistema è determinata da delle trasformazioni {T_{t} : X → X}_{t∈G} tali che

(i) Se e ∈ G è l’elemento neutro, allora T_{e} = id
(ii) Per ogni s, t ∈ G, ϕ_{st} = ϕ_{s} ∘ ϕ_{t}.

Lo spazio X ha una struttura (tipicamente X è uno spazio di misura o uno spazio topologico o una varietà differenziabile) e le trasformazioni T_{t} preservano tale struttura (le T_{t} sono rispettivamente trasformazioni che conservano la misura o omeomorfismi o diffeomorfismi).

Il gruppo G è generalmente ℝ (sistemi dinamici continui) o ℤ (sistemi dinamici discreti), ma spesso si definiscono sistemi dinamici dati dall’azione di un semigruppo, ad esempio ℕ.

Nel corso di questa tesi l’ambito sarà quello della teoria ergodica e l’oggetto che noi considereremo sarà uno spazio di probabilità (X, B, μ) con una trasformazione T che conserva la misura.

La teoria ergodica è lo studio matematico del comportamento a lungo termine di certe quantità medie di dati sistemi dinamici. Il problema dell’esistenza delle medie attirò l’attenzione dei matematici in seguito all’interesse dei fisici riguardo alla cosiddetta ipotesi ergodica. Essa fu formulata da Boltzmann nell’ambito della meccanica statistica nel tentativo di concludere che la media temporale di una quantità osservabile f,

lim_{N→∞} \frac{1}{N} ∑_{k=0}^{N−1} f(T^{k}x),

e la media sullo spazio delle fasi,

∫_{X} f dμ,

coincidessero quasi ovunque. È senz’altro desiderabile che il valore atteso di una variabile fisica coincida con la sua media pesata su tutti i possibili stati del sistema, tuttavia l’ipotesi ergodica come espressa sopra è in generale falsa. La proprietà che il sistema deve possedere affinché la media sullo spazio e le medie temporali di una funzione a valori reali siano uguali è quella che oggi viene chiamata ergodicità.

La parola ergodico fu introdotta da Boltzmann e deriva dalla fusione delle parole greche εργoν (lavoro) e oδoς (cammino).

1.2 Spazi di misura e trasformazioni che conservano la misura

Sia X = (X, B, μ) uno spazio di probabilità. Nel corso della tesi il nostro oggetto di indagine sarà sempre una trasformazione T : X → X misurabile che conserva la misura, cioè tale che

∀B ∈ B T^{−1}(B) ∈ B e μ(T^{−1}(B)) = μ(B).

Equivalentemente, la condizione che T conserva la misura μ è espressa dicendo che μ è T -invariante.

Osserviamo che, poiché la composizione di trasformazioni misurabili che conservano la misura è misurabile e conserva la misura, ha senso considerare le trasformazioni iterate T^{n} : X → X.

È difficile verificare in pratica se una data trasformazione conservi la misura oppure no usando la definizione appena data, poiché in genere non si conoscono esplicitamente tutti gli elementi di B. Tuttavia è sufficiente, come in molti casi accade, avere esplicita conoscenza di una semi-algebra che genera B. Una semi-algebra è una collezione S di sottoinsiemi di X per la quale valgono:

(i) ∅ ∈ S;

(ii) se A, B ∈ S allora A ∩ B ∈ S;

(iii) se A ∈ S allora X \ A = ∪_{i=1}^{n}E_{i} con E_{i} ∈ S per ogni i e gli E_{i} a due a due disgiunti.

Ad esempio, nel caso in cui lo spazio è l’intervallo unitario [0, 1], la collezione dei sottointervalli è una semi-algebra. Vale infatti il seguente teorema (vedi Walters [Wa1], p. 20).

Teorema 1.2.1. Siano X_{1} = (X_{1}, B_{1}, μ_{1}) e X_{2} = (X_{2}, B_{2}, μ_{2}) due spazi di probabilità e T : X_{1} → X_{2} una trasformazione. Sia S_{2} una semi-algebra che genera B_{2}. Se per ogni A_{2} ∈ S_{2} si ha T^{−1}(A_{2}) ∈ B_{1} e μ_{1}(T^{−1}(A_{2})) = μ_{2}(A_{2}), allora T conserva la misura.

Con un abuso di notazione, nel seguito useremo la scrittura T : X → X (e analoghe) al posto della piú corretta T : X → X.

1.3 Esempi di trasformazioni che conservano la misura

1. La trasformazione identica su uno spazio (X, B, μ) conserva ovviamente la misura.

2. Siano S^{1} = {z ∈ ℂ : |z| = 1}, B la σ-algebra dei sottoinsiemi boreliani di S^{1} e μ la misura di Haar. Sia inoltre a ∈ S^{1} e si definisca T : S^{1} → S^{1} come T (z) = az. Poiché μ è la misura di Haar, T conserva la misura. La trasformazione T è detta una rotazione di S^{1}.

3. La trasformazione T (x) = ax definita su un qualunque gruppo compatto G (dove a è un dato elemento di G) conserva la misura di Haar. Tali trasformazioni sono dette rotazioni di G.

4. Ogni automorfismo continuo di un gruppo compatto conserva la misura.

Dimostrazione. Sia A : G → G un automorfismo continuo e si denoti con m la misura di Haar su G. Si definisca una misura di probabilità μ sui sottoinsiemi boreliani di G tramite μ(E) = m(A^{−1}(E)). La misura μ è regolare poiché m è regolare. Inoltre, μ(Ax·E) = m(A^{−1}(Ax·E)) = m(x·A^{−1}E) = μ(E) e quindi la misura μ è invariante per rotazioni. Da ciò segue che μ = m, per l’unicità della misura di Haar. Ciò dimostra che A conserva la misura.

5. Per n ∈ ℤ \ {0} le trasformazioni T (z) = z^{n} conservano la misura di Haar di S^{1}.

1.4 Isomorfismo di trasformazioni che conservano la misura

Nello studio delle trasformazioni che conservano la misura si rivela molto utile introdurre una nozione di isomorfismo tra di esse. Grazie a tale nozione è in molti casi possibile ricondurre lo studio di una trasformazione che conserva la misura di un dato spazio a una trasformazione di shift su spazi di successioni simboliche (vedi sezione 1.5).

Due trasformazioni isomorfe avranno o non avranno entrambe certe proprietà (ad esempio l’ergodicità, vedi sezione 1.6) e per esse si troveranno delle quantità invarianti (ad esempio l’entropia, vedi capitolo 2).

Definizione 1.4.1. Siano (X_{1}, B_{1}, μ_{1}) e (X_{2}, B_{2}, μ_{2}) due spazi di probabilità con rispettive trasformazioni che conservano la misura

T_{1} : X_{1} → X_{1}, T_{2} : X_{2} → X_{2}.

Si dice che T_{1} e T_{2} sono isomorfe (o, piú precisamente, che i sistemi dinamici (X_{1}, B_{1}, μ_{1}, T_{1}) e (X_{2}, B_{2}, μ_{2}, T_{2}) sono isomorfi), e si scrive T_{1} ∼ T_{2}, se esistono due insiemi M_{1} ∈ B_{1}, M_{2} ∈ B_{2} con μ_{1}(M_{1}) = 1, μ_{2}(M_{2}) = 1 tali che

(i) T_{1}M_{1} ⊆ M_{1}, T_{2}M_{2} ⊆ M_{2},

(ii) esiste una trasformazione invertibile che conserva la misura

ϕ : M_{1} → M_{2} con ϕT_{1}(x) = T_{2}ϕ(x) ∀x ∈ M_{1},

tale cioè che sia commutativo il diagramma seguente.

(M_{1}, μ_{1}) ⟶^{T_{1}} (M_{1}, μ_{1})
ϕ↓  ^{ϕ}↓
(M_{2}, μ_{2}) ⟶^{T_{2}} (M_{2}, μ_{2})

(Nella condizione (ii) l’insieme M_{i}, i = 1, 2, si intende dotato della σ-algebra M_{i} ∩ B_{i} = {M_{i} ∩ B | B ∈ B_{i}} e della restrizione della misura μ_{i} a tale σ-algebra.)

Si dice che T_{2} è un fattore di T_{1} se esistono M_{1} e M_{2} come sopra tali che vale (i) e

(ii’) esiste una trasformazione non necessariamente invertibile che conserva la misura

ϕ : M_{1} → M_{2} con ϕT_{1}(x) = T_{2}ϕ(x) ∀x ∈ M_{1}.

In tal caso, T_{1} è detta un’estensione di T_{2}.

Osserviamo che l’isomorfismo di trasformazioni che conservano la misura è una relazione di equivalenza. Inoltre, se T_{1} ∼ T_{2}, allora T_{1}^{n} ∼ T_{2}^{n} per ogni n > 0.

Esempio. Sia T la trasformazione T z = z^{2} sulla circonferenza unitaria S^{1} con la σ-algebra di Borel e la misura di Haar, e sia U definita da Ux = 2x (mod 1) su [0, 1) con la σ-algebra di Borel e la misura di Lebesgue. Consideriamo l’applicazione ϕ : [0, 1) → S^{1} definita da ϕ(x) = e^{2πix}. La mappa ϕ è biiettiva e conserva la misura (è sufficiente verificarlo per gli intervalli e usare il teorema 1.2.1). Inoltre vale ϕU = T ϕ e perciò U ∼ T.

1.5 Dinamica simbolica

Nel descrivere il comportamento di un sistema dinamico si rivela molto utile avere opportuni modelli. Una buona fonte di modelli è fornita dagli spazi di successioni con le trasformazioni di shift. Presentiamo qui nel seguito tali spazi e trasformazioni di shift e come essi sono uno strumento importante per lo studio di un sistema dinamico.

1.5.1 Processi e spazi di successioni

Un processo stocastico a tempo discreto è una successione di variabili aleatorie X_{1}, X_{2}, X_{3}, … definite su uno spazio di probabilità (X, Σ, μ). In molte occasioni è utile considerare successioni bi-infinite …, X_{−1}, X_{0}, X_{1}, …, e quanto diremo per i processi indicizzati su ℕ vale con le dirette generalizzazioni per i processi indicizzati su ℤ. Per maggiori dettagli si veda Shields [Sh].

Diciamo che il processo ha alfabeto A se ogni X_{i} è a valori in A. A noi interesseranno solo processi ad alfabeto finito, e nel seguito intenderemo col termine ‘processo’ un processo stocastico a tempo discreto (indicizzato su ℕ o su ℤ) e ad alfabeto finito.

La successione finita a_{m}, a_{m+1}, …, a_{n}, dove a_{i} ∈ A per m ≤ i ≤ n, sarà indicata con a_{m}^{n}. L’insieme di tutte le stringhe a_{m}^{n} sarà indicato con A_{m}^{n}, tranne nel caso m = 1 in cui si userà A^{n}.

La distribuzione congiunta di ordine k del processo {X_{k}} è la misura μ_{k} su A^{k} definita da

μ_{k}(a_{1}^{k}) = Prob(X_{1}^{k} = a_{1}^{k}), per ogni a_{1}^{k} ∈ A^{k}.

Chiameremo i valori μ_{k}(a_{1}^{k}), a_{1}^{k} ∈ A^{k}, anche valori k-marginali di μ.

Chiamiamo distribuzione del processo l’insieme delle distribuzioni congiunte {μ_{k} : k ≥ 1}. La distribuzione di un processo può essere anche definita specificando la distribuzione iniziale μ_{1} e per ogni k ≥ 2 le distribuzioni condizionate

μ(a_{k}|a_{1}^{k−1}) = Prob(X_{k} = a_{k}|X_{1}^{k−1} = a_{1}^{k−1}) = \frac{μ_{k}(a_{1}^{k})}{μ_{k−1}(a_{1}^{k−1})}.

La distribuzione di un processo è quindi una famiglia di distribuzioni di probabilità, una per ogni k. La successione non può però essere completamente arbitraria, poiché è implicito nella definizione di processo che valga la seguente condizione di consistenza per ogni k ≥ 1,

μ_{k}(a_{1}^{k}) = ∑_{a_{k+1}∈A} μ_{k+1}(a_{1}^{k+1}), per ogni a_{1}^{k} ∈ A^{k}.  (1.1)

Un processo è definito dalle sue distribuzioni congiunte e ciò significa in particolare che lo spazio su cui le funzioni misurabili X_{n} sono definite non è importante. Dato un processo, esiste un modo canonico di definire uno spazio di probabilità e delle variabili aleatorie su di esso che realizzano il processo dato. Tale costruzione è la cosiddetta rappresentazione di Kolmogorov ed è basata sugli spazi di successioni simboliche. La descriviamo brevemente qui di seguito, rimandando al testo di Shields [Sh] per una presentazione piú dettagliata e formale.

Sia A un insieme finito. Indichiamo con A^{ℕ} l’insieme delle successioni infinite

x = (x_{i}), x_{i} ∈ A, i ≥ 1.

Il cilindro determinato da a_{m}^{n}, con a_{i} ∈ A per m ≤ i ≤ n, che indichiamo con [a_{m}^{n}], è il sottoinsieme di A^{ℕ} definito da

[a_{m}^{n}] = {x ∈ A^{ℕ} : x_{i} = a_{i}, m ≤ i ≤ n}.

Indichiamo con Σ la σ-algebra generata dai cilindri. Gli elementi di Σ sono chiamati gli insiemi di Borel di A^{ℕ}. Per ogni n ≥ 1 la funzione coordinata X̂_{n} : A^{ℕ} → A è definita da X̂_{n}(x) = x_{n}. Il prossimo teorema stabilisce che ogni processo con alfabeto A può essere pensato come il processo delle funzioni coordinate {X̂_{n}} sullo spazio A^{ℕ} dotato della σ-algebra dei boreliani e di una misura di probabilità.

Teorema 1.5.1 (Teorema di rappresentazione di Kolmogorov). Se {μ_{k}} è una successione di misure per cui valgono le condizioni di consistenza (1.1), allora esiste un’unica misura di probabilità di Borel μ su A^{ℕ} tale che μ([a_{1}^{k}]) = μ_{k}(a_{1}^{k}), per ogni k e ogni a_{1}^{k}. In altre parole, se {X_{n}} è un processo ad alfabeto finito A, esiste un’unica misura di Borel μ su A^{ℕ} per la quale la successione delle funzioni coordinate {X̂_{n}} ha la stessa distribuzione di {X_{n}}.

Per la dimostrazione si veda Shields [Sh], pag. 2.

Un processo si dice stazionario se le distribuzioni congiunte non dipendono dalla scelta dell’origine dei tempi, cioè se

Prob(X_{i} = a_{i}, m ≤ i ≤ n) = Prob(X_{i+1} = a_{i}, m ≤ i ≤ n),  (1.2)

per ogni m, n e ogni a_{m}^{n}. L’idea intuitiva della stazionarietà è che il meccanismo che genera le variabili aleatorie non cambia nel tempo.

È spesso conveniente pensare che il processo vada avanti da molto tempo prima dell’osservazione, cosí che siano visibili solo gli effetti non transitori. Per tale interpretazione è piú funzionale lo spazio delle successioni bi-infinite A^{ℤ}. La definizione di cilindro si estende immediatamente a questo caso e vale per lo spazio A^{ℤ} un analogo del teorema 1.5.1. Cioè, se {μ_{k}} è una famiglia di misure per cui valgono le condizioni di consistenza (1.1) e di stazionarietà (1.2), allora esiste un’unica misura di Borel su A^{ℤ} tale che μ([a_{1}^{k}]) = μ_{k}(a_{1}^{k}), per ogni k ≥ 1 e ogni a_{1}^{k}. La proiezione di μ su A^{ℕ} è ovviamente la misura di Kolmogorov su A^{ℕ} per il processo definito da {μ_{k}}.

1.5.2 Trasformazioni di shift

Se le successioni simboliche costituiscono gli spazi di probabilità che in molti casi utilizzeremo, lo shift è la trasformazione che regola la dinamica di tali spazi.

Lo shift (verso sinistra) è l’applicazione σ : A^{ℕ} → A^{ℕ} definita da

(σx)_{n} = x_{n+1}, x ∈ A^{ℕ}, n ≥ 1.

In sostanza, lo shift trasla tutti gli elementi della successione di un posto a sinistra e la sua definizione si può riscrivere in forma simbolica come

x = (x_{1}, x_{2}, x_{3}, …) ⇒ σx = (x_{2}, x_{3}, x_{4}, …).

Si osservi che

σ^{−1}[a_{m}^{n}] = [b_{m+1}^{n+1}], b_{i+1} = a_{i}, m ≤ i ≤ n,

quindi l’applicazione tra insiemi σ^{−1} manda insiemi cilindrici in insiemi cilindrici. Da ciò segue che per ogni insieme boreliano B la sua controimmagine σ^{−1}B è anch’essa un insieme boreliano, e quindi lo shift σ è un’applicazione misurabile rispetto alla σ-algebra di Borel.

La condizione di stazionarietà del processo si traduce nelle uguaglianze μ([a_{m}^{n}]) = μ([b_{m+1}^{n+1}]) per ogni m, n e ogni a_{m}^{n}, cioè μ(B) = μ(σ^{−1}B) per ogni cilindro B. Segue da ciò che vale l’uguaglianza μ(B) = μ(σ^{−1}B) per ogni insieme boreliano B, cioè la trasformazione di shift σ conserva la misura μ o, equivalentemente, μ è σ-invariante.

Per processi stazionari esistono due rappresentazioni canoniche, una come misura di Kolmogorov su A^{ℕ}, l’altra come estensione σ-invariante allo spazio A^{ℤ}. La seconda rappresentazione è detta modello bi-infinito di Kolmogorov di un processo stazionario. Si osservi che lo shift σ nel modello bi-infinito è invertibile.

1.5.3 Dalle trasformazioni che conservano la misura alla dinamica simbolica

Esponiamo in questa sezione un metodo molto utile per ricondurre lo studio di un sistema dinamico su un generico spazio allo studio di uno spazio di successioni con la trasformazione di shift.

Sia T una trasformazione invertibile che conserva la misura su uno spazio di probabilità (X, B, μ) e sia α = {A_{1}, …, A_{k}} una partizione misurabile finita di X. Indichiamo con Ω lo spazio prodotto {1, 2, …, k}^{ℤ}, cosí che un punto di Ω è una successione bi-infinita ω = (ω_{n})_{−∞}^{∞} dove ω_{n} ∈ {1, 2, …, k} per ogni n. Su Ω è definita la trasformazione di shift σ come nella sezione 1.5.2.

Mostriamo ora che esistono una misura di probabilità σ-invariante ν sulla σ-algebra di Borel B(Ω) di Ω e un’applicazione che conserva la misura ϕ_{α} : (X, B, μ) → (Ω, B(Ω), ν) tale che ϕ_{α}T = σϕ_{α}. Per x ∈ X, si definisce

ϕ_{α}x = (ω_{n})_{−∞}^{∞} se T^{n}x ∈ A_{ω_{n}}.

La n-esima coordinata di ϕ_{α}x è cioè il numero dell’elemento di α cui appartiene T^{n}x.

Cosí risulta definita un’applicazione ϕ_{α} : X → Ω e vale ovviamente σ(ϕ_{α}x) = ϕ_{α}(T x), per ogni x ∈ X. Per vedere che ϕ è misurabile si osservi che per ogni insieme cilindrico [ω_{m}^{n}], m < n, vale

ϕ_{α}^{−1}([ω_{m}^{n}]) = ⋂_{j=m}^{n} T^{−j}A_{ω_{j}}.

Quindi, per ogni cilindro C vale ϕ_{α}^{−1}(C) ∈ B, e poiché i cilindri generano B(Ω) si ha ϕ_{α}^{−1}(B(Ω)) ⊆ B.

La mappa ϕ_{α} trasporta in modo naturale la misura μ su (Ω, B(Ω)):

ν(E) =^{def} μ(ϕ_{α}^{−1}E) per ogni insieme misurabile E ⊆ Ω.

Chiaramente ϕ_{α} : X → Ω conserva la misura e dall’uguaglianza σϕ_{α} = ϕ_{α}T discende che σ conserva ν.

Nel caso in cui la mappa T non sia invertibile, un’analoga costruzione si ha prendendo in considerazione lo spazio delle successioni simboliche Ω^{+} = {1, 2, …, k}^{ℕ}.

La costruzione ora esposta è molto importante e su di essa baseremo le simulazioni al calcolatore che tratteremo nel capitolo 5. Stabiliamo ora della terminologia.

Definizione 1.5.2. La successione ϕ_{α}(x) è detta l’(α, T)-nome di x. Un punto x ∈ X è detto α-tipico per T (o semplicemente tipico) se ogni blocco ω_{1}ω_{2} … ω_{n} appare nell’(α, T)-nome di x con frequenza μ(A_{ω_{1}} ∩T^{−1}A_{ω_{2}} ∩…∩ T^{−n+1}A_{ω_{n}}).

Osserviamo che, per il teorema ergodico di Birkhoff 1.6.3, quasi ogni punto di X è α-tipico per T.

L’applicazione ϕ_{α} : X → Ω non è in generale invertibile, per cui non fornisce sempre un isomorfismo tra X e Ω. In generale, (Ω, B(Ω), ν, σ) sarà solo un fattore di (X, B, μ, T) (vedi definizione 1.4.1). Tuttavia, se la partizione α è generatrice (vedi definizione 1.5.3 qui sotto), allora si ha un isomorfismo, come stabilito dalla proposizione 1.5.4, per la cui dimostrazione si veda Petersen [Pe], pag. 274.

Definizione 1.5.3. Sia T una trasformazione dello spazio di probabilità (X, B, μ) che conserva la misura μ. Una partizione finita α = {A_{1}, …, A_{n}} di X è detta generatrice se gli insiemi della forma

A_{i_{1}} ∩ T^{−1}A_{i_{2}} ∩ … ∩ T^{−(k−1)}A_{i_{k}}

generano la σ-algebra B.

Proposizione 1.5.4. La mappa ϕ_{α} è un isomorfismo se e soltanto se α è una partizione generatrice per T.

1.6 Ergodicità

Sia (X, B, μ) uno spazio di probabilità e sia T : X → X una trasformazione che conserva la misura. Se T^{−1}B = B per qualche B ∈ B (in questo caso B si dice completamente invariante), allora anche T^{−1}(X \ B) = X \ B, e potremmo studiare T considerando le due trasformazioni T |_{B} e T |_{X\B}. Se 0 < μ(B) < 1 ciò ci semplifica lo studio di T. Se invece μ(B) = 0 o μ(X\B) = 0, considerare le restrizioni di T a B e al suo complementare non porta a una semplificazione significativa. Da tali considerazioni emerge l’importanza di studiare quelle trasformazioni che non possono essere decomposte come sopra. Le trasformazioni indecomponibili sono dette ergodiche:

Definizione 1.6.1. Sia (X, B, μ) uno spazio di probabilità. Una trasformazione T su (X, B, μ) che conserva la misura si dice ergodica se i soli insiemi misurabili completamente invarianti hanno misura nulla o piena, cioè se

T^{−1}B = B, B ∈ B ⇒ μ(B) = 0 oppure μ(B) = 1.

Esistono molti altri modi equivalenti di definire la proprietà di ergodicità. Ne elenchiamo alcuni nel prossimo teorema, per la cui dimostrazione si veda ad esempio Walters [Wa1] o un qualunque testo di teoria ergodica.

Teorema 1.6.2. Se T : X → X è una trasformazione che conserva la misura dello spazio di probabilità (X, B, μ), allora le seguenti affermazioni sono equivalenti:

(i) T è ergodica.

(ii) Per ogni A ∈ B con μ(A) > 0 si ha μ(∪_{n=1}^{∞}T^{−n}A) = 1.

(iii) Per ogni A, B ∈ B con μ(A) > 0, μ(B) > 0 esiste n > 0 tale che μ(T^{−n}A ∩ B) > 0.

(iv) Se f ∈ L^{1}(X, B, μ) è T -invariante (cioè f ∘ T = f q. o.) allora f è costante quasi ovunque.

(v) Per ogni A, B ∈ B si ha lim_{n→∞} \frac{1}{n} ∑_{j=0}^{n−1} μ(T^{−j}A ∩ B) = μ(A)μ(B).

Uno dei piú importanti risultati in teoria ergodica fu dimostrato da G. D. Birkhoff nel 1931 [Bir]. Noi lo enunciamo nel caso degli spazi di probabilità, ma esso vale piú in generale nel caso di spazi di misura σ-finita.

Teorema 1.6.3 (Teorema ergodico, Birkhoff 1931). Siano (X, B, μ) uno spazio di probabilità e T : X → X una trasformazione misurabile su di esso che conserva la misura. Data f ∈ L^{1}(X, B, μ), esiste f^{∗} ∈ L^{1}(X, B, μ) tale che

f^{∗}(x) = lim_{n→∞} \frac{1}{n} ∑_{i=0}^{n−1} f(T^{i}(x)) q. o.

Inoltre f^{∗} è T -invariante (cioè f^{∗} ∘ T = f^{∗} q. o.) e ∫_{X} f^{∗}dμ = ∫_{X} fdμ.

Osserviamo che, se T è ergodica, dall’affermazione (iv) del teorema 1.6.2 e dal teorema ergodico di Birkhoff discende che f^{∗}(x) = ∫_{X} f^{∗}dμ q. o. Da tale osservazione segue il seguente corollario.

Corollario 1.6.4. Siano (X, B, μ) uno spazio di probabilità e T : X → X una trasformazione che conserva la misura. Sia inoltre E ∈ B. Se T è ergodica allora

\frac{1}{n} ∑_{i=0}^{n−1} χ_{E}(T^{i}(x)) → μ(E) q. o.

In altre parole, se T è ergodica allora l’orbita di quasi ogni punto di X entra nell’insieme E con frequenza asintotica uguale a μ(E).

Il teorema seguente asserisce che l’ergodicità è una proprietà invariante per isomorfismo (per la dimostrazione si veda per esempio Walters [Wa1]).

Teorema 1.6.5. Siano (X_{1}, B_{1}, μ_{1}) e (X_{2}, B_{2}, μ_{2}) due spazi probabilità con trasformazioni misurabili che conservano la misura T_{i} : X_{i} → X_{i}, (i = 1, 2). Se T_{1} è isomorfa a T_{2} e T_{2} è ergodica, allora anche T_{1} è ergodica.

Entropia

2.1 Introduzione

Il concetto di entropia fu introdotto per la prima volta nella termodinamica da Clausius nel 1854; Shannon lo trasportò in teoria dell’informazione nel 1948 e Kolmogorov in teoria ergodica nel 1958. In tutti i casi l’entropia è una misura della casualità o del disordine.

Quando Claude Shannon iniziò uno studio matematico della trasmissione dell’informazione, si basò sulle idee fondamentali che (1) la quantità di informazione trasmessa è misurata dalla quantità di incertezza rimossa e (2) l’incertezza di una trasmissione è proporzionale al valore atteso del logaritmo della probabilità del simbolo ricevuto.

Per essere piú specifici, si consideri una sorgente, ovvero un oggetto che emette stringhe di simboli … x_{0}x_{1}x_{2} …, dove gli a_{i} sono elementi di un alfabeto finito A = {a_{1}, a_{2}, …, a_{n}}. Si supponga di ricevere il simbolo a_{i} con probabilità p_{i}, per ogni i = 1, …, n. Se ogni simbolo viene trasmesso indipendentemente da ciò che è stato trasmesso in precedenza, si può prendere come quantità di informazione trasmessa mediamente per simbolo la quantità

H = − ∑_{i=1}^{n} p_{i} log_{2} p_{i}.  (2.1)

(Si usa 2 come base del logaritmo perché normalmente l’informazione è misurata in termini binari, contando il numero delle domande a risposta affermativa/negativa cui è necessario rispondere per comunicare l’informazione stessa.)

Si noti che se qualche p_{i_{0}} = 1 (e tutti gli altri p_{i} = 0), allora non c’è incertezza alcuna su ciò che farà la sorgente. In questo caso, usando la convenzione 0 log 0 = 0, si ha H = 0. H è massima invece quando tutti i p_{i} sono uguali a 1/n. Per vedere questo, si consideri la funzione f definita in [0, 1]

f(t) = \{ \begin{matrix}0 & se t = 0 \\ −t log_{2} t & se 0 < t ≤ 1. \end{matrix}  (2.2)

La funzione f è continua, non negativa e convessa. Dalla disuguaglianza di Jensen segue che comunque si scelgano positivi λ_{1}, λ_{2}, …, λ_{n} ∈ [0, 1],

f (\frac{1}{n} ∑_{i=1}^{n} λ_{i}) ≥ \frac{1}{n} ∑_{i=1}^{n} f(λ_{i}).  (2.3)

Quindi, per ogni vettore di probabilità (λ_{1}, λ_{2}, …, λ_{n}),

\frac{1}{n} ∑_{i=1}^{n} f(λ_{i}) ≤ f (\frac{1}{n} ∑_{i=1}^{n} λ_{i}) = f (\frac{1}{n}) = −\frac{1}{n} log_{2} \frac{1}{n} = \frac{1}{n} log_{2} n, (2.4)

per cui H(λ) ≤ log_{2} n. E chiaramente H(1/n, 1/n, …, 1/n) = log_{2} n. Questo caso in cui tutti i simboli sono equiprobabili è quello in cui è massima l’incertezza su quale sarà il simbolo emesso dalla sorgente e perciò quello in cui è massima la quantità di informazione comunicata.

H è la quantità media di informazione trasmessa con ogni simbolo, se si prende come misura di informazione di un evento E la quantità − log_{2} P (E). Il fatto che questa scelta sia ragionevole e utile è motivato dal fatto che l’unica misura di informazione della forma f(P (E)), dove f : ℝ → [0, ∞) è continua, additiva su eventi indipendenti (f(P (E_{1} ∩ E_{2})) = f(P (E_{1})P (E_{2})) = f(P (E_{1})) + f(P (E_{2})) ) è − log_{r} P (E) per qualche r > 0. Per un’altra giustificazione della definizione di H si veda Khintchine [Kh].

Per una sorgente generica, la probabilità di ricevere un dato simbolo può dipendere da ciò che è stato ricevuto precedentemente. Per esempio, se la sorgente emette testo di prosa in italiano, la probabilità di ricevere una ‘u’ salirà enormemente ogni qual volta venga emssa una ‘q’. Tali effetti di dipendenza possono essere tenuti in conto nel calcolo dell’informazione media per simbolo considerando blocchi di simboli.

Per ogni k = 1, 2, … sia C_{k} l’insieme di tutti i blocchi di lunghezza k formati da simboli dell’alfabeto A. Ogni blocco C ha una certa probabilità P (C) (eventualmente 0) di essere ricevuto. Pertanto, l’informazione media per simbolo in una trasmissione di lunghezza k è

H_{k} = −\frac{1}{k} ∑_{C∈C_{k}} P (C) log_{2} P (C).  (2.5)

Si definisce l’entropia della sorgente come

h = lim_{k→∞} −\frac{1}{k} ∑_{C∈C_{k}} P (C) log_{2} P (C).  (2.6)

Il limite esiste (vedi proposizione 2.3.3), ed esso rappresenta la quantità media di informazione che la sorgente comunica con ogni simbolo emesso. Equivalentemente, h misura il grado medio di incertezza che un lettore della sorgente ha circa il simbolo successivo che verrà emesso, qualunque cosa abbia ricevuto prima.

2.2 Teoria ergodica

La sorgente discussa nella sezione precedente non era altro che un processo stazionario a stati finiti.

Gli output della sorgente sono stringhe infinite … x_{0}x_{1}x_{2} … di simboli presi da un alfabeto A = {a_{1}, a_{2}, …, a_{n}}, ovvero elementi dello spazio di successioni A^{ℤ}. Assumendo che la sorgente sia stazionaria, tale cioè che la probabilità di ricevere una data stringa non cambi nel tempo, esiste allora una misura su A^{ℤ} conservata dalla trasformazione di shift σ : A^{ℤ} → A^{ℤ} (vedi sezione 1.5.1). Se μ è la misura prodotto generata dai pesi p_{i} sugli a_{i}, si è in presenza dello shift di Bernoulli; esso è il caso in cui i simboli sono trasmessi indipendentemente da ciò che è stato trasmesso in precedenza. Calcolando l’entropia della sorgente secondo la formula (2.6), si è trovata l’entropia di un sistema dinamico (A, B, μ, σ).

Ricordiamo che, dato un sistema dinamico (X, B, μ, T) che conserva la misura, si può associare ad esso un processo stazionario a stati finiti considerando una partizione misurabile finita α = {A_{1}, A_{2}, …, A_{n}} di X. Ogni punto x ∈ X determina una stringa simbolica infinita che al tempo j ha il simbolo A_{i} se T^{j}x ∈ A_{i} (vedi sezione 1.5.3).

Definizione 2.2.1. L’entropia della partizione α = {A_{1}, A_{2}, …, A_{n}} è la quantità

H(α) = − ∑_{i=1}^{n} μ(A_{i}) log_{2} μ(A_{i}).  (2.7)

La comparsa di un blocco di simboli A_{i_{1}}, A_{i_{2}}, …, A_{i_{k}} a partire dal posto di indice j corrisponde all’entrata del punto T^{j}x nell’insieme A_{i_{1}} ∩ T^{−1}A_{i_{2}} ∩ … ∩ T^{−k+1}A_{i_{k}}. Tale insieme è un elemento della partizione α_{0}^{k−1} = α ∨ T^{−1}α ∨ … ∨ T^{−k+1}α, che è il minimo comune raffinamento delle partizioni α, T^{−1}α, …, T^{−k+1}α.

Definizione 2.2.2. Se α = {A_{1}, …, A_{n}} e β = {B_{1}, …, B_{m}} sono due partizioni, allora

- T^{−1}α è la partizione {T^{−1}(A_{1}), …, T^{−1}(A_{n})},

- α ∨ β è la partizione {A_{i} ∩ B_{j} : i = 1, …, n; j = 1, …, m},

- β è un raffinamento di α (si scrive β ≥ α), se ogni B_{j} è, a meno di un insieme di misura nulla, un sottoinsieme di qualche A_{i}.

Alla luce di queste definizioni, la quantità H_{k} in (2.5) è

\frac{1}{k}H(α ∨ T^{−1}α ∨ … ∨ T^{−k+1}α),

e l’entropia della sorgente definita dalla (2.6) è

h(α, T) = h_{μ}(α, T) = lim_{k→∞} \frac{1}{k}H(α ∨ T^{−1}α ∨ … ∨ T^{−k+1}α).

Definizione 2.2.3. La quantità h(α, T) è detta entropia della trasformazione T rispetto alla partizione α.

Il limite nella definizione di h(α, T) esiste, come dimostreremo piú avanti nella proposizione 2.3.3.

Il numero h(α, T) è una misura dell’incertezza media per unità di tempo che si ha riguardo a quale sia l’elemento della partizione α in cui entrerà un dato punto x (mosso dalla trasformazione T), dato il suo passato. Ovviamente, se α è scelta in modo banale potrebbe non esserci molta incertezza su quali saranno gli elementi della partizione stessa in cui cadranno i T^{j}x, e dire quali siano effettivamente potrebbe non comunicare molta piú informazione di quanto non fosse possibile indovinare a priori. Pertanto, l’entropia della trasformazione T è definita come la massima incertezza su tutti i possibili processi a stati finiti associati a T:

h(T) = h_{μ}(T) = sup_{α} h(α, T).

Il numero h(T) è una misura della nostra incertezza media riguardo a dove T muove i punti di X. La grandezza di h(T) riflette il grado con cui la trasformazione T ‘mischia’ lo spazio.

Chiaramente, h(T) è un invariante nella classe di isomorfismo di T. Piú in generale, se S è un fattore di T allora h(S) ≤ h(T) (perché ogni partizione relativa al sistema dinamico S determina una partizione di uguale entropia relativa a T, ma non necessariamente viceversa).

Si può inoltre pensare ad una partizione α come la collezione dei possibili risultati di un esperimento (per esempio la lettura del risultato di un lancio di dado). Il numero H(α) è una misura dell’incertezza media che si ha circa il risultato dell’esperimento, ovvero, equivalentemente, della quantità di informazione che si guadagna realizzando l’esperimento. Il raffinamento comune (o join) α ∨ β rappresenta l’esperimento composto, formato dalla realizzazione simultanea degli esperimenti α e β. Pertanto,

\frac{1}{k}H(α ∨ T^{−1}α ∨ … ∨ T^{−k+1}α).

è la quantità media di informazione per ripetizione ottenuta realizzando k ripetizioni dell’esperimento α, h(α, T) è la media temporale del contenuto di informazione dell’esperimento α, e h(T) è la massima informazione per ripetizione che si può ottenere da un qualsivoglia esperimento, fintanto che si usi T per l’evoluzione del sistema.

È naturale chiedersi se sia possibile ideare un esperimento che estragga dal sistema tutta l’informazione che a priori si può avere, cioè tale che

h(α, T) = h(T).

È ragionevole credere che ciò possa accadere se le partizioni α ∨ T^{−1}α ∨ … ∨ T^{−k+1}α generano l’intera σ-algebra, giacché in tal caso i possibili risultati di un qualunque esperimento possono essere descritti in termini di stringhe finite nell’alfabeto dato da α con un grado di accuratezza qualunque.

Nel 1958 Kolmogorov (in [Ko]) definí l’entropia di T come h(α, T) nel caso in cui T abbia una partizione generatrice α e ∞ altrimenti; la definizione data in precedenza è dovuta a Sinai (vedi [Si], 1959) e l’equivalenza delle due definizioni è data da quello che solitamente si chiama teorema di Kolmogorov-Sinai (teorema 2.4.1). Esso è lo strumento principale per il calcolo dell’entropia negli esempi concreti.

Prima della dimostrazione del teorema di Kolmogorov-Sinai enunciamo alcune proprietà dell’entropia e dell’entropia condizionata e dimostriamo l’esistenza del limite

h(α, T) = lim_{k→∞} \frac{1}{k}H(α ∨ T^{−1}α ∨ … ∨ T^{−k+1}α).

2.3 Informazione e condizionamento

In questa sezione raccogliamo i risultati tecnici per la dimostrazione del teorema di Kolmogorov-Sinai (teorema 2.4.1). Per le dimostrazioni si veda ad esempio Petersen [Pe].

È utile considerare i concetti di informazione ed entropia condizionate, i quali tengono conto dell’informazione di cui si dovesse essere già in possesso.

Sia F ⊂ B una sotto-σ-algebra della famiglia dei sottoinsiemi misurabili di X. Si ricordi che per ϕ ∈ L^{1}(X) la speranza condizionata E(ϕ|F) di ϕ data F è una funzione F-misurabile su X che soddisfa

∫_{F} E(ϕ|F)dμ = ∫_{F} ϕdμ

per ogni F ∈ F. E(ϕ|F)(x) rappresenta il valore atteso di ϕ data la conoscenza di F, cioè sapendo a quali insiemi di F appartiene il punto x. La probabilità condizionata di un insieme A ∈ B data F è

μ(A|F) = E(χ_{A}|F).

Essa rappresenta la misura della probabilità dell’occorrenza di A, rivalutata una volta che si conosca l’informazione contenuta in F. Si definisce la funzione di informazione condizionata di una partizione α, data una σ-algebra F ⊂ B, come

I_{α|F}(x) = − ∑_{A∈α} log_{2} μ(α|F)χ_{A}(x).

L’entropia condizionata di α, data F, è definita da

H(α|F) = ∫_{X} I_{α|F}(x)dμ(x).

Proposizione 2.3.1. H(α|F) = 0 se e solo se α ⊆ F a meno di insiemi di misura nulla.

Ricordiamo che α ⊆ F significa che per ogni A ∈ α esiste F ∈ F tale che l’insieme (A \ F) ∪ (F \ A) ha misura nulla.

Lemma 2.3.2. Se α e β sono due partizioni misurabili numerabili, allora

(i) H(T^{−1}α) = H(α).

(ii) Se α ≤ β allora H(α) ≤ H(β).

(iii) H(α ∨ β) ≤ H(α) + H(β).

Proposizione 2.3.3. Per ogni partizione misurabile numerabile α di X esiste il limite (eventualmente uguale a +∞)

h(α, T) = lim_{n→∞} \frac{H(α ∨ T^{−1}α ∨ … ∨ T^{−n+1}α)}{n}.

Dimostrazione. Si supponga H(α) < ∞, poiché ovviamente in caso contrario si ha h(α, T) = ∞. Per ogni n = 1, 2, … sia H_{N} = H(α ∨ T^{−1}α ∨ … ∨ T^{−n+1}α). Dal lemma segue che la successione {H_{n}} è crescente. Essa è anche subadditiva:

H_{m+n}

= H(α ∨ T^{−1}α ∨ … ∨ T^{−m+1}α ∨ T^{−m}(α ∨ T^{−1}α ∨ … ∨ T^{−n+1}α))
≤ H(α ∨ T^{−1}α ∨ … ∨ T^{−m+1}α) + H(α ∨ T^{−1}α ∨ … ∨ T^{−n+1}α)
= H_{m} + H_{n}.

Chiaramente, H_{jn} ≤ jH_{n} e H_{j} ≤ jH_{1}, e quindi la successione {H_{j}/j}_{j≥1} è limitata. Pertanto,

L = lim inf \frac{H_{j}}{j} < ∞.

Dato ε > 0, si scelga j tale che H_{j}/j < L + ε. Per ogni n > j si scelga i(n) tale che

[i(n) − 1]j < n ≤ i(n)j.

Allora H_{n} ≤ H_{i(n)j}, e pertanto

\frac{H_{n}}{n} ≤ \frac{Hi(n)j}{n} ≤ \frac{H_{i(n)j}}{[i(n) − 1]j} ≤ \frac{i(n)H_{j}}{[i(n) − 1]j} < \frac{i(n)}{i(n) − 1}(L + ε).

Per n abbastanza grande si ha allora

L − ε < \frac{H_{n}}{n} < L + 2ε.

Proposizione 2.3.4. Se B_{1} ⊂ B_{∈} ⊂ … sono sotto-σ-algebre di B e α è una partizione misurabile finita, allora

lim_{n→∞} H(α|B_{n}) = H(α| ⋁_{n=1}^{∞} B_{n}).

Proposizione 2.3.5. Comunque si prendano due partizioni misurabili numerabili α e β, vale

h(β, T) = h(α, T) + H(β|B(α)).

(B(α) è la σ-algebra generata da α.)

Proposizione 2.3.6. Per ogni n ∈ ℕ vale

h( ⋁_{i=−n}^{n} T^{−i}α, T) = h(α, T).

2.4 Il teorema di Kolmogorov-Sinai

Il calcolo di h(T) dalla sua definizione come sup_{α} h(α, T) è raramente possibile. Ma se esistesse una partizione α per la quale h(α, T) = h(T), il calcolo di h(T) sarebbe molto piú semplice. Tale è il caso in cui α è una partizione che genera l’intera σ-algebra B.

Per ogni partizione α verranno usate le notazioni α_{m}^{n} = ⋁_{k=m}^{n} T^{−k}α; nei casi in cui m = −∞ o n = ∞, si intenderanno con tale notazione le σ-algebre generate dalle partizioni:

\begin{aligned}α_{1}^{∞} & = & ⋁_{k=1}^{∞} B(T^{−k}α), \\ α_{−∞}^{−1} & = & ⋁_{k=1}^{∞} B(T^{k}α), \\ α_{−∞}^{∞} & = & ⋁_{k=−∞}^{∞} B(T^{k}α). \end{aligned}

Una partizione finita α è generatrice per T se α_{−∞}^{∞} = B a meno di insiemi di misura nulla (vedi definizione 1.5.3).

Teorema 2.4.1 (Kolmogorov-Sinai). Se α è una partizione generatrice per T, allora

h(T) = h(α, T).

Dimostrazione. È sufficiente dimostrare che per ogni partizione finita β si ha h(β, T) ≤ h(α, T). Per le proposizioni 2.3.5 e 2.3.6 si ha, per ogni n = 1, 2, …,

h(β, T) ≤ h(α_{−n}^{n}, T) + H(β|B(α_{−n}^{n})) = h(α, T) + H(β|B(α_{−n}^{n})).

Ma poiché β ⊆ α_{−∞}^{∞} a meno di un insieme di misura nulla, per le proposizioni 2.3.1 e 2.3.4 si ha

0 = H(β|α_{−∞}^{∞}) = lim_{n→∞} H(β|B(α_{−n}^{n})).

La tesi segue mandando n all’infinito nella prima formula.

Nel 1970 Krieger dimostrò in [Kr] il seguente teorema riguardo all’esistenza di partizioni generatrici.

Teorema 2.4.2 (Krieger). Se un sistema dinamico (X, B, μ, T) è ergodico e di entropia finita, allora esiste una partizione generatrice finita per T.

Il metodo NSRPS

3.1 Introduzione

Verrà ora illustrato il metodo delle sostituzioni di coppie di simboli studiato da Grassberger in [Gr]. Chiameremo esso piú brevemente metodo NSRPS (da Non-Sequential Recursive Pair Substitution).

Si consideri una stringa finita s^{0} di simboli presi da un alfabeto finito A = {a_{0}, …, a_{m−1}}. Per ogni coppia di indici i, j sia n_{ij} il numero delle occorrenze non sovrapposte della stringa a_{i}a_{j} in s^{0} e sia i_{0}, j_{0} la coppia (o una delle coppie) per cui n_{ij} è massimo. Si definisce una nuova successione s^{1} ottenuta da s^{0} sostituendo ogni occorrenza della coppia a_{i_{0}}a_{j_{0}} con un nuovo simbolo a_{m}. La nuova stringa è piú corta della vecchia e il suo alfabeto contiene un simbolo in piú. Partendo da s^{1} è possibile definire un’altra stringa s^{2} seguendo la stessa procedura, e cosí via.

Esemplificando, si consideri dapprima la stringa

s^{0} = 011010111011000111011010011,

nella quale si sostituisce la coppia 01 con il nuovo simbolo 2. Si ottiene

s^{1} = 2122112100211212021.

Indicando con |s| la lunghezza di una stringa s, si ha

|s^{1}| = |s^{0}| − #{01 ⊆ s^{0}},

dove con #{01 ⊆ s^{0}} si è indicato il numero di occorrenze di 01 nella stringa s^{0}. Dividendo per |s^{0}|,

\frac{|s^{1}|}{|s^{0}|} = 1 − \frac{#\{01 ⊆ s^{0}\}}{|s^{0}|}.

Nel seguito si avrà a che fare sempre con successioni estratte da una sorgente ergodica μ. Prendendo allora il limite per |s^{0}| → ∞ si ottiene che, per quasi ogni successione s^{0},

\frac{1}{Z} = lim_{|s^{0}|→∞} \frac{|s^{1}|}{|s^{0}|} = 1 − μ(01).  (3.1)

Si noti che la trasformazione è invertibile, per cui l’informazione contenuta nelle due successioni è la stessa. Pertanto, se h(s) è l’entropia per simbolo di s,

h(s^{0}) = \frac{h(s^{1})}{Z}.

Si consideri ora un esempio in cui la coppia da sostituire è formata da due simboli uguali. Nella stringa

00110100001010001000001100001

si esegua la sostituzione di 00 col simbolo 2. Si ottiene

211012210120122011221.

La differenza principale col caso precedente è che ora non vengono sostituite col nuovo simbolo tutte le coppie di zeri consecutivi. Per esempio 1001 → 121, ma 10001 → 1201. Si deduce facilmente che in questo caso la (3.1) diventa

\frac{1}{Z} = 1 − μ(00) + μ(000) − μ(0000) + μ(00000) − ….  (3.2)

Questo esempio mostra che, tramite una sostituzione NSRPS, le probabilità delle stringhe possono comportarsi in maniera complicata. Tuttavia, le sostituzioni NSRPS trasformano una successione markoviana in una successione markoviana, come dimostrato da Grassberger in [Gr]. In generale, se la sorgente di partenza non è markoviana, il processo non diventa markoviano dopo un numero finito di trasformazioni. Tuttavia è ragionevole pensare che le successioni tendano a diventare markoviane man mano che il numero delle trasformazioni tende a infinito. Nelle prossime sezioni si procederà alla formalizzazione di quanto detto, all’enunciazione e dimostrazione dei risultati.

3.2 La trasformazione di stringhe e misure

3.2.1 Stringhe

Dato un alfabeto A, si denota con A^{∗} = ∪_{k=1}^{∞}A^{k} l’insieme delle parole finite nell’alfabeto A. Gli elementi di A^{∗} saranno indicati con lettere latine sottolineate \underline{w}, \underline{z}, etc. La medesima notazione verrà usata anche per parole infinite (elementi di A^{ℕ} e A^{ℤ}). Un elemento \underline{w} ha lunghezza |\underline{w}| e, se |\underline{w}| = k, esso sarà altresí indicato con w_{1}^{k} = w_{1} … w_{k} = (w_{1}, …, w_{k}).

Si considerino x, y ∈ A, α ∉ A e A′ = A∪{α}. Una sostituzione di coppia è una funzione G = G_{xy}^{α} : A^{∗} → A^{′∗} che sostituisce in ordine le occorrenze di xy con α. Piú precisamente, G\underline{w} è definito sostituendo in \underline{w} la prima occorrenza da sinistra di xy con α, e ripetendo tale procedura fino al termine della stringa. Si definisce anche la funzione S = S_{α}^{xy} : A^{′∗} → A^{∗}, che agisce sulle parole \underline{z} ∈ A^{′∗} sostituendo ogni occorrenza del simbolo α con la coppia xy.

Si noti che la funzione G è iniettiva e non suriettiva mentre S è suriettiva e non iniettiva. Si noti inoltre che S|_{G(A^{∗})} = G^{−1}, cioè

S(G(\underline{w})) = \underline{w} per ogni \underline{w} ∈ A^{∗}.  (3.3)

Ci si rende conto facilmente che l’insieme delle parole ammissibili G(A^{∗}) è un sottoinsieme di A^{′∗} che può essere descritto da vincoli su simboli consecutivi: nel caso xy → α, con x ≠ y, G(A^{∗}) consiste delle stringhe di A^{′∗} in cui non compare la coppia xy; nel caso xx → α, G(A^{∗}) consiste delle stringhe di A^{′∗} in cui non compaiono le coppie xx e xα. Un fatto importante è che dopo l’applicazione di piú sostituzioni, l’insieme delle parole ammissibili è ancora descrivibile mediante vincoli su simboli consecutivi. È il contenuto del prossimo teorema.

Teorema 3.2.1. Sia {V_{a,b}}_{a,b∈A} una matrice binaria (la matrice dei vincoli), e sia A_{V}^{∗} il sottoinsieme di A^{∗} i cui elementi \underline{w} verificano

∏_{i=1}^{|\underline{w}|−1} V_{w_{i},W_{i+1}} = 1

(A_{V}^{∗} è l’insieme delle stringhe ammissibili rispetto ai vincoli su simboli consecutivi dati da V). Esiste una matrice di vincoli V′ con indici in A′ tale che

G(A_{V}^{∗}) = A_{V′}^{′∗}.

La dimostrazione segue da un controllo diretto. Qui di seguito verrà solo scritta V′ in funzione di V.

Siano z, w ∈ A\{x, y}. I valori degli elementi di V′ sono dati dalle seguenti tabelle:

\begin{matrix}se x ≠ y & x & y & w & α \\ x & V_{x,x} & 0 & V_{x,w} & V_{x,x} \\ y & V_{y,x} & V_{y,y} & V_{y,w} & V_{y,x} \\ z & V_{z,x} & V_{z,y} & V_{z,w} & V_{z,x} \\ α & V_{y,x} & V_{y,y} & V_{y,w} & V_{y,x} \end{matrix}  \begin{matrix}se x = y & x & w & α \\ x & 0 & V_{x,w} & 0 \\ z & V_{z,x} & V_{z,w} & V_{z,x} \\ α & 1 & V_{x,w} & 1 \end{matrix}

Si osservi che tali espressioni valgono se V_{x,y} = 1 e V_{x,x} = 1, rispettivamente; il caso contrario non è interessante e dà G(A_{V}^{∗}) = A_{V}^{∗}.

3.2.2 Misure

Qui e nel seguito si indicherà con E(A) l’insieme delle misure ergodiche stazionarie su A^{ℤ}, le sole che verranno prese in considerazione. Se μ ∈ E(A) verrà usata la notazione μ(\underline{w}) per indicare il valore dei |\underline{w}|-marginali di μ sulla stringa \underline{w}. Ricordiamo che i k-marginali della misura μ di un processo stazionario costituito dalla successione di variabili aleatorie {X_{i}}_{i∈ℕ} sono (vedi sezione 1.5.1) le misure secondo μ degli insiemi cilindrici della forma

[a_{s}, a_{s+1}, …, a_{s+k−1}] = ⋂_{i=0}^{k−1}{X_{s+i} = a_{s+i}}.

Il teorema e le proposizioni in questa sezione provengono dall’articolo [BCG]. Ne riportiamo le relative dimostrazioni nell’appendice A.

Le mappe G_{xy}^{α} e S_{α}^{xy} inducono in modo naturale le mappe G = G_{xy}^{α} : E(A) → E(A′) e S = S_{α}^{xy} : E(A′) → E(A). Siano μ ∈ E(A) e \underline{w} ∈ A^{ℕ} una successione tipica rispetto a μ; siano inoltre ν ∈ E(A′) e \underline{z} ∈ A^{′ℕ} una successione tipica rispetto a ν. La successione G\underline{w} è tipica per una misura ergodica che verrà chiamata Gμ e S\underline{z} è tipica per una misura ergodica che verrà chiamata Sν.

Piú precisamente, indicando il numero di occorrenze di una sottoparola \underline{s} in \underline{r} con #\{\underline{s} ⊆ \underline{r}\} = ∑_{i=1}^{|\underline{r}|−|\underline{s}|+1} 𝟙(r_{i}^{i+|\underline{s}|−1} = \underline{s}), dove 𝟙 è la funzione caratteristica, vale il seguente teorema.

Teorema 3.2.2. Se \underline{s} ∈ A^{′∗}, allora il limite

Gμ(\underline{s}) = lim_{n→∞} \frac{#\{\underline{s} ⊆ G(w_{1}^{n})\}}{|G(w_{1}^{n})|}  (3.4)

esiste ed è costante μ quasi ovunque in \underline{w}; inoltre \{Gμ(\underline{s})\}_{\underline{s}∈A^{′∗}} sono i marginali di una misura ergodica su A^{′ℤ}. Analogamente, se \underline{r} ∈ A^{∗}, allora il limite

Sν(\underline{r}) = lim_{n→∞} \frac{#\{\underline{r} ⊆ S(z_{1}^{n})\}}{|S(z_{1}^{n})|}  (3.5)

esiste ed è costante ν quasi ovunque in \underline{z}; inoltre \{Sν(\underline{r})\}_{\underline{r}∈A^{∗}} sono i marginali di una misura ergodica su A^{ℤ}. Vale

S_{α}^{xy}G_{xy}^{α}μ = μ.  (3.6)

Sia Z_{xy}^{μ} l’inverso dell’accorciamento medio rispetto a μ di una stringa sotto l’azione di G_{xy}^{α} e sia W_{α}^{ν} l’allungamento medio rispetto a ν di una stringa sotto l’azione di S_{α}^{xy}. Per queste quantità vale la seguente proposizione.

Proposizione 3.2.3. Se x ≠ y allora

Z_{xy}^{μ} =^{def} lim_{n→∞} \frac{n}{|G(w_{1}^{n})|} = \frac{1}{1 − μ(xy)} (μ q. o. in \underline{w}).  (3.7)

Se invece x = y allora

Z_{xx}^{μ} =^{def} lim_{n→∞} \frac{n}{|G(w_{1}^{n})|} = \frac{1}{1 − ∑_{k=2}^{∞}(−1)^{k}μ(\underline{x}^{k})} (μ q. o. in \underline{w}),  (3.8)

dove \underline{w}^{k} è la stringa formata da k simboli x. Per W_{α}^{ν} vale

W_{α}^{ν} =^{def} lim_{n→∞} \frac{|S(z_{1}^{n})|}{n} = 1 + ν(α) (ν q. o. in \underline{z}).  (3.9)

Inoltre,

W_{α}^{G_{xy}^{α}μ} = Z_{xy}^{μ}.  (3.10)

Proposizione 3.2.4. Se \underline{r} ∈ A^{∗}, il valore di Sν(\underline{r}) dipende solo dai valori di ν(\underline{s}) con |\underline{s}| ≤ |\underline{r}|.

Si osservi che la precedente affermazione è falsa per Gμ, e, nel caso in cui x = y, Gμ(\underline{s}) può coinvolgere la probabilità di infinite stringhe di lunghezza crescente.

Proposizione 3.2.5. Se ν ∈ E(A′) rispetta i vincoli di coppia dati da G, cioè per \underline{z} ∈ A^{′∗}

ν(\underline{z}) = 0 se \underline{z} ∉ G(A^{∗}),

allora

ν = GSν.

3.3 La trasformazione delle entropie per simbolo

Dati μ ∈ E(A) e n ≥ 1, indicando con log il logaritmo in base 2,

H_{n}(μ) = − ∑_{|\underline{z}|=n} μ(\underline{z}) log μ(\underline{z})  è l’entropia di ordine n
h_{n}(μ) = H_{n+1}(μ) − H_{n}(μ)  è l’entropia condizionata di ordine n
h(μ) = lim_{n→∞} \frac{H_{n}(μ)}{n} = lim_{n→∞} h_{n}(μ) è l’entropia di μ.

Ricordiamo che la misura μ si dice k-markoviana se, indicando le probabilità condizionate con μ(\underline{z}|\underline{w}) = μ(\underline{w}\underline{z})/μ(\underline{w}), si ha che per ogni n > k, \underline{w} ∈ A^{n} e a ∈ A vale μ(a|w_{1}^{n}) = μ(a|w_{n−k+1}^{n}). In questo caso h(μ) = h_{j}(μ) per ogni j ≥ k. Osserviamo anche che h(μ) = h_{k}(μ) implica che μ è una misura k-markoviana.

Diamo qui di seguito alcuni enunciati (vedi [BCG]) su come le entropie di trasformano sotto l’azione di G. Le relative dimostrazioni si trovano nell’appendice A.

Per alleggerire un poco le notazioni, verranno usate le abbreviazioni Z = Z_{xy}^{μ} e talvolta Z^{μ} = Z_{xy}^{μ} quando sarà necessario specificare la misura.

Teorema 3.3.1.

h(Gμ) = Zh(μ).  (3.11)

Il contenuto del precedente teorema non è una sorpresa, giacché la quantità di informazione della stringa \underline{w} è la stessa della stringa G(\underline{w}).

Teorema 3.3.2.

h_{1}(Gμ) ≤ Zh_{1}(μ).  (3.12)

Inoltre, se μ è una misura 1-markoviana allora anche G(μ) è 1-markoviana.

Si noti come la seconda affermazione sia una conseguenza della prima: se μ è una misura 1-markoviana, allora

h(Gμ) ≤ h_{1}(Gμ) ≤ Zh_{1}(μ) = Zh(μ) = h(Gμ).  (3.13)

Pertanto h_{1}(Gμ) = h(Gμ) e ciò implica che Gμ è 1-markoviana.

Il prossimo teorema è una generalizzazione del teorema 3.3.2.

Teorema 3.3.3.

h_{k}(Gμ) ≤ Zh_{k}(μ),  (3.14)

e G manda misure k-markoviane in misure k-markoviane.

3.4 Il teorema principale

Il teorema 3.3.2 dice che l’informazione contenuta in G(\underline{w}), che è pari a quella di \underline{w} per il teorema 3.3.1, è maggiormente concentrata sulle coppie di simboli, rispetto alla stringa di partenza \underline{w}. Tale fatto suggerisce che una successione di sostituzioni di coppie possa trasferire tutta l’informazione nella distribuzione delle coppie di simboli. Per formalizzare questa asserzione definiamo ricorsivamente: gli alfabeti A_{N} = A_{N−1} ∪ {α_{N}} dove α_{N} ∉ A_{N−1}, con A_{0} = A;

le mappe G_{N} = G_{x_{N} y_{N}}^{α_{N}} : A_{N−1}^{∗} → A_{N}^{∗}, dove x_{N}, y_{N} ∈ A_{N−1};

le mappe corrispondenti G_{N} = G_{x_{N} y_{N}}^{α_{N}}, S_{N} = S_{α_{N}}^{x_{N} y_{N}}, S_{N} = S_{α_{N}}^{x_{N} y_{N}};

le misure μ_{N} = G_{N}μ_{N−1}, con μ_{0} = μ;

i fattori di normalizzazione Z_{N} = Z_{x_{N} y_{N}}^{μ_{N−1}};

le mappe composte

\begin{matrix}\overline{G}_{N} = G_{N} ∘ … ∘ G_{1}, & \overline{G}_{N} = G_{N} ∘ … ∘ G_{1}, \\ \overline{S}_{N} = S_{1} ∘ … ∘ S_{N}, & \overline{S}_{N} = S_{1} ∘ … ∘ S_{N}; \end{matrix}

le corrispondenti normalizzazioni \overline{Z}_{N} = Z_{N} … Z_{1} (si userà il simbolo \overline{Z}_{N}^{μ} quando sarà necessario specificare la misura iniziale).

Con le notazioni introdotte possiamo ora enunciare e dimostrare il teorema centrale (vedi Benedetto-Caglioti-Gabrielli [BCG]).

Teorema 3.4.1. Se

lim_{N→∞} \overline{Z}_{N} = +∞  (3.15)

allora

h(μ) = lim_{N→∞} \frac{h_{1}(μ_{N})}{\overline{Z}_{N}}.  (3.16)

Grassberger, in [Gr], sceglie ad ogni passo la coppia (o una delle coppie) di simboli con la massima frequenza di occorrenze non sovrapposte. Questo fatto assicura la divergenza di \overline{Z}_{N}, come si dimostrerà ora usando il teorema 3.3.2.

Teorema 3.4.2. Se ad ogni passo N la coppia x_{N}y_{N} è una coppia con la massima frequenza di occorrenze non sovrapposte tra tutte le coppie di simboli di A_{N−1}, allora

lim_{N→∞} \overline{Z}_{N} = +∞.  (3.17)

Dimostrazione. Sia p_{N} il massimo della probabilità μ_{N−1} sulle coppie di simboli di A_{N−1}. Dalla definizione di Z_{N} segue che

\overline{Z}_{N} ≥ \overline{Z}_{N−1} (1 + \frac{p_{N}}{2} ) ,

(il fattore 2 compare per il caso di sostituzione di due simboli uguali). Si può stimare p_{N} con

p_{N} ≥ 2^{−H_{2}(μ_{N−1})},

dove H_{2}(μ_{N−1}) = − ∑_{a,b∈A_{N−1}} μ_{N−1}(ab) log μ_{N−1}(ab) è l’entropia di ordine 2. Usando il teorema 3.3.2 e il fatto che H_{1}(μ_{N−1}) ≤ log(N − 1 + |A|), con |A| la cardinalità di A, si ha

H_{2}(μ_{N−1}) = h_{1}(μ_{N−1}) + H_{1}(μ_{N−1}) ≤ \overline{Z}_{N−1}h_{1}(μ) + log(N − 1 + |A|).

Allora

\begin{matrix}\overline{Z} & N \\ \overline{Z} & N−1 \end{matrix} ≥ 1 + \frac{2^{−\overline{Z}_{N−1}h_{1}(μ)}}{2(N − 1 + |A|)}.

La successione \overline{Z}_{N} è crescente: se per assurdo \overline{Z}_{N} tendesse a una costante, dalla precedente equazione si avrebbe \overline{Z}_{N}/\overline{Z}_{N−1} ≥ 1 + c/(N − 1), ma ciò implicherebbe \overline{Z}_{N} → ∞.

Dimostriamo ora il teorema centrale. Dimostrazione del teorema 3.4.1. Per la composizione \overline{S}_{N} vale

\overline{S}_{N}(s_{1}^{n}) = \overline{S}_{N}(s_{1}) … \overline{S}_{N}(s_{n}),

dove le \overline{S}_{N}(s_{i}) sono parole nell’alfabeto originario A. Si consideri \underline{r} ∈ A^{∗}, |\underline{r}| = k e \underline{s} una stringa tipica per μ_{N}.

μ(\underline{r}) = lim_{n→∞} \frac{#\{\underline{r} ⊆ \overline{S}_{N}(s_{1}^{n})\}}{|\overline{S}_{N}(s_{1}^{n})|} = lim_{n→∞} \frac{#\{\underline{r} ⊆ \overline{S}_{N}(s_{1}) … \overline{S}_{N}(s_{n})\}}{|\overline{S}_{N}(s_{1}^{n})|}.

Si noti che

\begin{aligned}#\{\underline{r} ⊆ \overline{S}_{N}(s_{1}) & … \overline{S}_{N}(s_{n})\} = ∑_{g∈A_{N}} #\{\underline{r} ⊆ \overline{S}_{N}(g)\}#\{g ⊆ s_{1}^{n}\} \\ & + ∑_{p=2}^{k} ∑_{g_{1},...,g_{p}∈A_{N}} #\{\underline{r} ⌢ \overline{S}_{N}(g_{1}) … \overline{S}_{N}(g_{p})\}#\{g_{1} … g_{p} ⊆ s_{1}^{n}\} \end{aligned}

dove #\{\underline{r} ⌢ \overline{S}_{N}(g_{1}) … \overline{S}_{N}(g_{p})\} è il numero delle occorrenze di \overline{r} nella stringa \overline{S}_{N}(g_{1}) … \overline{S}_{N}(g_{p}) che inizia in \overline{S}_{N}(g_{1}) e termina in \overline{S}_{N}(g_{p}). Si ottiene

μ(\underline{r}) = lim_{n→∞} \frac{n}{|\overline{S}_{N}(s_{1}^{n})|}( ∑_{g∈A_{N}} #\{\underline{r} ⊆ \overline{S}_{N}(g)\}\frac{#\{g ⊆ s_{1}^{n}\}}{n}

+ ∑_{p=2}^{k} ∑_{g_{1},...,g_{p}∈A_{N}} #\{\underline{r} ⌢ \overline{S}_{N}(g_{1}) … \overline{S}_{N}(g_{p})\}\frac{#\{g_{1} … g_{p} ⊆ s_{1}^{n}\}}{n})

= \frac{1}{\overline{Z}_{N}} ( ∑_{g∈A_{N}} #\{\underline{r} ⊆ \overline{S}_{N}(g)\}μ_{N}(g)

+ ∑_{p=2}^{k} ∑_{g_{1},...,g_{p}∈A_{N}} #\{\underline{r} ⌢ \overline{S}_{N}(g_{1}) … \overline{S}_{N}(g_{p})\}μ_{N}(g_{1} … g_{p})).

Sia P l’operatore di proiezione che mappa una misura μ nella sua approssimazione 1-markoviana Pμ e si definisca π_{N}^{j} = S_{j+1} … S_{N}Pμ_{N}. In particolare si ha π_{N}^{0} = \overline{S}_{N}Pμ_{N} e π_{N}^{N} = Pμ_{N}. Vale

π_{N}^{N} = \overline{G}_{N}π_{N}^{0}.  (3.18)

Infatti le misure π_{N}^{N} e μ_{N} coincidono sulle coppie di simboli, e allora si ha π_{N}^{N}(\underline{w}) = 0 se \underline{w} ∉ \overline{G}_{N}(A^{∗}), come segue dal teorema 3.2.1. Poiché \overline{G}_{N}(A^{∗}) ⊆ G_{N}(A_{N−1}^{∗}), si può applicare la proposizione 3.2.5 e ottenere

π_{N}^{N} = G_{N}π_{N}^{N−1}.

Ora, anche π_{N}^{N−1} e μ_{N−1} coincidono sulle coppie di simboli (vedi proposizione 3.2.4) e allora si può iterare la procedura fino ad ottenere la (3.18).

Si noti che

\overline{Z}_{N}^{π_{N}^{0}} = ∏_{j=1}^{N}(1 + π_{N}^{j}(α_{j})) = ∏_{j=1}^{N}(1 + μ_{j}(α_{j})) = \overline{Z}_{N}^{μ};  (3.19)

infatti π_{N}^{j} e μ_{j} coincidono sulle coppie di simboli di A_{j}. Pertanto, per ogni k e ogni \underline{r} di lunghezza k, si ha

|π_{N}^{0}(\underline{r}) − μ(\underline{r})| ≤

≤ \frac{1}{\overline{Z}_{N}} ∑_{p=3}^{k} ∑_{g_{1},...,g_{p}∈A_{N}} (μ_{N} + π_{N})(g_{1} … g_{p})#\{\underline{r} ⌢ \overline{S}_{N}(g_{1}) … \overline{S}_{N}(g_{p})\}

≤ 2\frac{k^{2}}{\overline{Z}_{N}} ,

che tende a 0 per N → ∞. Ciò implica che

lim_{N→∞} h_{k}(π_{N}^{0}) = h_{k}(μ).

In conclusione, per ogni k vale

h(μ) = \frac{h(μ_{N})}{\overline{Z}_{N}} ≤ \frac{h_{1}(μ_{N})}{\overline{Z}_{N}} = \frac{h(π_{N}^{N})}{\overline{Z}_{N}} = h(π_{N}^{0}) ≤ h_{k}(π_{N}^{0}).

Il terzo passo nella precedente catena di uguaglianze e disuguaglianze segue dalla definizione π_{N}^{N} = Pμ_{N}, mentre il quarto passo segue dalle (3.18) e (3.19). Infine, prendendo i limiti per N → ∞ e k → ∞, si ha

h(μ) = lim_{N→∞} \frac{h_{1}(μ_{N})}{\overline{Z}_{N}},

cioè la tesi.

3.5 Un esempio interessante

La condizione (3.15), ipotesi del teorema centrale 3.4.1, è sufficiente ma non necessaria. In questa sezione analizzeremo nel dettaglio un esempio proposto da Benedetto, Caglioti, Gabrielli nell’articolo [BCG] (in cui gli autori elencano i risultati omettendo i calcoli). In tale esempio la suddetta condizione di divergenza del fattore di normalizzazione non è soddisfatta e tuttavia vale ancora la conclusione del teorema 3.4.1.

Nel corso di tutta questa sezione, indicheremo sempre con log il logaritmo in base 2.

L’alfabeto iniziale è A = {0, 1}. La prima sostituzione di coppia è 10 → 2, la seconda 20 → 3, e in generale l’N-esima sostituzione è N0 → N +1. Si noti che la composizione infinita di tali sostituzioni corrisponde alla procedura di codifica che sostituisce blocchi massimali di k zeri consecutivi, e l’uno che li precede, con il nuovo simbolo k + 1.

Se la misura iniziale assegna probabilità positiva alla coppia 11, allora il fattore di normalizzazione \overline{Z}_{N} non può divergere. Infatti esso rappresenta l’inverso dell’accorciamento della lunghezza delle stringhe, ma per una tipica stringa iniziale di lunghezza L dopo le trasformazioni restano circa μ(11)L simboli. Si ha pertanto che per N grande

\overline{Z}_{N} ≈ \frac{L}{μ(11)L} = \frac{1}{μ(11)} < ∞.

Si noti che solo la prima sostituzione coinvolge il simbolo 1. Pertanto,

μ_{N}(1|1) = μ_{1}(1|1) = \frac{μ(11) − μ(110)}{μ(1) − μ(10)} = μ(1|11),

μ_{N}(1|11) = μ_{1}(1|11) = \frac{μ(111) − μ(1110)}{μ(11) − μ(110)} = μ(1|111).

Se per la misura iniziale μ(1|111) ≠ μ(1|11), allora μ_{N}(1|11) ≠ μ_{N}(1|1) per ogni N e h_{1}(μ_{N})/\overline{Z}_{N} non può convergere a h(μ) (il processo limite non può essere 1-markoviano).

Consideriamo ora come misura iniziale quella di un processo di rinnovamento (renewal process) a media finita, ovvero un processo stazionario per il quale le distanze tra simboli ‘1’ consecutivi sono variabili aleatorie indipendenti e identicamente distribuite (i.i.d.r.v.) con distribuzione {p_{k}}_{k≥1}, dove i p_{k} soddisfano ∑_{k} p_{k} = 1 e E^{0} = ∑_{k=1}^{∞} kp_{k} < ∞. Per una trattazione dettagliata dei processi di rinnovamento discreti, il lettore è invitato a consultare il testo di Feller [Fe].

L’entropia di tale processo si può calcolare nel modo seguente. Essa rappresenta (vedi capitolo 2) il numero di bit per carattere che servono per codificare il processo binario. La quantità C = − ∑_{k} p_{k} log p_{k} invece rappresenta il numero di bit per numero di salti tra simboli ‘1’ consecutivi che servono per codificare il processo dei salti. In altre parole, la quantità C è l’entropia di una variabile aleatoria che descrive la lunghezza di un salto tra due simboli ‘1’ consecutivi. Il legame tra queste due quantità si può vedere mediante le seguenti considerazioni. Con n salti si descrive una stringa di circa nE^{0} caratteri, essendo E^{0} la lunghezza media dei salti. Pertanto, per n tendente all’infinito, con nC bit si descrivono nE^{0} caratteri e quindi

h(μ) ≈^{n→∞} \frac{nC}{nE^{0}} = \frac{− ∑_{k} p_{k} log p_{k}}{E^{0}} .  (3.20)

Per un calcolo esplicito dei marginali di μ_{N} abbiamo usato iterativamente le formule (3.21) qui sotto, le quali esprimono i valori marginali della misura trasformata da una sostituzione di coppie xy → α, con x ≠ y, in funzione dei valori marginali della misura di partenza e dei fattori di normalizzazione dati dalla (3.22). Per la loro dimostrazione si consulti l’appendice A, equazioni (A.8) e (A.9).

Se \underline{s} e \underline{r} sono due stringhe finite tali che \underline{s} = G_{xy}^{α}(\underline{r}) con |\underline{s}| = n e |\underline{r}| = k, l’espressione della misura trasformata ν(\underline{s}) = G_{xy}^{α}μ(\underline{s}) è data da una delle seguenti:

\begin{matrix}s_{1} ≠ y, s_{n} ≠ x, & ν(\underline{s}) = Zμ(\underline{r}) \\ s_{1} = y, s_{n} ≠ x, & ν(\underline{s}) = Z(μ(\underline{r}) − μ(xyr_{2}^{k})) \\ s_{1} ≠ y, s_{n} = x, & ν(\underline{s}) = Z(μ(\underline{r}) − μ(r_{1}^{k−1}xy)) \\ s_{1} = y, s_{n} = x, & ν(\underline{s}) = Z(μ(\underline{r}) + μ(xyr_{2}^{k−1}xy) − μ(xyr_{2}^{k}) − μ(r_{1}^{k−1}xy)). \end{matrix} ; (3.21)

Il fattore di normalizzazione Z = Z_{xy}^{μ} è dato in termini di μ da

Z = 1 + ν(α) = 1 + Zμ(xy) = \frac{1}{1 − μ(xy)}.  (3.22)

Spiegando le (3.21) a parole, esse tengono conto del fatto che, essendo \underline{s} e \underline{r} stringhe finite facenti parte di successioni infinite, possono esserci degli effetti di bordo all’inizio e alla fine delle stringhe stesse. Pur essendo S(∗\underline{s}∗) = ∗\underline{r}∗, potrebbe valere μ(\underline{r}) ≠ Gμ(\underline{s}), e ciò nel caso in cui \underline{s} abbia il primo o l’ultimo simbolo coinvolti nella sostituzione data.

Esemplificando secondo le convenzioni di questa sezione, mentre le stringhe che dopo la prima sostituzione (10 → 2) iniziano con 2 derivano da tutte e sole quelle che iniziano con 10, quelle che dopo la sostituzione iniziano con 0 derivano da tutte e sole quelle che iniziano con 00, non 0, perché ovviamente se lo 0 fosse stato preceduto da un 1, con la trasformazione sarebbe scomparso.

Grazie alle (3.21) si ha

dopo N sostituzioni 0 1 2 ⋯  N  N + 1
↕ ↕ ↕ ⋯  ↕  ↕
dopo 0 sostituzioni 0^{N+1} 11 101 ⋯ 10^{N−1}1 10^{N}

(3.23)

dove con 0^{k} si intende una stringa di k zeri consecutivi. Perciò, i valori marginali di μ_{N} sui simboli singoli sono uguali, a meno del fattore di normalizzazione \overline{Z}_{N} da determinare, ai valori della misura iniziale μ_{0} sulla stringa corrispondente.

Calcoliamo preliminarmente, perché utili nel seguito, μ_{0}(1) e μ_{0}(0^{k}). Il valore di μ_{0}(1) si può calcolare trovando la probabilità che ad un dato istante ci si trovi in un salto di lunghezza k, dividendo per k perché in tale salto ci sono k − 1 zeri e 1 uno, e sommando su tutti i k:

μ_{0}(1) = ∑_{k≥1} \frac{1}{k} \frac{kp_{k}}{∑_{j≥1} jp_{j}} = \frac{1}{E^{0}} .

Ragionando in modo del tutto analogo si trova

μ_{0}(0^{k}) = \frac{∑_{j≥1} jp_{k+j}}{E^{0}} .

Si ha cosí:

μ_{N}(0) = \overline{Z}_{N}μ_{0}(0^{N+1}) = \overline{Z}_{N} \frac{∑_{j≥1} jp_{k+j}}{E^{0}} ; μ_{N}(1) = \overline{Z}_{N}μ_{0}(11) = \overline{Z}_{N} \frac{p_{1}}{E^{0}} ; μ_{N}(2) = \overline{Z}_{N}μ_{0}(101) = \overline{Z}_{N} \frac{p_{2}}{E^{0}} ; ⋮ ; μ_{N}(N) = \overline{Z}_{N}μ_{0}(10^{N−1}1) = \overline{Z}_{N} \frac{p_{N}}{E^{0}} ; μ_{N}(N + 1) = \overline{Z}_{N}μ_{0}(10^{N}) = \overline{Z}_{N} \frac{p_{N+1} + p_{N+2} + …}{E^{0}}  (3.24)

Poiché deve essere ∑_{k=0}^{N+1} μ_{N}(k) = 1, si può trovare un valore esplicito del fattore di normalizzazione:

\overline{Z}_{N} = \frac{E^{0}}{p_{1} + … + p_{N} + p_{N+1} + 2p_{N+2} + 3p_{N+3} + …},

che si può riscrivere come

\overline{Z}_{N} = \frac{E^{0}}{E^{N}} ,  (3.25)

ponendo E^{N} = ∑_{j=1}^{∞} jp_{j}^{N} e

p_{j}^{N} = \{ \begin{matrix}p_{1} + … + p_{N+1} & j = 1 \\ p_{N+j} & j > 1 \end{matrix} .

Il ragionamento per determinare i marginali di μ_{N} sulle coppie di simboli è del tutto analogo e i risultati sono riportati nelle seguenti tabelle. Nella prima, M_{ij} è la stringa iniziale (dopo 0 sostituzioni) corrispondente alla coppia di simboli ij che si ha dopo N sostituzioni.

M = \begin{aligned}& 0 & 1 & 2 & … & N & N + 1 \\ 0 & 0^{N+2} & 0^{N+1}11 & 0^{N+1}101 & … & 0^{N+1}10^{N−1}1 & 0^{N+1}10^{N} \\ 1 & ∅ & 111 & 1101 & … & 110^{N−1}1 & 110^{N} \\ 2 & ∅ & 1011 & 10101 & … & 1010^{N−1}1 & 1010^{N} \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ N & ∅ & 10^{N−1}11 & 10^{N−1}101 & … & 10^{N−1}10^{N−1}1 & 10^{N−1}10^{N} \\ N + 1 & 10^{N+1} & 10^{N}11 & 10^{N}101 & … & 10^{N}10^{N−1}1 & 10^{N}10^{N} \end{aligned}

Nella prossima tabella sono riportati i valori marginali di μ_{N} sulle coppie di simboli. Il valore di posto (i, j) è V_{ij} = μ_{N}(ij) = \overline{Z}_{N}μ_{0}(M_{ij}).

V = \begin{aligned}& 0 & 1 & 2 & … & N & N + 1 \\ 0 & \frac{∑_{i≥1} ip_{N+2+i}}{E^{N}} & \frac{p_{1}p_{N+2}^{+}}{E^{N}} & \frac{p_{2}p_{N+2}^{+}}{E^{N}} & … & \frac{p_{N} p_{N+2}^{+}}{E^{N}} & \frac{p_{N+1}^{+}p_{N+2}^{+}}{E^{N}} \\ 1 & 0 & \frac{p_{1}p_{1}}{E^{N}} & \frac{p_{1}p_{2}}{E^{N}} & … & \frac{p_{1}p_{N}}{E^{N}} & \frac{p_{N+1}^{+}p_{1}}{E^{N}} \\ 2 & 0 & \frac{p_{2}p_{1}}{E^{N}} & \frac{p_{2}p_{2}}{E^{N}} & … & \frac{p_{2}p_{N}}{E^{N}} & \frac{p_{N+1}^{+}p_{2}}{E^{N}} \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ N & 0 & \frac{p_{N} p_{1}}{E^{N}} & \frac{p_{N} p_{2}}{E^{N}} & … & \frac{p_{N} p_{N}}{E^{N}} & \frac{p_{N+1}^{+}p_{N}}{E^{N}} \\ N + 1 & \frac{p_{N+2}^{+}}{E^{N}} & \frac{p_{N+1}p_{1}}{E^{N}} & \frac{p_{N+1}p_{2}}{E^{N}} & … & \frac{p_{N+1}p_{N}}{E^{N}} & \frac{p_{N+1}^{+}p_{N+1}}{E^{N}} \end{aligned}

dove si è usata la notazione p_{k}^{+} = ∑_{i≥k} p_{i}.

Osservazione 3.5.1. In particolare vale

μ_{N−1}(N0) = \overline{Z}_{N−1}μ_{0}(10^{N}) = \frac{E^{0}}{E^{N−1}} \frac{∑_{i≥N+1} p_{i}}{E^{0}} = \frac{∑_{i≥N+1} p_{i}}{E^{N−1}} ,

da cui si ricava

Z_{N} = \frac{1}{1 − μ_{N−1}(N0)} = \frac{E^{N−1}}{E^{N−1} − ∑_{i≥N+1} p_{i}} = \frac{E^{N−1}}{E^{N}} ,

in accordo con la (3.25).

Usando i risultati raccolti nelle (3.24), otteniamo

\frac{H_{1}(μ_{N})}{\overline{Z}_{N}} = − \frac{E^{N}}{E^{0}} [\frac{∑_{i≥1} ip_{n+1+i}}{E^{0}} log \frac{∑_{i≥1} ip_{n+1+i}}{E^{N}}

− ∑_{j=1}^{N} \frac{p_{j}}{E^{0}} log \frac{p_{j}}{E^{N}} − \frac{∑_{i≥1} p_{n+i}}{E^{0}} log \frac{∑_{i≥1} p_{n+i}}{E^{N}} ].

(3.26)

Ricordando che lim_{x→0^{+}} x log x = 0 e osservando che, per N tendente all’infinito, ∑_{i≥1} p_{n+i} → 0, ∑_{i≥1} ip_{n+1+i} → 0 e E^{N} → 1, otteniamo infine

lim_{N→∞} \frac{H_{1}(μ_{N})}{\overline{Z}_{N}} = \frac{− ∑_{j≥1} p_{j} log p_{j}}{E^{0}} .  (3.27)

Dai risultati della tabella V otteniamo, utilizzando la notazione p_{k}^{+} = ∑_{i≥k} p_{i},

\frac{H_{2}(μ_{N})}{\overline{Z}_{N}} = \frac{E^{N}}{E^{0}} [ ∑_{i=1}^{N+1} (∑_{j=1}^{N} (\frac{p_{i}p_{j}}{E^{N}} log \frac{p_{i}p_{j}}{E^{N}} ) + \frac{p_{i}p_{N+1}^{+}}{E^{N}} log \frac{p_{i}}{E^{N}} )

− \frac{p_{N+2}^{+}}{E^{N}} log \frac{p_{N+2}^{+}}{E^{N}} − \frac{∑_{k≥1} kp_{N+2+k}}{E^{N}} log \frac{∑_{k≥1} kp_{N+2+k}}{E^{N}}

− ∑_{j=1}^{N} \frac{p_{j}p_{N+2}^{+}}{E^{N}} log \frac{p_{j}p_{N+2}^{+}}{E^{N}} − \frac{p_{N+2}^{+}p_{N+1}^{+}}{E^{N}} log \frac{p_{N+2}^{+}p_{N+1}^{+}}{E^{N}} ].

(3.28)

In tale somma tutti i termini hanno limite nullo per N tendente all’infinito, tranne ∑_{i=1}^{N+1} ∑_{j=1}^{N} \frac{p_{i}p_{j}}{E^{N}} log \frac{p_{i}p_{j}}{E^{N}}, e da semplici calcoli otteniamo

lim_{N→∞} \frac{H_{2}(μ_{N})}{\overline{Z}_{N}} = \frac{−2 ∑_{j≥1} p_{j} log p_{j}}{E^{0}} .  (3.29)

Pertanto, ricordando che h_{1} = H_{2} − H_{1} e osservando che in questo caso si ha H_{2}(μ_{N}) = 2H_{1}(μ_{N}) nel limite per N che va a infinito, per il particolare processo di questo esempio vale

lim_{N→∞} \frac{h_{1}(μ_{N})}{\overline{Z}_{N}} = lim_{N→∞} \frac{H_{1}(μ_{N})}{\overline{Z}_{N}} = h(μ),  (3.30)

cioè non solo il processo diventa 1-markoviano h_{1}(μ_{N})/\overline{Z}_{N} → h(μ) nel limite per il numero di sostituzioni che va all’infinito, ma esso diventa anche indipendente H_{1}(μ_{N})/\overline{Z}_{N} → h(μ). Tale fatto è ovviamente conseguenza della scelta molto particolare della misura iniziale.

Quasto esempio fa sorgere una domanda naturale. Mentre il teorema centrale 3.4.1 dimostra che, sotto la condizione (3.15) di divergenza del fattore di normalizzazione, ogni processo ergodico diventa asintoticamente 1markoviano, ci si può chiedere quali siano le condizioni sul processo e sulle sostituzioni affinché il processo limite diventi addirittura indipendente. Tuttavia, tale quesito non sembra essere di facile soluzione.

Metodi di stima dell’entropia

Nel capitolo 5 guarderemo il metodo delle sostituzioni di Grassberger da un punto di vista computazionale e confronteremo i risultati di tale metodo con altri tre metodi classici per la stima empirica dell’entropia. In questo capitolo presentiamo i risultati teorici sui quali tali tre metodi sono basati.

Il metodo delle frequenze empiriche si basa sul teorema 4.1.2, il quale formalizza il tentativo piú intuitivo, cioè quello di applicare direttamente la definizione di entropia stessa.

Il secondo metodo è quello dei tempi di ritorno, basato sul teorema 4.2.2, il quale mette in relazione l’entropia con la crescita esponenziale in n del tempo che passa tra due occorrenze consecutive di un blocco simbolico di lunghezza n.

Il terzo metodo si basa sull’uguaglianza, per certe classi di trasformazioni, tra entropia e esponente di Lyapunov (teorema 4.3.4).

In tutto il capitolo indicheremo con log il logaritmo in base 2.

4.1 Frequenze empiriche

Data una successione campione x_{1}, x_{2}, …, x_{n} estratta da un processo ergodico μ non conosciuto, si vuole stimare l’entropia h di μ. Una procedura semplice è quella di determinare la distribuzione empirica q_{k} dei k-blocchi non sovrapposti e prendere H(q_{k})/k come stima di h. Se k è fissato e n → ∞ allora H(q_{k})/k converge quasi certamente a H(μ_{k})/k, quantità che converge a h per k → ∞. Quindi esiste una scelta di k = k(n) come funzione di n per la quale la stima converge quasi certamente a h. A prima vista, però, la scelta di k(n) potrebbe dipendere strettamente dalla misura μ e non c’è motivo di ritenere a priori che esista una scelta universale di k = k(n), con k(n) → ∞, per la quale la distribuzione empirica è vicina alla vera distribuzione μ_{k} per ogni processo ergodico μ. Tuttavia, il prossimo teorema dovuto a Ornstein e Weiss [OW] (per la cui dimostrazione rimandiamo al testo di Shields [Sh]) implica proprio l’esistenza di una tale scelta universale.

Data la successione x_{1}, x_{2}, …, x_{n}, la distribuzione empirica dei k-blocchi non sovrapposti è definita in modo naturale da

q_{k}(a_{1}^{k}|x_{1}^{n}) = \frac{|\{i ∈ [0, m − 1] : x_{ik+1}^{ik+k} = a_{1}^{k}\}|}{m},

dove n = km + r, 0 ≤ r < k.

Teorema 4.1.1 (Teorema dell’entropia empirica). Sia μ una misura ergodica con entropia h > 0. Per ogni ϵ > 0 e ogni k esiste un insieme T_{k}(ϵ) ⊆ A^{k} con |T_{k}(ϵ)| ≤ 2^{k(h+ϵ)}, tale che per quasi ogni x esiste un K = K(ϵ, x) tale che se k ≥ K e n ≥ 2^{kh}, allora

(a) q_{k}(T_{k}(ϵ)|x_{1}^{n}) > 1 − ϵ,

(b) q_{k}(B|x_{1}^{n}) < ϵ, per ogni B ⊆ A^{k} con |B| ≤ 2^{k(h−ϵ)}.

Da questo teorema discende il seguente.

Teorema 4.1.2. Se μ è una misura ergodica di entropia h > 0, se k(n) → ∞ per n → ∞ e se k(n) ≤ (1/h) log n, allora

lim_{n→∞} \frac{1}{k(n)}H(q_{k(n)}(·|x_{1}^{n})) = h, q. c.  (4.1)

Dimostrazione. Si fissi ϵ > 0 e sia {T_{k}(ϵ) ⊆ A^{k} : n ≥ 1} un insieme che soddisfi la parte (a) del teorema 4.1.1. Sia U_{k} l’insieme di tutte le stringhe a_{1}^{k} ∈ T_{k}(ϵ) per le quali q_{k}(a_{1}^{k}|x_{1}^{n}) < 2^{−k(h+2ϵ)}, cosí che per tutti i k ≥ K e tutti gli n ≥ 2^{kh},

q_{k}(U_{k}|x_{1}^{n}) ≤ |T_{k}(ϵ)| · 2^{−k(h+2ϵ)} ≤ 2^{k(h+ϵ)}2^{−k(h+2ϵ)} = 2^{−ϵk}.  (4.2)

Sia ora V_{k} l’insieme di tutte le stringhe a_{1}^{k} per le quali q_{k}(a_{1}^{k}|x_{1}^{n}) > 2^{−k(h−2ϵ)}, e si osservi che |V_{k}| ≤ 2^{k(h−2ϵ)}. La parte (b) del teorema 4.1.1 implica che per quasi ogni x esiste un K(x) tale che

q_{k}(V_{k}|x_{1}^{n}) ≤ ϵ, per k ≥ K(x), n ≥ 2^{kh}.  (4.3)

Dalle disuguaglianze (4.1) e (4.2) e dalla parte (a) del teorema 4.1.1 segue che per quasi ogni x esiste K_{1}(x) tale che

q_{k}(G_{k}|x_{1}^{n}) ≥ 1 − 3ϵ, per k ≥ K_{1}(x), n ≥ 2^{kh},

dove G_{k} = T_{k}(ϵ) \ (U_{k} ∪ V_{k}). Quindi, l’insieme degli a_{1}^{k} per cui

2^{−k(h+2ϵ)} ≤ q_{k}(a_{1}^{k}|x_{1}^{n}) ≤ 2^{−k(h−2ϵ)},

o equivalentemente

h − 2ϵ ≤ −\frac{1}{k} log q_{k}(a_{1}^{k}|x_{1}^{n}) ≤ h + 2ϵ,  (4.4)

misura secondo q_{k}(·|x_{1}^{n}) almeno 1 − 3ϵ. Moltiplicando nella (4.4) per la quantità q_{k}(a_{1}^{k}|x_{1}^{n})/μ(G_{n}) e sommando su G_{n} si ottiene

h − 2ϵ ≤ −\frac{1}{kμ(G_{n})} ∑_{G_{n}} q_{k}(a_{1}^{k}|x_{1}^{n}) log q_{k}(a_{1}^{k}|x_{1}^{n}) ≤ h + 2ϵ.

Poiché per n → ∞ la misura di G_{n} tende a 1, si ha infine

h − 2ϵ ≤ H(q_{k(n)}(·|x_{1}^{n})) ≤ h + 2ϵ,

cioè la tesi.

4.2 Tempi di ritorno

Wyner e Ziv hanno scoperto una connessione interessante fra entropia e i cosiddetti tempi di ritorno per processi ergodici. Essi hanno mostrato in [WZ] che il logaritmo del tempo di attesa perché si riosservino i primi n termini di una successione x è asintotico a nh in probabilità.

Presentiamo ora la formalizzazione di ciò e un’idea di dimostrazione.

Definizione 4.2.1. Data una successione x estratta da un processo ergodico, si definisce l’n-esimo tempo di ritorno come

R_{n}(x) = min{m ≥ 1 : x_{m+1}^{m+n} = x_{1}^{n}}.

Il teorema che lega i tempi di ritorno all’entropia è il seguente.

Teorema 4.2.2. Se μ è un processo ergodico con entropia h, allora vale

lim_{n→∞} \frac{1}{n} log R_{n}(x) = h, q. c.

Dimostrazione. Definiamo i limiti superiore e inferiore,

\overline{r}(x) = lim sup_{n→∞} \frac{1}{n} log R_{n}(x),
\underline{r}(x) = lim inf_{n→∞} \frac{1}{n} log R_{n}(x).

Poiché R_{n−1}(T x) ≤ R_{n}(x), i limiti superiore e inferiore sono entrambi subinvarianti, cioè

\overline{r}(T x) ≤ \overline{r}, e \underline{r}(T x) ≤ \underline{r},

e perciò sono entrambi invarianti quasi certamente. Poiché la misura è ergodica per ipotesi, i limiti superiore e inferiore sono dunque costanti quasi ovunque, e quindi esistono due costanti \overline{r} e \underline{r} tali che

\overline{r}(x) = \overline{r} e \underline{r}(x) = \underline{r}, q. o.

Inoltre \underline{r} ≤ \overline{r}, per cui la tesi si può dimostrare provando le due disuguaglianze \underline{r} ≥ h e \overline{r} ≤ h.

Per la prima disuguaglianza proponiamo qui una dimostrazione dovuta a Wyner e Ziv. Per la seconda la dimostrazione è piú complicata e richiede nozioni che non approfondiamo in questa tesi, come i codici fedeli e la relazione tra il rapporto di compressione di un codice e l’entropia. Ci limiteremo a indicare per sommi capi la linea della dimostrazione, invitando a consultare il testo di Shields [Sh] per una presentazione completa.

Per stabilire \overline{r} ≤ h si fissi ϵ > 0 e si definiscano gli insiemi

D_{n} = {x : R_{n}(x) > 2^{n(h+ϵ)}}, n ≥ 1.

L’obiettivo è dimostrare che, per quasi ogni x, x ∉ D_{n} definitivamente. È sufficiente dimostrare ciò sotto l’ipotesi ulteriore che x sia una successione tipica per l’entropia. Infatti, se

T_{n} = {x : μ(x_{1}^{n}) ≥ 2^{−n(h+ϵ/2)}}

allora per quasi ogni x si ha x ∈ T_{n} definitivamente, per cui è sufficiente dimostrare che

x ∉ D_{n} ∩ T_{n}, definitivamente, q. c.  (4.5)

Per dimostrare ciò si fissi a_{1}^{n} e si considerino solo gli x ∈ D_{n} per i quali x_{1}^{n} = a_{1}^{n}, cioè l’insieme D_{n}(a_{1}^{n}) = D_{n} ∩ [a_{1}^{n}]. Si noti che, se x ∈ D_{n}(a_{1}^{n}), allora T^{j}x ∉ [a_{1}^{n}] per j ∈ [1, 2^{n(h+ϵ)} − 1], per la definizione di D_{n}(a_{1}^{n}), e pertanto gli insiemi

D_{n}(a_{1}^{n}), T^{−1}D_{n}(a_{1}^{n}), …, T^{−2^{n(h+ϵ)}+1}D_{n}(a_{1}^{n})

sono disgiunti. Poiché tali insiemi hanno tutti la stessa misura, il fatto che siano disgiunti implica che

μ(D_{n}(a_{1}^{n})) ≤ 2^{−n(h+ϵ)}.  (4.6)

È ora semplice arrivare alla (4.5) dalla (4.6). Infatti, la cardinalità della proiezione di D_{n} ∩ T_{n} su A^{n} è limitata superiormente dalla cardinalità di T_{n}, la quale è limitata superiormente da 2^{n(h+ϵ/2)}, cosí che dalla (4.6) segue

μ(D_{n} ∩ T_{n}) ≤ 2^{n(h+ϵ/2)}2^{−n(h+ϵ)} = 2^{−nϵ/2}.

Per il principio di Borel-Cantelli si ha infine che per quasi ogni x, definitivamente x ∉ D_{n} ∩ T_{n}.

La disuguaglianza \underline{r} ≥ h si può dimostrare facendo vedere che, se non fosse vera, si potrebbe costruire un codice con un rapporto di compressione superiore all’entropia. L’esistenza di un tale codice non è però possibile (vedi Shields [Sh], p. 121 ss.)

4.3 Esponente di Lyapunov

Nel teorema 4.3.4 si dimostrerà che l’entropia di una trasformazione C^{1} a tratti T definita su un intervallo, che abbia una misura di probabilità invariante assolutamente continua, può essere calcolata prendendo la media di log |T′|. Tale media è chiamata esponente di Lyapunov di T e misura la velocità di allontanamento esponenziale di due punti vicini sotto l’azione della trasformazione T.

Siano X = [0, 1], T : X → X un’applicazione C^{1} a tratti e μ una misura di probabilità T -invariante.

Definizione 4.3.1. La quantità ∫_{0}^{1} log |T′|dμ è detta esponente di Lyapunov di T.

Sebbene la conclusione del teorema 4.3.4 si pensa valga in casi molto generali, noi ne presentiamo qui la dimostrazione sotto le seguenti ipotesi restrittive (vedi Choe [Ch]). Qui e nel seguito della sezione si assumerà che valga dμ = ρ(x)dx con A ≤ ρ(x) ≤ B per ogni x ∈ [0, 1], per due costanti A, B > 0. Sia P una partizione generatrice di X, costituita da intervalli E_{j} con μ(E_{j}) > 0 e ∑_{j} μ(E_{j}) = 1. Sia

P_{n} = P ∨ T^{−1}P ∨ … ∨ T^{−(n−1)}P,

cioè la partizione negli insiemi cilindrici

[i_{1}, i_{2}, …, i_{n}] = E_{i_{1}} ∩ T^{−1}E_{i_{2}} ∩ … ∩ T^{−(n−1)}E_{i_{n}}.  (4.7)

Si assuma che esista un N tale che se n ≥ N allora (i) ogni insieme cilindrico della forma (4.7) è un intervallo e (ii) T è monotona e differenziabile con continuità su ogni insieme cilindrico in P_{n}.

Lemma 4.3.2. Sia λ la misura di Lebesgue su [0, 1]. Allora

λ([i_{2}, …, i_{n}]) = |T′(z_{i_{1},...,i_{n}})|λ([i_{1}, …, i_{n}]),

per qualche z_{i_{1},...,i_{n}} ∈ [i_{1}, …, i_{n}] per n sufficientemente grande. Dimostrazione. Poiché T ([i_{1}, …, i_{n}]) = [i_{2}, …, i_{n}] e T è iniettiva sull’insieme cilindrico [i_{1}, …, i_{n}], vale

λ([i_{2}, …, i_{n}]) = |∫_{[i_{1},...,i_{n}]} T′(x)dx| = |T′(z_{i_{1},...,i_{n}})|λ([i_{1}, …, i_{n}])

per qualche z_{i_{1},...,i_{n}} ∈ [i_{1}, …, i_{n}]. Lemma 4.3.3. Si supponga che una successione {b_{n}}_{n=1}^{∞} soddisfi

lim_{n→∞}(b_{n+1} − b_{n}) = C

per qualche costante C. Allora

lim_{n→∞} \frac{b_{n}}{n} = C.

Dimostrazione. Fissato ϵ > 0, si scelga N tale che se n ≥ N allora

|b_{n+1} − b_{n} − C| < ϵ.

Allora

|b_{N+k} − b_{N} − kC| ≤ ∑_{j=1}^{k} |b_{N+j} − b_{N+j−1} − C| < kϵ

e

|\frac{b_{N+k}}{N + k} − \frac{b_{N}}{N + k} − \frac{k}{N + k} C| < \frac{k}{N + k} ϵ.

Mandando k all’infinito si ottiene

C − ϵ ≤ lim inf_{n→∞} \frac{b_{n}}{n} ≤ lim sup_{n→∞} \frac{b_{n}}{n} ≤ C + ϵ.

Poiché ϵ è arbitrario si ha la tesi. Teorema 4.3.4. Sia h l’entropia di T. Con le condizioni su T sopra elencate si ha

h = ∫_{0}^{1} log |T′(x)|dμ.

Dimostrazione. Si ponga

b_{n} = ∑_{i_{1},...,i_{n}} μ([i_{1}, …, i_{n}]) log λ([i_{1}, …, i_{n}])

e

L_{n} = ∑_{i_{1},...,i_{n}} μ([i_{1}, …, i_{n}]) log |T′(z_{i_{1},...,i_{n}})|.

Il lemma 4.3.2 implica che

b_{n} = ∑_{i_{1},...,i_{n}} μ([i_{1}, …, i_{n}]) log λ([i_{2}, …, i_{n}]) − L_{n}

= ∑_{i_{2},...,i_{n}} μ([i_{2}, …, i_{n}]) log λ([i_{1}, …, i_{n}]) − L_{n}

= b_{n−1} − L_{n}.

Allora

lim_{n→∞}(b_{n} − b_{n−1}) = − lim_{n→∞} L_{n} = − ∫_{0}^{1} log |T′|dμ.

Per il lemma 4.3.3 si ha

lim_{n→∞} \frac{b_{n}}{n} = − ∫_{0}^{1} log |T′|dμ

e allora

h = − lim_{n→∞} \frac{1}{n} ∑_{i_{1},...,i_{n}} μ([i_{1}, …, i_{n}]) log μ([i_{1}, …, i_{n}])

= − lim_{n→∞} \frac{1}{n} ∑_{i_{1},...,i_{n}} μ([i_{1}, …, i_{n}]) log λ([i_{1}, …, i_{n}])

= − lim_{n→∞} \frac{b_{n}}{n}

= ∫ log |T′|dμ.

La seconda uguaglianza segue dal fatto che

log A + log λ([i_{1}, …, i_{n}]) ≤ log μ([i_{1}, …, i_{n}]) ≤ log B + log λ([i_{1}, …, i_{n}]) e la dimostrazione è completa.

Simulazioni al calcolatore

In questo capitolo presentiamo le trasformazioni considerate per le simulazioni, discutiamo le simulazioni al calcolatore fatte e infine ne illustriamo e commentiamo i risultati.

5.1 Trasformazioni dell’intervallo [0, 1]

Abbiamo applicato i metodi di stima dell’entropia a quattro trasformazioni dello spazio ([0, 1], B([0, 1])).

La prima è la mappa logistica con fattore 4, definita da

Λx = 4x(1 − x), x ∈ [0, 1]  (5.1)

(vedi figura 5.1). È l’unico esempio di mappa continua che consideriamo.

Abbiamo poi considerato una mappa espandente a pezzi, discontinua in \frac{1}{2} e con due rami suriettivi. Essa è definita da

Ex = \{ \begin{matrix}\frac{4x}{3−2x} & se x ∈ [0, \frac{1}{2}] \\ \frac{2x−1}{2−x} & se x ∈]\frac{1}{2}, 1] \end{matrix}  (5.2)

e per essa vale E′(x) > k per ogni x, dove k > 1 è una costante (vedi figura 5.2).

Un esempio di mappa con due rami non suriettivi è la mappa di tipo Lorenz definita da

Lx = \{ \begin{matrix}1 − (\frac{−6x+3}{4})^{\frac{3}{4}} & se x ∈ [0, \frac{1}{2}[ \\ (\frac{6x−3}{4})^{\frac{3}{4}} & se x ∈ [\frac{1}{2}, 1] \end{matrix} .  (5.3)

46  5.1. TRASFORMAZIONI DELL’INTERVALLO [0, 1]

Figura 5.1: La mappa logistica Λ(x) = 4x(1 − x).

Figura 5.2: La mappa espandente a pezzi E definita da E(x) = \frac{4x}{3−2x} per 0 ≤ x ≤ \frac{1}{2} e da E(x) = E(x − \frac{1}{2}) per \frac{1}{2} < x ≤ 1.

Figura 5.3: Una mappa di tipo Lorenz, con rami non suriettivi e derivata uniformemente maggiore di 1. Essa è definita da L(x) = (\frac{6x−3}{4})^{\frac{3}{4}} per \frac{1}{2} ≤ x ≤ 1 e L(x) = 1 − L(1 − x) per 0 ≤ x < \frac{1}{2}.

Anche per essa vale L′ > 1 uniformemente per ogni x ∈ [0, 1]\\{\frac{1}{2}\} e L′(\frac{1}{2}^{±}) = +∞ (vedi figura 5.3).

Per la quarta trasformazione abbiamo preso in considerazione la classe delle mappe di Manneville (vedi [PM]) definite da

M_{s}x = x + x^{s} (mod 1), s ∈ ℝ^{+}.  (5.4)

Tali mappe sono di notevole interesse in fisica e hanno caratteristiche diverse al variare del parametro s. Noi abbiamo focalizzato l’attenzione sui valori 1 < s < 2, per i quali le mappe ammettono una misura di probabilità invariante assolutamente continua. Nella figura 5.4 è riportato il grafico della mappa di Manneville con esponente s = \frac{3}{2}.

La mappa logistica si conosce molto bene. Di essa è nota esplicitamente l’unica misura invariante, che è ergodica e assolutamente continua con densità ρ(x) = \frac{1}{π\sqrt{x(1−x)}}. Pur essendo ρ illimitata, Choe dimostra (vedi [Ch]) che la

conclusione del teorema 4.3.4 vale anche in questo caso. Si sa inoltre (vedi ad esempio [Ch]) che il sistema dinamico ([0, 1], B([0, 1]), ρ(x)dx, Λ) è isomorfo allo shift di Bernoulli con alfabeto \{0, 1\} e parametri (\frac{1}{2}, \frac{1}{2}). Tale isomorfismo è ottenuto mediante il passaggio alla dinamica simbolica considerando la partizione generatrice \{[0, \frac{1}{2}],]\frac{1}{2}, 1]\}.

Figura 5.4: La mappa di Manneville con esponente s = \frac{3}{2}. La derivata è strettamente maggiore di 1 in ogni x ∈]0, 1] mentre M′(0^{+}) = 1.

Le mappe espandente a pezzi e di tipo Lorenz possiedono anch’esse un’unica misura di probabilità invariante, la quale è assolutamente continua rispetto alla misura di Lebesgue ed ergodica (vedi Viana [Vi]).

Le mappe di Manneville con esponente 1 < s < 2 hanno una misura invariante assolutamente continua con densità illimitata per x → 0^{+} ma integrabile (vedi Isola [Is]).

Ricordiamo che il passaggio da una trasformazione T : [0, 1] → [0, 1] alla dinamica simbolica si effettua fissando una partizione (vedi sezione 1.5.3). Affinché la trasformazione di shift sullo spazio di successioni cosí ottenuto costituisca una t.c.m. isomorfa alla trasformazione T, occorre ed è sufficiente che la partizione considerata sia generatrice (proposizione 1.5.4). Nel caso che T sia una delle trasformazioni espandente a pezzi, di tipo Lorenz e di tipo Manneville sono generatrici le partizioni {[0, c],]c, 1]}, dove c ∈]0, 1[ è quel valore tale che T (c^{−}) = 1 e T (c^{+}) = 0 (si veda a tal proposito Buzzi [Bu]).

5.2 Simulazioni

Per le simulazioni al calcolatore abbiamo usato il linguaggio di programmazione C, con la libreria GMP - GNU Multiple Precision per la gestione di numeri in virgola mobile con precisione arbitraria. Il lettore interessato può visitare il sito Internet http://gmplib.org/ dove si trova la documentazione completa.

Tali simulazioni sono consistite nel calcolare, per le trasformazioni considerate, un certo numero di iterazioni partendo da un punto pseudo-casuale, nel calcolo dell’esponente di Lyapunov, nella creazione di stringhe simboliche derivanti dalle partizioni scelte, nell’applicazione a tali stringhe dei metodi di stima dell’entropia descritti nei capitoli 3 e 4. Nei casi da noi considerati, le partizioni sono costituite da due elementi cui abbiamo associato, come consuetudine, i simboli 0 e 1.

È necessario prestare attenzione nell’eseguire esperimenti al calcolatore che presuppongono l’iterazione di una data trasformazione, poiché l’accuratezza delle cifre diminuisce man mano che si eseguono le iterazioni. Gli errori dovuti all’uso da parte dei calcolatori di una precisione finita si amplificano, fino a quando le iterazioni calcolate ben poco hanno a che fare con i punti da cui si era partiti. Si può mostrare (vedi Choe [Ch], cap. 9) che, partendo con un certo numero d di cifre binarie significative, dopo n iterazioni rimangono in media d − nh cifre corrette, dove h è l’entropia della trasformazione. Si può fare anche un ragionamento piú preciso, che permette di determinare fino a quando si può iterare la trasformazione avendo la certezza che i simboli binari fino a quel momento determinati siano corretti.

Nell’eseguire il calcolo delle iterazioni abbiamo fatto due prove. Nella prima abbiamo usato per ogni numero gestito un numero di cifre molto alto (variabile da 56000 a 100000 a seconda delle trasformazioni), tale da garantire la correttezza teorica di 100000 simboli binari. L’ovvio prezzo da pagare per la correttezza teorica del calcolo è la lentezza dell’esecuzione del programma e il conseguente basso numero di iterazioni calcolabili in tempi accettabili. Nella seconda prova abbiamo usato un numero di cifre piú basso (1000), riuscendo ad ottenere per ognuna delle mappe una stringa simbolica lunga 33 milioni di bit. Al vantaggio di avere successioni simboliche piú lunghe si contrappone lo svantaggio (almeno in teoria) di avere dati affetti da errore. Tuttavia, applicando i vari metodi di stima alle successioni simboliche da 100 mila e 33 milioni di bit abbiamo ottenuto risultati uguali nella sostanza. Interpretiamo ciò dicendo che, anche con una precisione di calcolo teoricamente non sufficiente, non viene alterata in maniera apprezzabile la dinamica delle mappe. Vista la sostanziale uguaglianza dei risultati delle simulazioni nei due casi, riporteremo e commenteremo i dati ottenuti dall’applicazione dei metodi di stima alle successioni simboliche lunghe 33 milioni di bit.

Il calcolo dell’esponente di Lyapunov (ovvero la media rispetto alla misura invariante di log_{2} |T′|) è stato eseguito calcolando 100 milioni di iterazioni utilizzando una precisione pari a 1000 cifre binarie.

Il metodo di stima delle frequenze empiriche basato sul teorema 4.1.2 è stato applicato (seguendo le notazioni del medesimo teorema) con k = 1, 2, … e n(k) = ⌈2^{k\overline{h}}⌉, dove \overline{h} è il valore dell’entropia alla terza cifra decimale dato dal calcolo dell’esponente di Lyapunov e ⌈x⌉ denota il minimo intero maggiore di o uguale a x. Sono stati considerati valori di k crescenti fin tanto che il tempo di esecuzione al calcolatore è rimasto contenuto entro poche decine di minuti. Come valore massimo abbiamo considerato k = 25. Osserviamo che il tempo richiesto cresce esponenzialmente con k, giacché l’algoritmo richiede un numero di operazioni al passo k proporzionale a 2^{k}.

Poiché l’ipotesi del teorema 4.1.2 assume che si abbia k(n) ≤ \frac{1}{h} log_{2} n (o, equivalentemente, n(k) ≥ 2^{hk}), dove h è l’entropia della trasformazione, impostando nella formula di k(n) (ovvero di n(k)) un valore h̃ ≥ h l’ipotesi è vera a fortiori. Si potrebbe pertanto pensare di considerare dei valori k(n) che crescano con n piú lentamente (o, ciò che è lo stesso, dei valori di n(k) che crescano piú velocemente con k). Abbiamo fatto delle prove in questo senso, riuscendo ad ottenere delle approssimazioni decisamente migliori del valore di riferimento. Tuttavia, i valori h̃ ≥ h piú opportuni sono stati determinati empiricamente a seconda della trasformazione considerata, senza ravvisare in essi un criterio che li suggerisca a priori.

Il metodo dei tempi di ritorno di stringhe simboliche (vedi teorema 4.2.2) è stato eseguito mediando i dati su un campione di 1000 stringhe. Tale versione dell’algoritmo di stima dà risultati piú attendibili rispetto a quella che considera i tempi di ritorno delle sole stringhe simboliche iniziali, giacché quest’ultima risente fortemente della scelta pseudo-casuale del punto iniziale. Nella versione media, inoltre, i dati sono piú regolari e non presentano, come invece i dati relativi alla versione singola, rami di monotonia intervallati da salti di ampiezza apprezzabile.

Il metodo delle sostituzioni di coppie di Grassberger è stato applicato in conformità al capitolo 3 e all’appendice A. Vi sono solo due precisazioni da fare. Quando si sostituisce una coppia formata da simboli uguali, la somma infinita in (A.12) è stata approssimata troncandola ai primi ⌊log_{2} l(s)⌋ addendi, dove l(s) è la lunghezza del vettore simbolico dopo s sostituzioni di coppie e ⌊x⌋ indica il massimo intero minore di o uguale a x. Come seconda osservazione, facciamo presente che nelle simulazioni si sono eseguite in tutti i casi 280 sostituzioni di coppie. Dai dati ottenuti, tale numero sembra sufficiente.

5.3 Risultati delle simulazioni

Commenteremo diffusamente i risultati nel caso della mappa logistica e si potrà osservare come negli altri casi i dati si prestino spesso a un’analisi

Figura 5.5: Stima dell’esponente di Lyapunov per la mappa logistica Λ.

analoga. Quando non dovesse essere cosí ci soffermeremo per evidenziare i dettagli.

5.3.1 Mappa logistica Λ

Il calcolo dell’esponente di Lyapunov si stabilizza molto velocemente, fino già alla sesta cifra decimale dopo 10 milioni di iterazioni, tanto che i dati riportati nel grafico in figura 5.5 non sono distinguibili da una linea retta.

Nel grafico di figura 5.6 sono riportati i medesimi dati. Nonostante l’enorme ingrandimento di scala sulle ordinate, i dati risultano quasi perfettamente allineati sul valore 1.

Vista la notevole precisione e stabilizzazione dell’esponente di Lyapunov, esso verrà preso come valore ‘vero’ dell’entropia con cui comparare i dati ottenuti con gli altri metodi di stima.

Calcolando la distribuzione empirica dei blocchi simbolici non sovrapposti, otteniamo dei dati poco soddisfacenti (vedi figura 5.7).

La crescita dei valori stimati è estremamente lenta, e nei limiti del numero di iterazioni considerate essi arrivano a indicare un valore di stima molto piú basso rispetto al valore di riferimento. Si arguisce dal grafico in figura 5.7 che per osservare valori vicini a 1 bisognerebbe disporre di un numero molto piú alto di iterazioni.

Figura 5.6: Stima dell’esponente di Lyapunov per la mappa logistica Λ (zoom).

Figura 5.7: Stima dell’entropia per la mappa Λ mediante il calcolo delle frequenze empiriche dei blocchi simbolici.

Figura 5.8: Stima dell’entropia della mappa Λ mediante il calcolo dei tempi di ritorno di stringhe simboliche.

La stima ottenuta mediante il metodo dei tempi di ritorno presenta un andamento crescente al crescere della lunghezza l del blocco considerato (vedi figura 5.8). Complessivamente, i valori massimi ottenuti approssimano meglio il valore dell’entropia dato dall’esponente di Lyapunov rispetto al metodo del calcolo delle entropie empiriche.

Il metodo di Grassberger fornisce stime dell’entropia che crescono e si avvicinano velocemente al valore dell’entropia nel giro delle prime decine di sostituzioni. I valori di stima raggiungono un massimo in corrispondenza della 157-esima sostituzione, dopo la quale essi decrescono lentamente (vedi figure 5.9 e 5.10).

5.3.2 Mappa espandente a pezzi E

Anche in questo caso il calcolo dell’esponente di Lyapunov si stabilizza velocemente, anche se in misura minore rispetto al caso della mappa logistica. Nel corso dei 100 milioni di iterazioni considerate, il valore stimato dell’entropia si assesta fino alla terza cifra decimale e anche la quarta subisce oscillazioni molto ridotte. Posizionando i dati in un grafico con intervallo di osservazione delle ordinate [0, 1] (figura 5.11), dopo i primi 7-8 milioni di iterazioni essi non sono distinguibili da una linea retta.

Figura 5.9: Stima dell’entropia della mappa logistica Λ mediante il metodo delle sostituzioni di coppie di Grassberger.

Figura 5.10: Stima dell’entropia della mappa logistica Λ mediante il metodo delle sostituzioni di coppie di Grassberger (zoom).

Figura 5.11: Stima dell’esponente di Lyapunov per la mappa espandente a pezzi E.

Nel grafico di figura 5.12 riportiamo i medesimi dati ma con intervallo di osservazione sulle ordinate notevolmente ridotto.

Anche in questo caso, considerate la precisione e stabilizzazione dell’esponente di Lyapunov, esso verrà preso come valore di riferimento per l’entropia.

Il metodo del calcolo della distribuzione empirica dei blocchi simbolici non sovrapposti fornisce dei dati qualitativamente analoghi al caso corrispondente per la mappa logistica. Tali dati crescono molto lentamente e restano molto al di sotto del valore stimato dall’esponente di Lyapunov (vedi figura 5.13).

La stima ottenuta mediante il metodo dei tempi di ritorno (vedi figura 5.14) è anche in questo caso migliore rispetto a quella ottenuta dal calcolo delle probabilità empiriche dei blocchi simbolici, in termini di una migliore approssimazione del valore di riferimento.

Il metodo delle sostituzioni di coppie di Grassberger, analogamente al caso della mappa logistica, fornisce stime dell’entropia che crescono e si avvicinano velocemente al valore di riferimento (vedi figure 5.15 e 5.16). I valori di stima raggiungono un massimo intorno alla 170-esima sostituzione, e poi decrescono lentamente.

Figura 5.12: Stima dell’esponente di Lyapunov per la mappa espandente a pezzi E (zoom).

Figura 5.13: Stima dell’entropia per la mappa E mediante il calcolo delle frequenze empiriche dei blocchi simbolici.

Figura 5.14: Stima dell’entropia della mappa E mediante il calcolo dei tempi di ritorno di stringhe simboliche.

Figura 5.15: Stima dell’entropia della mappa espandente a pezzi E mediante il metodo delle sostituzioni di coppie di Grassberger.

Figura 5.16: Stima dell’entropia della mappa espandente a pezzi E mediante il metodo delle sostituzioni di coppie di Grassberger (zoom).

5.3.3 Mappa di tipo Lorenz L

La stima dell’esponente di Lyapunov per la mappa L ha un andamento molto simile al caso della mappa espandente a pezzi E. Nei 100 milioni di iterazioni calcolate essa si stabilizza velocemente fino alla quarta cifra decimale, come si può osservare dal grafico in figura 5.18. In figura 5.17 si nota come senza ingrandimenti degli assi i dati sembrano perfettamente allineati.

Nuovamente, il valore determinato dalla stima dell’esponente di Lyapunov verrà preso come termine di paragone per i dati ottenuti con gli altri metodi di stima.

Calcolando la distribuzione empirica dei blocchi simbolici non sovrapposti, otteniamo i dati riportati nel grafico di figura 5.19. Valgono anche in questo caso le corrispondenti considerazioni fatte per le mappe Λ e E.

Il calcolo dei tempi di ritorno fornisce, come per le mappe Λ e E, stime migliori rispetto al metodo del calcolo delle entropie empiriche dei blocchi simbolici (vedi figura 5.20).

Il metodo NSRPS stima l’entropia in modo qualitativamente analogo ai casi delle mappe logistica e espandente a pezzi. I valori di stima crescono fino a raggiungere un massimo in corrispondenza della 159-esima sostituzione, dopo la quale essi decrescono seppure molto lentamente (vedi figure 5.21 Figura 5.17: Stima dell’esponente di Lyapunov per la mappa di tipo Lorenz L.

Figura 5.18: Stima dell’esponente di Lyapunov per la mappa di tipo Lorenz L (zoom).

Figura 5.19: Stima dell’entropia per la mappa L mediante il calcolo delle frequenze empiriche dei blocchi simbolici.

Figura 5.20: Stima dell’entropia della mappa L mediante il calcolo dei tempi di ritorno di stringhe simboliche.

Figura 5.21: Stima dell’entropia della mappa di tipo Lorenz L mediante il metodo delle sostituzioni di coppie di Grassberger.

e 5.22).

5.3.4 Mappa di Manneville M con esponente \frac{3}{2}

La stabilizzazione della stima dell’esponente di Lyapunov nel caso della mappa di Manneville è un po’ piú lenta rispetto agli altri tre esempi considerati. I dati inseriti nel grafico di figura 5.23 si presentano quasi su una retta orizzontale e uno zoom sull’asse delle ordinate (vedi figura 5.24) mostra che nell’arco dei 100 milioni di iterazioni calcolate la convergenza della stima si stabilizza fino alla terza cifra decimale. Tuttavia osserviamo che negli altri tre esempi si registrava una stabilizzazione superiore. Questa maggiore oscillazione dei valori di stima è dovuta al fatto che la derivata M′(x) è uguale a 1 in 0 ed è molto vicina a 1 per valori molto piccoli di x. Quando, iterando la trasformazione, capita che un’iterazione cada molto vicino a 0, le successive iterate si manterranno per molto tempo vicine a 0. Si ha cosí che la stima dell’esponente di Lyapunov è continuamente alterata dalla presenza di lunghi blocchi di iterazioni per cui la quantità da mediare log_{2} |M′| è pressoché nulla. Si spiegano cosí le frequenti ripide diminuzioni della quantità stimata osservabili in figura 5.24. In termini di successioni simboliche, il fenomeno Figura 5.22: Stima dell’entropia della mappa di tipo Lorenz L mediante il metodo delle sostituzioni di coppie di Grassberger (zoom).

appena osservato si traduce nella presenza di lunghe sequenze costituite da molti zeri consecutivi.

Nonostante la stima dell’entropia come esponente di Lyapunov sia piú imprecisa rispetto ai casi delle mappe Λ, E, L, tre cifre significative stabilizzate sono comunque sufficienti perché possiamo prendere tale stima come valore di riferimento per il raffronto tra i vari metodi.

Il calcolo della distribuzione empirica dei blocchi simbolici non sovrapposti dà dei risultati insoddisfacenti (vedi figura 5.25). I valori di stima che si ottengono con questo metodo sono molto bassi e la loro crescita molto lenta, come del resto avviene nel caso delle altre tre trasformazioni prese in considerazione.

Il metodo dei tempi di ritorno dà una stima che, differentemente da quanto accadeva per le mappe Λ, E, L, resta molto al di sotto del valore di riferimento (vedi figura 5.26). Per ciascuna delle altre tre mappe lo scarto tra il valore di riferimento e gli ultimi valori stimati col metodo dei tempi di ritorno è inferiore a 0, 036. Per la mappa di Manneville invece tale scarto è circa 0, 076. Tale fatto si spiega con l’osservazione seguente. Nel caso della mappa di Manneville M ci sono molti blocchi simbolici di misura molto piccola e per i quali quindi i tempi di ritorno sono mediamente molto alti. La nostra successione simbolica lunga 33 milioni di bit è troppo corta perché in essa tali Figura 5.23: Stima dell’esponente di Lyapunov per la mappa di Manneville M.

Figura 5.24: Stima dell’esponente di Lyapunov per la mappa di Manneville M (zoom).

Figura 5.25: Stima dell’entropia per la mappa M mediante il calcolo delle frequenze empiriche dei blocchi simbolici.

blocchi di misura piccola si ripresentino. Segue da ciò che la media dei tempi di ritorno che noi calcoliamo su un campione di 1000 stringhe è sottostimata, ed essa è tanto piú sottostimata quanto piú sono numerosi i blocchi simbolici del campione di bassa probabilità. Nel caso della mappa di Manneville, per il blocco lungo 24 simboli abbiamo registrato sempre almeno 90 casi su 1000 in cui il blocco non ricompare entro la fine della successione. Molti di meno erano i casi analoghi per le mappe Λ, E, L. Osserviamo che con tale medesima motivazione Choe spiega un analogo fenomeno riguardo allo shift di Bernoulli di parametri (p, 1 − p) con p ≠ \frac{1}{2} (vedi [Ch], capitolo 12).

Il metodo di Grassberger fornisce per la mappa M dei risultati differenti rispetto alle altre tre mappe (vedi figure 5.27 e 5.28). In questo caso infatti le stime dell’entropia crescono e raggiungono un valore massimo molto al di sotto del valore di riferimento. Lo scarto è circa 0, 048, valore decisamente piú alto rispetto a quanto si aveva per le altre tre mappe, per le quali lo scarto era inferiore a 0, 002. Nonostante questa diversità, anche in questo caso i valori di stima raggiungono un massimo (questa volta in corrispondenza della 153-esima sostituzione) per poi decrescere molto lentamente.

Per capire il motivo di questa peggiore approssimazione del valore di riferimento da parte del metodo di Grassberger, abbiamo provato a variare alcuni parametri. Innanzi tutto, ricordiamo che nel programma che imple-Figura 5.26: Stima dell’entropia della mappa M mediante il calcolo dei tempi di ritorno di stringhe simboliche.

menta l’algoritmo abbiamo troncato una somma infinita a un numero di addendi pari a ⌊log_{2} l(s)⌋ (vedi sezione 5.2). Per capire se questo potesse incidere sui valori stimati abbiamo provato ad aumentare il numero di addendi calcolati. Tuttavia, a tale aumento di precisione teorica non è corrisposta una variazione rilevabile entro la sesta cifra decimale. Siamo quindi portati a concludere che l’approssimazione della somma infinita con una somma finita non è responsabile del fatto che la stima ottenuta è insoddisfacente.

Abbiamo poi provato ad applicare il metodo NSRPS a stringhe simboliche di lunghezza piú corta, sia nel caso della mappa di Manneville che negli altri tre casi. Al diminuire della lunghezza della stringa abbiamo registrato una diminuzione del valore massimo stimato e una diminuzione del numero di sostituzioni in corrispondenza del quale tale massimo è raggiunto. Ciò lascia supporre che si avrebbero migliori risultati di approssimazione del valore di riferimento applicando il metodo delle sostituzioni a una stringa simbolica piú lunga. Il motivo perché questo sia il caso della sola mappa di Manneville tra quelle considerate risiede probabilmente nelle caratteristiche molto particolari della mappa M.

Figura 5.27: Stima dell’entropia della mappa di Manneville M mediante il metodo delle sostituzioni di coppie di Grassberger.

Figura 5.28: Stima dell’entropia della mappa di Manneville M mediante il metodo delle sostituzioni di coppie di Grassberger (zoom).

5.4 Tempi di esecuzione delle simulazioni

Esponiamo in questa sezione alcuni commenti importanti sul tempo di esecuzione dei programmi delle simulazioni.

Nella sezione 5.3 abbiamo confrontato e valutato i vari metodi di stima dell’entropia studiati in virtú della loro migliore o peggiore approssimazione di un valore preso come riferimento. Non abbiamo fatto menzione dei tempi di esecuzione dei programmi, cosa che facciamo qui di seguito. Ai fini di una valutazione piú completa di un metodo computazionale di stima, la questione del tempo che occorre per l’applicazione dello stesso è tutt’altro che oziosa. Un metodo di stima che desse buoni o ottimi risultati di approssimazione ma che richiedesse dei tempi sproporzionatamente grandi non potrebbe essere valutato complessivamente bene.

Riporteremo i tempi approssimativi impiegati nell’esecuzione dei programmi su uno stesso calcolatore. Per una trattazione piú precisa dovrebbe eseguirsi un’analisi della complessità degli algoritmi. Per i nostri fini è tuttavia sufficiente una comparazione relativa tra i tempi dei vari metodi.

La velocità dei programmi che stimano l’esponente di Lyapunov dipende in modo consistente dal grado di precisione utilizzato e dal numero di operazioni necessarie nel calcolo di ogni iterazione. Tuttavia, come abbiamo già avuto modo di osservare, anche con una precisione di calcolo non eccessivamente alta (1000 cifre binarie) i risultati non differiscono quantitativamente in modo significativo da quelli ottenuti con precisione molto piú elevata. I programmi che abbiamo realizzato per la stima dell’esponente di Lyapunov (vedi sezione 5.2) impiegano circa 10-12 minuti, le variazioni essendo dovute alla trasformazione considerata.

Quello che ci interessa veramente però è il confronto fra i tempi di esecuzione dei programmi che realizzano gli altri tre metodi di stima, poiché, come già abbiamo osservato nell’Introduzione, questi si basano su operazioni eseguite su successioni simboliche e hanno pertanto un carattere essenzialmente diverso rispetto al calcolo dell’esponente di Lyapunov.

Il metodo che calcola le frequenze empiriche dei blocchi simbolici è fortemente influenzato dal valore h̃ che si usa nella relazione k(n) = ⌊\frac{1}{h̃} log_{2} n⌋ o nella relazione n(k) = ⌈2^{h̃k}⌉. L’implementazione del metodo richiede un numero di operazioni al passo k dell’ordine di n_{k}^{1/h̃}.

Se si usa il valore dell’entropia h̃ = h e si esegue l’algoritmo per valori di n equidistanziati, i tempi richiesti sono enormemente alti. Per esempio, se n_{k} = k · 10^{5}, k = 1, 2, …, 330, il numero di operazioni richieste (e quindi anche il tempo di esecuzione del programma) è proporzionale a ∑_{k=1}^{330}(k · 10^{5})^{1/h} ≈ 10^{5/h}330^{1/h+1}. Il tempo necessario ha quindi una crescita con legge di potenza con esponente pari a 1 piú l’inverso dell’entropia. Ciò rende l’algoritmo estremamente lento, ed esso è tanto piú inefficiente quanto piú piccola è l’entropia h della trasformazione, tanto da risultare inapplicabile in tempi ragionevoli per valori di h inferiori a circa 0, 9.

Abbiamo superato questa difficoltà eseguendo il calcolo per valori di n i cui logaritmi siano equidistanziati. In particolare abbiamo considerato k = 1, 2, …, 25 e n(k) = ⌈2^{h̃k}⌉, dove h̃ = h + 10^{−3} e h è il valore dell’entropia alla terza cifra decimale dato dalla stima dell’esponente di Lyapunov.

Gli algoritmi che implementano il metodo dei tempi di ritorno e quello delle sostituzioni di coppie di Grassberger sono decisamente piú efficienti. La loro esecuzione ha richiesto 5-6 minuti per il calcolo dei tempi di ritorno di 1000 blocchi simbolici e circa 3 minuti per effettuare 280 sostituzioni di coppie simboliche. In questi due algoritmi il numero di operazioni eseguite è lineare nella lunghezza della successione simbolica.

Le piccole variazioni registrate per il calcolo dei tempi di ritorno nei casi delle quattro trasformazioni sono imputabili al fatto che è talvolta necessario scorrere tutta la successione simbolica (quando il dato blocco simbolico non ricompare entro i 33 milioni di simboli) e talvolta no.

Per le sostituzioni di coppie, le piccole variazioni dei tempi di esecuzione sono da attribuirsi principalmente a due fattori. In primo luogo, ricordiamo che quando la sostituzione è del tipo xx → α, cioè quando si sostituiscono due simboli uguali, il programma stima la somma infinita nella (3.8) calcolando i primi ⌊log_{2} l(s)⌋ addendi, dove l(s) è la lunghezza del vettore simbolico dopo s sostituzioni di coppie (vedi sezione 5.2). A tal fine il programma scorre la successione simbolica ⌊log_{2} l(s)⌋ − 1 volte per determinare le frequenze empiriche dei blocchi di lunghezza i, per 2 ≤ i ≤ ⌊log_{2} l(s)⌋. Il secondo fattore che determina piccole differenze dei tempi di esecuzione del programma al variare della mappa considerata è il fatto che ogni sostituzione riduce la lunghezza della successione simbolica e ovviamente ciò avviene in misura diversa per mappe diverse.

Conclusioni

In questa tesi abbiamo studiato da un punto di vista teorico e computazionale un metodo di stima dell’entropia di processi simbolici e di sistemi dinamici ergodici.

Tale metodo si basa sul lavoro di Grassberger [Gr] e sui risultati ottenuti e formalizzati da Benedetto, Caglioti, Gabrielli in [BCG].

Il metodo di Grassberger (o metodo NSRPS, da Non-Sequential Recursive Pair Substitution) consiste nella sostituzione ricorsiva di coppie di simboli (le piú frequenti) con simboli singoli nuovi. Il risultato fondamentale, esposto nel teorema 3.4.1, asserisce che l’applicazione ripetuta della procedura di sostituzione trasforma, nel limite per il numero di sostituzioni che tende a infinito, ogni processo ergodico in un processo 1-markoviano.

Il nostro approfondimento teorico è consistito nello studio di un esempio molto particolare di processo (vedi sezione 3.5), proposto nell’articolo [BCG] dove gli autori elencano i risultati senza riportare i calcoli. Per il processo di tale esempio e per le sostituzioni di coppie considerate vale la conclusione del teorema 3.4.1 pur non valendone l’ipotesi, come abbiamo dimostrato nella sezione 3.5. In particolare, le sostituzioni considerate non sono relative a coppie di simboli tra quelle con probabilità massima. Ciò nonostante, il processo diventa ugualmente 1-markoviano nel limite per il numero di sostituzioni che tende a infinito, e anzi diventa addirittura indipendente (0-markoviano). Trovare condizioni sufficienti e necessarie sul processo e sulle sostituzioni affinché valga la tesi del teorema 3.4.1 resta una questione aperta, di soluzione apparentemente non semplice. Ciò nondimeno, ci sembra questa una delle piú interessanti direzioni da investigare per quanto riguarda il metodo NSRPS.

Guardando al metodo NSRPS da un punto di vista applicativo, il teorema centrale 3.4.1 suggerisce un algoritmo per la stima dell’entropia di processi simbolici ergodici, che abbiamo implementato per ottenere delle simulazioni al calcolatore nel caso di trasformazioni ergodiche dell’intervallo unitario (vedi capitolo 5). Per una valutazione del metodo di stima studiato, lo abbiamo confrontato con altri tre (vedi capitolo 4). Due di questi sono anch’essi applicabili nell’ambito della dinamica simbolica (vedi sezioni 4.1 e 4.2), mentre un altro è il calcolo dell’esponente di Lyapunov (vedi sezione 4.3) e presuppone la conoscenza esplicita della trasformazione considerata.

Dalle simulazioni realizzate al calcolatore (vedi capitolo 5) emerge che la stima dell’esponente di Lyapunov, ottenuta mediando la quantità log_{2} |T′| su un’orbita molto lunga, dà ottimi risultati sia in termini di approssimazione del valore dell’entropia sia in termini del tempo di esecuzione dell’algoritmo. In particolare, abbiamo osservato per tutte e quattro le trasformazioni considerate una notevole stabilizzazione del valore stimato. Nel caso della mappa logistica, tale valore di stima era perfettamente in accordo col valore vero dell’entropia, noto da argomentazioni teoriche. In virtú di tale precisione, il valore stimato dell’esponente di Lyapunov è stato preso come valore dell’entropia delle altre tre trasformazioni dell’intervallo [0, 1], per le quali il valore teorico dell’entropia non è noto.

Abbiamo altresí visto che cercare di stimare l’entropia calcolando le frequenze empiriche dei blocchi (vedi teorema 4.1.2) su stringhe simboliche di lunghezza crescente in modo lineare è un metodo assolutamente inefficiente in termini di tempo. Un’analisi dell’algoritmo ha mostrato che il numero di operazioni necessarie è estremamente alto e aumenta all’aumentare del blocco considerato seguendo una legge di potenza con esponente pari a 1+ \frac{1}{h} (vedi sezione 5.4). Abbiamo dovuto pertanto eseguire le stime in corrispondenza di valori crescenti in modo esponenziale (vedi sezione 5.4).

Oltre alla lentezza di tale algoritmo, abbiamo osservato che le stime ottenute con esso crescono in maniera estremamente lenta al crescere del blocco simbolico considerato, e per il numero di iterazioni che abbiamo considerato i valori massimi restano molto al di sotto del valore di riferimento.

Il metodo di stima dato dal calcolo dei tempi di ritorno di stringhe simboliche finite (vedi sezioni 4.2 e 5.2) ha dato, per tre delle quattro mappe considerate, risultati molto piú soddisfacenti rispetto al metodo delle frequenze empiriche in termini di approssimazione del valore di riferimento. Nel caso della mappa di Manneville M i risultati di approssimazione non sono buoni, e il motivo di ciò risiede nella particolarità della mappa e nella lunghezza non sufficiente dell’orbita campione considerata, come spiegato nella sezione 5.3.4. I tempi di esecuzione dell’algoritmo sono piuttosto contenuti (vedi sezione 5.4).

L’applicazione del metodo delle sostituzioni di coppie di Grassberger (NSRPS) ha dato ottimi risultati di approssimazione per tre delle quattro trasformazioni prese in esame. Come nel caso dei tempi di ritorno, risultati non soddisfacenti (anche se migliori rispetto ai metodi delle frequenze empiriche e dei tempi di ritorno) sono stati ottenuti per la mappa di Manneville (vedi sezione 5.3.4). Sempre come nel caso dei tempi di ritorno, anche il tempo di esecuzione dei programmi al calcolatore è stato decisamente contenuto (vedi sezione 5.4) e ciò fa sí che il metodo NSRPS sia interessante anche da un punto di vista applicativo computazionale.

Il metodo delle sostituzioni di coppie simboliche si è dimostrato, nelle simulazioni eseguite, un valido strumento di stima dell’entropia per alcune trasformazioni ergodiche dell’intervallo. Nel confronto con gli altri due metodi di stima basati sulle successioni simboliche, esso è risultato piú accurato ed efficiente nell’approssimazione del valore di riferimento e nel tempo di esecuzione dell’algoritmo.

Avendo preso sempre come valore di riferimento per l’entropia quello dato dalla stima dell’esponente di Lyapunov, che converge velocemente e in maniera molto precisa, ci si potrebbe chiedere quale importanza possa rivestire la stima mediante il metodo di Grassberger. Se esso infatti semplicemente ‘approssima’ il valore che si ottiene stimando l’esponente di Lyapunov, non è forse conveniente utilizzare sempre quest’ultimo metodo? La risposta l’avevamo già accennata nell’Introduzione. Il calcolo o la stima dell’esponente di Lyapunov presuppongono che si sia in presenza di una trasformazione di qualche intervallo e che essa sia nota esplicitamente. Poiché gli altri tre metodi di stima -e in particolare quello di Grassberger- agiscono invece soltanto su processi simbolici, possono essere applicati ad una classe di casi piú ampia. Non di poca importanza a fini applicativi sono tutti quei casi in cui la sorgente non è nota e si rilevano empiricamente successioni simboliche.

Sopra abbiamo individuato un’interessante direzione di indagine riguardo agli aspetti teorici delle sostituzioni ricorsive di coppie simboliche. Un’altra direzione di studio, questa interessante soprattutto a fini applicativi e altrettanto importante, ci sembra essere quella della determinazione del numero piú opportuno di sostituzioni da eseguire a seconda del particolare processo in esame.

Appendice A

Risultati tecnici sul metodo NSRPS

Riportiamo in questa appendice le dimostrazioni dei risultati che abbiamo solo enunciato o di cui ci siamo serviti nel capitolo 3. Seguiamo [BCG] e nel corso di tutta l’appendice indicheremo con log il logaritmo in base 2.

A.1 Trasformazioni delle misure

Dimostrazione del teorema 3.2.2

Si fornisce qui di seguito una dimostrazione informale.

Il fatto che i limiti siano costanti quasi ovunque segue dalla legge forte dei grandi numeri. Ciò implica l’ergodicità di Gμ e di Sν (vedi teorema I.4.2 pag. 44 di [Sh]). Le condizioni di compatibilità per le famiglie dei marginali si verificano facilmente. La formula (3.6) è conseguenza della (3.3).

Dimostrazione della proposizione 3.2.3

Nel caso x ≠ y si ha

|G(w_{1}^{n})| = n − #{xy ⊆ w_{1}^{n}}

cosí che

\frac{n}{|G(w_{1}^{n})|} = \frac{1}{1 − \frac{#\{xy⊆w_{1}^{n}\}}{n}}

e la (3.7) segue dalla legge forte dei grandi numeri. Nel caso x = y si ha

|G(w_{1}^{n})| = n − ∑_{k=2}^{n} #\{∗x^{k}∗ ⊆ w_{1}^{n}\} [\frac{k}{2}] ,

dove [·] denota la parte intera e #{∗x^{k}∗ ⊆ w_{1}^{n}} è il numero dei blocchi di esattamente k simboli x consecutivi contenuti in w_{1}^{n} (∗ rappresenta una possibile occorrenza di una lettera generica diversa da x). Vale

#{∗x^{k}∗ ⊆ w_{1}^{n}} = #{x^{k} ⊆ w_{1}^{n}} − 2#{x^{k+1} ⊆ w_{1}^{n}} + #{x^{k+2} ⊆ w_{1}^{n}}.

Ora, si ha

\frac{n}{|G(w_{1}^{n})|} = \frac{1}{1 − ∑_{k=2}^{n}(−1)^{k} (\frac{#\{x^{k}⊆w_{1}^{n}\}}{n})},

che converge al membro di destra della (3.8) per ogni misura ergodica μ diversa dalla misura concentrata sulla successione di tutti x (in tal caso, chiaramente Z = 2).

La formula (3.9) segue da

S(z_{1}^{n}) = n + #{α ⊆ z_{1}^{n}}

e dalla legge forte dei grandi numeri.

La formula (3.10) si deduce dalla (3.3).

Sν in termini di ν

Si consideri la sostituzione α → xy. Si ha che

W = lim_{n→∞} \frac{|S(z_{1}^{n})|}{n} = lim_{n→∞} ∑_{|\underline{z}|=n} ν(\underline{z})\frac{|S(\underline{z})|}{n},

e vale

Sν(\underline{r}) =^{def} lim_{n→∞} \frac{#\{\underline{r} ⊆ S(z_{1}^{n})\}}{|S(z_{1}^{n})|} = lim_{n→∞} \frac{#\{\underline{r} ⊆ S(z_{1}^{n})\}}{W n}

= lim_{n→∞} \frac{1}{W n} ∑_{|\underline{z}|=n} ν(\underline{z})#\{\underline{r} ⊆ S(z_{1}^{n})\}.

(A.1)

Si supponga ora |\underline{r}| = k e si consideri, per n ≥ k,

\begin{aligned}D_{n} & = ∑_{|\underline{z}|=n} ν(\underline{z})#\{\underline{r} ⊆ S(\underline{z})\} − ∑_{|\underline{z}|=n−1} ν(\underline{z}) \\ & = ∑_{|\underline{z}|=n} ν(\underline{z})𝟙(\underline{r} = S(\underline{z})_{1}^{k}) + ∑_{|\underline{z}|=n−1} ν(α\underline{z})𝟙(\underline{r} = yS(\underline{z})_{1}^{k−1}). \end{aligned}  (A.2)

I due termini di questa somma possono essere riscritti come

∑_{|\underline{z}|=n} ν(\underline{z})𝟙(\underline{r} = S(\underline{z})_{1}^{k}) = ∑_{\underline{s}:S(\underline{s})=\underline{r}} (ν(\underline{s}) + ν(s_{1}^{|\underline{s}|−1}α)𝟙(r_{k} = x))  (A.3)

e

\begin{matrix}∑_{|\underline{z}|=n−1} ν(α\underline{z}) & 𝟙(\underline{r} = yS(\underline{z})_{1}^{k−1}) = \\ = ∑_{\underline{s}:S(\underline{s})=\underline{r}} (ν(αs_{2}^{|\underline{s}|}) + ν(αs_{2}^{|\underline{s}|−1}α)𝟙(r_{k} = x)) 𝟙(r_{1} = y). \end{matrix} (A.4)

Pertanto D_{n} è costante per n ≥ k e

lim_{n→∞} \frac{1}{W} ∑_{|\underline{z}|=n} ν(\underline{z})#\{\underline{r} ⊆ S(z_{1}^{n})\} = \frac{1}{W} D_{k}.  (A.5)

Mettendo insieme le (A.1)÷(A.5), si ottiene l’espressione per Sν:

\begin{aligned}Sν(\underline{r}) & = \frac{1}{W} ∑_{\underline{s}:S(\underline{s})=\underline{r}} (ν(\underline{s}) + ν(s_{1}^{|\underline{s}|−1}α)𝟙(r_{k} = x) + ν(αs_{2}^{|\underline{s}|})𝟙(r_{1} = y) \\ & + ν(αs_{2}^{|\underline{s}|−1}α)𝟙(r_{1} = y)𝟙(r_{k} = x)) . \end{aligned} (A.6)

Gμ in termini di μ

Poiché la mappa S inverte G, per trovare l’espressione di Gμ si può invertire l’espressione di SGμ = μ. Sia ν la misura Gμ.

La somma su \underline{s} nell’equazione (A.6) si riduce a \underline{s} = G(\underline{r}), cioè ν(\underline{s}) = 0 se \underline{s} ∉ G(A^{∗}). Questa riduzione rende esplicitamente invertibile la (A.6), ma bisogna distinguere i casi x ≠ y e x = y.

Caso x ≠ y Sia \underline{r} ∈ A^{∗} e siano z, w ∈ A tali che z ≠ x e w ≠ y. Dalla (A.6) si ottiene:

\begin{matrix}W μ(w\underline{r}z) = ν(G(w\underline{r}z)) \\ W μ(w\underline{r}x) = ν(G(w\underline{r})x) + ν(G(w\underline{r})α) \\ W μ(y\underline{r}z) = ν(yG(\underline{r}z)) + ν(αG(\underline{r}z)) \\ W μ(y\underline{r}x) = ν(yG(\underline{r})x) + ν(αG(\underline{r})x) + ν(yG(\underline{r})α) + ν(αG(\underline{r})α). \end{matrix} (A.7)

Sia ora \underline{s} = G(\underline{r}) con |\underline{s}| = n e |\underline{r}| = k. L’espressione di ν(\underline{s}) = Gμ(\underline{s}) può essere calcolata dalle equazioni (A.7), ottenendo

\begin{matrix}s_{1} ≠ y, s_{n} ≠ x, & ν(\underline{s}) = W μ(\underline{r}) \\ s_{1} = y, s_{n} ≠ x, & ν(\underline{s}) = W (μ(\underline{r}) − μ(xyr_{2}^{k})) \\ s_{1} ≠ y, s_{n} = x, & ν(\underline{s}) = W (μ(\underline{r}) − μ(r_{1}^{k−1}xy)) \\ s_{1} = y, s_{n} = x, & ν(\underline{s}) = W (μ(\underline{r}) + μ(xyr_{2}^{k−1}xy) − μ(xyr_{2}^{k}) − μ(r_{1}^{k−1}xy)). \end{matrix} ; (A.8)

Ora si può calcolare Z = W (cfr. equazione (3.10)) in termini di μ:

Z = 1 + ν(α) = 1 + Zμ(xy) = \frac{1}{1 − μ(xy)}.  (A.9)

Si osservi infine che le equazioni (A.8) possono essere sintetizzate in

Gμ(\underline{s}) = Z ∑_{a,b∈A:a\underline{s}b∈G(A^{∗})} μ(a\underline{s}b).  (A.10)

Caso x = y Procedendo come prima si ottendono espressioni esplicite per ν(\underline{s}), le quali però sono piú complicate. Come prima, sia \underline{s} ∈ G(A^{∗}), |\underline{s}| = n > 0, G(\underline{r}) = \underline{s}, |\underline{r}| = k. Siano s_{1}, s_{n} ≠ x. Indicando con \underline{a}^{p} la stringa costituita da p simboli a consecutivi, le stringhe in G(A^{∗}) sono del tipo

\underline{α}^{p}\underline{x}^{π}\underline{s}\underline{α}^{q}\underline{x}^{σ} e \underline{α}^{p}\underline{x}^{π}, con p, q ≥ 0 e π, σ = 0, 1.

L’espressione di Gμ = ν in termini di μ è data da:

ν(\underline{s}\underline{α}^{q}) = Zμ(\underline{r}\underline{x}^{2q})  per q ≥ 0
ν(\underline{s}\underline{α}^{q}x) = Z(μ(\underline{r}\underline{x}^{2q+1}) − μ(\underline{r}\underline{x}^{2q+2}))  per q ≥ 0
ν(\underline{α}^{p}) = Z ∑_{j=0}^{∞}(−1)^{j}μ(\underline{x}^{2p+j})  per p ≥ 1
ν(\underline{α}^{p}\underline{x}) = Z(μ(\underline{x}^{2p+1}) − 2 ∑_{j=2}^{∞}(−1)^{j}μ(\underline{x}^{2p+j})) per p ≥ 1
ν(\underline{α}^{p}\underline{x}^{π}\underline{s}\underline{α}^{q}) = Z ∑_{j=0}^{∞}(−1)^{j}μ(\underline{x}^{2p+π+j}\underline{r}\underline{x}^{2q})  per p + π ≥ 1, q ≥ 0
ν(\underline{α}^{p}\underline{x}^{π}\underline{s}\underline{α}^{q}x) = Z ∑_{j=0}^{∞}(−1)^{j}·
(μ(\underline{x}^{2p+π+j}\underline{r}\underline{x}^{2q+1}) − μ(\underline{x}^{2p+π+j}\underline{r}\underline{x}^{2q+2})) per p + π ≥ 1, q ≥ 0

(A.11)

Ora è possibile calcolare Z in termini di μ:

Z = 1 + ν(α) = 1 + Z ∑_{j=0}^{∞}(−1)^{j}μ(\underline{x}^{2+j}) = \frac{1}{1 − ∑_{j=2}^{∞}(−1)^{j}μ(\underline{x}^{j})}. (A.12)

Dimostrazione della proposizione 3.2.4

Questa proposizione è una conseguenza dell’equazione (A.6), cioè |\underline{s}| ≤ |\underline{r}| se S(\underline{s}) = \underline{r}.

Dimostrazione della proposizione 3.2.5

Questa proposizione è una conseguenza del fatto che l’espressione esplicita (A.6) di μ = Sν in termini di ν può essere invertita (in modo unico) se ν rispetta i vincoli di coppia dati da G, come segue dalle equazioni (A.7)÷(A.11). L’espressione di ν in termini di μ è esattamente Gμ, e allora ν = Gμ = GSν.

A.2 Trasformazioni delle entropie

Dimostrazione del teorema 3.3.1

Il teorema segue dal fatto che G è un codice fedele e S è un codice fedele se ristretto al supporto di Gμ. Si indichi con C = {C_{n}}_{n∈ℕ} una successione di codici universali nell’alfabeto A e C′ = {C′_{n}}_{n∈ℕ} una successione di codici universali nell’alfabeto A′ (si vedano i teoremi II.1.1 e II.1.2, pag. 122 di [Sh]). La composizione C′ ∘ G è una successione di codici fedeli in A. Da ciò si deduce che su un insieme di misura uno secondo μ vale

h(Gμ) = lim_{n→∞} \frac{C′_{|G(w_{1}^{n})|}(G(w_{1}^{n}))}{|G(w_{1}^{n})|} = lim_{n→∞} \frac{n}{|G(w_{1}^{n})|} \frac{C′_{|G(w_{1}^{n})|} ∘ G(w_{1}^{n})}{n} ≥ Zh_{1}(μ).

(A.13)

Similmente, anche C ∘ S è una successione di codici fedeli in A′. Da ciò si deduce che su un insieme di misura uno secondo μ vale

h(μ) = lim_{n→∞} \frac{C_{n}(w_{1}^{n})}{n} = lim_{n→∞} \frac{|G(w_{1}^{n})|}{n} \frac{C_{n} ∘ S(G(w_{1}^{n}))}{|G(w_{1}^{n})|} ≥ \frac{h(Gμ)}{Z}. (A.14)

Dimostrazioni dei teoremi 3.3.2 e 3.3.3

Nel corso di queste dimostrazioni, l’azione di G (e quindi di G) verrà divisa in tre parti, mediante l’introduzione di due nuovi simboli b1, b2 ∉ A. Data una stringa:

passo 1: si sostituirà, partendo dalla sinistra, ogni occorrenza di xy con xb_{1}. Questa operazione definisce una mappa R : A^{∗} → A_{R}^{∗}, dove A_{R} = A ∪ {b_{1}}. Si indicherà con R la corrispondente mappe tra le misure, definita con lo stesso spirito del teorema 3.2.2;

passo 2: si sostituirà ogni occorrenza di xb_{1} con b_{2}b_{1}. Questa operazione definisce una mappa L : A_{R}^{∗} → A_{L}^{∗}, dove A_{L} = A_{R} ∪ {b_{2}}. Si indicherà con L la corrispondente mappe tra le misure;

passo 3: si sostituirà ogni occorrenza di b_{2}b_{1} con α. Questa operazione definisce una mappa C : A_{L}^{∗} → A_{C}^{∗}, dove A_{C} = A_{L} ∪ {α}. Si indicherà con C la corrispondente mappe tra le misure.

Da queste definizioni si ha

C(L(R(\underline{w}))) = G(\underline{w}), e quindi CLRμ = Gμ.

Per mezzo di questa fattorizzazione di G, vengono separati gli effetti dell’accorciamento delle stringhe (passo 3) dall’effetto delle sostituzioni parziali dei simboli (passi 1 e 2).

Lemma A.2.1.

h_{1}(Rμ) ≤ h_{1}(μ)  (A.15)

La dimostrazione del lemma si trova poco oltre.

La medesima disuguaglianza vale anche per LRμ. Infatti, si può definire L anche considerando le sostituzioni iniziando da destra, con x ≠ b_{1}. Cosí, L(\underline{w}) = (R′(\underline{w}^{r}))^{r}, dove \underline{w}^{r} = (w_{1} … w_{k})^{r} = w_{k} … w_{1} e R′ è la sostituzione, da sinistra, di b_{1}x con b_{1}b_{2}. La mappa R′ agisce nello stesso modo di R, e quindi il lemma A.2.1 vale per la corrispondente mappa tra le misure R′, e quindi anche per L. In questo modo si prova che

h_{1}(LRμ) ≤ h_{1}(μ).

Il terzo passo lascia invariata h_{1}, a meno della normalizzazione, come asserito nel seguente lemma (la dimostrazione si trova poco piú giú).

Lemma A.2.2. Se ρ ∈ E(A_{L}) soddisfa

ρ(b_{2}w) = ρ(zb_{1}) = 0 per w ≠ b_{1}, z ≠ b_{2},  (A.16)

allora

h_{1}(Cρ) = W h_{1}(ρ),  (A.17)

dove

W = \frac{1}{1 − ρ(b_{2}b_{1})} = 1 + Cρ(α).  (A.18)

La dimostrazione del teorema 3.3.2 si conclude osservando che la misura ρ = LRμ verifica le condizioni (A.16), per cui h_{1}(Gμ) ≤ W h_{1}(μ), dove W = Z perché W = 1 + Cρ(α) = 1 + Gμ(α) = W_{α}^{Gμ} = Z_{xy}^{μ} (cfr. equazione (3.10)).

Per dimostrare il teorema 3.3.3 è sufficiente osservare che il lemma A.2.1 vale anche per h_{k} e che per h_{k} vale il seguente analogo del lemma A.2.2, che sarà dimostrato piú giú.

Lemma A.2.3. Sotto le medesime ipotesi del lemma A.2.2, vale

h_{k}(Cρ) = W h_{k}(ρ).  (A.19)

Dimostrazione del lemma A.2.1

Sia ξ = Rμ. La misura μ può essere espressa in termini di ξ nel modo seguente:

μ(\underline{w}) = ∑_{\underline{z}:R(\underline{z})=\underline{w}} ξ(\underline{w}).

Questa formula verrà usata ora per esprimere le probabilità dei simboli e delle coppie di simboli.

Caso x ≠ y Sia p ∈ A:

μ(y) = ξ(y) + ξ(b_{1}),  μ(p) = ξ(p) per p ≠ y,
μ(yp) = ξ(yp) + ξ(b_{1}p), μ(pq) = ξ(pq) per p ≠ x, p ≠ y
μ(xy) = ξ(xb_{1}),  μ(xp) = ξ(xp) per p ≠ y.

Da un calcolo diretto segue

h_{1}(μ) − h_{1}(ξ) = − sup_{p∈A}(ξ(yp) + ξ(b_{1}p)) log \frac{ξ(yp) + ξ(b_{1}p)}{ξ(y) + ξ(b_{1})}

+ ∑_{p∈A} (ξ(yp) log \frac{ξ(yp)}{ξ(y)} + ξ(b_{1}p) log \frac{ξ(b_{1}p)}{ξ(b_{1})}) .

(A.20)

Il lemma sarà provato dimostrando che vale

(ξ(yp) log \frac{ξ(yp)}{ξ(y)} + ξ(b_{1}p) log \frac{ξ(b_{1}p)}{ξ(b_{1})}) ≥ (ξ(yp) + ξ(b_{1}p)) log \frac{ξ(yp) + ξ(b_{1}p)}{ξ(y) + ξ(b_{1})}.

Dividendo per ξ(yp)+ξ(b_{1}p) e ponendo β = \frac{ξ(y)}{ξ(y)+ξ(b_{1})}, γ = \frac{ξ(yp)}{ξ(yp)+ξ(b_{1}p)}, l’ultima disuguaglianza si può riscrivere come

γ log \frac{β}{γ} + (1 − γ) log \frac{1 − β}{1 − γ} ≤ 0,

che è sempre verificata.

Caso x = y Sia p ∈ A, p ∉ x... p ∈ A, p ∉ x:

\begin{matrix}μ(x) = ξ(x) + ξ(b_{1}), & μ(p) = ξ(p), \\ μ(xx) = ξ(xb_{1}) + ξ(b_{1}x), & μ(xp) = ξ(xp) + ξ(b_{1}p), \\ μ(pq) = ξ(pq) per q ∈ A, & μ(px) = ξ(px). \end{matrix}

La differenza tra le entropie condizionate di ordine 1 è

h_{1}(μ) − h_{1}(ξ) = − ∑_{{p∈A \atop p≠x}}(ξ(xp) + ξ(b_{1}p)) log \frac{ξ(xp) + ξ(b_{1}p)}{ξ(x) + ξ(b_{1})}

− (ξ(xb_{1}) + ξ(b_{1}x)) log \frac{ξ(xb_{1}) + ξ(b_{1}x)}{ξ(x) + ξ(b_{1})}

+ ∑_{{p∈A \atop p≠x}} (ξ(xp) log \frac{ξ(xp)}{ξ(x)} + ξ(b_{1}p) log \frac{ξ(b_{1}p)}{ξ(b_{1})})

+ ξ(xb_{1}) log \frac{ξ(xb_{1})}{ξ(x)} + ξ(b_{1}x) log \frac{ξ(b_{1}x)}{ξ(b_{1})}.

Il fatto che tale differenza sia positiva si dimostra argomentando come nel caso x ≠ y.

Si osservi infine che nella medesima maniera si può dimostrare che h_{k}(ξ) ≤ h_{k}(μ).

Dimostrazione del lemma A.2.2

Siano ν = Cρ e W = 1 + ν(α). È facile scrivere ρ in termini di ν. Siano p, q ≠ b_{1}, b_{2}. Le probabilità dei simboli e delle coppie di simboli sono date da:

\begin{matrix}W ρ(b_{1}) = W ρ(b_{2}) = ν(α) & W ρ(p) = ν(p) \\ W ρ(pb_{1}) = W ρ(b_{2}q) = 0 & W ρ(pq) = ν(pq) \\ W ρ(pb_{2}) = ν(pα) & W ρ(b_{1}q) = ν(αq) \\ W ρ(b_{2}b_{1}) = ν(α) & W ρ(b_{1}b_{2}) = ν(αα). \end{matrix}

Tramite calcolo diretto si trova:

H_{1}(ρ) = − ∑_{p∈A_{C}\α} \frac{ν(p)}{W} log \frac{ν(p)}{W} − 2\frac{ν(α)}{W} log \frac{ν(α)}{W}

= \frac{H_{1}(ν)}{W} + \frac{log W}{W} − \frac{ν(α)}{W} log \frac{ν(α)}{W},

H_{2}(ρ) = − ∑_{p,q∈A_{C}} \frac{ν(pq)}{W} log \frac{ν(pq)}{W} − \frac{ν(α)}{W} log \frac{ν(α)}{W}

= \frac{H_{2}(ν)}{W} + \frac{log W}{W} − \frac{ν(α)}{W} log \frac{ν(α)}{W}.

Pertanto,

h_{1}(ρ) = H_{2}(ρ) − H_{1}(ρ) = \frac{h_{1}(ν)}{W}.

Dimostrazione del lemma A.2.3

Prima di tutto, ecco alcune definizioni. Sia \underline{w} = w_{1}^{l}. Si può identificare \underline{w} con il sottoinsieme cilindrico K\underline{w} ⊆ A^{ℤ} definito da

K\underline{w} = \{\underline{x} ∈ A^{ℤ} : z_{−l} = w_{1}, x_{−l+1} = w_{2}, …, x_{−1} = w_{l}\}.

Sia P ⊆ A^{∗} un insieme finito. Si dice che P è una partizione se

\{K\underline{w}\}_{\underline{w}∈P} è una partizione di A^{ℤ}, cioè \{ \begin{matrix}(1) & K\underline{w} ∩ K\underline{z} = ∅ se \underline{w} ≠ \underline{z}, \\ (2) & ⋃_{\underline{w}∈P} K\underline{w} = A^{ℤ} \end{matrix}

La condizione (1) dice che nessuna stringa di P è un suffisso di un’altra stringa di P. Se solo la condizione (1) è verificata, P è detta una semi-partizione. Si vede facilmente che ogni semi-partizione si può completare per ottenere una partizione. Inoltre, se il minimo delle lunghezze delle stringhe in P è l, si può completare P usando stringhe di lunghezza maggiore di o uguale a l.

Se P è una partizione, si definisce l’entropia P -condizionata come

h_{P} (μ) = − ∑_{{\underline{w}∈P \atop a∈A}} μ(\underline{w}a) log \frac{μ(\underline{w}a)}{μ(\underline{w})}.

Se P e Q sono due partizioni, si dice che P è piú fine di Q se ogni stringa di P termina con una stringa di Q. Se P è piú fine di Q, allora vale la formula (la dimostrazione è alla fine della sezione)

h_{P} (μ) ≤ h_{Q}(μ).  (A.21)

Si noti che

P = \{\underline{s} ∈ A_{L}^{∗}||C(\underline{s})| = k\}

è una semi-partizione, e che mediante calcolo diretto si ottiene

h_{k}(ν) = W h_{P} (ρ),

dove ν = Cρ. In particolare, si è usato che se \underline{s} ∈ A_{L}^{∗} allora ρ(\underline{s}b_{2}) = ρ(\underline{s}b_{2}b_{1}) e che se l’ultimo simbolo di \underline{s} è diverso da b_{2} allora ρ(\underline{s}b_{1}) = 0. Sia infine \overline{P} un completamento di P; allora

h_{k}(ν) = W h_{P} (ρ) ≤ W h\overline{P} (ρ).

La lunghezza delle stringhe in P è maggiore di o uguale a k e si può costruire \overline{P} in modo che lo stesso valga per \overline{P}. Per la (A.21) si ha in conclusione che

h_{k}(ν) ≤ W h_{A_{L}^{k}}(ρ) = W h_{k}(ρ).

Dimostrazione della disuguaglianza (A.21)

Sia \underline{w} ∈ Q e sia X\underline{w} ⊆ P il sottoinsieme delle stringhe che terminano con \underline{w}. Da questa definizione:

P = ⋃_{\underline{w}∈Q} X\underline{w}, μ(\underline{w}) = ∑_{\underline{r}∈X\underline{w}} μ(\underline{r}).

La funzione Φ(x) = x log x è convessa, allora se λ_{i} ≥ 0 e ∑ λ_{i} = 1, si ha Φ(∑ λ_{i}x_{i}) ≤ ∑ λ_{i}x_{i} log x_{i}. Ora,

−h_{Q}(μ) = ∑_{\underline{w}∈Q} μ(\underline{w}) ∑_{a∈A} μ(a|\underline{w}) log μ(a|\underline{w}),

e

μ(a|\underline{w}) = \frac{μ(\underline{w}a)}{μ(\underline{w})} = ∑_{\underline{r}∈X\underline{w}} \frac{μ(\underline{r}a)}{μ(\underline{w})} = ∑_{\underline{r}∈X\underline{w}} \frac{μ(\underline{r}a)}{μ(\underline{r})} \frac{μ(\underline{r})}{μ(\underline{w})}.

Indicando con xa ; \underline{r} = μ(\underline{r}a)/μ(\underline{r}) e con λ\underline{r} = μ(\underline{r})/μ(\underline{w}) e osservando che ∑_{\underline{r}∈X\underline{w}} λ\underline{r} = 1, si ottiene

−h_{Q}(μ) = ∑_{\underline{w}∈Q} ∑_{a∈A} μ(\underline{w})Φ( ∑_{\underline{r}∈X\underline{w}} λ\underline{r}xa ; \underline{r})

≤ ∑_{\underline{w}∈Q} ∑_{\underline{r}∈X\underline{w}} ∑_{a∈A} μ(\underline{w})\frac{μ(\underline{r})}{μ(\underline{w})}μ(a|\underline{r}) log μ(a|\underline{r})
= ∑_{\underline{r}∈P} ∑_{a∈A} μ(\underline{r})μ(a|\underline{r}) log μ(a|\underline{r}) = −h_{P} (μ).

Bibliografia

[Ab] M. Abate, Sistemi Dinamici Discreti, dispense del corso tenuto presso l’Università di Pisa nell’A.A. 2005-2006. Su Inter-

net in http://www.dm.unipi.it/~abate/matdid/dispense/ (22

novembre 2007).

[BCG] D. Benedetto, E. Caglioti, D. Gabrielli, Non sequential recursive pair substitution: some rigorous results, Journal of Statistical Mechanics (2006) P09011.

[Bil] P. Billingsley, Probability and measure, Wiley, New York, 1979.

[Bir] G. D. Birkhoff, Proof ot the ergodic theorem, Proceedings of the National Academy of Sciences USA 17 (1931), 656-660.

[Br] L. Breiman, Probability theory, Addison-Wesley, Reading, MA, 1968.

[Bu] J. Buzzi, A minicourse on entropy theory on the interval,

arXiv:math/0611337v1 [math.DS], 2006.

[Ch] G. H. Choe, Computational ergodic theory, Springer-Verlag, Berlin, 2005.

[EJM] W. Ebeling, M. A. Jiménez-Montaño, On grammars, complexity, and information measures of biological macromolecules, Mathematical Biosciences 52 (1980), 53-71. M. A. Jiménez-Montaño, On the syntactic structure of protein sequences and the concept of grammar complexity, Bulletin of Mathematical Biology 42 (1984), 641-659. M. A. Jiménez-Montaño, W. Ebeling, T. Pöschel, SYNTAX: a computer program to compress a sequence and to estimate its information

content, arXiv:cond-mat/0204134, 2002.

P. E. Rapp, I. D. Zimmermann, E. P. Vining, N. Cohen, A. M. Albano, M. A. Jiménez-Montaño, Tha algoritmic complexity of neural spike trains increases during focal seizures, The Journal of Neuroscience 14 (1994), 4731-4739.

[Fe] W. Feller, An introduction to probability theory and its applications (vol. I, 3a ediz.), Wiley, New York, 1968.

[Gr] P. Grassberger, Data compression and entropy estimates by nonsequential recursive pair substitution, arXiv:physics/0207023, 2002.

[Is] S. Isola, On systems with finite ergodic degree, Far East Journal of Dynamical Systems 5 (2003), 1-62.

[KH] A. Katok, B. Hasselblatt, Introduction to the modern theory of dynamical systems, Cambridge University Press, 1995.

[Kh] A. Ya. Khintchine, Mathematical Foundations of Information Theory, Dover, New York, 1957.

[Ko] A. N. Kolmogorov, A new metric invariant of transitive dynamical systems and automorphisms of Lebesgue spaces, Doklady Akademii Nauk SSSR 119 (1958), 861-864. (In russo.)

[Kr] W. Krieger, On entropy and generators of measure-preserving transformations, Transactions of the American Mathematical Society 149 (1970), 453-464.

[Ma] R. Mañé, Ergodic theory and differentiable dynamics, Springer-Verlag, Berlin, 1987.

[OW] D. Ornstein, B. Weiss, How sampling reveals a process, The Annals of Probability 18 (1990), 905-930.

[Pa] W. Parry, Entropy and generators in ergodic theory, Benjamin, New York, 1969.

[Pe] K. Petersen, Ergodic theory, Cambridge University Press, 1983.

[PM] Y. Pomeau, P. Manneville, Intermittent transition to turbulence in dissipative dynamical systems, Communications in Mathematical Physics 74 (1980), 189-197.

[Sh] P. C. Shields, The ergodic theory of discrete sample paths, American Mathematical Society, 1996.

[Si] Ya. G. Sinai, On the notion of entropy of a dynamical system, Doklady Akademii Nauk SSSR 124 (1959), 768-771. (In russo.)

[Th] M. Thaler, Estimates of the invariant densities of endomorphisms with indifferent fixed points, Israel Journal of Mathematics 37 (1980), 303-314.

[Vi] M. Viana, Stochastic dynamics of deterministic systems, Lecture Notes XXI Brazilian Mathematics Colloquium, Instituto de Matemática Pura e Aplicada, Rio de Janeiro, 1997. Su Internet in

http://www.impa.br/~viana/ (22 novembre 2007).

[Wa1] P. Walters, An introduction to ergodic theory, Springer-Verlag, New York, 1982.

[Wa2] P. Walters, Invariant measures and equilibrium states for some mappings which expand distances, Transactions of the American Mathematical Society 236 (1978), 121-153.

[WZ] A. D. Wyner, J. Ziv, Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression, IEEE Transactions on Information Theory 35 (6) (1989), 1250-1258.