FROM STATISTICAL MECHANICS TO LARGE DEVIATIONS OF UNIFORMLY RANDOM d-REGULAR GRAPHS BY IBRAHIM UMAR (10167765) THIS THESIS IS SUBMITTED TO THE UNIVERSITY OF GHANA, LEGON IN PARTIAL FULFILMENT OF THE REQUIREMENT FOR THE AWARD OF MPHIL STATISTICS DEGREE JULY, 2017 DECLARATION I certify that this thesis is as a result of my original research work toward the award of a Master of Philosophy Statistics degree. I have faithfully and accurately cited all my sources, including, books, journals, and articles both published and unpublished. I also declare that no part of this work, wholly or partially, has been submitted for a degree in this university or elsewhere. SIGNATURE…………………………………….. DATE……………………………………………. IBRAHIM UMAR (CANDIDATE) SIGNATURE…………………………. DATE………………………………… DR. KWABENA-DOKU AMPONSAH (PRINC. SUPERVIOSOR) SIGNATURE……………………… DATE…………………………….... DR. ANANI LOTSI (CO-SUPERVISOR) i ABSTRACT A Large system is difficult to study globally. Its study requires some random procedure that can expose some of its properties to enable the identification of its typical behaviour. To this end, uniformly random regular graphs were generated due to their fascinating properties and applications. The Potts model was used to assign spin values to the vertices of the graph from a finite spin space. Errors do occur in large system rarely but when they do, their impact may cause some destruction. The randomness in rare events allows the use of probability theory to assess it. Large deviations principle measures the probabilities of rare event and the rate at which they occur. The aim of this thesis was to derive the Large Deviations Principle of the joint empirical spin and bond measures of the uniformly random -regular graphs. Subsequently, the rate function of the large deviation probabilities was derived. To achieve this, the method of types of the joint empirical measure was used. The rate function was expressed in terms of sum of the relative entropies of the joint empirical measures. The upper and lower bounds of the large deviation probabilities were formulated using the types and type class of the measures. It is recommended that to examine a large system, it is more parsimonious to find the large deviations of the interaction of its components which would describe vividly the typical behaviour of the system. ii DEDICATION I dedicate this thesis to my parents, Alhaji Umar Ibrahim and the late Husseinatu Khalid for their support and love. I also dedicate this work to my bosom friend and brother Abdul-Mumin Alhassan who has been most inspirational and supportive toward this cause. My dedications also go to my siblings Laila Ibrahim and Anwar Ibrahim. iii ACKNOWLEDGEMENT My utmost praises and thanks go to Allah, the Almighty for giving me such an opportunity to climb up the academic ladder. My heartfelt gratitude goes to my principal supervisor, Dr. Kwabena-Doku Amponsah whose encouragement and advice helped me to go through this thesis. I salute you for having the confidence in me to carry out this herculean task. My gratitude also goes to my co-supervisor, Dr. Anani Lotsi for his tips and guide. To all my hardworking lecturers, I say a big thank you for all the tuition and impartment they gave me throughout my stay here on campus. It was worthwhile. Finally, my appreciation goes to all my colleagues especially Augustine and Delalinam for their selflessness and warmest friendship. I appreciate you all and I ask God to bless you abundantly. iv TABLE OF CONTENTS DECLARATION............................................................................................................................ i ABSTRACT ................................................................................................................................... ii DEDICATION.............................................................................................................................. iii ACKNOWLEDGEMENT ........................................................................................................... iv TABLE OF CONTENTS ............................................................................................................. v CHAPTER ONE ........................................................................................................................... 1 1.0 Background of study ..................................................................................................... 1 1.2 Objective of Study ...................................................................................................... 10 1.3 Organization of Chapters ............................................................................................ 10 CHAPTER TWO ........................................................................................................................ 11 2.0 Introduction ................................................................................................................. 11 2.1 Graph Theory Definitions ........................................................................................... 11 2.2. Potts Model definitions .............................................................................................. 13 2.3 Large Deviation Definitions ....................................................................................... 14 CHAPTER THREE .................................................................................................................... 18 3.0 Introduction ................................................................................................................. 18 3.1 Generating uniform random regular graphs. ............................................................... 18 3.1.1 The Configuration Model ............................................................................ 19 3.2 The Potts Model Assignment ...................................................................................... 20 3.3 The Large Deviations of the Joint Empirical Vertex and Edge Measure ................... 21 3.3.1 Method of Types for Large Deviations Bounds .......................................... 22 CHAPTER FOUR ....................................................................................................................... 23 4.0 Introduction ................................................................................................................. 23 4.1 Preliminaries ............................................................................................................... 23 4.2 Large deviations probability of the joint empirical measure ...................................... 26 4.3 Large deviations Principles for the joint empirical measures ..................................... 31 v CHAPTER FIVE ........................................................................................................................ 36 5.0 Introduction ................................................................................................................. 36 5.1 Summary ..................................................................................................................... 36 5.2 Discussions ................................................................................................................. 36 5.3 Conclusions ................................................................................................................. 38 5.4 Recommendation and Future Work ............................................................................ 38 REFERENCES ............................................................................................................................ 40 vi CHAPTER ONE INTRODUCTION 1.0 Background of study Research in Graph Theory was initiated by Leonhard Euler in 1736. In the middle of the twentieth century another giant success was chalked by Erdos and Renyi (1960) when they introduced the thoughts of traditional random graphs. By the end of the 1990s an increasing number of original maps of extensive networks had become accessible and efforts were coordinated towards describing the newly perceived properties of these systems. In the recent past, graph theory has seen a lot of outstanding and enviable transformation. It has also become a very essential tool in mathematics and other disciplines like Chemistry, Genetics, Engineering, Geography, Sociology, Architecture, etc. At the same time it has become a discipline in mathematics that can stand the test of time. This change is largely due to the amount of information that we are faced with to handle in modern times. To handle such humongous information and datasets, one has to build and examine the network formed according to how they connect. Google’s search engine, for instance, works by using the World Wide Webs as the vertices (nodes) and the hyperlinks, which connect them, as edges. In the human system, the chemical compounds of a living cell are linked by biochemical reactions which convert one compound into another. The reactions are catalysed by enzymes. Therefore, all chemical compounds in a cell are like the vertices of a graph and the biochemical reactions between them are its edges (Proulx, Promislow & Phillips, 2005). A graph basically looks at the relationship between vertices and edges. This basic concept runs through most systems as mentioned earlier. The vertices are like the microscopic parts or subunits of a system while the edges are the interactions between these parts. For instance, the 1 social media (Facebook, Twitter, etc.), is a graph in which the individuals are the vertices and the relationship that exists between individuals is the edge. Several real-world problems can be explained through the use of graphs made up of a set of points (vertices) together with lines (edges) linking some pairs of these points. For instance, in a community, the people can be denoted by the points and whether a particular relationship exists between the people will be denoted by the presence or absence of a line between them. Also, in computer technology, communication centres might be represented by points and the link between them represented by lines. It is worthy of note that, in such systems our interest is in whether the points are connected by a line or not; the way they are linked is not so important. Again, the ability to assess the performance of a system depends largely on the information one has on the various components and the link among them. Our systems as humans are made up of various organs that work together to enable our organ systems function. A failure in one or more organs may affect the robustness of the system. A medical doctor needs to check the performance of one or more organs to enable him draw conclusion(s) on the performance of a particular system. Therefore it is imperative to have knowledge of the various parts of a network. A mathematical conception of circumstances of this sort offers ascend to the idea of a graph. The above examples are sufficient for making graph theory an invaluable and indispensable tool in modern times. In graph theory, a graph is defined as a pair of sets made up of a non-empty finite set V of elements called vertices and a set called edges E connecting the vertices. A graph G is denoted by ( ) (Bondy& Murty, 1976). Over one billion people use Facebook each month and over 140 billion friendship connections have been made between them (Facebook, 2012). Almost 10 billion electronic devices are able to connect to the Internet, exceeding the number of living people (IMS Research, 2012). Airports 2 around the world are connected with thousands of flights between them every day (Guimerá, Mossa, Turtsch & Amaral, 2005). These are just three examples of huge networks, a set of nodes with links between them. But these huge networks have a large number of elements and their growth is generally unpredictable. Therefore, an exact description of the state of each element of the system globally is utterly intractable if not impossible. Due to this challenge recent researches (in applications and in mathematics), are focused on neighbourhood description of graphs i.e. the number of vertices they have, the manner in which neighbouring vertices connect to one another, etc. These rules are not deterministic with certainty, indicating that there is a large amount of variations in how connections can be formed. Embracing a probabilistic notion, an observation of the system is treated as a realization of a random experiment. Probability theory offers an exceptionally viable methodology to deal with the complex networks, and therefore leads us to consider random graphs. Computer scientists have also discovered that NP- hard problems, when restricted to random graphs, have linear solutions making it a key tool in computer science (Bollabàs, 1999). A random graph is the probability distribution over graphs. It is a random procedure that generates the graphs (Bollabàs, 2001). Random graphs help in knowing the properties of a typical graph or system and therefore modeling it will not be too difficult since we know the random process that generated it. Using statistical theory, one can study the vertices of a random graph and the interactions between them through the edges that join them. The foundation of random graphs was laid by Paul Erd s and Alfréd Rényi towards the end of the 1950’s. The field remained grey until the next century when scientists discovered that many natural processes may be modeled using the random graph. This is because random graphs have large girth and chromatic number which make them very useful in small world networks. 3 A more interesting area to look at is the regularity of networks. For example having each node in an electrical network link to the same number of conductors and imagine further each person in a social network being connected to equal number of friends on Facebook. A graph is said to be regular if all the vertices have the same number of neighbours called degree. A regular graph where each vertex has degree three is termed a cubic graph. Empty graphs are regular graphs of zero degree. The probability distribution of all r- regular graphs is called a random r- regular graph. All regular graphs are connected and therefore have wide range of applications. They are among the most invaluable and fascinating models for random graphs. It has been pursued by a lot of scientists in different disciplines due to its obvious practical importance. Years on after the works of Erd s and Rényi, the study of random regular graphs began through the works of Bender and Canfield (1978) to Bollobas (1980) and Wormald (1999). The study of random regular graphs is as of late blooming, and some beautiful outcomes are newly rising, for example the almost doubtless properties that the edges can be partitioned into disjoint Hamilton cycles (when the degree is even).Its growth till date has been partly due to its applications in other areas such as computer science and statistical mechanics. Random regular graphs have been assuming a significant part in theoretical computer science, particularly in the theory of expanders. For instance, it is currently realised that a uniformly random d-regular graph has asymptotically the most ideal expansion rate, i.e., its second eigenvalue is almost surely , ( )-√ (Friedman, 2004). Again, it is used to find the eigenvalue of random matrices, whose utmost important is obvious. The observation of the behaviour of all the atoms of block of ice or the nodes on the internet or the boulders in an earthquake fault is impracticable (Sethna, 2006). Imagine for example, how 4 one can observe each of the components of a gas composed of a huge number of similar 30 particles, say 10 .That will be a herculean task, but having a reasonable description of such a humungous system would be of great help. A reasonable description means a theory capable of making prediction about some properties of the system, like how the gas will react to external forces or thermodynamic changes. Since the gas is made of particles, knowing the state of each particle is equivalent to knowing the state of the gas. But the study of the aggregate behaviour of the system cannot be possible from a deterministic description of its interacting units. Having no perfect information of the state of the system is tantamount to describing the system using probability theory, even though such systems show behaviours that are simple and striking. This theory founded by Boltzmann, Gibbs and others in the late 1800s is called Statistical Mechanics. Most often models in Statistical Mechanics are simplified through the usage of graphs and graph tools. The Potts model is a typical model which is endeared in Statistical Mechanics. The Potts model examines the microscopic part of a complex system to see how their energy interactions determine the aggregate behaviour of the system. Usually the vertices (sites) of a graph are assigned values from a finite set and internal interaction between sites is assigned by the edge that joins them. Thereafter, graph theory concepts are used to analyse the model. Kasteleyn and Fortuin (1969) were the first to model the relationship between Potts model and graph theory. They treated some networks like spanning trees, resistor network, and other problems related to graph theory in the form of a Potts model. The use of the Potts model has led to solving problems in statistical mechanics which hitherto were hard to crack. Later, the relationship between Potts model and the Tutte polynomial in graph theory was discovered to help to easily determine the Hamiltonian via the partition function (Essam & Tsallis, 1986). Ever since, this revelation has been expanded to include multisite correlation functions and their applications. Clearly, the role 5 of Potts model via graph theory cannot be over-emphasized. Its applications cut across wide areas including tumor migration, magnetism, foam behaviours and social demographics. Moreover, the connectivity of systems like the internet and its growth can be elucidated by using the statistical mechanics of network growth (Albert & Baraba'si, 2002), and graph theory properties can used to quantify the behaviour of amorphous solids (Franzblau, 1991). Rare events in a system are usually studied even though they are unlikely to occur but when they do the destruction they might cause could be very unbearable. For example, earth wakes and floods occur and cause devastation in communities therefore, their study cannot be ignored. Better still to be convinced that the study of rare events is important, consider winning a jackpot and the impact it will have on you. In the same vein, if the event is negative the impact will be severe and costly (Dembo & Zeitouni, 1998). Large Deviation Theory (LDT) is an aspect of probability theory that studies the asymptotic results of these unlikely event probabilities and the set of techniques to derive them. Its focus is on the exponential degeneration of probabilities of large variations of a random system about its most probable state (Touchette, 2009). It provides details of the most likely way the unlikely event occurs. It also provides exponential estimate probabilities that generalize Einstein's theory of fluctuations. The mathematics of large deviations theory was first started by Cramér (1938), and later developed by Donsker and Varadhan (1975, 1975, 1976, and 1983) and by Freidlin and Wentzell (1984). In Statistical Mechanics, it is able to create a mutual connection between entropy and free energy via the Legendre Transform and the explanation of this platform in Thermodynamics. The Law of Large Numbers (LLN) touches on convergence of an empirical distribution to its true value whilst the Central limit theorem looks at how close the distribution is to its true value. But any deviation that is significantly different from the true value is termed large and such 6 deviations are of higher order of in most cases, as against the order of √ which is considered ―normal‖ according to the Central Limit Theorem (CLT). So, the Weak Law of Large Numbers (WLLN) is a corollary of the large deviation theory. Large deviations theory has been useful to a diverse scope of issues in which in-depth statistics on rare events are needed. However, the theory is not applicable to all rare events but to only rare events that are caused by a large number of unlikely events working together but not a single event which cannot be partitioned into more than one sub-events. Moreover, the interest in rare events is not only about their occurrence but also in the typical behaviour of the system involved as the rare event happens. For instance, in communication systems and queuing theory, the rare event might denote an overload or failure of the system. For such situations, large deviations procedures can prompt an effective overhaul of the framework so that the over-burden or collapse would not happen. The theory of large deviations in statistical mechanics derives exact estimates of exponential order which are rightly appropriate for asymptotic analysis. In insurance a company may be interested in how much money they need to reserve against claims that exceed the expected number of claims significantly. It is obvious the company will like to minimize such claims especially when it exceeds the revenue and the reserves. That is because the company might be insolvent should the claims from policy holders exceed such conditions. Therefore the company must go the extra mile to find the amount of reserve that is adequate to guarantee that the probability of insolvency does not go beyond a pre-specified threshold, with large deviation theory one can find such estimates. Their application in insurance is quite innumerable from estimation of ruin probabilities to estimation of large portfolio losses, etc. It has other applications in electrical engineering for performance analysis. 7 In 1877, as a key note in his paper, Ludwig Boltzmann gave a probabilistic clarification of the second law of Thermodynamics by estimating the asymptotic behaviour of multinomial probabilities in terms of the relative entropy. This historic calculation by Boltzmann gave birth to the two concepts Large Deviations and Statistical Mechanics. In fact the mathematics of statistical mechanics, in general, is the theory of large deviations, just like differential geometry is the mathematics of general relativity. Ellis (1985) is recognized for giving what is maybe the most entire articulation of this opinion, in a book that has had a noteworthy influence in bridging the gap between large deviations and statistical mechanics. The possibility that statistical mechanics can be figured in the dialect of large deviations has likewise been communicated in various review papers, including one by Oono (1989) , two by Ellis (1995, 1999) , and the seminal paper of Lanford (1973), which is seen as the main work on large deviations and statistical mechanics. After these works showed up, more uses of large deviations have come to light. Most random graphs have unknown probability distributions but because of their relevance to diverse applications they are usually modeled using empirical measures. Empirical probability measures are utilised to compute approximations for a sequence of random variables whose probability distribution is unknown. With the empirical measure, the approximations get closer and closer to the true distribution for sufficiently large sample size. Large systems normally have unknown distributions and finding the bounds of their rare events would be daunting without adopting an alternative way which gives close approximation to its distribution. Large deviations of empirical measures have been studied extensively. Ellis (1988) and Acosta (1990) derived large deviations principle for multivariate empirical distributions of Markov chains. These works 8 were preceded by the works of Donsker and Varadhan (1975, 1976) whose ground-breaking work opened the way for large deviations on empirical measures of Markov chains. Similar works on Markov chains can be found in Cover and Choi (1987) and Natarajan (1986). In Bryc and Dembo (1995), it was shown that the large deviations properties of empirical measures of any continuous-time Gaussian process have spectral density which vanishes to infinity. For the same Gaussian processes, Bercu, Gamboa and Rouault (1997) proved that a Toeplitz quadratic form of the Gaussian process has rate function which can be expressed in terms of eigenvalues of two matrices. On randomly coloured graphs, Biggins and Penman (2009) studied the large deviations features of the number of edges in the graph and that of mixtures conditioning on whether or not an edge is presence. The joint large deviations of empirical pair and empirical neighbourhood measures were estimated in Doku-Amponsah and Mörters (2010) where the rate function was expressed in terms of the sum of relative entropies and Doku-Amponsah (2012) again computed good exponential approximations of the empirical neighbourhood measures of random graphs with symbols conditioned on a given empirical distribution of neighbourhood and pairs. Another interesting large deviations derivation was by Nyquist (2013) who generated the deviations for weighted empirical measures and processes that arise from importance sampling. See also Doku-Amponsah (2014, 2016) for more on geometric random graphs and their specific empirical measures. What most of these papers concentrated on was on simple random graphs whether coloured or finitely typed that is not replicated per vertex. Little work has been done on the large deviations of uniformly random regular graphs. That is the motivation for carrying out this study. 9 1.2 Objective of Study This thesis seeks to derive the large deviations principle of the joint empirical spin and bond measures of the Potts model on uniformly random regular graphs. The specific objective of this study is to estimate the rate function of the measure in terms of relative entropies. 1.3 Organization of Chapters The thesis is organised in chapters as below:  Chapter 1 gives some background and the motivation for studying large deviations on Potts model. It also makes a statement of the objective of the thesis and how the chapters are organised.  Chapter 2 deals with the various definitions and properties that will help understand the thesis adequately. Some important theorems to be used to achieve the desired results are also stated.  Chapter 3 looks at how to generate the uniformly random regular graphs and the Potts model. It will examine the Combinatorics of the Potts model on the uniformly random regular graphs generated.  In Chapter 4 presents the large deviation results for the joint empirical measure with some interpretations.  Chapter 5, the last chapter, draws the conclusion based on findings, make some recommendations and identify possible areas of future research work.  References, which contain the articles, books, publications, etc. cited in the thesis. 10 CHAPTER TWO DEFINITIONS AND PROPERTIES 2.0 Introduction This chapter examines some important concepts and principles in graph theory, Statistical Mechanics and Large Deviation Principles. 2.1 Graph Theory Definitions Definition 2.1.1. A graph G is a triple(  ), where V is a set of vertices or nodes, E is the edge set and is a map which associates to every edge to a pair of unordered vertices . If (e) a,b , then we say e is incident to and . If then e is said to be a loop. However, if two or more edges are incident to the same pair of vertices, then we have multiple edges and the graph is said to multi-edged. A graph is said to finite if | | | | , otherwise it is infinite. A graph G which is such that for any two vertices , ( ) ( ) is said to be a directed graph or digraph, otherwise G is said to be undirected An undirected, unweighted graph that has no loops or multiple edges is called a Simple Graph (Weisstein, 2001). In this thesis we consider only simple graphs where the connection of vertices is concerned not the direction in which they connect. Figure 2.1 illustrates the distinguishing features of the aforementioned graphs. 11 Figure 2.1: Types of Graphs Definition 2.1.2. Two vertices are said to be if there is an edge joining to . That is to say if such that ( ) . The of a vertex is the set of all vertices adjacent to . Denote a as the neighbourhood of . The of a vertex is the cardinality of its neighbourhood with loops counted twice and denote this by ( ). Hence, ( ) |a |. A graph whose vertices have the same degree is said to be a . A graph with fixed degree d is said to be . This thesis focuses on regular graphs because of their intriguing properties. Definition 2.1.3. are generated starting with n vertices and adding edges between them according to a random procedure. Different random graph models generate different probability measures. Let and , -. The probability space ( ) is the space of all undirected graphs with n vertices with an edge having probability p independently from other edges. More precisely, 12 ( ) ( ( ) ) where is the set of all undirected graphs with n vertices and is the probability measure on . This random graph is called the Erdȍs-Rényi graph. For any distinct vertices , p is the probability that the edge ( ) is present and if absent. The graph is a random element of ( ) so all labeled graphs with n vertices and m edges | | will be assigned a probability of ( ) , where | | ( ) is the maximum number of edges from n vertices. Another form of the Erdȍs-Rényi graph is the uniform random graph, .In this model there are two parameters; n and m with their usual definitions. The model assigns equal probability to each labeled graph G on the vertex set V with exactly m edges. More precisely the probability of G being selected is given by: ( ) | | , where | |. . / A regular graph which is generated according to a random procedure is called a random regular graph and if the graph is selected uniformly from the random regular graph it is called a uniformly random regular graph. The study of uniformly random regular graphs is central to this thesis. Definition 2.1.4. A graph G (n, p) has a property E if with high probability (w.h.p.) ( ) 2.2. Potts Model definitions Definition 2.2.1. Let A be a finite or countable set of properties and G be a graph. The assignment of a member of A to the vertex v in the graph G is called a .The set of all possible choices of spins at a vertex is termed the state of a spin. 13 Definition 2.2.2. A is any graph model in which every vertex of a graph G is assigned spin from a set of q-possible states. If the there are two states, up or down, the model is called the l and for states , the model is called the . These models are designed for simple graphs. 2.3 Large Deviation Definitions Definition 2.3.1. Let be a set of random variables, called finite alphabet. Let ( ) be the probability measure on . Then for any ( ), the between and is defined as the measure of the closeness between the two probability vectors. Denote by ( ), the variational distance. Thus d(, ) : sup (x)  (x)x (2.1) Definition 2.3.1. Let be a finite alphabet and : , - be two probability laws such that  (x) ,  v(x) 1 . Then the Entropy ( ) of is defined by x x H () :  (x) ln (x) (2.2) x The entropy, ( ) of a random variable is the estimation of the expected amount of information in its realization. It was first introduced by Shannon (1948). Von Neumann (1936) defines it as the difference between what is known from far and neighbouring distances. It measures the uncertainty associated with the random variable: it is the measure of the quantity of information needed on average to give a description of the random variable. In information theory it is measured in bits. 14 In addition we define the between two probability distributions and as the measure of the probability distance between them It is also called the and it is given by (x) H ( | v) :(x) ln (2.3) x v(x) 0 Where the conventions 0ln0  0 and 0ln  0 would be assumed. 0 It is the measure of the wastefulness assuming the distribution is used to describe the random variable when the actual distribution is . In Statistics it is the expectation of the logarithm of the likelihood ratio. Definition 2.3.2. Convex functions: A function is said to be if for all points and all , -, g a 1b  g(a) 1g b Definition 2.3.3. Jensen Inequality: A function which is real-valued and defined on an interval I is said to be convex if for all x1, x2..., x  I and scalars n 1,2...,k 0,1where n  k 1 , k1  n  n f k xk  k f xk  (2.4)  k1  k1 15 Definition 2.3.4 Convexity of Multivariate Functions Let be twice differentiable on the domain . Then is convex if and only if 2 f (x)  0 , , where  2 f (x) , the Hessian, is a symmetric matrix whose entries are the second-order partial derivatives of at and it is defined by : 2 2  f (x)  f (x) ij for xix j That is if the Hessian is positive semi-definite . Definition 2.3.5 Lower Semi-continuous Functions Let be a topological space, and let * + an extended real-valued function. Then f is said to be lower semi-continuous at if : , a neighbourhood of such that , ( ) ( ) or alternatively liminf f (x)  f (x0 ) where liminf is the limit inferior of f at . xx0 Definition 2.3.6 Rate Functions Let be a Polish space, i.e. a complete separable metric space and let I be an extended real- valued function i.e. , -. Then I is said to be a rate function if it is a lower semi- continuous function such that , - the sub-level sets * | ( ) + is a closed subset of . However I is said to be a good rate function if the level set is a compact subsets of . The rate function quantifies the probabilities of the unlikely events. 16 Definition 2.3.7. Large Deviations Principles Let be a topological space and a Borel sigma field where . Then the family of probability distributions * + satisfies the large deviation principle with rate function I if, for all inf I(x) lim inf logv ( ) lim sup logv ( ) inf I(x) x 0 0 x where and ̅ are the interior and closure of and is a convergent sequence. 17 CHAPTER THREE METHODOLOGY 3.0 Introduction This chapter outlines the methodology employed to achieve the objective of the study. In this regard, this chapter will first discuss the procedure used to generate uniformly random d-regular graphs. It goes further to use the Potts model of statistical mechanics to model the graph. Moreover, the chapter will elucidate the edge or pair empirical measure of the Potts model. Finally, the procedure used to determine the large deviations upper and lower bounds of the edge empirical measures of the Potts model will be discussed. 3.1 Generating uniform random regular graphs. The structure of a network (graph) affects its performance. For example, the topology of a social network influences the spread of information or diseases (Strogatz, 2001).Moreover, it is not easy to study the properties of a uniform regular random graph if it cannot be generated. The cardinality of the graph can only be found if the graph can be generated. It is a strenuous task to get a finite list of the graphs because of the existence of large number of regular graphs. A superior method to follow is the Configuration Model proposed by Bollabàs (1980) which was inspired in parts by Bender and Canfield (1978). The configuration or pairing model is used to generate firstly uniformly at random a set of multi-graphs (with loops and multi-edges) and conditioning on its distribution having no loops or multi-edges, a simple regular graph is generated. 18 3.1.1 The Configuration Model Let ( ) denote the set all labeled d-regular graphs on n vertices where is even since the sum of the vertices is twice the number of edges and . This graph has edges and n vertices. Then the random regular graph ( ) is a uniform member of ( ). Estimating the probability space of ( ) is an arduous task because the estimation of the cardinality of ( ) is equally herculean if not impossible. A better approach and alternative is illustrated below: Assume is even and . Consider a set of points partitioned into n cells v ,v ,...,v of 1 2 n points each. A perfect matching of the points into pairs is called a configuration or pairing. A configuration Y corresponds to a multigraph (Y) with the cells considered as vertices and the configurations as edges. A configuration or pair ( ) in Y corresponds to an edge ( ) of (Y) where and . Upon conditioning on the multigraph being simple, the graph sampled is uniformly selected from ( ). The sampled graph is the uniformly random d- regular graph ( ) required. This is the Configuration or Pairing Model by Bollabàs (1985). The configuration model has some fascinating features. First, the probability that is simple is bounded away from zero therefore, any property that is true asymptotically almost surely ( ) for is also true for ( ). Wormald (1999) showed that the probability that the multigraph is simple when d is large tends to zero extremely fast in d. However, if , most of the multigraphs will be non-simple. Again, it is usually simpler and less complicated to prove some properties in in ( ) explicitly. However, unconditionally multi-edged graphs with loops appear with smaller probability than simple graphs. This makes the Configuration Model a preferred one in generating random regular graphs. 19 3.2 The Potts Model Assignment Using the uniformly random regular graphs G generated spin values from the spin space were assigned to each vertex randomly. A spin system is defined for an n-vertex graph G with vertex set V and edge set E and integers on a space of configurations or assignments such that , - , - ,where , - * + and * + , -. When there are only two possible states the spin system is called the Ising model and when there are more than two state the model is called the Potts Model. It studies long term behaviour of complex systems. The model is able to investigate how the inner components of the system respond with each other in light of certain qualities that each component has. Naturally visible characteristics of the system will advance as these reactions occur. The Potts model has shown to be an exceptionally valuable tool, with diverse applications in fields such as Sociology, Physics, Biology and Chemistry. A q-state Potts model on a graph ( ) is a generalization of the Ising model in which there are q possible states at a vertex rather than the two up/down states. In this model introduced by Ashkin and Teller (1943) and Potts (1952), each node of the graph will be allotted a spin value from a finite set. The way the spins that are close to each combine determines which internal components will associate with each other. Possible spin values are magnetism (positive or negative), temperature (hot or cold), health (healthy, sick, or cancerous), direction (up, down or sideways) and colour (black, white, green, or yellow). Generally the spins are assumed to be where q =| |. The Ising model was developed by Ernst Ising in the 1920’s to study phase transitions. It has many significant applications like calculating the basic temperature for which the magnetism of a magnet is lost (Cipra, 2000). The Potts Model on the other hand has applications in simulation of foams for brewing, lubrication, oil recovery, and firefighting (Jiang, 1996). It is also applied in the study of cancerous tumors in humans (Sun, Chang & Cai, 2004). More so, it has been used in Sociology to study human behaviour. Schelling (1971) used features 20 of the Potts model to determine the possible causes of segregation in people. A slight modification of Schelling's model was done by Fouladvand and Darooneh (2005) to study the formation of Ghettos in inner cities. As stated earlier, the graph or lattice used in these experiments is regular because of the interesting features they have. A very important component of the Potts Model is its Hamiltonian. The Hamiltonian measures the total energy of the model due to the interactions between adjacent spins. It measures the number of edges of a particular spin value. Usually, the interacting edges are assigned values based on how the vertices (sites) interact. However, changing spin values would lead to a different Hamiltonian. In fact, there are as many as | | possible states of the Potts model on the graph. Clearly, the Hamiltonian depends on the manner of interaction of spins via the edges hence any model that can provide information about these two would go a long way to help interpret the model better. 3.3 The Large Deviations of the Joint Empirical Vertex and Edge Measure The joint empirical measure of the Potts model enumerates the number of edges connecting any given pairs of spins and the number of vertices of a particular spin. Since each vertex was assigned the discrete spin values uniformly and independently at random from the spin set the empirical edge measure is independently and identically distributed (IID). The probability distribution of the joint empirical measure is multinomial. To derive the large deviations approximations in exponential rates, the weakly convergence of the multinomial distribution to the exponential was used. Combinatorial procedure and Stirling's approximations were used to express the probability distribution in exponential form. The rate function was then extracted from the probability distribution and was specifically written in terms of relative entropies. 21 Finally, Method of Types was used to formulate the large deviations principles for the joint empirical measure, showing its lower and upper bounds. 3.3.1 Method of Types for Large Deviations Bounds The method of types is one of the main procedural tools in information theory and it is invaluable also in several other fields like Statistical Mechanics, Computer Science, etc. The method associates a probability mass function (distribution) called a type to each sequence of symbols drawn from a random variable say X over a finite alphabet . The main idea behind the method of types is that a good bound can be obtained on the probability that an empirical measure takes a particular type from the collection of all types called type class. And by computing the type class, large deviations upper and lower bounds can be found. It is even used to derive Sanov's theorem for IID random variables. That is how powerful the method is. Method of types is used to generate the type and its large deviations probabilities. 22 CHAPTER FOUR STATEMENT OF RESULTS 4.0 Introduction In this chapter, the results are presented using the stipulated approach in chapter three. Firstly a preliminary or background for the method of types is given. Secondly, the large deviations probabilities of the joint empirical measure and its rate function are derived. Lastly the lower and upper bounds for the large deviations probability are formulated using the Method of Types. 4.1 Preliminaries Let be a finite set of spins of the -state Potts model and as already denoted G(n, d) is the set of all uniformly random d-regular graphs with n vertices, fixed degree d and spin set . The following are noteworthy:  | | ( )  { } for the configuration model via the half-edges  The spin set on the q-state Potts model is * + , - For each spin assignment, let the empirical spin measure be defined by 1 L (x)  1(  x), for x  q 1 n iiV and a symmetric finite measure, the empirical bond measure by 1 L 2 x,y  :  1 ,   x,y   1 ,   x,y , for x,y  qnd  i j j i   i,jV 23 The spin measure , measures the proportion of vertices assigned a particular spin value from the Potts Model while the bond empirical measure, is the proportion of the bonds of the graph ( ) that are assigned the spin value , -. In other words it is the number of occurrences of spin pairs ( ) from the Potts model over , - on the graph G. Let and be the space of all probability distributions on , - and , - endowed with the topology generated by the total variation norm. Therefore, L1and L2 . The collection of types constitute elements which are types and contains information on how often each value shows up in the sample irrespective of the order in which they appear. Definition 4.2. For the q-state Potts model on the graph G let   i  , where , -, be the probability distribution on , - and    ij  , where , - be the probability distributions on , - such that for all , -. Then ( ) is said to be admissible for the graph G on n vertices and half-edges if , are integers for all , - and  ij  ji , iq . j j In other words, the marginal distribution of is in all dimensions, i.e. . Let   be the product measure of the product distribution i j  where , -. 24 Definition 4.3: Large Deviations Probabilities Let ( ) be admissible for the graph ( ). Moreover, let the be a partition of the vertex set V such that V   n for all iq . Let , - , - be the spin law for . Then i i F N M P (L ,L ) ( , )1 2 (4.1) N where q  n  F ( (i))  (4.2) n1,n2 ,...,ni1 q  enumerates the total number of spins that are assigned to each of the n sites of the Potts model on q nd i N nd ,nd , ...nd i 1 i1 i2 iq q (nd ) ! i i 1 (4.3) q q (nd ) ! ij i 1 j 1 also measures the total number ways of assigning spin values to the half-edges while q q M (nd ij (nd ij (4.4) i j i j calculates the number of matchings of half edges respecting the spin assignment 25 and N (nd 1) (4.5) is the total number of possible matching of the half edges 4.2 Large deviations probability of the joint empirical measure Lemma 4.2 Let ( ) be admissible for the uniformly random regular graphs ( ) with spin law .Then for the pair ( ) nd logP (L ,L ) ( , ) nH( | ) H( | ) o(logn) (4.6) 1 2 2 Proof: To obtain the large deviation probabilities in exponential form, Stirling’s Approximation in the refined form is required i.e. logn n logn n o(logn) (4.7) where means natural logarithm, and the relationship between the double factorial and Stirling’s approximation n n log n 1) logn o(logn) (4.8) 2 2 Taking the natural logarithm of both sides of (4.2) gives q q logF log ( (i)) logn ! log(n i)! (4.9) i 1 i 1 and applying (4.7) to (4.9) yields 26 q q q logF n i log i n logn n n i log(n i ) n i i 1 i 1 i 1 q q q q n i log i n logn n n i log( i ) n i logn n i i 1 i 1 i 1 i 1 q But i 1 i 1 q q Hence logF n i log i n logn n n i log( i ) n logn n i 1 i 1 q q n i log i n i log( i ) i 1 j 1 Further factorizing and applying basic logarithm rule gives q logF n i log i i 1 i q n i log i i 1 i logF nH( | ) (4.10) Next, taking natural logarithm of both sides of (4.3) we have q q log N log ndi !log nd ij ! (4.11) i1 i, j1 Applying (4.7) to (4.11) results to q q q q log N ndi log ndi ndi nd ij log nd ij nd ij i1 i1 i, j1 i, j1 q q q q q q ndi log nd ndi logi ndi nd ij log nd nd ij log ij nd ij i1 i1 i1 i, j1 i, j1 i, j1 27 q q sin cei 1and ij 1 i1 i, j1 q q  log N  nd log nd  ndi logi  nd  nd log nd  nd ij log ij  nd i1 i, j1 q q  ndi log  nd ij log ij i1 i, j1 q But  ij  i j1 q q  log N  ij logi  nd ij log ij i, j1 i, j1 q  log N  nd iij log (4.12)  i, j1 ij Now considering (4.4) and taking natural log of both side it becomes q q 1 log M  nd ij !nd ij 1!! (4.13) 2 i j i j Applying (4.7) to (4.13) simplifies to   q q   1  nd ij !  log M   log nd ij ! log 2   nd ij i j i j   nd ij 2 2     !    2   28 q q q q 1 nd  nd ij   log M   log nd ij ! log nd ij !  ij log2  log  !2 2 2 i j i j i j i j   q q q q 1  nd     ij  nd   log nd ij ! log nd ij ! log  !2 2 2  ij log2 i j i j i j   i j Applying (4.8) it follows that q q q q 1  nd ij  nd log M   log nd ij ! log nd ij !2  log  !  ij log22 2 i j i j i j   i j q 1   nd ij log nd   ij  nd ij2  i j q  nd ij  nd ij  nd ij nd ij   nd ij log nd ij  nd ij  log     log 22 2 2 2 i j     q 1   nd  ij log nd ij  nd ij2  i j q  nd ij nd ij ndvij   nd ij log ij  nd ij log nd   log nd  log ij  i j  2 2 2  q q 1 nd  ij nd ij nd ij    nd ij log nd  nd ij ij   log ij   log nd  2  2 2 2i j i j  q q 1 1  nd ij log ij  nd ij log nd  nd   ij  nd ij log ij  nd ij log nd  nd ij 2 2  i j i j q 1   nd ij log ij  nd ij log nd  nd ij2  i, j1 q q q q nd nd log nd nd   ij logij   ij   ij But ij 12 2 2 i, j1 i, j1 i, j1 i, j1 29 q nd nd nd logM 2 ij log ij lognd (4.14) 2 2 i, j 1 Finally, taking log of both sides of (4.5) and applying (4.8) to it gives nd nd log N  nd log(nd )  log(nd)  2 2 nd nd logN lognd (4.15) 2 2 Taking log of both sides of (4.1) and substituting each of equations (4.10), (4.12), (4.14) and (4.15) into it gives logP (L ,L ) ( , ) logF logN logM log 1 2 v q q nd nd nd nH( | ) nd log i log lognd ij 2 ij ij 2 2 i,j ij i,j 1 nd nd lognd o(logn) 2 2 q q nd nH( | ) nd log i log o(logn) ij 2 ij ij i,j ij i,j 1 q q nd nd 2 nH( | ) log log i o(logn) 2 ij ij 2 ij i,j 1 i,j 1 ij q nd 2 nH( | ) log i o(logn) But 2 for i j                  2 ij i i j i,j 1 ij q nd logP (L ,L ) ( , ) nH( | ) log i j o(logn) 1 2 2 ij i,j 1 ij q q nd i j nd ij But log log 2 ij 2 ij i,j 1 ij i,j 1 i j nd H( ) 2 30 nd logP (L ,L ) ( , ) nH( | ) H( ) o(logn) (4.16) 1 2 2 which completes the proof of Lemma 4.1. From (4.16) the rate function of the large deviations probabilities P (L ,L ) ( , ) can be 1 2 extracted as follows: d logP (L ,L ) ( , ) n H( | ) H( ) o(logn) 1 2 2 d Now let I( , ) H( | ) H( ) 2 P (L ,L ) ( , ) o(n)exp( nI( , )) 1 2 Therefore the rate function is given by d H( | ) H( ), if ( , )is admissible I( , ) 2 (4.17) otherwise. Since the rate function is expressed in terms of relative entropies, it has the expected properties of entropy. That is 1. ( ) and degenerates when or or both; 2. I  ρ,ν is a convex function. This can be seen from the fact that its Hessian is positive semi-definite; 3. I  ρ,ν is lower semi-continuous and its compact set are closed obviously. 4.3 Large deviations Principles for the joint empirical measures Theorem 4.3 Suppose that ( ) is a Potts Model on d-regular graphs with spin law i.e. :, - , -. Let be a Borel subset of . Then the pair (L ,L ) obeys an LDP on with speed and 1 2 convex good rate function ( ) in the following sense: 31 1 1 inf I( , ) lim inf logP (L ,L ) lim sup logP (L ,L ) n n 1 2 n n 1 2 (4.18) inf I( , ) c where are the interior and closure of respectively. Proof: Let n : {( , ) : (L1,L2) ( , )} In other words, n is the set of all possible types of (L1,L2) of size n in . The empirical pair measures has cardinality (n+1) since elements of (L ,L )belong to the set { }. 1 2 .Again, each type has cardinality (n+1) and is specified by not more than for the edge measure and q for the spin measure (Dembo & Zeitouni, 1998). Then it can be observed that for the joint empirical, measure n (n 1) 2 But q and q (n 1)q(1 q)n (4.19) Now, let be a Borel subset of Next P (L ,L )1 2 is decomposed as follows: P (L ,L ) P (L ,L ) ( , ) 1 2 1 2 ( , ) c n 32 Now for the Upper bound, P (L ,L ) P (L ,L ) ( , ) 1 2 1 2 ( , ) n sup P (L ,L ) ( , ) n 1 2 ( , ) c n c q(1 q) But But (n 1)n P (L ,L ) (n 1)q(1 q)1 2 sup P (L1,L2) ( , ) ( , ) c n q(1 q) P (L1,L2) (n 1) exp( n inf I( , ) ) (4.20) ( , ) c n 1 Taking normalized logarithmic limit of (4.20) and the fact that lim log(n 1)q(1 q) 0 gives n n 1 lim P (L ,L ) lim inf I( , ) n n 1 2 n ( , ) c n 1 lim sup P (L ,L ) lim sup inf I( , ) n n 1 2 n ( , ) c n lim sup( inf I( , ) n ( , ) c n lim inf( inf I( , )) n ( , ) c n lim inf( inf I( , )) n ( , ) c n inf I( , ) ( , ) c n But for all n, c c n inf I( , ) inf I( , ) ( , ) c n ( , ) c Hence, the upper bound of (4.18) follows as 33 1 lim P (L ,L ) inf I( , ) (4.21) n n 1 2 ( , ) c n For the Lower Bound, again P (L ,L ) P (L ,L ) ( , ) 1 2 1 2 ( , ) n But P (L ,L ) ( , ) exp( nI( , )) 1 2 (n 1) q(1 q) exp( nI( , )) P (L ,L ) (n 1) q(1 q) exp( nI( )) (4.22) 1 2 c 2 n And taking normalized logarithmic limit of (4.22) as with(4.20) gives 1 1 lim logP (L ,L ) lim log(n 1) q(1 q)1 2 lim inf I( , )n n n n n ( , ) c n lim inf I( , ) n ( , ) c n Taking the infimum of both sides results in 1 lim inf P (L1,L2) lim inf inf I( , )n n n ( , ) c n inf I( , ) ( , ) c n But o c cn Therefore, the lower bound of (4.18) is 1 lim infP (L1,L2) inf I( , ) n n ( , ) o (4.23) 34 For the middle inequality, since infA supA, for any set A, it is obvious that 1 1 lim inf logP (L ,L ) lim sup P (L ,L ) (4.24) n n 1 2 n n 1 2 Hence from (4.21),(4.23) and (4.24) the LDP 1 1 inf I( , ) lim inf logP (L ,L ) lim sup logP (L ,L ) 1 2 1 2 ( , ) o n n n n inf I( , ) ( , ) c 35 CHAPTER FIVE SUMMARY, DISCUSSIONS AND CONCLUSIONS 5.0 Introduction In this concluding chapter, the summary, findings, discussions and conclusions of the study are presented. Further, some few recommendations are mentioned and a statement of future work made. 5.1 Summary The overriding aim of this thesis was to determine the joint large deviations principle of the empirical spin and bond measures of the uniformly random d-regular graphs via the Potts model of Statistical Mechanics. To this end, it was important to achieve some pre-requisite goals. First, the uniformly random d-regular graphs were generated using the Configuration Model. Further, the Potts model was used to assign spin values to the vertices of the graph randomly. More so, the joint probability distributions of the two empirical measures was determined and later converted to joint large deviation probabilities using the principle of weak convergence and Stirling's approximations. The rate function of the measure was deduced from the large deviations probability and expressed explicitly in terms of relative entropies of both the spin and bond measures. Finally, Method of Types was used to formulate the joint large deviations principles of the empirical measures. 5.2 Discussions The rate function is the most important part of the large deviation as it characterizes the rare behaviour of the graph and the most likely way an unlikely event will occur. It quantifies and bounds the probabilities of the rare event. Further, it highlights on how the major components of the graph namely: the edges and the vertices, relate in the whole graph. The rate function of the 36 pair empirical measure (L ,L ) is non-negative and decreases exponentially when 1 2 .and The typical behaviour of the graph is found whenI( , ) 0 and that will only happen when and In other words, the most probable behaviour of the graph is that the bond empirical measure will be the same as the product measure of the spin empirical measure and the This means that the edge empirical measure gives us more information compared to using the vertex measure of the graph. In effect the edge empirical measure is more efficient than the vertex measure. Though, the rate was expressed in terms of the sum of relative entropies, there is a unique feature of the entropies. The factor in the relative entropy of the bond measure is because spin assignments on a bond are symmetric as mentioned in Chapter 2. This was evident in Doku (2016). The unique feature is the factor in the bond empirical measure and its appearance is due to the graph being cloned with degree . For a 2-degree random regular graph the rate function will be exactly equal to the sum of the relative entropies. As an application, in Statistics and Decision theory one is mostly torn between two decisions. For example an extension officer might want to know whether a new fertilizer is efficient or not. In basic terms, he is torn between two probability distributions. This is an area in hypothesis testing in a more general setting. One would have to reduce the type II probability error by finding the rate at which it decreases in terms of relative entropies and this can be estimated using the LDP. In Machine Learning, it is sometimes necessary to decide whether a characteristic A of a machine should be rejected conditioned on if another characteristic B depends on it or not. To arrive at this decision, Independence Testing, using the LDP via the rate function stated in terms of the relative entropies, is employed. The distributions embedded in the 37 relative entropies would help to come out with the independence or dependence between the two decisions. 5.3 Conclusions This thesis reports that the pair empirical measure (L ,L ), of the uniformly random -regular 1 2 graphs  has large deviations probability P (L ,L ) ( , ) o(n).exp( nI( , )) 1 2 whereI( , ) is the rate function expressed in terms of relative entropies H( | )and H( / )  the large deviations principle of the family of laws P (L ,L ) with rate and rate 1 2 functionI( , ) is given by 1 1 inf I( , ) lim inf logP (L ,L ) lim sup logP (L ,L ) o n n 1 2( , ) n n 1 2 inf I( , ) ( , ) c 5.4 Recommendation and Future Work It is recommended that to examine a large system, it is more parsimonious to find the large deviations of the interactions of components which would describe vividly the typical behaviour of the system. 38 An area that is worth exploring in future is looking into is the possibility of finding the joint large deviations principles of the empirical measures of exponential random graphs. Exponential graphs are widely used on social networks or what is called small networks. 39 REFERENCES Ashkin, J., & Teller, E. (1943). Statistics of two-dimensional lattices with four components. Physical Review, 64(5-6), 178. Bender, E. A., & Canfield, E. R. (1978). The asymptotic number of labeled graphs with given degree sequences. Journal of Combinatorial Theory, Series A, 24(3), 296-307. Bercu, B., Gamboa, F., & Rouault, A. (1997). Large deviations for quadratic forms of stationary Gaussian processes. Stochastic Processes and their Applications, 71(1), 75-90. Biggins, J. D., & Penman, D. B. (2009). Large deviations in randomly coloured random graphs. Electronic Communications in Probability, 14, 290-301. Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1(4), 311-316 Bollobás, B. (2001). Random graphs. 2001. Cambridge Stud. Adv. Math Bondy, J. A., & Murty, U. S. R. (1976). Graph theory with applications, 290. Bryc, W., & Dembo, A. (1995). On large deviations of empirical measures for stationary Gaussian processes. Stochastic processes and their applications, 58(1), 23-34. Cipra, B. (2000). Statistical physicists phase out a dream. Science, 288(5471), 1561-1562. Cramér, H. (1938). Sur un nouveau théoreme-limite de la théorie des probabilités. Actualités scientifiques et industrielles, 736(5-23), 115. Csiszár, I., Cover, T., & Choi, B. S. (1987). Conditional limit theorems under Markov conditioning. IEEE Transactions on Information Theory, 33(6), 788-801. 40 Dembo, A., & Zeitouni, O. (1998). Large deviations techniques and applications Second edition. Large deviations techniques and applications, 38. Doku-Amponsah, K. (2012). Exponential approximation, method of types for empirical neighbourhood measures of random graphs by random allocation. arXiv preprint arXiv:1212.4281. Doku-Amponsah, K. (2014). Large deviation result for the empirical locality measure of typed random geometric graphs. arXiv preprint arXiv:1406.3167. Doku-Amponsah, K. (2014). Large deviations for number of edges of near intermediate random geometric graphs. arXiv preprint arXiv:1406.3171. Doku-Amponsah, K., & Mörters, P. (2010). Large deviation principles for empirical measures of colored random graphs. The annals of Applied Probability, 20(6), 1989-2021. Doku-Amponsah, K. (2016). Joint large deviation result for empirical measures of the coloured random geometric graphs. SpringerPlus, 5(1), 1140. Donsker, M. D., & Varadhan, S. S. (1975). Asymptotic evaluation of certain Markov process expectations for large time, I. Communications on Pure and Applied Mathematics, 28(1), 1-47. Donsker, M. D., & Varadhan, S. R. S. (1975). Asymptotic evaluation of certain Markov process expectations for large time, II. Communications on Pure and Applied Mathematics, 28(2), 279-301. 41 Donsker, M. D., & Varadhan, S. R. S. (1976). Asymptotic evaluation of certain Markov process expectations for large time—III. Communications on pure and applied Mathematics, 29(4), 389-461.Donsker, M. D., & Varadhan, S. R. S. (1983). Asymptotic evaluation of certain Markov process expectations for large time. IV. Communications on Pure and Applied Mathematics, 36(2), 183-212. Ellis, R. S. (1985). Large deviations and statistical mechanics. Particle systems, random media and large deviations,(Brunswick, Maine, 1984), 41, 101-123. Ellis, R. S. (1995). An overview of the theory of large deviations and applications to statistical mechanics. Scandinavian Actuarial Journal, 1995(1), 97-142. Ellis, R. S. (1999). The theory of large deviations: from Boltzmann’s 1877 calculation to equilibrium macrostates in 2D turbulence. Physica D: Nonlinear Phenomena, 133(1), 106-136. Erdos, P., & Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1), 17-60. Essam, J. W., & Tsallis, C. (1986). The Potts model and flows. I. The pair correlation function. Journal of Physics A: Mathematical and General, 19(3), 409. Facebook. One Billion Fact Sheet. Available from:http://newsroom.fb.com/download- media/4227, (2012) Franzblau, D. S. (1991). Computation of ring statistics for network models of solids. Physical Review B, 44(10), 4925. 42 Freidlin, M. I., & Wentzell, A. D. (1998). Random Perturbations. In Random Perturbations of Dynamical Systems, 15-43. Friedman, J. (2003, June). A proof of Alon's second eigenvalue conjecture. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 720-724. IMS Research. Internet Connected Devices Approaching 10 Billion, to exceed 28 Billion by 2020. Press Release, available from: http://imsresearch.com/, (2012). Jiang, Y. (1996). Extended large-Q Potts model simulation of foam drainage. Philosophical Magazine Letters, 74(2), 119-128. Kasteleyn, P. W., & Fortuin, C. M. (1969). Phase transitions in lattice systems with random local properties. Journal of the Physical Society of Japan Supplement, 26, 11. Lanford, O. (1973). Entropy and equilibrium states in classical statistical mechanics. Statistical mechanics and mathematical problems, 1-113. Natarajan, S. (1985). Large deviations, hypotheses testing, and source coding for finite Markov chains. IEEE Transactions on Information Theory, 31(3), 360-365. Nyquist, P. (2013). Large deviations for weighted empirical measures and processes arising in importance sampling (Doctoral dissertation, KTH Royal Institute of Technology). Oono, Y. (1989). Large deviation and statistical physics. Progress of Theoretical Physics Supplement, 99, 165-205. 43 Potts, R. B. (1952, January). Some generalized order-disorder transformations. In Mathematical proceedings of the cambridge philosophical society, 48(1), 106-109. Proulx, S. R., Promislow, D. E., & Phillips, P. C. (2005). Network thinking in ecology and evolution. Trends in ecology & evolution, 20(6), 345-353. R. Guimerà, S. Mossa, A. Turtschi and L.A.N. Amaral. The worldwide air transportation network: anomalous centrality, community structure, and cities’ global roles.Proceedings of the National Academy of Sciences, 102(22):7794–7799, (2005). Schelling, T. C. (1971). Dynamic models of segregation. Journal of mathematical sociology,1(2), 143-186. Sethna, J. (2006). Statistical mechanics: entropy, order parameters, and complexity, 14, Oxford University Press. Sun, L., Chang, Y. F., & Cai, X. (2004). A discrete simulation of tumor growth concerning nutrient influence. International Journal of Modern Physics B, 18(17n19), 2651- 2657. Touchette, H. (2009). The large deviation approach to statistical mechanics. Physics Reports, 478(1), 1-69. Weisstein, E. W. (2001). Simple Graph Wormald, N. C. (1999). Models of random regular graphs. London Mathematical Society Lecture Note Series, 239-298. Wu, F. Y. (1982). The potts model. Reviews of modern physics, 54(1), 235. 44 Zeitouni, O., & Zelditch, S. (2010). Large deviations of empirical measures of zeros of random polynomials. International Mathematics Research Notices, 2010(20), 3935-3992. 45