Three-Toed Sloth

"Two Problems on Stirring Processes --- and their Solutions" (This Week at the Statistics Seminar)

Attention conservation notice: Irrelevant unless you are (a) interested in interacting particle systems and/or stochastic processes on graphs, and (b) in Pittsburgh.

This week (in fact, tomorrow!) at the statistics seminar:

Thomas M. Liggett, "Two Problems on Stirring Processes — and their Solutions"

Abstract: Consider a finite or infinite graph G=(V,E), together with an assignment of nonnegative rates c_e to e \in E. For each edge e, there is a Poisson process \Pi_e of rate c_e. A Markov process is defined on this structure by placing labels on V, and then interchanging the labels at the two vertices joined by e at the event times of \Pi_e. If one considers the motion of just one label, this is a random walk on V. If all labels are 0 or 1, it is the symmetric exclusion process on V. If all labels are distinct, it is a random walk on the set of permutations of V. In this talk, I will describe recent solutions to two problems about these processes:

1. Suppose G=Z¹ and c_e=1 for each edge. Consider the symmetric exclusion process starting with the configuration ... 1 1 1 0 0 0 .... , and let N_t be the number of 1's to the right of the origin at time t. This is sum of negatively correlated Bernoulli random variables. In 2000, R. Pemantle asked whether N_t satisfies a central limit theorem. I will explain how a new negative dependence concept leads to a a positive answer to this question. This is partly based on joint work with J. Borcea and P. Brändén.

2. Suppose G is the complete graph on n vertices, and consider both the random walk on V and the random walk on the set of permutations of V. Each is a reversible, finite state, Markov chain, with n and n! states respectively. The exponential rate of convergence to equilibrium (which is the uniform distribution) for such a chain is determined by the smallest non-zero eigenvalue of -Q, where Q is the transition rate matrix of the chain. Let l₁ and l₂ be these values for the two processes. It is elementary that l₂ =< l₁. Based on explicit computations in some special cases, D. Aldous conjectured in 1992 that l₁=l₂. I will describe some elements of the approach that leads to a proof of this conjecture. This is joint work with P. Caputo and T. Richthammer.

Time and Place: Thursday, 10 September 2009, 4:30--5:30 pm, Giant Eagle Auditorium (Baker Hall A53)

The seminar is free and open to the public.

Enigmas of Chance; Mathematics