Alain-Sol Sznitman (ETH Zürich)

The asymptotic behavior of diffusions in random environment remains to this day poorly understood. In particular proving diffusive behavior has essentially remained restricted to situations where the method of the environment viewed from the particle applies. We discuss in this talk results from a recent joint work with Ofer Zeitouni beyond this setting. In this work we show an invariance principle as well as transience for diffusions in random environment that are small perturbations of Brownian motion and satisfy a restricted isotropy property when the space dimension is three or more.
top of page

Mike Harrison (Stanford)

We consider a call center model with m input flows and r pools of agents; the m-vector L of instantaneous arrival rates is allowed to be time-dependent and to vary stochastic-ally. Seeking to optimize the trade-off between personnel costs and abandonment penalties, we develop and illustrate a practical method for sizing the r agent pools. Using stochastic fluid models, this method reduces the staffing problem to a multi-dimensional newsvendor problem, which can be solved numerically by a combination of linear programming and Monte Carlo simulation. Numerical examples are presented, and in all cases the pool sizes derived by means of the proposed method are very close to optimal.
top of page

Tom Liggett (UCLA)

Given a random field M, one can ask the following question: For which densities R does M stochastically dominate the product measure with density R? In this talk, I will give answers to this question for the contact process stationary distribution, the Ising model, and exchangeable sequences. This problem is motivated by dependent percolation, and is joint work with Jeff Steif.
top of page

Tiefeng Jiang (University of Minnesota)

I will present my solution to the well known open problem by Diaconis stated as follows: What are the largest orders of p_n and q_n such that Z_n, the p_n by q_n left upper block of an n by n typical orthogonal matrix G_n, can be approximated by independent standard normals? This problem is solved by two different approximation methods. First, we show that the largest order of p_n and q_n are o(p_n) in the sense of approximation by the variation norm. Second, suppose G_n = (g_ij)_n*n is generated by Y_n = (y_ij)_n*n through the Gram-Schmidt algorithm where {y_ij; i,j=1,...,n} are i.i.d. standard normals. We show that the largest order of m = m_n such that e_n(m) := max{|sqrt{n}g_ij - y_ij| : i,j=1,...,n} goes to zero in probability is o(n/ log n). A history from 1914 to 2003 of the problem from Mechanics, Statistics and Image Analysis will also be presented.
top of page

Christian Gromoll (Stanford)

This talk will introduce several related measure valued stochastic processes; in each case the process models a "resource sharing" type of queueing system that is difficult to analyze using finite dimensional stochastic processes. By considering these examples together, the talk aims to give an overview of the measure valued approach to such queueing models. The discussion will highlight some techniques and intuition for obtaining scaling limits, as well as describe some recent results and open questions.
top of page

Claudio Landim (IMPA)

The large deviation properties of equilibrium (reversible) lattice gases are mathematically reasonably well understood. Much less is known in non-equilibrium, namely for non reversible systems. In this talk we consider a simple example of a non-equilibrium situation, the symmetric simple exclusion process in which we let the system exchange particles with the boundaries at two different rates.

We derive large deviation estimates for the space-time fluctuations of the empirical current which include large deviations for the density. Large time asymptotic estimates for the fluctuations of the time average of the current, recently established by Bodineau and Derrida, can be derived in a more general setting.
top of page

Yevgeniy Kovchegov (UCLA)

A multi-particle generalization of edge-reinforced random walk (ERRW) is introduced. We observe that in multi-particle case, most of the ERRW techniques do not work: no Polya urn representation on acyclic graphs, no partial exchangeability. The recurrence of a two-point edge-reinforced process on a one-dimensional lattice is proved.
top of page

Serban Nacu (Stanford)

We discuss a series of problems involving the geometry of the paths of planar Brownian motion. One focus will be the shape of connected components of the complement of a path; we give a brief survey of some past results and some ongoing work. The study of the foraging behavior of ants raises some related questions, that are interesting mathematically and may be useful biologically.
top of page

Valdo Durrleman (Stanford)

This talk is concerned with the link between implied volatilities and the spot volatility. Such a link is of great practical interest since it relates the fundamental quantity for pricing derivatives (the spot volatility) which is not observable, to directly observable quantities (the implied volatilities). We first motivate our work by some examples. Then, we explain how the dynamics of the spot volatility and that of the implied volatility surface relate to each other. Finally, we discuss some practical implications.
top of page

Alan Hammond (UC Berkeley)

In a joint work with Fraydoun Rezakhanlou, we consider a random model of diffusion and coagulation. A large number of small particles are randomly scattered at an initial time. Each particle has some integer mass and moves in a Brownian motion whose diffusion rate is determined by that mass. When any two particles are close, they are liable to combine into a single particle that bears the mass of each of them. Choosing the initial density of particles so that, if their size is very small, a typical one is liable to interact with a unit order of other particles in a unit of time, we determine the macroscopic evolution of the system, in any dimension d greater than or equal to 3. The density of particles evolves according to the Smoluchowski system of PDEs, indexed by the mass parameter, in which the interaction term is a sum of products of densities. Central to the proof is establishing the so-called Stosszahlensatz, which asserts that, at any given time, the presence of particles of two distinct masses at any given point in macroscopic space is asymptotically independent, as the size of the particles is taken towards zero.
top of page

Sourav Chatterjee (Stanford)

Suppose we have two random vectors (X_1,...,X_n) and (Y_1,...,Y_n), and a smooth function f:R^n --> R. Under what conditions can we say that f(X_1,...,X_n) and f(Y_1,...,Y_n) are close in distribution? The speaker will describe a general approach to handling such problems, based on an extension of Lindeberg's proof of the CLT. The power of this method will be demonstrated through applications to current topics of interest like random matrices and spin glasses, besides classical objects like random permutations and diffusion approximation. It will also be shown that Charles Stein's celebrated Normal approximation bound using exchangeable pairs can be derived as a corollary of this method.
top of page

Tom Hayes (UC Berkeley)

Given a group G and a set of generators S, the Cayley graph is the graph with vertex set G and all edges {x,gx} such that g is in S. A long-standing conjecture says that there exists a polynomial p(n) such that the diameter of any Cayley graph for the symmetric group S_n is at most p(n), regardless of the set of generators used. The best known upper bound is exp(O(sqrt(n log n))). We prove that the conjecture holds for almost every pair of permutations generating S_n, and hence for almost every set of generators of any size. Previously, only a superpolynomial bound (n^{(log n)/2}) was known for almost all generators. The proof hinges on finding a large set of random permutations whose first cycle lengths are pairwise "nearly independent." This is joint work with Laszlo Babai.
top of page

David Revelle (UC Berkeley)

The typical distance between two points in the uniform spanning tree (UST) on the complete graph K_m is on the order of m^{1/2}, and Aldous showed that a suitable scaling limit of the UST is the Brownian continuum random tree. We will show that for d>= 5, the scaling limit of the UST on the discrete torus Z_n^d is again the Brownian continuum random tree. This verifies a conjecture of Pitman.

In the talk we will describe the Brownian continuum random tree as well as explain Wilson's algorithm between the UST and loop-erased random walk. No previous familiarity with either of these topics will be assumed.

This is joint work with Yuval Peres.
top of page

David Galvin (IAS)

A homomorphism from a graph G to a graph H is a function f:V(G)->V(H) which preserves adjacency (if x~y in G, then f(x)~f(y) in H). Questions about independent (stable) sets in G and proper q-colourings of G, among many others, can be framed in terms of graph homomorphisms. Write hom(G,H) for the number of homomorphisms from G to H.

Using entropy methods, we show that for any H and any N-vertex, d-regular, biparite G, hom(G,H) is at most (hom(K(d,d),H))^{N/2d} where K(d,d) is the complete bipartite graph with d vertices in each partition class. This generalizes a result of J. Kahn on independent sets in regular biparite graphs.

We also give a weighted version of this result which can be interpreted as a statement about the partition function of a statistical physics "spin-system".

This represents joint work with Prasad Tetali, Georgia Tech.
top of page

Benjamin Yakir (Hebrew University)

Recently admixed populations have been proposed as a resource for complex traits mapping in a case-control design. Differences between the two founding populations in the frequencies of alleles, both in markers and in the functional polymorphism, is the vehicle that enables detection. The Hidden-Markov Model (HMM) is used for the computation of the scanning statistic, which can be applied for the detection of the functional polymorphism from the markers' genotypic information.

In this talk we will discuss some of the statistical properties of the scanning statistic when a dense collection of markers is used. Approximations to the covariance structure of the scanning process will be proposed. Similarities between the problem at hand and the problem of change-point detection will be highlighted.
top of page

Chandra Nair (Stanford)

Optimization seeks to minimize a value function subject to constraints on the solution set. It also seeks to obtain efficient algorithms for finding good solutions. Statistical physics studies the evolution of systems governed by local (microscopic) rules, and tries to quantify their global (macroscopic) behavior. The Minimum Energy principle of physics states that these systems evolve towards ground states. In a sense, physicists have been studying optimization problems that occur in nature. A particular branch of statistical physics, called Spin Glass Theory, has produced a number of remarkably effective methods for hard optimization problems in Electrical Engineering and Computer Science.

This talk begins with a brief overview of the interplay between statistical physics and optimization. I will focus on the Random Assignment Problem which arises in a variety of situations of practical interest; for example, in finding minimum weight graph matchings, minimum cost paths/flows in weighted graphs, etc. By using the (non-rigorous) Replica Method of statistical physics, Mezard and Parisi computed the average value of the minimum cost assignment to be pi2/6 in the "thermodynamic limit"; i.e. as the size of the system, N, goes to infinity. Subsequently, Parisi conjectured that when the costs are independent, rate 1, exponential random variables, the expected minimum cost for a system of size N is 1/12 + 1/22 + ... + 1/N2. This conjecture was later generalized by Coppersmith and Sorkin.

I will present a proof of the Parisi and Coppersmith-Sorkin conjectures. Subsequently, I will revisit the approach employed by the physicists and investigate some insights on the nature of optimal solutions of optimization problems. My talk will then focus attention on a recent result that proves another conjecture proposed using methods from physics on the number partitioning problem. In this problem we prove the "local REM" conjecture; equivalently, a convergence of the ordered statistics, locally, to a Poisson Process and the fact that nearby configuartions are uncorrelated.
top of page

Balint Virag (University of Toronto and MSRI)

A power series is Gaussian if its coefficients are jointly complex Gaussian random varaibles. We will review some recent developments concerning the geomteric properties of zeros of Gaussian power series. We will show that the zeros of the i.i.d. series form a determinantal process just like the eigenvalues of random matrices. We will present new results on the distribution of zeros and study the repulsion between them via a conformally invariant process. Joint work with Yuval Peres.
top of page

James Martin (Paris VII)

We consider totally asymmetric simple exclusion processes with n types of particle and holes (n-TASEPs).

Omer Angel recently gave an elegant construction of the stationary measures for the 2-TASEP, based on a pair of independent product measures. We show that Angel's construction can be interpreted in terms of the operation of a discrete-time M/M/1 queueing server; the two product measures correspond to the arrival and service processes of the queue. We extend this construction to represent the stationary measures of an n-TASEP in terms of a system of priority queues in tandem. The proof of stationarity involves a system of n 1-TASEPs, whose evolutions are coupled but whose distributions at any fixed time are independent.

One corollary is the form of an arrival process which is a "fixed point" for an n-type priority queue (i.e. such that the departure process has the same law as the arrival process)

Joint work with Pablo Ferrari.
top of page

Marc Mezard (MSRI and CNRS-Universite Paris Sud)

The phase transition in random K-satisfiability problems is a very important phenomenon both from the point of view of physics and from that of computational complexity. This talk exposes the analysis of this transition using the cavity method, developed in spin glass theory. It predicts the existence of an intermediate phase, when the density of constraints is smaller than the critical threshold, where satisfying assignments cluster in well separated regions. The cavity analysis can be turned into an algorithm, 'survey propagation', which succeeds in finding satisfiable assignments in very large formulas quite close to the threshold.
top of page

Alexander Holroyd (UBC and MSRI)

Initially a car is placed with probability p at each site of the two-dimensional integer lattice. Each car is equally likely to be East-facing or North-facing, and different sites receive independent assignments. At odd time steps, each North-facing car moves one unit North if there is a vacant site for it to move into. At even time steps, East-facing cars move East in the same way.

Simulations suggest that the model has remarkable self-organising properties, but rigorous results have been notoriously elusive. We make a step towards establishing a phase transition by proving that there is a phase in which traffic is completely jammed.

Joint work with Omer Angel and James B. Martin.
top of page

Ofer Zeitouni (University of Minnesota)

I will describe enumeration techniques that lead to a CLT for traces of symmetric random matrices with independent but not necessarily identically distrbuted entries. I will then explain how the use of concentration inequalities allows one to extend the CLT to linear statistics of more general type.

(Joint work with G. W. Anderson)
top of page

Assaf Naor (Microsoft Research)

The entropy of a random variable with density f is defined as the integral of -f log f. In the 1940s, Shannon proved that if X_1 and X_2 are i.i.d., then the entropy of (X_1+X_2)/sqrt{2} is at least the entropy of X_1. The problem whether, for i.i.d. random variables X_i, the entropy of (X_1+...+X_n)/sqrt{n} is an increasing sequence remained open. In this talk we will show that, indeed, entropy increases along central limit averages. The proof is based on a new variational formula which is motivated by (a proof of) the Brunn-Minkowski inequality.

Based on joint works with S. Artstein, K. Ball and F. Barthe.
top of page

Marek Biskup (UCLA)

We consider a simple random walk on the (unique) infinite cluster C_\infty of bond percolation in Z^d, d >= 2. At each unit of time the walk picks one of its 2d neighbors at random and attempts to move to it, but the move is suppressed if the respective edge is not present in C_\infty. We will show that, in almost every realization of C_\infty, the path of this walk scales to d-dimensional Brownian motion under the "usual" scaling of space and time. The proof is based on analysis of the "corrector" which is an additive term that makes the position of the walk a martingale. Based on joint work with Noam Berger.
top of page

Steven Lalley (University of Chicago)

At each vertex of the integer lattice in d dimensions is located a colony of N individuals, each of whom is initially susceptible to infection by a contagious disease. Once infected, an individual remains contagious for one time period, after which he/she recovers and is thereafter immune to further infection. While contagious, an individual may infect susceptible individuals in neighboring colonies, according to the following rules:

(A) In the "symmetric" model, an infected individual at vertex x will infect a susceptible individual in any of the 2d neighboring colonies with probability 1/(2dN).

(B) In the "totally asymmetric" model, an infected individual at vertex x will infect a susceptible individual in any of the d neighboring colonies "up or to the right" with probability 1/(dN).

The probabilities are chosen so that the epidemic is "critical": the mean number of new infections caused by a contagious individual is 1.

Problem: If initially only individuals at the origin (or in some neighborhood of the origin) are infected, how far will the epidemic extend in space?
top of page

Mark Meckes (Stanford)

We consider the following generalization of the classical central limit problem, whose motivation comes from convex geometry: what (sufficient) conditions on a random vector X (with dependent components) and a fixed vector theta guarantee that the linear statistic sum theta_i X_i is approximately normal? Using Stein's method of exchangeable pairs, we prove normal approximation theorems for such statistics under certain symmetry conditions. Our interest is primarily in the case in which X is uniformly chosen from some convex body, although our results are not limited to that context.

This is joint work with Elizabeth Meckes.
top of page

Lancelot James (Hong Kong University of Science and Technology)

