Archive of UW Probability Seminar

Probability Seminar Archive

Time: Monday, March 9, 2009 at 2:30 pm.

Location: MGH 085

Speaker: Soumik Pal (University of Washington)

Title: A combinatorial analysis of interacting diffusions

Abstract: We consider a particular class of multidimensional homogeneous diffusions all of which have an identity diffusion matrix and a drift function that is piecewise constant over cones. Abstract stochastic calculus immediately gives us general results about existence and uniqueness in law and invariant probability distributions when they exist. These invariant distributions are probability measures on the n-dimensional space and can be extremely resistant to a more detailed understanding. One can see that the structure of the invariant probability measure is intertwined with the geometry of the cones where the drift function is a constant. In this article we pursue results that make this connection precise. We show that several natural interacting Brownian particle models can thus be analyzed by studying the combinatorial fan generated by the drift function, particularly when these are simplicial. As broad classes of examples we analyze interactions defined by Coxeter groups actions and weighted graphs by this method.

Time: Monday, March 2, 2009 at 2:30 pm.

Location: MGH 085

Speaker: Ryan Card (University of Washington)

Title: Brownian Motion with Boundary Diffusion

Abstract: Diffusion in a domain can be described by a second order differential operator plus a boundary condition. Dirichlet and Neumann boundary conditions are familiar to us, which corresponds to killed and reflected processes respectively. General class of boundary conditions was found by Wentzell in 1959. I will describe how processes with Wentzell's boundary condition behave, and present an invariance principle for a class of Markov processes that converge to diffusion with Wentzell's boundary conditions. Time permitting, I will talk about some curious properties of these processes and how they can be used to prove Boundary Harnack Principle for harmonic functions that satisfy boundary diffusive condition.

Time: Monday, February 23, 2009 at 2:30 pm.

Location: MGH 085

Speaker: Amites Sarkar (Western Washington University)

Title: Partitioning Random Geometric Covers

Abstract: I'll present some new results on partitioning both random and non-random geometric covers. For the random results, let P be a Poisson process of intensity one in the infinite plane R^2, and surround each point x of P by the open disc of radius r centered at x. Now let S_n be a fixed disc of area n>>r^2, and let C_r(n) be the set of discs which intersect S_n. Write E_r^k for the event that C_r(n) is a k-cover of S_n, and F_r^k for the event that C_r(n) may be partitioned into k disjoint single covers of S_n. I'll sketch a proof of the inequality Prob(E^k_r | F^k_r) \leq c_k/log n, which is best possible up to a constant. The non-random result is a classification theorem for covers of R^2 with half-planes that cannot be partitioned into two single covers. It was motivated by a desire to understand the obstructions to k-partitionability in the original random context. This is all joint work with Paul Balister, Bela Bollobas and Mark Walters.

Time: Tuesday, February 10, 2009 at 1:30 pm.

Location: Gates Commons, 6th floor of CSE building

Speaker: Yuval Peres (Microsoft Research)

Title: The Unreasonable Effectiveness of Martingales

Abstract: I will illustrate the effectiveness of Martingales and stopping times with four examples, involving waiting times for patterns in coin tossing, random graphs, mixing of random walks, and metric space embedding. A common theme is the way stopping time arguments often circumvent the wasteful "union bound" (bounding of the probability of a union by the sum of the individual probabilities). Note Special Time and Place

Time: Monday, February 9, 2009 at 2:30 pm.

Location: MGH 085

Speaker: Matt Kahle (Stanford University)

Title: Random geometric simplicial complexes

Abstract: Choose n random points, independent and identically distributed in R^d, connect them if they are within distance r, and build a simplicial complex on this graph. (We will define and discuss two of the most standard geometric constructions: the Rips and Cech complexes.) What is the topology of this complex likely to be like, and how does it change as r grows from 0 to infinity? We are able to find a fairly detailed picture. In some cases we are able to prove Central Limit Theorems for the dimensions of certain homology groups. One interesting feature is that the underlying topological properties which we study are intrinsically non-monotone.

Time: Monday, February 2, 2009 at 2:30 pm.

Location: MGH 085

Speaker: Panki Kim (Seoul National University)

Title: Potential theory of 1-dimensional subordinate Brownian motions with continuous components

Abstract: Suppose that S is a subordinator (1-dimensional increasing Levy process) with a nonzero drift and W is an independent 1-dimensional Brownian motion. X_t = W(S_t) is called the subordinate Brownian motion. In this talk, we discuss sharp bounds for the Green function of the process X killed upon exiting a bounded open interval and a boundary Harnack principle. This is a joint work with Renming Song and Zoran Vondracek.

Time: Monday, January 26, 2009 at 2:30 pm.

Location: MGH 085

Speaker: Ioana Dumitriu (University of Washington)

Title: In search of the elusive beta: from full to tridiagonal random matrices

Abstract: For some classical random matrix ensembles, eigenvalue distributions are computable exactly. When changing the field of entries (from real to complex and to quaternion), these distributions change little, and in very simple ways, according to a $\beta$ parameter. This creates "interpolating" ensembles of eigenvalues with no full matrix model. If one lets go of the fullness requirement, tridiagonal models can be constructed which correspond to every $\beta$. These models are great in many ways, and insufficient in others. I will speak about constructing them, as well as about the pros and cons.

Time: Monday, June 2, 2008 at 2:30 pm.

Location: LOW 101

Speaker: Peter Hoff (University of Washington)

Title: Probability models over the Stiefel manifold, with applications to multivariate analysis

Abstract: Normal vectors and orthonormal matrices play an important role in spatial statistics, multivariate analysis and matrix decomposition methods. Probability models for these objects can play a role in describing heterogeneity and sampling variability across multivariate and matrix-valued data. In this talk I describe some simple exponential family models for the set of orthonormal matrices, and illustrate their use in a few data analysis examples. In particular, I will show how to model the heterogeneity in a population of covariance matrices via a model for the heterogeneity in their eigenvector matrices. Estimating the parameters in this model allows us to share information across the different covariance matrices, resulting for improved estimation for each specific covariance matrix.

Time: Monday, May 19, 2008 at 2:30 pm.

Location: LOW 101

Speaker: Oded Schramm (Microsoft Research)

Title: Random metrics, the mathematics of quantum gravity `

Abstract: In quantum gravity, the geometry of space itself is random. One procedure to produce a random metric on a sphere is to fix some large $n$ and to take the uniform distribution over all isometry classes of topological spheres that can be obtained by pasting together side to side $n$ equilateral triangles of side-length $1$. These objects can be shown to be metrically $4$ dimensional in the large (though topologically they are $2$ dimensional). One mathematical reason for the interest in these random geometries stems from the KPZ formula, which is a prediction from physics linking random processes on random geometries to conformally invariant random processes in the plane. Amazingly, some questions turn out to be simpler in the random geometry setting, and the KPZ formula has been used to make very specific conjectures about random processes in the plane. Very recently, there has been a great deal of progress in the mathematical understanding of the random geometries. I plan to survey the subject.

Time: Monday, May 12, 2008 at 2:30 pm.

Location: LOW 101

Speaker: Peter Moerters (University of Bath)

Title: INTERSECTIONS OF RANDOM WALKS IN SUPERCRITICAL DIMENSIONS

Abstract: In high dimensions two independent simple random walks have only a finite number of intersections. In the talk I present recent progress on the problem of describing the exact upper tail behavior of random variables associated with the number of intersections.

Joint work with Xia Chen.

Time: Monday, May 5, 2008 at 2:30 pm.

Location: LOW 101

Speaker: Eyal Lubetzky (Microsoft Research)

Title: Glauber dynamics for the mean-field Ising model and cutoff in birth-and-death chains

Abstract: We study the Curie-Weiss model, i.e., Glauber dynamics for the Ising model on the complete graph on $n$ vertices. It is well-known that the mixing-time in the high temperature regime has order $n\log n$ [Aizenman and Holley (1984)], whereas the mixing-time in low temperatures is exponential in $n$ [Griffiths et al. (1966)]. Recently, Levin, Luczak and Peres proved that for any fixed high temperature there is cutoff, whereas the mixing-time at the critical temperature $\beta=1$ has order $n^{3/2}$. It is natural to ask how the mixing-time transitions from order $n\log n$ (with cutoff) to order $n^{3/2}$ and finally to $\exp\left(\Theta(n)\right)$.

In this work, we extend the results of Levin et al. into a complete characterization of the mixing-time of the dynamics as a continuous function of the temperature, as it approaches its critical point both from below and from above. The above transition between the three regimes appears in the form of a scaling window of order $1/\sqrt{n}$ around the critical temperature. Cutoff occurs only in the subcritical regime, where we determine the cutoff point and window. Furthermore, for each temperature we also determine the order of the spectral gap of the Glauber dynamics.

A key element in the proofs is the analysis of the magnetization chain (the sum of all spins), as it turns out that the mixing of this birth-and-death chain essentially dictates the mixing of entire dynamics. If time permits, I will also present a related general result on the criterion for total-variation cutoff in birth-and-death chains (analogous to the result on convergence in separation by [Diaconis and Saloff-Coste (2006)]).

This is joint work with J. Ding and Y. Peres.

Time: Monday, April 28, 2008 at 2:30 pm.

Location: LOW 101

Speaker: Yuval Peres (Microsoft Research)

Title: Compression exponents of amenable groups and escape rates of random walks

Abstract: Let G be a countable amenable group, equipped with a finite set of generators and a corresponding word metric $d(x,y)$. The Hilbert-space compression exponent $a_*$ of G is the supremum of all $a>0$ such that there exists a Lipschitz map $f$ from G to Hilbert space and a constant $c>0$ so that for all $x,y$ in G, the norm $||f(x)-f(y)||$ is at least $cd(x,y)^a.$ Let $b$ denote the escape rate exponent for simple random walk (X_t) on the Cayley graph of G, that is, suppose that $Ed(X_0,X_t)$ grows like $t^b$. We prove that $2ba_*$ is at most $1$, and equality holds in many cases. In particular for the lamplighter group on Z with integer-valued lamps we have a_*=2/3 and b=3/4. Our proof uses K. Ball's notion of Markov type. We also obtain extensions to $L^p$ compression via p-stable random walks. No prior knowledge of group theory will be assumed; all the relevant notions will be explained in the talk. (Joint work with Assaf Naor and Tim Austin).

Time: Monday, April 21, 2008 at 2:30 pm.

Location: LOW 101

Speaker: Chris Hoffman (University of Washington)

Title: DLA on a cylinder

Abstract: One probabilistic model that has proven notoriously difficult to analyze is diffusion-limited aggregation (DLA) in the plane. This model for the growth of a collection of particles in the plane develops as follows. Initially there is one particle at the origin. Inductively we add particles to the boundary. We start a new particle at infinity and have it perform simple random walk until it is adjacent to the collection. The that particle is added to the collection where it hit the boundary. In this talk we consider a closely related model on a cylinder which we hope will shed light on DLA in the plane. This is joint work with Itai Benjamini.

Time: Monday, April 14, 2008 at 2:30 pm.

Location: LOW 101

Speaker: Ping He (Shanghai University of Finance and Economics and UW)

Title: Excursions of reflecting Brownian motions on Lipschitz domains

Abstract: Since B. Maisonneuve (1975) established an exit system to characterize excursions in general framework, there has been a considerable body of work dealing with what is called the general theory of excursions of a Markov process. However such exit system does not possess analytical description in general. It needs for some application to give an explicit form. P. Hsu (1986) studied the excursions of reflecting Brownian motion on a bounded domain in Euclidean space with smooth boundary. The approach of his work was completely independent of the general theory. Applying to the smoothness of the boundary, the normal derivative for the boundary points which is the density of the Poisson measure with respect to the surface measure is well-defined.

This work is concerned with whether Hsu's elegant results on excursions from the smooth boundary can be extended to the Lipschitz boundary which is no longer smooth. For reflecting Brownian motion on the closure of a bounded Lipschitz domain at first, we take a Martin kernel as Poisson kernel with respect to a positive Radon measure on the boundary. We then investigate the excursions from the boundary straddling on a fixed time $t$ and give a beautiful application on the Feller measure. Based on the previous results, we give an explicit Levy system of the boundary process for the reflecting Brownian motion on Lipschitz domain.

Time: 2:30 p.m., Monday, April 7, 2008

Location: LOW 101

Speaker: Zhen-Qing Chen (University of Washington)

Title: A strong limit theorem for Dawson-Watanabe Superprocesses

Abstract: In this talk I will discuss some recent progress on scaling limit theorems for Dawson-Watanabe superprocesses. We will show that weak limit theorem can be established for a large class of superprocesses when the underlying spatial processes are symmetric Hunt processes. When the underling process is a symmetric diffusion with $C^1_b$-coefficients or a symmetric L\'evy process on $\R^d$ whose L\'evy exponent $\Psi (\eta )$ is bounded from below by $c |\eta|^\alpha$ for some $c>0$ and $\alpha \in (0, 2)$ when $|\eta|$ is large, a stronger almost sure limit theorem can be established for the superprocess. Our approach uses the principal eigenvalue and the ground state for some associated Schrodinger operator. The limit theorems are established under the assumption that an associated Schrodinger operator has a spectral gap.

Joint work with Yanxia Ren and Hao Wang.

Time: 2:30 p.m., Monday, March 10, 2008

Location: MEB 245

Speaker: Alexander E. Holroyd (University of British Columbia and Microsoft Research)

Title: SLOW CONVERGENCE IN BOOTSTRAP PERCOLATION

Abstract: Bootstrap percolation is a simple cellular automaton model for nucleation and growth. Sites in an $L$ by $L$ square are initially infected with probability $p$, and a healthy site becomes infected if it has at least 2 infected neighbors. Asymptotically for large $L$, the model is known to undergo a phase transition as the parameter $p \log L$ crosses the threshold $\pi^2/18$. However, simulation predictions for this threshold are typically smaller by more than a factor of two! I'll talk about some attempts to understand this discrepancy. The main result is that the asymptotic value differs from the actual threshold by at least $const/\sqrt{\log L}$. [In contrast, the critical window has width only $const/\log L$.] For a variant model we can prove that to get within 1\% of the asymptotic value, $L$ must be at least $10^{3000}$!

Joint work with Janko Gravner.

Time: 2:30 p.m., Monday, Monday, March 3, 2008

Location: MEB 245

Speaker: Ariel Yadin (Weizmann Institute of Science)

Title: THE MAXIMAL PROBABILITY THAT $k$-WISE INDEPENDENT BITS ARE ALL 1

Abstract: A distribution over n bits is called k-wise independent if any subset of k bits are independent. Such distributions arise in many areas in probability and computer science. For example, there is a fundamental connection with linear error-correcting codes.

We address the following question: how high can the probability that all the bits are 1 be, for such a distribution? For a wide range of the parameters n,k and p we find an explicit lower bound for this probability which matches an upper bound given by Benjamini et al., up to multiplicative factors of lower order. The question we investigate can be seen as a relaxation of a major open problem in error-correcting codes theory, namely, how large can a linear error correcting code with given parameters be? We use a new approach that does not use coding theory, and thus we are able to improve on previous lower bounds. The main tool we use is a bound controlling the change in the expectation of a polynomial after small perturbation of its zeros.

Joint work with Ron Peled and Amir Yehudayoff.

Time: 2:30 p.m., Friday, February 29, 2008

Location: LOW 102

Speaker: Tadeusz Kuilczycki (Wroclaw University of Technology)

Title: HOT SPOTS THEOREM FOR 2-DIMENSIONAL SLOSHING PROBLEM

Abstract: The sloshing problem is a linear eigenvalue problem that describes the small oscillations of the free surface of a fluid subject to gravity. The sloshing problem is a classical problem in fluid mechanics.

The 2 dimensional sloshing problem has the following physical interpretation. An infinitely long canal with uniform cross section is filled with inviscid heavy fluid (water). The fluid makes, under gravity, oscillations about the equilibrium position. We consider only 2 dimensional motion in planes normal to the generators of the canal bottom.

Let rectangular Cartesian coordinates $(x,y)$ be taken in the plane of the motion with the origin and the $x$-axis in the mean free surface, whereas the $y$-axis is directed upwards. The uniform cross section of the canal is a bounded simple connected domain $W \subset {\bf R} \times (-\infty,0)$, $\partial W = F \cup B$, where $F$, lying on the $x$-axis, is the free surface of the fluid and $B = \partial W \setminus F$, lying in the half plane $y < 0$, is the bottom of the canal. The velocity potential equals $\cos(\sigma_n t + c) u_n(x,y)$. $u_n$ satisfies the following boundary eigenvalue problem $$ \Delta u_n(x,y) = 0, \quad (x,y) \in W, $$ $$ {\partial u_n \over \partial y}(x,0) = - \nu_n u_n(x,0), \quad ( x,0) \in F, $$ $$ {\partial u_n \over \partial n}(x,y) = 0, \quad (x,y) \in B, $$ We have $\sigma_n^2 = \lambda_n g$, where $g$ is the gravitational acceleration. ${\partial\over \partial n}$ is the differentiation normal to $B$.

It is known that there exists a sequence of eigenvalues $$ 0 = \nu_0 < \nu_1 \le \nu_2 \ldots \to \infty. $$

The main result is the following theorem. {\bf Theorem} Let $W \subset F \times (-\infty,0)$ be a bounded convex domain and let $B$ be a smooth curve. Then the first nontrivial eigenfunction $u_1$ is (up to a sign) increasing on $F$, that is $x \to u_1(x,0)$ is increasing for $x \in F$. In particular $u_1$ achieves its minimum and maximum on the boundary of $F$.

The sloshing problem has also the probabilistic interpretation for the semigroup of the Cauchy-like process which is the trace on $F$ of the reflected Brownian motion in $W$.

Time: 2:30 p.m., Monday, February 25, 2008

Location: MEB 245

Speaker: Itai Benjamini (Weizmann Institute of Science)

Title: GEOMETRIC REINFORCEMENT

Abstract: We will discuss a few random processes with reinforcement, e.g., DLA.

Time: 2:30 p.m., Monday, February 11, 2008

Location: MEB 245

Speaker: Benjamin Weiss (Hebrew University of Jerusalem)

Title: FINITE OBSERVABILITY AND CLASSIFICATION OF ERGODIC PROCESSES

Abstract: A function $F$ defined on some class of stochastic processes $\cal C$ is finitely observable if there is some universal estimation scheme which when applied to longer and longer finite sequences of typical observations drawn from any process $X$ in the class will converge to $F(X)$. In ergodic theory one tries to classify processes up to isomorphism or finitary isomorphism. It turns out that for the class of all ergodic processes there is basically only finitely observable function which is also an isomorphism invariant. All of theses notions will be explained together with some further results and open questions.

Time: 2:30 p.m., Wednesday, February 6, 2008

Location: LOW 102

Speaker: Kaneharu Tsuchida (Tohoku University, Japan)

Title: LARGE DEVIATIONS FOR DISCONTINUOUS ADDITIVE FUNCTIONALS OF SYMMETRIC STABLE PROCESSES

Abstract: As a useful approach in proving the large deviation principle, the Gartner-Ellis theorem is well known. In this talk, we show the large deviation principle for discontinuous additive functionals of symmetric stable processes by applying this theorem. Joint work with Masayoshi Takeda.

Time: 2:30 p.m., Monday, February 4, 2008

Location: MEB 245

Speaker: Maxim Krikun (Institut Elie Cartan, Nancy)

Title: STATIONARY MEASURES FOR BALLISTIC ANNIHILATION WITH BRANCHING

Abstract: 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 Serguei Popov (USP) and Philippe Chassaing and Lucas Gerin (IECN).

Please note the unusual time and location

Time: 2:30 p.m., Wednesday, January 23, 2008

Location: LOW 102

Speaker: Panki Kim (Seoul National University)

Title: BOUNDARY HARNACK PRINCIPLE FOR SUBORDINATE BROWNIAN MOTIONS

Abstract: The boundary Harnack principle for nonnegative classical harmonic functions is a very deep result in potential theory and has very important applications in probability and potential theory. In this talk, we discuss the boundary Harnack inequality for a large class of pure jump symmetric Levy processes, including mixtures of symmetric stable processes.

Time: 2:30 p.m., Monday, January 14, 2008

Location: MEB 245

Speaker: Gabor Pete (Microsoft Research)

Title: THE SCALING LIMITS OF DYNAMICAL AND NEAR-CRITICAL PERCOLATION AND THE MINIMAL SPANNING TREE

Abstract: Let each site of the triangular lattice, with small mesh $\eta$, have an independent Poisson clock with rate $\eta^{3/4+o(1)}$ switching between open and closed. Then, at any given moment, the configuration is just critical percolation; in particular, the probability of a left-right open crossing in the unit square is close to 1/2. Furthermore, because of the scaling, the expected number of switches in unit time between having a crossing or not is of unit order.

In joint work with Christophe Garban and Oded Schramm, we prove that the limit (as $\eta \to 0$) of the above process exists as a Markov process, and it is conformally covariant: if we change the domain with a conformal map $\phi(z)$, then time has to be scaled locally by $|\phi'(z)|^{3/4}$. The same proof yields a similar result for near-critical percolation, and it also shows that the scaling limit of (a version of) the Minimal Spanning Tree exists, it is invariant under rotations and scaling, but not under general conformal maps.

Time: 2:30 p.m., Monday, January 7, 2008

Location: MEB 245

Speaker: Asaf Nachmias (University of California, Berkeley)

Title: CRITICAL PERCOLATION ON FINITE GRAPH

Abstract: Bond percolation on a graph $G$ with parameter $p$ in [0,1] is the random subgraph $G_p$ of $G$ obtained by independently deleting each edge with probability $1-p$ and retaining it with probability $p$. For many graphs, the size of the largest component of $G_p$ exhibits a phase transition: it changes sharply from logarithmic to linear as p increases. When $G$ is the complete graph, this model is known as the Erdos-Renyi random graph: at the phase transition, i.e. $p=1/n$, the largest component satisfies a power-law of order $2/3$.

For which $d$-regular graphs does percolation with $p=1/(d-1)$ exhibit similar ``mean-field'' behavior? We show that this occurs for graphs where the probability of a non-backtracking random walk to return to its initial location behaves as it does on the complete graph. In particular, the celebrated Lubotzky-Phillips-Sarnak expander graphs and Cartesian products of 2 or 3 complete graphs exhibit mean-field behavior at $p=1/(d-1)$; surprisingly, a product of 4 complete graphs does not.

Please note the unusual time and location

Time: Wednesday, November 28, 2007 at 2:30 pm

Location: MOR 234

Speaker: Toshihiro Uemura (University of Connecticut and University of Hyogo, Japan)

Title: A remark on nonlocal operator

Abstract: Given a Levy kernel, then we reveal a connection between the nonlocal operator having it as Levy measure and the (symmetric) Dirichlet form having it as jumping measure. The relation is obtained through the carre du champ operator associated with the operator. We will show that this relation is quite different from the case of elliptic differential operators (diffusion processes)

Time: Monday November 19, 2007 at 2:30 pm

Location: THO 334

Speaker: Eyal Lubetzky (Microsoft Research)

Title: Poisson approximation for non-backtracking random walks

Abstract: Random walks have been applied extensively in theoretical Computer Science, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the vertices of a graph. In some of these applications, it seems to be better to apply non-backtracking random walks, rather than simple ones.

In the first part of this talk, I will analyze the mixing rate of non-backtracking random walks on a regular graph. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may indeed be up to twice as fast as the mixing rate of the simple random walk.

The second part of the talk will focus on an application illustrating the fact that non-backtracking walks exhibit stronger pseudo-random properties. We provide a Poisson approximation to the visits to vertices in non-backtracking random walks on expanders, and show that the multi-set of visited vertices is analogous to the result of throwing $n$ balls to $n$ bins uniformly, in contrast to the simple random walk on $G$, which almost surely visits some vertex $\Omega(\log n)$ times.

Based on joint works with Noga Alon, Itai Benjamini and Sasha Sodin.

Time: Friday November 2, 2007 at 2:30 pm

Location: EEB 026

Speaker: Ioana Dumitriu (University of Washington)

Title: Playing golf with many balls: Markov chains and Gittins indices

Abstract: I will analyze and solve a game in which a player chooses which of several Markov chains to advance, with the object of minimizing the expected cost (time) for one of the chains to reach a target state. The solution entails computing a variant of a Gittins index on the states of the individual chains, the minimization of which produces an optimal strategy.

This is older work with Prasad Tetali and Peter Winkler.

Time: Monday October 29, 2007 at 2:30 pm

Location: THO 334

Speaker: Krzysztof Burdzy (University of Washington)

Title: Branching Brownian motion, excursion theory, and potential analysis

Abstract: I will present an open question about a Fleming-Viot-type branching model for Brownian motion. Some progress has been made using excursion theory. Another technical aspect of the partial solution is based on a new type of the boundary Harnack principle.

Joint work with Mariusz Bieniek.

Time: Monday October 15, 2007 at 2:30 pm

Location: LOW 219

Speaker: Zhen-Qing Chen (University of Washington)

Title: Time Reversal and Elliptic Boundary Value Problems

Abstract: In this talk, we will present a new and probabilistic way to solve Dirichlet boundary value problem on bounded Euclidean domains for a class of second order elliptic operators that contain the $div (cu)$ term (dual to the first order term $c\nabla u$). The novelty of our approach is the use of time-reversal of a Girsanov transform. We will derive probabilistic representation for solutions to the elliptic boundary problem. Such a representation also enable us to obtain some new results in PDE.

Joint work with Tusheng Zhang.

Time: Wednesday, May 30, 2007 at 2:30 pm.

Location: MOR 225

Speaker: Mariusz Bieniek (Maria Curie-Sklodowska University, Lublin, Poland)

Title: OPTIMAL BOUNDS FOR EXPECTATIONS OF FUNCTIONS OF GENERALIZED ORDER STATISTICS

Abstract: There is a vast literature devoted to determination of optimal bounds on expectations of order statistics and record values. Most of them are derived by the application of the projection method introduced by Gajek and Rychlik. In this talk we consider extension of these results to generalized order statistics (GOS).

First, we briefly recall the concept of GOS which serves as a unified approach to distribution properties of order statistics, record values and other models of ordered random variables. Then we give a short description of the projection method which relies on finding the projection of functions onto convex cones in the Hilbert space $L^2$ of square integrable functions on $[0,1]$. To find a projection of a function onto the convex cone of nondecreasing functions in $L^2$ we need two tools: the greatest convex minorants method of Moriguti and variation diminishing property of densities of uniform GOS proved by the author. As examples of application of these results we derive optimal bounds on expectations of single GOS and of their differences.

Time: Monday, May 21, 2007 at 2:30 pm.

Location: MEB 238

Speaker: Oded Schramm (Microsoft Research)

Title: THE FOURIER SPECTRUM OF PERCOLATION

Abstract: The indicator function for the existence of a percolation crossing in an n by n square is naturally a function on the discrete cube $\{-1,1\}^E$, where $E$ is the set of edges. As such, it admits a ``Fourier'' expansion. In joint work with Christophe Garban and Gabor Pete, we obtain rather sharp estimates for the ``weight'' of the Fourier coefficients at different frequencies. This allows us to answer some basic questions about dynamical percolation (the dimension of the set of exceptional times and the existence of times with an infinite interface) and about the effect of noise on the crossing event (e.g., if you re-sample the vertical edges, is the event of a crossing in the new configuration substantially correlated with having a crossing in the original configuration?).

The above description is rather vague, and one primary objective of the talk is to clarify and expand it.

Time: Friday, May 18, 2007 at 2:30 pm.

Location: PDL C401

Speaker: Yves Lacroix (Institute of Engineering Sciences of Toulon and The Var)

Title: THE LAW OF SERIES IN ERGODIC THEORY

Abstract: The simplest model of a dynamical system in the probabilistic setting is the one obtained by a stationary ergodic process. For such process, Kolmogorov introduced the notion of entropy, which connects to the one discussed by Shannon when he was working at the Bell laboratories. The entropy is just a positive real number, and it is non zero if and only if the system is non invertible, that is the present does not only depend on the past. In other words, the system is non deterministic.

Any system can be pictured in the probabilistic sense by simple procedures, which are connected to quantification of recurrence to some events. Asymptotically, many processes admit a behavior which is much like the one of the independent process. So I have tried to understand possible asymptotics, in order to go beyond the independent or independent-like cases. After obtaining some characterizations, with T. Downarowicz, we have succeeded in proving that non determinism has an unexpected consequence : asymptotics can only reveal clustering of rare events, which means that positivity of this simple object, entropy, implies that no matter what one tries, rare events will have a natural tendency to cluster... like in the popular but yet unmodelled ``law of series''.

We have even proved that a typical partition of a positive entropy system produces a process with extreme clustering on an upper density one sequence of cylinder lengths. I will try to make this story comprehensive during my talk.

Time: Monday, May 14, 2007 at 2:30 pm.

Location: MEB 238

Speaker: Sourav Chatterjee (University of California, Berkeley)

Title: SPIN GLASSES AND STEIN'S METHOD

Abstract: The high temperature phase of the Sherrington-Kirkpatrick model of spin glasses is solved by the famous Thouless-Anderson-Palmer (TAP) system of equations. The only rigorous proof of the TAP equations, based on the cavity method, is due to Michel Talagrand. The basic premise of the cavity argument is that in the high temperature regime, certain objects known as `local fields' are approximately gaussian in the presence of a `cavity'. In this talk, I will show how to use the classical Stein's method from probability theory to discover that under the usual Gibbs measure with no cavity, the local fields are asymptotically distributed as asymmetric mixtures of pairs of gaussian random variables. An alternative (and seemingly more transparent) proof of the TAP equations automatically drops out of this new result, bypassing the cavity method.

