Markov chain methods for Monte Carlo simulation of complex physical or statistical models often require significant tuning. Recent theoretical progress has renewed interest in "adaptive" Markov chain algorithms which learn from their sample history. However, these algorithms produce non-Markovian, time-inhomogeneous, irreversible stochastic processes, making rigorous analysis challenging. We show that lower bounds on the mixing times of these processes can be obtained using familiar ideas of hitting times and conductance from the theory of reversible Markov chains. The bounds obtained are sufficient to demonstrate slow mixing of several recently proposed algorithms including adaptive Metropolis kernels and the equi-energy sampler on some multimodal target distributions. These results provide the first non-trivial bounds on the mixing times of adaptive MCMC samplers, and suggest a way of classifying adaptive schemes that leads to new hybrid algorithms. Many open problems remain.

In this talk I will discuss a branching process model developed to study intra-tumor diversity (i.e. the variation amongst the cells within a single tumor). This variation arises due to heritable (epi)genetic alterations which can confer changes in cellular fitness and drug response. In the asymptotic (t-> infinity) regime, we study the growth rates of the population as well as some ecological measures of diversity in the tumor. In the second half of the talk I will discuss applications of this model to studying the emergence of drug resistant populations in Chronic Myeloid Leukemia (CML). (Joint work w/K. Leder, J. Mayberry, R. Durrett, F. Michor)

We introduce a new measure constructed from high-frequency financial data which we call the Realized Laplace Transform of volatility. The statistic provides a nonparametric estimate for the empirical Laplace transform of the latent stochastic volatility process over a given interval of time. When a long span of data is used, i.e., under joint long-span and fill-in asymptotics, it is an estimate of the volatility Laplace transform. The asymptotic behavior of the statistic depends on the small scale behavior of the driving martingale. We derive the asymptotics both in the case when the latter is known and when it needs to be inferred from the data. When the underlying process is a jump-diffusion our statistic is robust to jumps and when the process is pure-jump it is robust to presence of less active jumps. We apply our results to simulated and real financial data.

The nature of dynamical processes occuring on a directed network can depend qualitatively on the logic implemented at each node. In large random networks where nodes act as Boolean gates, there is a phase transition from quiescent to chaotic behavior as the average degree and/or the probabilities of assigning the different logic functions are varied. To understand the behavior at the transition, we are led to a special type of percolation problem in which the relevant question is not whether a cascade spans the system, but whether it covers the entire system. I will introduce the problem of exhaustive percolation, outline a method for solving it, and describe its application to random Boolean networks.

Consider a connected network and suppose each edge in the network has a random positive edge weight. Understanding the structure and weight of the shortest path between nodes in the network is one of the most fundamental problems studied in modern probability theory and goes under the name first passage percolation. It arises as a fundamental building block in many interacting particle system models such as the spread of epidemics on networks. To a large extent such problems have been only studied in the context of the n-dimensional lattice. In the modern context these problems take on an additional significance with the minimal weight measuring the cost of sending information while the number of edges on the optimal path (hopcount) representing the actual time for messages to get between vertices in the network. Given general models of random graphs with random edge costs, can one develop techniques to analyze asymptotics of functionals of interest which are robust to the model formulation? The aim of this talk is to describe a heuristic based on continuous time branching processes which gives very easily, a wide array of asymptotic results for random network models in terms of the Malthusian rate of growth and the stable age distribution of associated branching process. These techniques allow us to solve not only first passage percolation problems rigorously but also understand functionals such as the degree distribution of shortest path trees, congestion across edges as well as asymptotics for “betweeness centrality” a concept of crucial interest in social networks, in terms of Cox processes and extreme value distributions. These techniques also allow one to exactly solve models of “weak disorder” in the context of the stochastic mean field model of distance, a model of great interest in probabilistic combinatorial optimization.

We consider first-passage percolation on the cylinder graph of length $n$ and width $h_n$ in the d-dimensional square lattice where each edge has an i.i.d.~nonnegative weight. The passage time for a path is defined as the sum of weights of all the edges in that path and the first-passage time between two vertices is defined as the minimum passage time over all paths joining the two vertices. We show that the first-passage time $T_n$ between the origin and the vertex $(n,0,\ldots,0)$ satisfies a Gaussian CLT as long as $h_n=o(n^{1/(d+1)})$. The proof is based on moment estimates, a decomposition of $T_n$ as an approximate sum of independent random variables and a renormalization argument. We conjecture that the CLT holds upto $h_n=o(n^{2/3})$ for $d=2$ and provide support for that. Based on joint work with Sourav Chatterjee.

