
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 Wassersteintype 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 highdimensional 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 highdimensional 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
highdimensional 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 socalled
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 McKeanVlasov 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 McKeanVlasov systems. We also illustrate the broader applicability of
our methodology by applying it to establish a CLT for a specific
linearquadratic 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 nonasymptotic 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 infinitedimensional partial differential
equation that characterizes the value function of the mean field game, to
construct an associated McKeanVlasov 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 McKeanVlasov 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
McKeanVlasov 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
measurevalued 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 measurevalued 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
socalled 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
rightcontinuous 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 socalled 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 typeaction 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 socalled CournotNash 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
finiteplayer game nor the associated nonatomic game has a unique equilibrium.
In addition, we study the asymptotic behavior of the price of anarchy,
complementing existing worstcase bounds with new probabilistic bounds in the
context of congestion games, which are used to model traffic routing in
networks.

We introduce a twocomponent infinitedimensional Markov process that serves
as a diffusion model for a certain parallel server queue called the GI/GI/N
queue, in the socalled HalfinWhitt 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
realvalued 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 socalled 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
firstcomefirstserve 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 socalled HalfinWhitt 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
infinitedimensional twocomponent 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 finitedimensional Markovian representation. We develop a
different approach to deal with the general case when the Markovian
representation of the limit is truly infinitedimensional. This approach is
more broadly applicable to a larger class of networks.

We show that for all positive beta the semigroups of betaDyson Brownian
motions of different dimensions are intertwined. The proof relates betaDyson
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
betaDyson OrnsteinUhlenbeck processes are also presented.

The Skorokhod map on the halfline has proved to be a useful tool for
studying processes with nonnegativity constraints. In this work we introduce a
measurevalued 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 halfline to a c\`{a}dl\`{a}g path that takes values in the
space of nonnegative 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
halfline, 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
earliestdeadlinefirst, the shortestjobfirst and the
shortestremainingprocessingtime 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 timeinhomogeneous 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 rightcontinuous regularization of such
a directional derivative can be characterized as the unique solution to a
Skorokhodtype 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 finitestate 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 meanfield analysis of largescale
loadbalancing 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 timeinhomogeneous Poisson arrivals, and mild
assumptions on the service distribution, show that the meanfield limit, as $N
\rightarrow \infty$, of the state can be characterized as the unique solution
of a sequence of coupled partial integrodifferential 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 nonsmooth 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}^{n1}$. 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}^{n1}$, 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}^{n1},$ $n \in \mathbb{N}$, corresponding
to Cram\'er's theorem is atypical.

The limits of scaled relative entropies between probability distributions
associated with Nparticle 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 finitestate 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 finitestate weakly interacting Nparticle 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 highdimensional vectors, we consider the
case of random, selfnormalized 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
nonparametric regression.

Two frameworks that have been used to characterize reflected diffusions
include stochastic differential equations with reflection and the socalled
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 wellposedness 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 wellposedness of martingale
problems and wellposedness of weak solutions of stochastic differential
equations in ddimensional Euclidean space. The analysis in the case of
reflected diffusions in domains with nonsmooth 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 intersensor
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
timescale behavior and biased perturbations, and its analysis requires a
different approach that is developed in the paper.

A manyserver 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
fourcomponent process that consists of the forward recurrence time of the
arrival process, a pair of measurevalued 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
realvalued 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.