
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.

We prove a large deviation principle (LDP) for a general class of Banach
space valued stochastic differential equations (SDE) that is uniform with
respect to initial conditions in bounded subsets of the Banach space. A key
step in the proof is showing that a uniform large deviation principle over
compact sets is implied by a uniform over compact sets Laplace principle.
Because bounded subsets of infinite dimensional Banach spaces are in general
not relatively compact in the norm topology, we embed the Banach space into its
double dual and utilize the weak$\star $ compactness of closed bounded sets in
the double dual space. We prove that a modified version of our stochastic
differential equation satisfies a uniform Laplace principle over weak$\star $
compact sets and consequently a uniform over bounded sets large deviation
principle. We then transfer this result back to the original equation using a
contraction principle. The main motivation for this uniform LDP is to
generalize results of Freidlin and Wentzell concerning the behavior of finite
dimensional SDEs. Here we apply the uniform LDP to study the asymptotics of
exit times from bounded sets of Banach space valued small noise SDE, including
reaction diffusion equations with multiplicative noise and $2$dimensional
stochastic NavierStokes equations with multiplicative noise.

The configuration model is a sequence of random graphs constructed such that
in the large network limit the degree distribution converges to a prespecified
probability distribution. The component structure of such random graphs can be
obtained from an infinite dimensional Markov chain referred to as the
exploration process. We establish a large deviation principle for the
exploration process associated with the configuration model. Proofs rely on a
representation of the exploration process as a system of stochastic
differential equations driven by Poisson random measures and variational
formulas for moments of nonnegative functionals of Poisson random measures.
Uniqueness results for certain controlled systems of deterministic equations
play a key role in the analysis. Applications of the large deviation results,
for studying asymptotic behavior of the degree sequence in large components of
the random graphs, are discussed.

A large deviation principle is established for a twoscale stochastic system
in which the slow component is a continuous process given by a small noise
finite dimensional It\^{o} stochastic differential equation, and the fast
component is a finite state pure jump process. Previous works have considered
settings where the coupling between the components is weak in a certain sense.
In the current work we study a fully coupled system in which the drift and
diffusion coefficient of the slow component and the jump intensity function and
jump distribution of the fast process depend on the states of both components.
In addition, the diffusion can be degenerate. Our proofs use certain stochastic
control representations for expectations of exponential functionals of finite
dimensional Brownian motions and Poisson random measures together with weak
convergence arguments. A key challenge is in the proof of the large deviation
lower bound where, due to the interplay between the degeneracy of the diffusion
and the full dependence of the coefficients on the two components, the
associated local rate function has poor regularity properties.

Parallel tempering, or replica exchange, is a popular method for simulating
complex systems. The idea is to run parallel simulations at different
temperatures, and at a given swap rate exchange configurations between the
parallel simulations. From the perspective of large deviations it is optimal to
let the swap rate tend to infinity and it is possible to construct a
corresponding simulation scheme, known as infinite swapping. In this paper we
propose a novel use of large deviations for empirical measures for a more
detailed analysis of the infinite swapping limit in the setting of continuous
time jump Markov processes. Using the large deviations rate function and
associated stochastic control problems we consider a diagnostic based on
temperature assignments, which can be easily computed during a simulation. We
show that the convergence of this diagnostic to its a priori known limit is a
necessary condition for the convergence of infinite swapping. The rate function
is also used to investigate the impact of asymmetries in the underlying
potential landscape, and where in the state space poor sampling is most likely
to occur.

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 discuss importance sampling schemes for the estimation of finite time exit
probabilities of small noise diffusions that involve escape from an
equilibrium. A factor that complicates the analysis is that rest points are
included in the domain of interest. We build importance sampling schemes with
provably good performance both preasymptotically, that is, for fixed size of
the noise, and asymptotically, that is, as the size of the noise goes to zero,
and that do not degrade as the time horizon gets large. Simulation studies
demonstrate the theoretical results.