Consider a Galton-Watson tree. Pick two individuals at random by simple random sampling from the nth generation and trace heir lines of descent back in time till they meet. Call that generation X_n. In this talk we will discuss the probability distribution of X_n and its limits for the four cases m <1, m=1, m greater than 1 but finite, and m infinite, where m is the mean offspring size.

A deterministic walk in a random environment can be understood as a general finite-range dependent random walk that starts repeating the loop once it reaches a site it has visited before. Such process lacks the Markov property. We will talk about the exponential decay of the probabilities that the walk will reach sites located far away from the origin.

The critical threshold for the emergence of a giant component in the random site subgraph of a d-dimensional Hamming torus is given by the positive root of a polynomial. This value is distinct from the critical threshold for the random edge subgraph of the Hamming torus. The proof uses an intuitive application of multitype branching processes.

We consider particle systems that are perturbations of the voter model and show that when space and time are rescaled the system converges to a solution of a reaction diffusion equation in dimensions $d \ge 3$. Combining this result with properties of the PDE and a block construction, we give general, and often asymptotically sharp, conditions for the existence of non-trivial stationary distributions, and for extinction of one type. As applications, we describe the phase diagrams of three systems when the parameters are close to the voter model: (i) a stochastic spatial Lotka-Volterra model of Neuhauser and Pacala, (ii) a model of the evolution of cooperation of Ohtsuki, Hauert, Lieberman, and Nowak, and (iii) a continuous time version of the non-linear voter model of Molofsky, Durrett, Dushoff, Griffeath, and Levin. The first two applications confirm conjectures of Cox and Perkins and Ohtsuki et al.

We introduce a technique, based on perturbation theory for Hamiltonian PDEs, to derive the asymptotic equations of the motion of a free surface of a fluid over a rough bottom (one dimension). The rough bottom is described by a realization of a stationary mixing process which varies on short length scales. We show that the problem in this case does not fully homogenize, and random effects are as important as dispersive and nonlinear phenomena in the scaling regime. We will explain how these technique can be generalized to higher dimensions

The last few years have witnessed an explosion in the number of mathematical models for random graphs and networks, as well as models for dynamics on these network models. In this context I would like to exhibit the power of two well known philosophies in attacking problems in random graphs and networks: First, local weak convergence: The idea of local neighborhoods of probabilistic discrete structures (such as random graphs) converging to the local neighborhood of limiting infinite objects has been known for a long time in the probability community and has proved to be remarkably effective in proving convergence results in many different situations. Here we shall give a wide range of examples of the above methodology. In particular, we shall show how the above methodology can be used to tackle problems of flows through random networks, where we have a random network with nodes communicating via least cost paths to other nodes. We shall show in some models on the completely connected network how the above methodology allows us to prove the convergence of the empirical distribution of edge flows, exhibiting how macroscopic order emerges from microscopic rules. Also, we shall show how for a wide variety of random trees (uniform random trees, preferential attachment trees arising from a wide variety of attachment schemes, models of trees from Statistical Physics etc) the above methodology shows the convergence of the spectral distribution of the adjacency matrix of theses trees to a limiting non random distribution function. Second, scaling limits: For the analysis of critical random graphs, one often finds that properly associated walks corresponding to the exploration of the graph encode a wide array of information (including the size of the maximal components). In this context we shall extend work of Aldous on Erdos-Renyi critical random graphs to the context of inhomogeneous random graph models. If time permits we shall describe the connection between these models and the multiplicative coalescent, arising from models of coagulation in the physical sciences.

