Kavita Ramanan - US grants

0406191
Ramanan
The main objective of this project is to extend the general theory of deterministic and stochastic constrained processes that have discontinuous dynamics and to apply it to gain better insight into the performance and control of stochastic networks. The project has four components. The first part studies reflected diffusions that arise as approximations to multi-class stochastic networks with cooperative servers (i.e. servers that use all the excess capacity allocated to one class in order to serve other classes). The estimation of functionals of these diffusions is complicated by the fact that these diffusions often fail to be semimartingales. The current project describes new techniques for the pathwise analysis of these diffusions. The second part of the research aims to first establish general sufficient conditions for uniqueness of differential equations that have discontinuous drifts and to then use these conditions to characterize fluid limits of queueing networks that exhibit discontinuous transition mechanisms in the interior of their domains. The third part is devoted to the analysis of phase transitions and Gibbs measures associated with a class of stochastic loss networks that appear as models of multicasting in telecommunication networks. The last part focuses on the design of optimal controls for a class of non-stationary queueing networks.
Over the last decade the increasing complexity of telecommunication, computer and manufacturing systems has emphasized the need for the systematic development of tools for their analysis, design and control. Since an exact analysis of these stochastic systems is often infeasible one resorts to an asymptotic analysis that is appropriate for the performance measure of interest. Three asymptotic regimes of interest are the fluid regime, which captures the mean behavior of the system, the diffusion regime, which describes stochastic variations around the mean and the large deviations regime, which analyzes probabilities of events that are rare, but of crucial importance to the operation of the network (such as, for example, data loss in a computer network). This project will develop tools that facilitate the asymptotic analysis (in each of the three regimes) of important classes of stochastic networks that arise naturally in applications. In particular, the tools developed are expected to be useful for the estimation of important network performance measures such as stability and buffer overflow probabilities and also for the design of optimal controls.

The objective of this proposed research is to develop mathematical tools for the analysis and design of complex stochastic networks arising in telecommunications, computer and service systems. These networks are typically too complex to lend themselves to an exact analysis. The primary goal of this research is to develop new techniques for obtaining a variety of asymptotic approximations for these systems. Specifically, these include so-called fluid or first-order approximations that describe the mean behavior of the system, diffusion approximations that capture fluctuations around the mean, and large deviations approximations that provide estimates for the probabilities of rare events that are critical to the working of the system. These techniques will be applied to gain insight into the behavior of several concrete classes of networks. In particular, new admission control algorithms will be developed for so-called ?real-time? systems that process tasks with deadlines such as, for example, telecom systems carrying digitized voice and tracking systems. In addition, estimates of performance measures will be obtained for multi-server systems that arise in call centers. We will also investigate the equilibrium properties of networks with blocking (used to model mobile wireless networks), as well as the stability of networks utilizing so-called bang-bang controls.
One of the mathematical challenges in analyzing stochastic networks is that they are often described by constrained processes that exhibit discontinuous transitions, and so much of the classical theory can no longer be applied. If successful, this research would provide a new set of mathematical tools for the analysis of such constrained processes, which could be of broader applicability. The research also has the potential to contribute to improving the design and control of real-time queueing networks, call centers and wireless networks, which could lead to greater economy in the running of these systems.

This proposal concerns the analysis of large-scale stochastic systems that arise in manufacturing and service systems, computer data systems and financial engineering. Three broad classes of problems will be considered. The first involves the design, control and performance analysis of networks of multi-server systems with generally distributed service times. The effect of customer abandonement in these systems will also be considered. The second problem arises in the study of microstructure in finance. The research in this part of the proposal aims to introduce a rigorous model that will provide insight into the dynamics of limit order books. The last topic concerns the study of time-varying stochastic networks. Although a lot of work has been carried out in the study of homogeneous systems, most real- world applications exhibit non-negligible time-varying behavior. However, there is relatively little theoretical analysis of the control of these systems.
The proposal aims to take a preliminary step towards establishing rigorous conditions under which the study of a simpler system can shed insight into the analysis of the time-varying network.If successful, the analysis on multi- server queues would provide guidelines for routing and staffing in call centers, as well as help assess the performance of computer data systems. The work on limit order books could lead to a better understanding of the effect that protocols governing an exchange have on important financial quantities such as the bid-ask spread. The study on time-varying stochastic systems would identify conditions under which simple heuristics may be used to construct near-optimal controls for more complex systems. In addition, the work in this proposal is likely to require the development of mathematical techniques in diverse areas, ranging from measure-valued processes and stochastic partial differential equations to large deviations and stochastic games, which would be of broader interest.

Travel support will be provided for 14 young researchers and 1 frontier session organizer from US institutions to attend the 2011 Applied Probability Conference to be held in Stockholm, Sweden. Priority for support will be given to researchers who have received their PhD within the last five years and to graduate students in the last year of their PhD programs, as well as worthy candidates from underrepresented groups.


