Student Probability and Related Fields Seminar

I will introduce some common random graph models initiated by Erdos and Renyi. The subject has a long history and I have only recently started looking at the relevant literature. I will try to collect some basic facts about random graphs (in no way comprehensive), including some startling zero-one law from a logic perspective, and prove one result or two about the distribution of the largest component of a random graph using martingale method. The prerequisite of the talk will be minimum.

I will introduce the concept of Markov type and cotype as suggested by K. Ball, and give a short description as to spaces which have certain Markov types and cotypes. I will then mention the original extension problems which the concept was introduced to prove, and discuss the first results of A. Naor and M. Mendel of the embedding of $(0, \ldots, m)^n$ with the $l^p_n$ metric into any 2-uniformly convex Banach space with small distortion.

I will talk about the paper Affine Processes and Applications in Finance by Duffie, Filipovic, and Schachermayer (2002) in which affine processes in Euclidean spaces and half-spaces were characterized after being used more than 30 years in various areas of mathematical finance, e.g. in derivative pricing or fixed income models. I will discuss the results of the paper and emphasize their importance in financial applications. In the end I will present some purely probabilistic open questions about affine processes.

I will be talking about the paper Random Walks on Truncated Cubes and Sampling 0-1 Knapsack solutions by Ben Morris and Alistair Sinclair. This paper finds polynomial bounds for the mixing of a Markov chain on a hypercube truncated by a hyperplane using random path methods, using the concept of balanced almost uniform permutations.

The project implements the method of pathwise derivatives in MC using adjoint algorithmic differentiation in the context of credit related instruments. Given a portfolio of names with specified hazard rates and pairwise default correlations, we want to estimate the default correlation risk of basket default products. Whereas the traditional method of bumping produces reasonable results as the size of the bump becomes small, the main focus is to obtain the same degree of accuracy while considerably improving the time efficiency of the calculations.

Let M be a compact, smooth Riemannian manifold. Varadhan proved that tlog*p_t(x,y), where p is heat kernel, converges to -E(x,y) where E(x,y) is an energy function defined by distance between x and y. Malliavin and Stroock showed that under some condition, the hessian is asymptotic to -1/t times the variance of a random variable as t goes to zero and Neel more recently described a method to compute the hessian as simply an integral over the set of midpoints of a minimal geodesic from x to y. I will determine such set and compute the hessian of several symmetric spaces such as sphere, projective spaces and Lie Groups.

The calibration of the local volatility model is based on the Dupire equation. However, this equation becomes difficult once the default term is introduced. I will present the original calibration technique as well as explain how to handle the difficulty caused by the default term.

Optimal transport was originally studied round the time of WWII and dealt with the best way of moving materials to different factories. Times have changed and now it has many applications in geometry and probability. I will give basic definitions and provide an introduction to the method of duality used, among others, to obtain bounds on quantities of interest.

Let $U \subseteq \C$ be a bounded domain with smooth boundary and let $F$ be an instance of the continuum Gaussian free field on $U$ with respect to the Dirichlet inner product $\int_U \nabla f(x) \cdot \nabla g(x) dx$. The set $T_U(a)$ of $a$-thick points of $F$ consists of those $z \in U$ such that the average of $F$ on a disk of radius $r$ centered at $z$ has growth $\sqrt{a/\pi} \log \tfrac{1}{r}$ as $r \to 0$. We show that for each $0 \leq a \leq 2$ the Hausdorff dimension of $T_U(a)$ is almost surely $2-a$ and that $T_U(a)$ is invariant under conformal transformations in an appropriate sense. The notion of a thick point is connected to the Liouville quantum gravity measure with parameter $\gamma$ given formally by $\Gamma(dz) = e^{\gamma F(z)} dz$ considered by Duplantier and Sheffield. (Joint work with Xiaoyu Hu and Yuval Peres)

I will describe the progress made in the so-called Kac's model, which is a continuous state space, discrete time Markov chain on either the unit (n-1)-sphere or SO(n). The problem originated from the pair-wise particle collision problem in physics and the unrealistic assumption that total momentum is not conserved (but total energy is). I will prove the best possible L^2 Wasserstein convergence rate of this Markov chain to stationarity and if time permit, indicate briefly the total variation convergence starting from an L^2 initial distribution. A model in which total momentum is conserved will also be outlined and results stated in that case. I would also like to sketch some generalizations I proved along the same line as Olliviera's paper on L^2 Wasserstein convergence rate.