Uncertainty quantification is a primary challenge for reliable modeling and
simulation of complex stochastic dynamics. Such problems are typically plagued
with incomplete information that may enter as uncertainty in the model
parameters, or even in the model itself. Furthermore, due to their dynamic
nature, we need to assess the impact of these uncertainties on the transient
and longtime behavior of the stochastic models and derive corresponding
uncertainty bounds for observables of interest. A special class of such
challenges is parametric uncertainties in the model and in particular
sensitivity analysis along with the corresponding sensitivity bounds for
stochastic dynamics. Moreover, sensitivity analysis can be further complicated
in models with a high number of parameters that render straightforward
approaches, such as gradient methods, impractical. In this paper, we derive
uncertainty and sensitivity bounds for pathspace observables of stochastic
dynamics in terms of new goaloriented divergences; the latter incorporate both
observables and information theory objects such as the relative entropy rate.
These bounds are tight, depend on the variance of the particular observable and
are computable through Monte Carlo simulation. In the case of sensitivity
analysis, the derived sensitivity bounds rely on the path Fisher Information
Matrix, hence they depend only on local dynamics and are gradientfree. These
features allow for computationally efficient implementation in systems with a
high number of parameters, e.g., complex reaction networks and molecular
simulations.

The large deviations principle for the empirical measure for both continuous
and discrete time Markov processes is well known. Various expressions are
available for the rate function, but these expressions are usually as the
solution to a variational problem, and in this sense not explicit. An
interesting class of continuous time, reversible processes was identified in
the original work of Donsker and Varadhan for which an explicit expression is
possible. While this class includes many (reversible) processes of interest, it
excludes the case of continuous time pure jump processes, such as a reversible
finite state Markov chain. In this paper, we study the large deviations
principle for the empirical measure of pure jump Markov processes and provide
an explicit formula of the rate function under reversibility.

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 introduce and illustrate a number of performance measures for rareevent
sampling methods. These measures are designed to be of use in a variety of
expanded ensemble techniques including parallel tempering as well as infinite
and partial infinite swapping approaches. Using a variety of selected
applications we address questions concerning the variation of sampling
performance with respect to key computational ensemble parameters.

Moderate deviation principles for stochastic differential equations driven by
a Poisson random measure (PRM) in finite and infinite dimensions are obtained.
Proofs are based on a variational representation for expected values of
positive functionals of a PRM.

We prove a moderate deviation principle for the continuous time interpolation
of discrete time recursive stochastic processes. The methods of proof are
somewhat different from the corresponding large deviation result, and in
particular the proof of the upper bound is more complicated. The results can be
applied to the design of accelerated Monte Carlo algorithms for certain
problems, where schemes based on moderate deviations are easier to construct
and in certain situations provide performance comparable to those based on
large deviations.

We extend the duality between exponential integrals and relative entropy to a
variational formula for exponential integrals involving the Renyi divergence.
This formula characterizes the dependence of risksensitive functionals and
related quantities determined by tail behavior to perturbations in the
underlying distributions, in terms of the Renyi divergence. The
characterization gives rise to upper and lower bounds that are meaningful for
all values of a large deviation scaling parameter, allowing one to quantify in
explicit terms the robustness of risksensitive costs. As applications we
consider problems of uncertainty quantification when aspects of the model are
not fully known, as well their use in bounding tail properties of an
intractable model in terms of a tractable one.

We study large deviation properties of systems of weakly interacting
particles modeled by It\^{o} stochastic differential equations (SDEs). It is
known under certain conditions that the corresponding sequence of empirical
measures converges, as the number of particles tends to infinity, to the weak
solution of an associated McKeanVlasov equation. We derive a large deviation
principle via the weak convergence approach. The proof, which avoids
discretization arguments, is based on a representation theorem, weak
convergence and ideas from stochastic optimal control. The method works under
rather mild assumptions and also for models described by SDEs not of diffusion
type. To illustrate this, we treat the case of SDEs with delay.

Stochastic partial differential equations driven by Poisson random measures
(PRM) have been proposed as models for many different physical systems, where
they are viewed as a refinement of a corresponding noiseless partial
differential equations (PDE). A systematic framework for the study of
probabilities of deviations of the stochastic PDE from the deterministic PDE is
through the theory of large deviations. The goal of this work is to develop the
large deviation theory for small Poisson noise perturbations of a general class
of deterministic infinite dimensional models. Although the analogous questions
for finite dimensional systems have been well studied, there are currently no
general results in the infinite dimensional setting. This is in part due to the
fact that in this setting solutions may have little spatial regularity, and
thus classical approximation methods for large deviation analysis become
intractable. The approach taken here, which is based on a variational
representation for nonnegative functionals of general PRM, reduces the proof of
the large deviation principle to establishing basic qualitative properties for
controlled analogues of the underlying stochastic system. As an illustration of
the general theory, we consider a particular system that models the spread of a
pollutant in a waterway.