Applied probability is an extremely active area of research and interest in the field cuts across many scientific disciplines including operations research, computer science, combinatorics, mathematics, statistics, physics and biology. Researchers from these different fields raise different questions about and bring different perspectives to similar problems. Thus, there is great benefit in bringing together these researchers to enable cross-fertilization of ideas. The Applied Probability Society is a focus group within the INFORMS (INstitute For Operations Research and the Management Sciences) professional society. Its biannual conferences have established themselves as a leading forum in the field of applied probability. The conference will consist of three plenary talks from distinguished speakers, two tutorial sessions, over seventy invited and contributed sessions, each of ninety minutes duration with three speakers. In addition, there will also be a few ``frontier'' sessions, in which survey talks and open problems in areas of research at the cutting edge of applied probability will be presented such as random matrix theory, smart grids and systems biology.

The conference plays a major role in establishing connections between different areas of applied probability that can potentially lead to significant new developments in the field. The conference also serves an important educational purpose, enabling young researchers from all around the world to present their work and at the same time keep abreast of the latest advances in the field.

Dynamics and stochastics, both interpreted in their broadest sense, are important mathematical areas that have made many contributions to applications. There are many natural links between these two areas that lead to a better appreciation of techniques and methods used in either field. In addition, an approach that combines stochastic modelling with a dynamical-systems analysis often has the best chances of tackling a problem successfully: three examples are nonlinear optics, where noise from various sources plays an important role in laser and fiber dynamics; stochastic networks, where stability of the network can, in many cases, be determined by the analysis of a related fluid limit that is characterized by an ordinary or partial differential equation; and cell physiology, where stochastic models of ion channel gates often provide better agreement with experiments. A similar trend occurs on the theoretical level: probabilistic methods are an important tool that aids in the analysis of PDEs, for instance in the derivation and validation of scaling laws and the dynamics of fronts in heterogeneous media; conversely, dynamical-systems methods provide insight into the behavior of PDEs with noise. The goal of this project is to broaden and enhance the scope and quality of the educational and research training provided to graduate students and postdoctoral fellows by integrating research and education in the fields of dynamics, stochastics, and their applications and to involve more undergraduate students in courses and research experiences in applied mathematics.

Dynamical systems and stochastic processes are highly active and exciting fields of research that make important contributions to many applications in economics and the natural and social sciences, whilst also being of intrinsic mathematical interest. Dynamical-systems theory is concerned with time-dependent processes, while stochastics deals with nondeterministic, random processes. Examples where the interplay between these two fields is important are noise fluctuations in the design of high-power lasers, the long-time behavior of random interacting systems such as consensus formation in social networks, self-assembly of micro- and nanostructures for drug delivery, random fluctuations in biological cell processes, and importance sampling of rare events in finance. Providing more systematic and integrated training in dynamics and stochastics for graduate students and postdoctoral fellows will prepare these groups better for careers in academia and industry. It will also lead to an increase in the number of US mathematicians trained in stochastic systems, and therefore make the US better able to compete with Europe, which has a larger community in this area. The initiatives for undergraduate students will increase the number of students who are exposed to applied mathematics and are engaged in summer research experiences.

This award provides funding for the development of analytical and computational tools for determining the sensitivity to system parameters of both transient and steady-state performance measures in queueing networks. Standard numerical methods to calculate sensitivity of performance measures with a high level of accuracy are usually computationally prohibitive because they involve a two-step approach of first obtaining numerical approximations of expectations of performance measures at different parameter values and then numerical differentiation of these approximate expectations. This work aims to provide a more tractable analytical characterization of the sensitivity in terms of a single expectation, and to then use this characterization to develop efficient one-step algorithms for the computation of sensitivities. In particular, this extends approaches that have been used in finance and other domains to queueing networks, where the issue is far more subtle due to the presence of boundaries. This award also supports research in the study of many-server queues, with the goal of obtaining tractable approximations for transient and steady-state performance measures associated with many-server queues. New tools will be developed for the analysis of stability in such systems and obtaining tractable approximations of steady state and transient performance measures and applied for optimal system design.

Due to uncertainty in parameters, computation of sensitivities are very important for design and capacity allocation in queueing networks. The development of efficient computational tools would greatly enhance the planning capabilities of companies with manufacturing processes governed by queueing networks. Many-server queues arise in diverse applications such as call centers, health-care and data centers. In applications, knowledge of steady state and transient performance measures are required for staffing and decisions, the efficiency of which can have significant economic and social impact. In addition, this research will also develop new mathematical tools that will be applicable in a broader setting.

