BRG meeting

October 13 & 14, 2005

EURANDOM, Eindhoven, The Netherlands

#### ABSTRACTS

Ellen Baake
Joint work with Robert Bialowons.

Ancestral lines in the Moran model with selection

We consider the ancestral lines of {\em single} individuals (i.e., genealogies of samples of size 1) in the Moran model with mutation and selection. To this end, we use analytical results of Fearnhead (2002) to determine the explicit properties, and parameter dependence, of the ancestral distribution of types, and its relationship with the stationary distribution in forward time.

Matthias Birkner

A conditional large deviation principle and size biasing for linear systems

For linear systems (e.g. in the sense of Chapter IX of Liggett (1985), also for "more continuous" relatives like the parabolic Anderson model as well as "more discrete" relatives like the normalized partition function for directed polymers in random environment) it is well known that there are no non-trivial equilibria in dimension 1 and 2, whereas in dimension $\ge 3$, sufficient criteria for existence can easily obtained by using $L^2$ bounds. On the other hand, we strongly suspect that there is a regime of heavy-tailed equilibria, which can not be explored via $L^2$ theory.

In all these cases, there is a stochastic representation of the locally size-biased distribution, which in principle yields a sharp criterion for persistence vs. local extinction. The analysis of this representation leads naturally to a conditional large deviation problem. We will discuss some recent progress as well as many remaining challenges.

Michael Eckhoff

Negative associations of the random connected graph

It is a numerically confirmed conjecture that two edges under the uniform distribution on connected subgraphs (or on forests) of a given connected graph are negatively associated. We shall present a proof of this property.

Friedrich Goetze

Random spectral approximations

Abstract: TBA

Gregory Maillard

Parabolic Anderson model with symmetric simple exclusion branching

We study intermittency for the Parabolic Anderson Model when the diffusion is driven by a constant $\kappa$ and the branching is induced by a simple exclusion process with symmetric random walk kernel. We consider the annealed Lyapunov exponents and we show that they display an interesting dependence on $\kappa$, with qualitatively different behaviours in different dimensions.

Ralph Neininger

Periodicities in search trees and random fragmentations

In the stochastic analysis of algorithms and data structures the performance (running time, space requirement) of algorithms for fundamental problems in computer science is measured by characteristic quantities such as key comparisons and depths, height or number of nodes in trees. These characteristics become random variables either if the algorithm is randomized or by considering a random input for (deterministic) algorithms or data structures. Then, as the size of the input tends to infinity, these characteristic quantities are studied asymptotically with respect to expectations, variances, limit laws, and tail bounds.

While for many parameters of random trees limit laws can be obtained after renormalization, recently, various other parameters have been shown not to converge after standardization due to periodic behavior of higher moments. We discuss this problem at the size of random m-ary search trees. For a related random tree fragmentation process we give a complete characterization of its limit behavior including normal limit laws as well as periodic limiting behavior.

Peter Pfaffelhuber
This project is joint work with Anton Wakolbinger

All about Eve. On the evolution of the time to the MRCA

In an ideal population of constant size all individuals alive at time 0 have a most recent common ancestor (MRCA). As the population evolves at some time in the future there will be a new MRCA. But when will this time be and when will the new MRCA have lived? These questions can be answered using Kingman's Coalescent, Polya urns und the lookdown process.

Silke Rolles
The talk is based on a joint paper with Franz Merkl

Linearly edge-reinforced random walk

Edge-reinforced random walk on any finite graph has the same distribution as a random walk in a random environment, where the environment is given by random, but time-independent weights on the edges. This result is well-known. In the talk we will present the result for arbitrary infinite graphs. The proof relies on a comparison with Polya urns. This comparison yields some bounds for the random environment.

Anita Winter
Joint work with Andreas Greven and Vlada Limic

Rescaling the spatial coalescent on $Z^2$: A genealogy approach to diffusive clustering

We consider the spatial coalescent on the two-dimensional lattice, that is, a partition-valued `particle' system in which partition elements migrate between lattice sites as independent random walks while the partition elements within a site follow the Kingman coalescent dynamics.

We show that the suitably rescaled spatial coalescent converges to a Kingman coalescent. This gives a stronger version of results obtained by Cox and Griffeath for the related coalescing random walks.

A key technical ingredient will be a Hausdorff--Gromov type distance to metrize coalescent trees which are isometry classes of ultra-metric spaces equipped with a probability measure. A handy convergence criterion is presented.