### Semimartingale Reflecting Brownian Motion in Two Dimensions: Exact Asymptotics for the Stationary Distribution

Monday June 18 2012, 09:30-10:30

Monday June 18 2012, 09:30-10:30

We consider a two-dimensional semimartingale reflecting Brownian motion (SRBM) in the nonnegative quadrant. Assume that the SRBM has a unique stationary distribution. We characterize the exact tail asymptotic of its marginal stationary distribution along each direction $c$ in the quadrant.

A key step in our analysis is to establish the convergence domain of the moment generating function of the two-dimensional stationary distribution. The line in direction $c$ intersects the boundary of the convergence domain at one point, and that point uniquely determines the decay rate $\alpha$ for the marginal stationary distribution. The one-dimensional moment generating function of the marginal distribution has a singularity at $\alpha$. Using analytic extension in complex analysis, we characterize the precise nature of the singularity there. Using that characterization and complex inversion techniques, we show that the tail distribution of the marginal stationary distribution has the exact asymptotic of the form $bx^\kappa \exp(-\alpha x)$ as $x$ goes to infinity, where $b$ is a positive constant and $\kappa$ takes one of the values $-3/2$, $ -1/2$, $0$, or $1$.

We will also review a variational problem (VP) that is associated with the SRBM and present a connection between the VP and the convergence domain. This talk is based on joint works with Masakio Miyazawa at Tokyo University of Science.

Jim Dai is the Edenfield Professor of Industrial \& Systems Engineering at Georgia Institute of Technology. He is a Special Term Professor at Tsinghua University and a Visiting Professor in Decision Sciences at National University of Singapore. Over the last twenty years, he has worked on stochastic models arising from communications, manufacturing, and service systems that include data switches, semiconductor wafer fabrication lines, call centers, and healthcare-delivery systems.

Jim Dai received B.A. and M.S. degrees from Nanjing University and a
Ph.D. degree from Stanford University. He is an elected fellow of
Institute of Mathematical Statistics and an elected fellow of
Institute for Operations Research and the Management Sciences
(INFORMS). He is currently an Area Editor for * Mathematics of
Operations Research *, an Area Editor for * Operations Research *,
and a past Series Editor for * Handbooks in
Operations Research and Management Science *.

Monday June 18 2012, 11:00-12:00

We review belief propagation algorithms inspired by the study of phase transitions in combinatorial optimization problems. In particular, we present rigorous results on convergence of such algorithms for matching and associated bargaining problems on networks. We also present a belief propagation algorithm for the prize-collecting Steiner tree problem, for which rigorous convergence results are not yet known. Finally, we show how this algorithm can be used to discover pathways in cancer genomics, and to suggest possible drug targets for cancer therapy.

Jennifer Chayes is Distinguished Scientist and Managing Director of Microsoft Research New England and Microsoft Research New York City. She is a renowned interdisciplinary scientist, author of over 110 papers and 25 patents, in mathematics, physics, computer science and social sciences. Chayes is a Fellow of the American Association for the Advancement of Science, the Association of Computing Machinery and the Fields Institute. She serves on numerous boards and committees including as Chair of the Turing Award Committee. Chayes' leadership has been recognized with many awards including the Anita Borg Institute Women of Vision Leadership Award.

Online privacy concerns prompt the following question: can a recommendation engine be accurate if end-users do not entrust it with their private data? To provide an answer, we study the problem of learning user ratings for items under so-called local or 'user-end' differential privacy, a formal notion of data privacy. Our first contribution is the obtention of lower bounds on learning complexity based on mutual information. These results highlight the role played by the amount of ratings performed by each user. In the information-rich regime (where each user rates at least a constant fraction of items), a spectral clustering approach is shown to achieve optimal sample complexity, as it matches our information-theoretic lower bounds. However the information-scarce regime (where each user only rates a vanishing fraction of the total item set) is found to require a different approach. We thus propose the so-called MaxSense algorithm, which achieves optimal sample complexity in the information-scarce regime. The techniques we develop for bounding mutual information may be of broader interest. To illustrate this, we show their applicability to (i) learning based on 1-bit sketches (in contrast to differentially private sketches), and (ii) interactive learning, where queries can be adapted based on answers to past queries.

Laurent Massoulié is a Distinguished Scientist and Fellow at Technicolor. He is a member of the Technicolor Research and Innovation Paris Lab. His research focuses on probabilistic modeling and design of distributed algorithms for 'large networks', including P2P, social and smart grid networks. He graduated from the Ecole Polytechnique in 1991, and obtained his PhD from Paris Sud University in 1995. He has held positions at France Telecom R&D, Issy-les-Moulineaux France (1995-1999) and at Microsoft Research, Cambridge United Kingdom (1999-2006). He has co-authored the Best Paper Award-winning papers of IEEE INFOCOM '99, ACM SIGMETRICS '05 and ACM Conext'07. He has served as associate editor of "Queueing Systems: Theory and Applications" (2000-2006), IEEE/ACM ToN (2008) and Stochastic Systems Journal (2011-).

