(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.

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.

Joint work with Z. Chen and D. Marshall.

Joint work with Tomas Caraballo, Jose Langa, and James Robinson

Joint work with Martin Dyer, Haiko Muller and Leen Stougie

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.

Joint work with Steve Boyd and Lin Xiao.

Joint work with Robert P. Dobrow.

Joint work with Martin Dyer and Mark Jerrum

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.

Joint work with L. Lovasz and R. Montenegro

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.

• 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

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.

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.

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.

Joint work with Andrew Stuart and Harbir Lamba.

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.

Joint work with Ioannis Kontoyiannis

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.

Joint work with G.O. Roberts, and partially with O. Christensen.

1. Abstract results about perturbation theory for transition kernels, and effect on invariant measures.
2. The effect of time discretization on persistence and approximation of invariant measures.
3. The use of SDEs, and other Markov processes, to approximate deterministic dynamics.
4. The approximation of Markov chains with large state space by small state space models, using spectral decompositions.

• 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.

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.

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).