I will follow Elton Hsu's excellent introduction to the subject of stochastic calculus on manifolds and discuss the "easy" construction of a Brownian motion on a Riemannian manifold. In particular I will show that Brownian motions defined on manifolds with bounded negative curvature (known as Cartan Hardamard manifolds) are transient. In the next meeting I will talk about the "hard" construction of Brownian motion due to Eells-Elworthy-Malliavin, which is suitable for stochastic differential equations.

First, I will try to give a rigorous proof that the solution to an SDE along vector fields of an imbedded manifold stays on the manifold almost surely. Second, I will give an explicit formula for the standard Brownian motion on the n-sphere and prove the Ito's Lemma for Manifold-valued Brownian motion. Last, I will state the Laplacian comparison theorem which is needed to show certain manifolds are stochastically complete as well as transience property of Brownian motions. There will be room for clarification of foundational stuff.

I will discuss Morris' bounds on the mixing time of the simple exclusion process on the lattice. The talk will not go into too many details, but will explain the exclusion process, Morris' related 'chameleon process', the method of entropy, and a few highlights of the proof. If I have time, I will try to relate this proof to the evolving set method, which underlies much of it.

I will describe the recent program carried out by Yau and his coauthors (Erdos, Ramirez, Schlein, Yin, etc) on using Log sobolev inequality and Bakry-Emery contraction principle to bound the mixing time of local eigenvalue distribution of Dyson's Brownian motion to its conditional equilibrium measure. This extends results on local eigenvalue statistics of the Gaussian Unitary Ensemble to the Wigner ensemble, where we replace Gaussian entries by iid random variables of other kinds. Even though later developments have eclipsed the strength of their result, the beautiful connection it makes with Markov chain theory deserves greater publicity. I also found a useful application of their machinery, perhaps not accessible otherwise. If time permits, I will describe their recent resolution of a famous conjecture by Dyson on the exact mixing time of local eigenvalue process under DBM.

The birthday paradox states that at least two out of any 23 people share a common birth date with at least probability 0.5. The calculation for this problem assumes that all birth dates are equally likely. What if the distribution of birth dates is non-uniform and possibly even unknown? Further what if we focus on birthdays shared by two friends rather than any two people? I will present some of our results and conjectures in this generalized setting. I will also show how these results are related to the Stanley chromatic conjecture and the 'shameful conjecture', two famous conjectures in combinatorics.

Consider a Markov chain on a space X with unique stationary distribution. We aim to find a suitably "small" subset C of X towards which the chain tends to drift. If C is a single point, a coupling argument bounds the rate of convergence to equilibrium in terms of the rate of drift towards C. Harris recurrence techniques extend this argument to the case where C satisfies a certain minorization condition. Meyn and Tweedie proved that after t steps, the distance from stationarity is bounded by cr^t, where r<1 depends only on the rate of drift towards C. Unfortunately, the constant c is non-explicit and might be very large. I will discuss some extra hypotheses under which there is an explicit formula for c, and whether the results obtained thereby are useful. This is work of Rosenthal; Roberts and Tweedie; Bakry, Cattiaux, and Guillin; and Dey.

The Ewens sampling formula is a one-parameter family of measures on permutations weighted by the number of cycles. It is intimately connected with rates of mutation, and not surprisingly was first conceived as a model in genetics, but also arises in urn problems, card shuffling and Bose-Einstein condensation. I will present a selection of results with the goal of demonstrating that "rates of mutation" is an inherently combinatorial notion that applies to a wide range of problems.

Consider an irreducible aperiodic Markov chain on a finite state space. After t steps, the distance from stationarity can be bounded by cr^t for some constants c and r. It is natural to look for the smallest value of r that works. Unfortunately, when the chain is non-normal, the associated value of c may be very large. I will explain how this is possible and discuss alternatives.

We prove that many well-known families of statistics on the symmetric groups are asymptotically independent under the uniform measure. These statistics can be used to construct metrics on permutations, which are useful in nonparametric correlation studies. If time permits, extensions to other finite groups as well as continuous models will be discussed.

I will introduce a family of Gibbs samplers on convex sets, briefly review some general bounds, and then talk about a specific Gibbs sampler on the simplex. In particular, I'll construct a non-Markovian coupling which gives nearly optimal mixing time bounds. I'll briefly discuss some small extensions, and how they go horribly wrong.

In this talk I will show how concentration of measure techniques can be applied in the context of interacting diffusion processes. More precisely, I will present various tail decay bounds for paths of multidimensional diffusion processes with respect to the uniform norm. In particular, these results can be used to prove concentration of measure for reflected diffusion processes and infinite systems of Brownian particles. This is joint work with Soumik Pal.

There's been much analysis of the following model of rock breaking: split a rock into two by some probability distribution, then iterate this process on the smaller resulting rocks. This has a nice algebraic generalisation to taking Hopf powers on graphs and other species. If there's time, I'll outline how we can find the multiplicities of the eigenvalues of the transition matrix using only basic linear algebra.

The Sherrington-Kirkpatrick model represents the behaviour of a magnet with random ferromagnetic or antiferromagnetic interactions between any two pairs of particles. The free entropy of this system represents the amount of work that can be done by this magnet, and was proved to converge almost surely to a limit by Guerra and Toninelli (2002). I will present a result of Carmona and Hu (2006) that proves this limit does not depend on the distribution of interactions between particles.

In random walk on a cyclic group, how should the generators be chosen so as to minimize the mixing time? I'll discuss this and give some bounds on the fastest possible mixing time.

It is well known now that the local eigenvalue distribution of the Gaussian Unitary Ensemble converges to a determinantal point process governed by the sine kernel, and that this is universal in the class of Wigner ensembles. More generally, the eigenvalue clusters in two regions separated in macroscopic scale converge to two independent such processes. I will mention two approaches to establish universality of the asymptotic independence phenomenon: one in terms of local relaxation flow, as developed by Erdos, Ramirez, Schlein, and Yau. The other approach uses classical contour integration and saddle point analytic tools; this was developed initially by Johansson, and later by Erdos, Peches, Ramirez, Schlein and Yau. I will focus on the latter approach for the talk.

In this talk, I will build on work of Diaconis and Wood concerning random birth and death (BD) chains. I'll begin by defining BD chains, and talking about sampling algorithms on them, both my own and those by Diaconis and Stanley. I'll then develop some properties of random BD chain with unimodal stationary distribution, and use them to show that these chains are less likely to exhibit cutoff than those obtained by the Metropolis algorithm. Finally, I show some families of stationary distribution for which cutoff can be obtained, and describe future directions for work.

The drift-minorization approach is a very broadly applicable method of finding upper bounds for the mixing time of Markov chains. In general, the bounds are not very good, but under certain monotonicity conditions one can obtain good results. Even then, a fair amount of computation is necessary. I will introduce an algorithm for computing exponential moments of hitting times and show how it can be used to get bounds in these situations.

The Hopfield model is a spin glass model with an interpretation as a simple neural network. I will give an introductory overview of the Hopfield model, and describe a new result in the parameter region of superlinearly many patterns.

We consider the ferromagnetic Potts model on typical d-regular graphs, and the independent set model on typical bipartite d-regular graphs, with graph size tending to infinity. We compute the asymptotic free energy density for all parameter values in these two models, and show that the value coincides with the Bethe prediction of statistical physics. In this talk I will describe some of the proof techniques, which will give an indication of the contrast with the anti-ferromagnetic Potts model and the independent set model at high fugacity on non-bipartite graphs, where the Bethe prediction is known to fail. This is joint work with Amir Dembo, Andrea Montanari, and Allan Sly.

We prove an O(n^3) upper bound for the convergence rate to stationarity of the so-called uniformized Rosenthal walk on SO(n). This is the first polynomial time upper bound for this walk, which interpolates between the original Rosenthal's random $\pi$ rotation walk and Kac's random walk on SO(n). The techniques are similar to the ones used by Rosenthal. One new ingredient used here is the interpretation of the character ratio Fourier coefficients as arising from the branching rules of classical Lie groups. Since the proof is relatively short, the exposition will be completely self-contained, modulo some naive understanding about representation theory. The work could not have been completed without generous help from Bob Hough.

From chemical systems to population dynamics, many Markov chain models look like small random perturbations to an underlying system of ODE's. In this talk, I will discuss Kurtz's theorem, a way of formalizing this idea and proving concentration results. I will then go over a few applications, illustrating concentration both around short-term evolution of an ODE and long-term asymptotics.

I'll describe the Dirichlet process over the interval and show how this defines a measure on Wasserstein space (probability measures equipped with a certain metric, which I'll define). Then, I'll discuss why this allows us to ask whether or not this space has "positive Ricci curvature," in the sense of a certain functional (the entropy functional) being convex in the appropriate sense. We'll say why one might hope this was true, and then sketch the proof that it is not.

In this talk I will attempt to draw analogies between three notions of mixing times from different fields (probability, PDE, and ergodic theory).

Let P be the transition kernel for a Markov chain on a finite or countable state space. Assume the chain is reversible and 1/2-lazy. It is a natural conjecture that given any fixed state c, for every state x and positive integer n, P^n(c,c) is greater than or equal to P^n(x,c). Unfortunately, this conjecture is false. I will present a simple counterexample and then explain a weaker form of the conjecture which was proved true by Lund, Zhao, and Kiessler. Finally, I will demonstrate a coupling argument that uses the LZK result to bound the chain's rate of convergence to stationarity.

Metropolis-Hastings algorithm has been named \emph{the} most important algorithm of the century. It is one of the most general recipes for Markov chain Monte-Carlo, and empirical evidence all suggests that sampling using Metropolis algorithm is extremely efficient. Nonetheless, according to Persi Diaconis, almost no good theoretical results are available to backup the claim. Here we present a sharp mixing time analysis of a Metropolis algorithm that converges to the Ewens sampling distribution on the symmetric groups, based on the random transposition walk. The main technical input is the Jack symmetric functions, which are 1-parameter generalizations of the Schur polynomials. There is the question of whether similar analysis can be carried out for metropolis walks based on random k-cycle shuffle; however this is far from clear. This is continuation of work by Diaconis and Hanlon.

I will discuss total variation mixing time analysis for a random walk on the orthogonal group generated by either deterministic or random rotation matrices. The work extends earlier analysis of Rosenthal, in particular, we demonstrate a cut-off phenomenon. This is joint work with John Jiang.

A long-standing question in the theory of Markov chains concerns the amount of time it takes for a chain to first enter a given state. I will briefly go over some old results on this topic, including classical results on the expected hitting time and Karlin & McGregor's analytic approach for birth and death chains. I will then discuss some of the more modern takes on the subject, including the more probabilistic proofs of Miclo, Fill, Diaconis and others.

Are you sitting comfortably? Then I'll tell you the story behind Persi Diaconis and Jason Fulman's paper "Foulkes characters, Eulerian idempotents and an amazing matrix", and my attempts to generalise it. It concerns how the descent set of a deck of cards changes as one shuffles.

Comparison is a powerful strategy for the analysis of Markov chains. To study a chain of interest, a related but simpler or more symmetric chain is analyzed completely, and the results transferred to the original chain. This theory has been developed by Diaconis, Saloff-Coste, and others for chains on the same state space. However, in many examples, a natural `symmetrized' walk takes place on a larger state space. I discuss how extensions can be used to compare walks on different state spaces, with some simple illustrations. I'll then go over a more difficult example, comparing simple random walk on derangements to a related simple random walk on permutations. This talk is a mixture of current analyses, future projects, and joint work with John Jiang.

The original Kac random walk only prescribes conservation of energy of the particle system. If one imposes linear momentum conservation, the system degenerates into the random transposition shuffle walk on S_n. In order to have a continuous model, one has to put the particles in higher dimensions > 1. Here I discuss some previous work on these extended models, and derive some new master equation analogous to the walk on the Lie group SO(n). A strange phenomenon occurs in dimension 2. I will also discuss a few related models arising from quantum computing. Finally if time permits, some simulation results on the Wasserstein mixing time of the original Kac walk will be presented.