Berkeley Probability Seminar
Wednesdays, 3:10 - 4:00pm
330 Evans Hall

 Organizers: David Aldous Nayantara Bhatnagar

 Mathematics Statistics Berkeley Probability Group Maps & Directions Previous Seminars

# Spring 2008

30 Jan Nayantara Bhatnagar (UC Berkeley) Reconstruction for Colorings on Trees. Maxim Krikun (Institut Elie Cartan, Universite Henri Poincare) Stationary Measures for Ballistic Annihilation with Branching. Fabio Martinelli (University of Rome III) Dynamical Relaxation of a 1D Pinning Model. *Note the unusual day Kshitij Khare (Stanford) From Markov Chains to Gaussian Priors and Back. Elizabeth Meckes (Case Western Reserve University) Normal Approximation with Continuous Symmetries. Matina Rassias (UC Berkeley) Stochastic Differential Delay Equations. Amarjit Budhiraja (UNC Chapel Hill)Elliott-Kalton Stochastic Differential Games Associated with the Infinity Laplacian. Isaac Meilijson (Tel Aviv University)On the Expected Diameter of an L_2-bounded Martingale. Asaf Nachmias (UC Berkeley)The Alexander-Orbach conjecture holds in high dimensions. No seminar Allan Sly (UC Berkeley)Mixing on Random Graphs. David Aldous (UC Berkeley)Spatial Random Networks. Jason Fulman (USC)  Commutation Relations and Markov Chains Vlada Limic (CNRS)

# Abstracts

Reconstruction for Colorings on Trees.
Nayantara Bhatnagar (UC Berkeley)

Consider a process where some information is propagated from the root of a tree along the branches to all the leaves. During the transmission, the information is modified by a random process at each vertex. The question of reconstruction is whether the information available at the leaves give any significant information about the information at the root. The question arises naturally in a number of areas including transmission of genetic information in a tree of ancestors, noisy communication networks on trees, information theory and statistical physics.

We will survey what is known about the problem, questions that remain unresolved, and present some recent work (joint with Juan Vera and Eric Vigoda) on the reconstruction problem for proper colorings of  trees.
top of page

Stationary Measures for Ballistic Annihilation with Branching.
Maxim Krikun (Institut Elie Cartan, Universite Henri Poincare)

A basic model of ballistic annihilation consists of a system of particles in one-dimensional space, moving in either direction with constant speed and annihilating upon collision, so that eventually most of the particles disappear.

When branching is introduced into the picture, the system becomes stable and admits a non-trivial stationary measure. Also, the union of trajectories of all particles, seen as a subset of the plane, has some interesting properties.

This is a joint work with Seruei Popov (USP)
and Philippe Chassaing and Lucas Gerin (IECN).
top of page

Dynamical Relaxation of a 1D Pinning Model.
Fabio Martinelli (University of Rome III)

We consider paths of a one–dimensional simple random walk conditioned
to come back to the origin after L steps,  In the pinning model each path
has a weight  exp(c N(η)), where  N is the number of zeros in the path and c, the
pinning strength can be positive or negative. When
the paths are constrained to be non–negative, the polymer is said to satisfy a hard–
wall constraint. Such models are well known to undergo a localization/delocalization
transition as the pinning strength is varied. In this paper we study a natural "spin
flip" dynamics for these models, derive several estimates on its spectral gap and
mixing time and discuss a possible signature of the phase transition on the dynamics.

Joint work with F. Toninelli and P. Caputo.
top of page

From Markov Chains to Gaussian Priors and Back.
Kshitij Khare (Stanford)

The Dynkin isomorphism associates a Gaussian field to a Markov chain. These Gaussian fields can be used as priors for prediction and time series analysis. The older construction gives fields with all positive covariances. A parallel construction of Diaconis-Evans gives fields with all covariances negative. This work is extended to allow general covariance sign patterns.
top of page

Normal Approximation with Continuous Symmetries.
Elizabeth Meckes (Case Western Reserve University)

I will describe a modification of Stein's method of exchangeable pairs for normal approximation, for situations in which a random variable is invariant under the action of a continuous group of symmetries.  I will discuss two applications of the method: firstly, to the distributions of eigenfunctions of the Laplacian on compact Riemannian manifolds, and secondly, to approximation of random orthogonal and unitary matrices by Gaussian matrices.
top of page
Stochastic Differential Delay Equations.
Matina Rassias (UC Berkeley)