Referring to similarities between moderate-deviations-scale and diffusion-scale heavy traffic analysis, D. Wischik wrote in his 2001 paper, Moderate Deviations in Queueing Theory, "We conjecture that there is a similar control theory for queueing systems at the moderate deviations scale." In this talk I will discuss similarities that indeed occur between optimal control in the moderate deviations regime and in the diffusion regime. The former is also closely related to large-deviations-scale analysis, and this relation, and related ideas, will be described. This is joint work with Anup Biswas (Technion).

Rami Atar is with the Department of Electrical Engineering, Technion, Israel, where he received his Ph.D. in 1997. He held visiting appointments at Brown University, the Fields Institute, University of Washington and University of North Carolina. His research interests are in stochastic processes. These include asymptotic analysis of queueing and stochastic network models in diffusion and large deviation regimes, PDE techniques in stochastic control and differential games, filtering and estimation.

Benes networks are constructed with simple switch modules and have many advantages, including small latency and requiring only an almost linear number of switch modules. As circuit-switches, Benes networks are rearrangeably non-blocking, which implies that they are full-throughput as packet switches, with suitable routing. Routing in Benes networks can be done by time-sharing permutations. However, this approach requires centralized control of the switch modules and statistical knowledge of the traffic arrivals. We propose a backpressure-based routing scheme for Benes networks, combined with end-to-end congestion control. This approach achieves the maximal utility of the network and requires only four queues per module, independently of the size of the network.

Several classes of stochastic networks can be viewed as weakly interacting jump Markov processes. We establish large deviations principles for the scaled sequences of empirical measures associated with a large class of weakly interacting jump Markov processes, and discuss the implications for the design and performance of associated stochastic networks. The difficulty in establishing a large deviations principle arises from the fact that the processes do not satisfy the commonly assumed condition that the jump rates are not uniformly bounded below, away from zero. This is joint work with Paul Dupuis and Wei Wu.

We consider the following dynamic Boolean model introduced by van den Berg, Meester and White (1997). At time 0, let the nodes of thegraphbe a Poisson point process in R^d with constant intensity and let each node move independently according to Brownian motion. At any time t, we put an edge between every pair of nodes if their distance is at most r. We study two features in this model: detection (the time until a target point--fixed or moving--is within distance r from some node of thegraph), isolation (the time until the origin is isolated) and percolation (the time until a given node belongs to the infinite connected component of thegraph). We obtain asymptotics for these features by combining ideas from stochasticgeometry, coupling and multi-scale analysis. (Based on joint works with Yuval Peres, Alistair Sinclair and Alexandre Stauffer)

Tuesday June 19 2012, 15:30-16:30

We are motivated by the problem of designing simple distributed algorithms for peer-to-peer streaming applications that can achieve high throughput and low delay, while maintaining a very small neighbor set for each peer. Our algorithm constructs multiplerandomdirected Hamiltoncyclesand disseminates content over the superposed graph of thecycles. We show that the algorithm achieves any arbitrary fraction of the maximum streaming capacity while maintaining a small streaming delay. The result is established by showing that the superposed graph is an expander with high probability.

R. Srikant is the Fredric G. and Elizabeth H. Nearing Endowed Professor of Electrical and Computer Engineering and a Professor in the Coordinated Science Lab at the University of Illinois at Urbana-Champaign. His research interests include communication networks, stochastic processes, game theory, and distributed algorithms.

We propose a new model for peer-to-peer networking which takes the network bottlenecks into account beyond the access. This model allows one to cope with the fact that distant peers often have a smaller rate than nearby peers. We show that the spatial point process describing peers in their steady state then exhibits an interesting repulsion phenomenon. We study the implications of this phenomenon by analyzing two asymptotic regimes of the peer-to-peer network: the fluid regime and the hard-core regime. We get closed form expressions for the mean (and in some cases the law) of the peer latency and the download rate obtained by a peer as well as for the spatial density of peers in the steady state of each regime. The analytical results are based on a mix of stochastic and dimensional analysis and have important design implications.

Joint work with F. Mathieu and I. Norros.

Wednesday June 20 2012, 09:30-10:30

