Scott Schmidler : Mixing times for non-stationary processes
- Probability ( 191 Views )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.
Jasmine Foo : Modeling diversity in tumor populations and implications for drug resistance
- Probability ( 103 Views )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)
George Tauchen : The Realized Laplace Transform of Volatility
- Probability ( 98 Views )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.
Josh Socolar : Exhaustive Percolation and Random Boolean Networks
- Probability ( 100 Views )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.
Shankar Bhamidi : Flows, first passage percolation and random disorder in networks
- Probability ( 206 Views )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.
Partha Dey : Central Limit Theorem for First-Passage Percolation along thin cylinders
- Probability ( 104 Views )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.
Krishna Athreya : Coalescence in Galton-Watson trees
- Probability ( 194 Views )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.
Ivan Matic : Deterministic Walks in Random Environments
- Probability ( 95 Views )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.
David Sivakoff : Random Site Subgraphs of the Hamming Torus
- Probability ( 146 Views )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.
Rick Durrett : Voter Model Perturbations
- Probability ( 186 Views )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.
Oliver R Diaz : Long wave expansions for water waves over random bottom
- Probability ( 100 Views )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
Leonid Bogachev : Gaussian fluctuations for Plancherel partitions
- Probability ( 115 Views )The limit shape of Young diagrams under the Plancherel measure was found by Vershik & Kerov (1977) and Logan & Shepp (1977). We obtain a central limit theorem for fluctuations of Young diagrams in the bulk of the partition 'spectrum'. More specifically, under a suitable (logarithmic) normalization, the corresponding random process converges (in the FDD sense) to a Gaussian process with independent values. We also discuss a link with an earlier result by Kerov (1993) on the convergence to a generalized Gaussian process. The proof is based on poissonization of the Plancherel measure and an application of a general central limit theorem for determinantal point processes. (Joint work with Zhonggen Su.) (see more details hear.
Shankar Bhamidi : Two philosophies for random graphs and networks: Local weak convergence and scaling limits
- Probability ( 100 Views )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.
Sourav Chatterjee : Superconcentration
- Probability ( 107 Views )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.
Asaf Nachmias : The Alexander-Orbach Conjecture Holds in High Dimensions
- Probability ( 124 Views )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.
Lea Popovic : Genealogy of Catalytic Populations
- Probability ( 214 Views )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.
Jan Wehr : Entanglement percolation in quantum networks
- Probability ( 142 Views )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.
John McSweeney : A Nonuniform Stochastic Coalescent Process with applications to Biology and Computer Science
- Probability ( 209 Views )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.
Firas Rassoul-Agha : On the almost-sure invariance principle for random walk in random environment
- Probability ( 201 Views )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.
Carl Mueller : Nonuniqueness for some stochastic PDE
- Probability ( 111 Views )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.
Peter Bubenik : Multivariate topological data analysis
- Probability ( 111 Views )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.
Maria Gordina : Gaussian type analysis on infinite-dimensional Heisenberg groups
- Probability ( 170 Views )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.
Matthew Kahle : Homology of geometric random complexes
- Probability ( 149 Views )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.
Davar Khoshnevisan : Nonlinear Stochastic Heat Equations: Existence, Growth, and Intermittency
- Probability ( 141 Views )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.
Mark Huber : Conditions for Parallel and Simulated Tempering to be fast or slow
- Probability ( 143 Views )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.
Ronnie Sircar : Games with Exhaustible Resources
- Probability ( 151 Views )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).
Krishna Athreya : Preferential attachment random graphs with general weight function
- Probability ( 147 Views )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
Santosh Vempala : Logconcave Random Graphs
- Probability ( 146 Views )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.
Stanislav Molchanov : On the random analytic functions
- Probability ( 219 Views )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.