We introduce the term `superconcentration' to describe the phenomenon when a function of a Gaussian random field exhibits a far stronger concentration than predicted by classical concentration of measure. We show that when superconcentration happens, the field becomes chaotic under small perturbations and a `multiple valley picture' emerges. Conversely, chaos implies superconcentration. While a few notable examples of superconcentrated functions already exist, e.g. the largest eigenvalue of a GUE matrix, we show that the phenomenon is widespread in physical models; for example, superconcentration is present in the Sherrington-Kirkpatrick model of spin glasses, directed polymers in random environment, the Gaussian free field and the Kauffman-Levin model of evolutionary biology. As a consequence we resolve the long-standing physics conjectures of disorder-chaos and multiple valleys in the Sherrington-Kirkpatrick model, which is one of the focal points of this talk.

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.

For neutral branching models of two types of populations there are three universality classes of behavior: independent branching, (one-sided) catalytic branching and mutually catalytic branching. Loss of independence in the two latter models generates many new features in the way that the populations evolve. In this talk I will focus on describing the genealogy of a catalytic branching diffusion. This is the many individual fast branching limit of an interacting branching particle model involving two populations, in which one population, the "catalyst", evolves autonomously according to a Galton-Watson process while the other population, the "reactant", evolves according to a branching dynamics that is dependent on the number of catalyst particles. We show that the sequence of suitably rescaled family forests for the catalyst and reactant populations converge in Gromov-Hausdorff topology to limiting real forests. We characterize their distribution via a reflecting diffusion and a collection of point-processes. We compare geometric properties and statistics of the catalytic branching forests with those of the "classical" (independent branching) forest. This is joint work with Andreas Greven and Anita Winter.

Reliable information transmission between two sites of a network naturally leads to a percolation problem. When the information to be transmitted is quantum an exciting possibility arises: transform the network performing well chosen measurements to enhance the transmission probability. This idea, introduced recently by Acin, Cirac and Lewenstein is now systematically and successfully applied to a variety of two-dimensional networks, but open questions show that a complete theory is missing. The talk will involve some quanta, some network geometry, some percolation and, hopefully, some fun. No knowledge of quantum theory or percolation theory is assumed. Graduate students are encouraged to attend.

Viewed forwards in time, a population reproducing according to some random mechanism can be thought of as a branching process. What if it is viewed backwards? We can take a sample of individuals from the current generation and trace their genealogy backwards, and for instance find their most recent common ancestor; this is known as a coalescent process. If we know a population's random mating process, but have no actual data as to what the phylogenetic tree looks like, how do we derive the distribution of the time until its most recent common ancestor? I will discuss a variant on the classical Wright-Fisher reproductive model and deduce some parameter thresholds for emergence of different qualitative features of the tree. An isomorphic problem may also be useful in computer science for bounding the running time of certain random sampling algorithms.

Consider a crystal formed of two types of atoms placed at the nodes of the integer lattice. The type of each atom is chosen at random, but the crystal is statistically shift-invariant. Consider next an electron hopping from atom to atom. This electron performs a random walk on the integer lattice with randomly chosen transition probabilities (since the configuration seen by the electron is different at each lattice site). This process is highly non-Markovian, due to the interaction between the walk and the environment. We will present a martingale approach to proving the invariance principle (i.e. Gaussian fluctuations from the mean) for (irreversible) Markov chains and show how this can be transferred to a result for the above process (called random walk in random environment). This is joint work with Timo Sepp\"al\"ainen.

The superprocess or Dawson-Watanabe process is one of the most intensively studied stochastic processes of the last quarter century. It arises as a limit of population processes, and includes information about the physical location of individuals. Usually the superprocess is measure valued, but In one dimension it has a density that satisfies a parabolic stochastic PDE. For a long time uniqueness for this equation was unknown. In joint work with Barlow, Mytnik, and Perkins, we show that nonuniquess holds for the superprocess equation and several related equations.

I will present results on constructing an estimator of a function on a compact manifold for the purpose of recovering its "topology". What this means will be explained in detail. The talk will conclude with an application to brain imaging.

This is a joint work with B.Driver. The groups in question are modeled on an abstract Wiener space. Then a group Brownian motion is defined, and its properties are studied in connection with the geometry of this group. The main results include quasi-invariance of the heat kernel measure, log Sobolev inequality (following a bound on the Ricci curvature), and the Taylor isomorphism to the corresponding Fock space. The latter is a version of the Ito-Wiener expansion in the non-commutative setting.