We consider the G/GI/N queue with multiple server pools, each possessing a pool-specific service time distribution. We then consider the class of non-idling routing policies referred to as u-greedy policies. These policies route incoming customers to the server pool with the longest weighted cumulative idle time. Our first set of results demonstrate that asymptotically in the Halfin-Whitt regime and under any u-greedy policy, the diffusion scaled cumulative idle time processes of each of the server pools are held in fixed proportion to one another. We next move on to providing a heavy-traffic limit theorem for the process keeping tracking of the total number of customers in the system. Our limit may be characterized as the solution to a stochastic convolution equation. As a first step to proving our main results, we also show that under any non-idling policy and under appropriate initial conditions, the fluid scaled total number of customers in the system and in each server pool is asymptotically constant. This is joint work with Yair Shaki.

Josh Reed is an Assistant Professor of Information, Operations and Management Sciences at New York University's Stern School of Business. Josh's primary research interests are in the performance analysis and optimal control of stochastic networks arising in manufacturing and service systems. In particular, he is interested in applications related to telephone call centers. Josh received his Ph.D. in Operations Research from the Georgia Institute of Technology and his B.S. in Industrial Engineering from the University of Illinois.

Large dynamic economic systems are all around us: financial markets, power markets, sponsored search auctions, online marketplaces such as eBay, and resource sharing systems (e.g., cloud computing platforms) are just a few timely examples. It is of central societal importance to have systematic approaches to management, design, and control of such systems. Unfortunately, classical methods of analysis suggested by economics suffer from two major flaws: they are both intractable and implausible. Computation of these equilibria is often impossible for the system analyst, and even computing best responses within the game may be intractable for individual agents. Further, these equilibrium concepts often place excessive demands on the rationality and foresight of agents in the system. This talk first surveys recent results on an alternative concept we call mean field equilibrium (MFE). In a mean field equilibrium, individuals take a simpler view of the world: they postulate that fluctuations in the empirical distribution of other players' states have "averaged out" due to large scale, and thus optimize holding the state distribution of other players fixed. MFE requires a consistency check: the postulated state distribution must arise from the optimal strategies agents compute. MFE is typically more tractable and more plausible than its classical counterparts. We discuss basic theoretical results related to MFE, as well as applications in a range of settings. We then focus our attention on MFE in multiarmed bandit games. These are a class of games where each agent solves a multiarmed bandit problem, but payoffs depend on how many other agents choose the same action at each time step. Such games are a reasonable economic model for a range of settings, from wireless spectrum allocation to product selection by competing firms. We study existence of MFE in such games; establish conditions under which MFE are unique; and show under the same conditions that agents converge to the unique MFE from any initial condition.

Ramesh Johari is an Associate Professor at Stanford University and the Cisco Faculty Scholar in the School of Engineering, with a full-time appointment in the Department of Management Science and Engineering (MS&E), and courtesy appointments in the Departments of Computer Science (CS) and Electrical Engineering (EE). He is a member of the Operations Research group in MS&E, the Information Systems Laboratory in EE, and the Institute for Computational and Mathematical Engineering. He received an A.B. in Mathematics from Harvard (1998), a Certificate of Advanced Study in Mathematics from Cambridge (1999), and a Ph.D. in Electrical Engineering and Computer Science from MIT (2004).

In many of the challenges faced by the modern world, from overcrowded road networks to overstretched healthcare systems, large benefits for society come about from small changes by very many individuals. We survey the problems and the cost they impose on society. We then describe a series of pilot projects which aim to develop principles for inducing small changes in behavior in networks such as transportation, wellness and recycling. Pilots have been conducted with Infosys Technologies, Bangalore (commuting) and Accenture-USA (wellness), and two are ongoing: in Singapore (public transit congestion) and at Stanford (congestion and parking).

In this talk, we will describe this work and present results from the pilots. Some salient themes are the use of low-cost sensing and networking technology for sensing individual behavior, and the use incentives and social norming to influence the behavior.

Balaji Prabhakar is a faculty member in the Departments of Electrical Engineering and Computer Science at Stanford University. His research interests are in computer networks; notably, in designing algorithms for the Internet and for Data Centers. Recently, he has been interested in Societal Networks: networks vital for society's functioning, such as transportation, electricity and recycling systems. He has been involved in developing and deploying incentive mechanisms to move commuters to off-peak times so that congestion, fuel and pollution costs are reduced.

He has been a Terman Fellow at Stanford University and a Fellow of the Alfred P. Sloan Foundation. He has received the CAREER award from the U.S. National Science Foundation, the Erlang Prize, the Rollo Davidson Prize, and delivered the Lunteren Lectures. He is a co-recipient of several best paper awards.

Thursday June 21 2012, 10:15-11:15

