Modern probabilistic techniques for design and analysis of stochastic systems and networks
Monday 12th August 2013 to Friday 16th August 2013
09:00 to 09:50  Registration  
09:50 to 10:00  Welcome by John Toland, Director of the Institute  INI 1  
10:00 to 10:45 
PH Robert (INRIA Paris  Rocquencourt) On the Fluid Limits of a Resource Sharing Algorithm with Logarithmic Weights
The properties of a class of resource allocation algorithms for communication networks are presented in this talk.The algorithm is as follows: if a node of this network has x requests to transmit, then it receives a fraction of the capacity proportional to log(x), the logarithm of its current load. A fluid scaling analysis of such a network is presented. It is shown that several different times scales play an important role in the evolution of such a system. An interesting interaction of time scales phenomenon is exhibited. It is also shown that these algorithms with logarithmics weights have remarkable, unsual, fairness properties. A heavy traffic limit theorem for the invariant distribution is proved. Joint work with Amandine Veber.

INI 1  
10:45 to 11:00  Morning Coffee  
11:00 to 11:45 
D Shah (Massachusetts Institute of Technology) Optimal queuesize scaling in switched networks
We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input queued switches, wireless networks and more recently datacenters. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. Designing a scheduling policy with optimal average queuesize for switched network has been a question of interest for a while now. As the main result, we shall discuss a new class of online scheduling policies that achieve optimal scaling for average queuesize for a class of switched networks including inputqueued switches. Talk is based on work with Neil Walton (U of Amsterdam)+ Yuan Zhong (UC Berkeley).

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
13:30 to 14:15 
AR Ward (University of Southern California) Routing and Staffing to Incentivize Servers in ManyServer Systems
Coauthors: S. Doroudi, R. Gopalakrishnan, and A. Wierman
Traditionally, research focusing on the design of scheduling and staffing policies for service systems has modeled servers as having fixed (possibly heterogeneous) service rates. However, service systems are often staffed by people. Then, the rate a server chooses to work may be impacted by the scheduling and staffing policies used by the system. We present a model for such ``strategic servers'' that choose their service rate in order to maximize a tradeoff between an ``effort cost'', which captures the idea that servers exert more effort when working at a faster rate, and a ``value of idleness'', which assumes that servers prefer to be idle as much as possible. In this strategic server framework, we revisit classic scheduling and staffing questions in manyserver systems, and, in particular, we investigate the performance of the common squareroot safety staffing rule. 
INI 1  
14:15 to 14:30  Afternoon Tea  
14:30 to 15:15 
AN Rybko (Russian Academy of Sciences) Infinite Networks with Varying Topology  A MeanField Approach
We consider a model of a queuing network, containing infinite moving servers (nodes). The customers of different types are getting into the network in corresponding entrance nodes and each of the customer c has an exit node D(c) which it needs to reach. On the way to its destination the customer visits some intermediate nodes, where it stays in queues. Service times distributions depend on the customer and on the node types. After being served at any node v, the customer c is sent to the server v' which is the closest to the destination server D(c). Once it gets to D(c), it leaves the network.
The main feature of the network is that its nodes are moving. So while the customer c is waiting in the queue in some node v, this node and its destination node D(c) can move. In such networks with moving nodes new effects take place, which are encountered in the situation with stationary nodes.
My talk is based on joint paper with Francois Baccelli and Senya Shlosman. Its main result can be described as follows: we start with the definition of the class of the networks with jumping nodes. The network can be finite or infinitely extended. In order to be able to treat them we consider the meanfield version of it, which consists of N copies of the network, interconnected in a meanfield manner. We show that as N increases, the limiting object becomes NonLinear Markov Process in time. We establish the existence of the NLMP and the convergence to it. 
INI 1  
17:00 to 18:00  Welcome reception 
10:00 to 10:45 
A Anandkumar (University of California, Irvine) A Tensor Spectral Approach to Learning Mixed Membership Community Models
Coauthors: Rong Ge (Princeton), Daniel Hsu (Microsoft Research), Sham Kakade (Microsoft Research)
Modeling community formation and detecting hidden communities in networks is a well studied problem. However, theoretical analysis of community detection has been mostly limited to models with nonoverlapping communities such as the stochastic block model. In this paper, we remove this restriction, and consider a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced in Aioroldi et. al. 2008. This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. We propose a unified approach to learning these models via a tensor spectral decomposition method. Our estimator is based on loworder moment tensor of the observed network, consisting of 3star counts. Our learning method is fast and is based on simple linear algebra operations, e.g. singular value decomposition and tensor power iterations. We provide guaranteed recovery of community memberships and model parameters and present a careful finite sample analysis of our learning method. Additionally, our results match the best known scaling requirements in the special case of the stochastic block model. Related Links: http://newport.eecs.uci.edu/anandkumar/pubs/AnandkumarCommunity.pdf  manuscript 
INI 1  
10:45 to 11:00  Morning Coffee  
11:00 to 11:45 
V Borkar (Indian Institute of Technology) Miscellaneous gossip
This talk will describe several problems related to gossip and related algorithms implemented on a network. These include: convergence issues for averaging schemes on graphs and a `learning' variant, distributed ranking algorithms on graphs, opinion dynamics on graphs and its optimization and/or control, etc.

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
13:30 to 14:15 
M OlveraCravioto (Columbia University) Ranking algorithms on directed random networks
The probabilistic analysis of information ranking algorithms on directed random networks, e.g., Google's PageRank, has recently led to natural approximations based on stochastic fixedpoint equations whose explicit solutions can be constructed on weighted branching trees and whose tail behavior can be described in great detail. In this talk we present a model for generating directed random graphs with prescribed degree distributions where we can prove that the rank of a randomly chosen node does indeed converge to the solution of the corresponding fixedpoint equation as the number of nodes in the graph grows to infinity. The proof of this result is based on classical random graph coupling techniques combined with the now extensive literature on the behavior of branching recursions on trees. The results we present are applicable to a wide class of linear algorithms on directed graphs, and have the potential to be extended to other maxplus type of recursions. This is joint work with Ningyuan Chen and Nelly Litvak.

INI 1  
14:15 to 14:30  Afternoon Tea  
14:30 to 15:15 
B Prabhakar (Stanford University) Models of congestion and human response 
INI 1  
15:45 to 17:00  Open Problems Session  INI 1  
17:00 to 18:30  Poster Session 
10:00 to 10:45 
S Sanghavi (University of Texas at Austin) Clustering Sparse Graphs
Graph clustering involves the task of partitioning nodes, so that the edge density is higher within partitions as opposed to across partitions. A natural problem, it represents a first step in a wide array of applications in network analysis, community detection, recommendation systems etc.
A classic and popular statistical setting for evaluating between different solutions to this problem is the stochastic block model, also referred to as the planted partition model. In this talk, we present a new algorithm for this problem, which improves by polynomial factors over the performance of all previous known algorithms. It is based on convex optimization, and draws a connection between this problem and a different field: highdimensional statistical inference. 
INI 1  
10:45 to 11:00  Morning Coffee  
11:00 to 11:45 
A Proutiere ([KTH]) Bandit Optimisation with Large Strategy Sets: Theory and Applications
In this talk, we report recent results on bandit optimisation problems with large strategy (or decision) sets. These problems naturally arise in many contemporary applications found in communication networks, ecommerce, and recommendation systems. We address both stochastic or adversarial settings, depending on the way rewards obtained under various strategies are generated. We provide lower bounds on regret, which provide fundamental performance limits that any online algorithm cannot beat, and develop algorithms that approach these limits. Results are applied to resource allocation in wireless networks, and recommendation systems.

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
13:30 to 14:15 
S Meyn (University of Illinois) Ancillary service to the grid from deferrable loads: the case for intelligent pool pumps in Florida
Renewable energy sources such as wind and solar power have a high degree of unpredictability and timevariation, which makes balancing demand and supply challenging. One possible way to address this challenge is to harness the inherent flexibility in demand of many types of loads. We focus on pool pumps, and how they can be used to provide ancillary service to the grid for maintaining demandsupply balance. The control solution is based on the following steps: 1. A Markov Decision Process (MDP) model is introduced for an individual pool pump. 2. Using the Todorov's formulation, a randomized control architecture is proposed, motivated by the need for decentralized decision making, and the need to avoid synchronization that can lead to large and detrimental spikes in demand. 3. An aggregate model for a large number of pools is obtained from a mean field limit. 4. A linearization of the eigenvector problem in (2) provides an LTIsystem approximation of the aggregate nonlinear model, with a scalar signal as the input and a measure of the aggregate demand as the output. The final approximation is convenient for control design at the grid level. Simulations are provided to illustrate the accuracy of the models and effectiveness of the proposed control approach. 
INI 1  
14:15 to 14:30  Afternoon Tea  
14:30 to 15:15 
J Reed (New York University) High Frequency Asymptotics for the Limit Order Book
We study the onesided limit order book corresponding to limit sell orders and model it as a measurevalued process. Limit orders arrive to the book according to a Poisson process and are placed on the book according to a distribution which varies depending on the current best price. Market orders to buy periodically arrive to the book according to a second, independent Poisson process and remove from the book the order corresponding to the current best price. We consider the above described limit order book in a high frequency regime in which the rate of incoming limit and market orders is large and traders place their limit sell orders close to the current best price. Our first set of results provide weak limits for the unscaled price process and the properly scaled measurevalued limit order book process in the high frequency regime. In particular, we characterize the limiting measurevalued limit order book process as the solution to a measurevalued stochastic differential equation. We then provide an analysis of both the transient and longrun behavior of the limiting limit order book process. This is joint work with Peter Lakner and Sasha Stoikov.

INI 1  
19:30 to 22:00  Conference Dinner at Cambridge Union Society hosted by Cambridge Dining Company 
10:00 to 10:45 
R van der Hofstad ([TU Eindhoven]) Optimal flows on random graphs
We investigate minimalweight problems on the configuration model, in which flow passes through the network minimizing the total weight along edges. In practice, one is both interested in the actual weight of the minimal weight path, which represents its cost, as well as the number of edges used or hopcount, as this is often a good measure of the delay observed in the network.
We assume that the edge weights are independent continuous random variables, leading to first passage percolation on the configuration model. We then investigate the total weight and hopcount of the minimal weight path. We study how the minimal weight and hopcount depend on the structure of the edge weights as well as on the structure of the graph. Our proofs crucially rely on the connection between first passage percolation and continuoustime branching processes, which is due to the treelike nature of the configuration model. The above research is inspired by transport in realworld networks, such as the Internet. Measurements have shown fascinating features of the Internet, such as the `small world phenomenon'. The smallworld phenomenon states that typical distances in the network under consideration is small. Also, the degrees in the Internet are rather different from the degree structure in classical random graphs. Internet is a key example of a complex network, other examples being the Internet Movie Data Base, social networks, biological networks, the WWW, etc. [This is joint work with Gerard Hooghiemstra, Shankar Bhamidi, Piet Van Mieghem, Henri van den Esker and Dmitri Znamenski.] 
INI 1  
10:45 to 11:00  Morning Coffee  
11:00 to 11:45 
J Salez (Université Paris 7  DenisDiderot) Distances in large random regular networks
We study the array of pointtopoint distances in large random regular graphs equipped with exponential edgelengths. The asymptotic marginal distribution of a single entry is now wellunderstood, thanks to the work of Bhamidi, van der Hofstad and Hooghiemstra (2010). In this talk, we will show that the whole array, suitably recentered, converges in the weak sense to a rather simple infinite random array. This confirms a prediction of David Aldous.

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
13:30 to 14:15 
AE Holroyd (Microsoft Research) Selforganizing cellular automata
Cellular automata display an extraordinary range of behavior, ranging from the very simple to the apparently chaotic, with many cases in between. Perhaps the most interesting rules are those that yield multiple behavior types from different initial conditions  this is common even for onedimensional rules started from finitelysupported seeds. If a rule yields chaos from some initial conditions, it is tempting to conclude by analogy with the second law of thermodynamics that chaos should be prevalent from almost all initial conditions. For a certain natural class of rules, we prove that the opposite holds: typical (i.e. random) initial seeds selforganize into predictable (but nontrivial) evolution, while exceptional seeds generate more complicated behavior, including chaos. The key technique is the application of percolation arguments to the highly nonindependent setting of spacetime configurations of cellular automata.
Joint work with Janko Gravner. 
INI 1  
14:15 to 14:30  Afternoon Tea  
14:30 to 15:15 
JB Martin (University of Oxford) Forest fires and coagulationdeletion processes
Consider the following extension of the ErdosRenyi random graph process; in a graph on $n$ vertices, each edge arrives at rate 1, but also each vertex is struck by lightning at rate $\lambda$, in which case all the edges in its connected component are removed. Such a "meanfield forest fire" model was introduced by Rath and Toth. For appropriate ranges of $\lambda$, the model exhibits selforganised criticality. We investigate scaling limits, involving a multiplicative coalescent with an added "deletion" mechanism. I'll mention a few other related models, including epidemic models and "frozen percolation" processes.

