• ### Positive feedback in coordination games: stochastic evolutionary dynamics and the logit choice rule(1701.04870)

Feb. 15, 2018 cs.GT
We show that under the logit dynamics, positive feedback among agents (also called bandwagon property) induces evolutionary paths along which agents repeat the same actions consecutively so as to minimize the payoff loss incurred by the feedback effects. In particular, for paths escaping the domain of attraction of a given equilibrium-called a convention-positive feedback implies that along the minimum cost escaping paths, agents always switch first from the status quo convention strategy before switching from other strategies. In addition, the relative strengths of positive feedback effects imply that the same transitions occur repeatedly in the cost minimizing escape paths. By combining these two effects, we show that in an escaping transition from one convention to another, the least unlikely escape paths from the status quo convention consist of only the repeated identical mistakes of agents. Using our results on the exit problem, we then characterize the stochastically stable states under the logit choice rule for a class of non-potential games with an arbitrary number of strategies.
• ### Non-Equilibrium Steady States for Networks of Oscillators(1712.09413)

Non-equilibrium steady states for chains of oscillators (masses) connected by harmonic and anharmonic springs and interacting with heat baths at different temperatures have been the subject of several studies. In this paper, we show how some of the results extend to more complicated networks. We establish the existence and uniqueness of the non-equilibrium steady state, and show that the system converges to it at an exponential rate. The arguments are based on controllability and conditions on the potentials at infinity.
• ### How biased is your model? Concentration Inequalities, Information and Model Bias(1706.10260)

