Introduzione ai processi di Markov

Introduzione ai processi di Markov
maggio 2014
Sommario
La cinematica o la dinamica di una variabile aleatoria prende il nome di processo stocastico.
• E Marinari G Parisi
Trattatello di probabilit`a
marzo 2002
• Sokal Monte Carlo Methods etc.
(1996)
Indice
1 Processi stocastici
1.1 processo markoviano, discreto . . . . . . . . . . . .
1.1.1 matrice di Markov . . . . . . . . . . . . . .
1.1.2 evoluzione misure e distribuzione stazionaria
1.1.3 teorema di Frobenius-Perron . . . . . . . .
1.1.4 reversibilit`a e bilancio dettagliato . . . . . .
1.2 RV funzioni della traiettoria . . . . . . . . . . . . .
1.2.1 serie temporali . . . . . . . . . . . . . . . .
1.3 grandezze fondamentali . . . . . . . . . . . . . . . .
1.3.1 shema conti e commenti . . . . . . . . . . .
1.3.2 algebra dell‘evoluzione . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
4
4
5
6
7
7
8
11
13
15
2 Processi di Markov non discreti
16
2.1 |Ω| → ∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1 transizione fase . . . . . . . . . . . . . . . . . . . . . . 18
2.2 ∆t → 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 simulazioni Monte Carlo
19
1
Capitolo 1
Processi stocastici
La cinematica (la dinamica) di una variabile stocastica `e detta processo stocastico
Fissato un intervallo [0, T ] e uno spazio di probabilit`a Ω, (con sua algebra e
possibili misure di probabilit`a)
un processo stocastico `e la famiglia delle variabili aleatorie
{ω(t) t ∈ [0, T ],
ω(t) ∈ Ω}
ATT! le variabili aleatorie sono le traiettorie, le storie: Il punto essenziale,
che dovete aver sempre in mente, consiste nel fatto che il processo stocastico `e dato dalla probabilit`a della ‘storia‘ t → ω(t) e non dalle probabilit`a
(marginali) del valore assunto dalla variabile aleatoria in un certo istante
Se l‘intervallo `e formato da N punti discreti
[0, T ] ≡ {0, t1 , t2 , · · · , tj , · · · , tN −1 = T , il processo stocastico `e definito dalla
probabilit`a congiunta
p(ω(0), ω(t1), · · · , ω(T )) cio`e da una probabilit`a definita su ΩN
Se l‘intervallo `e continunuo il processo `e determinato dalla famiglia di probabilit`a congiunte definite
1) per ogni N
2) ed ogni set {t1 , t2 , · · · , tN } :
cio`e processo stocastico `e dato dall‘insieme delle probabilit`a congiunte
∀N, ∀{t1 , t2 , · · · , tN } ⇒ p(ω(t1 ), · · · , ω(tN ))
(Questo insieme nasce dal problema di definire cosa `e misurabile in spazi
infinito dimensionali tipo C 0 [0, T ] , vedi insiemi cilindrici )
2
Sono necessarie ulteriori precisazioni in base alla natura dello spazio Ω ma
per ora ci basta e ci `e utile pensare che Ω sia un insieme discreto
esempi.........................
• Le storie di N lanci di moneta definiscono un processo stocastico.
Se chiamo testa, croce ω = {0, 1} e p(ω) = pω (1 − p)1−ω Q
la probabilit`a
associata alla traiettoria,P
alla storia {ω(0), ω(t1), · · · , ω(T )) `e i p(ω(ti ))
La famiglia t → X(t) = ti ≤t ω(ti ) ( somma totale vinta/ persa in t tiri) `e
un processo stocastico a salti indipendenti (senza memoria)
• La storie di lunghezza N di un‘urna di Polia `e un processo stocastico.
Se la condizione iniziale dell‘urna `e data da w palline bianche (ω = 1) e r
palline rosse (ω = 0), la probabilit`a associata alla traiettoria {ω(0), ω(t1), · · · , ω(T )),
condizionata a ..., risulta
p({ω|
X
j=1,N
ωi = B}) =
(b + w)! b−1
x (1 − x)w−1
b! w!
(vedi appunti probabilit`a)
P
In questo caso il processo t → X(t) =
ti ≤t ω(ti ) ha memoria (nota che
il salto al tempo t `e condizionato dal risultato totale ottenuto fino a quel
momento).
• Il moto browniano `e un processo stocastico
..........................
3
1.1
processo markoviano, discreto
Consideriamo il caso di intervallo [0, T ] ≡ {0, t1 , t2 , · · · , tj , · · · , tN −1 = T }
discreto e spazio degli eventi Ω discreto.
Mi pare che questa situazione sia ottimale per focalizzare le idee fondamentali
della teoria.
Possiamo assumere che ti − ti−1 = ∆t sia costante.
La probabilit`a p(ω, ω‘|∆t) si dice probabilit`a di salto
I processi di markov sono processi stocastici caraterizzati da
Y
p(ω(t0 ), · · · , ω(tN )) =
p(ω(ti ), ω(ti+1 ))
i=0,N −1
cio`e in cui le probabilit`a dei successivi salti sono indipendenti
Si dice che il processo non ha memoria.
1.1.1
matrice di Markov
Se inoltre la probabilit`a di salto `e indipendente dal tempo (iniziale) si parla
di processo stazionario. In tal caso li processo `e descritto da una matrice
(matrice di Markov) M = [|Ω| × Ω|]
Mω←ω‘ (∆t) = p(ω(ti ) = ω, ω(ti−1) = ω‘)
e in termini degli elementi della matrice M la probabilit`a della storia
{ωo , ω1, · · · , ωN } `e data da
p(ωo , ω1 , · · · , ωN ) = MωN ←ωN−1 MωN−1 ←ωN−2 · · · Mω1 ←ω0
La matrice M ha due propriet`a di base:
⇒ 1) Mω←ω‘ ≥ 0 perch`e ogni elemento di matrice `e una probabilit`a (condizionata
P di salto)
⇒ 2) ω∈Ω Mω←ω‘ = 1 perch`e qualunque sia l‘evento di partenza assumo di
finire in un qualche evento, cio`e assumo di non uscire dallo spazio Ω ( non
estenzione del processo)
Queste propriet`a implicano che lo spettro di M `e contenuto nella bolla unitaria di C. La matrice M `e matrice di contrazione
per la propriet`a (2), µ = 1 `e autovalore, con autovettore
sinistro costante
P
sommando su ω , l‘equazione agli autovalori ω∈Ω
P ·Mω←ω‘ α(ω‘) = µ · α(ω)
sempre per la propriet`a (2), ho
o
µ
=
1
oppure
o a(ω) = 0
P
Quindi, prendendo il modulo ω∈Ω ·Mω←ω‘ |α(ω‘)| ≥ |µ| · ka(ω)|
4
(1) ottengo che |µ| ≤ 1
(2) inoltre l‘eguaglianza `e possibile solo se a(ω) = ka(ω)| ovvero l‘autovettore
destro corrispondente all‘ autovalore µ = 1 se esiste `e (sceglibile) a componenti positive.
1.1.2
evoluzione misure e distribuzione stazionaria
Se α `e una generica misura di probabilit`a definita su Ω il processo di markov
induce una evoluzione
di questa probabilit`a :
P
α(ω) → α(ω) = ω Mω←ω‘ α(ω‘)
Per esempio si pensi ad Ω come spazio di stati microscopici e α come la
misura di probabilit`a che descrive uno stato macroscopico
Il processo di markov fa evolvere gli stati microscopici, passo passo con M.
Se al tempo iniziale t = 0 ho probabilit`a α(0) (ω) di essere in ω, poich`e al
tempo t = 1 lo stato ω `e con probabilit`a Mω‘←ω diventato ω‘ e le probabilit`a
di salto `e indipendente da α(0) , ho probabilit`a Mω‘←ω α(ω) di essere
P in ω‘. (0)
(1)
In conclusione la probabilit`a al tempo t = 1 `e data da α (ω‘) = ω Mω‘←ω α (ω)
(sommo perch`e c‘`e autoesclusione ...)
Le propriet`a base della matrice di Markov garantiscono che α(0)Pa componenti
(1)
(1)
positive
P (0) sia trasformato in α a componeti positive e che ω‘ α (ω‘) =
e che sia conservata la normalizzazione della misura.
ω α (ω) cio`
` immediato scrivere l‘evoluto dopo t passi della misura iniziale α(0) :
E
α(t) (ω‘) = [M t ]ω‘←ω α(0) (ω)
Notate la similitudine con l‘evoluzione MQ via U(t) = [eiH ]t → [M]t
Ma ATT! M non `e , in generale, simmetrica.
Una misura di probabilit`a π su Ω tale che Mπ = π si dice distribuzione
stazionaria (di equilibrio) del processo
Se pensiamo che il processo descriva l‘evoluzione del sistema micro questa
distribuzione `e lo stato macroscopico di equilibrio termodinamico
Data la matrice M non `e detto che esista una corrispondente distribuzione
di equilibrio.
Il teorema di Frobenius-Perron individua le condizioni di esistenza per una
classe di matrici M che soddisfano (oltre le propriet`a base) la condizione di
irriducibilit`a
La matrice M `e irriducibile se per qualsiasi coppia di stati ω, ω‘ esiste m > 0,
finito tale che [M m ]ω←ω‘ > 0. Intuitivamente ci`o significa che qualsisi coppia
di stati `e dinamicamente connessa, partendi da ω‘, in un tempo finito, ho
probabilit`a non nulla di essere in ω.
` sostanzialmente una propriet`a di ergodicit`a della dinamica aleatoria.
E
5
1.1.3
teorema di Frobenius-Perron
Per esempio vedi : PerronFrobenius theorem
From Wikipedia, the free encyclopedia
Let A be an irreducible non-negative nn matrix with period h and spectral
radius ρ(A) = r . Then the following statements hold.
1) The number r is a positive real number and it is an eigenvalue of the
matrix A, called the PerronFrobenius eigenvalue.
2) The PerronFrobenius eigenvalue r is simple. Both right and left eigenspaces
associated with r are one-dimensional.
3) A has a left eigenvector v with eigenvalue r whose components are all
positive.
Likewise, A has a right eigenvector w with eigenvalue r whose components
are all positive.
The only eigenvectors whose components are all positive are those associated
with the eigenvalue r .
4) Matrix A has exactly h (where h is the period) complex eigenvalues with
absolute value r . Each of them is a simple root of the characteristic polynomial and is the product of r with an h-th root of unity.
5) CollatzWielandt formula: for all non-negative non-zero vectors x let f (x)
be the minimum value of [Ax]i /xi taken over all those i such that xi 6= 0.
Then f is a real valued function whose maximum is the PerronFrobenius
eigenvalue.
6) The
eigenvalue satisfies the inequalities
P PerronFrobeniusP
mini j aij ≤ r ≤ maxi j aij
...............................................................................................
commenti
• periodo h e ciclicit`a
Considerando l‘identit`a e le matrici di permutazione come matrici di
markov ci si convince che una matrice di markov pu`o avere varie radici
dell‘unit`a come autovalori. Questo fatto `e legato alla ciclicit`a del processo.
La ciclicit`a comporta la scomposizione dell‘ insieme Ω in vari cluster
etc. Nel seguito siamo interessati a escludere queste situazioni, almeno
nel caso di
Ω finito. Vedi Parisi-Marinari ‘ trattatello ...‘
Nel sequito escluderemo processi ciclici e quindi richiederemo propriet`a
di connettivit`a, ergodicit`a etc per la matrice M
• l‘unicit`a discende dalla positivit`a delle componenti
6
1.1.4
reversibilit`
a e bilancio dettagliato
Si dice che il processo di markov soddisfa la condizione di bilancio dettagliato
se esiste una vettore χ tale che
Mω←ω‘ χ(ω‘) = Mω′ ←ω χ(ω) ∀ω, ω‘
(1.1)
P
• Osservo chePse sommo questa eguaglianza su ω poich`e Pω Mω←ω‘ = 1 trovo
che χ(ω‘) = ω Mω′ ←ω χ(ω) cio`e se χ `e normalizzabile ω χ(ω) < ∞ allora
χ `e la distribuzione stazionaria associata ad M (χ = π)
• Il significato della condizione di bilancio dettagliato `e legato alla reversibilit`a
del processo. In modo sintetico si pu`o dire che [ 1.1] dice, nella distribuzione
di equilibrio, la probabilit`a del salto ω → ω‘ `e eguale alla probabilit`a del
salto opposto,
• Tecnicamente una conseguenza importante del bilancio dettagliato consiste
fω‘,ω = π(ω‘)− 21 Mω′ ←ω pi(ω) 21 `e simmetrica. (verifinel fatto che la matrice M
care )
f ( e quindi di M) sia reale ed ho µ1 = 1 >
Ci`o implica che lo spettro di M
µ2 ≥ µ3 · · · ≥ µN ≥ −1
f = P µPµ e sviluppare molte considerazioni in moPosso diagonalizzare M
µ
do molto semplice.
P
L‘algebra dell‘evoluzione `e molto semplice M t ∼ µ µt Pµ
t
In particolare notare che limt→∞ Mω‘,ω
= P1 ovvero qualunque sia la distribuzione iniziale il processo la trasforma nella distribuzione stazionaria.
1.2
RV funzioni della traiettoria
Consideriamo le variabili aleatorie definite su Ω ( quelle che chiamiamo le
‘osservabili‘ microscopiche) ovvero le funzioni misurabili a valori reali (o vettoriali o altro) tipo f : ω → f (ω) .
Abbiamo visto, nel capito sulle probabilit`a, che a variabili aleatorie, fissata
una misura su Ω associamo valori di aspettazione, varianze etc... che interpretiamo comePgrandezze macroscopiche:
P
f →< f >α = ω∈Ω f (ω)α(ω), var 2 = ω∈Ω (f (ω)− < f >)2 α(ω) etc.
Qui stiamo studiando un processo e quindi dobbiamo considerare la dinamica
indotta dal processo sui valori assunti dalla RV f .
come dire che non ci basta conoscere valori medi e varianze ad un certo istante ma dobbiamo conoscere anche le correlazioni fra i valori assunti da f
a momenti diversi , < f (t) >, < f (t)f (s) >, etc.
7
In altre parole dobbiamo considerare la famiglia (il processo stocastico) dei
varori assunti da f sui vari stati della storia: {f0 (ω0 ), f1 (ω1 ), · · · , fN (ωN )}
( ft `e la RV f misurata al tempo t)
Evidentemente la probabilit`a di una sequenza {ft }i=0,N `e la probabilit`a della
storia sottostane {ωi }i=0,N
Se π(ω) `eP
la dstribuzione iniziale avremo che
t
< ft >= ω,ω‘ f (ω)Mω,ω‘
π(ω‘)
P
t
s
< ft+s fs >= ω,ω‘,ω“ f (ω)Mω,ω‘
f (ω ′ )Mω‘,ω“
π(ω“)
etc...
P
t
In particolare se π(ω) `e la dstribuzione stazionaria ( ω‘ f (ω)Mω,ω‘
π(ω‘) =
π(ω)) allora
P
< ft >= ω fP(ω)π(ω) ≡< f > time independent
t
< ft+s fs >= ω,ω‘ f (ω)Mω,ω‘
f (ω ′ )π(ω‘) ≡ gf f (t) funzione solo di t etc.
Nota————
Come nel caso MQ passo dalla descrizione di Schrodinger a quella di Heisember qui posso passare dalla descrizione in cui faccio evolvere il macrostato alla
descrizione in cui P
faccio evolvere le osservabili.
t
f (ω‘) → ft (ω‘) = ω f ωMω,ω‘
e i valori attesi li prendo con misura fissata
al tempo t = 0
—————————————–
1.2.1
serie temporali
Il fatto che le RV ft non siano indipendenti ci pone un problema relativo a
teoremi come la leggi dei grandi numeri e il teorema del limite centrale per
la sequenza delle variabili ft .
Che leggi soddisfano la media empirica, la varianza della media, etc. ?
P
Consideriamo l‘ aspettazione della “somma totale” F (T ) =
ft
t=0,T
P P e calcoliamone la varianza σ (T ) =
t ft
s fs
(per semplicit`a assumiamo < f >= 0)
Tutto ci`o che ci serve sapere `e la correlazione temporale g(t) fra le nostre
RV, correlazione che assumiamo dipendere solo dall‘intervallo temporale che
separa le osservazioni (stazionariet`a del processo).
Infatti abbiamo:
X X X X
X
ft
fs ] =
ft fs =
ft ft +
ft fs
t
s
t,s
t=s
t6=s
= T gf f (0) + (T − 1)gf f (1) + (T − 1)gf f (−1) + (T − 2)gf f (2) + · · ·
8
= |T |
T X
1−
|h|=0
|h| g(|R|)
T
(sommo gli addendi per diagonali: v. figura)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . .
.
g(1) (T−1)
. . . .g(0) T
. . . .
g(−1)(T−1)
Ora se
P+∞
−∞
g(r) = g˜(0) < ∞ ⇒
lim
T →∞
X X T −1 [
fi ][
fj = g˜(0)
i
j
P+∞
PT
r
a(r)
→=
- E’ Conseguenza del Lemma di Cesaro:
1
−
−∞ a(r) 0
T
- Scrivo g˜(0) perche’ e’ la trasformata di Fourier di g(r) calcolata in 0 : si
dice ’correlazione integrale’
Se si confronta il risultato ottenuto con cio’ che conosciamo nel caso di variabili indipendenti, si vede che la grandezza g(0) = var2 (σ) e’ sostituita dalla
dalla grandezza g˜(0).
Si pu`o ripetere la dimostarzione alla Chebishev della legge dei grandi numeri
< F (T ) >
σ (T )
−<f >≥ǫ ≤ 2 2
P T
T ǫ
(T )
dove, da quanto sopra, σ = T g˜(0)
La legge dei grandi numeri continua ad essere valida anche se g˜(0) diverge
ma in modo sublineare nel tempo.
Schematicamente possiamo considerare i seguenti andamenti della funzione
di correlazione temporale per h → ∞:
9
• g(h) → γ costante, `e la massima correlazione permessa, allora g˜(0) diverge
linearmente in T e la legge dei grandi numeri cade
• g(h) ∼ h−α α > 0 , la correlazione si spegne lentamente, con legge di
potenza ( code grasse in gergo) , allora g˜(0) diverge come T 1−α ma la legge
continua a valere
• g(h) ∼ eh/τ , la correlazione si spegne rapidamente, dopo un tempo ordine τ
le RV sono (come) scorrelate, allora g˜(0) ∼ (1 − e1/τ )−1 vale la legge. Notare
che posso stimare (...) g˜(0) ∼ τ
Nel caso di processi di Markov su Ω discreti e finiti quello che ci apsettiamo
`e di trovarci sempre nel terzo caso
La dinamica delle fluttuazioni di f definitePcome (∆f )t = (ft − < f >) `e
t
t
data considerando le identit`a (M − P1 )t = P
i>1 µi Pi = M − P1
t
t
t
Ora (∆f )t = f M − f P1 = f (M − P1 ) = f ( i>1 µi Pi )
Gli autovalori (diversi dal primo) sono tutti in modulo minori di uno, chiamando µ ‘mixing rate‘ il massimo fra essi e cio`e
µ = max(µ2 , |µn |) > |µi | con i 6= 2, n
posso dire t >> 1 (∆f )t ∼ f Pµ µt ⇒ ho spegnimento esponenziale
In altri termini, le funzioni di correlazione gf f (t) sono funzioni esponenzialmente decrescenti dell‘ intervallo temporale che separa le variabili.
Da M t ∼= P1 + µt2 P2 + · segue che < ft f0 > − < f >2 ∼ µt < f Pµ f >
+ · · · ∼ elog µt cf f
Sokal usa ρf f (t) = gf f (t)/gf f (0) normalized autocorrelation cosich`e
t
1
ρf f (t) ∼ e− τ e quindi τexp,f
= − log max[µ2 , µn ]
e definisce τexp,f = lim supt→∞ log ρ−tf f (t) )
Questo tempo, intuitivamente, ci indica quanto dobbiamo aspettare per considerare ’scorrelati’ i valori assunti dalla f , `e il tempo di ‘rilassamento‘del
modo pi`
u lento nel sistema.
t
Se vale ρf f (t) ∼ e− τ allora
P posso definire un secondo tempo caratteristico
1
del processo τint,f = 2 + t=1,∞ ρf f (t)
cosich`e risulta
1
var(f ) = (2τint,f )gf f (0)
T
1
Nota che τint,f ∼ 1−µ
Simili considerazioni si possono sviluppare per quanto riguarda la legge limite a cui converge la media empirica
Svilupperemo questo punto nei sucessivi capitoli. Qui dico solo che sostanzialmente tranne che per il primo caso, vale sempre un teorema del limite ma
10
pu`o accadere `e di uscire dal bacino gaussiano e cadere in un bacino di L`evy.
( rif K L Chung: ‘Markov chains with stationary Transition probabilties’
(spriger 1967))
1.3
grandezze fondamentali
vedi nota da Feller negli appunti MS classica, vedi Kac etc...
Il processo di Markov `e caratterizzato da un insieme di (ddp) tempi carateristici che svolgono un ruolo importante per la descrizione del processo stesso.
Analizzaeremo queste ddp e le equazioni che li legano con dettaglio nello
studio del RW e dei processi di diffusione, per ora mi pare importante darne
un elenco e fare qualche commento
Indico la probabilit‘a di occupazione ( essere in) dello stato ω‘, al tempo t,
condizionata all‘essere in ω al tempo zero, con P (ω‘, t : ω, 0) ≡ < ω‘M t ω >
Gli oggetti fondamentali sono:
• autocorrelazione temporale: P (ω, t|ω, 0) = PA (ω, t) ; t > 0
definisce la ddp “tempo di ritorno”.
• tempo di primo passaggio, tempo di primo ritorno
Indichiamo con P1 (ω, t|0, 0) la ddp del tempo di primo passaggio, ovvero
la probabilit`a di essere in ω al tempo t per la prima volta (cond.
dall‘essere partiti da 0 al tempo 0).
Indichiamo con P1R (ω, t) la ddp tempo di primo ritorno, ovvero la probabilit`a di essere in ω per la prima volta essendo partiti da ω stesso al
tempo 0
Vale la equazione
X
P (ω, t|0, 0) = δω,0 δt,0 +
P1 (ω, t1|0, 0) P (ω, t2|x, 0)
|
{z
}
t1 +t2 =t>0
PA (ω,t2 )
Per l‘origine il tempo di primo passaggio `e tempo di primo ritorno (t > 0
!) e similmente definisco tempo di primo ritorno P1R (ω, t) considerando
la precedente equazione con la condizione (..|0, 0) → (..|ω, 0)
• ddp tempo di i-simo passaggio Pi (ω, t|0, 0) (`e una p(Ti (x) = t|..))
X
ricorsivita‘: i ≥ 2 Pi (ω, t|0, 0) =
Pi−1 (ω, t1 )P1R (ω, t2 )
t1 +t2 =t
11
• numero medio stati distinti visitati fino al tempo t : N(t)
( = D(t)
P di Itzykson-Drouffe)
numero medio siti nuovi visitati al tempo t : ω6=0 P1 (ω, t)
P
P
N(t) = 1 + t‘=1,t ω6=0 P1 (ω, t‘)
L‘equazione fondamentale `e
p(ω, t|0, 0) = δω,0 δt,0 +
X
i
= δω,0 δt,0 +
Pi (ω, t, |00)
X
P1 (ω, t1 |0, 0) PA (ω, t2)
(1.2)
t1 +t2 =t>0
Ricordando Feller e Kac `e immediato collegare queste ddp alla ddp di equilibrio del processo studiato.
funzioni generatrici
In generale la trasformata di laplace nella variable tempo permette di sviluppare uno studio dettagliato di queste distribuzioni di probabilit`a. trasformata di laplace nella variable tempo. Non tocco e non faccio ipotesi sullo spazio.
• f-generatrice
P della RV ‘tempo medio trascorso in ω ‘:
G(ω, λ) = λ t λt P (ω, t|0, 0)
P
→ tempo medio trascorso in ω :G(ω, 1) = t P (ω, t|0, 0)
• f-generatrice
P della RV ‘prob di almeno una visita in ω per t > 0:
Π(ω, λ) = t λt P1 (ω, t)
P
→ prob di almeno una visita in ω 6= 0 : Π(ω, 1) = t P1 (ω, t)
ATT! prob di almeno una visita in ω = 0, t > 0 `e la prob. di ritorno (t > 0!)
per ω 6= 0 prob di almeno una visita e prob. di ritorno sono grandezze diverse. Indico con Π1R (ω, λ) la f. g. di questa seconda grandezza.
• f-generatrice della RV ‘prob di i-sima visita in ω vale l‘equazione ricorsiva
Πi+1 (ω, λ) = ΠI (ω, λ)Π1R (ω, λ) i ≥ 1 e quindi Πi+1 (ω, λ) = Π(ω, λ)Π1R (ω, λ)i
0
• f-generatrice
P della autocorrealzione temporale di ω :
ΠA (ω, λ) = t λt P (ω, t; x, 0)
P
P
→ prob di ritorno in ω : P
ΠA (ω, 1) = t P (ω, t; x, 0) = t PA (ω, t)
Evidentemente ΠA (ω, λ) = i≥1 Π1R (ω, λ)i = 1−Π1R1 (ω,λ)
12
i≥
e in generale posso riscrivere le equazioni fondamentali come
G(ω.λ)/λ =δω,0 + Π(ω, λ)ΠA (ω, λ)
X
= δω,0 + Π(ω, λ)
Πi1R (ω, λ)
(1.3)
i≥0
= δx,0 + Π(ω, λ)
1
1 − Π1R (ω, λ)
• f-generatrice della RV ‘siti nuovi visitati fino al tempo‘ N(λ) =
N(λ) =
X
1
[1 +
Π(ω, λ)]
(1 − λ)
P∞
t‘=1
λt N(t)
ω6=0
1.3.1
prob
prob
prob
prob
di
di
di
di
shema conti e commenti
almeno una visita =Π(x),
primo ritorno =ΠR (x),
non visita 1 − Π(x),
una visita, prob di due visite, etc.
+
+
+
+
+
+ . . . ...
per l‘origine:
G(0) = 1 + 1Π(0)[1 − Π(0)] + 2Π2 (0)[1 − Π(0)] + · · · = [1 − Π(0)]−1
per ω 6= 0
G(ω) = Π(ω) + 2Π(ω)ΠR (ω)[1 − ΠR (ω)] + 3Π(ω)Π2R (ω)[1 − ΠR (ω)] + · · ·
= Π(ω)[1 − ΠR (ω)]−1
Dalla equazione [1.2] si ottengono le relazioni fra le diverse funzioni generatrici con l‘algebra alla Laplace transform.
∀i ≥ 1 Pi+1 (x, t) =
X
t1 +t2 +t
13
Pi (x, t)P1 (0, t)
P
t
tempo prima visita → almeno una visita : Π(x, λ) = t=∞
t=0 λ P1 (x, t)
Pt=∞ t
Pt=∞ t
Π(0, λ) =
t=0 λ P1 (0, t) =
t=0 λ PA (x, t) (∀ x)
P (x, t) =δx,0 δt,0 +
t=∞
X
Pi (x, t)
i=1
= δx,0δt,0 + P1 (x, t) +
+
X
X
P1 (x, t1 )P1 (0, t2 )+
t1 +t2 =t
P1 (x, t1 )P1 (0, t2 )P1 (0, t3 ) + · · ·
t1 +t2 +t3 =t
h
i
⊗2
⊗3
= δx,0δt,0 + P1 (x, t) 1 + P1 (0, t) + P1 (0, t) + P1 (0, t) · · ·
(1.4)
convoluzione → prodotto
1
1
G(x, λ) = δx,0 + Π(x, λ)
λ
1 − Π(0, λ)
(1.5)
Simili per N(λ) etc.
P (0, t|0, 0) = δt,0 + PA (0, t)
ΠA (0, λ) = λ1 G(0, λ) − 1
Π(0,λ)
ΠA (0, λ) = 1−Π(0.λ)
——————————————breve commento
Nel caso di |Ω| finito esiste un tempo medio Tcov finito necessario per visitare
tutti i siti almeno una volta.`e detto tempo di ricoprimento,
Per |Ω| finito il tempo medio di ritorno `e 1/π eq (ω) cosich`e G(ω|0) diverge (
come G(ω|0) ∼ T /π eq (x))
inoltre `e sempre Π(ω|0) = 1
(Indico con Π(x|0) la peobabilit`a di almeno una visita in x partendo da 0 e
similmente le altre grandezze)
Vale sempre la relazione ΠA (ω) =: [1 − Π1R (ω)]−1
1
e per i moti che partano da 0 al tempo zero vale la Π(0) + G(0)
=1
(la probabilit`a di non ritorno `e l‘inverso del tempo di permanenza)
mentre Π(ω|0) = G(ω|0) [1 − Π1R (ω)] e ΠA (x) = 1/G(x|0) diverge
14
Osservo ancora che dalla finitezza del tempo medio di ritorno 1/π eq (x) segue
sostanzialmente G(x, λ) ∼ λ/(1 − λ)
e quindi il numero di nuovi siti visitati ha funzione generatrice N(λ) ∼
t
1/(1 − λ) ovvero N(t) ∼ n ( va come N(t) ∼ n(1 − e− τ ) ??)
1.3.2
algebra dell‘evoluzione
Le stesse osservazioni via algebra della matrice di markov
Nel caso di uno spazio Ω discreto e finito, l‘algebra dell‘evoluzione `e molto
semplice e permette di calcolare tutte le grandezze definite sopra. In particolare nel caso in cui il processo soddisfi il bilancio dettagliato (sia time
reversible)
• la matrice
PM `e equivalente ad una matrice simmetrica quindi
M ∼ P1 + i>1 µi Pi con P1 = |π >< e|
• lo spettro `e µ1 = 1 > µ2 ≥ · · · ≥ µn ≥ −1
(escudiamo µnP= −1 per semplicit`a, per es nei grafi non-bipartiti µn > −1 )
• M t ∼ P1 + i>1 µti Pi
Per t → ∞ M t ∼ P1 + µt Pµ dove µ = mixing rate = max(µ2 , |µn |)
• l‘ autocerrelazione satura con legge esponenziale
PA (x, t) =< xP1 x > +µt < xPµ x > |µ| < 1
anche µ = e−1/τ mix etc.
• I tempi di permanenza fino al tempo T sono dati dagli elementi della matrice
PT
P
1−µT
t
i
t=0 M ∼ T P1 +
i>1 [ 1−µi ] Pi
PT
ovvero t=0 M t ∼ T P1 ∼ T π
(stato in esame-stato di partenza, questo ultimo irrilevante)
15
Capitolo 2
Processi di Markov non discreti
Ci poniamo due questioni
1) cosa succede quando lo spazio degli stati |Ω| → ∞ ?
2) cosa succede quando il processo diventa un processo continuo, da fisici
cosa succede quando ∆t → 0 ?
2.1
|Ω| → ∞
Quando |Ω| → ∞ la matrice diventa una matrice infinita (operatore su opportuno dominio in l2 (Ω))
Se penso alla Mec Stat, |Ω| → ∞ vuol dire fare il limite termodinamico.
il teorema di Frobenius Perron pu`o continuare a valere
Glimm-Jaffe .............
Let A have a strictly positive kernel
let ||A|| = λ be an eigenvalue of A (ATT! `e assunzione)
⇓ Then λ has multiplicity 1, and Ω the corresponding eigenvector can be
chosen to be strictly positive function.
( strictly positive kernel: nella realizzazione L2 (X, dν) ... per qualsiasi θ(x)
`e Aθ > 0 a.e.
segue che per θ, φ positive, non identicamente nulle < θ, Aφ. > `e strettamente positivo)
————
Ma pu`o accadere che il teorema di Frobenius Perron non sia pi´
u valido
Lo spettro dell’ operatore pu´o diventare continuo (sempre limitato) e se
• l’autovalore massimo 1 diventa inproprio
16
⇒ π eq 6∈ l1 non esiste pi´
u come misura di equilibrio.
in tal caso ⇒ esiste [I − M]−1 che pu´o essere operatore sia limitato che illimitato.
R 1
P
t
La ∞
dPµ = [I − M]−1 definisce il tempo di permanenza in x
t=0 M =
1−µ
(come < x[I − M]−1 0 >) che quindi pu´o anche essere limitato. Come dire
che la probabilit`a di visita pu`o essere minore di uno, essere in x `e un evento
transitorio, etc.
————
(The Fredholm alternative)
O esiste π eq oppure esiste [I − M]−1 .
Let K(x, y) be an integral kernel, and consider the homogeneous equation,
the Fredholm
R b integral equation,
λφ(x) − a K(x, y)φ(y) dy = 0
and the inhomogeneous
equation
Rb
λφ(x) − a K(x, y)φ(y) dy = f (x).
The Fredholm alternative states that, for any non-zero fixed complex number
λ ∈ C, either the first equation has a non-trivial solution, or the second
equation has a solution for all f (x)
A sufficient condition for this theorem to hold is for K(x, y) to be square
integrable on the rectangle [a, b] × [a, b] (where ”a” and/or ”b” may be minus
or plus infinity).
————
⇒ Ancora l‘ autocerrelazione pu`o essere pwl:
1
trM t → t−a
< xM t x >∼ |Γ|
R
1
(tipo diffusione pura su reticolo regolare: |Γ|
trM t = [dk]d e − −k 2 t = t−d/2 :
vedi capitolo RW)
• Indipendetemente dal fatto che il primo autovalore resti autovalore proprio
o no posso schizzare una storia algebrica del tipo che segue
X
(M − P1 )t = M t − P1 =
µti Pi → · · ·
i>1
⇒ Ω finito:
sempre µ = max(µ2 , |µn |) tale che per
P esiste
t
t
t >> 1
di spegnimento
esponenziale
i>1 µi Pi ∼ µ Pµ col significato
R
P
⇒ ma quando Ω va ad infinito i>1 µti Pi ⇒ [1,−1] µt dP (µ)
e non posso in generale isolare il secondo autovalore (indipendentemente dal
fatto che il primo sia proprio o no). Allora ho fenomeni tipo:
17
R
R
tr [1,−1] µt dP (µ) = [1,−1] µt n(µ)dµ
dove n(µ) `e la densit`a di autovalori. Se n(µ) ∼ (1 − µ)a−1 accade che
nell‘intorno
di 1 valuto l‘integrale
via
R
R
t
a−1
t a−1
µ
(1
−
µ)
dµ
=
(1
−
e)
e de
[1,−1]
[0,··· ]
R
−et a−1
−a
∼ [0,··· ] e e de = t cio`e emergono comportamenti pwl.
1
|Γ|
2.1.1
transizione fase
Sostanzialmente nel limite |Ω| → ∞ perdo la irriducibilit`a.
Forse meglio dire tempo di autocorrelazione diverge
il punto chiave per Ω → ∞ consiste nella possibilit`a che τexp,f → ∞,
τint,f → ∞
Per esempio, il tempo di autocorrelazione vicino al punto critico (transizioni
di fase del secondo ordine ) diverge come τ = [min(L, ξ)]z dove L `e la dimensione lineare del sistema, ξ `e la lunghezza correlazione e z `e l‘esponente
critico dinamico
update locali → per avere una configurazione statisticamente significativa
(scorrelata) il processo deve eplorare (e cambiare) una regione di dimensione
ξ → per un RW gaussiano questo richede τ ∼ ξ 2,.
altri ............
In generale la funzione di autocorrelazione ρf f (t) obbedisce a leggi di scala
dinamiche:
ρf f (t; β) = |t|−a F (β − βc )|t|b ) |t| >> 1 |β − βc | << 1 |β − βc ||t|blim
con a, b > 0 e F continua, strettamente positiva, rap. decrescente per
argomento divergente. Allora

 τexp,f ∼
|β − βc |−1/b
τ
∼
|β − βc |−(1−a)/b
 ρ int,f
|t|−a
f f (t; βc ) ∼
2.2
∆t → 0
problema M ∆t
problema misure infinitamente divisibili
Fer esmpio Feller Vol II, capitolo IX : `e una lettura particolarmente adatta
a un fisico perch`e sviluppa argomenti dl tutto simili a MQ.
18
Capitolo 3
simulazioni Monte Carlo
Vedi A.D. Sokal
Monte Carlo Method in Sattistical Mechanics
lectures at the Carg`ese Summer school - september 1996
19

Download Report