INI 1  
15:45 to 17:00  Open Problems Session  INI 1  
17:00 to 18:30  Poster Session 
10:00 to 10:45 
M Mandjes (Universiteit van Amsterdam) Timescaling results for Markov modulated infiniteserver systems and OU processes
Coauthors: J. Blom (CWI), K. de Turck (Ghent), O. Kella (Jerusalem), D. Anderson (Wisconsin), H. Thorsdottir (CWI), G. Huang (Amsterdam), P. Spreij (Amsterdam)
In this talk I'll consider an infiniteserver queue whose input is modulated by a Markovian background process, with a focus on the analysis of the number of customers in the system, both in the centrallimit and the large deviations regime. In the scaling that we study, the background process is sped up by a factor N^f, while the arrival rate are scaled by N. Interestingly, in the CLT regime crucially different results come out for f > 1 and for f 
INI 1  
10:45 to 11:00  Morning Coffee  
11:00 to 11:45 
J Blanchet (Columbia University) Tolerance Enforced Simulation for Stochastic Differential Equations via Rough Path Analysis
Consider a stochastic differential equation (SDE) driven by Brownian Motion which possesses a strong solution in the interval [0,t]. Given any tolerance error, say epsilon, defined in advance, we explain how to simulate a piecewise linear path which approximates the underlying SDE in uniform norm in [0,t] with an error less than epsilon with probability one. The technique, as we shall explain, takes advantage of continuity estimates, studied in the theory of rough paths, of the ItoLyons map defining the underlying the SDE. (This presentation is based on joint work with Xinyun Chen and Jing Dong.)

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
13:30 to 14:15 
A Ganesh (University of Bristol) On the secure connectivity of wireless sensor networks
We consider a model of a wireless sensor network in which nodes are distributed uniformly at random over a unit square, and can communicate other nodes within a ?xed radius. This is the wellknown random geometric graph model. In addition, each node is assigned a subset of cryptographic keys chosen uniformly at random from a key pool. Two nodes can communicate only if they are within range of each other, and possess at least one common key. We establish a connectivity threshold for these random graph models. This resolves a conjecture of Osman Yagan. Joint work with Bikash Dey, Santhana Krishnan and D. Manjunath.

INI 1  
14:15 to 14:30  Afternoon Tea  
14:30 to 15:15 
H Thorisson (University of Iceland) Unbiased shifts of Brownian Motion
Let $B = (B_t)_{t\in\mathbb{R}}$ be a twosided standard Brownian motion. Let $T$ be a measurable function of $B$. Call $T$ an \emph{unbiased shift} if $(B_{T+t}B_T)_{t\in\mathbb{R}}$ is a Brownian motion independent of $B_T$. We characterize unbiased shifts in terms of allocation rules balancing local times of $B$. For any probability distribution $\nu$ on $\mathbb{R}$ we construct a nonnegative stopping time $T$ with the above properties such that $B_T$ has distribution $\nu$. In particular, we show that if we travel in time according to the clock of local time at zero we always see a twosided Brownian motion. A crucial ingredient of our approach is a new theorem on the existence of allocation rules balancing jointly stationary diffuse random measures on $\mathbb{R}$. We also study moment and minimality properties of unbiased shifts.

INI 1 