• We establish large deviation principles (LDPs) for empirical measures associated with a sequence of Gibbs distributions on $n$-particle configurations, each of which is defined in terms of an inverse temperature $% \beta_n$ and an energy functional consisting of a (possibly singular) interaction potential and a (possibly weakly) confining potential. Under fairly general assumptions on the potentials, we use a common framework to establish LDPs both with speeds $\beta_n/n \rightarrow \infty$, in which case the rate function is expressed in terms of a functional involving the potentials, and with speed $\beta_n =n$, when the rate function contains an additional entropic term. Such LDPs are motivated by questions arising in random matrix theory, sampling, simulated annealing and asymptotic convex geometry. Our approach, which uses the weak convergence method developed by Dupuis and Ellis, establishes LDPs with respect to stronger Wasserstein-type topologies. Our results address several interesting examples not covered by previous works, including the case of a weakly confining potential, which allows for rate functions with minimizers that do not have compact support, thus resolving several open questions raised in a work of Chafa\"{\i} et al.
  • The study of high-dimensional distributions is of interest in probability theory, statistics and asymptotic convex geometry, where the object of interest is the uniform distribution on a convex set in high dimensions. The $\ell^p$ spaces and norms are of particular interest in this setting. In this paper, we establish a limit theorem for distributions on $\ell^p$ spheres, conditioned on a rare event, in a high-dimensional geometric setting. As part of our proof, we establish a certain large deviation principle that is also relevant to the study of the tail behavior of random projections of $\ell^p$ balls in a high-dimensional Euclidean space.
  • Mean field games (MFGs) describe the limit, as $n$ tends to infinity, of stochastic differential games with $n$ players interacting with one another through their common empirical distribution. Under suitable smoothness assumptions that guarantee uniqueness of the MFG equilibrium, a form of law of large of numbers (LLN), also known as propagation of chaos, has been established to show that the MFG equilibrium arises as the limit of the sequence of empirical measures of the $n$-player game Nash equilibria, including the case when player dynamics are driven by both idiosyncratic and common sources of noise. The proof of convergence relies on the so-called master equation for the value function of the MFG, a partial differential equation on the space of probability measures. In this work, under additional assumptions, we establish a functional central limit theorem (CLT) that characterizes the limiting fluctuations around the LLN limit as the unique solution of a linear stochastic PDE. The key idea is to use the solution to the master equation to construct an associated McKean-Vlasov interacting $n$-particle system that is sufficiently close to the Nash equilibrium dynamics of the $n$-player game for large $n$. We then derive the CLT for the latter from the CLT for the former. Along the way, we obtain a new multidimensional CLT for McKean-Vlasov systems. We also illustrate the broader applicability of our methodology by applying it to establish a CLT for a specific linear-quadratic example that does not satisfy our main assumptions, and we explicitly solve the resulting stochastic PDE in this case.
  • We study a sequence of symmetric $n$-player stochastic differential games driven by both idiosyncratic and common sources of noise, in which players interact with each other through their empirical distribution. The unique Nash equilibrium empirical measure of the $n$-player game is known to converge, as $n$ goes to infinity, to the unique equilibrium of an associated mean field game. Under suitable regularity conditions, in the absence of common noise, we complement this law of large numbers result with non-asymptotic concentration bounds for the Wasserstein distance between the $n$-player Nash equilibrium empirical measure and the mean field equilibrium. We also show that the sequence of Nash equilibrium empirical measures satisfies a weak large deviation principle, which can be strengthened to a full large deviation principle only in the absence of common noise. For both sets of results, we first use the master equation, an infinite-dimensional partial differential equation that characterizes the value function of the mean field game, to construct an associated McKean-Vlasov interacting $n$-particle system that is exponentially close to the Nash equilibrium dynamics of the $n$-player game for large $n$, by refining estimates obtained in our companion paper. Then we establish a weak large deviation principle for McKean-Vlasov systems in the presence of common noise. In the absence of common noise, we upgrade this to a full large deviation principle and obtain new concentration estimates for McKean-Vlasov systems. Finally, in two specific examples that do not satisfy the assumptions of our main theorems, we show how to adapt our methodology to establish large deviations and concentration results.
  • Randomized load balancing networks arise in a variety of applications, and allow for efficient sharing of resources, while being relatively easy to implement. We consider a network of parallel queues in which incoming jobs with independent and identically distributed service times are assigned to the shortest queue among a randomly chosen subset of $d$ queues, and leave the network on completion of service. Prior work on dynamical properties of this model has focused on the case of exponential service distributions. In this work, we analyze the more realistic case of general service distributions. We first introduce a novel particle representation of the state of the network, and characterize the state dynamics via a sequence of interacting measure-valued stochastic processes. Under mild assumptions, we show that the sequence of scaled state processes converges, as the number of servers goes to infinity, to a hydrodynamic limit that is characterized as the unique solution to a countable system of coupled deterministic measure-valued equations. We also establish a propagation of chaos result that shows that finite collections of queues are asymptotically independent. The general framework developed here is potentially useful for analyzing a larger class of models arising in diverse fields including biology and materials science.
  • We formulate a continuous version of the well known discrete hardcore (or independent set) model on a locally finite graph, parameterized by the so-called activity parameter $\lambda > 0$. In this version, the state or "spin value" $x_u$ of any node $u$ of the graph lies in the interval $[0,1]$, the hardcore constraint $x_u + x_v \leq 1$ is satisfied for every edge $(u,v)$ of the graph, and the space of feasible configurations is given by a convex polytope. When the graph is a regular tree, we show that there is a unique Gibbs measure associated to each activity parameter $\lambda>0$. Our result shows that, in contrast to the standard discrete hardcore model, the continuous hardcore model does not exhibit a phase transition on the infinite regular tree. We also consider a family of continuous models that interpolate between the discrete and continuous hardcore models on a regular tree when $\lambda = 1$ and show that each member of the family has a unique Gibbs measure, even when the discrete model does not. In each case, the proof entails the analysis of an associated Hamiltonian dynamical system that describes a certain limit of the marginal distribution at a node. Furthermore, given any sequence of regular graphs with fixed degree and girth diverging to infinity, we apply our results to compute the asymptotic limit of suitably normalized volumes of the corresponding sequence of convex polytopes of feasible configurations. In particular, this yields an approximation for the partition function of the continuous hard core model on a regular graph with large girth in the case $\lambda = 1$.
  • Reflected diffusions in convex polyhedral domains arise in a variety of applications, including interacting particle systems, queueing networks, biochemical reaction networks and mathematical finance. Under suitable conditions on the data, we establish pathwise differentiability of such a reflected diffusion with respect to its defining parameters --- namely, its initial condition, drift and diffusion coefficients, and (oblique) directions of reflection along the boundary of the domain. We characterize the right-continuous regularization of a pathwise derivative of the reflected diffusion as the pathwise unique solution to a constrained linear stochastic differential equation with jumps whose drift and diffusion coefficients, domain and directions of reflection depend on the state of the reflected diffusion. The proof of this result relies on properties of directional derivatives of the associated (extended) Skorokhod reflection map and their characterization in terms of a so-called derivative problem, and also involves establishing certain path properties of the reflected diffusion at nonsmooth parts of the boundary of the polyhedral domain, which may be of independent interest. As a corollary, we obtain a probabilistic representation for derivatives of expectations of functionals of reflected diffusions, which is useful for sensitivity analysis of reflected diffusions.
  • It is often possible to speed up the mixing of a Markov chain $\{ X_{t} \}_{t \in \mathbb{N}}$ on a state space $\Omega$ by \textit{lifting}, that is, running a more efficient Markov chain $\{ \hat{X}_{t} \}_{t \in \mathbb{N}}$ on a larger state space $\hat{\Omega} \supset \Omega$ that projects to $\{ X_{t} \}_{t \in \mathbb{N}}$ in a certain sense. In [CLP99], Chen, Lov{\'a}sz and Pak prove that for Markov chains on finite state spaces, the mixing time of any lift of a Markov chain is at least the square root of the mixing time of the original chain, up to a factor that depends on the stationary measure. Unfortunately, this extra factor makes the bound in [CLP99] very loose for Markov chains on large state spaces and useless for Markov chains on continuous state spaces. In this paper, we develop an extension of the evolving set method that allows us to refine this extra factor and find bounds for Markov chains on continuous state spaces that are analogous to the bounds in [CLP99]. These bounds also allow us to improve on the bounds in [CLP99] for some chains on finite state spaces.
  • We study a static game played by a finite number of agents, in which agents are assigned independent and identically distributed random types and each agent minimizes its objective function by choosing from a set of admissible actions that depends on its type. The game is anonymous in the sense that the objective function of each agent depends on the actions of other agents only through the empirical distribution of their type-action pairs. We study the asymptotic behavior of Nash equilibria, as the number of agents tends to infinity, first by deriving laws of large numbers characterizes almost sure limit points of Nash equilibria in terms of so-called Cournot-Nash equilibria of an associated nonatomic game. Our main results are large deviation principles that characterize the probability of rare Nash equilibria and associated conditional limit theorems describing the behavior of equilibria conditioned on a rare event. The results cover situations when neither the finite-player game nor the associated nonatomic game has a unique equilibrium. In addition, we study the asymptotic behavior of the price of anarchy, complementing existing worst-case bounds with new probabilistic bounds in the context of congestion games, which are used to model traffic routing in networks.
  • We introduce a two-component infinite-dimensional Markov process that serves as a diffusion model for a certain parallel server queue called the GI/GI/N queue, in the so-called Halfin-Whitt asymptotic regime. Under suitable assumptions on the service distribution, we characterize this process as the unique solution to a pair of stochastic evolution equations comprised of a real-valued It\^{o} equation and a stochastic partial differential equation on the positive half line, which are coupled together by a nonlinear boundary condition. We construct an asymptotic (equivalent) coupling to show that this Markov process has a unique invariant distribution. These results are used in a companion paper to show that the sequence of suitably scaled and centered stationary distributions of the GI/GI/N queue converges to the unique invariant distribution of the diffusion model, thus resolving (for a large class service distributions) an open problem raised by Halfin and Whitt in 1981. The methods introduced here are more generally applicable for the analysis of a broader class of networks.
  • We consider the so-called GI/GI/N queue, in which a stream of jobs with independent and identically distributed service times arrive as a renewal process to a common queue that is served by $N$ identical parallel servers in a first-come-first-serve manner. We introduce a new representation for the state of the system and, under general conditions on the service and interarrival distributions, establish convergence of the corresponding sequence of centered and scaled stationary distributions in the so-called Halfin-Whitt asymptotic regime. In particular, this resolves an open question posed by Halfin and Whitt in 1981. We also characterize the limit as the stationary distribution of an infinite-dimensional two-component Markov process that is the unique solution to a certain stochastic partial differential equation. Previous results were essentially restricted to exponential service distributions or service distributions with finite support, for which the corresponding limit process admits a reduced finite-dimensional Markovian representation. We develop a different approach to deal with the general case when the Markovian representation of the limit is truly infinite-dimensional. This approach is more broadly applicable to a larger class of networks.
  • We show that for all positive beta the semigroups of beta-Dyson Brownian motions of different dimensions are intertwined. The proof relates beta-Dyson Brownian motions directly to Jack symmetric polynomials and omits an approximation of the former by discrete space Markov chains, thereby disposing of the technical assumption beta>1 in [GS]. The corresponding results for beta-Dyson Ornstein-Uhlenbeck processes are also presented.
  • The Skorokhod map on the half-line has proved to be a useful tool for studying processes with non-negativity constraints. In this work we introduce a measure-valued analog of this map that transforms each element $\zeta$ of a certain class of c\`{a}dl\`{a}g paths that take values in the space of signed measures on the half-line to a c\`{a}dl\`{a}g path that takes values in the space of non-negative measures on $[0,\infty)$ in such a way that for each $x > 0$, the path $t \mapsto \zeta_t[0,x]$ is transformed via a Skorokhod map on the half-line, and the regulating functions for different $x > 0$ are coupled. We establish regularity properties of this map and show that the map provides a convenient tool for studying queueing systems in which tasks are prioritized according to a continuous parameter. Three such well known models are the earliest-deadline-first, the shortest-job-first and the shortest-remaining-processing-time scheduling policies. For these applications, we show how the map provides a unified framework within which to form fluid model equations, prove uniqueness of solutions to these equations and establish convergence of scaled state processes to the fluid model. In particular, for these models, we obtain new convergence results in time-inhomogeneous settings, which appear to fall outside the purview of existing approaches.
  • The study of both sensitivity analysis and differentiability of the stochastic flow of a reflected process in a convex polyhedral domain is challenging because the dynamics are discontinuous at the boundary of the domain and the boundary of the domain is not smooth. These difficulties can be addressed by studying directional derivatives of an associated extended Skorokhod map, which is a deterministic mapping that takes an unconstrained path to a suitably reflected version. In this work we develop an axiomatic framework for the analysis of directional derivatives of a large class of Lipschitz continuous extended Skorokhod maps in convex polyhedral domains with oblique directions of reflection. We establish existence of directional derivatives at a path whose reflected version satisfies a certain boundary jitter property, and also show that the right-continuous regularization of such a directional derivative can be characterized as the unique solution to a Skorokhod-type problem, where both the domain and directions of reflection vary (discontinuously) with time. A key ingredient in the proof is establishing certain contraction properties for a family of (oblique) derivative projection operators. As an application, we establish pathwise differentiability of reflected Brownian motion in the nonnegative quadrant with respect to the initial condition, drift vector, dispersion matrix and directions of reflection. The results of this paper are also used in subsequent work to establish pathwise differentiability of a much larger class of reflected diffusions in convex polyhedral domains.
  • We establish a large deviation principle for the empirical measure process associated with a general class of finite-state mean field interacting particle systems with Lipschitz continuous transition rates that satisfy a certain ergodicity condition. The approach is based on a variational representation for functionals of a Poisson random measure. Under an appropriate strengthening of the ergodicity condition, we also prove a locally uniform large deviation principle. The main novelty is that more than one particle is allowed to change its state simultaneously, and so a standard approach to the proof based on a change of measure with respect to a system of independent particles is not possible. The result is shown to be applicable to a wide range of models arising from statistical physics, queueing systems and communication networks. Along the way, we establish a large deviation principle for a class of jump Markov processes on the simplex, whose rates decay to zero as they approach the boundary of the domain. This result may be of independent interest.
  • We introduce a general framework for the mean-field analysis of large-scale load-balancing networks with general service distributions. Specifically, we consider a parallel server network that consists of N queues and operates under the $SQ(d)$ load balancing policy, wherein jobs have independent and identical service requirements and each incoming job is routed on arrival to the shortest of $d$ queues that are sampled uniformly at random from $N$ queues. We introduce a novel state representation and, for a large class of arrival processes, including renewal and time-inhomogeneous Poisson arrivals, and mild assumptions on the service distribution, show that the mean-field limit, as $N \rightarrow \infty$, of the state can be characterized as the unique solution of a sequence of coupled partial integro-differential equations, which we refer to as the hydrodynamic PDE. We use a numerical scheme to solve the PDE to obtain approximations to the dynamics of large networks and demonstrate the efficacy of these approximations using Monte Carlo simulations. We also illustrate how the PDE can be used to gain insight into network performance.
  • Let $p\in[1,\infty]$. Consider the projection of a uniform random vector from a suitably normalized $\ell^p$ ball in $\mathbb{R}^n$ onto an independent random vector from the unit sphere. We show that sequences of such random projections, when suitably normalized, satisfy a large deviation principle (LDP) as the dimension $n$ goes to $\infty$, which can be viewed as an annealed LDP. We also establish a quenched LDP (conditioned on a fixed sequence of projection directions) and show that for $p\in(1,\infty]$ (but not for $p=1$), the corresponding rate function is "universal", in the sense that it coincides for "almost every" sequence of projection directions. We also analyze some exceptional sequences of directions in the "measure zero" set, including the directions corresponding to the classical Cram\'er's theorem, and show that those directions yield LDPs with rate functions that are distinct from the universal rate function of the quenched LDP. Lastly, we identify a variational formula that relates the annealed and quenched LDPs, and analyze the minimizer of this variational formula. These large deviation results complement the central limit theorem for convex sets, specialized to the case of sequences of $\ell^p$ balls.
  • We construct obliquely reflected Brownian motions in all bounded simply connected planar domains, including non-smooth domains, with general reflection vector fields on the boundary. Conformal mappings and excursion theory are our main technical tools. A key intermediate step, which may be of independent interest, is an alternative characterization of reflected Brownian motions in smooth bounded planar domains with a given field of angles of oblique reflection on the boundary in terms of a pair of quantities, namely an integrable positive harmonic function, which represents the stationary distribution of the process, and a real number that represents, in a suitable sense, the asymptotic rate of rotation of the process around a reference point in the domain. Furthermore, we also show that any obliquely reflected Brownian motion in a simply connected Jordan domain can be obtained as a suitable limit of obliquely reflected Brownian motions in smooth domains.
  • The empirical mean of $n$ independent and identically distributed (i.i.d.) random variables $(X_1,\dots,X_n)$ can be viewed as a suitably normalized scalar projection of the $n$-dimensional random vector $X^{(n)}\doteq(X_1,\dots,X_n)$ in the direction of the unit vector $n^{-1/2}(1,1,\dots,1) \in \mathbb{S}^{n-1}$. The large deviation principle (LDP) for such projections as $n\rightarrow\infty$ is given by the classical Cram\'er's theorem. We prove an LDP for the sequence of normalized scalar projections of $X^{(n)}$ in the direction of a generic unit vector $\theta^{(n)} \in \mathbb{S}^{n-1}$, as $n\rightarrow\infty$. This LDP holds under fairly general conditions on the distribution of $X_1$, and for "almost every" sequence of directions $(\theta^{(n)})_{n\in\mathbb{N}}$. The associated rate function is "universal" in the sense that it does not depend on the particular sequence of directions. Moreover, under mild additional conditions on the law of $X_1$, we show that the universal rate function differs from the Cram\'er rate function, thus showing that the sequence of directions $n^{-1/2}(1,1,\dots,1) \in \mathbb{S}^{n-1},$ $n \in \mathbb{N}$, corresponding to Cram\'er's theorem is atypical.
  • The limits of scaled relative entropies between probability distributions associated with N-particle weakly interacting Markov processes are considered. The convergence of such scaled relative entropies is established in various settings. The analysis is motivated by the role relative entropy plays as a Lyapunov function for the (linear) Kolmogorov forward equation associated with an ergodic Markov process, and Lyapunov function properties of these scaling limits with respect to nonlinear finite-state Markov processes are studied in the companion paper [6].
  • The focus of this work is on local stability of a class of nonlinear ordinary differential equations (ODE) that describe limits of empirical measures associated with finite-state weakly interacting N-particle systems. Local Lyapunov functions are identified for several classes of such ODE, including those associated with systems with slow adaptation and Gibbs systems. Using results from [5] and large deviations heuristics, a partial differential equation (PDE) associated with the nonlinear ODE is introduced and it is shown that positive definite subsolutions of this PDE serve as local Lyapunov functions for the ODE. This PDE characterization is used to construct explicit Lyapunov functions for a broad class of models called locally Gibbs systems. This class of models is significantly larger than the family of Gibbs systems and several examples of such systems are presented, including models with nearest neighbor jumps and models with simultaneous jumps that arise in applications.
  • We consider the probability that a weighted sum of $n$ i.i.d. random variables $X_j$, $j = 1, . . ., n$, with stretched exponential tails is larger than its expectation and determine the rate of its decay, under suitable conditions on the weights. We show that the decay is subexponential, and identify the rate function in terms of the tails of $X_j$ and the weights. Our result generalizes the large deviation principle given by Kiesel and Stadtm\"uller [8] as well as the tail asymptotics for sums of i.i.d. random variables provided by Nagaev [10, 11]. As an application of our result, motivated by random projections of high-dimensional vectors, we consider the case of random, self-normalized weights that are independent of the sequence $\{X_j\}_{j \in \mathbb N}$, identify the decay rate for both the quenched and annealed large deviations in this case, and show that they coincide. As another example we consider weights derived from kernel functions that arise in non-parametric regression.
  • Two frameworks that have been used to characterize reflected diffusions include stochastic differential equations with reflection and the so-called submartingale problem. We introduce a general formulation of the submartingale problem for (obliquely) reflected diffusions in domains with piecewise C^2 boundaries and piecewise continuous reflection vector fields. Under suitable assumptions, we show that well-posedness of the submartingale problem is equivalent to existence and uniqueness in law of weak solutions to the corresponding stochastic differential equation with reflection. Our result generalizes to the case of reflecting diffusions a classical result due to Stroock and Varadhan on the equivalence of well-posedness of martingale problems and well-posedness of weak solutions of stochastic differential equations in d-dimensional Euclidean space. The analysis in the case of reflected diffusions in domains with non-smooth boundaries is considerably more subtle and requires a careful analysis of the behavior of the reflected diffusion on the boundary of the domain. In particular, the equivalence can fail to hold when our assumptions are not satisfied. The equivalence we establish allows one to transfer results on reflected diffusions characterized by one approach to reflected diffusions analyzed by the other approach. As an application, we provide a characterization of stationary distributions of a large class of reflected diffusions in convex polyhedral domains.
  • The paper studies distributed static parameter (vector) estimation in sensor networks with nonlinear observation models and noisy inter-sensor communication. It introduces \emph{separably estimable} observation models that generalize the observability condition in linear centralized estimation to nonlinear distributed estimation. It studies two distributed estimation algorithms in separably estimable models, the $\mathcal{NU}$ (with its linear counterpart $\mathcal{LU}$) and the $\mathcal{NLU}$. Their update rule combines a \emph{consensus} step (where each sensor updates the state by weight averaging it with its neighbors' states) and an \emph{innovation} step (where each sensor processes its local current observation.) This makes the three algorithms of the \textit{consensus + innovations} type, very different from traditional consensus. The paper proves consistency (all sensors reach consensus almost surely and converge to the true parameter value,) efficiency, and asymptotic unbiasedness. For $\mathcal{LU}$ and $\mathcal{NU}$, it proves asymptotic normality and provides convergence rate guarantees. The three algorithms are characterized by appropriately chosen decaying weight sequences. Algorithms $\mathcal{LU}$ and $\mathcal{NU}$ are analyzed in the framework of stochastic approximation theory; algorithm $\mathcal{NLU}$ exhibits mixed time-scale behavior and biased perturbations, and its analysis requires a different approach that is developed in the paper.
  • A many-server queueing system is considered in which customers arrive according to a renewal process and have service and patience times that are drawn from two independent sequences of independent, identically distributed random variables. Customers enter service in the order of arrival and are assumed to abandon the queue if the waiting time in queue exceeds the patience time. The state of the system with $N$ servers is represented by a four-component process that consists of the forward recurrence time of the arrival process, a pair of measure-valued processes, one that keeps track of the waiting times of customers in queue and the other that keeps track of the amounts of time customers present in the system have been in service and a real-valued process that represents the total number of customers in the system. Under general assumptions, it is shown that the state process is a Feller process, admits a stationary distribution and is ergodic. It is also shown that the associated sequence of scaled stationary distributions is tight, and that any subsequence converges to an invariant state for the fluid limit. In particular, this implies that when the associated fluid limit has a unique invariant state, then the sequence of stationary distributions converges, as $N\rightarrow \infty$, to the invariant state. In addition, a simple example is given to illustrate that, both in the presence and absence of abandonments, the $N\rightarrow \infty$ and $t\rightarrow \infty$ limits cannot always be interchanged.