UBC Probability Seminars, 2008-2009

#### Often Wednesday 3:00-4:00 pm, PIMS WMAX Room 216

Seminars by visiting speakers will typically be followed by dinner at a restaurant at 6pm
Seminars by local speakers will typically be followed by beer at Koerner's Pub
Organiser: Ben Graham, ben@math.ubc.ca, (+1) 604-822-4605.

 Past Talks 10 Sep Eugene Kritchevski (UBC) Poisson statistics of eigenvalues for random discrete Schrödinger operators. In this talk, I will consider random discrete Schrödinger operators of the form H= L+ c V acting on the Hilbert space l^2(X), where X is a given countable set endowed with a nice homogeneous structure: e.g. the lattice Z^d, a regular tree, or a hierarchical lattice. Here L is a given self-adjoint operator on l^2(X) e.g. the discrete or the hierarchical Laplacian, V is a random potential (Vf)(x)=v(x)f(x) with v(x) i.i.d. random variables, and c>0 is a coupling constant measuring the strength of the disorder. One is interested to understand the statistical behavior of the random eigenvalues of large finite volume approximations to H in the thermodynamic limit. In some cases it is possible to prove that, after a natural rescaling, the random eigenvalues behave as a Poisson point process. After reviewing the known results for the the Anderson model on Z^d and for the regular tree, I will discuss my work on the hierarchical model. I will explain the mechanism responsible for Poisson statistics of eigenvalues and, if time permits, results on generic spectral localization. 17 Sep Robert Masson (UBC) The growth exponent for loop-erased random walk The loop-erased random walk is the process obtained by chronologically erasing loops from a random walk. The growth exponent for LERW is defined to be the number a such that the expected number of steps of a LERW from the origin to the circle of radius n grows like n^a. Using domino tilings to compute the number of uniform spanning trees of rectilinear regions in the plane, Rick Kenyon showed that the growth exponent for LERW on Z^2 is equal to 5/4. In this talk, I will give a new proof of this result using the convergence of LERW to SLE_2, valid for walks on more general lattices. I will then indicate how these techniques can be used to get estimates on the second moment of the number of steps and also give a sketch of an as yet incomplete argument showing the existence of the growth exponent in three dimensions. 24 Sep Shankar Bhamidi (UBC) Flows through Random Networks: Probabilistic and Statistical Problems In the last few years with the availability of large amounts of data, there has been a lot of effort in coming up with Network models trying to explain "Real world" networks as well as in trying to model dynamic processes on these networks. In connection to the above consider the following 3 problems: 1> Edge flow problem: Given a connected network with edge costs, suppose each node sends a unit amount of flow to every other node via the least cost path. We are intersted in the amount of flow passing through various nodes and edges. What happens when the Network becomes large ? Can we come up with a tractable math model giving us precise asymptotic information ? 2> Price of Anarchy: Networks such as road networks, typically exhibit "selfish" behaviour in that there are a large number of agents each of whom try to move in the network maximizing their own utility, depending on the present congestion levels of the edges in the network. Suppose there was a central authority who could minimize some sort of global cost function and route traffic so that the "common good" is maximized. How much better of is the above central planning method compared to the selfish routing behavior ? How can we make mathematical sense of the above problem ? Further can we come up with some math model which gives us asymptotic results as the number of interacting agents becomes large ? 3> Multicast tree problem: In a number of problems that arise from trying to discover the underlying structure of the Internet, often it is impossible to take direct measurements at the routers. We shall mention some initial progress in trying to reconstruct the "Multicast" tree using only "end-to-end " measurements. We shall give a brief overview of the above problems and state results from works in progress. In the last part of the talk we shall try to give the key probabilistic ideas that help us understand the edge flow problem in the model considered and the predictions for other locally tree like network models. 1 Oct Pierluigi Falco (UBC) Extended Scaling Relations for the Eight Vertex and Ashkin Teller models The critical, nonuniversal properties of the Eight Vertex, Ashkin-Teller and XYZ models are widely expected to be described by the quantum field theory obtained as a formal scaling limit. On the basis of this assumption, Kadanoff, Luther and Peschel conjectured universal scaling formulae that connect the nonuniversal critical indices. So far these conjectures have remained unproven. We present a constructive, renormalization-group approach that allows us to prove some of them under the condition of small coupling. 8 Oct Vieri Mastropietro (Univ. Rome - Tor Vergata) The Hubbard model on the square and honeycomb lattice by functional integral methods We present some results on the planar Hubbard model on the square and the honeycomb lattice in the weak coupling regime. The Schwinger functions are expressed in terms of fermionic Grassmann integrals and analyzed by by constructive Renormalization Group methods. 15 Oct Xinghua Zheng (UBC) Critical Branching Random Walks and Spatial Epidemics Watanabe's Theorem asserts that the measure-valued processes associated with a sequence of critical branching random walks, under suitable assumptions and after rescaling, converge to a super-Brownian motion $\{X_t\}$. There has been extensive study of the closed support of the measure $X_t$. In particular, it is known that when $d \geq 3$, for any fixed time $t>0$, the measure can be recovered from its support (Perkins(1989)) and the measure spreads its mass over the support in a fairly uniform manner (Perkins(1988)). We will discuss analogous results about branching random walks in 2 or higher dimensions via the study of the following occupation statistics: the maximal number of particles at a single site, the number of multiplicity-$j$ sites, the number of particles at a typical'' site, and the number of occupied sites. We will then focus on the 2 or 3 dimensional case. We show that the local time processes associated with branching random walks, under suitable scaling, converge to the local time density process associated with the limiting super-Brownian motion. This establishes a conjecture due to Adler (1993). Finally we will talk about spatial SIR epidemics. In these models, finite populations of size $N$ are situated at the sites of the integer lattice. Based on the local time convergence result, we show that the measure-valued processes associated with these epidemics, suitably scaled, converge, in the large-$N$ limit, either to a standard Dawson-Watanabe process (super-Brownian motion) or to a Dawson-Watanabe process with density-dependent killing, depending on the size of the the initially infected set. Based on joint work with Steven Lalley. 22 Oct David Brydges (UBC) A combinatorial generalisation of Cramers rule We review a result of G. X. Viennot, Lecture Notes in Mathematics, #1234, and comment on its significance for statistical mechanics: a ratio of generating functions for disjoint oriented loops in a finite graph can be expressed in terms of the generating function of a single path in the graph weighted according to loops in the path, where the loops are defined by the same algorithm as in loop erased random walk. The result is a generalisation of Cramer's formula for the inverse of a matrix. 29 Oct Éric Fusy (UBC) Probabilistic algorithms to estimate the cardinality of large multisets A multiset is a set where each element can appear many times, its cardinality n is the number of distinct elements. The problem of computing n has many applications in computer science (e.g. estimate the number of distinct connections on a server), the difficulty being that the multiset is often too large to be stored. I will explain how probabilistic methods make it possible to precisely estimate n without storing the multiset and with very little auxiliary memory. 5 Nov Lung-Chi Chen (UBC) The limit distribution for long-range oriented percolation In this talk, I will present the Fourier transform of the properly-scaled, normalized, two-point function for sufficiently spread-out long-range oriented percolation with index $\alpha>0$. The Fourier transform converges to $e^{-C|k|^{\alpha\wedge2}}$ for some $C\in(0,\infty)$ above the upper-critical dimension $d_c\equiv 2(\alpha\wedge 2)$. Moreover, the constant $C$ exhibits crossover at $\alpha=2$, which is a result of interactions among occupied paths. 19 Nov Edwin Perkins (UBC) Voter Model Perturbations and Reaction Diffusion Equations We study both high density and low density limit theorems for voter model perturbations including the spatial Lotka-Volterra model introduced by Neuhauser and Pacala. The high density limit produces reaction-diffusion equations while the low density setting leads to superprocesses. In earlier work with Ted Cox, the low density theorems were used to show results on survival (in two and more dimensions) and coexistence (in three and more dimensions). I will report on work with Ted Cox and Rick Durrett where both limit theorems are used to show these results are locally sharp in three and more dimensions and verify a conjecture of Neuhauser and Pacala on the lack of founder control in the competitive regime of the model at least for values near the voter model. 26 Nov Asaf Nachmias (Microsoft Research) The Alexander-Orbach Conjecture Holds in High Dimensions It is known that the simple random walk on the unique infinite cluster of supercritical percolation on Z^d diffuses in the same way it does on the original lattice. In critical percolation, however, the behavior of the random walk changes drastically. The infinite incipient cluster (IIC) of percolation on Z^d can be thought of as the critical percolation cluster conditioned on being infinite. Alexander and Orbach (1982) conjectured that the spectral dimension of the IIC is 4/3. This means that the probability of an n-step random walk to return to its starting point scales like n^{-2/3} (in particular, the walk is recurrent). In this work we prove this conjecture when d>18; that is, where the lace-expansion estimates hold. Joint work with Gady Kozma. 14 Jan Allan Sly (Berkeley) Mixing in Time and Space For Markov random fields temporal mixing, the time it takes for the Glauber dynamics to approach it's stationary distribution, is closely related to the spatial mixing properties of the measure such as uniqueness and the reconstruction problem. Such questions are of importance in probability, statistical physics and theoretical computer science. I will discuss some recent progress in understanding the mixing time of the Glauber dynamics for the Ising model and for random colourings of graphs. 21 Jan Ben Graham (UBC) Influence and statistical mechanics Statistical mechanics is the branch of physics that seeks to explain the properties of matter that emerge from microscopic scale interactions. Probabilistic models such as percolation help describe various physical phenomena. The models are generally not exactly solvable; simple local interactions produce complex long range behaviour. The technology of influence provides a way to study these processes. We will look at applications of influence to percolation, directed and undirected first passage percolation, the Ising model, and the random-cluster model. Joint work with Geoffrey Grimmett. 28 Jan Martin Barlow (UBC) Convergence of random walk in random environment to fractional kinetic motion. I will consider a random walk in random environment obtained by putting iid bond weights $\mu_e$ on the bonds in the lattice $Z^d$.(Here $d\ge 3$). We assume $\mu_e \ge 1$, but have heavy tails: $P(\mu_e > t) \sim t^{-\alpha}$ with $\alpha \in (0,1)$. This process, when suitably rescaled, converges to a non Markovian process, called 'fractional kinetic motion'. This is joint work with J. Cerny. Tuesday 3 Feb (PIMS WMAX 216) Michael Goldstein (Toronto) Fluctuations and growth of the magnitude of the Dirichlet determinants of Anderson Model at all disorders Abstract 25 Feb Ronnie Pavlov (UBC) Estimating the entropy of a Z^d shift of finite type with probabilistic methods In symbolic dynamics, a Z^d shift of finite type (or SFT) is the set of all ways to assign elements from a finite alphabet A to all sites of Z^d, subject to rules about which elements of A are allowed to appear next to each other. A simple example of an SFT is the Z^d golden mean shift, which is the set of all ways to assign zeroes and ones to sites of Z^d such that no two ones are adjacent (for d=2, this example is also known as the hard square model.) Any Z^d SFT has an associated topological entropy (or entropy), which is a real number measuring the exponential growth rate, as n goes to infinity, of the number of configurations in A^({1,...,n}^d) which satisfy the SFT adjacency rules. For d=1, the entropy of any SFT is easy to compute: it is always the log of the largest eigenvalue of an easily defined integer-valued matrix associated with the SFT; for the golden mean shift, the entropy is the log of the golden mean. For d>1, the computation is much more difficult. For instance, there is no known explicit closed form for the entropy of the Z^2 golden mean shift. And the standard ways to approximate the entropy of a Z^d SFT appear to converge very slowly. For the Z^2 golden mean shift, we give a sequence of computable upper and lower bounds which converge exponentially fast to the entropy. Empirical data suggested that these particular numbers approach the entropy some time ago, but it has been an open problem to prove the convergence. Surprisingly, the methods we use to solve this combinatorially defined problem come mostly from measure theory and probability. We use concepts and techniques from the theory of interacting particle systems, including stochastic domination of measures and uniqueness of Gibbs states. Some results from percolation theory are also used to prove the exponential rate of convergence. 11 Mar Robert Masson (UBC) Second moment estimates for the growth exponent of loop-erased random walk The loop-erased random walk Y^n is the process obtained by running a random walk in Z^d from the origin to the first exit time of the ball of radius n and then chronologically erasing its loops. If we let X_n denote the number of steps of Y^n then the growth exponent a is defined to be such that E[X_n] grows like n^a. The value of a (or even its existence) depends on the dimension d. In this talk I'll focus on d=2 where it's been shown that a = 5/4. What we want to know is how close is X_n to its mean? By the Markov inequality one gets that P(X_n > bE[X_n]) < b^{-1}. The goal of this talk will be to show a similar lower bound: P(X_n < bE[X_n]) < b^{c} for some c>0. 18 Mar Michael Kozdron (University of Regina) Using multiple SLE to explain a certain observable in the 2d Ising model The Schramm-Loewner evolution (SLE) is a one-parameter family of random growth processes that has been successfully used to analyze a number of models from two-dimensional statistical mechanics. Currently there is interest in trying to formalize our understanding of conformal field theory using SLE. Smirnov recently showed that the scaling limit of interfaces of the 2d critical Ising model can be described by SLE(3). The primary goal of this talk is to explain how a certain non-local observable of the 2d critical Ising model studied by Arguin and Saint-Aubin can be rigorously described using multiple SLE(3) and Smirnov's result. As an extension of this result, we explain how to compute the probability that a Brownian excursion and an SLE(k) curve, 0 1 Apr Eugene Kritchevski (UBC) Localization of the eigenfunctions of the one-dimensional Schrödinger operator in the presence of random potentials We consider the one-dimensional discrete Schrödinger operator (Hf)(x)=f(x-1)+f(x+1)+v(x)f(x), on the interval {1,2,...,N} with Dirichlet boundary conditions f(0)=f(N+1)=0. We assume that v(x) are independent random variables for a very small fraction of the sites x and nonrandom for the remaining sites. We discuss a mechanism responsible for the following localization phenomenon: for large N, outside a set of realizations of the potentials of very small probability, each eigenfunction of H decays exponentially. Our approach to localization is based on a recent method of Goldstein. 8 Apr Ori Gurel-Gurevich (Microsoft Research) Choice-memory tradeoff in allocations Consider the classical balls-and-bins setup: n balls are thrown independently and uniformly into n bins. The most loaded bin then has log n/log log n balls with high probability. What happens when instead of throwing balls completely by random, there is an allocation algorithm which is given k uniformly and independently selected bins to choose from for the location of each ball? A well known result of Azar, Broder, Karlin & Upfal states that one can then achieve a maximal load of log_k log n, simply by putting each ball in the less loaded of the k optional bins. In order to implement this simple algorithm, one needs to keep track of the status of the entire array of n bins, which requires about n bits of memory. The problem of what can be achieved with less memory was raised by Itai Benjamini. The main result in this talk is that, generally speaking, there is a tradeoff between the number of choices, k, and the memory, m. That is, when km>>n one can achieve a constant maximal load, while for km<