June 30, 2017 cs.IT, math.IT, math.PR
We derive tight and computable bounds on the bias of statistical estimators, or more generally of quantities of interest, when evaluated on a baseline model P rather than on the typically unknown true model Q. Our proposed method combines the scalable information inequality derived by P. Dupuis, K.Chowdhary, the authors and their collaborators together with classical concentration inequalities (such as Bennett's and Hoeffding-Azuma inequalities). Our bounds are expressed in terms of the Kullback-Leibler divergence R(Q||P) of model Q with respect to P and the moment generating function for the statistical estimator under P. Furthermore, concentration inequalities, i.e. bounds on moment generating functions, provide tight and computationally inexpensive model bias bounds for quantities of interest. Finally, they allow us to derive rigorous confidence bands for statistical estimators that account for model bias and are valid for an arbitrary amount of data.
• ### Strategic Decompositions of Normal Form Games: Zero-sum Games and Potential Games(1602.06648)

May 19, 2020 cs.GT
We study new classes of games, called zero-sum equivalent games and zero-sum equivalent potential games, and prove decomposition theorems involving these classes of games. We say that two games are "strategically equivalent" if, for every player, the payoff differences between two strategies (holding other players' strategies fixed) are identical. A zero-sum equivalent game is a game that is strategically equivalent to a zero-sum game; a zero-sum equivalent potential game is a zero-sum equivalent game that is strategically equivalent to a common interest game. We also call a game "normalized" if the sum of one player's payoffs, given the other players' strategies, is always zero. We show that any normal form game can be uniquely decomposed into either (i) a zero-sum equivalent game and a normalized common interest game, or (ii) a zero-sum equivalent potential game, a normalized zero-sum game, and a normalized common interest game, each with distinctive equilibrium properties. For example, we show that two-player zero-sum equivalent games with finite strategy sets generically have a unique Nash equilibrium and that two-player zero-sum equivalent potential games with finite strategy sets generically have a strictly dominant Nash equilibrium.
• ### Information Criteria for quantifying loss of reversibility in parallelized KMC(1605.02375)

Oct. 17, 2016 math.NA, cs.IT, math.IT
Parallel Kinetic Monte Carlo (KMC) is a potent tool to simulate stochastic particle systems efficiently. However, despite literature on quantifying domain decomposition errors of the particle system for this class of algorithms in the short and in the long time regime, no study yet explores and quantifies the loss of time-reversibility in Parallel KMC. Inspired by concepts from non-equilibrium statistical mechanics, we propose the entropy production per unit time, or entropy production rate, given in terms of an observable and a corresponding estimator, as a metric that quantifies the loss of reversibility. Typically, this is a quantity that cannot be computed explicitly for Parallel KMC, which is why we develop a posteriori estimators that have good scaling properties with respect to the size of the system. Through these estimators, we can connect the different parameters of the scheme, such as the communication time step of the parallelization, the choice of the domain decomposition, and the computational schedule, with its performance in controlling the loss of reversibility. From this point of view, the entropy production rate can be seen both as an information criterion to compare the reversibility of different parallel schemes and as a tool to diagnose reversibility issues with a particular scheme. As a demonstration, we use Sandia Lab's SPPARKS software to compare different parallelization schemes and different domain (lattice) decompositions.
• ### Information metrics for long-time errors in splitting schemes for stochastic dynamics and parallel KMC(1511.08240)

Oct. 4, 2016 math.NA, math.PR
We propose an information-theoretic approach to analyze the long-time behavior of numerical splitting schemes for stochastic dynamics, focusing primarily on Parallel Kinetic Monte Carlo (KMC) algorithms.Established methods for numerical operator splittings provide error estimates in finite-time regimes, in terms of the order of the local error and the associated commutator. Path-space information-theoretic tools such as the relative entropy rate (RER) allow us to control long-time error through commutator calculations. Furthermore, they give rise to an a posteriori representation of the error which can thus be tracked in the course of a simulation. Another outcome of our analysis is the derivation of a path-space information criterion for comparison (and possibly design) of numerical schemes, in analogy to classical information criteria for model selection and discrimination. In the context of Parallel KMC, our analysis allows us to select schemes with improved numerical error and more efficient processor communication. We expect that such a path-space information perspective on numerical methods will be broadly applicable in stochastic dynamics, both for the finite and the long-time regime.
• ### Uncertainty quantification for generalized Langevin dynamics(1609.02739)

Sept. 9, 2016 math.NA, math.PR
We present efficient finite difference estimators for goal-oriented sensitivity indices with applications to the generalized Langevin equation (GLE). In particular, we apply these estimators to analyze an extended variable formulation of the GLE where other well known sensitivity analysis techniques such as the likelihood ratio method are not applicable to key parameters of interest. These easily implemented estimators are formed by coupling the nominal and perturbed dynamics appearing in the finite difference through a common driving noise, or common random path. After developing a general framework for variance reduction via coupling, we demonstrate the optimality of the common random path coupling in the sense that it produces a minimal variance surrogate for the difference estimator relative to sampling dynamics driven by independent paths. In order to build intuition for the common random path coupling, we evaluate the efficiency of the proposed estimators for a comprehensive set of examples of interest in particle dynamics. These reduced variance difference estimators are also a useful tool for performing global sensitivity analysis and for investigating non-local perturbations of parameters, such as increasing the number of Prony modes active in an extended variable GLE.
• ### Improving the convergence of reversible samplers(1601.08118)

June 9, 2016 math-ph, math.MP, math.PR, stat.ME
In Monte-Carlo methods the Markov processes used to sample a given target distribution usually satisfy detailed balance, i.e. they are time-reversible. However, relatively recent results have demonstrated that appropriate reversible and irreversible perturbations can accelerate convergence to equilibrium. In this paper we present some general design principles which apply to general Markov processes. Working with the generator of Markov processes, we prove that for some of the most commonly used performance criteria, i.e., spectral gap, asymptotic variance and large deviation functionals, sampling is improved for appropriate reversible and irreversible perturbations of some initially given reversible sampler. Moreover we provide specific constructions for such reversible and irreversible perturbations for various commonly used Markov processes, such as Markov chains and diffusions. In the case of diffusions, we make the discussion more specific using the large deviations rate function as a measure of performance.
• ### Scalable Information Inequalities for Uncertainty Quantification(1605.04184)

May 13, 2016 cs.IT, math.IT, math.PR
In this paper we demonstrate the only available scalable information bounds for quantities of interest of high dimensional probabilistic models. Scalability of inequalities allows us to (a) obtain uncertainty quantification bounds for quantities of interest in the large degree of freedom limit and/or at long time regimes; (b) assess the impact of large model perturbations as in nonlinear response regimes in statistical mechanics; (c) address model-form uncertainty, i.e. compare different extended models and corresponding quantities of interest. We demonstrate some of these properties by deriving robust uncertainty quantification bounds for phase diagrams in statistical mechanics models.
• ### Efficient estimators for likelihood ratio sensitivity indices of complex stochastic dynamics(1510.05439)

Feb. 23, 2016 math.NA, math.ST, stat.TH
We demonstrate that centered likelihood ratio estimators for the sensitivity indices of complex stochastic dynamics are highly efficient with low, constant in time variance and consequently they are suitable for sensitivity analysis in long-time and steady-state regimes. These estimators rely on a new covariance formulation of the likelihood ratio that includes as a submatrix a Fisher Information Matrix for stochastic dynamics and can also be used for fast screening of insensitive parameters and parameter combinations. The proposed methods are applicable to broad classes of stochastic dynamics such as chemical reaction networks, Langevin-type equations and stochastic models in finance, including systems with a high dimensional parameter space and/or disparate decorrelation times between different observables. Furthermore, they are simple to implement as a standard observable in any existing simulation algorithms without additional modifications.
• ### Simple Characterizations of Potential Games and Zero-sum Games(1602.04410)

Feb. 24, 2020 cs.GT
We provide several tests to determine whether a game is a potential game or whether it is a zero-sum equivalent game---a game which is strategically equivalent to a zero-sum game in the same way that a potential game is strategically equivalent to a common interest game. We present a unified framework applicable for both potential and zero-sum equivalent games by deriving a simple but useful characterization of these games. This allows us to re-derive known criteria for potential games, as well as obtain several new criteria. In particular, we prove (1) new integral tests for potential games and for zero-sum equivalent games, (2) a new derivative test for zero-sum equivalent games, and (3) a new representation characterization for zero-sum equivalent games.
• ### Irreversible Langevin samplers and variance reduction: a large deviation approach(1404.0105)

April 22, 2015 math-ph, math.MP, math.PR
In order to sample from a given target distribution (often of Gibbs type), the Monte Carlo Markov chain method consists in constructing an ergodic Markov process whose invariant measure is the target distribution. By sampling the Markov process one can then compute, approximately, expectations of observables with respect to the target distribution. Often the Markov processes used in practice are time-reversible (i.e., they satisfy detailed balance), but our main goal here is to assess and quantify how the addition of a non-reversible part to the process can be used to improve the sampling properties. We focus on the diffusion setting (overdamped Langevin equations) where the drift consists of a gradient vector field as well as another drift which breaks the reversibility of the process but is chosen to preserve the Gibbs measure. In this paper we use the large deviation rate function for the empirical measure as a tool to analyze the speed of convergence to the invariant measure. We show that the addition of an irreversible drift leads to a larger rate function and it strictly improves the speed of convergence of ergodic average for (generic smooth) observables. We also deduce from this result that the asymptotic variance decreases under the addition of the irreversible drift and we give an explicit characterization of the observables whose variance is not reduced reduced, in terms of a nonlinear Poisson equation. Our theoretical results are illustrated and supplemented by numerical simulations.
• ### Variance reduction for irreversible Langevin samplers and diffusion on graphs(1410.0255)

Feb. 18, 2015 math.PR, math.ST, stat.TH
In recent papers it has been demonstrated that sampling a Gibbs distribution from an appropriate time-irreversible Langevin process is, from several points of view, advantageous when compared to sampling from a time-reversible one. Adding an appropriate irreversible drift to the overdamped Langevin equation results in a larger large deviations rate function for the empirical measure of the process, a smaller variance for the long time average of observables of the process, as well as a larger spectral gap. In this work, we concentrate on irreversible Langevin samplers with a drift of increasing intensity. The asymptotic variance is monotonically decreasing with respect to the growth of the drift and we characterize its limiting behavior. For a Gibbs measure whose potential has one or more critical points, adding a large irreversible drift results in a decomposition of the process in a slow and fast component with fast motion along the level sets of the potential and slow motion in the orthogonal direction. This result helps understanding the variance reduction, which can be explained at the process level by the induced fast motion of the process along the level sets of the potential. The limit of the asymptotic variance as the magnitude of the irreversible perturbation grows is the asymptotic variance associated to the limiting slow motion. The latter is a diffusion process on a graph.
• ### Measuring the Irreversibility of Numerical Schemes for Reversible Stochastic Differential Equations(1207.5665)

April 15, 2013 math.NA, math.PR
For a Markov process the detailed balance condition is equivalent to the time-reversibility of the process. For stochastic differential equations (SDE's) time discretization numerical schemes usually destroy the property of time-reversibility. Despite an extensive literature on the numerical analysis for SDE's, their stability properties, strong and/or weak error estimates, large deviations and infinite-time estimates, no quantitative results are known on the lack of reversibility of the discrete-time approximation process. In this paper we provide such quantitative estimates by using the concept of entropy production rate, inspired by ideas from non-equilibrium statistical mechanics. The entropy production rate for a stochastic process is defined as the relative entropy (per unit time) of the path measure of the process with respect to the path measure of the time-reversed process. By construction the entropy production rate is nonnegative and it vanishes if and only if the process is reversible. Crucially, from a numerical point of view, the entropy production rate is an {\em a posteriori} quantity, hence it can be computed in the course of a simulation as the ergodic average of a certain functional of the process (the so-called Gallavotti-Cohen (GC) action functional). We compute the entropy production for various numerical schemes such as explicit Euler-Maruyama and explicit Milstein's for reversible SDEs with additive or multiplicative noise. Additionally, we analyze the entropy production for the BBK integrator of the Langevin processes. We show that entropy production is an observable that distinguishes between different numerical schemes in terms of their discretization-induced irreversibility. Furthermore, our results show that the type of the noise critically affects the behavior of the entropy production rate.
• ### Decompositions of two player games: potential, zero-sum, and stable games(1106.3552)

July 18, 2011 math-ph, math.MP, q-bio.PE, cs.GT, math.OC, cs.SY
We introduce several methods of decomposition for two player normal form games. Viewing the set of all games as a vector space, we exhibit explicit orthonormal bases for the subspaces of potential games, zero-sum games, and their orthogonal complements which we call anti-potential games and anti-zero-sum games, respectively. Perhaps surprisingly, every anti-potential game comes either from the Rock-Paper-Scissors type games (in the case of symmetric games) or from the Matching Pennies type games (in the case of asymmetric games). Using these decompositions, we prove old (and some new) cycle criteria for potential and zero-sum games (as orthogonality relations between subspaces). We illustrate the usefulness of our decomposition by (a) analyzing the generalized Rock-Paper-Scissors game, (b) completely characterizing the set of all null-stable games, (c) providing a large class of strict stable games, (d) relating the game decomposition to the decomposition of vector fields for the replicator equations, (e) constructing Lyapunov functions for some replicator dynamics, and (f) constructing Zeeman games -games with an interior asymptotically stable Nash equilibrium and a pure strategy ESS.
• ### Absolute continuity of Brownian bridges under certain gauge transformations(1103.4822)

March 24, 2011 math.AP, math.CA, math.PR
We prove absolute continuity of Gaussian measures associated to complex Brownian bridges under certain gauge transformations. As an application we prove that the invariant measure for the periodic derivative nonlinear Schr\"odinger equation obtained by Nahmod, Oh, Rey-Bellet and Staffilani in [20], and with respect to which they proved almost surely global well-posedness, coincides with the weighted Wiener measure constructed by Thomann and Tzvetkov [24]. Thus, in particular we prove the invariance of the measure constructed in [24].
• ### Entropic Fluctuations in Statistical Mechanics I. Classical Dynamical Systems(1009.3248)

Within the abstract framework of dynamical system theory we describe a general approach to the Transient (or Evans-Searles) and Steady State (or Gallavotti-Cohen) Fluctuation Theorems of non-equilibrium statistical mechanics. Our main objective is to display the minimal, model independent mathematical structure at work behind fluctuation theorems. Besides its conceptual simplicity, another advantage of our approach is its natural extension to quantum statistical mechanics which will be presented in a companion paper. We shall discuss several examples including thermostated systems, open Hamiltonian systems, chaotic homeomorphisms of compact metric spaces and Anosov diffeomorphisms.
• ### Ruelle-Lanford functions for quantum spin systems(1009.4491)

We prove a large deviation principle for the expectation of macroscopic observables in quantum (and classical) Gibbs states. Our proof is based on Ruelle-Lanford functions and direct subadditivity arguments, as in the classical case, instead of relying on G\"artner-Ellis theorem, and cluster expansion or transfer operators as done in the quantum case. In this approach we recover, expand, and unify quantum (and classical) large deviation results for lattice Gibbs states. In the companion paper \cite{OR} we discuss the characterization of rate functions in terms of relative entropies.
• ### Invariant weighted Wiener measures and almost sure global well-posedness for the periodic derivative NLS(1007.1502)

July 9, 2010 math.AP, math.PR
In this paper we construct an invariant weighted Wiener measure associated to the periodic derivative nonlinear Schr\"odinger equation in one dimension and establish global well-posedness for data living in its support. In particular almost surely for data in a Fourier-Lebesgue space ${\mathcal F}L^{s,r}(\T)$ with $s \ge \frac{1}{2}$, $2 < r < 4$, $(s-1)r <-1$ and scaling like $H^{\frac{1}{2}-\epsilon}(\T),$ for small $\epsilon >0$. We also show the invariance of this measure.
• ### Deterministic Equations for Stochastic Spatial Evolutionary Games(1007.0723)

July 5, 2010 nlin.PS, math.PR, q-bio.PE
Spatial evolutionary games model individuals who are distributed in a spatial domain and update their strategies upon playing a normal form game with their neighbors. We derive integro-differential equations as deterministic approximations of the microscopic updating stochastic processes. This generalizes the known mean-field ordinary differential equations and provide a powerful tool to investigate the spatial effects in populations evolution. The deterministic equations allow to identify many interesting features of the evolution of strategy profiles in a population, such as standing and traveling waves, and pattern formation, especially in replicator-type evolutions.
• ### Coarse-graining schemes and a posteriori error estimates for stochastic lattice systems(math/0608007)

Aug. 1, 2006 math.NA
The primary objective of this work is to develop coarse-graining schemes for stochastic many-body microscopic models and quantify their effectiveness in terms of a priori and a posteriori error analysis. In this paper we focus on stochastic lattice systems of interacting particles at equilibrium. %such as Ising-type models. The proposed algorithms are derived from an initial coarse-grained approximation that is directly computable by Monte Carlo simulations, and the corresponding numerical error is calculated using the specific relative entropy between the exact and approximate coarse-grained equilibrium measures. Subsequently we carry out a cluster expansion around this first-and often inadequate-approximation and obtain more accurate coarse-graining schemes. The cluster expansions yield also sharp a posteriori error estimates for the coarse-grained approximations that can be used for the construction of adaptive coarse-graining methods. We present a number of numerical examples that demonstrate that the coarse-graining schemes developed here allow for accurate predictions of critical behavior and hysteresis in systems with intermediate and long-range interactions. We also present examples where they substantially improve predictions of earlier coarse-graining schemes for short-range interactions.
• ### Large deviations in quantum lattice systems: one-phase region(math-ph/0406065)

We give large deviation upper bounds, and discuss lower bounds, for the Gibbs-KMS state of a system of quantum spins or an interacting Fermi gas on the lattice. We cover general interactions and general observables, both in the high temperature regime and in dimension one.
• ### Low regularity solutions to a gently stochastic nonlinear wave equation in nonequilibrium statistical mechanics(math-ph/0312072)

Dec. 29, 2003 math-ph, math.MP, math.PR
We consider a system of stochastic partial differential equations modeling heat conduction in a non-linear medium. We show global existence of solutions for the system in Sobolev spaces of low regularity, including spaces with norm beneath the energy norm. For the special case of thermal equilibrium, we also show the existence of an invariant measure (Gibbs state).
• ### Statistical mechanics of anharmonic lattices(math-ph/0303021)

March 7, 2003 math-ph, math.MP, math.PR
This paper is a review on the statistical mechanics of anharmonic oscillators coupled to heat reservoirs. We discuss stationary states (existence and ergodic properties) and entropy production (positivity, Green-Kubo formulas and the Gallavotti-Cohen fluctuation theorem).This review will appear in the Proceedings of the 2002 UAB International Conference on Differential Equations and Mathematical Physics.
• ### Exponential Convergence to Non-Equilibrium Stationary States in Classical Statistical Mechanics(math-ph/0110024)

Oct. 20, 2001 math-ph, math.MP, math.PR
We continue the study of a model for heat conduction consisting of a chain of non-linear oscillators coupled to two Hamiltonian heat reservoirs at different temperatures. We establish existence of a Liapunov function for the chain dynamics and use it to show exponentially fast convergence of the dynamics to a unique stationary state. Ingredients of the proof are the reduction of the infinite dimensional dynamics to a finite-dimensional stochastic process as well as a bound on the propagation of energy in chains of anharmonic oscillators.