Stochastic networks and stochastic geometry
A conference dedicated to François Baccelli on his 60th birthday
Paris, IHP, Hermite Amphitheater, January 12 - 14, 2015
| Speakers | Program | Directions | Contact | Photos | Participants |
Organized by Inria/ENS
Organizing committee: Bartek Blaszczyszyn (DI ENS, Inria), Charles Bordenave (IMT Toulouse, CNRS) , Bruno Gaujal (LIG Grenoble, Inria), Marc Lelarge (DI ENS, Inria) and Jean Mairesse (LIP6, CNRS)
Sponsors:
| Time | Speaker | Talk | |
|---|---|---|---|
| Monday, January 12 | |||
| 8:30 | Registration | ||
| 9:00 | Brigitte Plateau | How François met and lived Stochastic Network, Contributions from his scientific family | Speech |
| TBA | |||
| 9:45 | Sergei Foss | On a regenerative structure that may depend both on the past and on the future | Abstract |
|
I will present conditions on discrete-time processes that lead to (asymptotically) regenerative structure that may depend on both the past and the future, with a number of examples. The talk is partly based on the joint paper with S. Zachary, AdvAP (2013). |
|||
| 10:30 | Break | ||
| 11:00 | Laurent Massoulié | Community detection and Ramanujan graphs: A proof of the "spectral redemption conjecture" | Abstract Slides |
|
Community detection consists in clustering graph nodes into groups with homogeneous properties. When the observed random graph is drawn from the stochastic block model (a multi-type version of the Erdös-Rényi model), phase transitions on feasibility of community detection occur. The spectral redemption conjecture, formulated in [1], states that right above the transition point, community detection can be made on the basis of the leading eigenvectors of the so-called non-backtracking matrix. In this talk I will present our proof of this conjecture. In the process Ramanujan-like properties of random graphs will be discussed. [1] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborova, P. Zhang, "Spectral redemption: clustering sparse graphs". Joint work with Charles Bordenave and Marc Lelarge. |
|||
| 11:45 | Philippe Bougerol | RSK, product of matrices and random walks | Abstract |
|
The Robinson Schensted Knuth insertion algorithm is interpreted as a product of max-plus matrices. This leads to explicit computations for some random walks on groups. |
|||
| 12:30 | Lunch Break | ||
| 14:15 | Pierre Brémaud | Spectral measures of point processes | Abstract Slides |
|
I shall review the computational aspects of the spectral theory of point processes and propose some topics of further research. The talk is mostly based on joint work with Laurent Massoulié. |
|||
| 15:00 | Break | ||
| 15:30 | Jean-Yves Le Boudec | Stochastic analysis of real and virtual storage in the smart grid | Abstract Slides |
|
The electrical grid of the future will require more storage to compensate for the intermittency of distributed generators (such as solar, wind, combined heat and power). Storage will be real (batteries, water reservoirs) or virtual (demand response). In this talk we analyze the impact of storage of the real electricity markets, using several stochastic models. Joint work with Nicolas Gast, Alexandre Proutière and Dan Tomozei. |
|||
| 16:15 | Darryl Veitch | Topology inference: escaping the spatial independence straightjacket | Abstract Slides |
|
Network tomographic methods typically rely on a strong assumption of spatial independence to ensure that the inference problem is both well-posed and tractable. In tree-based network tomography for instance, independence over links is assumed for each of the loss, delay, and topology branches of the literature. We introduce "Jump Independent" (JI) models, which possess spatial dependency which is both rich and physically meaningful, and yet still allows the recovery of the topology based on measurements at leaves. We first study the underlying system identifiability problem (assuming an exact knowledge of the marginal at leaves), and then the practical estimation problem from a finite number of leaf measurements. This is joint work with Rhys Bowden, and was inspired by an inference problem in ADSL networks proposed by François Baccelli. |
|||
| Tuesday, January 13 | |||
| 9:00 | Frank Kelly | Efficient advert assignment | Abstract Slides |
|
In current Ad-auctions, there is an information asymmetry between the platform and advertisers: the platform typically knows more than an advertiser about the search being conducted, such as information about the searcher. Hence the platform can potentially choose prices and an allocation that depends on the platform's additional information. In contrast, the advertiser has to rely on more coarse-grained information, perhaps just the search terms of a query together with a crude categorization of the searcher. We show that the information asymmetry can be used to develop a simple mechanism for advert assignment and pricing that incentivizes truthful bidding and encourages convergence to a unique Nash equilibrium that is socially optimal. Joint work with Peter Key (Microsoft) and Neil Walton (Amsterdam). |
|||
| 9:4S | Eitan Altman | Branching processes with non-Markovian immigration | Abstract Slides1 Slides2 |
|
We introduce a class of vector valued processes that have the form $ Y_{n+1} = A_n ( Y_n ) + B_n $. $B_n$ is assumed to be stationary ergodic and $A_n$ is assumed to have a divisibility property. This class includes linear stochastic difference equations as well as multi-type branching processes (with a discrete or with a continuous state space). We derive explicit expressions for the probability distribution as well as for the two first moments of the state vectors at the stationary regime. We then apply this approach to various queueing models as well as to epidemic models that arise in delay tolerant networks. The paper summarizes the fruits of a collaboration with Dieter Fiems inspired by the work of Françcois Baccelli on non Markovian queueing analysis. |
|||
| 10:30 | Break | ||
| 11:00 | Kavita Ramanan | Hydrodynamic limits of randomized load balancing models | Abstract Slides |
|
We establish mean-field limits for a class of randomized load balancing models in networks with many servers in the presence of general service distributions. A key tool is the representation of the process in terms of interacting measure-valued processes and the identification of a system of PDEs that capture key performance measures of the system. This is joint work with Mohammadreza Aghajani. |
|||
| 11:45 | David McDonald | Yaglom limits can depend on the starting state | Abstract Slides |
|
We construct a simple example, surely known to Harry Kesten, of an $R$-transient Markov chain on a countable state space $S \cup \{ \delta \} where $\delta$ is absorbing. The transition matrix $K$ on $S$ is irreducible and strictly substochastic. We determine the Yaglom limit, that is, the limiting conditional behavior given non-absorption. Each starting state $x \in S$ results in a different Yaglom limit. Each Yaglom limit is an $R^{-1}$-invariant quasi-stationary distribution where $R$ is the convergence parameter of $K$. Yaglom limits that depend on the the starting state are related to a nontrivial $R^{-1}$-Martin boundary. |
|||
| 12:30 | Lunch Break | ||
| 14:15 | Jean Walrand | Scheduling tasks with precedence constraints on multiple servers | Abstract |
|
We consider the scheduling of jobs modeled as directed acyclic graphs of tasks. Multiple servers can each serve a subset of the tasks. The processing rate of a task by a server depends on the speed of the server and the complexity of the task. We derive maximal throughput policies that do not require detailed statistics of the tasks. We discuss the scalability of the policies. Joint work with Ramtin Pedarsani (UC Berkeley) and Yuan Zhong (Columbia University). |
|||
| 15:00 | Break | ||
| 15:30 | Takis Konstantopoulos | Finitely exchangeable probability measures and their extensions | Abstract Related article1 Related Article2 |
|
Whereas de Finetti's theorem characterizes exchangeable probability measures on infinite product spaces under some topological assumptions, analogous results for finite products have received less attention. We give a short proof of the theorem stating that finitely exchangeable product measures are "signed mixtures" of product measures and then proceed in giving necessary and sufficient conditions for extendibility of exchangeable probability measures. This is joint work with Linglong Yuan. |
|||
| 16:15 | Armand Makowski | A tale of degrees | Abstract |
|
In random graph models, the degree distribution of individual nodes should be contrasted with the degree distribution of the graph, i.e., the usual fractions of nodes with given degrees. We explore this difference in the context of the search of models displaying a power law degree distribution. Some easy results and a surprise! |
|||
| Wednesday, January 14 | |||
| 9:00 | Günter Last | Invariant transports of random measures and the extra head problem | Abstract Slides |
|
The extra head problem requires finding a head in an infinite sequence of independent fair coin tosses, without changing the (joint) distribution of the rest of the sequence. This problem was solved by Liggett (2001) by a nice matching procedure. Closely related allocation and matching problems for Poisson processes were studied by Holroyd and Peres (2005) and by Holroyd, Pemantle, Peres and Schramm (2008). In this talk we shall discuss matching and embedding problems for a two-sided standard Brownian motion and explain the close relationship of all these matching problems with invariant transports and Palm measures of stationary random measures. Significant parts of this talk are based on joint work with Peter Mörters (Bath) and Hermann Thorisson (Reykjavik). |
|||
| 9:4S | Sergei Zuyev | Segment recombinations and random sharing models | Abstract Slides1 Slides2 |
|
Consider a renewal point process on the line and divide each of the segments it defines in a proportion given by i.i.d. realizations of a fixed distribution supported by [0,1]. Now recombine the obtained pieces of the segments by joining the neighbouring ones, so that the division points are now the separation points between the new segments. We ask ourselves for which renewal processes and which division distributions, the division points follow the same renewal process distribution? An evident case is that of equal length segments and a degenerate division distribution. Interestingly, the only other possible case is when the increments of the renewal process is Gamma and division points are Beta-distributed. In particular, the division points of a Poisson process is again Poisson, if the dividing distribution is Beta(r,1-r) for some 0<r<1. We show that a similar situation arises in the random sharing model when a countable number of "households" exchange randomly distributed parts of their "wealth" with neighbours. More generally, a Dirichlet distribution arises in these models as a fixed point distribution preserving independence of the wealths at each step. We also show that the fixed points of the random sharing are attractors meaning that starting with a non-equilibrium configuration distribution iterations will converge to the equilibrium. |
|||
| 10:30 | Break | ||
| 11:00 | Jean Bolot | A walk up the stack: From networks, to users and the data they generate | Abstract Slides |
|
Many of us have moved our research agendas "up the stack" over the years. We will take a walk up that stack, from networks to users and the data they generate, to self-driving cars and augmented humans, focusing on topics related to François. |
|||
| 11:45 | William Massey | The dynamics of queueing transience | Abstract |
|
This talk discusses how random sample path behavior combines with asymptotic analysis to give us insight into the evolution of dynamic rate queueing systems. |
|||
| 12:30 | Lunch Break | ||
| 14:15 | Venkat Anantharam | The Shannon capacity of a power-harvesting transmitter over an additive noise channel | Abstract Slides |
|
A power-harvesting transmitter has a battery of limited capacity, and gathers energy from the environment while it operates. The study of the Shannon capacity of communication with such a transmitter over an additive noise channel requires an understanding of how to design transmission codebooks subject to the requirement that each transmitted codeword meets the available energy budget at every moment during the course of the transmission. In this talk, we provide upper and lower bounds on this Shannon capacity which are tight enough to give a good understanding of what it is in both the low noise power and the high noise power regime, focusing on discrete time models with additive Gaussian noise, and with the amount of energy harvested per symbol time assumed to be a constant. From a mathematical point of view, the problem is one of high dimensional geometry, where the high dimensional unit balls of traditional Shannon theory are replaced by certain high dimensional polytopes defined by the real time nature of the constraints on the available energy. A study of Steiner's formula in high dimensions with a viewpoint that parallel large deviations theory is central to the development of our results. Joint work with Varun Jog. |
|||
| 15:00 | Conference closing by François Baccelli | Speech | |