Many phenomena that arise in statistical physics, engineering and biology are modeled by stochastic processes that are constrained to live within a domain. This proposal aims to further develop the theory of such processes, with three concrete application areas in mind. The first area concerns random networks that arise in biology, manufacturing, and other service systems when they operate near capacity. The performance of these networks can often be described by diffusions that are constrained to have nonnegative components. A second area is in mathematical finance, where the advent of electronic exchanges driven purely by the flow of orders has revolutionized the method by which prices are formed. The price process in a model of strategic agents who place buy and sell limit orders can be better understood by studying a class of constrained processes. The third area involves the study of scaling limits of random matrices, which arise in many areas, including physics and engineering. The gaps between the eigenvalues of some classes of high-dimensional random matrices, when properly scaled, can be shown to be approximated by constrained multi-dimensional diffusions with singular drift. The proposal seeks to develop a unified theory for the construction and study of these processes, and to examine their implications for the described applications. Another theme of the proposal involves the study of planar obliquely reflected diffusions. Planar stochastic processes have been the focus of active research over the last two decades. Finally, the proposal also has a substantial educational component that includes training of post-doctoral fellows, graduate students and undergraduate students, as well as new course development. It also entails a broader effort that coordinates several graduate students in outreach activities aimed at communicating mathematics to a broader audience.

This is an interdisciplinary proposal that focuses on several problems in probability that require substantial use of analytical techniques. The first theme concerns various aspects of obliquely reflected diffusions, including the construction and properties of obliquely reflected Brownian motions in bounded planar domains, and also excursion reflected Brownian motion which arises in the boundary theory of Markov processes. It also involves the development of a common framework for the analysis of diffusions with both reflection and singular drift, large deviations of semimartingale reflected Brownian motions and a free boundary problem related to a two-dimensional reflected Brownian motion. These are motivated by applications in queuing networks, biology, and mathematical finance. The tools that will be used intersect with several areas of mathematics including analysis (in particular, complex analysis, conformal mappings, harmonic analysis, functional analysis, partial differential equations and free-boundary problems). There are also implications of this work for mathematical physics, specifically the study of repulsive particle models associated with random matrices.

Stochastic networks are comprised of "jobs" in the form of packets or customers that arrive to a network and wait in buffers at different nodes of the networks until their processing requirements are fulfilled. Stochastic variability arises from randomness in arrival and processing times, as well as from routing and scheduling decisions. Such networks are ubiquitous and arise as models in diverse fields ranging from telecommunications and service systems to biological systems. A better understanding of these networks has the potential to lead to new algorithms that dramatically improve performance and enable the support of novel network applications. This award supports the development of a general mathematical framework for the analysis of two broad classes of stochastic networks: large-scale load-balancing networks that arise, for example, in web-server farms, and queueing networks that use scheduling policies involving prioritization, which are relevant for real-time scheduling in computer networks and health care systems. The goal is to identify tractable approximations of both transient dynamics and equilibrium behavior, rigorously establish their accuracy for suitable values of network parameters, and to use them to gain insight into network design. There will be mentorship of graduate students, a multidisciplinary project for an undergraduate student and opportunity for outreach. The project also involves interactions with industry, which increases the potential of impacting the design of real networks.

Stochastic networks are typically too complex to admit an exact analysis. The goal then is to obtain tractable approximations, whose accuracy can be rigorously justified in a suitable (asymptotic) regime of network parameters via limit theorems for suitably scaled state processes. While there is a well developed mathematical theory of "scaling limits" for certain classes of networks, it does not cover the networks considered in this project, which involve many servers at a single node, general service distributions and non-head of the line scheduling policies. One of the challenges is that Markovian scaling limits of these networks are typically not finite-dimensional. The research will develop tractable infinite-dimensional Markovian representations of these systems, involving interacting measure-valued processes and infinite-dimensional Skorokhod maps, and rigorously establish scaling limit theorems. The analysis will combine methods from different fields, including probability, stochastic analysis, dynamical systems, partial differential equations and optimization. The tools developed will potentially be applicable more broadly for the study of analogous stochastic models arising in other applications. Simulations will also be carried out to ascertain the validity of these approximations for finite systems.

Applications in diverse fields, including data analysis, convex geometry, biology, physics, economics, engineering, operations research, and computer science, give rise to questions about random phenomena in high dimensions. For example, given data that lives in a high-dimensional space, what information can be obtained by studying lower-dimensional projections of the data? Given a large number of interacting agents, who strategically make choices based only on their own state and the distribution of states of the other agents, what do their equilibria (or optimal strategies) look like? This award supports the development of diverse mathematical techniques for the analysis of such questions. The focus will be on characterizing large deviations from typical behavior, which though rare, are often of crucial importance in applications. The investigator will help train new mathematics researchers, mentor early career researchers, and be involved in outreach efforts.

