Probability and Stochastic Networks

Leader of the group Probability and Stochastic Networks (PNA2): Rob van der Mei

Many real-life systems and processes are dynamic and essentially stochastic. Examples can be found in areas like communication and information systems, biology, geo-physics, finance and economics, production systems, maintenance, logistics and transportation. PNA2 develops and studies stochastic and statistical models that yield fundamental understanding and enable control and optimization of such systems. Analysis of these models relies on techniques from fundamental probability theory, queueing theory, stochastic scheduling, spatial stochastics and stochastic geometry.

The research group is internationally well-known and embedded in different national and international research communities. The group organizes two nationally oriented regular seminars: (1) the Queueing Colloqium (twice a year), and (2) the bi-weekly Spatial Stochastics seminar, which act as broad and integrating forums for researchers and practitioners in the field of fundamental and applied probability theory.

The group covers a broad range of research areas in (applied) probability theory, providing a unique opportunity for synergy between the different fields of expertise. The goals for the next few years are to further strengthen the national and international research reputation of the group and to provide an active and stimulating environment for young talented researchers. In addition, the group aims to actively transfer knowledge to society through publications and presentations in leading international journals and conferences, as well as by lecturing at universities, consultancy for industry and governmental institutes and teaching courses for companies.

The team aims at striking a good balance in performing both fundamental and applied research. The group currently consists of six senior researchers, and a seventh will join in the fall of 2008.

To structure the range of research areas the group is subdivided in three main areas:

Vacancy
None

Staff members
Rob van den Berg, Kacha Dzhaparidze, Marie-Colette van Lieshout, Rob van der Mei, Rudesindo Núñez-Queija, Vladas Sidoravicius, Bert Zwart

Seconded staff members
Urtzi Ayesta, Rene Bekker, Sandjai Bhulai, Sem Borst, Matthieu Jonckheere, Michel Mandjes, Frank Redig, Werner Scheinhardt, Harry van Zanten.

Post docs
Ohad Perry, Florian Simatos.

PhD students
Arnoud den Boer, Joost Bosman, Maria Frolkova, Gerard Hoekstra, Demeter Kiss, Kerem Turkyilmaz, Chretien Verhoef, Ran Yang, Bo Zhang.

Master students
Oscar Kanters, Jan Pieter Dorsman (from jan 2010)

Research seminars

Recent PhD theses

  • Maaike Verloop. Scheduling in Stochastic Resource-Sharing Systems, 2009 Eindhoven University of Technology.
  • Wemke van der Weij. Queueing Networks with Shared Resources, 2009 VU University Amsterdam.
  • Regina Egorova. Sojourn time tails in processor-sharing systems, 2009 Eindhoven University of Technology.
  • Pascal Lieshout. Queueing Models for Bandwidth-Sharing Disciplines, 2008 University of Amsterdam. 
  • Ton Dieker. Extremes and fluid queues, 2006 University of Amsterdam. 
  • Rene Bekker. Queues with state-dependent rates, 2005 Eindhoven University of Technology.
Recent awards
  • Bert Zwart received the Erlang Prize from the Institute for Operations Research and Management Sciences (INFORMS) in 2008. The Erlang Prize is to honour the best researcher under the age of 36 who has contributed significantly to applied probability. Zwart is the first person outside the United States to win this prize.
  • J. van den Berg and V. Sidoravicius received highly prestigious NSF PIRE (Programms in Research and Education) grant, creating a network linking CWI, Courant Institute, ENS-Paris and IMPA-Rio de Janeiro (organized jointly with C. Newman) in 2007.
  • R.D. van der Mei was nominated for best-paper award at Performance-2007 conference, for the paper 'Polling models with renewal arrivals: a new method to derive heavy-traffic asymptotics' (with E.M.M. Winands).
  • Pascal Lieshout won best student paper award for his paper “GPS scheduling: selection of optimal weights and comparison with strict priorities” at ACM Sigmetrics / Performance 2006, Saint Malo, France, 2006.
  • Maaike Verloop was awarded VVS-price for the best Master thesis in the field of Operations Research and Statistics in the Netherlands, 2005.
  • Sem Borst was awarded the Van Dantzig price for his ground-breaking research in the field of Statistics and Operations Research (jointly with Mark van der Laan), 2005.

Publications of this group
Publications of Probability and Stochastic Networks in the CWI repository

Cooperation partners
Partners in the group of Probability and Stochastic Networks

Description of the three research areas

Performance analysis of information and communication systems (PNA2.1)

Information and communication systems continue to expand rapidly in terms of traffic volume, the number of users, as well as the range of applications. The use of both the Internet and wireless services has experienced an explosive growth. Network operators and service providers anticipate further expansion, fueled by the emergence of all-optical networking as well as the convergence of wireless and Internet access, along with a fundamental trend towards service integration. Future information and communication systems are expected to accommodate a variety of new applications with a diverse range of Quality-of-Service (QoS) requirements.
These observations have raised the need for the development and analysis of quantitative stochastic models to predict and control the QoS of information and communication systems, including wired and wireless networks and large-scale distributed systems. Our main focus is on the development and analysis of queueing theoretic models and methods to predict and control the performance experienced by the user. In addition, we focus on network economics, addressing problems related to pricing and cost allocation in communication systems.