There has been a flurry of recent activity in studying the topology of point cloud data. However, there is a feeling that we are lacking rigorous null hypotheses to compare with the results. This is one motivation for the following: Take n points, independently and identically distributed in R^d, according to some distribution (for example, a standard normal distribution). Connect them if they are close (within distance epsilon, a function of n), and then build the Cech complex or Rips complex. What can one say about the homology of this complex as n approaches infinity? Or the persistent homology with respect to the radius? Using a variety of techniques, including Poissonization, Stein's method, and discrete Morse theory, we are able to identify phase transitions, and for certain ranges of epsilon prove central limit theorems for the Betti numbers. This is joint work with Gunnar Carlsson and Persi Diaconis.

We introduce some recent advances in the study of nonlinear stochastic heat equations, and related stochastic PDEs. Special attention will be paid to the local structure of the solution. In particular, we show that, frequently, the solution exhibits a form of intermittency. Time permitting, we discuss related connections to classical potential theory and mathematical physics as well.

In Markov chain Monte Carlo, a Markov chain is constructed whose limiting distribution is equal to some target distribution. While it is easy to build such chains, for some distributions the standard constructions can take exponentially long to come near that limit, making the chain torpidly mixing. When the limit is reached in polynomial time, the chain is rapidly mixing. Tempering is a technique designed to speed up the convergence of Markov chains by adding an extra temperature parameter that acts to smooth out the target distribution. In this talk I will present joint work with Dawn Woodard (Cornell) and Scott Schmidler (Duke) that give sufficient conditions for a tempering chain to be torpidly mixing, and a related (but different) set of conditions for the chain to be rapidly mixing.

We study N-player repeated Cournot competitions that model the determination of price in an oligopoly where firms choose quantities. These are nonzero-sum (ordinary and stochastic) differential games, whose value functions may be characterized by systems of nonlinear Hamilton-Jacobi-Bellman partial differential equations. When the quantity being produced is in finite supply, such as oil, exhaustibility enters as boundary conditions for the PDEs. We analyze the problem when there is an alternative, but expensive, resource (for example solar technology for energy production), and give an asymptotic approximation in the limit of small exhaustibility. We illustrate the two-player problem by numerical solutions, and discuss the impact of limited oil reserves on production and oil prices in the dupoly case. Joint work with Chris Harris (Cambridge University) and Sam Howison (Oxford University).

Consider a network of sites growing over time such that at step n a newcomer chooses a vertex from the existing vertices with probability proportional to a function of the degree of that vertex, i.e., the number of other vertices that this vertex is connected to. This is called a preferential attachment random graph. The objects of interest are the growth rates for the growth of the degree for each vertex with n and the behavior of the empirical distribution of the degrees. In this talk we will consider three cases: the weight function w(.) is superlinear, linear, and sublinear. Using recently obtained limit theorems for the growth rates of a pure birth continuous time Markov chains and an embedding of the discrete time graph sequence in a sequence of continuous time pure birth Markov chains, we establish a number of results for all the three cases. We show that the much discussed power law growth of the degrees and the power law decay of the limiting degree distribution hold only in the linear case, i.e., when w(.) is linear

We propose the following model of a random graph on $n$ vertices. Let F be a distribution in R_+^{n(n-1)/2} with a coordinate for every pair ij with 1 \le i,j \le n. Then G_{F,p} is the distribution on graphs with n vertices obtained by picking a random point X from F and defining a graph on n vertices whose edges are pairs ij for which X_{ij} \le p. The standard Erd\H{o}s-R\'{e}nyi model is the special case when F is uniform on the 0-1 unit cube. We determine basic properties such as the connectivity threshold for quite general distributions. We also consider cases where the X_{ij} are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight. This is joint work with Alan Frieze (CMU) and Juan Vera (Waterloo). The talk will be self-contained and no prior knowledge of random graphs is assumed.

The talk will contain a review of several recent results on the analytic continuation of the random analytic functions. We will start from the classical theorem on the random Taylor series (going to Borel’ s school), but the main subject will be the random zeta – function (which was introduced implicitly by Cramer) and its generalizations. We will show that “true primes are not truly random “, since zeta – functions for the random “pseudo-primes” (in the spirit of Cramer) have no analytic continuation through the critical line Re (z) = 1/2.