Regenerative processes occur naturally in queueing theory. They are essentially characterized by the law of their excursions, and it is therefore natural to expect the convergence of the excursions to characterize the convergence of the whole processes. In this talk I will discuss such ideas, give a general result along these lines and provide two examples of stochastic networks in heavy traffic that we have been able to study using this result.

Florian Simatos got his Master of Science from the Electrical Engineering department at Stanford in 2005, and then did my PhD under the supervision of Philippe Robert from 2006 to 2009 at INRIA Paris-Rocquencourt. In 2005-2006, I was a post-doc at CWI (Amsterdam) and since January 1st, 2012, I am a post-doc at TU/e (Eindhoven) in the Mathematics department.

Thursday June 21 2012, 11:30-12:00

The (exogenous) traffic offered to a network significantly influences both its qualitative and quantitative behavior. For example, one commonly employed theoretical model is that of so-called renewal traffic. Its intrinsic statistical regularity has profound implications, ranging from fluid limits to the "square root staffing formula". In this talk, we will provide a brief survey of some of the historical developments in this area, and discuss some of the current work and potential future directions for research.

Given the significant energy consumption of data centers, improving their energy efficiency is an important social problem. However, energy efficiency is necessary but not sufficient for sustainability, which demands reduced usage of energy from fossil fuels. In this talk, I will describe some recent work highlighting the algorithmic challenges associated with designing sustainable data centers. We will focus on two applications -- (i) dynamic resizing within a data center and (ii) geographical load balancing across an Internet-scale system. In both cases, the core algorithmic problem is that of "smoothed online convex optimization (SOCO)". SOCO is a variant of the class of "online convex optimization (OCO)" problems, and is strongly related to the class of "metrical task systems", each of which have been studied extensively. Prior literature on these problems has focused on two performance metrics: regret and competitive ratio. There exist known algorithms with sub-linear regret and known algorithms with constant competitive ratios (some of which we have developed); however no known algorithms achieve both. In this talk I will discuss some recent progress toward this goal.

Adam Wierman is an Assistant Professor in the Department of Computing and Mathematical Sciences at the California Institute of Technology, where he is a member of the Rigorous Systems Research Group (RSRG). He received his Ph.D., M.Sc. and B.Sc. in Computer Science from Carnegie Mellon University in 2007, 2004, and 2001, respectively. His research interests center around resource allocation and scheduling decisions in computer systems and services. He received the ACM SIGMETRICS Rising Star award in 2011, and has received best paper awards at ACM SIGMETRICS, IFIP Performance, IEEE INFOCOM, and ACM GREENMETRICS. He has also received multiple teaching awards, including the Associated Students of the California Institute of Technology (ASCIT) Teaching Award.

This talk includes joint work with Krzysztof Debicki, Peter Glynn, Offer Kella, Zbigniew Palmowski and Tomasz Rolski. In this talk I'll treat several topics related to the transient analysis of Levy-driven queues. I start by pointing out how, in terms of transforms, the transient distribution can be uniquely characterized for the (general) situation that jumps to both sides are allowed -- the resulting expressions are in terms of the Wiener-Hopf factors, and have an appealing intuitive interpretation. Then 'll analyze the so-called quasi-stationary workload of the Levy-driven queue: assuming the system is in stationarity, we study its behavior conditional on the event that the busy period in which time 0 is contained has not ended before time t, as t -> inf. For the spectrally one-sided cases explicit results are obtained; for instance in the case of Brownian input, we conclude that the corresponding workload distributions at time 0 and t are both Erlang(2). Then I'll present results on the workload correlation function, in terms of structural properties, as well as an efficient importance sampling algorithm. Time permitting, I'll conclude with an analysis of the transient workload in Levy-driven tandem systems.

Michel Mandjes received M.Sc. (in both mathematics and econometrics) and Ph.D. degrees from the Vrije Universiteit (VU), Amsterdam, the Netherlands. After having worked as a member of technical staff at KPN Research (Leidschendam, the Netherlands) and Bell Laboratories/Lucent Technologies (Murray Hill NJ, USA), as a full professor at the University of Twente, and as department head at CWI, Amsterdam, he currently holds a full professorship (chair of Applied Probability) at the University of Amsterdam, the Netherlands. He is also affiliated (as an advisor) with EURANDOM, Eindhoven, the Netherlands. In 2008, Mandjes spent a sabbatical at Stanford. His research interests include performance analysis of communication networks, queueing theory, advanced simulation methods, Gaussian traffic models, traffic management and control, and pricing in multi-service networks. He is the author of Large Deviations for Gaussian Queues, Wiley, 2007. He is associate editor of Stochastic Systems, Stochastic Models, Queueing Systems, and Journal of Applied Probability.