Statistics Seminar
Time: Monday, May 7, 2007 at 3:30 pm.

Location: Savery 249

Speaker: Peter Imkeller (Humboldt University at Berlin, Germany)

Title: Scheduling, Percolation, and the Worm Order

Abstract: A spectral analysis of the time series representing average temperatures during the last ice age featuring the Dansgaard-Oeschger events reveals an alpha-stable noise component with an alpha ~ 1.78. Based on this observation, papers in the physics literature attempted a qualitative interpretation by studying diffusion equations that describe simple dynamical systems perturbed by small Levy noise. We study exit and transition problems for solutions of stochastic differential equations and stochastic reaction-diffusion equations derived from this proto-type. Due to the heavy-tail nature of the alpha-stable component of the noise, the results differ strongly from the well known case of purely Gaussian perturbations. For SPDE, transitions are governed by the modes with the largest jumps.

Time: Monday, May 7, 2007 at 2:30 pm.

Location: MEB 238

Speaker: Ron Peled (Microsoft Research)

Title: $k$-WISE INDEPENDENT EVENTS, BOOLEAN FUNCTIONS AND PERCOLATION

Abstract: What is the effect of $k$-wise independence? We consider some specific Boolean functions whose behavior we understand well when their input is independent random bits (possibly biased). We check whether assuming only that each {\it subset} of size $k$ of their input bits is completely independent can change the distribution of the output of the function significantly. Our main example is percolation: a (bond) percolation on $Z^d$ (the integer lattice in $d$-dimensions), is the process of erasing each edge of $Z^d$ with probability $1-p$ independently of all other edges. It is well known that for each $d\geq 2$, there is a critical $0p_c$, an infinite connected component remains with probability 1 and if $p
We also consider some other examples of boolean functions such as tribes and recursive majority. Our methods use techniques from error correcting codes and the classical moment problem which turn out to have many connections to this subject. We also explore connections to the harmonic analysis of boolean functions. As one application we obtain a new lower bound for the minimal size of an orthogonal array over $GF(q)$.

Time: Monday, April 30, 2007 at 2:30 pm.

Location: MEB 238

Speaker: Yuval Peres (Microsoft Research and University of California, Berkeley)

Title: STRONG SPHERICAL ASYMPTOTICS FOR ROTOR-ROUTER AGGREGATION AND THE DIVISIBLE SANDPILE

Abstract: The rotor-router model is a deterministic analogue of random walk. It can be used to define a deterministic growth model analogous to internal DLA. We prove that the asymptotic shape of this model is a Euclidean ball, in a strong sense. In 2D, for the shape consisting of $n=\pi r^2$ sites, we show that the inradius of the set of occupied sites is at least $r-O(\log r)$, while the outradius is at most $r+O(r^a)$ for any $a > 1/2$. For a related model, the divisible sandpile, we give a constant upper bound for the difference of the outradius and the inradius. For the classical Abelian sandpile model in two dimensions, with $n=\pi r^2$ particles, we improve on the best available bounds due to Le Borgne and Rossin. Similar bounds apply in higher dimensions. (Talk based on joint work with Lionel Levine).

Time: Friday, April 27, 2007 at 2:30 pm.

Location: PDL C401

Speaker: Tomoyuki Shirai (Kyushu University)

Title: ON THE VARIANCE OF RANDOMIZED VALUES OF RIEMANN'S ZETA FUNCTION ON THE CRITICAL LINE

Abstract: Recently, M. Lifshits and M. Weber studied randomized values of Riemann's zeta-function on the critical line $s=1/2 + it$ by sampling along the Cauchy random walk and show that its variance grows slowly, which is related to the famous Lindel\"of hypothesis. In this talk, I would like to explain the background and related topics of this problem, and discuss a slight extension of this result.

PIMS 10th Anniversary Distinguished Lecturer
Time: Thursday, April 19, 2007 at 4 pm.

Location: Smith 304

Speaker: Peter Winkler (Dartmouth College)

Title: Scheduling, Percolation, and the Worm Order

Abstract: When can you schedule a multi-step process without having to take backward steps? Critical are an old concept called "submodularity", a new structure called the "worm order", and a variation of what physicists call "percolation".

With these tools we will attempt to update the computer system at UW, find a lost child in the Cascades, and minimize water usage in Seattle, all without backward steps.

Joint work in part with Graham Brightwell (LSE) and in part with Lizz Moseman (Dartmouth). (This talk is designed to be accessible to undergraduates interested in mathematics.)

Time: Monday, April i16, 2007 at 2:30 pm.

Location: MEB 238

Speaker: Chris Hoffman (University of Washington)

Title: RANDOM WALK AMONG BOUNDED RANDOM CONDUCTANCES

Abstract: Over the last decade there has been much interest in the study of simple random walk on percolation clusters on $Z^d$. Condition on the origin being in the infinite cluster. Then the probability that the simple random walk started at the origin returns to the origin after $2n$ steps is $O(n^{-d/2})$, just as it is for simple random walk on $Z^d$.

In this talk we consider the nearest-neighbor random walk on $Z^d$, $d\ge2$, driven by a field of bounded random conductances $\omega_{xy}\in (0,1]$. We study the decay of the probability that the random walk started at the origin returns to the origin after $2n$ steps. We prove that this probability is bounded by a random constant times $n^{-d/2}$ in $d=2,3$, while it is $o(n^{-2})$ in $d\ge5$ and $O(n^{-2}\log n)$ in $d=4$. We prove that the $o(n^{-2})$ bound in $d\ge5$ is the best possible. This is joint work with Noam Berger, Marek Biskup and Gady Kozma

Time: Monday, April 9, 2007 at 2:30 pm.

Location: MEB 238

Speaker: Russell Lyons (Indiana University and Microsoft)

Title: SPANNING TREES, RANDOM GRAPHS, AND RANDOM WALKS

Abstract: In the usual Erd\"os-R\'enyi model of random graphs, each pair of $n$ vertices is connected by an edge independently with probability $c/n$ for some constant $c$. When $c > 1$, it has a unique ``giant'' component. How quickly does the number of spanning trees of the giant component grow with $n$ compared to the growth in the number of its vertices? Is it monotonic in $c$? We answer this in joint work with Ron Peled and Oded Schramm.

Time: Monday, April 2, 2007 at 2:30 pm.

Location: MEB 238

Speaker: Jason Swanson (University of Wisconsin, Madison)

Title: STOCHASTIC INTEGRATION WITH RESPECT TO A QUARTIC VARIATION PROCESS

Abstract: Brownian motion (BM) is used to model a wide array of stochastic phenomena in a variety of scientific disciplines. Typically, this is done by using BM as a driving term in a stochastic differential equation (SDE). We are able to define and study these SDEs using Ito's stochastic calculus. Similarly, stochastic partial differential equations (SPDEs) are often used to model stochastic phenomena. In this talk, we consider a very simple example of a stochastic heat equation. The solution to this SPDE, when regarded as a process indexed by time, has a nontrivial 4-variation. It follows that we cannot use the traditional methods of the Ito calculus to define an SDE driven by this process.

In this talk, I will describe work in progress toward constructing a stochastic integral with respect to this process and a corresponding Ito-like change-of-variables formula. The integral being constructed is a limit of discrete Riemann sums. It turns out that the process we are considering has a very close relationship to a certain "flavor" of fractional Brownian motion (FBM). The quest for a calculus for FBM has led researchers in several different directions and there is a large body of literature on the topic. I will discuss some of the similarities and differences between our approach and an analogous approach for FBM using the so-called regularization procedure of Russo and Vallois.

Part of this project is joint work with Chris Burdzy.

Time: Friday March 2, 2007 at 2:30 pm.

Location: PDL C-36

Speaker: Noam Berger (UCLA, visiting Microsoft Research)

Title: Intersection of paths and high dimensional random walk in random environment.

Abstract: We show an easy estimate for the probability of intersection of two random walks in random environment (RWRE) in dimension five or more. We then get two corollaries:
a law of large numbers for distributionally symmetric RWRE in dimension geq 5, and
a quenched CLT for certain ballistics RWRE-s in dimension geq 4.

Partly based on joint work with Ofer Zeitouni. No knowledge of RWRE will be assumed.

Time: Friday 2/23/2007 at 2:30 pm.

Location: PDL C-401

Speaker: Yan-Xia Ren (Beijing University, visiting University of Oregon)

Title: Limit theorems for super-diffusions corresponding to the operator $Lu+\beta u-ku^2$

Abstract: Consider a superdiffusion $X$ corresponding to the operator $Lu+\beta u-ku^2$, where $\beta(x)$ is bounded from above and is in the Kato class, and $k(x)\ge 0$ is bounded on compact subset of ${\bf R}^d$. Let $-\Lambda $ be the $L^{\infty}$-spectral radius of the semigroup $Q_t$ corresponding to the Schrodinger operator $Lu+\beta u$. We prove that if $\Lambda >0$, the exponential growth rate of the total mass of $X$ is $\Lambda $; if $\Lambda <0$, the exponential decay rate of the total mass of $X$ is $\Lambda <0$. We also describe the limiting behavior of $\exp(-\Lambda t)X_t({\bf R}^d)$, where $X_t({\bf R}^d)$ is the total mass of $X$ at time $t$. In particular, in the case $\Lambda =0$, under some restrict conditions on $\beta$, we give a sufficient and necessary condition for the superdiffusion $X$ exhibiting weak extinction. It turns out that the branching rate function $k$ affects the weak extinction, this should be compared with the known result that $k$ does not affects the weak local extinction of $X$.

Time: Monday 2/12/2007 at 2:30 pm.

Location: SAV 151

Speaker: Alexander Holroyd (University of British Columbia)

Title: Random Sorting Networks

Abstract: See http://www.math.ubc.ca/~holroyd/sort for pictures. Joint work with Omer Angel, Dan Romik and Balint Virag.

Sorting a list of items is perhaps the most celebrated problem in computer science. If one must do this by swapping neighboring pairs, the worst initial condition is when the n items are in reverse order, in which case n choose 2 swaps are needed. A sorting network is any sequence of n choose 2 swaps which achieves this.

We investigate the behavior of a uniformly random n-item sorting network as n->infinity. We prove a law of large numbers for the space-time process of swaps. Exact simulations and heuristic arguments have led us to astonishing conjectures. For example, the half-time permutation matrix appears to be circularly symmetric, while the trajectories of individual items appear to converge to a famous family of smooth curves. We prove the more modest results that, asymptotically, the support of the matrix lies within a certain octagon, while the trajectories are Holder-1/2. A key tool is a connection with Young tableaux.

Time: Monday 2/5/2007 at 2:30 pm.

Location: SAV 151

Speaker: Abraham Flaxman (Microsoft Research)

Title: Expansion and lack thereof in randomly perturbed graphs

Abstract: This talk will investigate the expansion properties of randomly perturbed graphs. These graphs are formed by, for example, adding a random 1-out or very sparse Erdos-Renyi graph to an arbitrary connected graph.

When any connected n-vertex base graph is perturbed by adding a random 1-out then, with high probability, the resulting graph has expansion properties. When the perturbation is by a sparse Erdos-Renyi graph, the expansion of the perturbed graph depends on the structure of the base graph.

The same techniques also apply to bound the expansion in the small worlds graphs described by Watts and Strogatz in [Nature 292 (1998), 440--442] and by Kleinberg in [Proc. of 32nd ACM Symposium on Theory of Computing (2000), 163--170]. Analysis of Kleinberg's model reveals a phase transition: the graph stops being an expander exactly at the point where a decentralized algorithm is effective in constructing a short path.

The proofs of expansion rely on a way of summing over subsets of vertices which allows an argument based on the First Moment Method to succeed.

Time: Monday 1/29/2007 at 2:30 pm.

Location: SAV 151

Speaker: Gabor Pete (Microsoft Research)

Title: Corner percolation on \Z^2, and other linear entropy models

Abstract: Corner percolation is a strongly dependent percolation model introduced by Bálint Tóth, exhibiting some unusual critical behaviour. We prove that all connected components are finite cycles almost surely, but the expected diameter of the cycle containing the origin is infinite. Moreover, we derive the following critical exponents: the tail probability \Pr(diameter of the cycle of the origin > n) \approx n^{-\gamma}, and the expectation \E(length of a cycle conditioned on having diameter n) \approx n^\delta, with \gamma=(5-\sqrt{17})/4=0.219... and \delta=(\sqrt{17}+1)/4=1.28... The value of \delta comes from the solution of a singular sixth order ODE, while the relation \gamma+\delta=3/2 corresponds to the fact that the scaling limit of the natural height function in the model is the Additive Brownian Motion, whose level sets have Hausdorff dimension 3/2.

I will discuss many exciting open problems, e.g. on the conformal invariance of some similar linear entropy models.

Time: Monday 1/22/2007 at 2:30 pm.

Location: SAV 151

Speaker: Ioana Dumitriu (University of Washington)

Title: Central Limit Theorems for \beta-Hermite and \beta-Laguerre ensembles (C^1 functions)

Abstract: The \beta-Hermite and -Laguerre ensembles are generalizations of the "classical" Gaussian and central Wishart ones, and have applications in statistical physics (from the theory of log-Coulomb gases to traffic patterns, parked car spacings, etc.)

The (scaled) empirical distributions of these ensembles converge to the famous Wigner semicircle law (in the case of Hermite), respectively, Mar\v{c}enko-Pastur law (for Laguerre). I will show that the fluctuations from these laws describe Gaussian processes on C^1 functions. Then I will comment on a "natural barrier" found at C^{1/2}, and express consternation and a certain degree of frustration with it.

This is joint work with Ofer Zeitouni.

Time: Monday 1/8/2007 at 2:30 pm.

Location: SAV 151

Speaker: Krzysztof Burdzy (University of Washington)

Title: Pathwise uniqueness for reflected Brownian motion in $C^{1+\gamma}$ domains

Abstract: A domain in $R^d$ is called $C^{1+\gamma}$ if its boundary can be locally represented as the graph of a function whose gradient is Holder with exponent $\gamma$. For $d\geq 3$, pathwise uniqueness holds for the SDE representing reflected Brownian motion in a $C^{1+\gamma}$ domain provided $\gamma > 1/2$. For every $\gamma < 1/2$, there exists $d$ and a $C^{1+\gamma}$ domain $D$ in $R^d$ such that pathwise uniqueness fails in $D$.
Work in progress. Joint with R. Bass.

Time: Monday, December 4, 2006 at 2:30 pm.

Location: MGH 288

Speaker: Yuval Peres (Microsoft Research, UC Berkeley and UW)

Title: GRAVITATIONAL ALLOCATION TO POISSON POINTS

Abstract: We consider the Poisson fair allocation problem: Given a realization of a Poisson point process, allocate to each point of the process a unit of volume, in a deterministic translation-invariant way, so that the diameter of the region allocated to each point is stochastically as small as possible. One approach to this problem, studied in previous work with C. Hoffman and A. Holroyd, uses the stable marriage algorithm of Gale and Shapley. Here we show that in dimensions 3 and higher, gravity without inertia yields a very satisfying solution. The argument starts with the classical calculation by Chandrasekar of the total force acting on a point, which has a symmetric stable law. The fairness of the allocation is a consequence of the divergence theorem; The diameters of the allocated regions are analyzed using methods from percolation theory. (Joint work with S. Chatterjee, R. Peled, D. Romik).

Time: Monday, November 27, 2006 at 2:30 pm.

Location: MGH 288

Speaker: Gunnar Gunnarsson (University of Washington)

Title: SPDE MODELS FOR HIGHWAY TRAFFIC

Abstract: We introduce a new stochastic partial differential equation model for multi-lane highway traffic. We prove well-posedness of the model, derive a numerical method for calculating its solutions and estimate some of its parameters.

Time: Monday, November 20, 2006 at 2:30 pm.

Location: MGH 288

Speaker: Yuan-Chung Sheu (National Chiao Tung University, Hsinchu, Taiwan)

Title: AN ODE APPROACH FOR THE EXPECTED DISCOUNTED PENALTY AT RUIN IN JUMP DIFFUSION MODEL