The research will address three topics concerning high-dimensional random phenomena. The first involves the study of random projections of probability measures in high-dimensional Euclidean spaces. This is relevant both for the statistical analysis of high-dimensional data, as well as for asymptotic convex geometry and asymptotic functional analysis. The focus is on characterizing the large deviation behavior of such random projections, as the dimension goes to infinity. This is of interest because, unlike fluctuations, the large deviation behavior is non-universal and thus distinguishes between different high-dimensional distributions. The second topic considers properties of high-dimensional Gibbs distributions on a class of hard-core configurations associated with a graph. Whereas classical models assume discrete spins, the focus of this research is on versions with continuous spins, which exhibit quite different behavior and require new techniques for their analysis. The last topic concerns the analysis of fluctuations, large deviations and concentration inequalities for Nash equilibria in both static and dynamic games of mean-field type with a large number of rational agents. This has implications for a broad range of applications and entails the development of new mathematical techniques, including large deviations principles for set-valued random elements, and analysis of solutions to a master equation for mean-field games.

Women's Intellectual Network Research Symposium: A Meeting of Mathematical Minds is a one-day symposium that will be held at Brown University on Saturday, March 4th, 2017. The goal of this symposium is to bring together undergraduate and graduate students, as well as post-doctoral fellows and faculty from New England, in order to engage in research discussions and exchange ideas. This symposium particularly seeks to connect women and other underrepresented minorities in similar fields of mathematics or statistics from universities in the New England area, as well as to promote collaboration and share strategies for addressing issues facing these groups. However, the symposium is more broadly inclusive, and hopes to benefit a larger community. The symposium is open to everyone, regardless of gender identity. The symposium will feature two plenary talks, in applied dynamical systems and geometric group theory, three tutorials, including one on public key cryptography, and one in data science, short talks by students (graduate and undergraduate), post-doctoral fellows and faculty, a poster session, and a panel on effective mentoring. A meeting of members of AWM (Association for Women in Mathematics) Student Chapters will also be convened during the symposium. The symposium seeks to have a broad representation from pure, applied and industrial math, and encourages participation from researchers in all areas of mathematics, applied mathematics and statistics.

This pan-New England symposium will serve to build bridges between universities and connect researchers, particularly upcoming and younger researchers, women and underrepresented minorities, in similar mathematical fields. The geographic proximity of these universities makes it more likely that networks formed at the conference can be sustained and strengthened, which in turn should increase the probability that these researchers stay in the field and become highly productive members of the community. The symposium lays a strong emphasis on vertical integration, namely having representation at all levels, from undergraduate students to faculty, as we believe this is particularly beneficial to achieve the objectives of the symposium.

The symposium website is: http://www.dam.brown.edu/people/aah/WINRS/index.html

This project will support participation of graduate students, post-doctoral researchers and early career researchers from the United States of America in one of the workshops "Interacting Particle Systems and Hydrodynamic Limits" to be held from March 13-27, 2022, or the "Mean-Field Games" workshop to be held from April 10-17, 2022 at the Centre de Recherches Mathematiques (CRM) in Montreal, Canada. Both workshops are part of a larger interdisciplinary thematic program on "Probabilities and PDEs" held at CRM from January to July 2022. Probability theory and the theory of partial differential equations (PDEs) are important areas of mathematics with substantial overlap in their methods and goals. In both fields, one of the major aims is to provide accurate models of how engineered, physical, chemical and biological systems change over time. Probability frequently focuses on how systems which are random and/or unpredictable at the microscopic level can become highly ordered at the macroscopic level. PDE theory frequently focuses on the spatial and temporal evolution of such macroscopic systems. For decades there has been a fruitful interplay between the two fields probability and PDEs, with both intuitions and mathematical techniques from each area finding application in the other.

This project focuses on two aspects of that interplay, which are both related to how probabilistic particle systems resemble PDEs when sufficiently "zoomed out". One of these, the area of mean-field games, describes scaling limits of strategically controlled interacting agents evolving as diffusions coupled via a graph structure (often the complete graph). The second, interacting particle systems and hydrodynamic limits, typically focuses on PDE approximations for particle systems in more geometric settings, such as lattices (on taking an appropriate fine-mesh limit in both space and time). The goal of this project is to support the participation of US-based junior researchers and researchers from underrepresented groups in a thematic semester on Probability and PDEs (and in particular their participation in two workshops, on the subjects of mean-field games and interacting particle systems), taking place in the first half of 2022 at the Centre de Recherches Mathématiques in Montréal, Canada. The thematic semester website is maintained at http://www.crm.umontreal.ca/2022/Probab22/index_e.php the Interacting Particle Systems and Hydrodynamic Limits Workshop at http://www.crm.umontreal.ca/2022/Particules22/index_e.php and the Mean-Field Games Workshop at http://www.crm.umontreal.ca/2022/Games22/index_e.php.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.