Khasminskii (1969), introduced a powerful test for stochastic differential equations (SDEs) to have non-exploding solutions without satisfying a linear growth condition. Mao (2002), extended the above idea for stochastic differential delay equations (SDDEs). We (with our PhD dissertation, 2008) investigated an even more general Khasminskii-type test for SDDEs which covers a wide class of highly non-linear SDDEs and presented some moment estimates and almost sure asymptotic estimates in order to study the long-term behavior of the solution. In our talk we discuss some of the above mentioned results.
top of page
Elliott-Kalton Stochastic Differential Games Associated with the Infinity Laplacian.
Amarjit Budhiraja (UNC Chapel Hill)

Let G be a bounded domain in Rm and let $g:\partial G\to R$, $h:\stackrel{}{G}\to R$ be given continuous functions. In a recent work, Peres, Schramm, Sheffield, Wilson [PSSW] have considered a two player, zero sum, discrete time stochastic game, called Tug of War. In this game, at each time instant $k\in N$, one of the two players is selected by toss of a fair coin who is then allowed to move the state Xk by an amount that is bounded by ε $\in \left(0,\infty \right)$. The game ends at the first time instant $k$ when Xk $\in \partial G$ with a payoff of g(Xk)-(ε2/2)Σj=0k-1h(Xj). Player 1 seeks to maximize this payoff while Player 2 aims to minimize it. It is shown in [PSSW] that if inf h > 0 then the game has a value uε and as ε$\to 0$, uε converges uniformly to the "continuum value" u which is the unique viscosity solution of the equation:
 $\left\{\begin{array}{cc}\hfill {\Delta }_{\infty }u\left(x\right)=-2h\left(x\right),& \mathrm{ }x\in \mathrm{G;}\hfill \\ \hfill \\ \hfill u\left(x\right)=g\left(x\right),& \mathrm{ }x\in \partial G.\hfill \end{array}$ $\left(1\right)$
Here ${\Delta }_{\infty }f = \left(Df/|Df|\right)\text{'} D2f\left(Df/|Df|\right) is the infinity Laplacian operator.$
In this work we consider a continuous time two player zero sum stochastic differential game that is motivated by the Tug of War game of [PSSW]. The state dynamics are driven by a one dimensional Brownian motion and each player can control both drift and diffusion coefficients. In particular, diffusion control term can be unbounded and possibly lead to degenerate dynamics. We show that the game has a value in the usual Elliott-Kalton sense which is characterized as the unique viscosity solution of (1). Thus the result provides a game theoretic interpretation of the "continuum value" $u$ in the [PSSW] analysis.
This is a joint work with Rami Atar.
top of page
On the Expected Value of an L_2-bounded Martingale
Isaac Meilijson (Tel Aviv University)

It is shown that the ratio between the expected diameter of an L_2-bounded martingale and the standard deviation of its last term cannot exceed sqrt{3}. A quantity related to diameter, maximal drawdown (or rise), is introduced and its expectation is shown to be bounded by sqrt{2} times the standard deviation of the last term of the martingale. These results complement the Dubins & Schwarz respective bounds 1 and sqrt{2} for the ratios between the expected maximum and maximal absolute value of the martingale and the standard deviation of its last term. All four bounds are sharp.

Authors: Lester E. Dubins, David Gilat, Isaac Meilijson
top of page
The Alexander-Orbach Conjecture Holds in High Dimensions
Asaf Nachmias (UC Berkeley)

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.

top of page
Mixing on Random Graphs
Allan Sly (UC Berkeley)

Understanding Gibbs measures on trees and their spatial mixing thresholds (uniqueness, strong spatial mixing, reconstruction) can give insight into the behavior of Gibbs measures on general graphs, in particular random graphs which are locally tree-like.  We discuss a number of cases where tree thresholds determine / does not determine the spatial and temporal mixing properties of Gibbs measures on general and random graphs. Partially based on joint work with E. Mossel.
top of page

Spatial Random Networks
David Aldous (UC Berkeley)

I will give an overview of ongoing research concerning networks linking random vertices in two-dimensional space, emphasising two aspects.

(1) If we get to choose edges, subject to a given total length, then how efficient can we make the network in the sense of providing routes between vertices whose route-length is not much larger than straight-line distance, and what precise statistic is most useful for measuring this notion of ``efficient"?

(2) There is a general class of proximity graphs, defined for arbitrary vertices, which are always connected.  Applying to random points gives a class of random networks which are connected and have bounded mean degree.   This class has scarcely been studied, but seems an appealing modeling alternative to the classical  geometric random graphs for which one cannot have both connectivity and bounded mean degree.
top of page
Commutation Relations and Markov Chains
Jason Fulman (USC)

It is shown that the combinatorics of commutation relations can be used to give sharp convergence rate results for certain Markov chains. The main example described in this talk will be a random walk on partitions whose stationary distribution is the Ewens distribution from population genetics.
top of page

 Mathematics Statistics Berkeley Probability Group Maps & Directions Previous Seminars