Abstract: For a general penalty function, the expected discounted penalty at ruin was considered by, for example, Gerber and Shiu(1998) and Gerber and Landry (1998) in insurance literature. On the other hand, many pricing functionals in mathematical finance can be formulated in terms of expected discounted penalties. Under the assumption that the asset value follows a jump diffusion, we show the expected discounted penalty satisfies an ODE and obtain a general form for the expected discounted penalty. In particular, if only downward phase-type jumps are allowed, we get an explicit formula in terms of the penalty function and jump distribution. On the other hand, if downward jump distribution is a mixture of exponential distributions (and upward jumps are determined by a general L\'{e}vy measure), we obtain closed form solutions for the expected discounted penalty. As an application, we work out an example in Leland's structural model with jumps. For earlier and related results, see Gerber and Landry(1998), Hilberink and Rogers(2002), Mordecki(2002), Kou and Wang(2004), Asmussen et al.(2004) and others.

Time: Monday, November 13, 2006 at 2:30 pm.

Location: MGH 288

Speaker: Tomoyuki Shirai (Kyushu University)

Title: ON THE NUMBER OF EIGENVALUES OF GINIBRE MATRIX ENSEMBLE

Abstract: Ginibre matrix ensemble is the random matrix whose entries are i.i.d. complex Gaussian random variables. Its random eigenvalues form a determinantal point process (associated with exponential kernel) on the whole complex plane. We discuss the large deviation principle for the number of its eigenvalues inside a ball and also its conditional expectation given that there are no eigenvalues in a big ball.

Time: Monday, November 6, 2006 at 2:30 pm.

Location: MGH 288

Speaker: Tusheng Zhang (University of Manchester)

Title: GLOBAL FLOWS FOR STOCHASTIC DIFFERENTIAL EQUATIONS WITHOUT GLOBAL LIPSCHITZ CONDITIONS

Abstract: We consider stochastic differential equations driven by Brownian motion. The coefficients are supposed to satisfy only local Lipschitz conditions. The Lipschitz constants of the drift, valid on balls of radius $R$, are supposed to grow not faster than $\log R$, those of diffusion coefficient not faster than $\sqrt{\log R}$. Under these conditions, we establish the existence of a global flow for the stochastic differential equation.

Time: Monday, October 30, 2006 at 2:30 pm.

Location: MGH 288

Speaker: Kavita Ramanan (Carnegie Mellon University)

Title: EXISTENCE AND UNIQUENESS OF SOLUTIONS TO A CLASS OF STOCHASTIC DIFFERENTIAL INCLUSIONS

Abstract: We establish sufficient conditions for pathwise uniqueness and existence of strong solutions to a class of stochastic differential equations in $R^n$ with discontinuous drift (interpreted as stochastic differential inclusions), that are possibly reflected in a polyhedral domain with piecewise constant reflection field. In contrast to previous results, we do not impose any uniform ellipticity assumptions, and our results also yield new conditions for uniqueness of solutions to ordinary differential inclusions with drifts that have multiple intersecting surfaces of discontinuity. We will also briefly discuss the application of our results to the study of large deviations of a class of jump Markov processes that arise naturally in applications. This is joint work with Rami Atar and Amarjit Budhiraja.

MATHEMATICS COLLOQUIUM (PIMS 10th Anniversary Distinguished Lecturer)
Time: Tuesday, October 24, 2006 at 4 pm.

Location: Smith 304

Speaker: Gregory Lawler (University of Chicago)

Title: CONFORMAL INVARIANCE AND TWO-DIMENSIONAL STATISTICAL PHYSICS

Abstract: A number of lattice models in two-dimensional statistical physics are conjectured to exhibit conformal invariance in the scaling limit at criticality. In this talk, I will try to explain what the previous sentence means, focusing on three elementary examples: simple random walk, self-avoiding walk, loop-erased random walk. I will describe the limit objects, Schramm-Loewner Evolution (SLE), the Brownian loop soup, and the normalized partition functions, and show how conformal invariance can be used to calculate quantities ("critical exponents") for the model. I will also describe why (in some sense) there is only a one-parameter family of conformally invariant limits. In conformal field theory, this family is parametrized by central charge.

This talk is for a general mathematical audience. No knowledge of statistical physics will be assumed.

Time: Friday, October 20, 2006 at 2:30 pm.

Location: THO 235

Speaker: Eulalia Nualart (Universit\'e Paris 13)

Title: HITTING PROBABILITIES FOR SYSTEMS OF NONLINEAR STOCHASTIC HEAT EQUATIONS

Abstract: In this talk we develop potential theory for a system of non-linear stochastic heat equations in spatial dimension one and driven by a space-time white noise. In particular, we prove upper and lower bounds on hitting probabilities of the process which is solution of this system of equations, in terms of respectively Hausdorff measure and Newtonian capacity. These estimates make it possible to discuss polarity for points and to compute the Hausdorff dimension of the range and the level sets of this process. In order to prove the hitting probabilities estimates, we need to establish Gaussian type bounds for the bivariate density of the process in order to quantify its degeneracy. For this, we use techniques of Malliavin calculus.

Time: Monday, October 9, 2006 at 2:30 pm.

Location: MGH 288

Speaker: Lionel Levine (University of California, Berkeley)

Title: THE SCALING LIMIT OF DIACONIS-FULTON ADDITION

Abstract: Given two sets $A$ and $B$ in the lattice, the Diaconis-Fulton sum is a random set obtained by putting one particle in every point of the symmetric difference, and two particles in every point of the intersection, of $A$ and $B$. Each "extra" particle performs random walk until it reaches an unoccupied site, where it settles. The law of the resulting random occupied set $A+B$ does not depend on the order of the walks. We find the (deterministic) scaling limit of the sums $A+B$ when $A$ and $B$ consist of the lattice points in some overlapping domains in Euclidean space. The limit is described by focusing on the "odometer" of the process, which solves a free boundary obstacle problem for the Laplacian. Joint work with Yuval Peres.

Time: Monday, October 2, 2006 at 2:30 pm.

Location: MGH 288 (Mary Gates Hall)

Speaker: Peter Moerters (University of Bath)

Title: LOCALIZATION OF MASS IN THE PARABOLIC ANDERSON MODEL

Abstract: The parabolic Anderson model is the Cauchy problem for the heat equation with random potential. After a gentle introduction of some basic features of the model, I will discuss a recent result showing that, for a particular class of potentials, at large times the mass becomes localised in a single point in space, which moves in time.

The talk is based on joint work with W Koenig and N Sidorova.

Time: Thursday 8/3/2006 at 2:30 pm.

Location: LOW 111

Speaker: Panki Kim (University of Illinois at Urbana-Champaign)

Title: Intrinsic Ultracontractivity for Non-symmetric Levy Processes

Abstract: Recently the concept of intrinsic ultracontractivity to non-symmetric semigroups has been introduced by Kim and Song. In this talk, we study the intrinsic ultracontractivity for non-symmetric discontinuous Levy processes.

Time: Wednesday May 24, 2006 at 2:30 pm.

Location: THO 211

Speaker: Takashi Kumagai (Kyoto University)

Title: On the existence of cut points for Brownian motion on fractals

Abstract: Let $B(t)$ be a Brownian motion on some metric space $K$. A time $t\in [0,1]$ is called a cut time for $B[0,1]$ if $B[0,t)\cap B(t,1]$ is empty, and $B(t)$ is called a cut point if $t$ is a cut time. Let $L$ be the set of cut points for $B[0,1]$. When $K=R^d (d=2,3)$, Burdzy showed that non-trivial cut points exist, and later Lawler obtained the Hausdorff dimension of $L$ in terms of the intersection exponent. On the other hand, it is known that when $d=1$, there is no non-trivial cut points. In this talk, we will discuss the existence of cut points for Brownian motion on fractals. We will prove that there is a family of fractals whose Brownian motions are point recurrent, but have non-trivial cut points. This is a on-going joint work with Peter Morters (Bath).

Time: Wednesday May 17, 2006 at 2:30 pm.

Location: THO 211

Speaker: Kavita Ramanan (Carnegie-Mellon University)

Title: A Concentration Inequality for Weakly Contracting Markov Chains

Abstract: Given a Markov chain X on a countable state space S and a Lipschitz function f on S^n, we derive a concentration inequality for the function f around its mean. We use the method of bounded martingale differences to derive this concentration inequality. To set this result in context, we will also provide a brief survey of concentration of measure results in the i.i.d. setting. This is joint work with Leonid Kontorovich.

Time: Monday May 8, 2006 at 2:30 pm.

Location: MEB 238

Speaker: Kittipat Wong (Chulalongkorn University, Thailand)

Title: Large time behavior of Dirichlet heat kernels

Abstract: We will discuss the asymptotic behavior of the transition density $p^D(t,x,y)$ of killed Brownian motions in $D$ where $D \subset R^d, d \ge 2$ is an unbounded domain above the graph of a bounded Lipschitz function.

Time: Wednesday May 3, 2006 at 2:30 pm.

Location: THO 211

Speaker: Rami Atar (Technion and University of Washington)

Title: Large Deviations and Related PDE

Abstract: It is well known that dynamic control problems for Markov processes, in which large deviations are heavily penalized, lead in an appropriate scaling limit to differential games and, in turn, to Hamilton-Jacobi type PDE. I will review results in the field and present new queueing networks applications.

Time: Monday, April 24, 2006 at 2:30 pm.

Location: MEB 238

Speaker: Hanna Jankowski (University of Washington)

Title: Central Limit Theorem for a Zero Range Tagged Particle

Abstract: To further understand the scaling limit of an interacting particle system, one would like to establish a limit law for the evolution of a tagged particle and the associated central limit theorem. Tagging the particles makes this a difficult problem, and one method to deal with it is to consider first an intermediate step: limit laws and fluctuations for the colour empirical densities. I will discuss the nonequilibrium fluctuations of the coloured version of the symmetric zero range particle system, and what this implies about the CLT for the tagged particle.

Time: Monday, April 17, 2006 at 2:30 pm.

Location: MEB 238

Speaker: Krzysztof Burdzy (University of Washington)

Title: Shy couplings

Abstract: Given Markovian transition probabilities, can one construct two processes $X$ and $X'$ with these transition probabilities, such that the distance between $X$ and $X'$ stays always above some $\eps>0$? A pair of proceses with the above property is called a shy coupling. I will give examples of Markovian transition probabilities that admit shy couplings and examples when shy couplings do not exist.

Joint work with I. Benjamini and Z. Chen.

Time: Monday, April 3, 2006 at 2:30 pm.

Location: MEB 238

Speaker: David Wilson (Microsoft Research)

Title: Boundary Connections in Trees and Dimers

Abstract: We study groves on planar graphs, which are forests in which every tree contains one or more of a special set of vertices on the outer face. Each grove partitions the set of special vertices. When a random grove is selected, we show how to compute the various partition probabilities as functions of the electrical properties of the graph when viewed as a resistor network. We prove that for any partition sigma, Pr[grove has type sigma] / Pr[grove is a tree] is a dyadic-coefficient polynomial in the pairwise resistances between the special vertices, and Pr[grove has type sigma] / Pr[grove has maximal number of trees] is an integer-coefficient polynomial in the entries of the Dirichlet-to-Neumann matrix. We give analogous polynomial formulas for the double-dimer model. These partition probabilities are relevant to multichordal SLE_8, SLE_2, and SLE_4. (Joint work with Richard Kenyon.)

Note the unusual day of the week.
Time: Friday, March 10, 2006 at 2:30 pm.

Location: PDL C-401

Speaker: Jin Ma (Purdue University)

Title: STOCHASTIC CONTROL PROBLEMS DRIVEN BY NORMAL MARTINGALES

Abstract: We study a class of stochastic control problems in which the control of the jump size is essential. Such a model is a generalized version for various applied problems, such as the optimal reinsurance selections for general insurance models. The main novel nature of such a control problem is that by changing the jump size of the system, one essentially changes the type of the driving martingale. Such a feature does not seem to have been investigated in any existing stochastic control literature. Assuming that the driving normal martingale is one-dimensional, we prove the Bellman Principle for such a control problem, and derive the corresponding Hamilton-Jacobi-Bellman (HJB) equation, which in this case is a mixed second-order partial differential/difference equation. We prove that the value function is the {\it unique} viscosity solution of such an HJB equation and discuss the uniqueness of such PDDE.

This is a join work with Rainer Buckdahn and Catherine Rainer.

Time: Monday, February 27, 2006 at 2:30 pm.

Location: PDL C-401

Speaker: Kathryn Temple (Central Washington University)

Title: PARTICLE REPRESENTATIONS OF EXIT MEASURES

Abstract: The connection between diffusions and certain linear elliptic boundary value problems is well-known. More recently, a connection between superdiffusions and a class of nonlinear elliptic PDEs has been developed and exploited. Making this connection requires a construction of the superdiffusion which allows additional structure, such as Dynkin's Branching Exit Markov Systems, the Dawson-Perkins Historical Process, or LeGall's Brownian Snake. We use an adaptation of a particle construction of Kurtz and Rodrigues to construct an exit measure and therefore solutions of the PDEs associated with a certain class of superdiffusions. As time permits, we will give an application of this construction to a simple homogenization problem.

Note the unusual day of the week and unusual room.
Time: Wednesday, February 22, 2006 at 2:30 pm.

Location: SIG 226

Speaker: Yuichi Shiozawa (Tohoku University)

Title: EXTINCTION OF BRANCHING SYMMETRIC $\alpha$-STABLE PROCESSES

Abstract: We give a criterion for extinction of branching symmetric $\alpha$-stable processes in terms of the principal eigenvalue for Schr\"odinger type operators. Here the branching rate and the branching mechanism are spatially dependent. In particular, the branching rate is allowed to be singular with respect to the Lebesgue measure. We also study the exponential growth of the number of particles for these processes.

Time: Monday, February 13, 2006 at 2:30 pm.

Location: PDL C-401

Speaker: Oded Schramm (Microsoft)

Title: THE DISCRETE GAUSSIAN FREE FIELD AND ITS LEVEL LINES

Abstract: An instance of the Gaussian free field is a random function defined in a domain in $R^d$. It is a generalization of Brownian motion to the case where time is multi-dimensional, and it is useful for modelling many different kinds of random surfaces. In two dimension, it exhibits conformal invariance.

During the talk we will define the Gaussian free field and also the discrete Gaussian free field and describe joint work with Scott Sheffield identifying the scaling limit of the level lines of the discrete Gaussian free field in two dimensions (as the lattice mesh tends to zero). These limits are random curves having Hausdorff dimension 3/2 a.s.

Time: Monday, February 6, 2006 at 2:30 pm.

Location: PDL C-401

Speaker: Nicole Immorlica (Microsoft)

Title: MARRIAGE, HONESTY AND STABILITY

Abstract: Many centralized two-sided markets, such as the medical residency market or online dating services, form a matching between participants by running a stable marriage algorithm. It is a well-known fact that no matching mechanism based on a stable marriage algorithm can guarantee truthfulness as a dominant strategy for participants. However, as we will show in this talk, in a certain probabilistic setting, truthfulness is (in some sense) the best strategy for the participants.

We show this by proving that in our setting the set of stable marriages is small. We derive several corollaries of this result. First, we show that, with high probability, in a stable marriage mechanism, the truthful strategy is the best response for a given player when the other players are truthful. Then we analyze equilibria of the deferred acceptance stable marriage game. We show that the game with complete information has an equilibrium in which a $(1-o(1))$ fraction of the strategies are truthful in expectation. In the more realistic setting of a game of incomplete information, we will show that the set of truthful strategies form a $(1+o(1))$-approximate Bayesian-Nash equilibrium. Our results have implications in many practical settings and were inspired by experimental observations in a paper of Roth and Peranson (1999) concerning the National Residency Matching Program.

This is joint work with Mohammad Mahdian.

Time: Monday, January 30, 2006 at 2:30 pm.

Location: PDL C-401

Speaker: Omer Angel (University of British Columbia)

Title: ONE DIMENSIONAL DLA

Abstract: We consider a variation on DLA (diffusion limited aggregation) in 1 dimension generated by a random walk with large jumps. The growth rate of the diameter of the $n$ particle aggregate depends on the tail of the step distribution, and exhibits three phase transitions when the steps have 1, 2 or 3 finite moments.

Time: Monday, January 23,, 2006 at 2:30 pm.

Location: PDL C-401

Speaker: Rami Atar (Technion and University of Washington)

Title: ANALYSIS OF MIRROR COUPLINGS IN SMOOTH DOMAINS

Abstract: We analyze a coupling of two reflecting Brownian motions in (the closure of) a smooth domain, with the property that whenever both processes are in the domain, the motions form mirror images of each other. Under appropriate geometric conditions, we show that the motion of the mirror is limited in the sense that there are parts of the domain that it will never intersect (for suitable initial conditions). This will be described along with consequences regarding monotonicity of the Neumann-Laplacian eigenfunctions a la the `hot spots' problem. Joint work with Chris Burdzy.

Note the unusual day of the week and time. This will be also a colloquium talk.
Time: 4:00 p.m., Thursday, January 19, 2006

Location: Smith 105

Speaker: Jin Feng (University of Massachusetts at Amherst)

Title: LARGE DEVIATIONS FOR MARKOV PROCESSES AND RELATED VARIATIONAL PROBLEMS

Abstract: Large deviation estimates are probabilistic limit theorems which are used to describe atypical behavior of random systems. Markov processes are a rich class of probabilistic models. Their generators constitute a link between probability, classical analysis and *linear* partial differential equations. I will describe a method for deriving large deviation estimates for a sequence of Markov processes through convergence of some *nonlinear* transforms of their generators. This is a previously unknown connection between probability and certain topics in nonlinear analysis such as Hamilton-Jacobi equations, viscosity solutions, and optimal control theory. I will offer examples where probability can help with analytical problems and vice versa. I will use examples ranging from small random perturbations of ODEs to the more physically motivated ones such as macroscopic description of multi-scale microscopic interacting particle systems.

Time: Monday, January 9, 2006 at 2:30 pm.

Location: PDL C-401

Speaker: Jason Swanson (University of Wisconsin, Madison)

Title: ASYMPTOTIC BEHAVIOR OF A GENERALIZED TCP CONGESTION AVOIDANCE ALGORITHM

Abstract: The Transmission Control Protocol (TCP) is designed to guarantee reliable and sequential delivery of packets of data from a sender to a receiver on a computer network. To avoid network congestion, TCP uses various variations on an additive-increase-multiplicative-decrease algorithm, which means that the rate of data flow is increased linearly until a packet loss is detected, at which point the rate is reduced by some constant multiplicative factor. I will present a generalization of this TCP Congestion Avoidance algorithm, which is due to Teunis J. Ott of the New Jersey Institute of Technology. This model includes, as a special case, the so-called "Scalable TCP," which is a multiplicative-increase-multiplicative-decrease scheme.

The general model is given by a Markov chain $\{W_n\}$, which represents the size of the congestion window (that is, the rate of data flow) at the time of the delivery of the $n$-th packet. Implicit in this model is a parameter $p$, which denotes the probability of a packet loss. Under suitable scaling of time and space, this process converges weakly as $p\to 0$ to the solution of a stochastic differential equation. The form of the equation depends on the values of certain parameters in the model. For some values, it is the Ornstein-Uhlenbeck equation; for the others, it is an equation driven by a Poisson process. I will sketch the proof of this result and discuss further unanswered question. This is joint work with Teun Ott.

Time: Wednesday, December 7, 2005 at 2:30 pm.

Location: PDL C-401

Speaker: Jeremy Quastel (University of Toronto)

Title: Asymptotic speed of traveling fronts in the KPP equation with noise

Abstract: The most basic reaction-diffusion equation, KPP, was introduced by Fisher to model the spread of an advantageous gene. In this context it is very natural to consider what happens to traveling fronts when the equation is perturbed by an appropriate noise. Brunet and Derrida observed, by simulations and physical arguments, that the noise leads to an unexpectedly large slowdown of the traveling fronts. We describe the problem and proofs of some of their conjectures. This is joint work with Carl Mueller (Rochester) and Leonid Mytnik (Technion).

Time: Monday, November 21, 2005 at 2:30 pm.

Location: PDL C-401

Speaker: Jim Burke (University of Washington)

Title: Estimation of Constrained Mixture Densities

Abstract: We consider the constrained mixture density estimation problem over a parametric family of densities. It is shown how this problem can be posed as a convex optimization problem on the space of regular Borel measures. By combining this formulation with Caratheodory's Theorem for convex sets in finite dimensions it is possible to pose an equivalent finite dimensional optimization problem. The problem is then amenable to a variety of numerical optimization routines. One such approach based on interior point technology is discussed and numerical results are presented.

This research is the result of a joint work between the speaker and Yeongcheon Baek.

Time: Monday, November 14, 2005 at 2:30 pm.

Location: PDL C-401

Speaker: Peter D. Hoff (University of Washington)

Title: Random Graph Models for Relational Network Data

Abstract: Relational data measure the presence or absence of links among a set of objects. This data structure is very general and has many applications in the social and biological sciences. In this talk we consider two families of probability models which are used to make inference from network data. The first family includes exponentially parameterized models, which are motivated by simplicity and maximum entropy considerations. Models in the second family are motivated by a certain type of row-and-column exchangeability for arrays, and typically have a very large parameter space. Finally, we compare the appropriateness of these two model classes for a variety of inferential goals.

Time: Monday, November 7, 2005 at 2:30 pm.

Location: PDL C-401

Speaker: Chris Hoffman (University of Washington)

Title: Dynamic random walk in two dimesnions

Abstract: Benjamini, Haggstrom, Peres and Steif introduced the concept of a dynamical random walk. This is a continuous family of random walks in d dimensions, S_n(t), indexed by a real number t. They asked which properties of simple random walk that hold for almost every t hold for all t. They proved that if d=3,4 then there exist (random) times t such that the random walk returns to the origin infinitely often, but if d>4 then the random walk returns to the origin only finitely often for all t. We prove that if d=2 then there exists (random) times t such that the random walk returns to the origin only finitely often. This result is related to a theorem of Adelman, Burdzy and Pemantle in which they prove that although Browninan motion in three dimensions spends an infinite amount of time in a given infinite cylinder of radius one almost surely, but there exist (random) cylinders where Brownian motion spends only a finite amount of time almost surely.

Time: Monday, Oct 31, 2005 at 2:30 pm.

Location: PDL C-401

Speaker: Vlada Limic (University of British Columbia)

Title: The spatial Lambda-coalescent

Abstract: This talk is based on a joint paper with Anja Sturm, and it will describe the extension of the Lambda-coalescent of Pitman (1999) to the spatial setting. The partition elements of the spatial Lambda-coalescent migrate in a (finite) geographical space and may only coalesce if located at the same site of the space. We characterize the Lambda-coalescents that come down from infinity, in an analogous way to Schweinsberg (2000). Surprisingly, all spatial coalescents that come down from infinity, also come down from infinity in a uniform way. This enables us to study space-time asymptotics of spatial Lambda-coalescents on large tori in transient dimensions. Our results generalize and strengthen those of Greven et al. (2005), who studied the spatial Kingman coalescent in this context.

Time: Monday, Oct 24, 2005 at 2:30 pm.

Location: PDL C-401

Speaker: David Levin (University of Oregon)

Title: A Coupling, and a Conjecture of Darling and Erdos

Abstract: I will describe a new coupling of the running maximum of an Ornstein-Uhlenbeck process and the running maximum of an explicit iid sequence. This coupling can be used to resolve a conjecture of Darling and Erdos (1956). Joint work with D. Khoshnevisan.

Time: Monday, Oct 17, 2005 at 2:30 pm.

Location: PDL C-401

Speaker: Ken Alexander (University of Southern California)

Title: The pinning transition for a polymer in the presence of a random potential

Abstract: We consider a polymer, with monomer locations modeled by the trajectory of a Markov chain, in the presence of a potential that interacts with the polymer when it visits a particular site 0. We assume the probability of an excursion of length $n$ from 0, in the absence of the potential, decays like $n^{-c}$ for some $c>1$. Disorder is introduced by, having the interaction vary from one monomer to another, as a constant $u$ plus i.i.d. mean-0 randomness. There is a critical value of $u$ above which the polymer is pinned, placing a positive fraction, called the contact fraction, of its monomers at 0 with high probability. We obtain bounds for the contact fraction near the critical point and examine the effect of the disorder on the specific heat exponent, which describes the approach to 0 of the contact fraction at the critical point. Our results are consistent with predictions in the physics literature that the effect of disorder is quite different in the cases $c<3/2$ and $c>3/2$.

Time: Wednesday, Oct 12, 2005 at 2:30 pm.

Location: SMI 311

Speaker: Bartek Dyda (Technical Univ of Wroclaw)

Title: On fractional order Hardy inequalities

Abstract: We will state the fractional order Hardy inequality for e.g. bounded Lipschitz domains, and prove it in the simplest case when the domain is R^d \setminus \{0\}. This inequality will give us transcience of the censored stable process (with the stability index > 1) in bounded Lipschitz domains. This result was obtained earlier (by another methods) in the paper of Bogdan, Burdzy and Chen. We will also mention some further results concerning fractional order Hardy inequalities.

Time: Wednesday, August 24, 2005 at 3:30 pm.

Location: Padelford C-36

Speaker: Wojbor A. Woyczy\'nski (Case Western Reserve University)

Title: STOCHASTIC PARTICLE METHODS FOR NONLINEAR EVOLUTION EQUATIONS INVOLVING L'EVY GENERATORS

Abstract: I will consider a class of nonlinear integro-differential equations driven by L\'evy infinitesimal generators and involving nonlocal nonlinearities represented by singular integral operators. We associate a nonlinear diffusion in the McKean sense with the original singular equation and are able to prove the convergence of cut-off interacting particle systems to the law of this nonlinear singular diffusion.

Time: Monday, May 23, 2005 at 2:30 pm.

Location: SMI 102

Speaker: Elton Hsu (Northwestern University)

Title: MASS TRANSPORTATION PROBLEM AND COUPLING OF DIFFUSION PROCESSES

Abstract: We will discuss the problem of existence and uniqueness of maximal Markov coupling of diffusion processes, in particular, Brownian motion on Riemannian manifolds. We will show how this problem is related to the mass transportation problem with a cost function determined by the heat kernel of the diffusion process. The problem is completely solved only in the Euclidean case.
A part of this talk is the joint work with Theo Sturm (Bonn).

Time: Monday, May 16, 2005 at 2:30 pm.

Location: SMI 102

Speaker: Matthew Stephens (University of Washington)

Title: EXCHANGEABLE AND NON-EXCHANGEABLE DISTRIBUTIONS ARISING FROM APPLICATIONS IN POPULATION GENETICS

Abstract: Population genetics is the study of genetic variation in random samples of individuals from a population. I will give an informal introduction to some of the mathematical theory underlying recent progress in this discipline. Much of the theory is derived under simplistic and unrealistic assumptions. I will describe work to relax these assumptions to capture important aspects of real data. Although this work has had important impact in several practical applications, it raises several interesting and unresolved theoretical problems.

Time: Monday, May 9, 2005 at 2:30 pm.

Location: SMI 102

Speaker: Karoly Simon (Technical University of Budapest)

Title: THE SIZE OF THE ALGEBRAIC DIFFERENCE OF TWO RANDOM CANTOR SETS

Abstract: In this talk we consider some families of random Cantor sets on the line and investigate the question whether the condition that the sum of Hausdorff dimension is larger than one, implies the existence of interior points in the difference set. We prove that this is the case for the so called Mandelbrot percolation. On the other hand the same is not always true if we apply a construction of random Cantor sets similar to the Mandelbrot percolation but with different probabilities.

Time: Monday, May 2, 2005 at 4:30 pm.

Location: THO 119

Speaker: Michael Taksar (University of Missouri)

Title: SINGULAR STOCHASTIC CONTROL AND RELATED PDE WITH GRADIENT CONSTRAINTS IN PORTFOLIO OPTIMIZATION MODELS IN MATHEMATICAL FINANCE

Abstract: In the modern mathematical finance the stock prices are modeled by stochastic differential equations, whose solutions produce logarithmic Brownian motions. This is the backbone of what is nowadays became the classical Black-Scholes option pricing theory and Merton's investment/consumption theory. We consider a dynamical portfolio optimization model in the spirit of the latter. The portfolio consists of several risky assets (Stocks) and one risk-free asset (Bond). The rate of return on Bond is constant while the rate of return of Stocks is governed by SDE of the logarithmic Brownian motion type. Funds can be transferred from one asset to another, however such transaction involves penalty (brokerage fees) proportional to the size of the transaction. The objective is to find the policy which maximizes the expected rate of growth of funds.
The main mathematical tool in the solution of this problem is singular stochastic control theory. In this theory the control functionals are represented by processes of bounded variation, and the optimal control consists of functionals which reflect the process from an a priori unknown boundary. They are continuous but singular (not absolutely continuous) with respect to time. The analytical part of the solution to singular control is related to a free boundary problem for an elliptic PDE with gradient constraints, similar to the ones encountered in elastic-plastic torsion problems. The existence of the classical $C^2$ solution cannot be proved in general but one can show an existence of viscosity solution to this equation.
The optimal policy is to keep the vector of fractions of funds invested in different assets in an optimal (a priori unknown) boundary. We show how to find these boundaries explicitly in the case of one risky and one risk-free asset when the problem becomes one dimensional. In this case the free boundary problem can be reduced to a Stephan problem for an ODE.

Time: Thursday, April 21, 2005 at 2:30 pm.

Location: SAV 131

Speaker: Wlodzimierz Bryc (University of Cincinnati)

Title: QUADRATIC HARNESSES, Q-COMMUTATIONS, AND ORTHOGONAL MARTINGALE POLYNOMIALS

Abstract: Harnesses were introduced by Hammersley (1967) as random fields that model `long-range misorientation'. They were studied for example by Williams (1973), and recently by Mansuy-Yor (2005) who considered harnesses indexed by t>0 and defined them by a reverse-martingale condition for the normalized increments of the process.
Quadratic harnesses are related to Hammersley-Manuy-Yor harnesses by mimicking the relation between the martingale and the quadratic martingale conditions. Examples of quadratic harnesses are the Poisson, Gamma, Pascal (negative binomial), and the Wiener process. Lesser known examples are Markov processes associated with certain free Levy processes, and with non-commutative q-Gaussian processes introduced in the physics literature by Frisch-Bourret (1970) and constructed rigorously by Bozejko-Kummerer-Speicher {1997}.
It is plausible that generic quadratic harnesses are in fact five-parameter Markov processes. The five parameters arise as the coefficients in the q-commutation equation for the Jacobi matrix of the associated orthogonal martingale polynomials, which exist under minimal assumptions. At present, constructions of the corresponding Markov transition probabilities are known only for special choices of these parameters, and explicit answers are even less frequent. One such explicit example of a two-parameter quadratic harness is obtained by appropriately re-scaling a certain non-homogeneous pure-birth Markov process that `explodes' at a deterministic moment of time, and then `returns back from infinity' as a pure-death process.
This talk is based on joint research with W. Matysiak and J. Wesolowski.

Time: Monday, April 18, 2005 at 2:30 pm.

Location: SMI 102

Speaker: Fausto Di Biase (Universit\`a `G.d'Annunzio', Pescara, Italy)

Title: THE STOLZ APPROACH IS SHARP, ISN'T IT?

Abstract: We consider the following question: how sharp is the Stolz approach region for the almost everywhere convergence of bounded harmonic functions in the unit disc in the plane or in NTA domains in $R^n$? The issue was first settled in the rotation invariant case in the unit disc by Littlewood in 1927 and later examined, under less stringent conditions, by Aikawa in 1991. We will present results that are, in a certain sense, sharp.
A joint work in collaboration with A. Stokolos, O. Svensson and T. Weiss.

Time: Monday, April 11, 2005 at 2:30 pm.

Location: SMI 102

Speaker: Joan Lind (University of Washington)

Title: THE GEOMETRY OF THE LOEWNER EVOLUTION

Abstract: The Loewner differential equation provides a connection between continuous, real-valued functions (called driving terms) and families of domains in the complex plane (said to be generated by the driving term.) The recent interest in this 80-year-old equation is due to Oded Schramm's introduction of the SLE processes, which have allowed mathematicians to prove many results predicted by physicists as well as Mandelbrot's conjecture that the outer boundary of a planar Brownian path has Hausdorff dimension 4/3. I will discuss how the geometry of the generated domains is related to the driving function, both in the deterministic setting and for SLE.

Time: Monday, April 4, 2005 at 2:30 pm.

Location: SMI 102

Speaker: Julien Dub\'edat (Courant Institute, New York University)

Title: COMMUTATION OF SLE's

Abstract: Schramm-Loewner Evolutions (SLEs) have proved to be a powerful tool to describe the scaling limit of a conformally invariant simple curve. In several instances (percolation, uniform spanning tree ...), one can define in a discrete setting several simple curves. We will discuss questions pertaining to the joint law of these curves in the scaling limit.

Time: Tuesday, March 22, 2005 at 2:30 pm.

Location: PDL C-36

Speaker: Jason Swanson (University of Wisconsin)

Title: WEAK CONVERGENCE OF THE MEDIAN OF INDEPENDENT BROWNIAN MOTIONS

Abstract: In a model of Spitzer (1968) model, we begin with countably many particles distributed on the real line according to a Poisson distribution. Each particle then begins moving with a random velocity; these velocities are independent and have mean zero. The particles interact through elastic collisions: when particles meet, they exchange trajectories. We then choose a particular particle (the tagged particle) and let X(t) denotes its trajectory. Spitzer showed that, under a suitable rescaling of time and space, X(t) converges weakly to Brownian motion.
Harris (1965) demonstrated a similar result: if the individual particles move according to Brownian motion, then X(t) converges to fractional Brownian motion. These results were generalized even further by D\"{u}rr, Goldstein, and Lebowitz in 1985.
All of these results rely heavily on the initial distribution of the particles. The initial Poisson distribution provides tractable computations in the models of Spitzer, Harris, and D\"{u}rr et al;
In this talk, I will outline the following result: the (scaled) median of independent Brownian motions converges to a centered Gaussian process whose covariance function can be written down explicitly. As with the other results, proving tightness is the chief difficulty. Unlike the other results, the initial distribution of the particles does not play a key role. Tightness is proved in this model by direct estimates on the median process itself. It is my hope that these techniques can be generalized and used to extend the current family of results to models with arbitrary initial particle distributions.

Time: Monday, March 7, 2005 at 2:30 pm.

Location: PDL C-401

Speaker: Roman Kotecky (Charles University, Prague, and Microsoft Research)

Title: BIRTH OF EQUILIBRIUM DROPLET

Abstract: We consider large deviations for Ising model in the phase coexistence region. The typical behavior, inside the coexistence region and far from its edge, is governed by droplet configurations. However, a new type of transition is experienced close to the edge of the coexistence. It stems from the competition between droplet contributions and supersaturated phase and leads to an abrupt occurrence of a droplet. Its proof needs a careful evaluation of typical configurations in different regimes. Main results will be explained and some idea of the proofs will be given without assuming any preliminary knowledge about the Ising model.
The talk is based on joint papers with Marek Biskup and Lincoln Chayes as well as a recent work with Ostap Hryniv and Dima Ioffe.

Time: Monday, February 28, 2005 at 2:30 pm.

Location: THO 135

Speaker: Ryan O'Donnell (Microsoft Research)

Title: NOISE STABILITY OF BOOLEAN FUNCTIONS WITH LOW INFLUENCES

Abstract: Suppose we model a close election (such as Bush/Gore '00 or Gregoire/Rossi '04) by assuming n voters vote independently and 50-50 between two candidates, 0 and 1. An ``election scheme'' is a boolean function $f : \{0,1\}^n \to \{0,1\}$ mapping the votes to a winner; e.g., $f$ = Majority, or $f$ = Electoral College. Analyzing the properties of such functions is hampered by the fact that the trivial ``dictator'' schemes, $f(x_1, ..., x_n) = x_i$, are often extremal. It is thus both natural and desirable to restrict attention to $f$'s in which each voter has small ``influence''.
We resolve two conjectures regarding functions with low influences: 1. The ``Majority Is Stablest'' conjecture from theoretical computer science, which states that if each vote is mis-recorded independently with probability epsilon (butterfly ballot? Diebold?) then Majority is the low-influence election scheme most likely to preserve the outcome. 2. The ``It Ain't Over Till It's Over'' conjecture from social choice in economics, which states that if a random 99\% of the votes are in (from Florida, say) then for any low-influence election scheme, the outcome is still overwhelmingly likely to be ``too close to call''.
This is joint work with Elchanan Mossel (Berkeley) and Krzysztof Oleszkiewicz (Warsaw).

Time: Tuesday, February 22, 2005 at 2:30 pm.

Location: SAV 311

Speaker: Dayue Chen (Peking University)

Title: THE ANCHORED EXPANSION CONSTANT OF RANDOM GRAPHS

Abstract: The anchored expansion constant is a variant of the Cheeger constant; its positivity implies positive lower speed for the simple random walk, as shown by Virag (2000). We prove that if $G$ has a positive anchored expansion constant then so does every infinite cluster of independent percolation with parameter $p$ sufficiently close to 1. We also show that positivity of the anchored expansion constant is preserved under a random stretch if, and only if, the stretching law has an exponential tail.
This talk is based on my joint work with Yuval Peres and Gabor Pete of the University of California, Berkeley. The paper entitled ``Anchored Expansion, Percolation and Speed'' just appeared in the Annals of Probability.

Time: Monday, February 14, 2005 at 2:30 pm.

Location: THO 135

Speaker: Assaf Naor (Microsoft Research)

Title: MARKOV CHAINS IN METRIC SPACES AND THEIR APPLICATIONS TO METRIC GEOMETRY

Abstract: In this talk we will discuss the notion of Markov type: an important bi-Lipschitz invariant of metric spaces which was introduced by K. Ball. This invariant measures the affect of the geometry of a metric space $X$ on the speed of certain Markov chains taking values in $X$. We will describe some of the applications of Markov type, and proceed to present a proof of the recent solution of Ball's Markov type 2 problem, showing that $L_p, p>2$, has Markov type 2. This result completes the work of Ball and settles a conjecture of Johnson and Lindestrauss from 1992 by showing that every Lipschitz function defined on a subset of $L_p, p>2$, with values in $L_q, 1 < q <2$, extends to a Lipschitz function defined on all of $L_p$.
Based on joint work with Yuval Peres, Oded Schramm and Scott Sheffield.

Time: Monday, February 7, 2005 at 2:30 pm.

Location: THO 135

Speaker: Uriel Feige (Weizmann Institute and Microsoft Research)

Title: ON SUMS OF INDEPENDENT RANDOM VARIABLES

Abstract: We prove the following inequality: for every positive integer $n$ and every collection $X_1, \ldots, X_n$ of nonnegative independent random variables that each has expectation~1, the probability that their sum remains below $n+1$ is at least $\alpha > 0$. Our proof produces a value of $\alpha = 1/13 \simeq 0.077$, but we conjecture that the inequality also holds with $\alpha = 1/e \simeq 0.368$.

Time: Monday, January 31, 2005 at 2:30 pm.

Location: THO 135

Speaker: Richard Bass (University of Connecticut)

Title: RENORMALIZED SELF-INTERSECTION LOCAL TIME AND THE RANGE OF RANDOM WALKS

Abstract: Self-intersection local time $\beta_t$ is a measure of how often a Brownian motion (or other process) crosses itself. Since Brownian motion in the plane intersects itself so often, a renormalization is needed in order to get something finite. LeGall proved that $E e^{\gamma \beta_1}$ is finite for small $\gamma$ and infinite for large $\gamma$. It turns out that the critical value is related to the best constant in a Gagliardo-Nirenberg inequality. I will discuss this result (joint work with Xia Chen) as well as large deviations for $\beta_1$ and $-\beta_1$ and LILs for $\beta_t$ and $-\beta_t$. The range of random walks is closely related to self-intersection local times, and I will also discuss joint work with Jay Rosen making this idea precise.

Time: Tuesday, January 25, 2005 at 12:30 pm.

Location: MOR 219

Speaker: Bruce Erickson (University of Washington)

Title: FINITENESS OF INTEGRALS OF FUNCTIONS OF LEVY PROCESSES

Abstract: We determine necessary and sufficient conditions under which various integrals of functions of the supremum absolute value of a Levy process are finite. The conditions are expressed analytically in terms of the canonical Levy measure of the process. An application of some of these results leads to an interesting local (small time) comparison of the above mentioned supremum process with the supremum absolute jump process.
This is a brief report on some work in progress with R. Maller.

Time: Wednesday, January 12, 2005 at 3:30 pm.

Location: Padelford C-36

Speaker: Krzysztof Burdzy (University of Washington)

Title: THE ROBIN PROBLEM AND RAY-KNIGHT THEOREM

Abstract: The ``Robin problem'' or the ``third boundary problem'' is a mathematical model for the flow of a substance (or heat) out of a domain through a semi-permeable membrane. I will address the question of when the concentration of the substance (or the temperature) is bounded below by a constant over the whole domain. The argument is based in part on a very non-trivial (although old) result known as "Ray-Knight theorem". It describes the distribution of the local time of Brownian motion as a function of the space variable.

Time: Monday, Dec 6, 2004 at 2:30 pm.

Location: PDL C-401

Speaker: David Wilson (Microsoft Research)

Title: BALANCED BOOLEAN FUNCTIONS THAT CAN BE EVALUATED SO THAT EVERY INPUT BIT IS UNLIKELY TO BE READ

Abstract: A Boolean function of n bits is balanced if it takes the value 1 with probability 1/2. We exhibit a balanced Boolean function with a randomized evaluation procedure (with probability 0 of making a mistake) so that on uniformly random inputs, no input bit is read with probability more than $\Theta(n^{-1/2} \sqrt{\log n})$. We give a balanced monotone Boolean function for which the corresponding probability is $\Theta(n^{-1/3} \log n)$. We then show that for any randomized algorithm for evaluating a balanced Boolean function, when the input bits are uniformly random, there is some input bit that is read with probability at least $\Theta(n^{-1/2})$. For balanced monotone Boolean functions, there is some input bit that is read with probability at least $\Theta(n^{-1/3})$.
Joint work with Itai Benjamini and Oded Schramm.

Time: Monday, Nov. 29, 2004 at 2:30 pm.

Location: PDL C-401

Speaker: David White (University of Washington)

Title: INTERACTIONS OF A BROWNIAN PARTICLE AND AN INERT PARTICLE

Abstract: Frank Knight recently introduced a model for the motion of an inert particle that is impinged on one side by a Brownian particle. Interesting behavior can result when the two types of particles are combined in different configurations. We describe the stochastic process resulting from these interactions for a few possible configurations.

Time: Monday, Nov. 15 and Monday, Nov. 22, 2004 at 2:30 pm.

Location: PDL C-401

Speaker: Charles J. Geyer (University of Minnesota)

Title: PROBABILITY AND STATISTICS USING NELSON-STYLE NONSTANDARD ANALYSIS (parts I and II)

Abstract: Edward Nelson's book Radically Elementary Probability Theory shows how to `radically' simplify both nonstandard analysis (NSA) and probability theory. In this approach all sample spaces are finite and all nonempty events have nonzero probability. So all nontrivial collections of random variables are finite. We have only with finite sequences of random variables, stochastic processes with finite carriers, etc. This eliminates any need for measure theory. Nevertheless, infinitesimal and unlimited numbers allow analogs of phenomena of conventional probability theory, such as continuous random variables, laws of large numbers, central limit theorems, invariance principles, and Brownian motion.
In part I (Nov 15) we will introduce Nelson's `radically elementary' version of NSA, which is simple enough to teach to undergraduates, and using de Finetti's theorem as an example, show how this approach can greatly simplify probabilistic reasoning. We also start a survey of the definitions and main results of Nelson's book.
In part II (Nov 22) we will discuss some of our work: weak convergence in metric spaces, the portmanteau theorem, the continuous mapping theorem, the Glivenko-Cantelli theorem, Prohorov metric strong consistency of the empirical process, spatial point processes (redone Nelson-style).

Time: Monday, Nov. 8, 2004 at 2:30 pm.

Location: PDL C-401

Speaker: Benjamin Morris (Indiana University and Microsoft Research)

Title: THE MIXING TIME FOR THE THORP SHUFFLE

Abstract: In 1973, Thorp introduced the following card shuffling procedure. Cut the deck into two equal piles. Drop the first card from the left pile or the right pile according to the outcome of a fair coin flip; then drop from the other pile. Continue this way, flipping an independent coin each time, until both piles are empty.
Despite its simple description, the Thorp shuffle has been hard to analyze. It has long been believed that the mixing time is polynomial in log of the number of cards. We prove the first such bound.

Time: Monday, Nov. 1, 2004 at 2:30 pm.

Location: PDL C-401

Speaker: Chris Hoffman (University of Washington)

Title: HOW WELL CAN WE PREDICT A NEAREST NEIGHBOR PROCESS?

Abstract: We consider the class of integer valued nearest neighbor processes. These are the processes $S(t)$ such that for all $t$ $|S(t)-S(t+1)|=1$ a.s. In this problem we are given the past $S(0),S(-1),...$ and we try to predict $S(k)$. We want to bound the maximum probability that we predict correctly. Define $$v(k)=\sup_{n,S(0),S(-1),S(-2),\dots} P(S(0)-S(k)=n|S(0),S(-1),S(-2),\dots).$$ We will show that for any decreasing sequence $f(k)$ such that $\sum_{k=1}^{\infty}f(k)=\infty$ there does not exist a nearest neighbor process such that $$v(k)<{1\over kf(k)}$$ for all $k$ and that this condition is tight. We will also talk about how this problem relates to random walks on percolation clusters.

Time: Monday, Oct 18, 2004 at 2:30 pm.

Location: PDL C-401

Speaker: Zhenqing Chen (University of Washington)

Title: EIGENVALUES FOR SUBORDINATE PROCESSES IN DOMAINS

Abstract: Abstract: When studying spectral properties for nonlocal operator in domains, one often faces many new challenges. For example, in contrast to the Laplace operator case, even the first eigenvalue for 1-dimensional fractional Laplace operator in unit interval is not explicitly known. In this talk, we will show that it is possible to obtain two-sided eigenvalue estimates for fractional Laplacian in terms of the eigenvalues of the Dirichlet Laplacian in the domain. In fact, the above result holds more generally, with Laplacian being replaced by a self-adjoint operator $L$ that is the generator of a strong Markov process, and the fractional Laplacian being replaced by $-\phi (-L)$, where $\phi$ is the Laplace exponent of a subordinator. We further show that the eigenvalues of $\phi (-L)$ in a domain with Dirichlet exterior condition depends continuously on $\phi$. This talk is based on joint work with R. Song.

Time: Monday, Oct 11, 2004 at 2:30 pm.

Location: PDL C-401

Speaker: Nati Linial (Hebrew University of Jerusalem and Microsoft)

Title: RANDOM LIFTS OF GRAPHS AND WHAT THEY ARE GOOD FOR

Abstract:

Time: Monday, Oct 11, 2004 at 2:30 pm.

Location: PDL C-401

Speaker: Nati Linial (Hebrew University of Jerusalem and Microsoft)

Title: RANDOM LIFTS OF GRAPHS AND WHAT THEY ARE GOOD FOR

Abstract: The most thoroughly studied random graph model is the classical Erd\"os-Renyi G(n,p) model where edges are placed independently and with probability p between any pair from among n vertices. There is a strong feeling in many parts of discrete mathematics that this is not enough, and new models for random graphs are needed. The quest for new models often comes from a desire to depict some physical phenomena, or just to understand the typical behavior of a certain family of graphs. Random lifts are a new class of random graphs, and the chief reason for introducing them was the hope to construct graphs with special desired properties, which existing methods seem unable to achieve. Our research into these graphs has revealed lots of beautiful phenomena and raised new intriguing problems. However, only recently did it become possible to use Random Lifts to construct graphs "by design" i.e., graphs with some desired extremal properties. Specifically, they were utilized to explicitly construct graphs with very good spectral properties ("Quasi-Ramanujan" graphs). In this talk I will explain what random lifts are. I will also survey the main known results and some of the open problems.

Time: Monday, October 4, 2004 at 2:30 pm.

Location: PDL C-36

Speaker: Krzysztof Burdzy (University of Washington)

Title: LENSES IN SKEW BROWNIAN MOTION`

Abstract: Skew Brownian motion is a version of Brownian motion which makes more positive excursions from 0 than negative excursions (or vice versa). I will discuss a stochastic flow of skew Brownian motions, i.e., a family of skew Brownian motions driven by the same ``noise.'' Individual processes in the flow have a tendency to coalesce so this leads to a number of questions about the topological and stochastic nature of the flow. Lenses are pairs of distinct processes in the flow that start from the same point, diverge, and then converge.

Time: Thursday, August 26, 2004 at 3:00 pm.

Location: PDL C-36

Speaker: Wojbor A. Woyczynski (Case Western Reserve University)

Title: Critical nonlinearity exponent for Levy conservation laws

Abstract: Behavior of solutions of nonlinear evolutions of the form u_t=Lu-\nabla Nu, where L is a linear diffusive operator and N is a nonlinear operator depends on the interaqction and relative strength of L and N. In the case when L is an infinitesimal generator of a Levy process there is a critical nonlinearity which causes the asymptotic behavior of all solutions to be like the asymptotic behavior of special selfsimilar solutions. Statistical implications of this facts are indicated.

Time: Thursday, May 27, 2004 at 2:30 pm.

Location: THO 331

Speaker: Richard Sowers (University of Illinois at Urbana-Champaign)

Title: Random Perturbations of Pseudoperiodic Flows

Abstract: Arnol'd in 1991 characterized ``pseudoperiodic'' flows on the 2-dimensional torus. We consider small random perturbations of such flows. Under appropriate scaling of time, we search for an averaged picture which describes the evolution of local ``energies''. Under certain circumstances, we identify a certain limiting Markov process with glueing conditions (as suggested by Freidlin in 1996) which characterizes energy evolution.

Time: Monday, May 24, 2004 at 2:30 pm.

Location: THO 125

Speaker: Zoran Vondracek (University of Zagreb, Croatia)

Title: Ruin Probabilities for General Perturbed Risk Processes

Abstract: We study a general perturbed risk process with cumulative claims modeled by a subordinator with finite expectation, and the perturbation being a spectrally negative Levy process with zero expectation. We derive a Pollaczek-Hinchin type formula for the survival probability of that risk process, and give an interpretation of the formula based on the decomposition of the dual risk process at modified ladder epochs. We also give a formula that the ruin will occur by a jump of the subordinator.

Notice the different time and location

Time: Tuesday, May 18, 2004 at 2:30 pm.

Location: THO 331

Speaker: Renming Song (University of Illinois at Urbana-Champaign)

Title: Potential Theory of Geometric Stable Processes

Abstract: Geometric stable processes form a special class of Levy processes. Geometric stable processes are very useful in modeling heavy-tailed phenomena and have been used by various researchers in option pricing. In this talk we will present some recent results on the potential theory of geometric stable processes. In particular, we will talk about asymptotic behaviors of the Green function and jumping functions of geometric stable processes, and estimates on the capacities of small balls with respect to geometric stable processes. We also show that the Harnack inequality is valid for positive harmonic functions of geometric stable processes.

Time: Monday, May 10, 2004 at 2:30 pm.

Location: THO 125

Speaker: Chris Hoffman (University of Washington)

Title: Coexistence for Richardson Type Competing Spatial Growth Models

Abstract: In the Richardson growth model the vertices in Z^d can take on three possible states 0,1, and 2. Vertices in states 1 and 2 remain in their states forever, while vertices in state 0 which are adjacent to a vertex in state 1 (or state 2) can switch to state 1 (or state 2). We think of the vertices in states 1 and 2 as infected with one of two infections while the vertices in state 0 are considered uninfected. We start the models with a single vertex in state 1 and a single vertex is in state 2. We show that with positive probability state 1 reaches an infinite number of vertices and state 2 also reaches an infinite number of vertices. The key tool is applying the ergodic theorem to stationary first passage percolation.

Time: Monday, May 3, 2004 at 2:30 pm.

Location: THO 125

Speaker: Tadeusz Kulczycki (Wroclaw Technical University, visiting Purdue University)

Title: The Cauchy Process and the Steklov Problem

Abstract: Let $X_t$ be the Cauchy process in $R^d$. We investigate some of the fine properties of the semigroup of this process killed upon leaving a domain $D$. We establish a connection between the semigroup of this process and a mixed boundary value problem for the Laplacian in one dimension higher, known as the "Mixed Steklov Problem". Using this we derive a variational characterization for the eigenvalues of the Cauchy process in $D$. This characterization leads to many detailed properties of the eigenvalues and eigenfunctions for the Cauchy process inspired by those for the Brownian motion. The results are new even in the simplest geometric setting of the interval $D=(-1,1)$ where we obtain more precise information on the size of the second eigenvalue and on the geometry of the corresponding eigenfunction.

Time: Monday, April 26, 2004 at 2:30 pm.

Location: THO 125

Speaker: Gordon Slade (University of British Columbia, Visiting Microsoft)

Title: The phase transition for random subgraphs of the n-cube

Abstract: We describe recent results, obtained in collaboration with C. Borg, J. T. Chayes, R. van der Hofstad and J. Spencer, which provide a detailed description of the phase transition for random subgraphs of the n-cube.

Time: Monday, April 19, 2004 at 2:30 pm.

Location: THO 125

Speaker: Jason Swanson (UW)

Title: The Signed Variations of the Solution to a Stochastic Heat Equation

Abstract: We will consider the solution to a certain stochastic heat equation. This solution is a random function of time and space. For a fixed point in space, the resulting random function of time (call it $F(t)$) has the same local behavior as a fractional Brownian motion with Hurst parameter $H=1/4$. (Roughly speaking, this means that, almost surely, the function $F(t)$ is H\"{o}lder continuous with index $\alpha$ for all $\alpha<1/4$, but not for $\alpha\ge1/4$.) The function $F(t)$, therefore, has an infinite quadratic variation and, hence, is not a semimartingale. It follows then that the classical Ito calculus does not apply to $F(t)$.

Heuristic ideas about a possible new calculus for this process will be presented. These heuristics lead us in a natural way to define and study what will be called the ``signed" quadratic variation of $F(t)$. The main result to be presented is that, although the traditional quadratic variation of $F(t)$ is infinite, the signed quadratic variation converges to a Brownian motion.

Time: Monday, April 5, 2004 at 2:30 pm.

Location: THO 125

Speaker: Paul Shields

Title: Two New Methods of Markov Order Estimation

Abstract: Given an ergodic finite state Markov chain of unknown order K, the goal is to make an estimate k(n) of K from observation of a sample path of length n, such that k(n) is eventually almost sure equal to K. An important and widely used estimation method is Schwarz's BIC, which is based on Bayesian ideas. Recently, in joint work with Csiszar, BIC consistency was established without the usual prior bound assumption. The proof, however, is quite complex. I will discuss two new methods that are simple to describe, require no prior order bound, involve less computation than the BIC, and whose consistency proofs use only classical probability and information theory concepts. The first method focuses on maximum fluctuations of empirical conditional probabilities of order k over slowly growing intervals of values of k. The second method compares empirical conditional entropy of order k with an auxiliary, upwardly biased, entropy estimator. In both cases, the focused quantities have, eventually almost surely, a qualitative change in behaviour for the first time at the place where $k=K$. Extensions to random fields and to hidden Markov chains will also be discussed. (This is joint work with Yuval Peres.)

Time: Wednesday, March 24, 2004 at 2:30 pm.

Location: PDL C-36

Speaker: Marek Biskup (UCLA)

Title: Graph Distance in Long-range Percolation

Abstract: In 1967, using an ingenious sociological experiment, S. Milgram studied the length of acquaintance chains between "geometrically distant" individuals. The results led him to the famous conclusion that average two Americans are about six acquaintances (or "six handshakes") away from each other. We will model the situation in terms of long-range percolation on Z^d, where the nearest neighbor bonds represent the acquaintances due to geometric proximity -- people living in the house next door -- while long bonds are acquaintances established by other means -- e.g., friends from college. The question is: What is the minimal number of bonds one needs to traverse to get from site x to site y.
Thus, in addition to the usual connections between nearest neighbors on Z^d, any two sites x,y in Z^d at Euclidean distance |x-y| will be connected by an occupied bond independently with probability proportional to |x-y|^-s, where s>0 is a parameter. Using D(x,y) to denote the length of the shortest occupied path between x and y, the main question boils down to the asymptotic scaling of D(x,y) as |x-y| tends to infinity. I will discuss a variety of possible behaviors and mention known results and open problems. Then I will sketch the proof of the fact that, when s in the interval (d,2d), the distance D(x,y) scales like (log|x-y|)^Delta, where Delta^-1 is the binary logarithm of 2d/s.

SPECIAL COLLOQUIUM/PROBABILITY SEMINAR
Time: Tuesday, March 16, 2004 at 2:30 pm.

Location: SMI 205

Speaker: Wendelin Werner (Universite Paris-Sud)

Title: CONFORMAL FIELD THEORY VIA BROWNIAN LOOP SOUP

Abstract: We will (briefly) show how to relate Schramm-Loewner Evolutions and to define Conformal Field Theories using the Brownian loop-soup, a random conformally invariant countable family of overlapping Brownian loops in a domain that we introduced in a joint paper with Greg Lawler.

Time: Monday, March 8, 2004 at 2:30 pm.

Location: LOW 217

Speaker: Fadoua Balabdaoui (University of Washington)

Title: NONPARAMETRIC ESTIMATION OF A $K$-MONOTONE DENSITY ASYMPTOTIC DISTRIBUTION THEORY

Abstract: Let $k \geq 1$ be an integer. We consider nonparametric estimation of a $k$-monotone density on $(0,\infty)$ via the methods of Maximum Likelihood and Least Squares. Under the assumption that at a fixed point $x_0 > 0$, the true density $g_0$ satisfies $g^{(k)}_0(x_0) \ne 0$, we establish asymptotic minimax lower bounds for estimation of the $j$-th derivative of $g_0$ for $j=0, \cdots, k-1$. These bounds show that the rates of convergence of any estimator of $g^{(j)}_0(x_0)$ can be {\it at most} $n^{-(k-j)/(2k+1)}$. Furthermore, we are close to proving that the ML and LS estimators, $\hat{g}_n$ and $\tilde{g}_n$, achieve these rates, and that the limiting distributions depend on smooth stochastic processes $H_k$ that stay above (or below) $Y_k$, the $(k-1)$-fold integral of two-sided Brownian motion + $\left(k!/(2k)!\right) t^{2k}, t \in {\bf R}$ when $k$ is even (or odd). The key remaining difficulty for $k > 2$ consists in showing that the distance between two successive jump points $\tau^{-}_n$ and $\tau^{+}_n$ of $\hat{g}^{(k-1)}_n$ or $\tilde{g}^{(k-1)}_n$ (in the neighborhood of $x_0$) is $O_p(n^{-1/(2k+1)})$ as $n \to \infty$. Similarly, if $H_{k,c}$ denotes the envelope (or the \lq\lq invelope\rq\rq) of $Y_k$ when $k$ is odd (or even) on $\lbrack -c,c \rbrack$, $c > 0 $, it remains to prove that the distance between two successive points of touch $\tau^{-}_c$ and $\tau^{+}_c$, before and after a point $-c < t < c$, between the processes $H_{k,c}$ and $Y_k$ is $O_p(1)$ as $c \to \infty$. Several numerical examples will be shown to illustrate the theoretical results and conjectures. For that, we will introduce a $(2k-1)$-th iterative spline algorithm developed to compute the ML and LS estimators, and to obtain an approximation of the process $H_k$ on $\lbrack -c,c \rbrack $.

Joint work with Jon Wellner.

Time: Monday, March 1, 2004 at 2:30 pm.

Location: LOW 217

Speaker: Martin Barlow (University of British Columbia)

Title: RANDOM WALKS ON CRITICAL PERCOLATION CLUSTERS

Abstract: It is now known that random walks on supercritical ($p>p_c$) percolation clusters in $Z^2$ behave in many ways like the simple random walk on $Z^d$. The critical case ($p=p_c$) is much harder. One needs to consider the ``incipient infinite cluster''; in the cases where this has been defined it has a fractal structure. The easiest case is that of trees; this was studied by Kesten in 1986, but we can now revisit this problem with new techniques.

This is a joint Math Department Colloquium and Probability Seminar Talk
Time: Monday, February 23, 2004 at 2:30 pm.

Location: LOW 217

Speaker: Masatoshi Fukushima (Kansai University)

Title: POISSON POINT PROCESSES ATTACHED TO SYMMETRIC DIFFUSIONS

Abstract: Let $a$ be a non-isolated point of a topological space $S$ and $X^0$ be a symmetric diffusion on the complementary set $S_0$ which approaches to $a$ in finite time before killing with positive probability. By making use of Poisson point processes taking values in the spaces of excursions around $a$ whose characteristic measures are uniquely determined by $X^0$, we construct a symmetric diffusion on $S$ with no killing inside $S$ which extends $X^0$ on $S_0.$ We also prove that such an extension is unique in law and its resolvent and Dirichlet form admit explicit expressions in terms of $X^0.$

Time: Monday, February 9, 2004 at 2:30 pm.

Location: LOW 217

Speaker: Tilmann Gneiting (University of Washington)

Title: CONVOLUTION ROOTS OF COMPACTLY SUPPORTED RADIAL POSITIVE DEFINITE FUNCTIONS

Abstract: A classical theorem of Boas, Kac, and Krein states that a characteristic function $\varphi$ with $\varphi(x) = 0$ for $|x| \geq \tau$ admits a representation of the form $$ \varphi(x) = \int u(y) \overline{u(y+x)} dy, x \in \real $$ where $u \in L_2(\real)$ is complex-valued with $u(x) = 0$ for $|x| \geq \tau/2$. The result can be expressed equivalently as a factorization theorem for entire functions of finite exponential type. This talk examines the Boas-Kac representation under additional constraints: If $\varphi$ is real-valued and even, can the convolution root $u$ be chosen as a real-valued and/or even function?

A complete answer in terms of the zeros of the Fourier transform of $\varphi$ is obtained. Furthermore, the analogous problem for radially symmetric functions is solved. Perhaps surprisingly, there are compactly supported, radial positive definite functions that do not admit a convolution root with half support. Related results include pointwise and integral bounds on compactly supported positive definite functions and the solution to an associated minimization problem. Applications to spatial moving average processes, geostatistical simulation, crystallography, optics, and phase retrieval are noted.

This is joint work with Werner Ehm and Donald Richards.

Time: Monday, February 2, 2004 at 2:30 pm.

Location: LOW 217

Speaker: David Galvin (Microsoft Research)

Title: THE ``ENTROPY METHOD'' IN COMBINATORICS

Abstract: The binary entropy of a finite-range uniform random variable is exactly the log of the size of the range space. For this reason, entropy methods have become quite popular recently for tackling certain enumerative problems in combinatorics---any bounds that can be put on the entropy of a uniformly chosen member of a set correspond immediately to bounds on the size of the set.

In this talk I will introduce an entropy inequality due to J. B. Shearer that is proving to be a powerful tool in this direction. I will give two applications. The first is a swift entropy proof of an old result of Loomis and Watson, bounding the volume of a body in $R^d$ in terms the volumes of its $(d-1)$-dimensional projections. The second is a recent result (joint with P. Tetali of Georgia Tech) giving a tight upper bound on the number of graph homomorphisms from a regular bipartite graph to any fixed constraint graph.

Time: Monday, January 26, 2004 at 2:30 pm.

Location: LOW 217

Speaker: D. Brian Walton (University of Washington)

Title: HIDDEN MARKOV MODELS AND SINGLE-MOLECULE MOTOR PROTEIN EXPERIMENTS

Abstract: Motor proteins convert chemical energy into directed mechanical motion, often along filamentary tracks. This talk will introduce a particular motor protein, kinesin, which converts the energy released from ATP hydrolysis into motion along a microtubule. Recent biophysical experiments have tethered a glass bead to an individual kinesin which allows to impose an external force by laser tweezers as well as to record detailed position measurements of the bead as it moves. Using a continuous time Markov chain to model the driving cycle of the protein and a tethered diffusion to model the position of the bead, we develop a hidden Markov model for analyzing the experimental data. Such a model allows for parameter estimation and model selection.

Time: Monday, January 11, 2004 at 2:30 pm.

Location: LOW 217

Speaker: Panki Kim (University of Washington)

Title: $(-\Delta)^{\alpha/2}$-HARMONIC FUNCTIONS IN BOUNDED $\kappa$-FAT OPEN SET

Abstract: In this talk, we will discuss about the boundary behavior of $(-\Delta)^{\alpha/2}$-harmonic functions (equivalently harmonic function for symmetric $\alpha$-stable processes) in bounded $\kappa$-fat open set where $\alpha \in (0,2)$.

Consider a positive $(-\Delta)^{\alpha/2}$-harmonic function $u$ in a bounded $\kappa$-fat open set $D$, and a positive $(-\Delta)^{\alpha/2}$-harmonic function in $D$ vanishing outside of $D$. It is true that non-tangential limits of $u/h$ exist almost everywhere with respect to the Martin-representing measure of $h$.

We also study relative Fatou's theorem for operators obtained from the generator of the killed $\alpha$-stable process in bounded $\kappa$-fat open set $D$ through non-local Feynman-Kac transforms.

Time: Monday, Decemmber 8, 2003 at 2:30 pm.

Location: PDL C-36

Speaker: Alan Michael Hammond (UC Berkeley)

Title: Kinetic Limit for Coagulating and Diffusing Particles

Abstract: Consider a system of $N$ balls of radius $\epsilon$, initially placed at Poisson random locations in a compact region of space $R^d$, with $d \geq 3$. Each ball has a mass $m \in N$, and evolves as Brownian motion with a diffusion rate $d(m)$. When two balls come close enough that they overlap, they are prone to coagulate, being replaced by a new ball that combines the mass of the old two, and pursues a Brownian evolution at a new diffusion rate. In this joint work with Fraydoun Rezakhanlou, we study the macroscopic evolution of the particle densities, in the mean free path regime, where $N \epsilon^{d-2}$ tends to a constant as $N$ is taken high (this limit is chosen to ensure that the typical collision rate of a particle remains of unit order per unit time). This evolution takes the form of a coupled system of PDEs, indexed by the mass parameter, and sometimes called the discrete diffusive coagulation equations. Time permitting, we will discuss the implications of introducing fragmentation into the model.

Time: Monday, Decemmber 1, 2003 at 2:30 pm.

Location: PDL C-36

Speaker: Gabor Pete (UC Berkeley)

Title: Bootstrap percolation on infinite trees and non-amenable groups

Abstract: Consider an arbitrary infinite graph with two possible states for each vertex: {\it vacant} or {\it occupied}. We start with a random configuration in which each vertex is occupied independently with a fixed probability $p$, and then follow a deterministic {\it spreading rule}: if a vacant site has at least $k$ occupied neighbors at a certain time step, then it becomes occupied in the next step. We are interested in the values of $p$ for which complete occupation of the graph happens with positive probability. This process is well-studied on $Z^d$; here we investigate it on infinite trees and non-amenable Cayley graphs. For example, on general trees we find the following discontinuity: if the {\it branching number} of a tree is strictly less than $k$, then no $p<1$ will result in occupying the tree completely, while on the $k$-regular tree, an initial configuration with $p=1-1/k$ already succeeds almost surely.

This is joint work with J\'ozsef Balogh and Yuval Peres.

Time: Monday, November 24, 2003 at 2:30 pm.

Location: PDL C-36

Speaker: David Revelle (UC Berkeley)

Title: Some exotic behavior of random walks on lamplighter groups

Abstract: The behavior of random walks on finitely generated groups is best understood for groups that are either non-amenable or have polynomial volume growth. Random walks on amenable groups of exponential volume growth, however, can have a wide variety of behaviors, many of which do not occur in classical examples. They gave examples of groups for which the probability of a random walk returning to the identity at time $n$ decays at a rate that cannot occur on Lie groups, and have been used to disprove conjectures about the behavior of harmonic functions on amenable groups as well as give examples of groups on which inward biased walks can escape from the origin more quickly than unbiased walks.

The first examples of groups with many of these new behaviors have been lamplighter groups and other wreath products. We will present a number of these interesting examples and discuss their place in the general theory of random walks on groups.

Time: Monday, November 17, 2003 at 2:30 pm.

Location: PDL C-36

Speaker: Benjamin J Morris (Indiana University)

Title: The mixing time for simple exclusion

Abstract: We obtain a tight bound of $O(L^2 log r)$ for the mixing time of the exclusion process in the $d$-dimensional box of side length $L$ with $r \leq \half L^d$ particles.

Time: Monday, November 10, 2003 at 2:30 pm.

Location: PDL C-36

Speaker: Jiangang Ying (Fudan University and University of Washington)

Title: Time change and Feller measure

Abstract: We will discuss an identity going back to 1931, which is now called Douglas integral. The so-called Feller measure is identified with the jumping measure of the time changed process and it is proven that the Douglas integral type formula holds for diffusion process.

Time: Monday, November 3, 2003 at 2:30 pm.

Location: PDL C-36

Speaker: Scott Sheffield (Visiting Microsoft Research)

Title: Schramm-Loewner evolution and the Gaussian free field

Abstract: Many physical phenomena---like the adherence of particles to crystal surfaces or the way crystal surfaces fluctuate---are essentially two-dimensional. The boundaries of particle clusters and the contour lines of fluctuating surfaces may be viewed as random non-intersecting loop ensembles.

The discrete Gaussian free field (a.k.a. massless free field or harmonic crystal) is a popular model for describing the fluctuations of random surfaces. We show that the scaling limit of certain contour lines of discrete Gaussian free fields is given by the Schramm-Loewner evolution, SLE(4). We also introduce a conformally invariant class of random two-dimensional loop ensembles. This talk is based on joint work with Oded Schramm.

Time: Monday, October 27, 2003 at 2:30 pm.

Location: PDL C-36

Speaker: Krzysztof Burdzy (University of Washington)

Title: TRAPS FOR REFLECTED BROWNIAN MOTION

Abstract: Consider an open set $D\subset R^d$, $d\geq 2$, and a closed ball $B\subset D$. Let $\E^xT_B$ denote the expectation of the hitting time of $B$ for reflected Brownian motion in $D$ starting from $x\in D$. A set $D$ is called a trap domain if $\sup_x \E^x T_B = \infty$. One can fully characterize simply connected planar trap domains using a geometric condition. A number of less complete results for multidimensional domains are available. Time permitting, I will discuss the relationship between trap domains and some other potential theoretic properties of $D$ such as compactness of the 1-resolvent of the Neumann Laplacian. An answer to an open problem raised by Davies and Simon in 1984 about the possible relationship between intrinsic ultracontractivity for the Dirichlet Laplacian in a domain $D$ and compactness of the 1-resolvent of the Neumann Laplacian in $D$ will be given.

Joint work with Zhenqing Chen and Don Marshall.

Time: Monday, October 20, 2003 at 2:30 pm.

Location: PDL C-36

Speaker: Ping Ao (UW, Departments of Mechanical Engineering and Physics)

Title: Stochastic Differential Equations from a Scientist's View

Abstract: In physics and other branches of natural and social sciences as well as in engineering, one often encounters the solving of stochastic differential equations or Langevin equations. Among the important questions, the global trend of evolution has been dominant. In my talk I will put stochastic differential equations in the broader perspective of physics, and formulate a few mathematical problems based on a physicist's intuition: the structure of stochastic differential equations, the construction of potential hence the generalized Boltzmann-Gibbs distribution, and the connection to partial differential equations, Fokker-Planck equations. I am looking forward to professional mathematicians' feedback.

Time: Monday, October 12, 2003 at 2:30 pm.

Location: PDL C-36

Speaker: Vlada Limic (University of British Columbia)

Title: Attracting edge property for reinforced random walks

Abstract: Using martingale techniques and comparison with the generalized Urn scheme, one can show that the edge reinforced random walk on a graph of bounded degree, with the {\em weight function} W(k) = k^\rho,\,\rho > 1, crosses a random {\em attracting} edge at all large times. If the graph is a triangle, the above result is in agreement with a conjecture of Sellke (1994).

Time: Monday, October 6, 2003 at 2:30 pm.

Location: PDL C-36

Speaker: Panki Kim (University of Washington)

Title: Weak Convergence of Censored and Reflected Stable Processes

Abstract: A possible way of studying properties of some stochastic process in a open set $D$ with ``rough'' boundary is first to consider a sequence of stochastic processes in smooth open sets $D_k$ increasing to $D$. Then one could consider properties of that stochastic process in $D$ through the weak limit.

In this talk, we will discuss weak convergence of censored and reflected stable processes, which were introduced recently by Bogdan, Burdzy and Chen. One of the powerful tools in studying weak convergence of Markov processes is the so-called Mosco convergence. Some generalization of classical approximation theory (Trotter-Kato) and Mosco convergence will be introduced. We will also discuss about the Skorohod topology on the space of right continuous functions with left limits, and the tightness on that space. Some sufficient conditions for weak convergence will be discussed.

Time: Wednesday, September 24, 2003 at 2:30 pm.

Location: THO 231

Speaker: Serban Nacu (UC Berkeley)

Title: Fast Simulation of New Coins from Old

Abstract: We consider the problem of using a coin with probability of heads $p$ ($p$ unknown) to simulate a coin with probability of heads $f(p)$, where $f$ is some known function. We prove that if $f:I \rightarrow (0,1)$ is real analytic on the closed interval $I \subset (0,1)$, then it has a fast simulation (the number of needed inputs has tails which decay exponentially fast). Conversely, if a function $f$ has a fast simulation on an open set, it is real analytic on that set.

This is a joint work with with Yuval Peres.

Time: Monday, June 2, 2003 at 2:30 pm.

Location: SMI 313

Speaker: Takashi Kumagai (Tokyo University, Japan)

Title: STABILITY OF HEAT KERNEL ESTIMATES AND HOMOGENIZATION ON FRACTAL GRAPHS

Abstract: We consider stability of the long time behaviour of the Markov process (solution of the heat equation) when local structures are modified. The talk consists of three parts:

1) We introduce several recent results (including ours) on equivalence conditions for sub-Gaussian heat kernel estimates and their stability.

2) We give heat kernel estimates for a concrete class of finitely ramified fractal graphs.

3) We consider homogenization problem on the class of fractals.

Time: Wednesday, May 28, 2003 at 2:30 pm.

Location: SAV 131

Speaker: Neal Madras (York University)

Title: DECOMPOSITION OF MARKOV CHAINS

Abstract: The speed of convergence of a Markov chain to its equilibrium distribution has been a subject of intense study in recent years. Much progress has been made for chains with nice structure, but one often has to deal with chains that are not quite so nice. This talk will describe a method that analyzes convergence rates by decomposing a Markov chain into smaller pieces. The idea is that if the chain equilibrates rapidly on each piece, and if the chain moves from piece to piece efficiently, then the entire chain equilibrates rapidly. We will give some examples of this method in action. This talk describes joint work with Dana Randall and with Zhongrong Zheng.

Time: Monday, May 19, 2003 at 2:30 pm.

Location: SMI 313

Speaker: Jon A. Wellner (University of Washington)

Title: CONCENTRATION INEQUALITIES AND LIMIT THEOREMS FOR RATIOS

Abstract: Concentration inequalities have become increasingly valuable as tools in empirical process theory. In this talk I will discuss recent concentration inequalities due to Talagrand, Ledoux, and Massart. I will show how these can be used to derive some new inequalities for ratio-type suprema of empirical processes. The new inequalities will then be used to prove several new limit theorems for ratio-type suprema and to recover a number of the results of Alexander.

As a statistical application, I will briefly discuss an ``oracle inequality'' for nonparametric regression.

Time: Monday, May 12, 2003 at 2:30 pm.

Location: SMI 313

Speaker: Zhen-Qing Chen (University of Washington)

Title: BROWNIAN MOTION WITH SINGULAR DRIFT

Abstract: We consider the stochastic differential equation $$dX_t=dW_t+dA_t,$$ where $W_t$ is $d$-dimensional Brownian motion with $d\geq 2$ and the $i$th component of $A_t$ is a process of bounded variation that stands in the same relationship to a measure $\pi^i$ as $\int_0^t f(X_s) ds$ does to the measure $f(x)dx$. We prove weak existence and uniqueness for the above stochastic differential equation when the measures $\pi^i$ are members of the Kato class $\K_{d-1}$. The infinitesimal generator of such a process is a Laplacian with a very singular drift $\pi \cdot \nabla$.As a typical example, we obtain a Brownian motion that has upward drift when in certain fractal-like sets, and show that such a process is unique in law.

This is a joint work with Rich Bass.

Time: Monday, May 5, 2003 at 2:30 pm.

Location: SMI 313

Speaker: Chris Hoffman (University of Washington)

Title: PHASE TRANSITIONS IN ONE DIMENSIONAL SYSTEMS

Abstract: Many probabilistic models with short range interactions, such as percolation and the Ising model, exhibit phase transitions in two dimensions, but not in one dimension. One dimensional versions of the Ising model and percolation with long range interactions can exhibit phase transitions. I will also discuss phase transitions in processes defined by a continuous g function. I will describe an example due to Bramson and Kalikow and talk about the question of how long the interactions must be in order to have a phase transition.

This is joint work with Noam Berger and Vladas Sidoravicius.

Time: Monday, April 28, 2003 at 2:30 pm.

Location: SMI 313

Speaker: David Wilson (Microsoft Theory Group)

Title: CONFORMAL RADII OF LOOP MODELS

Abstract: We consider two loop models related to domino tilings. The first system of loops is formed by superimposing two uniformly random domino tilings, and is conjectured to be related to $SLE_4$. The second system of loops are the loops of the ``cycle-rooted spanning forest'' formed when applying the Temperleyan correspondence to a region containing a hole, and is conjectured to be related to $SLE_2$. Under the assumption of conformal invariance, and a couple of other assumptions, we derive the distribution of conformal radii of the nested loops, as well as the ``electrical thickness''', which is the difference between the conformal radius and capacity.

Joint work with Rick Kenyon.

Time: Monday, April 21, 2003 at 2:30 pm.

Location: SMI 313

Speaker: David Galvin (Microsoft Theory Group)

Title: GIBBS MEASURES FOR INDEPENDENT SET MODELS

Abstract: For a graph $G$ with vertex set $V(G)$, write $I(G)$ for the collection of {\it independent sets} of $G$ (sets of vertices no two of which are adjacent). When $G$ is finite, there is no problem interpreting the phrase ``uniformly chosen member of $I(G)$''. But how do we interpret it when $G$ (and hence $I(G)$) is infinite? One natural answer is to say that a measure $m$ on $I(G)$ is uniform if its restriction to finite patches is uniform. [Formally, this means that for $II$ chosen from $I(G)$ according to $m$, and for all finite subsets $W$ of $V(G)$, the conditional distribution of $II \cap W$ given $II \cap (V\setminus W)$ is ($m$-a.s.) uniform on the independent sets of $W$ which are compatible with $II \cap (V\setminus W)$]. We call such a measure a {\it Gibbs measure}. General arguments show that Gibbs measures always exist. For some infinite graphs, such as the two-dimensional integer lattice $Z^2$, the Gibbs measure is unique. But this is not the case for every graph. Indeed, if the dimension $d$ is large enough, there are at least two Gibbs measures on $I(Z^d)$. I will outline a proof of this result, which combines arguments from statistical physics with delicate combinatorial enumeration.

This is joint work with Jeff Kahn of Rutgers.

Time: Monday, April 14, 2003 at 2:30 pm.

Location: SMI 313

Speaker: Federico Marchetti (Politecnico di Milano)

Title: RANDOM SEQUENCES OF NESTED INTERVALS AND THE BARGAINING PROBLEM

Abstract: The limit of random sequences of nested intervals can be thought as providing a ``dynamic'' solution to the so-called bargaining problem. We discuss a simple Markovian case. As an example it is easy to recover Nash's 1950 solution, as the mean value of such a probabilistic solution. One application is, in turn, to use the bargaining model to select a price in incomplete markets.

Mathematics Department Colloquium :
Time: Thursday, April 3, 2003 at 4 pm.

Location: Thomson 119

Speaker: Michael Roeckner (University of Bielefeld, Germany)

Title: Heat equation in infinitely many variables and applications to stochastic partial differential equations

Abstract: I will first review the connection between ordinary stochastic differential equations (OSDE) on ${\bf R}^d$ and parabolic partial differential equations (such as the classical heat equation). Subsequently, a generalization to OSDE's in infinite dimensions will be given. A purely analytic approach to solve the corresponding (generalized) heat equation in infinitely many variables will be presented. Infinite dimensional OSDE's related to parabolic stochastic partial differential equation will be discussed. Examples will include the stochastic Ginzburg-Landau equation, the generalized stochastic Burgers equation, and the stochastic Navier-Stokes equation.

Time: Tuesday, April 1, 2003 at 2:30 pm.

Location: SMI 404

Speaker: Wembo Li (University of Delaware)

Title: Recent developments on small ball probabilities for stable processes

Abstract: The small ball probability or small deviation studies the behavior of \log \mu (x : ||x|| \le t) as t tend to zero for a given measure \mu and a norm ||.||. In the literature, small ball probabilities of various types are studied and applied to many problems of interest under different names such as small deviation, lower tail behavior, two sided boundary crossing probabilities, the first exit probabilities, the asymptotes of Laplace transforms, etc. We will overview some of the recent developments for stable measures/processes and present various connections with other areas of probability and analysis.

Time: Monday, March 31, 2003 at 2:30 pm.

Location: SMI 313

Speaker: Balint Toth (Budapest University of Technology and Economics)

Title: Derivation of Leroux's pde as the hydrodynamic limit of a two component system

Abstract: By applying a stochastic version of the method of \emph{compensated compactness} (originally developed by F. Murat, L. Tartar, R. DiPerna for proving convergence of the vanishing viscosity solutions of hyperbolic systems of conservation laws) we prove hydrodynamic limit -- even beyond the appearance of shock waves -- for an interacting particle system with two conservation laws. We obtain Leroux's system as Euler equations for our models. This is the first time that hyperbolic hydrodynamic limit is proved beyond the appearence of shock wavas for systems with more than one conservation laws. Joint work with Jozsef Fritz.

Time: Monday, March 10, 2003 at 2:30 pm.

Location: MGH 242

Speaker: Christian Borgs (Microsoft Research)

Title: The Scaling Window for Percolation on Finite Transitive Graphs

Abstract: Many models of practical relevance, like faulty wireless networks, are well described by random subgraphs of finite graphs, or, more probabilistically, by percolation on finite graphs. For both theoretical and practical reasons, one of the most interesting properties of these models is the behavior of the largest connected cluster as the underlying edge density is varied.

While the behavior of the largest cluster is well understood for the complete graph, which was first systematically studied by Erdos and Renyi in 1963, not much was known for general finite graphs.

In this talk I formulate conditions under which transitive graphs on N vertices exhibit the same scaling behavior as the complete graph, i.e. a scaling window of width N^{-1/3} in which the size of the largest cluster is of order N^{2/3}.

This work is in collaboration with Jennifer Chayes, Gordon Slade, Joel Spencer and Remco van der Hofstad.

Time: Monday, March 3, 2003 at 2:30 pm.

Location: MGH 242

Speaker: Oded Schramm (Microsoft Research)

Title: Random planar triangulations

Abstract: Triangulations of the plane with n vertices fall into finitely many isomorphism classes. The number of such classes has been determined by Tutte. Let n be large and let T_n be randomly-uniformly chosen among such isomorphism classes. The geometry of T_n turns out to be very different from the geometry one gets by random constructions based on the Euclidean geometry, such as Voronoi triangulations. In a way, T_n is a "generic" metric of the sphere. Physicists have been interested in these triangulations (under the name "quantum gravity"). The purpose of the talk will be to survey some recent progress in the understanding the geometry of the uniform triangulations.

Time: Monday, February 10, 2003 at 2:30 pm.

Location: MGH 242

Speaker: Jason Swanson (University of Washington)

Title: The p-th Variation of a Brownian Martingale with an Application to Mathematical Finance

Abstract: It is well known that a continuous martingale M_t has a finite quadratic variation, which is independent of time partitions used. Moreover, the p-th variation of M_t is zero if p>2 and infinity if p<2.

For a continuous martingale M_t that is adapted to a Brownian filtration and for p other than 2, suitably rescaling the p-th variation of M_t will result in nontrivial limits. Unlike the p=2 case, however, the limit depends on the choice of the time partitions. I will discuss what the rescaling is, what the limit is, and how it depends on the time partitions.

The special case p=1 will be used to partially generalize a result of Grannan and Swindle regarding the scaled limit of transaction costs in a model of mathematical finance.

Time: Monday, February 3, 2003 at 2:30 pm.

Location: MGH 278

Speaker: Zhen-Qing Chen (University of Washington)

Title: Boundary Trace of Reflecting Brownian Motion

Abstract: Reflecting Brownian motion (RBM) can be constructed on smooth as well as on non-smooth domains. For example, RBM in a simply connected planar domain can be defined as the image under the conformal map of RBM in a unit disk after a time change. A more robust way of defining RBM in a Euclidean domain in any dimension is to use energy form or Dirichlet form method. In this talk, we will show that, under some quite general conditions, RBM has the uniform dimension property that says the Hausdorff dimension of the image of a time set under RBM doubles that of the time set. We will also present results on the Hausdorff dimension for the occupation time set of RBM on the boundary, which then gives the Hausdorff dimension for the boundary trace of RBM. The above results are applicable to many Euclidean domains with fractal-like boundaries.

This is a part of a joint work with Itai Benjamini and Steffen Rohde.

Time: Monday, January 27, 2003 at 2:30 pm.

Location: MGH 278

Speaker: David M.Mason (University of Delaware)

Title: An Exponential Inequality for the Weighted Approximation to the Uniform Empirical Process

Abstract: Mason and van Zwet (1987) obtained a refinement to the Komlos, Major, and Tusnady (1975) Brownian bridge approximation to the uniform empirical process. From this they derived a weighted approximation to this process, which has shown itself to have some important applications in large sample theory. We will show that their refinement, in fact, leads to a much stronger result, which should be even more useful than their original weighted approximation. We demonstrate its potential applications through several interesting examples. These include a moment bound result which is useful in the study of central limit theorems for the both the trimmed and untrimmed Wasserstein distance between the empirical and the true distribution.

Time: Monday, January 13, 2003 at 2:30 pm.

Location: MGH 278

Speaker: Krzysztof Burdzy (University of Washington)

Title: LENSES IN SKEW BROWNIAN FLOW

Abstract: I will discuss a stochastic flow in which individual particles follow skew Brownian motions, with each one of these processes driven by the same Brownian motion. Due to the lack of the simultaneous strong uniqueness for the whole system of stochastic differential equations, the flow contains lenses, i.e., pairs of skew Brownian motions which start at the same point, bifurcate, and then coalesce in a finite time. I will present qualitative and quantitative (distributional) results on the geometry of the flow and lenses.

This is joint work with Haya Kaspi, and is based on two earlier papers, one joint with Barlow, Kaspi and Mandelbaum, and the other joint with Chen.

Time: Monday, December 9, 2002 at 2:30 pm.

Location: THO 331

Speaker: Hong Qian (University of Washington)

Title: NON-EQUILIBRIUM STATISTICAL MECHANICS OF SINGLE MOLECULES

Abstract: I shall discuss the general stochastic theory of Kurchan-Lebowitz-Spohn [1] and Jarzynski [2] for non-equilibrium steady-state, and then show how to experimentally verify some of the results from single molecule experiments on enzymes. A renewal process model will be proposed for enzyme kinetics.

[1] J.L. Lebowitz and H. Spohn, J. Stat. Phys. 95 (1999), 333--365

[2] Jarzynski, Phys. Rev. Lett. 78, 2690-2693 (1997)

Time: Monday, December 2, 2002 at 2:30 pm.

Location: THO 331

Speaker: Bruce Erickson (University of Washington)

Title: THE STRONG LAW FOR RANDOMIZED RANDOM WALKS

Abstract: Abstract: I will discuss some joint work, in progress, with R. Maller on the almost sure behavior of $\{S_{T_n}/n\}$, $n\to\infty$, where ${T_n\}$ is an independent integer renewal process and $\{S_m;\, m\ge 0\}$ is a random walk on the line. Interesting (and un-intuitive, I hope) examples occur when first moments do not exists.

Time: Monday, November 25, 2002 at 2:30 pm.

Location: THO 331

Speaker: Assaf Naor (Microsoft Research)

Title: ENTROPY PRODUCTION AND THE BRUNN-MINKOWSKI INEQUALITY

Abstract: Abstract: Let $X$ be a real valued random variable with density $f$. Its entropy is defined by $\Ent(X)=-\int f\log f$. A classical inequality of Shannon and Stam states that if $X, Y$ are IID then $\Ent((X+Y)/\sqrt{2})\ge \Ent(X)$. The problem whether or not the sequence $E_n=\Ent((X_1+...+X_n)/\sqrt{n})$ is increasing for $X_1,..., X_n$ IID remained open (in particular it wasn't known whether it is always the case that $E_3\ge E_2$). In this talk we will discuss the recent positive solution of this problem due to S. Artstein, K. Ball, F. Barthe and the speaker. The proof is based on a new formula for the entropy of a marginal which is motivated by (the proof of) the Brunn-Minkowski inequality. We will also discuss several other applications of this formula. In particular, we will show that if $X$ satisfies the Poincare inequality and $Y$ is an IID copy of $X$ then: $$\Ent((X+Y)/\sqrt{2})-\Ent(X)\ge c(\Ent(G)-\Ent(X))$$ where $G$ is a Gaussian random variable with the same variance as $X$ and $c$ depends only on the Poincare constant of $X$. Since the Gaussian has maximal entropy, this strengthening of the Shannon-Stam inequality yields a quantitative information theoretic proof of the central limit theorem. Time permitting, we will also discuss higher dimensional versions of these results, as well as related inequalities such as Shannon's entropy power inequality.

Time: Monday, November 18, 2002 at 2:30 pm.

Location: THO 331

Speaker: Benjamin Morris (University of California, Berkeley)

Title: EVOLVING SETS AND MIXING

Abstract: We introduce a probabilistic technique that yields the sharpest bounds obtained on mixing times for Markov chains in terms of isoperimetric properties of the state space. We show that the bounds for mixing time in total variation obtained by Lovasz and Kannan can be refined to apply to the maximum relative deviation $|p^n(x,y)/\pi(y) -1|$ of the distribution at time $n$ from the stationary distribution $\pi$. Joint work with Yuval Peres.

Time: Monday, November 4, 2002 at 2:30 pm.

Location: THO 331

Speaker: Panki Kim (University of Washington)

Title: STABILITY OF MARTIN BOUNDARY UNDER NON-LOCAL FEYNMAN-KAC PERTURBATIONS

Abstract: For $\alpha \in (1, 2)$, a censored $\alpha$-stable process $Y$ in bounded $C^{1,1}$ open set $D$ is a process obtained from a symmetric $\alpha$-stable Levy process by restricting its Levy measure to $D$. Recently It is shown that the Martin boundary and minimal Martin boundary of $Y$ can all be identified with the Euclidean boundary of $D$. In this talk, We discuss the stability of Martin boundary and Martin representation under non-local Feynman-Kac perturbations. As an application, Fatou's Theorem for operators obtained from the generator of $Y$ through non-local Feynman-Kac perturbations will be discussed.

This talk is based on a joint paper with Z.-Q. Chen ('02).

Time: Monday, October 14, 2002 at 2:30 pm.

Location: THO 331

Speaker: Zenghu Li (Beijing Normal University and University of Oregon)

Title: STOCHASTIC INTEGRAL EQUATIONS AND MEASURE-VALUED DIFFUSIONS CARRIED BY STOCHASTIC FLOWS

Abstract: Let $\{W(ds,dy): s\ge 0, y\in\IR\}$ be a time-space white noise and $h$ a smooth, square-integrable function on $\IR$. A stochastic flow $\{x(a,t): a\in\IR, t\ge 0\}$ is defined by the equation $$ x(a,t) = a + \int_0^t\int_{\IR} h(y-x(a,s))W(ds,dy). $$ A stochastic integral equation carried by the flow is discussed, which involves a Poisson process on the space of one-dimensional excursions. We show that the equation has a pathwise unique solution, which is then a measure-valued {\it diffusion} process. The approach is of interest since the uniqueness of solution of the corresponding martingale problem still remains open. The diffusion process is interpreted as a measure-valued branching process with immigration carried by the flow $\{x(a,t): a\in\IR, t\ge 0\}$. When $\IR$ shrinks to a single point, our equation gives a decomposition of a class of one-dimensional diffusions into excursions, which is also a new result.

This talk is based on joint papers with D.A. Dawson ('02) and Z.F. Fu ('02).

Time: Monday, October 14, 2002 at 2:30 pm.

Location: THO 331

Speaker: Zhen-Qing Chen (University of Washington)

Title: HEAT KERNEL ESTIMATES FOR STABLE-LIKE PROCESSES ON $d$-SETS

Abstract: The notion of $d$-set arises in the theory of function spaces and in fractal geometry. Geometrically self-similar sets are typical examples of $d$-sets. In this talk, we will discuss stable-like processes on $d$-sets, which include reflected stable processes in Euclidean domains as a special case. More precisely, we will present parabolic Harnack principle and derive sharp two-sided heat kernel estimate for such stable-like processes. Results on the exact Hausdorff dimensions for the range of stable-like processes will also be given.

This talk is based on a recent joint work with Takashi Kumagai.

Time: Monday, October 7, 2002 at 2:30 pm.

Location: THO 331

Speaker: David Brian Walton (University of Washington)

Title: ASYMPTOTIC LAW OF INDIRECT OBSERVATIONS WITH STATE-DEPENDENT NOISE

Abstract: A little over a year ago, a paper entitled "Noise Suppression by Noise" appeared in Phys. Rev. Lett. (Vilar and Rubi, 2001). Essentially, a hidden state evolves as an Ornstein-Uhlenbeck process X(t), and observations are made of a function of the state in addition to state-dependent white noise: dY(t)=f(X(t)) dt + \beta(X(t)) dW(t). The results of Vilar and Rubi consider a perturbative and asymptotic result to the autocorrelation function, and show that the noise scale of the resulting autocorrelation function can be reduced by increasing the noise scale of the hidden state process. I will demonstrate that the result actually relates to a central limit theorem of the observation process, and I will give exact formulas for the original perturbative results in terms of appropriate expectations.

Time: Tuesday July 23, 2002 at 2:30 pm.

Location: THO 325

Speaker: Tzong-Yow Lee (University of Maryland at College Park)

Title: Integrated Brownian motions and Sturmian theory

Abstract: We shall relate various integrated Brownian motions to higher order elliptic operators, and use this connection to obtain a stochastic domination result for the integrated BM's. This is a work in progress with F. Gao, L. Greenberg, J. Hannig, and F. Torcaso.

Time: Wednesday, July 3, 2002 at 2:30 pm.

Location: Communications 230

Speaker: Siva Athreya (Indian Statistical Institute)

Title: LONG TERM BEHAVIOUR OF BROWNIAN FLOW WITH JUMPS

Abstract: We consider a stochastic jump flow in an interval $(-a,b)$, where $a,b > 0$. Each particle of the flow performs a canonical Brownian motion and jumps to zero when it reaches $-a$ or $b$. We study the long term behavior of a random measure $\mu_t$ which is the image of the flow. This is joint work with Elena Kosegyna and Steve Tanner.

Time: Monday, June 3, 2002 at 2:30 pm.

Location: Raitt Hall 107

Speaker: Noam Berger (U. of California at Berkeley and Microsoft Research)

Title: Biased random walk on percolation clusters

Abstract: We study the behavior of the biased random walk on the infinite cluster of percolation in Z^2 (with high enough parameter). We get the seemingly surprising result that when the bias is big, the speed is zero while when the bias is small, the speed is positive. This is joint work with Nina Gantert and Yuval Peres.

Time: Monday, May 20, 2002 at 2:30 pm.

Location: Raitt Hall 107

Speaker: Renming Song (University of Illinois at Urbana-Champaign)

Title: Potential theory of subordinate killed Brownian motion in a domain

Abstract: Subordination of a killed Brownian motion in a domain $D\subset \R^d$ via an $\alpha/2$-stable subordinator gives a process $Z_t$ whose infinitesimal generator is $-(-\Delta|_D)^{\alpha/2}$, the fractional power of the negative Dirichlet Laplacian. In this talk we will present some results with Z. Vondracek on this process. We study the properties of the process $Z_t$ in a Lipschitz domain $D$ by comparing the process with the rotationally invariant $\alpha$-stable process killed upon exiting $D$. We show that these processes have comparable killing measures, prove the intrinsic ultracontractivity of the generator of $Z_t$, and, in the case when $D$ is a bounded $C^{1,1}$ domain, obtain bounds on the Green function and the jumping kernel of $Z_t$.

Time: Monday, May 13, 2002 at 2:30 pm.

Location: Raitt Hall 107

Speaker: Zhen-Qing Chen (University of Washington)

Title: Conditional gauge theorems and their characterizations

Abstract: Given a generator L of a Markov process X and a potential q, its associated conditional gauge function is the ratio of the Green functions for L+q and L respectively. The conditional gauge function can be represented probabilistically in terms of the conditional process of X and the Feynman-Kac functional of q. Conditional gauge theorem (CGT) says that under suitable conditions on L and q, the conditional gauge function is either bounded between two positive constants or identically infinity. CGT has been established for Laplacian (or equivalently for Brownian motion) in the 80's and for fractional Laplacian (or symmetric stable processes) in 97'.

In this talk I will present some recent progress in establishing CGT for (non-local) Feynman-Kac transforms for a large class of Markov processes. Results on analytic characterizations for the conditional gauge function to be bounded will be reported.

Time: Wednesday, May 8, 2001, 2002 at 2:30 p.m.

Location: Smith 305

Speaker: Elchanan Mossel (Microsoft Research)

Title: Some problems from biology

Abstract: I will discuss some probabilistic problems from biology that are mostly unstudied. I plan to discuss the following problems:

1. Determining keys sites in genes--Is Fourier analysis useful for non-product spaces?

2. A problem from phylogeny--how well do we understand branching processes?

3. Iterated prisoner dilemmas--can we prove that it's better to cooporate also on the lattice?

4. Crossover in genes and mixing times--a new card shuffling problem from biology.

Time: Monday, April 29, 2002 at 2:30 p.m.

Location: Raitt Hall 107

Speaker: Bela Bollobas (U. of Memphis and U. of Cambridge, visiting Microsoft Research)

Title: Bootstrap percolation on finite graphs

Abstract: A bootstrap percolation on a finite graph $G=(V,E)$ with (neighborhood) parameter $\ell$ is a nested sequence of subsets of $V$, $V_0 \subset V_1 \subset \dots $, such that for $t>0$ a vertex $v\in V$ belongs to $V_t$ iff either $v\in V_{t-1}$ or $v$ has at least $\ell$ neighbours in $V_{t-1}$. The set $V_t$ is the set of {\it sites occupied at time} $t$. Note that the entire percolation is determined by $V_0$, the set of sites occupied at time $0$. If eventually every site is occupied then we say that the starting set $V_0$ percolates. Choosing the vertices of $V_0$ at random, with probability $p$, we get a random bootstrap percolation with parameter $\ell$ and probability $p$. One of the main objects of study is the critical probability $p_c$, below which percolation is unlikely and above which it is very likely. In the talk, I shall review a number of the known results and shall report on my work in progress with Jozsef Balogh.

Time: Monday, April 22, 2002 at 2:30 p.m.

Location: Raitt Hall 107

Speaker: Krzysztof Burdzy (University of Washington)

Title: NEUMANN EIGENFUNCTIONS IN LIP DOMAINS

Abstract: A "lip domain" is a planar domain between the graphs of two Lipschitz functions whose Lipschitz constant is strictly less than 1. The second eigenvalue for the Laplacian in a lip domain with Neumann boundary conditions (i.e., the first non-zero eigenvalue) is simple. This implies that the strongest version of the "hot spots" conjecture holds for lip domains. Two conjectures of Jerison and Nadirashvili are special cases of the main result. This is joint work with Rami Atar.

Mathematics Department Colloquium :
Time: Tuesday, April 16, 2002 at 4:00 p.m.

Location: PDL C-36

Speaker: Weian Zheng (University of California, Irvine)

Title: Rate of Convergence in Homogenization of Parabolic PDEs

Abstract: We consider the solutions to ${\partial \over \partialt}u^{(n)}=a^{(n)}(x)\Delta u^{(n)}$ where $\{a^{(n)}(x)\}_{n=1,2,...}$ are random fields satisfying a ``well-mixing" condition (which is different to the usual ``strong mixing" condition). We estimate in this paper the rate of convergence of $u^{(n)}$ to the solution of a Laplace equation. Since our equation is of simple form, we get quite strong result which covers the previous homogenization results obtained on this equation.

Time: Monday, April 15, 2002 at 2:30 p.m.

Location: Raitt Hall 107

Speaker: Weian Zheng (University of California, Irvine)

Title: Discretizing a Backward Stochastic Differential Equation

Abstract: Given a probability space $(\Omega , F,P).$ Let $W_t$ be a standard Brownian motion with $(F_t)\subset F$ as its natural filtration. Given any positive constant $T<\infty $ and a random variable $\xi \in F_T$. A backward stochastic differential equation is the equation $$ Y_t = \xi - \int_t^T f(Y_s,Z_s,s) ds -\int_t^T Z_s dW_s , $$ $$ where $Y_t$ and $Z_t$ are unknown predictable processes. We give a discretization approach to solve the above equation numerically. It is known that the solution to a backward stochastic PDE is related to a semi-linear deterministic PDE. Therefore our method also give a probability method to solve a class of semi-linear PDE.

Time: Monday, April 8, 2002 at 2:30 p.m.

Location: Raitt Hall 107

Speaker: Fabio Machado (Microsoft Research and University of Sao Paulo, Brazil)

Title: Phase transition for the frog model

Abstract: We study a system of simple random walks on graphs, known as {\it frog model}. This model can be described as follows: There are active and sleeping particles living on a graph~$G$. Each active particle performs a simple random walk at discrete time. Each active particle dies after a random life time $ T $. When an active particle hits a sleeping particle, the latter becomes active. Active particles move independently. At time zero there is only one active particle on $G$ placed at its root. Phase transition results and asymptotic values for critical parameters are presented for $Z^d$ and regular trees.

Time: Wednesday, March 13, 2002 at 2:30 p.m.

Location: THO 231

Speaker: Laszlo Lovasz (Microsoft Research)

Title: MINIMA OF RANDOM LINEAR FUNCTIONS

Abstract: Let us assign independent, exponentially distributed random edge lengths to the edges of an undirected graph. Lyons, Pemantle and Peres proved that the expected length of the shortest path between two given nodes is bounded from below by the resistance between these nodes, where the resistance of an edge is the expectation of its length. This inequality can be formulated as follows: the expected length of a shortest path between two given nodes is the expected minimum of a stochastic linear program over a flow polytope, while the resistance is the minimum of a convex quadratic function over the same polytope. The inequality between these quantities holds true for an arbitrary polytope provided its blocker has integral vertices. There are several other combinatorial polytopes for which the convex quadratic function has a combinatorial meaning: for example, it can be related to hitting times of random walks and to modeling trafic congestion.

Time: Wednesday, March 6, 2002 at 2:30 p.m.

Location: MLR 316

Speaker: Alan Stacey (Cambridge University)

Title: PARTIAL IMMUNIZATION PROCESSES

Abstract: Partial Immunization Processes generalize the well-known contact process. The rate at which a site is infected can depend on whether or not the site has been previously infected, representing the fact that once a site has been infected and recovered it may be somewhat immunized against future infection or, perhaps, may be more susceptible to future infection. These processes can exhibit a phase of weak survival -- where the process survives but drifts off to infinity -- even on lattices where the contact process does not exhibit such behaviour. A conjecture is proved characterizing the strong survival phase on hypercubic lattices. Processes on trees are also studied and the phase diagram turns out to be rather rich; proofs of results on trees utilize a detailed analysis of the behaviour of the contact process on finite trees.

Time: Monday, February 25 at 2:30 p.m.

Location: MEB 237

Speaker: Itai Benjamini (Weizmann Institute and Microsoft Research)

Title: GLOBAL INFORMATION FROM LOCAL OBSERVATIONS

Abstract: We will discuss a few examples in which random processes are used to extract information on the underlying structure.

Time: Wednesday, February 20, 2002 at 2:30 p.m.

Location: THO 231

Speaker: Paul Shields

Title: RECURRENCE REVISITED

Abstract: The time for an initial k-block to appear again in an ergodic, finite-alphabet process and related waiting time problems will be discussed. I will review results I talked about a couple of years ago for the general case, then discuss the problem of when such recurrence (and or waiting) times have an asypmtotic exponential distribution, with a focus on recent results of Miguel Abadi and some conjectures.

Time: Monday, February 11, 2002 at 2:30 p.m.

Location: MEB 237

Speaker: Chris Hoffman (University of Washington)

Title: MIXING TIME FOR BIASED CARD SHUFFLING

Abstract: Consider a deck of $n$ cards labeled 1 through $n$. We employ the following biased shuffling. At each stage we pick a pair of adjacent cards uniformly at random. Then with probability $p>.5$ we replace the cards with the lower numbered card before the higher numbered card. With probability $1-p$ we replace the cards with the higher numbered card first. We prove that the mixing time for this system is $O(n^2)$. This proves a conjecture of Diaconis and Ram. This is joint work with Itai Benjamini, Noam Berger, and Elchanan Mossel.

Time: Monday, February 4, 2002 at 2:30 p.m.

Location: MEB 237

Speaker: Yevgeniy Kovchegov (Stanford University)

Title: BROWNIAN BRIDGE IN PERCOLATION AND RELATED PROCESSES

Abstract: Consider a $d$-dimensional model of a sub-critical bond percolation and a point $(a_1,a_2,...,a_d)$ in $Z^d$. The behavior of the cluster $C_a$ connecting points $(0,...,0)$ and $n(a_1,...,a_d)$ conditioned on the two points being connected is studied. An interesting result linking the asymptotic of the cluster $C_a$ (as $n\to\infty$) to that of Brownian Bridge is discovered.

Time: Monday, January 28, 2002 at 2:30 p.m.

Location: MEB 237

Speaker: Bruce Erickson (University of Washington)

Title: EXISTENCE OF IMPPROPER INTEGRALS WITH LEVY INTEGRATORS AND EXPONENTIAL LEVY INTEGRANDS

Abstract: We determine conditions under which an improper stochastic integral $\int_0^\infty f_s \exp(-\xi_{s-})d\eta_s $ converges, a.s., where $(\xi,\eta)$ is a two dimensional L\'{e}vy process and $f$ is a bounded non-anticipating functional of (\xi,\eta). In the case $f = 1$ we show that our conditions become necessary if in addition the support of the two-dimensional L\'{e}vy measure of the process does not lie in a one-dimensional curve of the form $\{(x,y) : y + k\exp(-x) = k \}$ for any real number $k$.

Time: Wednesday, January 23, 2002 at 2:30 p.m.

Location: THO 231

Speaker: Fabio Martinelli (University of Rome)

Title: RELAXATION TIME FOR ASYMMETRIC SIMPLE EXLUSION MODELS

Abstract: We analyze the relaxation time (inverse of the spectral gap) for a class of reversible asymmetric simple exclusion models. The latter can be viewed as n independent simple random walks with drift in some finite subgraph of $Z^d$ that avoid each other. We will also briefly mention the connection of the above problem with certain quantum spin models. Joint work with P. Caputo (Rome).

Time: Monday, January 14, 2002 at 2:30 p.m.

Location: MEB 237

Speaker: Takashi Kumagai (Kyoto University)

Title: FUNCTION SPACES AND STOCHASTIC PROCESSES ON FRACTALS

Abstract: Since the late 80's of the last century, there has been a lot of development in the mathematical study of stochastic processes and the corresponding operators on fractals. On the other hand, there has been intensive study of Besov spaces, (which are roughly speaking, fractional extensions of Sobolev spaces) on $d$-sets, which correspond to regular fractals. In this talk, we summarize recent work to connect these two areas and introduce local and non-local Dirichlet forms whose domains are Besov spaces. As an application, we will introduce diffusion processes on fractal fields, a collection of fractals, of in general different Hausdorff dimensions, embedded in Euclidean spaces.

Time: Wednesday, January 9, 2002 at 2:30 p.m.

Location: Smith 304

Speaker: Bernard Sapoval (Ecole Polytechnique, Palaiseau)

Title: LAPLACIAN TRANSPORT TO AND ACROSS IRREGULAR SURFACES: FROM ELECTRODES TO MAMMALIAN LUNGS

Abstract: Several phenomena in physics, chemistry and biology, can be brought to a single mathematical problem: transport across a "resistive" irregular surface driven by Laplacian fields. This includes charge transfer in batteries, species transfer in catalysts or molecular transfer across membranes. The mathematical problem is that of the properties of the solutions of Laplace equation with Fourier (or Robin) boundary conditions. We give an approximate way to treat this question and compare with experiments. We then introduce the more fundamental mathematical object, namely the Brownian self-transport operator, which governs this type of phenomenon.

Time: Monday, December 3, 2001 at 2:30 p.m.

Location: SMI 307

Speaker: Panki Kim (UW)

Title: Green Function Estimates and Martin Boundary of Censored Stable Processes

Abstract: For $\alpha \in (0, 2)$, a censored $\alpha$-stable process $Y$ in an open set $D$ is a process obtained from a symmetric $\alpha$-stable L\'evy process by restricting its L\'evy measure to $D$. It is recently known that when $D$ is a bounded Lipschitz open set, $Y$ is transient if and only if $\alpha>1$. In this talk, we will present sharp two-sided estimates for Green functions of censored $\alpha$ stable process $Y$ in a bounded $C^{1,1}$ open set $D$ for $1<\alpha<2$. The Martin boundary theory for $Y$ and for processes obtained from $Y$ through Feynman-Kac transformations with discontinuous additive functionals will also be discussed.

This talk is based on a joint work with Zhen-Qing Chen.

Time: Monday, November 26, 2001 at 2:30 p.m.

Location: SMI 307

Speaker: David Wilson (Miscrosoft Research)

Title: Critical Resonance in the Non-intersecting Lattice Path Model

Abstract: We study the phase transition in the honeycomb dimer model (equivalently, monotone non-intersecting lattice path model). At the critical point the system has a strong long-range dependence; in particular, periodic boundary conditions give rise to a ``resonance'' phenomenon, where the partition function and other properties of the system depend sensitively on the shape of the domain. Joint work with Richard Kenyon.

Time: Monday, November 19, 2001 at 2:30 p.m.

Location: SMI 307

Speaker: Youngmee Kwon (UW and Hansung University, Korea)

Title: On the blow up phenomena before crash

Abstract: We consider jump processes as bubble and crash models of stock price. The jumps of the processes are interpreted as crashes and we assume that there are only downward jumps with size a fixed fraction of the current price. Moreover, we assume that the jump intensity is a nondecreasing function of the current price or the bubble size, say $\lambda(p)$ ($p=p(t)$: price). Through this setting, we are able to put the endogenous variables into consideration.

For the case of $\lambda(p)=p^{\alpha}, \alpha>0$, we show that the price $p$ should explode in finite time, say $t_e$, conditional on no crash. This implies that the crash should occur before $t_e$, since the jump intensity tends to infinity as $p$ explodes. Also, for the case of $\lambda(p)=(\ln p)^{\alpha}$, we show that $\al =1$ is the borderline of two different classes of the processes. In fact, the price $p$ explodes in finite time if $\alpha>1$ and grows super exponentially but never explodes in finite time if $0<\alpha\leq 1$. We generalize the model by adding Brownian noise and examine the blow up properties of the sample paths. It turns out that the noise has much influence on determining the crash time. Finally, we calculate the crash time distribution of the above endogenous models explicitly.

Time: Monday, November 5, 2001 at 2:30 p.m.

Location: SMI 307

Speaker: Steffen Rohde (UW)

Title: Basic properties of SLE

Abstract: This talk is about Oded Schramm's Stochastic Loewner Evolution SLE, which can be thought of as a random family of compact sets in the plane. SLE has played a crucial role in some recent spectacular results in probability theory, most notably the proof of Mandelbrots conjecture about the dimension of the Brownian frontier (Lawler-Schramm-Werner) and Smirnov's result about scaling limits of critical percolation. In this talk, I will review definitions, some of these results, and then discuss some path properties of SLE (joint work with Oded Schramm).

Mathematics Department Colloquium
Time: Tuesday, October 23, 2000 at 4:00 p.m.

Location: PDL C-36

Speaker: Rodrigo Banuelos (Purdue University)

Title: Generalized Isoperimetric Inequalities

Abstract: The rearrangement inequalities for multiple integrals of H.S. Brascamp, E.H. Lieb, and J.M. Luttinger provide a powerful and elegant method for proving many of the classical geometric and physical isoperimetric inequalities for regions in Euclidean space. These include, amongst others, the classical isoperimetric inequality, the Rayleigh--Faber--Krahn inequality for the lowest eigenvalue of regions of fixed volume, isoperimetric inequalities for the trace of the Dirichlet heat kernel, and the Polya--Szego isoperimetric inequality for electrostatic capacity. After discussing some of these classical results, we will present new versions of multiple integral inequalities from which other ``generalized" isoperimetric inequalities for heat kernels of Schrodinger operators follow. Besides being of independent interest, such ioperimetric inequalities for heat kernels imply sharp inequalities for the lowest eigenvalue and the spectral gap of the Dirichlet Laplacian in certain convex regions of fixed diameter and fixed inradius (radius of largest ball in the region). In particular, these results improve the spectral gap bounds of I.M. Singer--B.Wang--S.T.Yau-- S.S.T.Yau and prove some special cases of a conjecture of M. van den Berg (Problem #44 in Yau's 1990 ``open problems in geometry") on the size of the spectral gap.

This talk is particularly designed for a general audience. We will discuss results, show some pictures, but provide as few technicalities as possible.

Time: Monday, October 22, 2001 at 2:30 p.m.

Location: SMI 307

Speaker: Rodrigo Banuelos (Purdue University)

Title: Space-Time Brownian martingales and $L^p$ Inequalities for $\partial$ and ${\overline \partial}$

Abstract: We will discuss some applications of martingales to some open problems concerning $L^p$ inequalities between $\partial f$ and ${\overline\partial} f$ and their connections to singular integral operators. More precisely, consider the following conjecture of T. Iwaniec (1982): Let $1 < p < \infty$ and set $p^*=\max\{p, q\}$ where $q$ is the conjugate exponent of $p$. For $f\in W^{1, p}(C, C)$ the following inequality should be true:
$$ \|{\overline\partial} f\|_p\leq (p^*-1)\|{\partial} f\|_p. (*} $$
This conjecture has been of considerable interest because of its many applications to quasiconformal mappings and to the regularity of solutions to some nonlinear PDE's. The conjecture is equivalent to an estimate on the norm of the Beurling-Ahlfors operator (a singular integral in the complex plane). Until recently the best known estimates for (*) were those obtained by the speaker and G. Wang ($\|{\overline\partial} f\|_p\leq 4(p^*-1)\|{\partial} f\|_p $) in 1995 using martingale inequalities and stochastic integration. Recently (in 2000) Nazarov and Volberg improved the estimate by a factor of 2. In this talk we will explain how the same stochastic analysis techniques used in the paper with Wang can be use to obtain the Nazarov-Volberg estimate and to provide some additional information on this conjecture.

Time: Monday, October 15, 2001 at 2:30 p.m.

Location: SMI 307

Speaker: Ross Maller (University of Western Australia)

Title: Stability of Perpetuities

Abstract: For a series of randomly discounted terms (a generalised ``perpetuity'') we give an integral criterion to distinguish between almost-sure absolute convergence and divergence in probability to $\infty$. These turn out to be the only possible forms of asymptotic behaviour. This settles the existence problem for a one-dimensional perpetuity, and yields a complete characterization of the existence of distributional fixed points of a random affine map in dimension one. As an application, conditions for stability of the ARCH(1) and GARCH(1,1) processes used in financial data modelling will be given. Some possible extensions (Levy Processes) will be briefly outlined.

Time: Monday, October 8, 2001 at 2:30 p.m.

Location: SMI 307

Speaker: Zhen-Qing Chen (University of Washington)

Title: Censored Stable Processes

Abstract: In this talk we will discuss a new topic in boundary potential theory for discontinuous Levy processes. We will present several constructions of a ``censored stable process'' in an open set $D$ in $R^n$, i.e., a symmetric stable process which is not allowed to jump outside $D$. We will address the question of whether the process will approach the boundary of $D$ in a finite time. Sharp conditions will be given for such boundary approach in terms of the stability index $\alpha$ and the ``thickness'' of the boundary. As a corollary, new results are obtained concerning Besov spaces on non-smooth domains, including the critical exponent case. If time permits, a boundary Harnack principle in $C^{1,1}$ open sets will also be presented, as well as results about the decay rate of the corresponding harmonic functions which vanish on a part of the boundary.
This talk is based on a joint work with K. Bogdan and K. Burdzy.

Time: Monday, September 10, 2001 at 2:30 p.m.

Location: Padelford C401

Speaker: Yukio Ogura (Saga University, Japan)

Title: Completion of a Class of One-dimensional Diffusion Processes

Abstract: We are concerned with a class of one-dimensional diffusion processes (ODP) on an interval $I$ associated with the Dirichlet forms ${\cal E}(u,u) =\int_I|u'|^2 \varphi dx$ on $L^2(\varphi dx)$ with $\varphi\in C^\infty(I)$ (in other words, distorted processes), and seek a condition for its precompactness in some sense. An elemet of the closure is no longer an ODP in general, but is a system of bi-generalized diffusion processes which were introduced by the speaker in 1989. There are abundant examples including the class of $\{\varphi_n\}$ of positive $C^\infty$ functions on $I=[0,l]$ such that $\varphi_n(x) = 1$ for $x\in [0,a_{0,n}]\cup [b_{k,n},l]$, $x = a_{i,n}$ or $x = b_{i,n}$, $\lim_n\int_{a_{i,n}}^{b_{i,n}}\varphi_n dx =\alpha_i\in(0,\infty]$, and $\lim_n\int_{b_{i,n}}^{a_{i+1,n}} 1/\varphi_n dx =\beta_i\in(0,\infty]$, for $i=0,1,\ldots,n-1$, where $0 This is a joint work with Takashi Shioya and Matsuyo Tomisaki.

Time: Monday, August 27, 2001 at 2:30 p.m.

Location: Padelford C401

Speaker: Zhi-Ming Ma (Academia Sinica, Beijing)

Title: SOME RECENT RESULTS ON PROBEBILITY THEORY

Abstract: In this talk I present some new results on Probability Theory in which I have recently been involved. It will involve the following topics.
Dirichlet forms and stochastic analysis on configuation spaces.

The property of Markove processes in Shiga model of infinite particle systems.

The study of uncountable independent random variables and its application to economic systems.

A new type of measure valued processes associated with stochastic flows

Time: Wednesday, May 30, 2001 at 2:30 p.m.

Location: RAI 109

Speaker: Itai Benjamini (Weizmann Institute and Microsoft Research)

Title: PERCOLATION ON GRAPHS

Abstract: A review of percolation on graphs will be presented. One point is to see how coarse geometric properties of the underling graphs manifests themself in the behaviour of the percolation process. Several problems will be mentioned.

Time: Monday, May 21, 2001 at 2:30 p.m.

Location: MLR 302A

Speaker: Ron Getoor (University of California, San Diego)

Title: GENERATORS AND SCHRODINGER EQUATIONS ASSOCIATED WITH MARKOV PROCESSES

Abstract: Let G be the generator of a nice Markov process. Then

(*) (G+p)u = f

is called the Schroedinger equation with potential p. If p and f are reasonable functions a solution u may be expressed using the Feynman-Kac formula. Recently there has been much interest in the situation in which p is a measure. It then seems natural to extend the domain of G so that it maps functions to measures and interpret (*) as an equation between measures where the right hand side is regarded as fm with m a given background measure--Lebesgue measure in classical cases. In this talk I will try to motivate and describe informally with as few technicalities as possible the definition of the extended generator. I will indicate some results for (*) and discuss the case f = 0 when the solutions are called p-harmonic.

Time: Monday, May 14, 2001 at 2:30 p.m.

Location: MLR 302A

Speaker: Siva Athreya (University of British Columbia)

Title: UNIQUENESS FOR DEGENERATE STOCHASTIC DIFFERENTIAL EQUATIONS AND SUPER-MARKOV CHAINS

Abstract: We will consider diffusions corresponding to the generator $$ L f(x) = \sum_{i=1}^d x_i \gamma_i(x)\frac{\partial^2} {\partial{x_i}^2}f(x) + b_i(x) \frac{\partial}{\partial{x_i}}f(x),$$ $x \in [0,\infty)^d,$ for continuous $\gamma_i, b_i : [0,\infty)^d \rightarrow \bR$ with $\gamma_i$ nonnegative. Our aim will be to establish uniqueness for the corresponding martingale problem under certain non-degeneracy conditions on $b_i, \gamma_i$. We will begin by briefly explaining the motivation for studying such diffusions, followed by a discussion on why standard techniques fail and conclude with a brief description of the proof.

This is joint work with Martin Barlow, Richard Bass, and Edwin Perkins.

Time: Wednesday, May 7, 2001 at 2:30 p.m.

Location: MLR 302A

Speaker: Zhenqing Chen (University of Washington)

Title: DRIFT TRANSFORMATION AND GREEN FUNCTION ESTIMATE FOR DISCONTINUOUS PROCESSES

Abstract: In this talk we will discuss processes obtained from symmetric stable processes in bounded domains through pure jump Girsanov transform and Feynman-Kac transform, which include relativistic stable processes. We show that when pure jump transform does not amplify small jumps of stable process too much and the potential in Feynman-Kac transform is not too large, the Green function of perturbed process is comparable to that of symmetric stable process. This result is obtained by first establishing a conditional gauge theorem for discontinuous additive functionals, and is in fact valid for more general processes. As an application, we obtain that the Green functions for the relativistic stable processes in bounded smooth domains are comparable to that of symmetric stable processes, which recovers the recent result of Ryznar.

Time: Wednesday, May 2, 2001 at 2:30 p.m.

Location: RAI 109

Speaker: Krzysztof Burdzy (University of Washington)

Title: BROWNIAN MOTION REFLECTED ON BROWNIAN MOTION

Abstract: It is not hard to define one-dimensional Brownian motion reflected on an independent one-dimensional Brownian path. I will discuss some path properties of the reflected process and the joint distribution of the two processes. If time permits, I will present a connection with the heat equation, some proofs and an open problem. This is joint work with David Nualart.

Time: Monday, April 16, 2001 at 2:30 p.m.

Location: MLR 302A

Speaker: Bruce Erickson (University of Washington)

Title: RENEWAL AND OTHER LIMITS FOR SOME SEQUENCES OF RANDOM AFFINE MAPS (PART II)

Abstract: Markov chains defined by random iteration of independent identically distributed maps acting on some space has always been a popular object of study. Of particular interest are chains $\{X_n\}$ of the form: $X_0\in R^d$, $X_n = A_nX_{n-1} + B_n$ where $\{(A_n,B_n)\}$ are independent and identically distributed, with values in $M(d)\times R^d$, $M(d)$ the square matrices of size $d$. An even more popular subset of these objects is the case that each $A_n$ is a random postive multiple of the identity. I will discuss a few more or less recent results, including some rather intricate, but quite interesting ones by Babillot, Bougerol, \& Elie dealing with the asymptotics of the potential kernel (or, if you prefer, the translates of the renewal measure) for the joint chain: $(X_n, \Pi_n)$, $\Pi_n = A_nA_{n-1} \cdots A_1 a$.

Time: Monday, April 9, 2001 at 2:30 p.m.

Location: MLR 302A

Speaker: Federico Marchetti (Politecnico di Milano)

Title: SPLITTING FREE LUNCHES: FINANCIAL MODELS WITH BOUNDARY CONDITIONS

Abstract: Dirichlet boundary conditions are easily handled in financial models (e.g. in down-and-out barrier options). Boundary reflections are not as acceptable, since they prevent the existence of an equivalent martingale measure and thus lead to arbitrage. We look at a few examples where they might nonetheless be used and suggest how a "fair price" interval (much as in an incomplete market) could be introduced. It should also be noted that the arbitrage opportunities in these models are illusory, since they disappear as soon as transaction costs are included.

Time: Monday, April 2, 2001 at 2:30 p.m.

Location: MLR 302A

Speaker: Bruce Erickson (University of Washington)

Title: RENEWAL AND OTHER LIMITS FOR SOME SEQUENCES OF RANDOM AFFINE MAPS

Abstract: Markov chains defined by random iteration of independent identically distributed maps acting on some space has always been a popular object of study. Of particular interest are chains $\{X_n\}$ of the form: $X_0\in R^d$, $X_n = A_nX_{n-1} + B_n$ where $\{(A_n,B_n)\}$ are independent and identically distributed, with values in $M(d)\times R^d$, $M(d)$ the square matrices of size $d$. An even more popular subset of these objects is the case that each $A_n$ is a random postive multiple of the identity. I will discuss a few more or less recent results, including some rather intricate, but quite interesting ones by Babillot, Bougerol, \& Elie dealing with the asymptotics of the potential kernel (or, if you prefer, the translates of the renewal measure) for the joint chain: $(X_n, \Pi_n)$, $\Pi_n = A_nA_{n-1} \cdots A_1 a$.

Time: Monday, March 5, 2001 at 2:30 p.m.

Location: SMI 111

Speaker: Omer Angel (Microsoft Research)

Title: Random Triangulations

Abstract: Planar triangulations have been studied for separate reasons by mathematiciens (Tutte counted them in 62) and physicists (in the context of quantum gravity). I prove that the uniform measure on random triangulations of the plane with $n$ vertices converge as $n \to \infty$ to some limit distribution of infinite planar triangulations. Some geometric properties of the infinite object are discussed and it is shown to be recurrent.

Time: Monday, February 26, 2001 at 2:30 p.m.

Location: SMI 111

Speaker: Jon A. Wellner (UW)

Title: Some functionals of Brownian motion connected with estimation of montone and convex functions

Abstract: Estimation and testing problems for monotone functions in ``Gaussian white noise'' lead to several interesting functions of two-sided Brownian motion $W$ plus a parabola: the slope process of the greatest convex minorant is now well-understood, thanks to the work of Groeneboom (1983), (1989). In particular, the distribution of the slope process at $0$, say $Z_0$, has been computed analytically and numerically in Groeneboom (1985) and Groeneboom and Wellner (2001). In recent work with Moulinath Banerjee, we have found that the analogue of a chi-square distribution in regular problems is played by the distribution of $$ Z_1 \equiv \int \{ S (t)^2 - S^0 (t)^2 \} dt $$ where $S $ is the slope process of the greatest convex minorant of $W(t) +t^2$ and $S^0$ is the slope process of the one-sided greatest convex minorants constrained to be greater than or equal to zero to the right of zero, and constrained to be less than or equal to zero to the left of zero. An analytical description of the distribution of $Z_1$ is still unknown.

For estimation of a convex function in Gaussian white noise, the maximum likelihood estimator turns out to be the second derivative of a certain ``invelope'' of integrated (two-sided) Brownian motion plus $t^4$. The value $Z_2$ of this second derivative at zero describes the limiting distribution in statistical problems of interest. Almost nothing is known about the distribution of $Z_2$.

I will discuss some of the statistical background for these problems and some of the many open questions.

Time: Friday, February 16, 2001 at 2:30 p.m.

Location: SMI 107 (Note unusal date and location)

Speaker: Jim Fill (The Johns Hopkins University)

Title: PERFECT SAMPLING: A TALE OF TWO ALGORITHMS

Abstract: In Markov chain Monte Carlo (MCMC), one samples approximately from a probability distribution $\pi$ of interest by (1) designing an ergodic Markov chain X whose stationary distribution is $\pi$ and (2) using X(t), with t suitably large, as an observation approximately from $\pi$. But in practice it is often impossible to determine how large is "suitable" for t.

In the last six years, widely (though not universally) applicable algorithms have been devised that overcome this problem by using the basic mechanisms of MCMC to sample perfectly from $\pi$. The two most widely applied are coupling from the past, due to Jim Propp and David Wilson, and an algorithm (called FMMR) based on rejection sampling, developed by the speaker and extended with coworkers.

I will review these two algorithms, discuss their original (monotone) settings, and explain how the use of so-called bounding processes and dominating processes extends their ranges of applicability. Along the way, we shall see that there is a simple, previously unnoted, connection between the two algorithms. If time permits, I either will discuss the application of perfect simulation to a distribution arising in the probabilistic analysis of the algorithm "Quickselect" for finding order statistics in an unordered file, or else will discuss how judicious choice of a certain user-supplied parameter (namely, the initial state) can lead to (sometimes dramatic) speedup of FMMR.

(This talk will be based on joint work with Moto Machida, Duncan Murdoch, and Jeff Rosenthal, and on joint work with Bob Dobrow.)

On Monday February 19, 2001, Jim Fill will give a talk at Microsoft Research, titled `` THE RANDOMNESS RECYCLER: A NEW TECHNIQUE FOR PERFECT SAMPLING". The following is the abstract of that talk.

For many probability distributions of interest, it is quite difficult to obtain samples efficiently. Often, Markov chains are employed to obtain approximately random samples from these distributions. The primary drawback to traditional Markov chain methods is that the mixing time of the chain is usually unknown, which makes it impossible to determine how close the output samples are to having the target distribution. Here we present a new protocol, the randomness recycler (RR), that overcomes this difficulty. Unlike classical Markov chain approaches, an RR-based algorithm creates samples drawn exactly from the desired distribution. Other perfect sampling methods such as coupling from the past use existing Markov chains, but RR does not use the traditional Markov chain at all. While by no means universally useful, RR does apply to a wide variety of problems. In restricted instances of certain problems, it gives expected linear time algorithms for generating samples. I will discuss how RR applies to self-organizing lists, the Ising model, random independent sets, random colorings, and the random cluster model. (This talk will be based on joint work with Mark Huber.)

Time: Monday, February 12, 2001 at 2:30 p.m.

Location: BAG 331A (Note unusal location)

Speaker: Laszlo Lovasz (Microsoft Research)

Title: A refined conductance bound on mixing times and sampling from convex bodies

Abstract: To get sharp bounds on the mixing times of a large variety of finite Markov chains is an important issue for many applications in computer science, physics, etc. One very successful technique to prove rapid mixing of Markov chains, introduced by Jerrum and Sinclair, is the use of "conductance". However, the bound on the mixing time in terms of the conductance, involves also the logarithm of the smallest stationary probability. This factor, sometimes called the "start penalty", is often an artifact of the proof: if we know better bounds on the conductance of small sets, than we can reduce it. Several techniques have been proposed to do so, most notably the "log-Sobolev" inequalities by Diaconis and Saloff-Coste. We prove a new inequality that bounds the mixing time in terms of a weighted average, where conductances of small sets get larger weights. We show various applications of this new inequality; in particular, one gets a new bound on the mixing time of the random walk in a d-dimensional convex body (with ball steps), which is optimal in terms of the diameter. This requires a new isoperimetric inequality for small subsets of a convex sets. Joint work with Ravi Kannan from Yale.

Time: Monday, February 5, 2001 at 2:30 p.m.

Location: SMI 111

Speaker: Federico Marchetti (UW and Politecnico di Milano)

Title: QUEUES WITH COMPETING ARRIVALS (II)

Abstract: Diffusion limits for queuing systems in "heavy traffic" promise to provide tractable models for important questions in queuing applications where different arrival streams compete for limited resources. We will illustrate some early results and some suggestions for further research. The models that arise involve mainly reflecting diffusions, both as descriptive models and as tools for possible optimal control questions.

Time: Monday, January 22, 2001 at 2:30 p.m.

Location: SMI 111

Speaker: Zhen-Qing Chen (UW)

Title: Conditional Gauge Theorem

Abstract: When $X$ is a Brownian motion and $D$ is a bounded smooth domain, it is known that under certain condition on potential $q$, function $u(x, y)=E_x^y[ \exp(\int_0^{\tau_D} q(X_s)ds)]$ is either identically infinity or is bounded on $D\times D$. This result is called conditional Gauge theorem. In this talk we will show that above theorem holds for a large class of processes, including processes with jumps. The significance of the conditional gauge function $u$ is that it is the ratio of the Green function for Schrodinger operator $L+q$ in $D$ and the Green function for $L$ in $D$, where $L$ is the generator of process $X$.

Time: Monday, January 8, 2001 at 2:30 p.m.

Location: SMI 111

Speaker: Chris Burdzy (UW)

Title: The supremum of Brownian local times on H\"older curves

Abstract: For $f: [0,1]\to \R$, let $L^f_t$ be the local time of space-time Brownian motion on the curve $f$. Let $\sS_\al$ be the class of all functions whose H\"older norm of order $\al$ is less than or equal to 1. We show that the supremum of $L^f_1$ over $f$ in $\sS_\al$ is finite if $\al>\frac12$ and infinite if $\al<\frac12$.

Joint work with R.~Bass.

Time: Monday, November 20, 2000 at 2:30 p.m.

Location: EEB 216

Speaker: Marek Biskup (Microsoft Research)

Title: LONG-TIME TAILS FOR DIFFUSIONS IN RANDOM MEDIA: PARABOLIC ANDERSON MODEL WITH BOUNDED POTENTIALS

Abstract: I will describe the long-time behavior of the solution to a parabolic second-order differential problem with a random i.i.d. potential. In the literature, this problem appears under the name "parabolic Anderson model," referring to the Anderson Hamiltonian which is widely studied in the context of disordered quantum systems. I will show that the leading order asymptotic of the moments of the solution as well as the solution itself can be described in terms of variational principles. As an application, the Lifshitz tails for the spectrum of the associated Schroedinger operator with random i.i.d. potential can be explicitly computed. The Lifshitz exponent varies between half spatial dimension and infinity, depending on the upper tail of the potential distribution. The main tools of the proof are the Feynman-Kac formula and estimates for principal eigenvalues. The results extend various findings about the "simple random walk among Poissonian obstacles" obtained by Sznitman and his school in the 1990s.

Jointly with Statistics
Time: Monday, November 13, 2000 at 3:30 p.m.

Location: COM 120

Speaker: Krzysztof Burdzy (University of Washington)

Title: REMARKS ON THE PHILOSOPHY OF BAYESIAN DECISION MAKING

Abstract: I will present a thought experiment showing that a Bayesian decision maker is forced in some circumstances to identify himself with an abstract group of people (as opposed to a real group). The analysis showing sub-optimality of the Bayesian decision will be made from the frequentist point of view. If time permits, I will discuss an unstated axiom in Bayesian textbook examples and its practical applications. The axiom is far from obvious and thus destroys the claim of the Bayesian approach to be based on an axiomatic system.

The talk will be partly based on the notes available at http://www.math.washington.edu/~burdzy/Bayes/welcome.html .

Time: Monday, November 6, 2000 at 2:30 p.m.

Location: EEB 216

Speaker: Elchanan Mossel (Microsoft Research)

Title: GLAUBER DYNAMICS AND THE ISING MODEL ON THE TREE

Abstract: Glauber dynamics on finite graphs are used in order to sample Markov chains such as the Ising model and random colorings.

We will recall the classical picture of the Ising model on Z^2 where in the uniqueness phase, the spectral gap is bounded away from zero, while in the non-uniqueness phase, the spectral gap decays exponentially in the diameter of squares. In recent years, effort was devoted to generalize this equivalence.

By studying these dynamics on trees, we will show that for general graphs this equivalence doesn't hold. We will show that bounded spectral-gap implies in general a property (*) of the Gibbs measure. Moreover, for trees and Z^2, the spectral-gap is bounded if and only if (*) holds.

Based on a joint work with Claire Kenyon and Yuval Peres.

Time: Monday, October 30, 2000 at 2:30 p.m.

Location: EEB 216

Speaker: Federico Marchetti (Politecnico di Milano)

Title: FINITE-BUFFER QUEUES: ALLOCATING LOSSES AMONG COMPETING INCOMING FLOWS IN HEAVY TRAFFIC

Abstract: Routers and switches provide finite buffers for incoming traffic and packet losses will occur. It does make a difference whose packets get lost, especially because different flows will work under different protocols and react differently to losses. Overall network efficiency might be affected depending on the protocol. Keeping track of packet labels poses no problem (in principle), but the heavy traffic (diffusion) limit of the loss processes is less obvious. We discuss some preliminary analysis of this limit.

Time: Tuesday, October 24, 2000 at 2:30 p.m.

Location: LOW 222

Speaker: Itai Benjamini (Weizmann Institute of Science and Microsoft Research)

Title: GEOMETRIC RANDOM GRAPHS

Abstract: I will present several results regarding the geometric structure of various models of random graphs, and the behavior of random walk on these graphs.

University of Washington Walker-Ames Lecture
Time: Wednesday, October 18, 2000 at 7:00 p.m.

Location: Kane 210

Speaker: Persi Diaconis (Stanford University)

Title: On coincidences

Abstract: Coincidences amaze us. I will review early work by Jung and Freud and also show how sometimes a bit of quantitative thinking can show that things aren't so surprising after all.

A reception will follow the lecture at the lobby.

Departments of Mathematics and Statistics Joint Colloquium
Time: Tuesday, October 17, 2000 at 4:00 p.m.

Location: MLR 301

Speaker: Persi Diaconis (Stanford University)

Title: What do we know about the metropolis algorithm?

Abstract: The metropolis algorithm is one of the most widely used tools of 20th century scientific computing. I will explain the algorithm, illustrate its use in cryptography and chemistry and describe new geometric tools for bounding rates of convergence.

A reception will be held at Faculty club after the colloquium.

Seminar on Mathematical Education

(sponsored by The University of Washington Teaching Academy, The Department of Statistics, The Department of Mathematics, and the Center for Quantitative Science)
Time: Tuesday, October 17, 2000 at 12:30 p.m.

Location: Anderson 22

Speaker: Susan Holmes (Stanford University)

Title: Probability by Surprise: the pleasure of paradoxes

Abstract: Probability by Surprise: Teaching with Paradoxes

The main idea is to unify the presentation of probability to a heterogenous audience through the interest we have in things that surprise us. Some examples we use in our probability classes include: 'the birthday problem', 'say red', 'russian roulette', 'de Mere's problem', 'Monty Hall'.

The tools developed are based on discoveries by cognitive pyschologists (in particular Tversky and Kanneman) over the last 20 years, that have not, as yet, been used in teaching probability in this country. The programs include simulation programs to give students a feel for probability, animated scenarios to help motivate and amuse them, as well as to make the material more memorable.

The project weaves together an "Introduction to Probability'' web-site including: - links to useful existing calculus material such as explanations of integration and summing rules. - interactive Venn diagrams, probability trees, densities as limits of histograms. - Relevant graphical animations written in java. - Historical material about probabilty. - Animations and simulations developed specifically. - Lists of team oriented project ideas that enable the students to try out their new computer simulation skills and compare these results to those of classical probabilistic analyses.

Joint Statistics and Biostatistics Seminar
Time: Monday, October 16, 2000 at 3:30 p.m.

Location: Communications 120

Speaker: Susan Holmes (Stanford University)

Title: Confidence Regions for Phylogenetic trees

Abstract: We consider a continuous space which models the set of all phylogenetic trees having a fixed set of leaves. This space has a natural metric of nonpositive curvature, giving a way of measuring distance between phylogenetic trees and providing some procedures for averaging or combining several trees whose leaves are identical. This geometry also shows which trees appear within a fixed distance of a given tree and enables construction of convex hulls of a set of tree

This geometric model of tree space provides a setting in which questions that have been posed by biologists and statisticians over the last decade can be approached in a systematic fashion. For example, it provides a justification for disregarding portions of a collection of trees that agree, thus simplifying the space in which comparisons are to be made.

New types of confidence statements are made possible in this cube complex.

(Coffee/Tea and Cookies in the Statistics Lounge after the seminar)

Time: Monday, October 16, 2000 at 2:30 p.m.

Location: MLR 301

Speaker: Persi Diaconis (Stanford University)

Title: Probability, statistics and the zeros of the zeta function.

Abstract: Random matrix theory uses the eigenvalue distribution of typical, large matrices to model natural phenomena. I will show that these models give remarkable fits to a large real data set (50,000 zeros of Riemanns zeta function). This opens up new problems in testing goodness of fit with dependent data.

Time: Monday, October 9, 2000 at 2:30 p.m.

Location: EEB 216

Speaker: Lisa Korf (University of Washington)

Title: PRICING CONTRACTS CONTINGENT ON A MARKET: A STOCHASTIC PROGRAMMING PERSPECTIVE

Abstract: The classical fundamental theorem of asset pricing, and its variants, say in essence that a market is arbitrage free if and only if there is an equivalent probability measure with respect to which the market price process is a martingale. The fair price of a financial instrument, i.e. the minimum initial investment in the market that permits replication of the instrument, may then be computed as an expectation of the contracted payouts of the instrument with respect to such a measure. When this problem of pricing contracts contingent on a market is cast in a stochastic programming setting, it opens up the possibility to analyze (and solve) much more complex problems than would be considered in the classical setting. Duality plays a central role. Some of the key features that come out of this approach will be presented.

Time: Monday, October 2, 2000 at 2:30 p.m.

Location: EEB 216

Speaker: Hong Qian (University of Washington)

Title: THE MATHEMATICAL THEORY OF SINGLE MOLECULES AS A MECHANICAL ENGINE

Abstract: A single molecule of a protein can move, along its designated track, against external applied force in aqueous solution. This process is the physical basis of the cellular movement which leads to many aspect of biological motion, for example, muscle contraction and wound healing. We will introduce this fascinating phenomenon and its mathematical model in terms of a set of coupled diffusion process. Some unsolved mathematical issues will be discussed.

Time: Wednesday, May 31, 2000 at 2:30 p.m.

Location: Smith 115

Speaker: S\"onke Lorenz (Freie Universit\"at Berlin and University of Washington)

Title: TRANSFER OPERATOR APPROACH TO CONFORMATIONAL DYNAMICS IN BIOMOLECULAR SYSTEMS

Abstract: In my talk, I am going to present the development of novel mathematical concepts and algorithmic approaches that result in modelling long-term behavior of biomolecular systems by applying conformational dynamics.

Both, a first deterministic approach, based on the Frobenius-Perron operator corresponding to the flow of the Hamiltonian dynamics, and later stochastic approaches, based on a spatial Markoff operator and on Langevin dynamics, can be subsumed under the unified mathematical roof of the transfer operator approach to effective dynamics of molecular systems.

At the end, I plan to illustrate the concept by numerical results.

Joint work with Christof Sch\"utte, Wilhelm Huisinga and Peter Deuflhard from the Freie Universit\"at Berlin und the Konrad-Zuse-Zentrum Berlin (ZIB).

Time: Monday, May 15, 2000 at 2:30 p.m.

Location: Smith 115

Speaker: Bruce Erickson (University of Washington)

Title: A LIMIT THEOREM FOR IMBEDDED REGENERATIVE SETS (Continued)

Abstract: See previous one

Mathematics Department Colloquium
Time: Tuesday, May 23, 2000 at 4:00 p.m.

Location: PDL C-36

Speaker: Michael Cranston (University of Rochester)

Title: Dispersion of stochastic flows

Abstract: A problem in statistical fluid mechanics is to determine how fast a pollutant (passive tracer) will spread. We will discuss some models of motion of so-called 'passive tracers' and give some results on how far they might travel in a given amount of time. In one model each passive tracer undergoes a Brownian motion and the Brownian motions experienced by different tracers will have a given correlation. In another model the tracers move according to a random velocity field. This is the model given by Kolmogorov. The results in each case are similar and maybe a little surprising.

Time: Monday, May 22, 2000 at 2:30 p.m.

Location: MEB 250

Speaker: Katalin Marton (R\'enyi Institute, Hungary)

Title: The "transportation cost" method to prove measure concentration

Abstract: The concentration of measure phenomenon, in product spaces, means the following: If a subset $A$ of the $n$'th power of a probability space $\Cal X$ has not too small probability then very large probability is concentrated on a small neighborhood of $A$. The neighborhood is, understood, e.g., with respect to Hamming distance.

A few years ago, M. Talagrand's work put measure concentration in the focus of attention of many people, proving a variety of interesting inequalities and showing lots of applications.

In this talk we show how to prove measure concentration by bounding some distance between probability measures, (e.g., $\bar d$-distance) in terms of the relative entropy of these measures. This method can be used to prove measure concentration for dependent random variables (or random fields) under the assumption that the given ensemble of random variables satisfies a strong mixing condition, in the sense of Dobrushin and Shlosman.

Mathematics Department Colloquium
Time: Tuesday, May 9, 2000 at 4:00 p.m.

Location: Thomson 125

Speaker: R. J. Williams (University of California, San Diego)

Title: Dynamic control of stochastic networks in heavy traffic

Abstract: Stochastic networks are used as models for complex manufacturing, telecommunications and computer systems. Some of these networks allow for flexible scheduling of jobs through dynamic (state-dependent) alternate routing and sequencing, hereafter collectively referred to as dynamic scheduling. Usually these models cannot be analyzed exactly, and it is a challenging problem to design dynamic scheduling policies for such networks that are simple to implement and yet are approximately optimal in an appropriate sense. As one approach to this problem, J. M. Harrison proposed the use of Brownian control problems (BCPs) as formal heavy traffic approximations to dynamic scheduling problems for stochastic networks. This talk will survey developments in the application and justification of this approach.

Time: Monday, May 8, 2000 at 2:30 p.m.

Location: MEB 250

Speaker: Bruce Erickson (University of Washington)

Title: A LIMIT THEOREM FOR IMBEDDED REGENERATIVE SETS

Abstract: If ${\bf R}\subset [0,\infty)$ denotes a closed unbounded random set of points and $Z_t(\omega) = 1_{{\bf R}(\omega)}(t)$ is the process of indicators, then ${\bf R}$ is a {\it regenerative set} if for any ${\bf F}_t\equiv\sigma\{Z_s, s\le t\}$--stopping time $T$ with $P\{T\in {\bf R}\} = 1$, the subset ${\bf R}\circ\!\theta_T = \{ s : s +T\in {\bf R}\}\cap [0,\infty)$ is independent of ${\bf F}_T$ and has the same law as ${\bf R}$. When the regenerative set is discrete, there exists a unique renewal process $S = \{S_n\}_{n\in N}$ such that ${\bf R} = S$. (A renewal proces is a sequence of partial sums of non-negative i. i. d. random variables: $S_k = \xi_1 + \cdots + \xi_k$.)

The familiy of random variables $$ A_t = \inf\{ s \ge 0 : t-s \in {\bf R} \}, \quad t \ge 0, $$ is called the {\it age process} (or ``spent waiting time at epoch $t$'').

In the discrete, non-lattice case, if the renewal jumps have finite mean, $m$, then the Markov process $A_t$ has a limit distribution (for $t \to \infty$) and the limit distribution has density: $\,m^{-1}P\{\xi > x\}\,\hbox{d}x$. This is a consequence of the strong renewal theorem.

If $m=\infty$, then $A_t/t$ has a non-trivial limit distribution if and only if $\xi$ belongs to the domain of attraction of a positive stable law. This result is due to Lamperti and, independently, Dynkin. The limit is a ``beta'' type distribution. (Note that the age process at time $t$ is bounded by $t$ and this fact combined with certain properties of regular varying functions show that the Dynkin-Lamperti result has the equivalent formulation: $A_t/t$ converges in distribution iff $E\{A_t\}/t$ has a limit in $(0,1)$.)

I will discuss a generalization, due to J. Bertoin, of the Lamperti-Dynkin result in the case of a finite sequence of embedded discrete regenerative sets. Naturally, I will have to tell you the meaning of the latte

Time: Monday, April 24, 2000 at 2:30 p.m.

Location: MEB 250

Speaker: Krzysztof Bogdan (Technical University of Wroclaw and UW)

Title: ON SCHR\"ODINGER TYPE OPERATORS BASED ON FRACTIONAL LAPLACIAN (continued)

Abstract: We will discuss weakly and strongly harmonic functions for Feynman-Kac semigroups corresponding to symmetric stable processes. Based on the properties of the weak Schr\"odinger operator we will then give examples of the gauge function for bounded Green domains. Larger domains, like half-lines, will be also mentioned in the context of the Kelvin transform.

Time: Monday, April 17, 2000 at 2:30 p.m.

Location: MEB 250

Speaker: Wenbo Li (University of Delaware)

Title: CAPTURE TIME OF BROWNIAN PURSUITS

Abstract: Let $B_0, B_1, \cdots, B_n$ be independent standard Brownian motions, starting at $0$. Define the stopping time $$ \tau_n = \inf \{ t > 0: B_i (t) -1 = B_0 (t) \; for some \; 1 \le i\le n \}. $$ A proof of the fact that $E \tau_3 =\infty$ and $E \tau_5 < \infty$ will be presented, along with various related problems.

Time: Monday, April 10, 2000 at 2:30 p.m.

Location: MEB 250

Speaker: Krzysztof Bogdan (Technical University of Wroclaw and UW)

Title: ON SCHR\"ODINGER TYPE OPERATORS BASED ON FRACTIONAL LAPLACIAN

Abstract: We will discuss some elements of the potential theory of Feynman-Kac semigroups corresponding to symmetric stable processes. We will focus on problems related to gaugeability and existence of $q$-harmonic functions.

Time: Monday, April 3, 2000 at 2:30 p.m.

Location: MEB 250

Speaker: Ron Pyke (University of Washington)

Title: ON RANDOM WALKS AND DIFFUSIONS RELATED TO PARRONDO'S GAMES

Abstract: Consider playing a seguence of simple games, with $X_n$ denoting the gain (or loss) from the $n$-th game. If $S_n = X_1+\cdot \cdot \cdot +X_n$ is the player's capital after $n$ games, we say that the game is winning/losing/fair according as $S_n/n$ converges $a.s.$ to a positive/negative/zero limit. In a recent series of papers, G. Harmer and D. Abbott study the behavior of random walks associated with games introduced in 1997 by J. M. R. Parrondo. These games illustrate an apparent paradox that random and deterministic mixtures of losing games may produce winning games. In this talk, classical cyclic random walks on the additive group of integers modulo $m$, a given integer, are used in a straightforward way to derive the strong law limits of a general class of games that contains the Parrondo games. We then consider the question of when random mixtures of fair games related to these walks may result in winning games. Although the context for these problems is elementary, there remain open questions. An extension of the structure of these walks to a class of shift diffusions is also presented, leading to the fact that a random mixture of two fair shift diffusions may be transient to $+\infty$.

Time: Tuesday, March 14, 2000 at 2:30 pm.

Location: PDL C-36

Speaker: Tadeusz Kulczycki (Technical University of Wroc\l aw)

Title: Intrinsic ultracontractivity for symmetric stable processes

Abstract: I will talk about intrinsic ultracontractivity (IU) for the semigroup $P_{t}^{D}$ generated by the symmetric $\alpha$-stable process "killed" on exiting an open set $D$ with finite Lebesgue measure. Intrinsic ultracontractivity has been extensively studied in the case of the Brownian motion. IU gives pointwise estimates of consecutive eigenfunctions by the first one and is equivalent to parabolic boundary Harnack principle.

The main result states that if $D$ is a bounded open set then $P_{t}^{D}$ is IU. I am also going to talk about IU for some unbounded open sets D.

Time: Monday, March 7, 2000

Location: Raitt 109

Speaker: Bert Schreiber (U of Washington and Wayne State U.)

Title: From Stationary to Nonstationary Processes on Groups: How Can We Extend the Spectral Analysis?

Abstract: The classical theory of stationary random processes and fields is founded upon the fact that the covariance function of such a field has an associated spectral measure. The talk will focus on several approaches to dealing with classes of nonstationary processes and fields. The classes we will discuss all have elements with some sort of spectral decomposition and all contain the stationary fields. First we will recall two types of harmonizable processes. The first class is defined by a direct extension of the spectral representation for stationary processes. The second type of harmonizable process involves a similar but much broader notion of spectral representation, which we will describe.

Next we will introduce a class of processes and fields called asymptotically stationary. For many processes that arise in the real world, it is the discrete spectrum that is of primary interest, the continuous spectrum being attributable to "noise." We will describe a recent result of L. Hanin and the speaker which provides a consistent statistical estimator for the coefficients of the discrete part of the associated spectral measure.

Time: Monday, February 28, 2000

Location: Raitt 109

Speaker: Minping Qian (University of Southern California and Beijing University)

Title: The Metastability Behavior of Markov Chains and Diffusion--A Large Deviation Consideration

Abstract: For a Markov chain, suppose it has transition probability prooportional to $ exp(-bH(x)) $ for very large $b$. As $b$ goes to infinite, this process may not be irreducible, its state space can divided into several parts, each part has its recurrent core (we say attractor). The limit may be degenerated to deterministic processes, if we restrict it in recurrent cores. These subspace of recurrent cores , are metastability sets (or points).There is a hierarchical structure in these subspaces. The path of original processes has a kind of special behavior moving in this hierarchical structure. This understanding has important application in Markov Monte Carlo, simulated annealing and other stochastic algorithms. This kind of structure can also be found for diffusions and nonsymmetric Markov processes.

Time: Wednesday, February 23, 2000

Location: THO 211

Speaker: Tusheng Zhang (UC Irvine and HIA in Norway)

Title: On the Small Time Large Deviations of Diffusion Processes on Hilbert Spaces

Abstract: In this talk, I will present results on the following small time large deviations of Varadhan type $$\lim_{t\rightarrow 0} 2t log P(X_0\in A, X_t\in B)=-d^2(A,B)$$ for diffusions on Hilbert spaces, which particularly includes solutions of SPDEs.

Time: Monday, February 14, 2000 at 2:30 pm.

Location: Raitt 109

Speaker: Bruce Erickson (University of Washington)

Title: The collection of recurrent (or transient) subsets for normal walks on Z^d (d >2) is independent of the walk

Abstract: This will be a continuation of my talk on February 7. A normal random walk on Z^d is one with an aperiodic step distribution which has mean (vector) 0 and finite variance.

Time: Monday, February 7, 2000 at 2:30 pm.

Location: Raitt 109

Speaker: Bruce Erickson (University of Washington)

Title: Some Recent Results in the Potential Theory of Normal Random Walks in Z^d.

Abstract: A normal random walk is one whose step distribution is aperiodic and has mean (vector) 0, and whose step length has a finite 2nd moment. This talk will be a brief report on some recent ('96 to '98) results due, mainly, to K. Uchiyama on the potentials of such walks. What is (mildly) surprising is that some of the consequences of this work had not already been established 35 years ago when this sort of thing was getting much greater attention.

By the way, the term ``normal'' is not normal. But it does make titles to talks a little more normal in size. Moreover, a normal random walk is in the domain of normal attraction of a normal distribution!

Time: Monday, January 31, 2000 at 2:30 pm.

Location: Raitt 109

Speaker: Christopher Hoffman (University of Washington)

Title: Simple Random Walk on Percolation Clusters

Abstract: Consider an infinite percolation cluster in Z^d. We perform simple random walk on this graph. We obtain bounds on the probability that simple random walk started at vertex at x at time 0 returns to x at time t. This is a joint work with Debby Heicklen.

Time: Tuesday, January 25, 2000 at 2:30 pm.

Location: RAI 116

Speaker: Michiel van den Berg (University of Bristol, UK)

Title: Heat Flow, Area and Capacity for Regions with Many Small Holes

Abstract: We consider the heat flow from a compact set K in euclidean space R^m if K is kept at fixed temperature 1 while R^m - K has initial temperature 0. We obtain estimates for the total heat content in R^m - K at time t as t goes to 0 in the special case where K is an infinite union of closed non-intersecting balls.

Time: Wednesday, January 19, 2000 at 2:30 pm.

Location: CMU 230

Speaker: Rick Durrett (Cornell University)

Title: Single Nucleotide Polymorphims in the Human Genome: How many are there? How many will Celera find?

Abstract: Single nucleotide polymorphisms (SNP's) are useful markers for locating genes since they occur throughout the human genome and thousands can be scored at once using DNA microarrays. Here, we use branching processes and coalescent theory to show that if one assumes a mutation rate of 5 x 10^{-9} per nucleotide per generation then there are 2.8 million SNP's in the human genome, or one every 1,063 base pairs. We further predict that Celera's strategy for sequencing the human genome will uncover 1.8 million variable nucleotides but that in only about 72% of these cases will the most common allele have a frequency of less than 99%. This means, however, that they will find approximately 45% of the SNP's in the human genome. The predicted numbers are of course proportional to the assumed mutation rates but the percentage estimates are independent of it.

Time: Monday, January 10, 2000 at 2:30 pm.

Location: RAI 109

Speaker: Zhen-Qing Chen (University of Washington)

Title: Strong Solutions of Stochastic Differential Equations for Dirichlet Processes and Pathwise Uniqueness

Abstract: Strong solution and pathwise uniqueness for stochastic differential equations (SDE) related to second order non-divengence form differential operator is well studied. It is an open question whether there is a strong solution for "SDE" related to second order divergence form differential operator with non-Lipschitz coefficients. In this talk, we will present some recent results on the existence of strong solution and pathwise uniqueness for one dimensional
1) SDE where the drift term is a signed measure,
2) SDE related to divergence form operator,
3) Stratonovitch SDE,
as well as some non-existence and non pathwise uniqueness results.
This talk is based on a joint research project with Rich Bass.

Time: Monday, November 22, 1999 at 2:30 p.m.

Location: THO 231

Speaker: Krzysztof Burdzy (University of Washington)

Title: SONIC BOOM FOR THE HEAT EQUATION

Abstract: Encyclopaedia Britannica has this to say about ``sonic boom,'' among other things: ``As the aircraft proceeds, the trailing parabolic edge of that cone of disturbance intercepts the earth, producing on earth a sound of a sharp bang or boom--with silence before and after.'' I will show that the heat equation may display a similar behavior in a time-variable domain. This is the fourth talk in a series on the heat equation and reflected Brownian motion in time-dependent domains. The previous three talks were given by the co-authors---Zhenqing Chen and John Sylvester.

Time: Monday, November 15, 1999 at 2:30 p.m.

Location: THO 231

Speaker: Federico Marchetti (Politecnico di Milano)

Title: EVALUATING STOCHASTIC ALGORITHMS

Abstract: For a convergent stochastic algorithm, the last entrance time into a prescribed neighborhood of the limit, seems a more meaningful parameter than, for instance, the first entrance time. To illustrate this point, we look at scaling properties and other features that are of interest in this application, for some simple cases, and suggest further lines of investigation.

Joint work with P. Glynn, Stanford.

Time: Monday, November 8, 1999 at 2:30 p.m.

Location: THO 231

Speaker: Yimin Xiao (Theory Group, Microsoft)

Title: LEVEL SETS OF ADDITIVE LEVY PROCESSES

Abstract: Let $X = \{ X(t); t \in {\bf R}^N_+ \}$ be an additive L\'evy process in ${\bf R}^d$. We show that the hitting probabilities of the level sets of $X$ are related to a class of natural capacities on ${\bf R}^N_+$.

We also present several probabilistic applications of the aforementioned potential--theoretic connections. They include areas such as intersections of L\'evy processes and level sets, as well as Hausdorff dimension computations.

Joint work with Davar Khoshnevisan.

Time: Monday, November 1, 1999 at 2:30 p.m.

Location: THO 231

Speaker: Zhenqing Chen (University of Washington)

Title: REFLECTING BROWNIAN MOTION IN TIME-VARYING DOMAIN AND ITS ASSOCIATED PDE (PART II)

Abstract: In this talk, I will first review reflecting Brownian motion in a time-varying domain that I discussed in the first talk. Then I will present its various properties and connections with PDE's, including various probabilistic representation for solutions to heat equation with a moving insulated boundary. Both one and higher dimensional cases will be considered. This is a part of a joint research project with Chris Burdzy and John Sylvester.

Time: Monday, October 25, 1999 at 2:30 p.m.

Location: THO 231

Speaker: K.B. Erickson (University of Washington)

Title: SOME PROBLEMS IN SINGULAR BRANCHING BROWNIAN MOTION

Abstract: A Brownian particle with initial position $\,a\,$ moves for a random time $\tau$ with conditional distribution depending on the path. At this time the particle splits in two. The new particles, given their initial position, $X_\tau$, are mutually independent and are governed by the same distributional laws as their parent. Etc. As time goes by, we get an increasing number of not quite independent Brownian particles. If $\#(t;I)$ denotes the the number of particles in $\,I\,$ at time $t$ and if the death rate has a particular form, one finds that $\#(t;I)< \infty$ for all $t$ with probability 1, but that $E^a \#(t;I) = \infty\, $ for all initial positions $a$ and all $t$ sufficiently large. One interesting question concerns the rate of growth of the spread of the process. Specifically, if $z(t)$ is the position of the right-most particle at time $t$, $z(t)=\max\{ b:\#(\, t; \, \ico{b}{\text{$\infty$}}\,) \neq 0 \} $, and $z_+(t) = \max(\, z(s);\, s \le t)$, then $z_+(t) \uparrow \infty$, but what is the rate of increase of $z_+(t)$ ?

(Joint with COMPLEX ANALYSIS SEMINAR)

Time: October 19, 1999 at 1:30 p.m.

Location: PDL C-401

Speaker: Balint Virag (University of California, Berkeley)

Title: BROWNIAN BEADS

Abstract: Two-dimensional stochastic models are of great interest to physicists and probabilists because they reflect, perhaps more than any other mathematical object, the rich world of conformal symmetries.

We consider perhaps the simplest one of these models, 2D Brownian motion. Two and three are the only dimensions where Brownian motion has interesting cut-times, that is times at which past and future paths are disjoint. Brownian beads are the sections of the path in between the cut-times. We show that these beads are in some sense independent of each other and 2D Brownian motion is stringed out of them just as 1D Brownian motion is built out of excursions.

As an application, we give a heuristic explanation for some conjectured formulas of Duplantier, Lawler and Werner about intersection exponents for planar Brownian motion.

Time: Monday, October 18,, 1999 at 2:30 p.m.

Location: THO 231

Speaker: Zhenqing Chen (University of Washington)

Title: REFLECTING BROWNIAN MOTION IN TIME-VARYING DOMAIN AND ITS ASSOCIATED PDE

Abstract: In this talk, I will describe a diffusion process associated with the heat equation with a moving insulated boundary which John Sylvester discussed in our last probability seminar. This process is a reflecting Brownian motion in a time-varying domain. I will present results on existence and uniqueness of such processes. I will also discuss their various properties and connections with PDE's. Both one and higher dimensional cases will be considered. This is a part of a joint research project with Chris Burdzy and John Sylvester.

Time: Wednesday, October 13, 1999 at 2:30 p.m.

Location: THO 134

Speaker: John Sylvester (University of Washington)

Title: A HEAT EQUATION WITH A MOVING INSULATED BOUNDARY

Abstract: In recent conversations with Chris Burdzy and Zhen-Qing Chen, we have found that analysts and probabilists ( at least this analyst and those probabilists) have quite different perspectives on the process of diffusion. I will present an elementary description, from an analysts point of view, of how one formulates the boundary value problem alluded to in the title, and the estimates one must obtain to prove existence and uniqueness.

Time: Monday, October 4, 1999 at 2:30 p.m.

Location: THO 231

Speaker: Krzysztof Burdzy (University of Washington)

Title: SYNCHRONOUS COUPLINGS IN NON-CONVEX DOMAINS

Abstract: Consider two Brownian particles trapped in a domain, i.e., consider two reflected Brownian motions. Suppose that they move in a synchronous way if both are away from the boundary. It is easy to see that the distance between the particles will go to $0$ if the domain is convex. Is this also true in non-convex domains? (Joint work with Z.-Q. Chen.)

Time: Wednesday, Septemeber 29, 1999 at 2:30 p.m.

Location: SMI 113

Speaker: Michal Karonski (Adam Mickiewicz University, Poznan, Poland)

Title: PHASE TRANSITION IN RANDOM GRAPHS AND HYPERGRAPHS

Abstract: The talk gives an overview of the basic ``epochs'' in the evolution of random graphs and hypergraphs. Special attention is given to the phase transition phenomenon. In particular, we present recent joint results with Tomasz Luczak on the phase transition in a random $d$-uniform hypergraph and the size of its largest component in the sub- and supercritical phases.

Time: Thursday, August 19, 1999 at 2:30 p.m.

Location: RAI 109

Speaker: Yuval Peres (University of California, Berkeley)

Title: PERCOLATION IN A DEPENDENT RANDOM ENVIRONMENT

Abstract: Draw planes in $R^3$ that are orthogonal to the $z$ axis, and intersect that axis at the points of a Poisson process with intensity $\lambda$; similarly, draw planes orthogonal to the $x$ and $y$ axes using independent Poisson processes (with the same intensity) on these axes. This yields a randomly stretched rectangular lattice. Consider bond percolation on this lattice where each edge of length $\ell$ is (independently) open with probability $e^{-\ell}$. We show that this model exhibits a phase transition: For large enough $\lambda$, there is an infinite open cluster a.s., and for small $\lambda$, all open clusters are finite a.s. (The question whether the analogous process in two dimensions exhibits a phase transition is open.) We prove this result using the method of `Paths With Exponential Intersection Tails'; This method yields a proof of phase transition for a large class of percolation processes in random environment in dimension $d \geq 3$.

Joint work with Johan Jonasson and Elchanan Mossel.

Time: Wednesday, August 11, 1999 at 2:30 p.m.

Location: Smith 109

Speaker: Itai Benjamini (Weizmann Institute)

Title: GEOMETRIC EMBEDDINGS AND PROBABILITY

Abstract: We will present several loosely related results regarding coarse geometric embeddings, mostly of graphs. We apply probabilistic, geometric and potential-theoretic arguments. Joint work with Oded Schramm.

Time: Tuesday, July 27, 1999 at 2:30 p.m.

Location: Smith 111

Speaker: Siva Athreya (University of British Columbia)

Title: THE DUALITY METHOD FOR VARIOUS MARTINGALE PROBLEMS

Abstract: Duality is a useful tool in showing uniqueness and other properties for solutions of martingale problems. We shall begin with a basic review of the method and then move onto applications with special emphasis on uniqueness issues for solutions of certain Stochastic differential equations and SPDE's.

This is joint work with Roger Tribe.

Time: Wednesday, June 2, 1999 at 2:30 p.m.

Location: Smith 311

Speaker: Paul Shields

Title: Why should a probabilist care about ergodic theory?

Abstract: One result from ergodic theory sometimes used, implicitly or explicitly, by probabilists is the ergodic theorem. Many also know about the Ornstein isomorphism theory, but as far as I know no probabilist has made use of it. I would like to discuss a recent application of isomorphism theory to an approximate-match waiting-time question, a question that probabilists might find of interest or even use someday. (In fact, some of what I discuss can be viewed as a generalized form of Talagrand's "new view of independence.")

Time: Wednesday, May 26, 1999 at 3:30 p.m.

Location: Smith 107

Speaker: ROBERT ADLER (Technion)

Title: SOME INTERACTING SUPERPROCESSES

Abstract: The talk will focus on some new perturbations of basic superprocess, generally involving highly singular self-interactions.

Abstract for the non-initiate (for whom the talk is really intended): The talk will be composed of four parts;

1: A brief introduction to superprocesses at the level of systems of branching, moving, particles. (For which you have to know only what Brownian motion is.)

2: An explanation of 2-3 ways of introducing smooth interactions (between particles) into the system. (For which you have to either watch my hands or read stochastic PDE's.)

3: A divergence into how to look at highly local interactions between two Brownian motions, and an explanation of what this has to do with Burgers' equation. (Including an explanation of what this equation is and why it is interesting.)

4: A discussion of a superprocess based on the above non-linear interaction, which turns out to be the same as looking at Burgers' equation with a random forcing term, and why this is interesting.

Time: Tuesday, May 25, 1999 at 3:30 p.m.

Location: Smith 205

Speaker: ROBERT ADLER (Technion)

Title: TWENTY FIVE YEARS LATER

Abstract: In 1973 and 1974 Ron Pyke published two review papers, one entitled "Partial sums of matrix arrays, and Brownian sheets" and the other "Multidimensional empirical processes: some comments". Both not only surveyed the literature of the time, but also posed a number of problems, which, with hindsight, set the scene for frenetic research activity that has continued to this day.

While it would be impossible to summarise all of this activity in one hour, or even to cover Ron's own contributions to the area, I will describe a number of the developments that would seem to be of widest interest. In particular, I will present some rather enticing problems in the random geometry generated by multi-parameter stochastic processes of both theoretical and applied interest.

(Remark: The talk is a part of Ron Pyke's retirement celebration.)

Time: Monday, May 10, 1999 at 2:30 p.m.

Location: LOW 216

Speaker: Kathy Temple (University of Washington)

Title: DIFFUSION-LIMITED AGGREGATION

Abstract: Diffusion-Limited Aggregation, or DLA, is a very simple process to describe but extraordinarily difficult to analyze. This talk will present the model and review a few known results about DLA.

Time: Monday, April 26, 1999 at 2:30 p.m.

Location: LOW 216

Speaker: Rajesh Nandy (University of Washington)

Title: A BRIEF REVIEW OF QUANTUM STOCHASTIC CALCULUS (continued)

Abstract: The basic integrator processes of Quantum Stochastic Calculus are introduced in appropriate Hilbert Space. Also the Quantum Ito Formula is described. Relevant examples will be given as well.

Time: Monday, April 19, 1999 at 2:00 p.m.

Location: LOW 216

Speaker: Richard M. Karp (University of Washington)

Title: Algorithms for Graph Partitioning on the Planted Partition Model

Abstract: The NP-hard graph bisection problem is to partition the nodes of an undirected graph into two equal-sized groups so as to minimize the number of edges that cross the partition. The more general graph k-partition problem is to partition the nodes of an undirected graph into k equal-sized groups so as to minimize the total number of edges that cross between groups.

We present a simple, linear-time algorithm for the graph k-partition problem and analyze it on a random ``planted'' k-partition model. In this model, the n nodes of a graph are partitioned into k groups, each of size n/k; two nodes in the same group are connected by an edge with some probability $p$, and two nodes in different groups are connected by an edge with some probability $r < p$. We show that if $p-r is sufficiently large then the algorithm finds the optimal partition with high probability. Joint work with Anne Condon of the University of Wisconsin.

Time: Monday, April 5, 1999 at 2:30 p.m.

Location: LOW 216

Speaker: Zhen-Qing Chen (University of Washington)

Title: Green function and Poisson kernel estimates for symmetric stable processes

Abstract: In this talk, we will present some new two-sided estimates for Green functions, Poisson kernels and Martin kernels of discontinuous symmetric $\alpha$-stable process in bounded $C^{1,1}$ open sets. The new estimates give explicit information on how the comparing constants depend on parameter $\alpha$ and consequently recover the Green function and Poisson kernel estimates for Brownian motion by passing $\alpha$ to 2.

Time: Wednesday, March 3, 1999 at 2:30 p.m.

Location: CMU B006

Speaker: Ron Pyke (University of Washington)

Title: ON THE SOLIDARITY OF RECURRENT MARKOV RENEWAL PROCESSES

Abstract: It is known that for a wide class of irreducible recurrent Markov Chains and Markov Renewal processes, the finiteness of the $p$-th moment of recurrence times is finite for one state if and only if it is finite for all states. This result also holds for a wide class of functionals of the processes between successive occurrence times. Such results are known as solidarity theorems. In this paper, a solidarity theorem is proved concerning the property of ``being in the domain of attraction of a stable law with specified parameters.'' A basic identity linking additive random functions determined by two distinct states is emphasized, and used to derive solidarity results for moments and for the WLLN.

Time: Wednesday, February 24, 1999 at 2:30 p.m.

Location: CMU B006

Speaker: Ron Pyke (University of Washington)

Title: REASSEMBLING OF SHATTERED BROWNIAN SHEET

Abstract: If $D_n:n\ge 1$ is a given countable collection of Borel subsets of the unit square $[0, 1]^2=I^2$ and $Z$ is a standard Brownian sheet over $I^2$, is it possible to reconstruct $Z$ from the knowledge of all of the patches $Z-c_n$ over transformed domains $\tau_n(D_n)$ for unknown constants $c_n$ and unknown rotation-translation transformations $\tau_n$? We show that the answer to this question is yes under fairly natural restrictions on the sets $D_n$. The main property of Brownian sheet that leads to this possibility is that the local behaviour of $Z$ around a point $\bt$ actually determines $\bt$. In this sense, a Brownian sheet carries with it its own location coordinates. An open problem exists when the fragments are rotated in their range space.

Mathematics Department Colloquium

Time: Tuesday, February 9, 1999 at 4:00 p.m.

Location: CMU 120

Speaker: Persi Diaconis (Stanford University)

Title: MATHEMATICS OF SOLITAIRE

Abstract: One of the embarrassment of applied probability is that we can not analyze the original game of solitaire. I will show that a simplified solitaire leads to fascinating mathematics and complete analysis. The mathematics involves combinatorics, random matrices, and Riemann-Hilbert theorem. This is a joint work with David Aldous.

This coloquium talk is accessible to general audience including undergraduate students.

Time: Tuesday, February 9, 1999 at 2:30 p.m.

Location: Padelford C-401

Speaker: Amir Dembo (Stanford University)

Title: THICK, THIN AND STICKY POINTS OF BROWNIAN MOTION

Abstract: We find the correct nondegenerate ``multifractal spectrum'' for Brownian occupation measure in ${\bf R}^d$, $d \geq 2$. It involves {\it thick points} $x$ for which the occupation measures of small balls (radius $r$) centered at $x$ are exceptionally large {\it for some} $r_n \downarrow 0$; {\it sticky points} having such a property {\it for all} $r \downarrow 0$ and {\it thin points} with exceptionally small occupation measures for some $r_n \downarrow 0$. As a by product we resolve problems posed by Taylor (1974) (for $d \geq 3$) and Perkins and Taylor (1987) (for $d=2$), as well as Erd\"{o}s and Taylor (1960) long standing open problem about favorite points for the simple random walk in ${\bf Z}^2$.

Our results are related to the LILs of Ciesielski \& Taylor (1962) and Ray (1963) for the Brownian occupation measure of small balls, in the same way that L\'{e}vy's uniform modulus of continuity, and the formula of Orey and Taylor (1974) for the dimension of {\it fast points}, are related to the usual LIL.

In the course of our work we provide a general framework for obtaining lower bounds on the Hausdorff dimension of random fractals of `limsup type'.

This talk is based on a joint work with Y. Peres, J. Rosen and O. Zeitouni.

Back to Probability Seminar Home Page