Past Probability Seminars Fall 2003
UW Math Probability Seminar Fall 2003
Thursdays in 901 Van Vleck Hall at 2:25 PM, unless otherwise noted.
Organized by [index.html Timo Sepp�l�inen ]
Schedule and Abstracts
|| Thursday, September 4 || || * Ellen Saada, * Universit� de Rouen || || * Abelian sandpile models in infinite volume * || || *Ellen Saada's seminar is cancelled * ||
Since its introduction by Bak,Tang and Wiesenfeld, the abelian sandpile dynamics has been studied extensively in finite volume. In a joint collaboration with C. Maes, F. Redig, A. van Moffaert, we investigate the existence of a sandpile dynamics in infinite volume, whose invariant distribution should be the thermodynamic limit (we also have to prove its existence) of the invariant measure for the finite volume dynamics. The crucial difficulty is the fact that the interaction is long range, so that no use of the usual Hille-Yosida machinery is possible. After a quick review of the involved results in finite volume, I will speak of the cases where we have completed this program: in dimension 1, on the infinite tree, and for dissipative systems.
|| Thursday, September 11 || || * Marton Balazs, * UW-Madison || || * Growth fluctuations in a class of stochastic deposition models * ||
In the talk, I introduce a wide class of stochastic deposition models. These models' growth can be used to describe the evolution of an infected area of plants, forest fires, etc. The wide class considered also serves as a general frame for several nearest-neighbor particle jump processes, e.g. the so-called simple exclusion or the zero range process. The rate of growth is easy to compute, the challenging problem is to find the fluctuation of the surface growing. This had been done earlier by Ferrari and Fontes for one of the most simple processes, namely, the simple exclusion. Generalizing their methods to less simple systems of our class requires new ideas. We first show how to make a stochastic coupling between two realizations of a process, and introduce the so-called second class particle as the object which traces the difference between the two processes. The second class particle has itself a highly nontrivial behaviour. We prove some of its properties, and use this result to compute the fluctuations of our models via some martingale arguments.
|| Thursday, September 18 || || * Elton Hsu, * Northwestern University || || * Mass Transportation and the uniqueness of Markov coupling of Euclidean Brownian motions * ||
A coupling of Brownian motion is maximal if it minimizes the coupling time of the coupling. We show that the mirror coupling is the unique maximal coupling for Euclidean Brownian motion. The problem is reduced to the coupling (or equivalently mass transportation) between two Gaussian distributions of the same variance.
|| Thursday, September 25 || || *Jim Propp, * UW-Madison || || *De-randomizing random walk and random aggregation * ||
This talk will describe a recipe for replacing certain sorts of stochastic processes by deterministic analogues that satisfy the same first-order limit laws but with smaller fluctuations.
For instance, the obvious way of estimating absorption probabilities for states in a Markov chain via simulation gives errors on the order of 1/sqrt(n) (where n is the number of trials). If instead of true random walk one uses "rotor-router walk", then in n consecutive trials one can obtain an estimate whose error is on the order of O(1/n). This is rigorously known for all finite graphs and some infinite graphs. It appears to hold for Z^2, but this has not been proved.
Another examples is given by internal diffusion-limited aggregation (IDLA). Lawler, Bramson and Griffeath showed that the shape of the growing IDLA blob converges in probability to a perfect disk. The fluctuations seem to be on the order of log n (Blachere proved they are no larger, and simulation suggests they are no smaller). A determinstic analogue of IDLA gives rounder disks, and I will try to convince you that it's not so crazy to think that the fluctuations for the deterministic model might be O(1). In any case, this determinstic process is a fascinating object in its own right: see http://www.math.wisc.edu/~propp/million.gif .
(Some of my work on derandomized random walk is joint with Ander Holroyd, and some of my work on derandomized aggregation is joint with Lionel Levine.)
|| Thursday, October 2 || || * Joshua Rushton, * UW-Madison || || * Functional laws of the iterated logarithm for alpha-stable L�vy processes * ||
Stable random variables are those whose distributions have domains of attraction. That is, those to which some sequence of i.i.d. random variables' (appropriately normalized and centered) partial sums converge in distribution. It turns out this class of distributions exhibits surprising regularity, allowing one to study many basic properties in full generality. In particular, for any stable random variable X_0, there is a unique L�vy process X (called a stable L�vy process) with X(1) ~ X_0. In this talk, I will discuss Strassen-type iterated logarithm laws for stable L�vy processes, and related iterated logarithm laws for the partial sum process with summands in the domain of attraction of a stable distribution.
|| Thursday, October 9 || || *Balaji Prabhakar, * Stanford University || || * The Parisi and Coppersmith-Sorkin conjectures for the finite random assignment problem * ||
Suppose that there are n jobs and n machines and it costs c(i,j) to execute job i on machine j. The assignment problem concerns the determination of a one-to-one assignment of jobs onto machines so as to minimize the cost of executing all the jobs. When the c(i,j) are independent and identically distributed exponentials of mean 1, Parisi has made the beautiful conjecture that the average minimum cost equals the sum of 1/i^2 over i=1,...,n.
Coppersmith and Sorkin have generalized Parisi's conjecture to the average value of the smallest k-assignment when there are n jobs and m machines. These conjectures have been open for some time now.
This talk outlines the resolution of these conjectures. As background, we shall survey approaches to the assignment problem from computer science, the replica method of statistical physics, and probability.
Joint work with Chandra Nair and Mayank Sharma.
|| Thursday, October 16 || || No seminar on account of the Midwest Probability Colloquium in Evanston, Illinois. ||
|| Thursday, October 23 || || * Jon Wellner, * University of Washington || || * Multiply Integrated Brownian Motion Plus Drift: Envelopes, Invelopes, and their Role in Shape-constrained Estimation * ||
[wellner-abs.pdf Abstract.]
|| Thursday, October 30 || || * Timo Sepp�l�inen, * UW-Madison || || * Phase transition behavior of disordered asymmetric exclusion * || || *Postponed to a later time * ||
In a disordered asymmetric exclusion process we give each particle its own jump rate, independently drawn from a distribution F. When F has a thin enough tail at its left end, the system has a critical density below which there are no equilibrium distributions. In this talk I will review what is known about this model and present some recent results obtained jointly with Ilie Grigorescu and Min Kang.
|| Thursday, November 6 || || * Scott Sheffield, * Microsoft Research || || * Crystal facets and the amoeba * ||
Why do crystals have facets? Why do the facets always rational slopes? What causes particular facets in an equilibrium crystal (e.g., certain surfactant and condensed helium crystals) to disappear and reappear when parameters (e.g., temperature) are changed?
In the real world, these questions are difficult to answer quantitatively. But for a certain class of random surface models (which arise as height functions of random perfect matchings of a weighted, bipartite doubly periodic graph G, embedded in the plane), we can precisely describe the facets that arise in the thermodynamic limit using an algebraic geometric construction called the amoeba. The slopes of these facets always lie in the dual of the lattice of translation symmetries of G; depending on the edge weights, some, none, or all of the possible facets may be present.
An ergodic Gibbs measure \mu on the space of perfect matchings of G is said to be a rough phase if, when two matchings chosen independently from \mu are superimposed, there are almost surely infinitely many cycles that surround the origin. If the origin is almost surely contained in only finitely many cycles, then \mu is smooth. We will see that crystal facets correspond to smooth phases. The criteria for the existence of smooth phases (and hence crystal facets) are surprisingly simple and can be stated in terms of the perfect matchings of a single period of G. One consequence of our analysis is that sampling a perfect matching from any rough phase is equivalent to constructing a spanning tree of a so-called T-graph using Wilsons algorithm and a zero-drift loop-erased random walk.
This talk is based on joint work with Rick Kenyon and Andrei Okounkov.
|| Thursday, November 13 || || * Michael Cranston, * University of Rochester || || * Some recent results on the parabolic Anderson model * || || *Seminar cancelled. Speaker's flight was delayed. * ||
The parabolic Anderson model refers to parabolic pdes of the form k\Delta u+ V u = u_t, where \Delta is the Laplacian on Z^d or R^d and V is a random potential. This equation models many phenomena such as entrapment of electrons in crystals with impurities (Anderson's original motivation), population dynamics with random births and deaths and magneto-hydrodynamics. It is also related by simple transformations to Burger's equations and to the KPZ equation for random surface growth. In this talk we shall discuss the asymptotic behavior of solutions of the equation for various choice of potential V . We shall show how they depend on the parameter k as k tends to 0. Traditionally, the equation has been considered over Z^d, but we will also discuss some results where the underlying state space is R^d.
|| Thursday, November 20 || || * Christine Jerritts, * University of Colorado || || * Optimal game theoretic strategies for winning a stochastic race * ||
A racecar driver's chance of being first across the finish line generally increases with the speed of her car. However, fuel consumption and accident risk also increase, thereby offsetting the advantage of the quicker pace alone. Thus an optimal strategy for winning a race must balance the risks and rewards of increased speed. We designed a mathematical framework for a _stochastic race_ in which players attempt to be the first to win n points in a sequence of rounds. In each round, racers independently choose the number of points k \le n they wish to attempt to win, which are then awarded to the racer with probability p(k). Since the function p is decreasing in k, a racer must weigh the benefits of increased speed, that is choosing large values k, with the risks of not moving at all as 1-p(k) gets close to 1. Our goal is to solve games of this type for various governing functions p and number m of racers. We describe optimal game theoretic strategies for winning the race under a range of conditions for 2 or 3 players, and some results are generalized to races with m players.
|| Thursday, November 27 || || Thanksgiving Break - No Seminar ||
|| Thursday, December 4 || || * David Quigg, * Bradley University || || * Excess capacity: a stochastic model * ||
Consider the economics of a hotel. It must fix its capacity, i.e. number of rooms, well in advance. Then the hotel must wait for a random number (which may depend on the price it had set) of prospective customers to arrive. If the number of customers is too low, the hotel has unfilled rooms, excess capacity. If the number of prospective customers is too high, all the rooms are filled and there is excess, unfilled demand.
We construct and analyze a model in which demand is random and investigate the effect of uncertainty upon price and capacity.
(1) For a fixed capacity, what price should the hotel choose to maximize expected profits?
(2) What is the optimal capacity?
This work is a joint effort with Bob Scott, Jan Highfill, and Ed Sattler.
|| Math Department Colloquium. Note time and place. || || Friday, December 5, 4 PM, Van Vleck B239 || || * Jason Schweinsberg,* Cornell University || || *Using random partitions to approximate the effect of beneficial mutations on the genealogy of a population * ||
When a beneficial mutation occurs in a population, the new, favored allele may spread to the entire population. This process is known as a selective sweep. Suppose we sample n individuals at the end of a selective sweep. If we focus on a site on the chromosome that is close to the location of the beneficial mutation, then many of the individuals will likely be descended from the individual that had the beneficial mutation at the beginning of the selective sweep, while others will be descended from a different individual because of recombination between the two sites on the chromosome. We will describe a random partition of {1,...,n} which gives a very accurate approximation to the effect of the selective sweep on the genealogy of the n sampled individuals.
Last modified: Tue Apr 6 13:39:58 CDT 2004