Some publications:

  1. S.C. Borst, R. Nunez-Queija and A.P. Zwart (2006). Sojourn time asymptotics in processor-sharing queues. Queueing Systems 53, 31-51.
  2. I.M. Verloop, S.C. Borst, R. Nunez-Queija (2006). Delay-based scheduling in bandwidth-sharing networks. In: Proc. ACM Sigmetrics / Performance 2006 Conference, Saint-Malo, France, June 28-30, 365-366.
  3. R.D. van der Mei and E.M.M. Winands (2007). Polling models with renewal arrivals: a new method to derive heavy-traffic asymptotics. Performance Evaluation 64, 1029-1040.
  4. B.M.M. Gijsen, R.D. van der Mei, P. Engelberts, J.L. van den Berg and K.M.C. van Wingerden (2006). Sojourn-time approximations in queueing networks with feedback. Performance Evaluation 63, 743-758.
  5. P.M.D. Lieshout, M.R.H. Mandjes, S.C. Borst (2006). GPS scheduling: selection of optimal weights and comparison with strict priorities. In: Proc. ACM Sigmetrics / Performance 2006 Conerence., Saint-Malo, France, June 28--30, 75—86 (received best student paper award).

Probability and spatial stochastics (PNA2.2)

During the last ten years the study of random processes in a spatial context has rapidly intensified. On one hand, there is an increasing motivation to understand such processes, for instance in chemistry and physics (e.g., models of magnetization, polymerization), earth and life sciences (epidemics, nerve systems, forest fires) and engineering (wireless communication networks). On the other hand, these processes give rise to very interesting mathematical problems requiring a rich variety of ideas and techniques. For instance, one of the main breakthroughs in this field, the introduction, development and applications of Stochastic Loewner Evolutions, involves a beautiful mixture of conformal mapping theory, stochastic analysis and interesting combinatorial-geometric arguments.
Much work by PNA2 members on random spatial processes concentrates on various models with a percolation-like flavor; in particular forest-fire models, models of epidemics, certain models of the spread of fluid through a random medium (invasion percolation), and systems of coalescing, randomly moving particles. The group is also active in fundamental research on spectral analysis of random fields, such as fractional Brownian motions, that are (e.g.) used to model traffic phenomena in communication networks with long-range dependence. An important method in the description of such processes is that of Krein's spectral theory of vibrating strings.

Some publications:

  1. J. van den Berg and B.N.B. de Lima. Linear lower bounds for $\delta_c(p)$ for a class of 2D self-destructive percolation models. Random Structures and Algorithms 34, 520-526, Wiley (2009). 
  2. J. van den Berg and H. Kesten (2002). Randomly coalescing random walks in dimension d ≥ 3. In and Out of Equilibrium (V. Sidoravicius, ed.), Birkhäuser, 1-45.
  3. J. van den Berg and R. Brouwer (2006). Self-organized forest-fires near the critical time. Communications in Mathematical Physics 67, 265-277.
  4. K. Dzhaparidze, H. van Zanten and P. Zareba (2006). Representations of isotropic Gaussian random fields with homogeneous increments. J. Appl. Math. Stoch. Anal., Art. ID 72731.
  5. K. Dzhaparidze and H. van Zanten (2005). Krein's spectral theory and the Paley-Wiener expansion for fractional Brownian motion. Ann. Probab. 33, no. 2, 620-644.

Stochastic geometry (PNA2.3)

Stochastic geometry is concerned with random geometric structures, ranging from simple points or line segments to arbitrary closed sets. Although it has roots in geometric probability and integral geometry, the modern theory of random sets was developed in the seventies, independently by David Kendall in Cambridge and Georges Matheron in Fontainebleau with important contributions from the German school around Professors Mecke and Stoyan. Stochastic geometry techniques can be applied in a wide range of fields for instance image analysis, telecommunication networks, forestry, and environmental research.

Some publications:

  1. M.N. van Lieshout (2000). Markov Point Processes and their Applications (London/Singapore: Imperial College Press/World Scientific Publishing).
  2. T. Schreiber and M.N.M. van Lieshout. Disagreement loop and path creation/annihilation algoritms for planar Markov fields with applications to image segmentation. Scandinavian Journal of Statistics, to appear.
  3. M.N.M. van Lieshout. Applications of stochastic geometry in image analysis. Stochastic geometry: Highlights, interactions and new perspectives, W.S. Kendall and I.S. Molchanov (Eds.), 427-450. Oxford: Clarendon Press, 2009.
  4. M.N.M. van Lieshout. Depth map calculation for a variable number of moving objects
    using Markov sequential object processes. IEEE Transactions on Pattern Analysis and Machine Intelligence 30, 1308-1312, 2008.
  5. M.N. van Lieshout (2006). Maximum likelihood estimation for random sequential adsorption. Advances in Applied Probability (SGSA) 38, 889-898.
  6. R. Kluszczynski, M.N. van Lieshout and T. Schreiber (2006). Image segmentation by polygonal Markov fields. To appear in Annals of the Institute of Statistical Mathematics. Published online, August 19, 2006.
The group PNA2 is part of the cluster Probability, Networks and Algorithms (PNA).