Description

UIVERSITÀ DEGLI STUDI DI PADOVA Sede Amministrativa: Università degli Studi di Padova Dipartimento di Matematica Pura ed Applicata SCUOLA DI DOTTORATO DI RICERCA I SCIEZE MATEMATICHE IDIRIZZO MATEMATICA

Information

Category:
## School Work

Publish on:

Views: 34 | Pages: 30

Extension: PDF | Download: 0

Share

Transcript

UIVERSITÀ DEGLI STUDI DI PADOVA Sede Amministrativa: Università degli Studi di Padova Dipartimento di Matematica Pura ed Applicata SCUOLA DI DOTTORATO DI RICERCA I SCIEZE MATEMATICHE IDIRIZZO MATEMATICA CICLO XXI TWO PROBLEMS COCERIG ITERACTIG SYSTEMS: 1. O THE PURITY OF THE FREE BOUDARY CODITIO POTTS MEASURE O GALTO-WATSO TREES 2. UIFORM PROPAGATIO OF CHAOS AD FLUCTUATIO THEOREMS I SOME SPI-FLIP MODELS Direttore della Scuola: Ch.mo Prof. Paolo dai Pra Supervisori: Ch.mo Prof. Paolo dai Pra Prof. Dr. Christof Külske Dottorando: Marco Formentin 30 giugno 2009 Abstract: A rigorous approach to Statistical Physics issues often produces interesting mathematical questions. This Ph.D. thesis is composed of two different parts. One does not intersect the other, but both research topics lie at the interface between Probability Theory and Statistical Mechanics. In the first part we deal with reconstruction of a tree-indexed Markov chain on Galton-Watson trees, improving previous bound by Mossel and Peres, both for symmetric and strongly asymmetric chains. Moreover, we give some numerical estimates to compare our bound with those of other authors. We provide a sufficient condition of the form QdcM 1 for the non-reconstructability of tree-indexed q-state Markov chains obtained by broadcasting a signal from the root with a given transition matrix M. Here cm is a constant depending on the transition matrix M and Qd is the expected number of offspring on the Galton-Watson tree. This result is equivalent to proving the extremality of the free boundary condition Gibbs measure within the corresponding Gibbs-simplex. When considering the Potts model case we take this point of view too. Our theorem holds for possibly non-reversible M. In the case of the symmetric Ising model the method produces the correct reconstruction threshold, in the case of the strongly asymmetric Ising model where the Kesten-Stigum bound is known to be not sharp the method provides improved numerical bounds. In the second part of the thesis we give sharp estimates for time uniform propagation of chaos in some specials mean field spin-flip models exhibiting phase transition. The first model is the dynamical Curie-Weiss model, that can be considered as the most basic mean field model. The second example is a model proposed recently in the context of credit risk in Finance; it describes the time evolution of finantial indicators for a network of interacting firms. Although we have chosen to deal with two specific models, the method we use appear to be rather general, and should work for other classes of models. A substantial limitation of our results is that they are limited to the subcritical case or, in Statistical Mechanical terms, to the high temperature regime. 3 Sommario: Un approccio rigoroso a questioni di Fisica Statistica spesso produce interessanti problemi matematici. Questa tesi di dottorato è composta da due parti. La prima non interseca la seconda, ma entrambe stanno sul confine tra Teoria della Probabilità e Meccanica Statistica. La prima parte tratta il problema della ricostruzione per catene di Markov su alberi di tipo Galton-Watson. Miglioriamo i risultati precedentemente ottenuti da Mossel e Peres, sia per catene simmetriche che fortemente asimmetriche. Dimostriamo una condizione sufficiente della forma QdcM 1 per la non ricostruzione di catene di Markov a q-stati sull albero. Qui cm è una costante che dipende dalla matrice di transizione M e Qd è la media del numero di figli per vertice nell albero di Galton-Watson. Questo risultato è equivalente alla purezza della misura libera di Gibbs. Quando consideriamo il caso del modello di Potts assumiamo anche questo punto di vista. Il teorema è valido anche per catene non reversibili. el caso del modello di Ising il nostro risultato produce la correta soglia di ricostruzione, nel caso di catene fortemente asimmetriche dove si sa che il bound di Kesten-Stigum non è esatto il metodo usato dà risultati numerici migliori. ella seconda parte diamo delle stime uniformi nel tempo per la propagazione del caos in alcuni modelli di spin con interazione a campo medio che presentano transizione di fase. Il primo è il modello dinamico di Curie-Weiss, che può essere considerato come il più semplice esempio di sistema con interazione a campo medio. Il secondo è un modello recentemente impiegato per spiegare i meccanismi del rischio di credito; esso descrive l evoluzione temporale di indicatori finaziari per un gruppo di aziende interagenti quotate sul mercato. Anche se abbiamo trattato modelli specifici, crediamo che il metodo funzioni piuttosto in generale e che sia applicabile anche ad altre classi di modelli. Una limitazione sostanziale dei nostri risultati è che valgono solo nel caso sottocritico, che corrisponde, nel linguaggio della Meccanica Statistica, al regime di alta temperatura. 4 Acknowledgments There are few people to whom I am indebted for various reasons: Paolo Dai Pra, Christof Külske, Ida Germana Minelli and Francesca Collet. o word in this thesis would have been possible without their help. I am sincerely grateful to each of them, and I hope they already know. In particular, I want to express my gratitude to Christof. He is a teacher, a co-worker and a friend. To meet him was a gift. Fortune has treated me kindly. 5 Contents I On the Purity of the free boundary condition Potts measure on Galton-Watson trees 11 Introduction to Part I 13 1 Ising model on trees: purity and reconstruction Introduction Purity for the Ising model and reconstruction for binary channels Proof of Theorem Proof of Theorem Purity transition on Galton-Watson trees I: the Potts model Introduction The Potts model on trees A criterion for extremality on random trees Proof of Theorem Recursions for the boundary entropy for subtrees Controlling the recursion relation for the boundary entropy The ferromagnetic ordering Purity transition on Galton-Watson trees II: entropy is Lyapunov Introduction Purity transition for q-state Markov chain on trees Applications: two special models Contents Potts model Asymmetric binary channels Proof of Theorem 3.2.1: entropy is Lyapunov Conclusions Introduction Conjectures and comparisons II Uniform propagation of chaos and fluctuation theorems in some spin-flip models 69 Introduction to Part II 71 5 Propagation of chaos for the Curie-Weiss mean field model Introduction The Curie-Weiss model and uniform propagation of chaos Proof of Theorem Case ω = Case ω Propagation of chaos in a model for large portfolio losses Introduction Description of the model Uniform propagation of chaos Proof of Theorem Uniform fluctuation theorem for the Curie-Weiss Model Uniform fluctuation theorem Proof of Theorem 7.1.1: step Ornstein-Ulembeck equation for the empirical fluctuations Uniform distance for distribution functions Proof of Proposition Proof of Proposition Proof of Theorem 7.1.1: step The linearization of the Curie-Weiss model Contents Proof of Proposition Bibliography Bibliogarphy: Part I Bibliography: Part II Part I On the Purity of the free boundary condition Potts measure on Galton-Watson trees 11 Introduction to Part I This first part of the thesis focuses on the purity transition for the Potts model on random and deterministic trees. Interacting stochastic processes on trees and lattices often differ in a fundamental way: where a lattice model has a single transition point a critical value for a parameter of the model the corresponding model on a tree might possess multiple transition points. Such phenomena happen more generally for non-amenable graphs where surface terms are no smaller than volume terms, trees being major examples [9]. A main example of an interacting model is the usual ferromagnetic Ising model [1]. Here the interesting property which gives rise to a new transition is the purity sometimes called extremality of the free boundary condition Gibbs measure. On a tree the open boundary state will still be extremal in a temperature interval strictly below the ferromagnetic transition temperature. It ceases to be extremal at even lower temperatures. Ferromagnetic order on a tree is characterized by the fact that a plus-boundary condition at the leaves of a finite tree of depth persists to have influence to the origin when tends to infinity. For the tree it now happens in a range of temperatures, that even though an all plus-boundary condition will be felt at the origin, a typical boundary condition chosen from the free boundary condition measure itself will not be felt at the origin for a range of temperatures below the ferromagnetic transition. The latter implies the extremality of the free boundary condition state. In the following we write θ = tanhβ where β is the inverse temperature of the 13 Introduction to Part I Ising or Potts model and denote by d the number of children on a regular rooted tree. Then the ferromagnetic transition temperature is given by dθ = 1, and the transition temperature where the free boundary condition state ceases to be extremal is given by dθ 2 = 1. A proof of the latter fact is contained in [5]. A beautiful alternate proof of the extremality for dθ 2 1 for regular trees was given by Ioffe [6]. The method used therin was elegant but very much dependent on the two-valuedness of the Ising spin variable. This was exploited for the control of conditional probabilities in terms of projections to products of spins. Some care is necessesary to treat the marginal case where equality holds in the condition. Indeed, one needs to control quadratic terms in a recursion; this is difficult for a general tree where the degrees are not fixed. A second paper [7] proves an analogue of the condition for general trees with arbitrary degrees leaves this case open. Finally, for a general tree which does not possess any symmetries, [14] give a sharp criterion for extremality in terms of capacities. It remains an open problem to determine the extremal measures and the weights in the extreme decomposition of the open boundary condition state for dθ 2 1. Let us remark that the problem of extremality of the open boundary condition state is equivalent to the so-called Reconstruction Problem: an issue about noisy information flow on trees. Reconstruction is a topic where people coming from Probability, Statistical Mechanics, Biology and Computer Science can give contributions: recently it have been of interest in spin glasses [15] and computational biology [13]. The Reconstruction Problem can be stated as follow: we send a signal a plus or a minus from the origin to the boundary, making a prescribed error that is related to the temperature of the Ising model at every edge of the tree. In this way one obtains a Markov chain indexed by the tree. The reconstruction problem on a tree is called to be solvable, if the measure, obtained on the boundary at distance by sending an initial +, keeps a finite variational distance to the measure obtained by sending a, as n tends to infinity. onsolvability of reconstruction is equivalent to the extremality of the open boundary condition state [12, 10]. This is to say that there can be no transport of information along the tree between root and boundary, for typical signals. This equivalence makes clear what purity transition is about. 14 Introduction to Part I In the present part we aim at an explicit sufficient condition ensuring the extremality of the free b.c. state for the Potts model, generalizing the Ising condition dθ 2 1. We consider the free boundary condition Gibbs measure of the Potts model on a random tree. We provide an explicit temperature interval below the ferromagnetic transition temperature for which this measure is extremal, improving older bounds of Mossel and Peres [11]. Consider an infinite random tree, without leaves, rooted at 0. Call d i the number of children at each vertex i and let be Q their distribution. The same and independent at each vertex. The symbol Q stands also for the mean. In this situation our main result, formulated for a random tree, is the following. Write P = {p i i=1,...,q, p i 0 i, for the simplex of Potts probability vectors. q p i = 1} 1 i=1 Theorem The free boundary condition Gibbs measure P is extremal, for Q-a.e. tree T when the condition Qd 0 cβ, q := sup p P 2θ q q 2θ cβ, q 1 is satisfied. Here, q i=1 qp i 1log1 + e 2β 1p i q i=1 qp i 1log qp i. 2 Let us comment briefly. It is known that on a regular tree of degree d, there is 2 2θ reconstruction beyond the Kesten-Stigum bound d q q 2θ 1 proven to be sharp, for every degree d, only when q = 2 and for d sufficiently large and q = 3 [21]. Our bound for non-reconstruction improves the one which has been previously given in [11] and it holds for every number of offspring. We recover the bound in [11] from our when we use the estimate cβ, q θ. This estimate we see indeed numerically. Moreover, numerically cβ, q seems to decrease monotonically in q at fixed β. In literature, there are other thresholds and important works: in particular those of Sly [21] and Montanari-Mezard [15] along with the conjecture for deterministic trees therein. The conjecture states that the Kesten-Stigum bound is sharp only when q 4. The paper by Sly partially proves this conjecture; he proves that the Kesten-Stigum bound is sharp also when q = 3 with the degree d large enough and 15 Introduction to Part I that it can not be sharp for q 5. Thus, when d is small the problem of finding a rigorous sharp bound is still open for every q 3. In this case d small our bounds seem to the best rigorous thresholds as of today as pointed out also in [22]. We don t think they can be sharp, however, they differ only few percent form the Kesten- Stigum bound when q 4, and from the numerically determined thresholds of Montanari and Mezard for q 5. We are going to describe these aspects in more details in the conclusions. This thesis, where we present two different proof of Theorem 0.0.1, is organized as follows. The first chapter is introductory to the the problem. We review the Ising Model on a regular deterministic tree i.e. the degree of a vertex is fixed and its ferromagnetic phase transition; then we pass to define purity transition describing also its equivalence to the solvability/non-solvability transition for the Reconstruction Problem, for a +/ signal sent from the root to the boundary of the tree. This problem is equivalent to the extremality of the free boundary Gibbs measure for the Ising model. Here we give also a proof for the threshold of purity transition in the Ising model case; this is a simplification of that due to Peres and Pemantle[14]. In the second chapter we switch to the purity transition for the Potts model where the possible signal sent from the origin can assume q values i.e. 1,2,..., q instead of only two + or as in the former case. We give the first proof of our main result i.e. Theorem stated for Galton-Watson trees. A second alternative proof is given in the third chapter. This second proof is more general and it can be applied beyond the Potts model and, as an application, we treat the case of an asymmetric binary channels. For strongly asymmetric channels the bound we derive, improves the known threshold for this model [11]. When the asymmetry is small there exists a tight bound [8] that, until the present, we are not able to recover with our method. The last chapter is for comments and comparison with thresholds for purity transition obtained by others authors. We propose also some conjectures. The results of this part of the thesis are in: - M. Formentin, C. Külske, On the Purity of the free boundary condition Potts measure on random trees, to be published in Stochastic Processes and their Applications 2009, available at arxiv: , 2008; 16 Introduction to Part I - M. Formentin, C. Külske, A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees, preprint, available at arxiv: , Chapter 1 Ising model on trees: purity and reconstruction 1.1 Introduction This is an introductory chapter. We review the purity/non-purity phase transition and its equivalence with the non-solvability/solvability transition in the Reconstruction Problem on regular trees [9, 11]. We describe this equivalence to make intuitive the meaning of purity transition: to say that the Free Gibbs Measure is pure is to say that there is no transport of information along the tree, form the boundary to the root. In this chapter we deal mainly with the Ising model on regular trees for which we prove a bound for the purity transition. The proof is a simplification of [14]. The same method provides a proof of the ferromagnetic transition too. 1.2 Purity for the Ising model and reconstruction for binary channels In the next, the situation is as follows: we have a tree T, where we have chosen a special point, the root, that we denote by 0 see Figure 1.1. Recall that a graph is a set of the vertices called V, connected with edges, G, and that a tree is a graph without 19 1.2. Purity for the Ising model and reconstruction for binary channels 0 Figure 1.1: A tree rooted at 0. loop. Thus, on a tree there is a unique chain of edges γ from one vertex v to another vertex ω. This induces a natural notion of distance as the number of edges in γ. We write ω v if ω has a greater distance than v from the root. The set of vertices at distance from the root is the level of the tree. We indicates with T the sub-tree with just levels and with T the level : i.e. the boundary of the sub-tree. Moreover, Tv is the sub-tree of T rooted at v. The Ising model is obtained by putting at every vertex v of T a random variable ηv {+1, 1} also called spin, and assigning to every configuration η {+1, 1} #V the probability: P β β = 1 Z where Z is a normalization factor. v ω,ω v e βηvηw 1.1 The product runs over all the vertices; v ω, ω v means all the couples v,ω where v is at distance one from ω and ω is a child of v meaning that it has a greater distance to the origin. We can look at the parameter β as the strength of the interactions between vertices at distance one. Coming the Ising model from Physics, β is often interpreted as the inverse of the temperature. In 1.1 no boundary condition is specified, thus this is called the free Gibbs measure. 20 Chapter 1. Ising model on trees: purity and reconstruction When dealing with the ferromagnetic transition we are interested in P,+ β, where + means that we set to +1 all the spins in T. More precisely, we are interested in the limit: lim,+ P β η0 = We want to know if 1.2 is greater than 1 for a certain range of the parameter β. 2 Or, in other words, if for some values of β the plus-boundary condition persists to have influence at the root even when its distance from the root grows and tends to infinity. In this chapter we deal with regular tree of degree d. To us, the degree of a vertex is the number of its children and a tree will be said to be regular if all the vertices have the same degree. For a regular tree where the degree d is the same for every vertex one has the following: Theorem The inequality lim holds only if dθ 1, where θ = tanhβ. For a proof see [1, 14] or later in this chapter.,+ 1 P β η0 = +1 2, 1.3 So, ferromagnetic order on a tree is characterized by the fact that a plus-boundary condition at the leaves of a finite tree of depth persists to have influence to the origin when tends to infinity. From an heuristics point of view we can say that, if β is sufficiently large, there is a transport of information from the boundary of the tree to the origin even when goes to infinity. Actually, there is a way to make precise this information theoretic interpretation of the Ising model: i.e. to show that nonsolvabilty of the reconstruction problem is equivalent to the extremality of the free Gibbs measure. The Reconstruction Problem on symm

Related Search

Università degli Studi di Padova - DipartimenUniversità degli Studi di BresciaUniversità degli Studi di BariUniversità Degli Studi Di Napoli OrientaleUniversità degli Studi di FirenzeUniversità Degli Studi Di MilanoStoria degli studi classicidipartimento di studi umanistici università dDipartimento «Istituto Italiano Di Studi Oriepdf

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks