Ron Peled (Berkeley)

Given a translation invariant point process in R^d of intensity 1, an allocation rule is a translation-equivariant mapping that allocates to each point in the process a set in R^d of unit volume, such that the sets allocated to different points are disjoint and their union covers almost all of R^d. Allocation rules can give a better understanding of the underlying point process, they measure in some sense how uniformly the mass is spread over space. They can also be used for obtaining so called extra head rules. In this talk we will consider the standard Poisson point process in R^d, allocation rules for this process were constructed by Hoffman, Holroyd and Peres using the Gale-Shapley stable marriage algorithm. I will describe a new allocation rule in dimensions 3 and higher, inspired by recent work of Nazarov, Tsirelson, Sodin and Volberg, that is defined by flow along the integral curves of a gravitational force field induced by the Poisson points. The main result is that this allocation is 'efficient', in the sense that the diameter of the cell allocated to a given point is a random variable with exponentially decaying tails. This is the first deterministic allocation with this property.

This is joint work with Sourav Chatterjee, Yuval Peres and Dan Romik.
top of page

Yun Long (Berkeley)

The Swendsen-Wang dynamics is a Markov chain widely used by physicists to sample from the Boltzmann-Gibbs distribution of the Ising model. It's generally believed that this new dynamics runs more efficiently than the glauber dynamics in most of the cases. I'll show that when the underlying graph is the complete graph, the SW dynamics indeed mixes fast. The sharp bounds here for the mixing time is logarithmic for all non critical temperatures, while at the critical temperature the mixing time is of order n^{1/4}. This improves a former result of Cooper, Dyer, Frieze and Rue. This is joint work with Asaf Nachmias and Yuval Peres.
top of page

Aubrey Clayton (Berkeley)

In two recent papers, Evans, Steinsaltz, and Wachter described a model for genetic mutation and natural selection in the presence of recombination. The essential ingredient of the model is a family of Poisson random measures whose intensities satisfy a differential equation. In this talk, I will briefly describe the derivation of the model and discuss convergence to equilibrium for a special category of selection cost functions.
top of page

Fraydoun Rezakhanlou (Berkeley)

Smoluchowski's equation is used to describe the coagulation-fragmentation process macroscopically. Microscopically clusters of various sizes coalesce to form larger clusters and fragment into smaller clusters. I formulate a conjecture about the nature of the fluctuations of the microscopic clusters about the solutions to the Smoluchowski's equation. I also sketch the proof of the conjecture when the model is in equilibrium.
top of page

Shankar Bhamidi (Berkeley)

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 interested 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? Using continuous time branching processes and "local information" of the neighborhood about edges we show how this can be done.

2. Price of Anarchy: Networks such as road networks, typically exhibit "selfish" behavior 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? We will state preliminary results as to what we think happens. However this work is still very much in progress.

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. Using ideas from algorithms in phylogenetics (reconstructing the "tree of life") we show how this can be done efficiently.
top of page

Persi Diaconis (Stanford)

In a statistical problem, the following task arises. Consider the set of positive n-tuples with a fixed sum and product. By its embedding in Euclidean space, this set inherits an area measure which can be normed to be a probability. The problem is to sample from this measure. Such problems arise in testing goodness of fit for the gamma distribution and as such offer an extension of "algebraic statistics" to continuous settings. The tools involved, the area and coarea formulae of geometric measure theory seem generally useful. This is joint work with Mehrdad Shahshahani and Susan Holmes.
top of page

Soumik Pal (Cornell)

Consider n positive diffusions whose logarithms are Brownian motions whose drift vector at every time point is determined by the arrangement of indices in increasing order of values. These processes appear naturally in a variety of areas from queueing theory, statistical physics, and economic modeling.

For finite n, the invariant distribution of the vector of spacings between the Brownian particles can be completely described. The interest is to describe a limiting invariant distribution when n is large. We show, as n grows to infinity, a curious phenomenon occurs for the rescaled positive diffusions divided by the sum of their coordinate values. Under very weak conditions, one of three things can happen to the scaled values: either they all go to zero, or the maximum grows to one while the rest go to zero, or they stabilize and converge in law to a Poisson-Dirichlet point process. The proof borrows ideas from Talagrand's analysis of Derrida's Random Energy Model of spin glasses.

The other alternative is to start with a countable collection of diffusions. We consider one such model and discuss the similarities and differences with the previous limit. This countable model is related to the Harris model of elastic collision and the discrete Ruzmaikina-Aizenmann model for competing particles.

This is based on separate joint works with Sourav Chatterjee and Jim Pitman.
top of page

Asaf Nachmias (Berkeley)

Let G be a transitive graph on n vertices with vertex degree d. We show that if the non-backtracking random walk behaves on G as it would on a random graph in some sense, then critical bond-percolation on G behaves as it would on a random graph.

More precisely, we provide geometric conditions on G, in terms of return probabilities of the non-backtracking random walk, which guarantees that the largest component in p-bond-percolation with p= 1/(d-1) is of roughly of size n^{2/3} and a scaling window of width n^{-1/3} around this critical probability exists. These conditions are usually easy to verify. In particular, bond-percolation on the celebrated Ramanujan graph constructed by Lubotzky, Phillips and Sarnak has the above scaling window. This provides the first examples of quasi-random graphs behaving like random graphs with respect to critical bond-percolation.
top of page

Richard Durrett (Cornell)

We consider the population genetics problem: How long does it take before some member of the population has k specified mutations? The case k = 2 is relevant to onset of cancer due to the inactivation of both copies of a tumor suppressor gene. Models for larger k are needed for colon cancer and other diseases where a sequence of mutations leads to cells with uncontrolled growth. (Joint work with Deena Schmidt and Jason Schweinsberg).
top of page

Craig Tracy (UC Davis)

In this joint work with Harold Widom we consider the ASEP on Z. Each particle waits exponential time, then with probability p it moves one step to the right if the site is unoccupied, otherwise it stays put; with probability 1 - p it moves one step to the left if the site is unoccupied, otherwise it stays put. We describe how to obtain a differential equation for the probability of a given configuration at time t. Then using the Bethe Ansatz we find an integral formula for the solution. From this we derive formulas for the probability that a particular particle is at a particular site at time t. Our formulas extend to an infinite system of particles for a special class of initial conditions. For the case of the T(totally)ASEP, p = 1, our formulas reduce to known ones, including one obtained by Johansson by other means connecting this to a Laguerre random matrix ensemble.
top of page

Yuval Peres (UC Berkeley & Microsoft Research)

More than twenty years ago, Diaconis and Shashahani proved a "cutoff" (concentration of the mixing time) for random transpositions, and Aldous showed it for random walk on a hypercube. The cutoff phenomenon is believed to be widespread, but still known in relativly few cases. I will disucss several conjectures and examples pertinent to understandiong this phenomenon. In joint work with David Levin and Malwina Luczak, we consider the Ising model on the complete graph, and establish the cutoff phenomenon for Glauber dynamics above the critical temperature, and mixing time n^{3/2} at criticality. We conjecture similar behaviour on many other graphs.
top of page

Lionel Levine (Berkeley)

We study the scaling limits of three aggregation models on the lattice: internal DLA, in which particles perform random walks until reaching an unoccupied site; the rotor-router model, in which particles perform deterministic analogues of random walks; and the divisible sandpile, in which each site distributes its excess mass equally among its neighbors. We prove that as the lattice spacing tends to zero, all three models have the same scaling limit, which we describe as the solution to a certain PDE free boundary problem. In particular, internal DLA has a deterministic scaling limit. Our results apply both to the case of multiple point sources and to the Diaconis-Fulton smash sum of domains. Joint work with Yuval Peres.
top of page

Roman Vershynin (UC Davis)

While developing algorithms for matrix inversion, Von Neumann and Goldstine discovered problems with ill-conditioned matrices. They experimented with large square matrices with random i.i.d. entries, and came to the conclusion that their condition numbers should be linear in the dimension. Von Neumann-Goldstine's prediction and its refinement by Smale was proved only for Gaussian matrices by Edelman in 1985. The simplest unsolved case has been for Bernoulli matrices, whose entries are 1 or -1 with equal probability. I will describe a recent solution of Von Neumann-Golstine conjecture. It is valid for all random matrices whose independent entries have bounded fourth moment. One new probabilistic ingredient in this work is a development of Littlewood-Offord theory of anti-concentration inequalities. I will describe its connections with ergodic theory and additive combinatorics. This is a joint work with Mark Rudelson.
top of page

Nick Crawford (Berkeley)

In this talk we will describe techniques which allow the extension of methods from the study of classical spin glasses to quantum versions. We will begin by describing the formalism of equilibrium quantum spin systems and then show how these objects may be studied within a probabilistic context. Our aim is to demonstrate that the free energy of of a certain generalization of the Sherrington-Kirkpatrick model, the transverse Ising spin glass, exists.
top of page

S. Alex Smith (UCLA)

For a fixed underlying graph G, "cycle free percolation with parameter p" is a sample of a random forest on G with a forest containing m edges weighed by (p/(1-p))^m. Equivalent descriptions involve conditioning bond percolation on the event that the resulting graph contains no cycles, or by taking the q -> 0 limit of the random-cluster model with parameter q. In this talk I will dicuss cycle-free percolation for G being the complete graph on n vertices.
top of page