In this talk we describe a Poisson Process Partition Calculus and how it can be applied to some specific problems. The calculus is designed such that one does not need substantial expertise in random measures and combinatorics. We give two concrete applications of this calculus. The first is to show how easily one can establish a Markov-Krein-type identity for linear functionals of a random probability measure defined by normalizing a positive Levy measure. This is a generalization of results developed for mean functionals of Dirichlet processes. Our second application is to neutral-to-the-right processes, where we describe various features of the induced exchangeable marginal distribution which is related to recent work on regenerative compositions. Neutral-to-the-right processes are shown to be related to exponential functionals of Levy processes, an area of intense recent activity in financial mathematics.
top of page

Michael Woodroofe (University of Michigan)

Let ...X_{-1}, X_0, X_1, X_2, ... denote a stationary ergodic process for which the X_k have mean 0 and a finite positive variance. Further, let S_n = X_1+ ... +X_n and sigma_n^{2} = E(S_n^2) and suppose that sigma_n converges to infinity as n tends to infinity. The conditional central limit question is whether the conditional distribution of S_n/sigma_n given ... X_{-1},X_0 converges to the standard normal distribution. There has been substantial recent progress on this question, leading conditions that are necessary and nearly sufficient. On one hand the conditions can be phrased in terms of growth restrictions on E(S_n | ... X_{-1},X_{0}). On the other, they may be phrased in terms of approximate solutions to Poisson's Equation for the Markov Chain W_n = (... X_{n-1},X_n) and solutions to a fractional version of Poisson's Equation. This progress will be reviewed, and some current work described.
top of page

Illya Targoniy (Stanford)

In the best traditions of Frank Spitzer's famous "Principles of Random Walks" book, we develop authentic theory of random walks on the lattices Z^d with absorption points - once random walk gets into such a point, it stays there for the rest of the time. The authenticity comes since with this theory we are able to calculate any transition probability and generation function for any positioning and number of absorbing points on a lattice via the known respective values of symmetric random walk on regular lattice.

We demonstrate then one of the applications of those principles to the Laplacian self-avoiding random walk defined and studied by Gregory Lawler. Specifically, we consider process behavior in the initial and infinitely large moments of time and compare it with the usual "myopic" self-avoiding random walk process. We show that the behavior of those two processes differs in their initial steps (this comes from the fact that opposite to the usual "myopic" SAW, a Laplcian -SAW cares about its future), but is similar after sufficiently large number of steps.

The latter fact is important - it follows that the second moment of Laplacian self-avoiding random walks is the same as of the usual SAW when the number of steps goes to infinity. So, here comes the advantage of the Laplacian SAW. It is not easy to simulate the paths of usual SAW, since the ratio of such non-intersecting trajectories to all possible is extremely low, thus to get the non-intersecting path is an extremely rare event. Whereas simulating Laplacian-SAW is relatively easy - we obtain its trajectories on the grid by simulating a simple symmetric random walk by Monte Carlo method. Then, by appropriate weighting through the evaluated transition probabilities of any such path, we can estimate the second moment of Laplacian self-avoiding random walk, that is similar to the usual self-avoiding walk.
top of page

Bert Zwart (Eindhoven Univ. of Tech.)

In recent studies it has been shown that the throughput of a TCP connection is strongly related to the random variable Z = int_0^infty exp{-X(t)} dt, with X(t) a compound Poisson process. Z also appears in the probabilistic analysis of other algorithms, in mathematical finance (where Z is called a perpetuity), in mathematical physics, and the analysis of self-similar Markov processes. In all these cases, X(t) is a (special case of a) Levy process.

In this talk we first review the TCP application, and then investigate various properties of the distribution of Z. In particular, we give an expression for the Mellin transform of Z, and derive the tail behavior of Z. We show that a large variety of tail asymptotics (depending on X(.)) are possible, ranging from extremely heavy tails (P(Z>x) ~ (log x)^{-a}) to extremely light tails (P(Z>x)~ e^{-x^p}).
top of page