It is widely believed that the scaling limit of the self-avoiding walk (SAW) is given by Schramm's SLE₈/₃. In fact, it is known that if SAW has a scaling limit which is conformally invariant, then the distribution of such a scaling limit must be given by SLE₈/₃. The purpose of this paper is to study the relationship between SAW and SLE₈/₃, mainly through the use of restriction measures; conformally invariant measures that satisfy a certain restriction property. Restriction measures are stochastic processes on randomly growing fractal subsets of the complex plane called restriction hulls, though it turns out that SLE₈/₃ measure is also a restriction measure. Since SAW should converge to SLE₈/₃ in the scaling limit, it is thought that many important properties of SAW might also hold for restriction measures, or at the very least, for SLE₈/₃. In [DGKLP2011], it was shown that if one conditions an infinite length self-avoiding walk in half-plane to have a bridge height at y-1, and then considers the walk up to height y, then one obtains the distribution of self-avoiding walk in the strip of height y. We show in this paper that a similar result holds for restriction measures ℙ(α), with α ∈ [5/8,1). That is, if one conditions a restriction hull to have a bridge point at some z ∈ ℍ, and considers the hull up until the time it reaches z, then the resulting hull is distributed according to a restriction measure in the strip of height Im(z). This relies on the fact that restriction hulls contain bridge points a.s. for α ∈ [5/8,1), which was shown in [AC2010]. We then proceed to show that a more general form of that result holds for restriction hulls of the same range of parameters α. That is, if one conditions on the event that a restriction hull in ℍ passes through a smooth curve γ at a single point, and then considers the hull up to the time that it reaches the point, then the resulting hull is distributed according to a restriction hull in the domain which lies underneath the curve γ. We then show that a similar result holds in simply connected domains other than ℍ. Next, we conjecture the existence of an object called the infinite length quarter-plane self-avoiding walk. This is a measure on infinite length self-avoiding walks, restricted to lie in the quarter plane. In fact, what we show is that the existence of such a measure depends only on the validity of a relation similar to Kesten's relation for irreducible bridges in the half-plane. The corresponding equation for irreducible bridges in the quarter plane, Conjecture 4.1.19, is believed to be true, and given this result, we show that a measure on infinite length quarter-plane self-avoiding walks analogous to the measure on infinite length half-plane self-avoiding walks (which was proven to exist in [LSW2002] exists. We first show that, given Conjecture 4.1.19, the measure can be constructed through a concatenation of a sequence of irreducible quarter-plane bridges, and then we show that the distributional limit of the uniform measure on finite length quarter-plane SAWs exists, and agrees with the measure which we have constructed. It then follows as a consequence of the existence of such a measure, that quarter-plane bridges exist with probability 1. As a follow up to the existence of the measure on infinite length quarter-plane SAWs, and the a.s. existence of quarter-plane bridge points, we then show that quarter plane bridge points exist for restriction hulls of parameter α ∈ [5/8,3/4), and we calculate the Hausdorff measure of the set of all such bridge points. Finally, we introduce a new type of (conjectured) scaling limit, which we are calling the fixed irreducible bridge ensemble, for self-avoiding walks, and we conjecture a relationship between the fixed irreducible bridge ensemble and chordal SLE₈/₃ in the unit strip {z ∈ ℍ : 0 < Im(z) < 1}.

In this thesis, motivated by modelling polymers, the topological entanglement complexity of systems of two self-avoiding polygons (2SAPs), stretched polygons and systems of self-avoiding walks (SSAWs) in a tubular sublattice of Z3 are investigated. In particular, knotting and linking probabilities are used to measure a polygonfs selfentanglement and its entanglement with other polygons respectively. For the case of 2SAPs, it is established that the homological linking probability goes to one at least as fast as 1-O(n^(-1/2)) and that the topological linking probability goes to one exponentially rapidly as n, the size of the 2SAP, goes to infinity. For the case of stretched polygons, used to model ring polymers under the influence of an external force f, it is shown that, no matter the strength or direction of the external force, the knotting probability goes to one exponentially as n, the size of the polygon, goes to infinity. Associating a two-component link to each stretched polygon, it is also proved that the topological linking probability goes to unity exponentially fast as n&rightarrow;&infin;. Furthermore, a set of entangled chains confined to a tube is modelled by a system of self- and mutually avoiding walks (SSAW). It is shown that there exists a positive number &gamma; such that the probability that an SSAW of size n has entanglement complexity (EC), as defined in this thesis, greater than &gamma;n approaches one exponentially as n&rightarrow;&infin;. It is also established that EC of an SSAW is bounded above by a linear function of its size. Using a transfer-matrix approach, the asymptotic form of the free energy for the SSAW model is also obtained and the average edge-density for span m SSAWs is proved to approach a constant as m&rightarrow;&infin;. Hence, it is shown that EC is a ggoodh measure of entanglement complexity for dense polymer systems modelled by SSAWs, in particular, because EC increases linearly with system size, as the size of the system goes to infinity.

In this thesis, motivated by modelling polymers, the topological entanglement complexity of systems of two self-avoiding polygons (2SAPs), stretched polygons and systems of self-avoiding walks (SSAWs) in a tubular sublattice of Z3 are investigated. In particular, knotting and linking probabilities are used to measure a polygonfs selfentanglement and its entanglement with other polygons respectively. For the case of 2SAPs, it is established that the homological linking probability goes to one at least as fast as 1-O(n^(-1/2)) and that the topological linking probability goes to one exponentially rapidly as n, the size of the 2SAP, goes to infinity. For the case of stretched polygons, used to model ring polymers under the influence of an external force f, it is shown that, no matter the strength or direction of the external force, the knotting probability goes to one exponentially as n, the size of the polygon, goes to infinity. Associating a two-component link to each stretched polygon, it is also proved that the topological linking probability goes to unity exponentially fast as n&rightarrow;&infin;. Furthermore, a set of entangled chains confined to a tube is modelled by a system of self- and mutually avoiding walks (SSAW). It is shown that there exists a positive number &gamma; such that the probability that an SSAW of size n has entanglement complexity (EC), as defined in this thesis, greater than &gamma;n approaches one exponentially as n&rightarrow;&infin;. It is also established that EC of an SSAW is bounded above by a linear function of its size. Using a transfer-matrix approach, the asymptotic form of the free energy for the SSAW model is also obtained and the average edge-density for span m SSAWs is proved to approach a constant as m&rightarrow;&infin;. Hence, it is shown that EC is a ggoodh measure of entanglement complexity for dense polymer systems modelled by SSAWs, in particular, because EC increases linearly with system size, as the size of the system goes to infinity.

Arbetet undersökte om det är möjligt att procedurellt generera giltiga och underhållande racerbanor för Formel 1 genom användandet av Voronoi diagram och self-avoiding random walk. En procedurell algoritm skapades och två enkäter konstruerades för att undersöka denna algoritms underhållningsvärde. Dessa enkäter distribuerades till kunniga individer inom racinggenren. Både algoritmen som helhet och dess dynamiska parametrar undersöktes. Det fastställdes att det är möjligt att procedurellt generera Formel 1 racerbanor som är underhållande med detta tillvägagångssätt. Vidare visar resultatet att en stor del av svarspersonerna finner artefaktens procedurella racerbanor underhållande, även i kontrast till riktiga racerbanor. Gynnsamma värden för artefaktens dynamiska parametrar i mån av ökad underhållning har också fastställts. En mer omfattande algoritm kan skapas utifrån detta arbete som tar hänsyn till exempelvis höjdskillnader och camber. Framtida arbeten kan då undersöka dessa delar av en racerbanas underhållningsvärde. Algoritmen kan även jämföras med andra procedurella metoder inom racing och andra spel. / <p>Det finns övrigt digitalt material (t.ex. film-, bild- eller ljudfiler) eller modeller/artefakter tillhörande examensarbetet som ska skickas till arkivet.</p>

La technique des répliques est une technique formidable prenant ses origines de la physique statistique, comme un moyen de calculer l'espérance du logarithme de la constante de normalisation d'une distribution de probabilité à haute dimension. Dans le jargon de physique, cette quantité est connue sous le nom de l’énergie libre, et toutes sortes de quantités utiles, telle que l’entropie, peuvent être obtenue de là par des dérivées. Cependant, ceci est un problème NP-difficile, qu’une bonne partie de statistique computationelle essaye de résoudre, et qui apparaît partout; de la théorie des codes, à la statistique en hautes dimensions, en passant par les problèmes de satisfaction de contraintes. Dans chaque cas, la méthode des répliques, et son extension par (Parisi et al., 1987), se sont prouvées fortes utiles pour illuminer quelques aspects concernant la corrélation des variables de la distribution de Gibbs et la nature fortement nonconvexe de son logarithme negatif. Algorithmiquement, il existe deux principales méthodologies adressant la difficulté de calcul que pose la constante de normalisation: a). Le point de vue statique: dans cette approche, on reformule le problème en tant que graphe dont les nœuds correspondent aux variables individuelles de la distribution de Gibbs, et dont les arêtes reflètent les dépendances entre celles-ci. Quand le graphe en question est localement un arbre, les procédures de message-passing sont garanties d’approximer arbitrairement bien les probabilités marginales de la distribution de Gibbs et de manière équivalente d'approximer la constante de normalisation. Les prédictions de la physique concernant la disparition des corrélations à longues portées se traduise donc, par le fait que le graphe soit localement un arbre, ainsi permettant l’utilisation des algorithmes locaux de passage de messages. Ceci va être le sujet du chapitre 4. b). Le point de vue dynamique: dans une direction orthogonale, on peut contourner le problème que pose le calcul de la constante de normalisation, en définissant une chaîne de Markov le long de laquelle, l’échantillonnage converge à celui selon la distribution de Gibbs, tel qu’après un certain nombre d’itérations (sous le nom de temps de relaxation), les échantillons sont garanties d’être approximativement générés selon elle. Afin de discuter des conditions dans lesquelles chacune de ces approches échoue, il est très utile d’être familier avec la méthode de replica symmetry breaking de Parisi. Cependant, les calculs nécessaires sont assez compliqués, et requièrent des notions qui sont typiquemment étrangères à ceux sans un entrainement en physique statistique. Ce mémoire a principalement deux objectifs : i) de fournir une introduction a la théorie des répliques, ses prédictions, et ses conséquences algorithmiques pour les problèmes de satisfaction de constraintes, et ii) de donner un survol des méthodes les plus récentes adressant la transition de phase, prédite par la méthode des répliques, dans le cas du problème k−SAT, à partir du point de vu statique et dynamique, et finir en proposant un nouvel algorithme qui prend en considération la transition de phase en question. / The replica trick is a powerful analytic technique originating from statistical physics as an attempt to compute the expectation of the logarithm of the normalization constant of a high dimensional probability distribution known as the Gibbs measure. In physics jargon this quantity is known as the free energy, and all kinds of useful quantities, such as the entropy, can be obtained from it using simple derivatives. The computation of this normalization constant is however an NP-hard problem that a large part of computational statistics attempts to deal with, and which shows up everywhere from coding theory, to high dimensional statistics, compressed sensing, protein folding analysis and constraint satisfaction problems. In each of these cases, the replica trick, and its extension by (Parisi et al., 1987), have proven incredibly successful at shedding light on keys aspects relating to the correlation structure of the Gibbs measure and the highly non-convex nature of − log(the Gibbs measure()). Algorithmic speaking, there exists two main methodologies addressing the intractability of the normalization constant: a) Statics: in this approach, one casts the system as a graphical model whose vertices represent individual variables, and whose edges reflect the dependencies between them. When the underlying graph is locally tree-like, local messagepassing procedures are guaranteed to yield near-exact marginal probabilities or equivalently compute Z. The physics predictions of vanishing long range correlation in the Gibbs measure, then translate into the associated graph being locally tree-like, hence permitting the use message passing procedures. This will be the focus of chapter 4. b) Dynamics: in an orthogonal direction, we can altogether bypass the issue of computing the normalization constant, by defining a Markov chain along which sampling converges to the Gibbs measure, such that after a number of iterations known as the relaxation-time, samples are guaranteed to be approximately sampled according to the Gibbs measure. To get into the conditions in which each of the two approaches is likely to fail (strong long range correlation, high energy barriers, etc..), it is very helpful to be familiar with the so-called replica symmetry breaking picture of Parisi. The computations involved are however quite involved, and come with a number of prescriptions and prerequisite notions (s.a. large deviation principles, saddle-point approximations) that are typically foreign to those without a statistical physics background. The purpose of this thesis is then twofold: i) to provide a self-contained introduction to replica theory, its predictions, and its algorithmic implications for constraint satisfaction problems, and ii) to give an account of state of the art methods in addressing the predicted phase transitions in the case of k−SAT, from both the statics and dynamics points of view, and propose a new algorithm takes takes these into consideration.