Home Participants Programme Abstracts

London Mathematical Society Durham Symposium
Markov Chains
Friday 25th July - Monday 4th August 2003

List of abstracts:

 David Aldous (Berkeley) Sunday 3rd August 09:00 Recursive Tree Processes Suppose we are given a joint distribution for some family of random variables $(A_i, i \geq 1)$, and given a function $g(\cdot)$. Let $X; (X_i,i \geq 1)$ be i.i.d. with some unknown distribution $\mu$. Consider the equation for $\mu$: $X \ed g ((X_i, A_i), i \geq 1 .$ Such equations arise in a variety of settings: (i) Galton-Watson branching processes and related random trees, (ii) probabilistic analysis of algorithms with suitable recursive structure (iii) statistical physics models on trees (iv) statistical physics and algorithmic questions in the mean-field model of distance. Though such questions are usually studied in terms of fixed points of the induced transformation on probability distributions, there is a richer probabilistic structure we call {\em recursive tree structure}, analogous to the {\em iterated random function (coupling from the past)} structure for Markov chains. We outline some theory and applications. Peter Ashwin (University of Exeter) Thursday 31st July 11:15 Convergence to local random attractors (joint work with Gunter Ochs, Bremen) We characterize convergence of trajectories in random dynamical systems to random invariant sets, with a view to better understanding decomposition of random attractors into local attractors analogous to the measure-theoretic attractors of Milnor for deterministic dynamics. Focussing on random mappings, we compare the usual notions of pullback and almost sure convergence with a variety of inequivalent ones, including the very weak notion of convergence in probability in the mean which nonetheless includes the support of all invariant measures. We also investigate some effects of different notions of convergence on definitions of random Milnor attractors, where we require a positive Lebesgue measure basin but not necessarily any open absorbing set. This is used to interpret some numerical simulations of a stochastically forced nonlinear (van der Pol-Duffing) oscillator. Alexandros Beskos (University of Lancaster) Wednesday 30th July 20:00 One-Shot Coupling From the Past Magnus Bordewich (University of Oxford) Wednesday 30th July 20:00 Counting problems in phylogenetics Evelyn Buckwar (Humboldt-University Berlin) Friday 1st August 11:15 Noise Induced Oscillation in Solutions of Stochastic Delay Differential Equation In this talk we study the oscillatory properties of solutions of linear scalar stochastic delay differential equations with multiplicative noise. It is shown that such noise will induce an oscillation in the solution whenever there is negative feedback from the delay term. The zeros of the process are a countable set; the solution is differentiable at each zero, and the zeros are simple. The addition of such noise does not alter the positivity of solutions when there is positive feedback. Krzysztof Burdzy (University of Washington) Tuesday 29th July 17:00 Trap domains for reflected Brownian motion Trap domains are bounded sets such that the reflected Brownian motion starting from some points close to the boundary of the domain takes a very long time to reach the center of the domain. I will present an explicit geometric characterization of simply connected planar trap domains. Some sufficient conditions for non-trap domains are available for non-simply connected and multidimensional domains. If time permits, I will discuss the multiparticle hydrodynamic limit model that inspired research on trap domains, and another research project inspired by the same model. Joint work with Z. Chen and D. Marshall. Colin Cotter (Imperial College) Wednesday 30th July 20:00 TBA Hans Crauel (Technische Universität Ilmenau) Sunday 27th July 10:00 An Introduction to Random Dynamical Systems The talk gives an introduction into the theory of random dynamical systems. Particular attention is given to the point where notions and results from dynamical systems and from ergodic theory meet -- and sometimes apparantly contradict - notions and results from the theory of Markov processes and semigroups. Hans Crauel (Technische Universität Ilmenau) Sunday 3rd August 09:30 Stabilization of a reaction-diffusion equation by additive noise Additive noise acting on a reaction-diffusion equation may cause the associated random attractor to become a one-point set. This is in sharp contrast to both the deterministic case and the case of multiplicative noise, where the Hausdorff dimension of the attractor can in certain cases be shown to increase with bifurcation parameters. Joint work with Tomas Caraballo, Jose Langa, and James Robinson Mary Cryan (University of Leeds) Thursday 31st July 09:00 Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources We consider the problem of uniformly sampling a vertex of a transportation polytope with m sources and n destinations, where m is a constant. We analyse a natural random walk on the edge-vertex graph of the polytope. The analysis makes use of the multi-commodity flow technique of Sinclair together with ideas developed by Morris and Sinclair for the knapsack problem, and by Cryan et al. for contingency tables, to establish that the random walk approaches the uniform distribution in time n^{O(m^2)}. Joint work with Martin Dyer, Haiko Muller and Leen Stougie Artur Czumaj (NJIT) Sunday 3rd August 11:15 Applications of convergence bounds for Markov chains to stochastic balls-into-bins processes. In this talk we present some applications of the analysis of convergence bounds for Markov chains to stochastic processes of allocating balls into bins. We consider a randomized process of allocating m balls into n bins assuming that each ball comes with d > 1 possible locations drawn at random from the set of bins. Previous analyses concentrated mostly on the lightly loaded case, i.e., m ~ n and no good (and accurate) analysis has been known for the heavily loaded case. In this case, the best known results correspond to the results known for the single-choice algorithm (i.e., each ball is assigned to a randomly chosen bin). In this talk we will discuss the first tight analysis for multiple-choice algorithms in the heavily loaded case. We will show that the multiple-choice processes are fundamentally different from the classical single-choice process in that they have "short memory." That is, for an arbitrary distribution of balls in the bins with a maximum load difference of K, inserting further K poly(n) balls will re-balance the system. Our proof of this result is based on a precise analysis of the convergence time of the underlying Markov chain. Our analysis of the convergence bound of the Markov chain uses a non-Markovian coupling approach which might be interested itself. Using the "short memory" property we can provide almost exact estimations for the distributions obtained by two different multiple choice algorithms, which are a "greedy" scheme and the recently introduced "always-go-left" scheme. Joint work with Petra Berenbrink, Angelika Steger, and Berthold Voecking. Brian Davies (King's College London) Tuesday 29th July 11:15 Markov-type semigroups and pseudospectra. The growth properties of positivity-preserving semigroups may not be easily explained in terms of the spectral properties their generators. We will describe recent work on pseudospectra, and how it relates to this problem. We also provide numerical results supporting our conclusions about the usefulness of pseudospectra in this context. Michael Dellnitz (Paderborn) Thursday 31st July 11:45 On the identification of macroscopic dynamics In this talk I am going to explain how to compute almost invariant (i.e. metastable) sets both using a spectral approach and by using graph theoretic algorithms. As an application it will be shown that these methods can be used to confirm (numerically) the existence of the asteroid belt between Mars and Jupiter. In fact, the results strongly suggest that Jupiter on its own is responsible for the existence of the asteroid belt. Michael Dellnitz (Paderborn) Tuesday 31st December : On the identification of macroscopic dynamics In this talk I am going to explain how to compute almost invariant (i.e. metastable) sets both using a spectral approach and by using graph theoretic algorithms. As an application it will be shown that these methods can be used to confirm (numerically) the existence of the asteroid belt between Mars and Jupiter. In fact, the results strongly suggest that Jupiter on its own is responsible for the existence of the asteroid belt. Michael Dellnitz (Paderborn) Tuesday 31st December : On the identification of macroscopic dynamics In this talk I am going to explain how to compute almost invariant (i.e. metastable) sets both using a spectral approach and by using graph theoretic algorithms. As an application it will be shown that these methods can be used to confirm (numerically) the existence of the asteroid belt between Mars and Jupiter. In fact, the results strongly suggest that Jupiter on its own is responsible for the existence of the asteroid belt. Michael Dellnitz (Paderborn) Tuesday 31st December : On the identification of macroscopic dynamics In this talk I am going to explain how to compute almost invariant (i.e. metastable) sets both using a spectral approach and by using graph theoretic algorithms. As an application it will be shown that these methods can be used to confirm (numerically) the existence of the asteroid belt between Mars and Jupiter. In fact, the results strongly suggest that Jupiter on its own is responsible for the existence of the asteroid belt. Michael Dellnitz (Paderborn) Tuesday 31st December : On the identification of macroscopic dynamics In this talk I am going to explain how to compute almost invariant (i.e. metastable) sets both using a spectral approach and by using graph theoretic algorithms. As an application it will be shown that these methods can be used to confirm (numerically) the existence of the asteroid belt between Mars and Jupiter. In fact, the results strongly suggest that Jupiter on its own is responsible for the existence of the asteroid belt. Michael Dellnitz (Paderborn) Tuesday 31st December : On the identification of macroscopic dynamics In this talk I am going to explain how to compute almost invariant (i.e. metastable) sets both using a spectral approach and by using graph theoretic algorithms. As an application it will be shown that these methods can be used to confirm (numerically) the existence of the asteroid belt between Mars and Jupiter. In fact, the results strongly suggest that Jupiter on its own is responsible for the existence of the asteroid belt. Michael Dellnitz (Paderborn) Tuesday 31st December : On the identification of macroscopic dynamics In this talk I am going to explain how to compute almost invariant (i.e. metastable) sets both using a spectral approach and by using graph theoretic algorithms. As an application it will be shown that these methods can be used to confirm (numerically) the existence of the asteroid belt between Mars and Jupiter. In fact, the results strongly suggest that Jupiter on its own is responsible for the existence of the asteroid belt. Bruno de Sousa (University of Toronto) Wednesday 30th July 20:00 Extremal Indices and Geometric Ergodicity of Markov Chains Persi Diaconis (Stanford) Saturday 2nd August 11:15 Fastest mixing Markov Chains and convex programming Fix a connected graph, how do we choose weights on the edges so that the natural random walk has a given stationary distribution and mixes rapidly? The metropolis algorithm gives one method. It turns out there are faster methods which can be found using convex programming. One may guess from data at some general heuristics. Joint work with Steve Boyd and Lin Xiao. Martin Dyer (Leeds) Monday 28th July 09:30 Markov Chains for sampling contingency tables We consider the mixing time of a natural Markov chain on a set of mxn contingency tables with given row and column sums, in the case where m may be considered a constant. We show that the chain mixes in time polynomial in the size of the input. Jim Fill (The Johns Hopkins University) Monday 28th July 10:00 Speeding up the FMMR perfect sampling algorithm: A case study revisited In a previous paper by the speaker, two Markov chain Monte Carlo perfect sampling algorithms -- one called coupling from the past (CFTP) and the other (FMMR) based on rejection sampling -- are compared using as a case study the move-to-front (MTF) self-organizing list chain. Here we revisit that case study and, in particular, exploit the dependence of FMMR on the user-chosen initial state. We give a stochastic monotonicity result for the running time of FMMR applied to MTF and thus identify the initial state that gives the stochastically smallest running time; by contrast, the initial state used in the previous study gives the stochastically *largest* running time. By changing from worst choice to best choice of initial state we achieve remarkable speedup of FMMR for MTF; for example, we reduce the running time (as measured in Markov chain steps) from exponential in the length n of the list nearly down to n when the items in the list are requested according to a geometric distribution. For this same example, the running time for CFTP grows exponentially in n. Joint work with Robert P. Dobrow. Leslie Goldberg (University of Warwick) Sunday 3rd August 12:15 Markov chains for sampling colourings We explore rates of convergence of single-site Markov chains for sampling colourings. In this setting, the state space is the set of all proper colourings of an n-vertex graph G. Given a proper colouring x and a vertex v, a Metropolis'' transition consists of choosing a colour c uniformly at random. A new colouring x' is formed by recolouring vertex v with colour c. A transition is made from x to x' unless colour c is already used at a neighbour of v in colouring x (in which case the move is rejected, and the chain stays at state x). We explore two different dynamics, Glauber dynamics'' in which a new vertex v is chosen uniformly at random at each transition, and Gibbs dynamics''. Each transition of Gibbs dynamics consists of n Metropolis moves, one for each vertex (applied in a systematic order). For an arbitrary graph G, the mixing times of the two dynamics are fairly close. In particular, the Poincare constant of Gibbs (measured in Scans) is at most O(n^2) times the Poincare constant of Glauber (measured in site updates), which (for bounded-degree graphs) is at most O(1) times the Poincare constant of Gibbs. This implies that the mixing time of the two chains are polynomially related. It is plausible that the Poincare constant of Gibbs is around n times that of Glauber, so scanning systematically neither helps nor hurts. As a benchmark, we consider the case in which G is a path. For this case, we get tight results about mixing times (matching upper and lower bounds). These results depend upon q, the number of colours. For q=3, the mixing time of Glauber is Theta(n^3 log n) and the mixing time of Gibbs is Theta(n^2 log n). For q>=4, the mixing time of Glauber is Theta(n log n) and the mixing time of Gibbs is Theta(log n). We also consider the extension of the dynamics to H-colourings, and show that the mixing times are O(n^5) and O(n^4), respectively. Presumably our bounds for H-colouring are not tight. Joint work with Martin Dyer and Mark Jerrum Olle Haggstrom (Chalmers) Thursday 31st July 10:00 Probability on bunkbed graphs We discuss various stochastic models (random walk, percolation, the Ising and random-cluster models) on so-called bunkbed graphs, together with a class of inequalities that are natural to conjecture for these models on bunkbed graphs. By a bunkbed graph, we mean a graph that is obtained as a Cartesian product of the complete graphs on two vertices and another graph. A new correlation inequality for the Ising model on bunkbed graphs is presented. Niels Richard Hansen (University of Copenhagen) Wednesday 30th July 20:00 Excursions for Markov Additive Processes and Biological Sequence Alignment The theory of positive excursions for a random walk with negative drift has played a crucial role in the area of biological sequence analysis, providing a foundation for assessing the significance of local alignments of sequences. That is, computing p-values for finding high-scoring local alignments in random sequences. A generalisation to excursions for Markov additive processes, sometimes called Markov controlled random walks, is also possible. In this talk, I will show some recent results on the asymptotic distribution of excursions for Markov additive processes, where the increments in some states have a heavy tailed distribution. Then I will show how this can be used to analyse excursions for semi-Markov additive processes with heavy tailed duration distributions. Finally, I will show how the theory of excursions for semi-Markov additive processes can explain how low-complexity regions, e.g. repeats, in biological sequences invalidate the commonly computed p-values. Especially if the distribution of the length of these regions is heavy-tailed. Wilhelm Huisinga (Berlin) Tuesday 29th July 11:45 On the Effects of Fast Degrees of Freedom on Macroscopic Dynamical Behavior The talk is about the averaging principle for stochastic dynamical systems with fast and slow degrees of freedom. It is demonstrated how the principle results from asymptotic multiscale analysis, how one can construct an indicator for its eventual inappropriateness, and how if inappropriate it may be extended into a valid approximation. All steps are illustrated by numerical experiments. Application to molecular dynamics problems is discussed. Mark Jerrum (University of Edinburgh) Saturday 26th July 09:30 Mixing time and its relation to other Markov chain parameters Obtaining tight bounds on mixing time of Markov chains (i.e., time to forget the initial state) is important in the analysis of algorithms and elsewhere. Success in this endeavour depends on understanding various parameters associated with Markov chains and their relationships, both with each other and with mixing time. Some of these parameters, for example spectral gap, depend purely on the Markov chain itself; others involve auxiliary structures, for example, a multicommodity flow supported on the transitions of the Markov chain. Mark Jerrum (University of Edinburgh) Saturday 26th July 15:15 Mixing time and its relation to other Markov chain parameters Obtaining tight bounds on mixing time of Markov chains (i.e., time to forget the initial state) is important in the analysis of algorithms and elsewhere. Success in this endeavour depends on understanding various parameters associated with Markov chains and their relationships, both with each other and with mixing time. Some of these parameters, for example spectral gap, depend purely on the Markov chain itself; others involve auxiliary structures, for example, a multicommodity flow supported on the transitions of the Markov chain. Ravi Kannan (Yale) Thursday 31st July 16:30 Blocking Conductance and improved mixing bounds While conductance provides a general tool for proving fast mixing, the bounds are usually not optimal; we focus on two sources of non-optimality here - (i) the start penalty, which penalizes bad starts - for discrete chains this is a factor of log (1/minimum steady state probablity) and (ii) the squaring of the conductance. We define a more general notion of blocking conductance'' to overcome the square in some situations. We also show we can average over set sizes to address (i). Joint work with L. Lovasz and R. Montenegro Wilfrid Kendall (University of Warwick) Saturday 26th July 11:45 Coupling I: concepts and examples "Coupling" is a many-valued term in mathematical science! In a probabilist's vocabulary it refers to the following: finding out about a random system X by constructing a second random system Y on the same probability space (perhaps augmented by a seasoning of extra randomness). Careful construction, choosing the right system Y, designing the right kind of dependence between X and Y, can lead to clear and intuitive demonstrations of important facts about X. One of the oldest applications of coupling, due to Doeblin, gives a conceptual proof of the classic theorem on convergence to equilibrium of finite aperiodic irreducible Markov chains, and the intellectual grandchildren of this idea are used today to deliver information about mixing rates. Other applications provide important representations of stochastic systems, facilitate approximation arguments, or deliver monotonicity results. This talk will introduce these ideas by discussing a variety of examples, mostly arising from applied probability. Wilfrid Kendall (University of Warwick) Sunday 27th July 09:15 Coupling II: applications to simulation The constructive nature of probabilistic coupling ("build Y using the randomness of X") makes it close in spirit to the task of constructing good stochastic simulations. Recently the link between coupling and simulation has been strengthened in striking ways, resulting in so-called "exact" or "perfect simulation". This talk will introduce these developments. Peter Kloeden (J.W. Goethe University) Saturday 2nd August 16:30 The computation of invariant measures of dynamical systems through Markov chains Invariant measures of dynamical systems generated by difference equations can be computed by discretizing the originally continuum state space, replacing the action of the generator by the transition mechanism of a Markov chain and using stationary vectors of these Markov chains to approximate the measures. The will be proved in outline for autonomous difference equations. The generalization to random difference equations involving random random measures and random Markov chains and will also be indicated. P. Diamond, P. Kloeden and A. Pokrovskii, Interval Stochastic Matrices: A Combinatorial Lemma and the Computation of Invariant Measures of Dynamical Systems. {\em J. Dynamics Differential Equations} {\bf 7} (1995), 341-364. P. Imkeller and P. Kloeden, On the computation of invariant measures in random dynamical systems, preprint Raz Kupferman (The Hebrew University) Monday 28th July 12:15 Variable reduction in heat bath models This talk considers mechanical models of a particle-in-a-heat-bath. A "distinguished" particle interacts with a large number of "heat bath" particles through mechanical springs; the heat bath particles are assumed to have random initial data. The goal is to derived a reduced (stochastic) equation for the trajectory of the distinguished particle as the size of the heat bath tends to infinity. I will discuss models with linear springs, nonlinear springs, and (if time permits) describe a models that exhibits fractional (sub-)diffusion. Tom Kurtz (Wisconsin) Tuesday 29th July 17:30 A complicated representation of a simple branching process A collection of particles in the interval [0,r] move according to the solution of an ordinary differential equation. Each particle randomly produces offspring in the interval which move according to the same rules. A particle dies when it reachs the right end point r. This system can be constructed in such a way that the number of particles alive gives a continuous time Markov branching process. The proof of this result exploits a very useful theorem on mapping of Markov processes. Letting r go to infinity, gives an easy proof of the Feller diffusion approximation and a particle representation of a continuous state branching process. The results extend to general Markov branching processes and their convergence to Dawson-Watanabe measure-valued branching processes. Benedict Leimkuhler (Leicester) Saturday 2nd August 09:30 Structured dynamical heat bath models for molecular systems Canonical ensemble simulations are typically performed using either a stochastic or dynamical formalism which mimic exchange of heat to a surrounding particle system. In both types of models the assumption of a simplified bath structure limits the usefulness of the formalism for molecular simulations. In this talk, I will describe some enhanced dynamical thermostatting models and simulation algorithms for classical moleclar and disordered magnetic systems aimed at improving samlping efficiency. Torgny Lindvall (Chalmers) Thursday 31st July 09:30 On a routing problem Consider a G/M/k queueing system, non-standard in the sense that the service intensities are not the same for all the stations. A natural routing policy is the following: if there are more than one station idle when a customer arrives, let her be served by the one with highest service intensity. We prove that this policy is optimal, using a suitable coupling. Carlangelo Liverani (University of Rome ) Monday 28th July 16:30 Stochastic properties of Anosov flows I will describe the known results on the ergodic properties of Anosov flows (geodesic flows on compact manifolds of negative curvature in particular). I will, then illustrate some recent results that partially solve long standing questions on the speed of mixing.) Carlangelo Liverani (University of Rome ) Saturday 26th July 16:45 Transfer operators in dynamical systems (a brief idiosyncratic review of Perron-Frobenius operators theory) Carlangelo Liverani (University of Rome ) Saturday 26th July 10:15 Transfer operators in dynamical systems (a brief idiosyncratic review of Perron-Frobenius operators theory) Transfer operators in dynamical systems (a brief idiosyncratic review of Perron-Frobenius operators theory) Malwina Luczak (University of Cambridge) Sunday 3rd August 11:45 On the power of two choices: balls and bins in continuous time Suppose that there are n bins, and balls arrive ina Poisson process at rate λn where λ>0 is a constant. Upon arrival each ball chooses a fixed number d of random bins and is placed into one with least load. Balls have independent exponential lifetimes with unit mean. We show that the system converges rapidly to its equilibrium distribution; and when dge2 there is an integer-valued function md(n)=\ln\ln n/\ln d+O(1) such that, in the equilibrium distribution, the maximum load of bins is md(n) or md(n)-1 with probability tending to 1 as n->&infty;. We show also that the maximum load usually does not vary by more than a constant amount from \ln\ln n/\ln d even over quite long periods of time.We obtain analogous results for the well known "supermarket" model, where insteal balls(customers) queue at their bins(servers) and are served according to the first-come first-served discipline.We further indicate how these results imply "propogation of chaos" in our models. Stefano Luzzato (Imperial College) Monday 28th July 17:00 Topological Markov Chains and Statistical properties of non-uniformly expanding maps I will survey several recent results on the coding of non-uniformly expanding maps by Markov induced maps on a countable partion and discuss the relation between geometrical features and statistical features such as rate of decay of correlation. Iain MacPhee (University of Durham) Tuesday 29th July 09:00 Classification of polling models via semi-martingales - Joint talk with M Menshikov Our goal is to discuss Lyapunov function methods for investigating many dimensional random walks with application to polling models. In a polling system customers form several queues which are served by a single server. While the server is processing queue $i$ all queues are growing but the server only switches to another queue (selected by some simple rule -- this is polling') when queue length $x_i$ has reached 0 (strictly this is exhaustive polling'). In the simplest model there are $k$ queues and queue $i$ has a Poisson arrival stream of rate $\lambda_i$ and service times are exponential with mean $\mu_i$, $i = 1$, $\ldots\,$, $k$ but there are other models which also have a jump process which is a multi-dimensional random walk with regions of homogeneity which are well defined and with geometrically obvious connections e.g.~with exhaustive polling regions are connected through sets $\{x_j = 0\}$. We will discuss general Lyapunov function methods for resolving transience/ergodicity of random walks in such spaces in terms of the drift parameters within the homogeneous regions and the nature and topology of their connections. The methods are powerful enough to be able to resolve critical cases though switching times become important here -- see \emph{Critical random walks on two-dimensional complexes with applications to polling systems} by MacPhee and Menshikov, to appear in Ann.~App.~Prob. We will also discuss a transient cases with three queues. Here we can show that a fluid model converges onto a periodic orbit for almost all sets of parameters and that in this case the stochastic model converges a.s.~onto the same orbit. We can construct parameters for which the fluid model and hence the stochastic model are not periodic. Jonathan Mattingly (Duke/IAS) Sunday 3rd August 14:15 Adaptive methods of long time simulations of stochastic differential equations Often the goal of simulating a stochastic differential equation (SDE) is to draw from its stationary distribution. There are examples of simple SDEs which are ergodic yet standard numerical approximations of the SDE, such as Euler's method, fails to be ergodic. I will describe a number of remedies for this problem. In particular, I will discuss some adaptive schemes which can be proven to be ergodic if the under lying SDE is ergodic and satisfies some additional assumptions. Some numerical experiments will also be shown to test the schemes efficiency and accuracy. Joint work with Andrew Stuart and Harbir Lamba. Ian Melbourne (University of Surrey) Sunday 3rd August 10:00 A New Test for Chaos We describe a new test (the result of joint work with Georg Gootwald, Sydney) for determining whethera given deterministic dynamical system is chaotic or nonchaotic. In contrast to the usual method of computing the maximal Lyapunov exponent, our method is applied directly to the time series data and does not require a phase space reconstruction. Moreover, the dimension of our dynamical system and the form of the underlying euqations is irrrelevant. The input is the time series data and the output is 0 or 1 depending on whether the dynamics is nonchaotic or chaotic.Our diagnostic is the rela valued function p(t)=\in_0^t\phix(s))ds where phi is an observable on the underlying dynamics x(t) and heta(t)=ct+int_0^tphi(x(s))ds. The constant c>o is arbitrarily fixed. We define the mean-square-displacement M(t) for p(t) and set K=lim_{t->&infty;}\log M(t)/\log(t). Using recent developments in ergodic theory, we argue that typically K=0 significantly nonchaotic dynamics or K=1 signifying chaotic dynamics. Sean Meyn (Illinois) Tuesday 29th July 12:15 Spectral theory and large deviations for Markov processes We survey recent approaches to the spectral theory of Markov processes based on finite approximations in a weighted L-infinty norm. The approximations are closely related to the standard representations of eigenfunctions and eigenmeasures via small functions used in the Perron-Frobenius theory of positive matrices. Applications to large deviations theory are also described. Joint work with Ioannis Kontoyiannis Ravi Montenegro (Georgia Institute of Technology) Wednesday 30th July 20:00 TBA Navaratnam Namachchivaya (University of Illinois @ Urbana-Champaign) Saturday 2nd August 17:00 Multi-Scale phenomena in noisy nonlinear mechanical systems Nonlinear stochastic systems are at the center of many engineering disciplines, and the multi-scale phenomena that arise in their study are the focus of the presentation. Matthew Nicol (Surrey) Monday 28th July 17:30 Statistical Properties of Endomorphisms and Compact Group extensions We consider the statistical properties of endomorphisms under the assumption that the asociated Perron-Frobenius operator is quasicompact. In particular we consider the central limit theorem, weak invariance principle and law of the iterated logarithm for sufficiently regular observations.We also give sufficient considtions for quasicompactness of the Perron-Frobenius operator to lift to the corresponding equivariant operator on acompact group extension of the base. This leads to statistical theorems. Examples considered include compact group extensions of piecewise uniformly expanded maps (for example Lasota-Yorke maps), and subshifts of finite type, as well as systems that are nonuniformly expanding or nonniformly hyperbolic. Neil O'Connell (University of Warwick) Thursday 31st July 17:30 Representations for Random Walks in Weyl Chambers A discrete version of Pitmans theorem states that, if X is a sample random walk with positive drift, and M(n) is its maxaimum up to time n, then the process 2M-X is a Markov Chain which has the same law as that of X conditiioned to stay positive. I will show how the classical output theorem for the stable, stationary M/M/1 queue, namely that the output has the same law as the input, can be used to prove this and, to a continuous setting, and in this context there is a direct connection with eigenvalues of random matrices. Jamie Radcliffe (University of Nebraska-Lincoln) Wednesday 30th July 20:00 TBA Sebastian Reich (Imperial College) Friday 1st August 10:00 Unresolved Gravity Waves in Particle Simulations Lagrangian particle methods are ideally suited for simulating large scale advective fluid motion. Gravity waves are much harder to simulate within this framework. However, one can formulate a simplified particle-wave model starting from a variational principle. Using quiter a bit of handwaving one can then again eliminate the fast linear gravity waves and derive a reduced Langevin type model. On the other hand, computationally it appears as more appropriate to work withni the coupled particle-wave model. Philippe Robert (INRIA) Tuesday 29th July 09:30 Stochastic Models of Data Transmission in Communication Networks The Additive-Increase Multiplicative-Decrease (AIMD) schemes designed to control congestion in communication networks are investigated. An important case of such an algorithm is TCP. Different packet loss models based on measurements are considered. The stationary behavior of this algorithm is analyzed when packet loss rate becomes arbitrarily small. Rigorous convergence results, such as functional limit theorems, as well as closed form expressions of some of the corresponding distributions are presented. From a probabilistic point of view, it is shown that exponential functionals associated to compound Poisson processes play a key role. Analytically, the natural framework of this study turns out to be the $q$-calculus. Considerations on call admission control on TCP networks shall be discussed in conclusion. Gareth Roberts (Lancaster University) Monday 28th July 09:00 MCMC convergence for hierarchical models MCMC has been hugely successful in the Bayesian analysis of hierarchical models. However little is known about the reasons why simple algorithms like the Gibbs sampler can be so powerful for analysing the types of distribution obtained from such a statistical analysis. This presentation will explore convergence properties of Gibbs samplers with particular attention being paid to posterior distributions obtained from hierarchical models.Some rate of convergence results will be given and applications to parameterisation issues for Gibbs sampling will be briefly discussed. Jeffrey Rosenthal (Toronto) Saturday 2nd August 12:15 Optimal Scaling of Metropolis-Hastings Proposal Distributions Metropolis-Hastings Algorithms allow one to choose the proposal distribution essentially arbitrarily. How should the choice be made? We will review results about optimal proposal scaling for random-walk Metropolis algorithms and for langevin algorithms. We will also discuss some more recent work involving inhomogeneously-scaled target distributions, and the behaviour of Metropolis-Hastings when started out in the tails of the target distribution. Joint work with G.O. Roberts, and partially with O. Christensen. Jeffrey Rosenthal (Toronto) Sunday 27th July 11:45 Statistics and MCMC Markov chain Monte Carlo algorithms have become extraordinarily widespread in statistics, as a way of approximately sampling from complicated probability distributions such as posterior distributions. The Gibbs sampler and Metropolis-Hastings algorithms are standard, and many variations are also used. The range of applications is enormous. In this talk, we will explain the basic MCMC algorithms used, and give some sense of the scope of their application in statistical research. Christof Schuette (Free University Berlin) Monday 28th July 11:15 Rare events in biomolecular dynamics Biomolecular dynamics can be modelled as deterministic or stochastic motion in a complex energy landscape. This energy landscape typically exhibits multiscale features that give rise to the multiscale nature of the dynamics. Activity and function of bioploymers are deeply related to the longest temporal scales in the systems which are rare transition events between the most important conformations of the molecule. Thus, mathematically, conformations can be modelled as metastable or almost invariant subsets of the phase space. The talk will give an expository introduction to the dynamical and stochastic concepts for the identification of the most important metastable sets and the computation of transition rates, and transition pathways between them. Christof Schuette (Free University Berlin) Tuesday 31st December : Rare events in biomolecular dynamics Biomolecular dynamics can be modelled as deterministic or stochastic motion in a complex energy landscape. This energy landscape typically exhibits multiscale features that give rise to the multiscale nature of the dynamics. Activity and function of bioploymers are deeply related to the longest temporal scales in the systems which are rare transition events between the most important conformations of the molecule. Thus, mathematically, conformations can be modelled as metastable or almost invariant subsets of the phase space. The talk will give an expository introduction to the dynamical and stochastic concepts for the identification of the most important metastable sets and the computation of transition rates, and transition pathways between them. Christof Schuette (Free University Berlin) Tuesday 31st December : Rare events in biomolecular dynamics Biomolecular dynamics can be modelled as deterministic or stochastic motion in a complex energy landscape. This energy landscape typically exhibits multiscale features that give rise to the multiscale nature of the dynamics. Activity and function of bioploymers are deeply related to the longest temporal scales in the systems which are rare transition events between the most important conformations of the molecule. Thus, mathematically, conformations can be modelled as metastable or almost invariant subsets of the phase space. The talk will give an expository introduction to the dynamical and stochastic concepts for the identification of the most important metastable sets and the computation of transition rates, and transition pathways between them. Christof Schuette (Free University Berlin) Tuesday 31st December : Rare events in biomolecular dynamics Biomolecular dynamics can be modelled as deterministic or stochastic motion in a complex energy landscape. This energy landscape typically exhibits multiscale features that give rise to the multiscale nature of the dynamics. Activity and function of bioploymers are deeply related to the longest temporal scales in the systems which are rare transition events between the most important conformations of the molecule. Thus, mathematically, conformations can be modelled as metastable or almost invariant subsets of the phase space. The talk will give an expository introduction to the dynamical and stochastic concepts for the identification of the most important metastable sets and the computation of transition rates, and transition pathways between them. Christof Schuette (Free University Berlin) Tuesday 31st December : Rare events in biomolecular dynamics Biomolecular dynamics can be modelled as deterministic or stochastic motion in a complex energy landscape. This energy landscape typically exhibits multiscale features that give rise to the multiscale nature of the dynamics. Activity and function of bioploymers are deeply related to the longest temporal scales in the systems which are rare transition events between the most important conformations of the molecule. Thus, mathematically, conformations can be modelled as metastable or almost invariant subsets of the phase space. The talk will give an expository introduction to the dynamical and stochastic concepts for the identification of the most important metastable sets and the computation of transition rates, and transition pathways between them. Christof Schuette (Free University Berlin) Tuesday 31st December : Rare events in biomolecular dynamics Biomolecular dynamics can be modelled as deterministic or stochastic motion in a complex energy landscape. This energy landscape typically exhibits multiscale features that give rise to the multiscale nature of the dynamics. Activity and function of bioploymers are deeply related to the longest temporal scales in the systems which are rare transition events between the most important conformations of the molecule. Thus, mathematically, conformations can be modelled as metastable or almost invariant subsets of the phase space. The talk will give an expository introduction to the dynamical and stochastic concepts for the identification of the most important metastable sets and the computation of transition rates, and transition pathways between them. Christof Schuette (Free University Berlin) Tuesday 31st December : Rare events in biomolecular dynamics Biomolecular dynamics can be modelled as deterministic or stochastic motion in a complex energy landscape. This energy landscape typically exhibits multiscale features that give rise to the multiscale nature of the dynamics. Activity and function of bioploymers are deeply related to the longest temporal scales in the systems which are rare transition events between the most important conformations of the molecule. Thus, mathematically, conformations can be modelled as metastable or almost invariant subsets of the phase space. The talk will give an expository introduction to the dynamical and stochastic concepts for the identification of the most important metastable sets and the computation of transition rates, and transition pathways between them. Christof Schuette (Free University Berlin) Sunday 27th July 14:00 Stochastic Approaches to Biomolecular Dynamics The talk aims at an introduction to traditional as well as some recent stochastic approaches to meodelling biomolecular dynamics. I will particularly comment on the high dimension and the inherent multiscale aspects of biomolecular dynamics. It will be demonstrated that it is mainly the lack of reliable error indicators that presently hinders dramatic progress in this field. Alex Scott (University College London) Friday 1st August 09:00 Finding a planted partition in a random graph Sandeep Shah (University of Warwick) Wednesday 30th July 20:00 TBA Tony Shardlow (Manchester) Sunday 3rd August 14:45 Stochastic PDEs and Spirals We review the modelling of spiral waves leading to a system of reaction diffusion equations, and then introduce a stochastic perturbation to one well studied spiral wave model (the Barkley model). We consider how the stochastic perturbation should be introduced, how to simulate the system numerically, and analyse the behaviour in a small noise limit. Robert Skeel (Illinois) Sunday 3rd August 15:15 Variance reduction for random walk calculations of rate constants Random walk (or path integral) methods are simple and general techniques for calculating quantities defined by the solution of a linear partial differential equation. They are particularly appropriate for problems of high dimension and complex geometry such as the calculation of rate constants for diffusion-limited bimolecular reactions. The error in such calculations is proportional to the square root of the reciprocal of the number of trials, and variance reduction is, therefore, of paramount importance. A general technique for variance reduction has been proposed by G. Milstein, which requires having some information about the solution of the partial differential equation. Presented here is an efficient and robust realization of that idea, which is more streamlined than the "weighted ensemble Brownian dynamics" of G. Huber and S. Kim and is also embarassingly parallel. Alan Sokal (New York University) Saturday 26th July 14:15 A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models At the request of the organizers, I will begin by reviewing the heuristic connections between different aspects of phase transitions (nonuniqueness of the infinite-volume Gibbs measure, complex zeros of the finite-volume partition function, torpid mixing of local Monte Carlo algorithms) and explain the Fortuin-Kasteleyn representation and Swendsen-Wang algorithm for the Potts model. I will then review some recent results and unsolved problems concerning the hard-core lattice gas and the q-coloring model (antiferromagnetic Potts model at zero temperature). Andrew Stuart (University of Warwick) Sunday 27th July 15:00 Approximation of/by Markov Chains The aim of this talk is to overview a variety of approximation ideas, related to Markov chains, which will permeate this meeting. Four particular themes that I will highlight are: Abstract results about perturbation theory for transition kernels, and effect on invariant measures. The effect of time discretization on persistence and approximation of invariant measures. The use of SDEs, and other Markov processes, to approximate deterministic dynamics. The approximation of Markov chains with large state space by small state space models, using spectral decompositions. Denis Talay (Inria) Tuesday 29th July 16:30 Extrapolation methods for stochastic particle systems (joint work in progress with M. Bossy and A. Kohatsu-Higa) Paul Tavan (Munich) Monday 28th July 11:45 Effective stochastic models for the conformational dynamics of peptides in solution extracted from molecular dynamics simulations Cyclic peptides with built-in light switches exhibit a lively conformational relaxation dynam-ics upon light excitation. Essential parts of this dynamics proceed on a subnanosecond time-scale as revealed by femtosecond (fs) time-resolved spectroscopy. The observed relaxation processes can be quantitatively described by molecular dynamics (MD) simulations (Spörlein et al., 2002), if these simulations are based on an adequate all-atom force field, cover a suffi-ciently large simulation system including the peptide and the surrounding solvent, provide for the experimental thermodynamic conditions like temperature and pressure, and properly ac-count for the long-range electrostatic interactions (Mathias et al., 2003), which constitute key forces in such solvent-solute systems. At equilibrium conditions, such peptides exhibit con-formational fluctuations, which at room temperature proceed on somewhat longer time-scale and can be made accessible to nanosecond (ns) MD simulations by elevating the temperature. MD simulations describe the conformational dynamics of such peptides in the form of huge data sets representing the motions of all atoms in the simulation system at fs time-steps over a given time span of typically a few ns. To achieve an unbiased qualitative and quantitative understanding of the conformational states and transitions sampled by the simulations, the application of data reduction and pattern recognition techniques enabling a statistical analysis of the raw simulation data is required. Here we explain the above sample system and sketch the techniques, which allow us to ex-tract effective stochastic models of the peptide conformational dynamics from the MD trajec-tories. These techniques are based on maximum likelihood estimates of the invariant configu-ration space density by mixtures of normal distributions (Kloppenburg and Tavan, 1997, Albrecht et al., 2000) and on multiple-scale analyses of such model densities (Tavan et al, 1990) as well as of corresponding transfer operators. The transfer operators can be set up by using the fuzzy partitions associated with the mixture models as means for a discretization of the configuration space. Spörlein, S, H Carstens, H Satzger, C Renner, R Behrendt, L Moroder, P Tavan, W Zinth, and J Wachtveitl (2002). Ultrafast spectroscopy reveals sub-nanosecond peptide conformational dynamics and validates mo-lecular dynamics simulation Proc. Natl. Acad. Sci. (USA) 99, 7998-8002. Mathias, G, B Egwolf, M Nonella, and P Tavan (2003). A fast multipole method combined with a reaction field for long-range electrostatics in molecular dynamics simulations: The effects of truncation on the properties of water. J. Chem. Phys., in press. Klopppenburg, M, and P Tavan (1997).Deterministic annealing for density estimation by multivariate normal mixtures. Phys. Rev E 55, 2089-2092. Albrecht, S, J Busch, M Kloppenburg, F Metze und P Tavan (2000). Generalized radial basis function networks for classification and novelty detection: Self-organization of optimal Bayesian decision. Neural Networks 13, 1075-1093. Tavan, P, H Grubmüller, and H Kühnel (1990). Self-organization of associative memory and pattern classifica-tion: Recurrent signal processing on topological feature maps. Biol. Cybern. 64, 95-105. Elke Thoennes (University of Warwick) Saturday 2nd August 11:45 MCMC for random trees and vascular structure In this talk I will discuss issues and methods of sampling a forest of random trees using reversible jump Markov chain Monte Carlo. Random binary trees are used as a prior model for artery/vein structure in retinal images. Inference on the true vascular structure in the image is then based on samples from the posterior distribution produced by the developed MCMC algorithm. Issues of the method include the choice of proposal distribution, diagnosing convergence and meta-stability. Hermann Thorisson (University of Iceland) Tuesday 29th July 10:00 Intuitive Coupling Argument in the Null Recurrent Case The classical coupling proof of the asymptotic stationarity of an irreducible aperiodic positive recurrent Markov chain $X$ is used in modern textbooks on Markov chains because it is both technically easy and intuitively appealing. It can be outlined as follows: Let $Y$ be a stationary version of $X$. Run $Y$ independently of $X$ until the two chains meet. Run them together from that time onward. It is easy to prove that the two chains eventually meet. Thus $X$ behaves asymptotically as a stationary chain. In the case when $X$ is null recurrent, asymptotic stationarity is replaced by the result that for each state $j$, $P(X_n = j)$ is close to 0 asymptotically. Proofs using coupling as a technical ingredient can be found in textbooks but lack the intuitive appeal of the above argument. In this talk we shall present an intuitive version of the classical coupling argument in the null recurrent case. It can be outlined as follows: Let $Y$ be a version of $X$ such that $P(Y_n = j)$ is close to 0 for all $n$. Run $Y$ independently of $X$ until the two chains meet. Run them together from that time onward. If they do not meet with probability one, then it is easy to show that $P(X_n = j)$ is close to 0 asymptotically. If they meet with probability one, then $X$ behaves as $Y$ asymptotically, and thus $P(X_n = j)$ is close to 0 asymptotically. Using a coupling of Ornstein type rather than the classical coupling (which need not be successful in the null recurrent case) this argument actually yields convergence uniform in sets of states with bounded stationary measure. This argument extends to null recurrent Harris chains. A version of the uniform limit result was obtained by Jain in 1966. Jain, N.C. (1966). Some limit theorems for the general Markov Process. Z. Wahrscheinlichkeitstheorie verw. Geb. 6, 206-223. Thorisson, H. (2000): Coupling, Stationarity, and Regeneration. Springer, New York. Paul Tupper (McGill) Saturday 2nd August 10:00 Models of Heat Baths, Long Term Statistics, and Numerical Simulation I will discuss a model for a massive particle interacting with a heat bath due to Kac, Zwanzig and others. Some rigorous results have been obtained about how this system can be approximated by a generalized Langevin equations. However, with respect to long term statistics, we would like to be able to say more, and I will state some open problems. Then I will discuss some results for long term statistics of numerical discretizations of such systems. Alexander Veretennikov (University of Leeds) Friday 1st August 12:15 Mixing for approximation of SDEs Convergence and mixing results are established simultaneously for a class of ergodic SDEs and their approximations by Euler's method. Eric Vigoda (University of Chicago) Thursday 31st July 17:00 A Non-Markovian Coupling for Randomly Sampling Colorings We study a simple Markov chain, known as the Glauber dynamics, for randomly sampling (proper) $k$-colorings of an input graph $G=(V,E)$ with maximum degree $\Delta$ and girth $g$. We prove the Glauber dynamics is close to the uniform distribution after $O(n\log{n})$ steps whenever $k>(1+\eps)\Delta$, for all $\eps>0$, assuming sufficiently large constant $g$ and $\Delta=\Omega(\log{n})$, where $n=|V|$. The best previously known bounds were $k>11\Delta/6$ for general graphs, and $k>1.489\Delta$ for graphs satisfying girth and maximum degree requirements. Our proof relies on the construction and analysis of a non-Markovian coupling. This appears to be the first application of a non-Markovian coupling to substantially improve upon known results. Joint work with Tom Hayes (University of Chicago). Divakar Viswanath (University of Michigan) Saturday 2nd August 17:30 Random Fibonacci sequences and the number $1.13198824...$ We will present results about a number of random recurrences including the random Fibonacci recurrence. Random Fibonacci sequences are defined by the recurrence $t_1 = t_2 = 1$ and $t_n = +/- t_{n-1} +/- t_{n-2}$ where each $+/-$ is either $+$ or $-$ with probability $1/2$. We will show that the $n$th term of a random Fibonacci sequence increases exponentially at a rate given by $1.13198824...$ Jessika Walter (Warwick) Wednesday 30th July 20:00 Averaging of Multiscale Systems Dominic Welsh (Oxford) Friday 1st August 09:30 Problems in Approximate Counting I shall survey some of the recent work on randomised approximarion schemes for quantiles relatedto the Potts and random cluster model of statistical physics. These include several classical combinatoral counting problems and also some specialisations into geometry and know polynomials. We know that unless there is a surprising collapse of the complexity hierachy amny of these quantities do not have good randomised approximation schemes. In this talk I will concentrae on problems which may turn out to be tractable Petter Wiberg (University of Warwick) Saturday 2nd August 09:00 Parameter Estimation for Partially Observed Hypo-Elliptic Diffusions In this talk we discuss parameter estimation for partially observed hypo-elliptic diffusions. We consider two questions: (i) how does data generation and parameter estimation interact; (ii) what effect does hidden data have on the estimation. The problem is examined with a combination of analysis and simulation. We conclude with two examples where a stochastic model is fitted to a large deterministic model and of estimation for nonlinear SDEs using MCMC. David Wilson (Microsoft) Friday 1st August 11:45 Mixing time of the Rudvalis shuffle We extend a technique for lower-bounding the mixing time of card-shuffling Markov chains, and use it to bound the mixing time of the Rudvalis Markov chain, as well as two variants considered by Diaconis and Saloff-Coste. We show that in each case Θ(n3 log n) shuffles are required for the permutation to randomize, which matches (up to constants) previously known upper bounds. In contrast, for the two variants, the mixing time of an individual card is only Θ(n2) shuffles. Peter Winkler (Bell Labs/Lucent) Thursday 31st July 12:15 Mixing times and card shuffling We will take a look at how some modern techniques for computing mixing time (joint work with Laci Lovasz) apply to an ancient problem: how many times should you shuffle a deck of cards? Three different shuffling models lead to two gratifying answers and one stultifying open problem.