Research in applied probability
Large-scale stochastic interacting agents are ubiquitous in operations research. A broad theme of my research is to analyze mathematical models of such interacting systems and establish crucial properties that provide insight into their performance, design, and control. I consider two types of interaction among the agents:
- Mean-field interaction, where each agent is influenced by every other agent in a symmetric and identical fashion;
- Local interaction, where the agents are associated with the vertices of a graph, and each agent is directly influenced only by its neighbors.
In both cases, the agents have a state that randomly evolves over time. Some examples of natural and engineered systems constituting many interacting agents are:
- Spread of epidemics on networks: Here, the vertices represent individuals in a community and the edges represent their contacts. Each individual could be in one of two states: healthy or infected.
- Load balancing networks: An agent in a network is a single-server queue; its state is the number of jobs waiting for service. The interaction could be of either mean-field or local nature, depending on the algorithm used for load balancing.
- Deep neural networks: An agent is a hidden neuron, and its state is the associated model parameter. The evolution of the states represents the stochastic gradient descent algorithm used in the training phase.
The performance of these systems is governed by the stationary behavior of the agents’ (random) states. For instance, in the epidemic spread model, this would be the number of infections under steady state; for the load balancing example, this would be the average queue length under steady state.
Metastability in finite-state mean field models
One of the primary challenges in quantifying the steady-state behavior of such systems is that they often exhibit metastability. That is, they behave differently over different time scales. This is illustrated in the adjacent figure. The zig-zag curve represents a sample path of the collective behavior of the system, which we refer to as the empirical measure process \(\mu_n\), where \(n\) represents the number of agents in the system. Mathematically, the empirical measure process at time \(t\) is the empirical distribution of the states of the agents \(\{X_1(t), \ldots, X_n(t)\},\) defined by \[\mu_n(t) = \frac{1}{n} \sum_{i=1}^n \delta_{X_i(t)},\] which is a (random) probability vector whose \(j\)th entry is the fraction of agents having state \(j\) at time \(t\). In many cases, this process can be viewed as a small-random perturbation of a deterministic dynamical system, whose trajectories are indicated by arrows. The dynamical system could possess multiple fixed points (denoted by \(x_1^*\) and \(x_2^*\)) or limit cycles (\(x_3^*\)). The trajectories of the dynamical system converge (as time \(t \to \infty \)) to one of the fixed points depending on the initialization. For a fixed time duration, the random process typically follows the trajectory of the dynamical system. However, if we wait long enough, we see transitions between fixed-points, which are away from the trajectories of the dynamical system.
In this paper, we quantify such metastable behavior for mean field models with a finite state space, such as the mean exit time from a small neighborhood of a fixed point. These estimates are of the form \(\mathbb{E}[\tau_{\text{exit}}] \approx \exp\{n c\} \) for a suitable constant \(c\). Using these, we then obtained a sharp estimate on the time required for \(\mu_n\) to equilibrate (which is referred to as the mixing time); we showed that \(\tau_{\text{mixing}} \approx \exp\{n\Lambda\} \) for a suitable constant \(\Lambda > 0\). Thus, metastability prevents rapid mixing. We also developed a simulated annealing algorithm to guide the dynamics toward a desired fixed point.
The main tool used in our proofs is a uniform version of the process-level large deviation principle (LDP) for \(\mu_n\), that is, asymptotic estimates of the form
\[\mathbb{P}(\mu_n = \varphi) \approx \exp\{-n I(\varphi)\} \text{ for all measure-valued paths } \varphi, \]
where \(I\) is a suitable "rate function" of measure-valued paths. The constants \(c\) and \(\Lambda\) above are expressed in terms of \(I\).
Invariant measure asymptotics in countable-state mean-field models
Quantifying the metastable behavior of mean field models with a countable state space (such as load balancing models wherein the state space of the queues is countable) is more challenging. In these models, we first studied the LDP for the invariant measure of \(\mu_n\). A natural candidate rate function in this context is the Freidlin-Wentzell quasipotential, defined by the minimization of the cost (in terms of the rate function \(I\)) over finite-horizon trajectories. We first constructed two counterexamples where the usual quasipotential is not the rate function. This occurs because of certain barriers in the state space that can be crossed in the stationary regime, but not over finite time horizons. After highlighting this phenomenon, under some sufficient conditions, we proved the LDP for the invariant measure whose rate function is given by the usual quasipotential. Our proof involves establishing various continuity properties of the quasipotential. This result is the first step in quantifying metastability in countable-state systems.
For more details, see our paper and this online talk.
A Sanov-type theorem for sparse random graphs with discrete marks
While the empirical measure \(\mu_n\) captures the collective behavior of all agents in the mean field case, it is challenging to analyze this object directly in the case of local interaction since it throws away the underlying interaction structure. A more tractable object is the so-called neighborhood empirical measure (denoted by \(L_n\), where \(n\) is the number of agents), which is the empirical distribution of first neighborhoods of the agents in the system. This is a (random) probability measure on the space of rooted depth-1 trees with vertex marks. The marks represent the trajectory of state evolution of the agents. In the unmarked case, \(L_n\) becomes the degree distribution of the underlying interaction graph. As a first step to analyze metastability, we considered the non-interacting case where the vertex marks are independent and identically distributed random variables with a common law, say \(\nu\). When the mark space is discrete, for suitable families of interaction graphs, we proved a tractable relative-entropy-based rate representation for the rate function that governs the LDP for \(L_n\). The rate function takes the form \[ J(\mu) = \frac{1}{2} \left[H(\mu \| \check{\mu}) + H(\mu \| \hat{\mu}) \right]; \]
here, \(\check{\mu}\) and \(\hat{\mu}\) are certain auxiliary independent and conditionally independent (given the root mark) versions of \(\mu\), and \(H( \cdot \| \cdot)\) is the usual relative entropy functional. Thus, the rate function quantifies the cost of deviation of the joint law of the leaf marks from its independent and conditionally independent versions. Note that if \(\eta\) is the law on rooted depth-1 trees with i.i.d. vertex marks with the original distribution \(\nu\), then \(J(\eta) = 0\), and we recover the typical behavior of \(L_n\). Our LDP is applicable to random graph families such as uniform graphs with a fixed degree distribution (i.e., configuration model), uniform graphs with a fixed number of edges, and Erdos-Renyi random graphs. Additionally, we can consider graphs with i.i.d. edge marks in addition to vertex marks; the rate function therein also takes the exact same form.
See our paper for more details.
Research in data analytics
I am also interested in exploring data from various domains to answer specific scientific questions of interest. Some of the projects that I have worked on in this direction are as follows:
COVID-19 response
Agent-based models for studying disease spread: During the first wave of COVID-19 in India, we developed an agent-based model for Mumbai and Bengaluru to forecast the number of cases under various scenarios, including the opening of schools and workplaces, different levels of lockdown and containment policies, among others. For more details, refer to our paper and this toy simulator.
Compartmental models for vaccine allocation: During the initial rollout of COVID-19 vaccines, we studied the problem of allocating vaccines across various age groups and geographic locations to minimize the number of infections. For this project, we developed a compartmental model of epidemic spread that captures mobility and age-stratified interactions. Check out this manuscript for more details.
Public transportation
By analyzing GPS data from buses, we studied the effectiveness of the Bus Priority Lane (BPL) in Bengaluru. We proposed an algorithm to compute travel times from GPS data, and we concluded an overall improvement in travel times after the implementation of the BPL. We also identified hotspots on the BPL, as well as improvements in the peak and non-peak hour travel times. For more details, refer to this paper.