Mark Huber : Conditions for Parallel and Simulated Tempering to be fast or slow
- Probability ( 142 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.
Omer Bobrowski : Phase transitions in random Cech complexes
- Probability ( 97 Views )A simplicial complex is a collection of vertices, edges, triangles, and simplexes of higher dimensions, and one can think of it as a generalization of a graph. Given a random set of points P in a metric space and a real number r > 0, one can create a simplicial complex by looking at the balls of radius r around the points in P, and adding a k-dimensional face for every subset of k+1 balls that has a nonempty intersection. This construction produces a random topological space known as the Èech complex - C(P,r). We wish to study the homology of this space, more specifically - its Betti numbers - the number of connected components and 'holes' or 'cycles'. In this talk we discuss the limiting behavior of the random Èech complex as the number of points in P goes to infinity and the radius r goes to zero. We show that the limiting behavior exhibits multiple phase transitions at different levels, depending on the rate at which the radius goes to zero. We present the different regimes and phase transitions discovered so far, and observe the nicely ordered fashion in which cycles of different dimensions appear and vanish.
Measure-Theoretic Dvoretzky Theorem and Applications to Data Science
- Probability,Uploaded Videos ( 1378 Views )SEPC 2021 in honor of Elizabeth Meckes. Slides from the talks and more information are available <a href="https://services.math.duke.edu/~rtd/SEPC2021/SEPC2021.html">at this link (here).</a>
Laurie Field : Relating variants of SLE using the Brownian loop measure
- Probability ( 192 Views )In this talk I will discuss a framework for transforming one variant of the SchrammLoewner evolution (SLE) into another. The main tool in this approach is the Brownian loop measure. A simple case is to relate the reversal of radial SLE to whole-plane SLE, which looks the same locally. Writing the formula one might naïvely expect fails, because the loop measure term is infinite. In joint work with Greg Lawler, we show that there is a finite normalized version of the loop measure term, and that with this change, the naïve formula relating the two SLEs becomes correct.
Jasmine Foo : Accumulation and spread of advantageous mutations in a spatially structured tissue
- Probability ( 105 Views )I will discuss a stochastic model of mutation accumulation and spread in a spatially-structured population. This situation arises in a variety of ecological and biological problems, including the process of cancer initiation from healthy tissue. Cancer arises via the accumulation of mutations to the genetic code. Although many mathematical models of cancer initiation have assumed `perfect mixing' or spatial homogeneity, solid tumors often initiate from tissues with well-regulated spatial architecture and dynamics. Here, we study a stochastic model to investigate the temporal dynamics and patterns of mutation accumulation (i.e. how they depend on system parameters such as mutation rate, population size, and selective fitness advantage of mutations). Joint work with R. Durrett (Duke) and K. Leder (Minnesota).
Amir Dembo : Factor models on locally tree-like graphs
- Probability ( 103 Views )Consider factor (graphical) models on sparse graph sequences that converge locally to a random tree T. Using a novel interpolation scheme we prove existence of limiting free energy density under uniqueness of relevant Gibbs measures for the factor model on T. We demonstrate this for Potts and independent sets models and further characterize this limit via large-deviations type minimization problem and provide an explicit formula for its solution, as the Bethe free energy for a suitable fixed point of the belief propagation recursions on T (thereby rigorously generalize heuristic calculations by statistical physicists using ``replica'' or ``cavity'' methods). This talk is based on a joint work with Andrea Montanari and Nike Sun.
Elizabeth Meckes : Projections of probability distributions: a measure-theoretic Dvoretzky theorem
- Probability ( 184 Views )Dvoretzky's theorem tells us that if we put an arbitrary norm on n-dimensional Euclidean space, no matter what that normed space is like, if we pass to subspaces of dimension about log(n), the space looks pretty much Euclidean. A related measure-theoretic phenomenon has long been observed: the (one-dimensional) marginals of many natural high-dimensional probability distributions look about Gaussian. A question which had received little attention until recently is whether this phenomenon persists for k-dimensional marginals for k growing with n, and if so, for how large a k? In this talk I will discuss recent work showing that the phenomenon does indeed persist if k less than 2log(n)/log(log(n)), and that this bound is sharp (even the 2!).
Jonathan Mattingly : Noise induced stabilization of dynamical systems
- Probability ( 193 Views )We investigate an example of noise-induced stabilization in the plane that was also considered in (Gawedzki, Herzog, Wehr 2010) and (Birrell,Herzog, Wehr 2011). We show that despite the deterministic system not being globally stable, the addition of additive noise in the vertical direction leads to a unique invariant probability measure to which the system converges at a uniform, exponential rate. These facts are established primarily through the construction of a Lyapunov function which we generate as the solution to a sequence of Poisson equations. Unlike a number of other works, however, our Lyapunov function is constructed in a systematic way, and we present a meta-algorithm we hope will be applicable to other problems. We conclude by proving positivity properties of the transition density by using Malliavin calculus via some unusually explicit calculations. arXiv:1111.175v1 [math.PR]
Soumik Pal : Markov chains on partitions and their diffusion analogs
- Probability ( 104 Views )A popular family of models of random partitions is called the Chinese Restaurant Process. We imagine n customers being seated randomly and sequentially at tables of a restaurant according to a fixed stochastic rule. Grouping customers by the tables gives us a partition of n. Consider a Markov chain on such partitions where we remove a randomly chosen customer and reseat her. How can one describe the limit of such a Markov chain as n tends to infinity? We will construct such limits as diffusions on partitions of the unit interval. Examples of such random partitions of the unit interval are given by the complement of the zeros of the Brownian motion or the Brownian bridge. The processes of ranked interval lengths of our partitions are members of a family of diffusions introduced by Ethier and Kurtz (1981) and Petrov (2009) that are stationary with respect to the Poisson-Dirichlet distributions. Our construction is a piece of a more complex diffusion on the space of real trees, stationary with respect to the law of the Brownian Continuum Random Tree, whose existence has been conjectured by David Aldous. Joint work with Noah Forman, Doug Rizzolo, and Matthias Winkel.
Corrine Yap : Reconstructing Random Pictures
- Probability ( 69 Views )Reconstruction problems ask whether or not it is possible to uniquely build a discrete structure from the collection of its substructures of a fixed size. This question has been explored in a wide range of settings, most famously with graphs and the resulting Graph Reconstruction Conjecture due to Kelly and Ulam, but also including geometric sets, jigsaws, and abelian groups. In this talk, we'll consider the reconstruction of random pictures (n-by-n grids with binary entries) from the collection of its k-by-k subgrids and prove a nearly-sharp threshold for k = k(n). Our main proof technique is an adaptation of the Peierls contour method from statistical physics. Joint work with Bhargav Narayanan.
Leonid Petrov : Spectral theory for interacting particle systems
- Probability ( 100 Views )I plan to discuss spectral theory-type results for several stochastic interacting particle systems solvable by the coordinate Bethe ansatz. These results include Plancherel type isomorphism theorems which imply completeness and biorthogonality statements for the corresponding Bethe ansatz eigenfunctions. These constructions yield explicit solutions (in terms of multiple contour integrals) for backward and forward Kolmogorov equations with arbitrary initial data. Some of the formulas produced in this way are amenable to asymptotic analysis. In particular, I will discuss the (stochastic) q-Hahn zero-range process introduced recently by Povolotsky, and also the Asymmetric Simple Exclusion Process (ASEP). In particular, the spectral theory provides a new proof of the symmetrization identities of Tracy and Widom (for ASEP with either step or step Bernoulli initial configuration). Another degeneration takes the q-Hahn zero-range process to the stochastic q-Boson particle system dual to q-TASEP studied by Borodin, Corwin et al. Thus, at the spectral theory level we unify two discrete-space regularizations of the Kardar-Parisi-Zhang equation / stochastic heat equation, namely, q-TASEP and ASEP.
Manon Michel : Non-reversible Markov processes in particle systems
- Probability ( 31 Views )Recently, Markov-chain Monte Carlo methods based on non-reversible piecewise deterministic Markov processes (PDMP) are under growing attention, thanks to the increase in performance they usually bring. Beyond their numerical efficacy, the non-reversible and piecewise deterministic characteristics of these processes prompt interesting questions, regarding for instance ergodicity proof and convergence bounds. During this talk, I will particularly focus on the obtained results and open problems left while considering PDMP evolution of particle systems, both in an equilibrium and out-of-equilibrium setting. Hardcore particle systems have embodied a testbed of choice since the first implementations of Markov chain Monte Carlo in the 50’s. Even today, the entropic barriers they exhibit are still resisting to the state-of-the-art MCMC sampling methods. During this talk, I will review the recent developments regarding sampling such systems and discuss the dynamical bottlenecks that are yet to be solved.
Pascal Maillard : Interval fragmentations with choice
- Probability ( 124 Views )Points fall into the unit interval according to a certain rule, splitting it up into fragments. An example rule is the following: at each step, two points are randomly drawn from the unit interval and the one that falls into the smaller (or larger) interval is discarded, while the other one is kept. This process is inspired by the so-called "power of choice" paradigm originating in the computer science literature on balanced load allocation models. The question of interest is how much the rule affects the geometry of the point cloud. With Elliot Paquette [1] we introduced a general version of this interval fragmentation model and showed that the empirical distribution of rescaled interval lengths converges almost surely to a deterministic probability measure. I will report on this work as well as on work in progress [2] where we show that the empirical measure of the points converges almost surely to the uniform distribution. The proofs involve techniques from stochastic approximation, non-linear integro-differential equations, ergodic theory for Markov processes and perturbations of semigroups on L^p spaces, amongst other things. [1] Maillard, P., & Paquette, E. (2016). Choices and intervals. Israel Journal of Mathematics, 212(1), 337384. [2] Maillard, P., & Paquette, E. (in preparation). Interval fragmentations with choice: equidistribution and the evolution of tagged fragments
Hendrik Weber : Convergence of the two-dimensional dynamic Ising-Kac model
- Probability ( 192 Views )The Ising-Kac model is a variant of the ferromagnetic Ising model in which each spin variable interacts with all spins in a neighbourhood of radius $\ga^{-1}$ for $\ga \ll1$ around its base point. We study the Glauber dynamics for this model on a discrete two-dimensional torus $\Z^2/ (2N+1)\Z^2$, for a system size $N \gg \ga^{-1}$ and for an inverse temperature close to the critical value of the mean field model. We show that the suitably rescaled coarse-grained spin field converges in distribution to the solution of a non-linear stochastic partial differential equation. This equation is the dynamic version of the $\Phi^4_2$ quantum field theory, which is formally given by a reaction diffusion equation driven by an additive space-time white noise. It is well-known that in two spatial dimensions, such equations are distribution valued and a \textit{Wick renormalisation} has to be performed in order to define the non-linear term. Formally, this renormalisation corresponds to adding an infinite mass term to the equation. We show that this need for renormalisation for the limiting equation is reflected in the discrete system by a shift of the critical temperature away from its mean field value. This is a joint work with J.C. Mourrat (Lyon).
Jay Newby : Spontaneous neural activity from stochastic ion channels
- Probability ( 97 Views )How does intrinsic noise from stochastic ion channels affect spontaneous activity in a single neuron? The size of a neuron affects how many ion channels in the membrane facilitate the generation of action potentials. Fewer ion channels causes an increase in the number of spontaneous action potentials. The density of neural tissue is therefore fundamentally limited by spontaneous activity. Evolutionary pressure tends to favor neural tissue with higher density for a variety of reasons, but the increase in spontaneous activity limits how dense it can become and still remain functional. I will talk about how large deviation theory can be used to quantify the relationship between ion channels (type and number) and spontaneous activity.
Eric Foxall : Social contact processes and the partner model.
- Probability ( 110 Views )We consider a model of infection spread on the complete graph on N vertices. Edges are dynamic, modelling the formation and breakup of non-permanent monogamous partnerships, and the infection can spread only along active edges. We identify a basic reproduction number \(R_0\) such that the infection dies off in \(O(\log N)\) time when \(R_0\)<1, and survives for at least \(e^{cN}\) time when \(R_0\)>1 and a positive fraction of vertices are initially infectious. We also identify a unique endemic state that exists when \(R_0\)>1, and show it is metastable. When \(R_0\)=1, with considerably more effort we can show the infection survives on the order of \(N^{1/2}\) amount of time.
Roberto I. Oliveira : Estimating graph parameters via multiple random walks
- Probability ( 132 Views )What can one say about a graph from multiple (short) random walk trajectories on it? In this talk we consider algorithms that only "see" walk trajectories and the degrees along the way. We will show that the number of vertices, edges and mixing time can be all estimated with a number of RW steps that is sublinear in the size of the graph and in its mixing or relaxation time. Our bounds on the number of RW steps are optimal up to constant or polylog factors. We also argue that such algorithms cannot "know when to stop", and discuss additional conditions that circumvent this limitation. To analyse our results, we rely on novel bounds for random walk intersections. The lower bounds come from a family of explicit constructions.
Santosh Vempala : Logconcave Random Graphs
- Probability ( 145 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.
Philip Matchett Wood : Random doubly stochastic tridiagonal matrices
- Probability ( 105 Views )Let $T_n$ be the compact convex set of tridiagonal doubly stochastic matrices. These arise naturally as birth and death chains with a uniform stationary distribution. One can think of a typical matrix $T_n$ as one chosen uniformly at random, and this talk will present a simple algorithm to sample uniformly in $T_n$. Once we have our hands on a 'typical' element of $T_n$, there are many natural questions to ask: What are the eigenvalues? What is the mixing time? What is the distribution of the entries? This talk will explore these and other questions, with a focus on whether a random element of $T_n$ exhibits a cutoff in its approach to stationarity. Joint work with Persi Diaconis.
David Herzog : Hypocoercivity for Langevin dynamics
- Probability ( 146 Views )This will be the last in his sequence of an introductory lecture on Hypocoercivity for Langevin dynamics. For those who have not attended the previous lectures and are familiar with Langevin dynamics, the talk should be accessible. We will continue our discussion on convergence to equilibrium for second-order Langevin dynamics using the Poincare approach. We'll recap convergence in H^1(\mu) and then we'll talk about the direct L^2(\mu) method of Dolbeault, Mouhot, and Schmeiser, also called the DMS approach.