Stochastic processing networks (SPNs) are a significant generalization of conventional queueing networks that allow for flexible scheduling through dynamic sequencing and alternate routing. SPNs arise naturally in a variety of applications in operations management and their control and analysis present challenging mathematical problems. One approach to these problems, via approximate diffusion control problems, has been outlined by J. M. Harrison. Various aspects of this approach have been developed mathematically, including a reduction in dimension of the diffusion control problem. However, other aspects have been less explored, especially, solution of the diffusion control problem, derivation of policies by interpretating such solutions, and limit theorems that establish optimality of such policies in a suitable asymptotic sense.

In this talk, for a concrete class of networks called parallel server systems which arise in service network and computer science applications, we explore previously undeveloped aspects of Harrison's scheme and illustrate the use of the approach in obtaining simple control policies that are nearly optimal. Identification of a graphical structure for the network, an invariance principle and properties of local times of reflecting Brownian motion, will feature in our analysis. The talk will conclude with a summary of the current status and description of open problems associated with the further development of control of stochastic processing networks.

This talk will draw on aspects of joint work with M. Bramson, M. Reiman, W. Kang and V. Pesic.

We shall demonstrate how a large class of stochastic networks that are of great interest in Operations Research are surprisingly quite amenable to efficient Monte Carlo simulation techniques. Take for instance reflected Brownian motion (RBM) in d dimensions in the positive quadrant with oblique reflection, and consider the following questions: a) Can one estimate quantities such as the maximum of the sum of the components during the time interval [0,T] without any bias? b) How much more difficult really is to estimate quantities such as those described in a) relative to the corresponding ones with standard Brownian motion? What about if the underlying dimensions are large? c)What about stationary expectations of RBM?Can we estimate them using Monte Carlo simulation without any bias? In this talk we will report good news (i.e. positive answers) to questions a) and c) above and we will see that, in fact, many models of interest in Operations Research share the convenient properties that make RBM "highly tractable" in a precise sense to be discussed in the talk and that relates to question b). In particular, we hope to convey that from a Monte Carlo standpoint really RBM and many other stochastic networks are not that much more different from standard Brownian motion.

Jose Blanchet is an Associate Professor in IEOR Department at Columbia University. Jose holds a Ph.D. in Management Science and Engineering from Stanford University. Prior to joining Columbia he was a faculty member in the Statistics Department at Harvard University. Jose is a co-recipient of both the 2009 Best Publication Award given by the INFORMS Applied Probability Society and of the 2010 Erlang Prize. He also received a PECASE award given by NSF in 2010. He has research interests in applied probability and Monte Carlo methods. He serves in the editorial board of Advances in Applied Probability, Journal of Applied Probability, Mathematics of Operations Research, QUESTA, and Stochastic Systems.

Levy networks are analogs of Brownian networks, arising as diffusion approximations when heavy tails are present. In this talk we will briefly summarize some approximation results and focus attention to the analysis of a fluid queue driven by the local time of a reflected Levy process. This can be thought of as a model of the low priority queue in a system with 2 priorities. Although the process is not Markovian, we manage, by combining fluctuation theory and Palm calculus to obtain explicit results for the distribution of various quantities in steady state. This is joint work with Andreas Kyprianou and Paavo Salminen.

Proportional fairness (PF) is an algorithm for allocating bandwidth in communication networks, and it is known to have many desirable features. However, the steady-state delay performance of PF can be improved, at least in small examples, by putting greater emphasis on efficient utilization of network resources, as opposed to equitable treatment of users. Building on recent work by Kang, Kelly, Lee and Williams (Ann. Appl. Probab. 2009), which provides a strikingly simple heavy traffic approximation for steady-state delay performance under PF, this talk will illuminate further the fairness-versus-efficiency tradeoff. (Based on joint work with Chinmoy Mandayam and Yang Yang.)

Michael Harrison is the Adams Distinguished Professor of Management in the Graduate School of Business, Stanford University. He earned a B.S. degree in industrial engineering from Lehigh University, an M.S. in industrial engineering from Stanford, and a Ph.D. in operations research from Stanford before joining the faculty of the Graduate School of Business in 1970. He has developed and analyzed stochastic models in several different domains related to business, including mathematical finance and processing network theory. His current research is focused on dynamic pricing and revenue management. Professor Harrison has been honored by INFORMS with its Expository Writing Award (1998), the Lanchester Prize for best research publication (2001), and the John von Neumann Theory Prize (2004); he was elected to the National Academy of Engineering in 2008. He is a fellow of INFORMS and of the Institute for Mathematical Statistics.