In the present paper we identify a rigorous property of a number of
temperingbased Monte Carlo sampling methods, including parallel tempering as
well as partial and infinite swapping. Based on this property we develop a
variety of performance measures for such rareevent sampling methods that are
broadly applicable, informative, and straightforward to implement. We
illustrate the use of these performance measures with a series of applications
involving the equilibrium properties of simple LennardJones clusters,
applications for which the performance levels of partial and infinite swapping
approaches are found to be higher than those of conventional parallel
tempering.

Parallel tempering, also known as replica exchange sampling, is an important
method for simulating complex systems. In this algorithm simulations are
conducted in parallel at a series of temperatures, and the key feature of the
algorithm is a swap mechanism that exchanges configurations between the
parallel simulations at a given rate. The mechanism is designed to allow the
low temperature system of interest to escape from deep local energy minima
where it might otherwise be trapped, via those swaps with the higher
temperature components. In this paper we introduce a performance criteria for
such schemes based on large deviation theory, and argue that the rate of
convergence is a monotone increasing function of the swap rate. This motivates
the study of the limit process as the swap rate goes to infinity. We construct
a scheme which is equivalent to this limit in a distributional sense, but which
involves no swapping at all. Instead, the effect of the swapping is captured by
a collection of weights that influence both the dynamics and the empirical
measure. While theoretically optimal, this limit is not computationally
feasible when the number of temperatures is large, and so variations that are
easy to implement and nearly optimal are also developed.

We construct importance sampling schemes for stochastic differential
equations with small noise and fast oscillating coefficients. Standard Monte
Carlo methods perform poorly for these problems in the small noise limit. With
multiscale processes there are additional complications, and indeed the
straightforward adaptation of methods for standard small noise diffusions will
not produce efficient schemes. Using the subsolution approach we construct
schemes and identify conditions under which the schemes will be asymptotically
optimal. Examples and simulation results are provided.

We describe a new approach to the rareevent Monte Carlo sampling problem.
This technique utilizes a symmetrization strategy to create probability
distributions that are more highly connected and thus more easily sampled than
their original, potentially sparse counterparts. After discussing the formal
outline of the approach and devising techniques for its practical
implementation, we illustrate the utility of the technique with a series of
numerical applications to LennardJones clusters of varying complexity and
rareevent character.

We apply the splitting method to three wellknown counting problems, namely
3SAT, random graphs with prescribed degrees, and binary contingency tables. We
present an enhanced version of the splitting method based on the
capturerecapture technique, and show by experiments the superiority of this
technique for SAT problems in terms of variance of the associated estimators,
and speed of the algorithms.

Much of uncertainty quantification to date has focused on determining the
effect of variables modeled probabilistically, and with a known distribution,
on some physical or engineering system. We develop methods to obtain
information on the system when the distributions of some variables are known
exactly, others are known only approximately, and perhaps others are not
modeled as random variables at all. The main tool used is the duality between
risksensitive integrals and relative entropy, and we obtain explicit bounds on
standard performance measures (variances, exceedance probabilities) over
families of distributions whose distance from a nominal distribution is
measured by relative entropy. The evaluation of the risksensitive expectations
is based on polynomial chaos expansions, which help keep the computational
aspects tractable.

We study the large deviations principle for locally periodic stochastic
differential equations with small noise and fast oscillating coefficients.
There are three possible regimes depending on how fast the intensity of the
noise goes to zero relative to the homogenization parameter. We use weak
convergence methods which provide convenient representations for the action
functional for all three regimes. Along the way we study weak limits of related
controlled SDEs with fast oscillating coefficients and derive, in some cases, a
control that nearly achieves the large deviations lower bound at the prelimit
level. This control is useful for designing efficient importance sampling
schemes for multiscale diffusions driven by small noise.

A large deviation principle is established for a general class of stochastic
flows in the small noise limit. This result is then applied to a Bayesian
formulation of an image matching problem, and an approximate maximum likelihood
property is shown for the solution of an optimization problem involving the
large deviations rate function.