August 26-28, 2008
EURANDOM 1998-2008
A Random Tour through a Decade of Research

ABSTRACTS

Samuli Aalto (TKK Helsinki University of Technology, FIN)

Recent sojourn time results for Multilevel Processor-Sharing scheduling disciplines

Multilevel Processor-Sharing (MLPS) disciplines refer to a family of age-based scheduling disciplines introduced already decades ago. A time-discretized version of an MLPS discipline is applied in the scheduler of the traditional UNIX operating system. In recent years, MLPS disciplines have been used to study the way that packet level scheduling mechanisms impact the performance perceived at the flow level in the Internet. Inspired by this latter application, many new sojourn time results have been discovered for these disciplines in the context of the M/G/1 queue. In this presentation, we highlight some of these new results. In addition, we point out some intriguing open problems for further research.

Nicola Armstrong (Netherlands Cancer Institute, NL)

Statistics in Biology

In the biological sciences, the advent of microarray technology changed the way experiments were done. Microarrays were the first mainstream high-throughput technology, generating enormous amounts of data for both the biologist and the statistician to understand. Over the course of the last six years the statistical focus of microarray experiments has shifted. Gene expression microarrays are now an accepted part of the biologists toolbox. One of the main statistical challenges in the coming years is to integrate data from a wide variety of sources, including microarrays, so that complex biological systems, such as cancer, may be better understood.

Federico Camia (Vrije Universiteit Amsterdam, NL)

Scaling Limits of Two-Dimensional Percolation: an Overview

Ten years ago, EURANDOM was born. Roughly at the same time, Oded Schramm invented what is now called the Shcramm-Loewner Evolution (SLE), which was to revolutionize the study of two-dimensional critical phenomena. Shortly after, Stas Smirnov proved the conformal invariance of the scaling limit of critical percolation. That opened the door to the use of SLE in the study of critical percolation. I will describe some of the progress that followed, after a brief introduction to SLE and conformal invariance in critical phenomena.

Dee Denteneer (Philips Research, NL)

IEEE 802.11s and the Philosophers' problem

IEEE 802.11s is the task group in the IEEE that is in the process of
standardising wireless mesh networks. A hot topic in this standardisation effort concerns
the need for additional medium access functionality beyond the basic IEEE 802.11
carrier sense multiple access with collision avoidance (CSMA/CA).
In this talk we discuss the connection between CSMA/CA and Dijkstra's
classical Philosophers' problem, and its implications for the debate inside IEEE 802.11s.
In an alternative view of this talk, we state some new mathematical models, theorems, and
conjectures related to the Philosophers' problem.

Peter Grünwald (CWI, NL)

Entropy Concentration and the Empirical Coding Game

Suppose one is given some constraints concerning the moments of a distribution, and one somehow wants to guess what that distribution actually is. The Maximum Entropy Principle states that the best guess is the distribution that maximizes the Shannon entropy subject to the given constraints. While this principle is widely used by physicists, biologists and econometrists, its justification has always been problematic. A pleasant justification is due to Topsoe
(1979): when used for prediction purposes, the maximum entropy achieves the minimax loss in a certain prediction game. Here we study whether this result extends to the more realistic situation where the constraints are empirical averages of statistics of data, rather than moments of a hypothesized distribution. Based on random walk theory, we prove the surprising result that this is only the case if less than three constraints are given.

Frank Kelly (University of Cambridge, UK)

Models of routing and congestion control

The evolution of the Internet and the current deployment of wireless networks are generating exciting new challenges for mathematical modellers.
This talk will give an overview of how probabilistic models can be used to provide insight into methods of routing and congestion control in communication networks.

Johan van Leeuwaarden (Technische Universiteit Eindhoven, NL)
Joint work with A.J.E.M. Janssen.

Back to the roots of the M/D/s queue and the works of Erlang, Crommelin, and Pollaczek  

A.K. Erlang introduced the M/D/ queue in 1917, while F. Pollaczek and C.D. Crommelin formalized the theory using complex analysis and transforms. Let  denote the stationary probability of experiencing no waiting time in the M/D/ queue with arrival rate  and service requirement 1. We use  as a vehicle to give an overview of some of the results we obtained over the last years, including explicit characterizations of the roots, the derivation of infinite series fromexpressions in terms of roots using Fourier sampling, and heavy-traffic limits obtained from square-root staffing. We propose to call  the Erlang D formula, for which several new results are presented and compared to the results of Pollaczek.

Franz Merkl (University of Munich, D)
Joint work with A. Öry and S. Rolles

The “magic formula” for linearly edge-reinforced random walks

Linearly edge-reinforced random walk on a finite graph is a mixture of reversible Markov chains with an explicitly known mixing measure. In the talk, a new proof of this fact will be described. Furthermore, some consequences of the description as a mixture will be given, including, among others, recurrence properties of linearly edge-reinforced random walk on various graphs.

Frank Redig (Universiteit Leiden, NL)

Time evolution of Gibbs measures

We discuss the Gibbsian or non-Gibbsian nature of a Gibbs measure evolved under a stochastic dynamics. We will especially highlight the results obtained at EURANDOM on this subject, as well as current research inspired by these results.

Gordon Slade (University of British Columbia, CA)

Self-Avoiding Walks

Random walks are well understood by now. However, if we require a random walk not to intersect itself, so that it is a self-avoiding walk, then it is much more difficult to analyse and many of the important mathematical problems remain unsolved. This lecture will give an overview of some of what is known about self-avoiding walks, including some old and some more recent results, using methods that touch on combinatorics, probability, and statistical mechanics.

 Jian Zhang (Institute of Maths, Statistics and Actuarial Sci. University of Kent at Canterbury, UK)

FDR Estimation and Stochastic Approximation Algorithms

Testing of multiple hypotheses has attracted considerable interest recently due to the availability of large datasets. Even though the test statistics are strongly dependent in some applications, most work on this subject are based on the assumption of independence between test statistics. Here we propose a new method for estimating the false discovery rate (FDR) of multiple hypothesis tests. In our method, the density of test scores is appromimated by a family of exponential power distributions. To avoid the assumption of independence, the unknown parameters in the family are estimated by minimizing the Kullback-Leibler distance between the unknown density and its estimator, which is equivalent to solving a system of estimating equations. Unlike the regular estimating equations, the estimating functions here might not be locally Lipschitz continuous. We consider a class of stochastic approximation (SA) algorithms for solving these irregular estimating equations. We show the convergence of these SA algorithms under the condition that the estimating functions in the equations are bounded and continuous almost everywhere. Some numerical results are provided.

Last updated on 23-02-2009
Maintained by coolen@eurandom.tue.nl