# On large deviation principles and the Monge–Ampère equation (following
Berman, Hultgren)

Yanir A. Rubinstein

(8 June 2022)

###### Abstract

This is mostly an exposition, aimed to be accessible to geometers, analysts,
and probabilists, of a fundamental recent theorem of R. Berman with recent
developments by J. Hultgren, that asserts that the second boundary value
problem for the real Monge–Ampère equation admits a probabilistic
interpretation, in terms of many particle limit of permanental point processes
satisfying a large deviation principle with a rate function given explicitly
using optimal transport. An alternative proof of a step in the Berman–Hultgren
Theorem is presented allowing to to deal with all “tempratures” simultaneously
instead of first reducing to the zero-temperature case.

Dedicated to Steve Zelditch on the occasion of his
6${\hbox{8}}^{\,{\hbox{\itnotsosml th}}}$ birthday

##  1 Introduction

The purpose of this exposition is to present one particularly beautiful
connection between the Monge–Ampère equation and probability, specifically, a
large deviation principle, discovered by Berman. Since the original work by
Berman is still unpublished [5], and moreover deals with the more technically
involved case where the gradient image is a polytope (that arises from toric
varieties), it seemed more pedagogical to give an exposition that concentrates
on subsequent work of Hultgren [18] that elaborates Berman’s ideas in the case
the gradient image has no boundary (that arises from Abelian varieties) as
many of the key ideas are present already in the latter setting.

It is worth pointing out that while the lack of boundary is a simplification,
Hultgren beautifully deals with a different set of technicalities that arises
in the Abelian setting that is absent from Berman’s toric setting: theta
function analysis.

We completely skip the connection to Abelian varieties in this exposition as
our goal was to present strictly the Monge–Ampère to LDP connection, stripping
away the underlying geometry. Our exposition culminates in Theorem 8.8, due to
Hultgren.

We take the opportunity to present an alternative proof to Theorem 8.8 that
deals with all “tempratures” simultaneously instead of first reducing to the
zero-temperature case as in the work of Berman and Hultgren (cf. [17, Remark
24, p. 59]). Basically this amounts to replacing an application of the
Gärtner–Ellis theorem with a direct computation (we still use Gärtner–Ellis
theorem in several other places). The proof we present culminates in §8.1 and
is self-contained in the sense that we present essentially all the basic
prerequisites from large deviations theory and optimal transport.

The family of Monge–Ampère equations Berman originally considers actually
corresponds to and is inspired by the Ricci continuity method introduced by
the author in 2008 [29] in connection with the Ricci flow and the search for
Kähler–Einstein metrics. The idea there, explained in detail in the survey
[30, §6], is to extend Aubin’s continuity method originally defined for
parameter values $t\in[0,1]$ all the way ‘back’ in time to $t\in(-\infty,1]$.
This is motivated by the Ricci flow [29, §3],[30, §6] and is exploited heavily
in subsequent work on existence of singular Kähler–Einstein metrics where the
standard continuity method of Aubin cannot be readily used, but where the
asymptotic analysis of the limit $t\rightarrow-\infty$ allows to bypass the
difficulty in getting the continuity method ‘started’ [19, §9]. Berman [5]
discovered a physics interpretation for this analytical gadget where the
temperature corresponds precisely to $-1/t$, and so the limit
$t\rightarrow-\infty$ becomes for him a ‘zero-temperature limit’. Making this
connection to physics proved extremely fruitful as it led Berman to several
observations, including the LDP result we describe in this survey.

Goal of present work. The purpose of these lectures is to give a detailed
exposition of some of Berman’s ideas [5] in the setting of Hultgren’s work
[18] hopefully with some simplification (in particular the alternative proof
mentioned above). We give some additional background in probability, hopefully
to allow the dissemination of this beautiful piece of mathematics to a wider
audience, given that the necessary background from probability might not be
standard for most students in geometric analysis. We learned the little
probability that we were able to present here from reading Berman and Hultgren
[5, 18] as well as using the classic reference of Dembo–Zeitouni [9] and the
more recent textbook of Rassoul-Agha–Seppäläinen [26] where thorough, and
probably more accurate, presentations of the results in §3–§6 can be found.
For the results on optimal transport our main reference is Ambrosio–Gigli [2].

Organization. We start by giving some anecdotes from the history of relations
between Monge–Ampère equations and probability in §2. This by no means is even
an attempt at an exhaustive historical account. Rather, it is for the sake of
placing the idea of Berman in a broader historical context. Section 3 serves
as a gentle crash (oxymoron alert) course on large deviation principles (LDP).
Section 4 discusses moment generating functions and the associated LDP with
rate function coming from the Legendre transform of the function: this is the
Gärtner–Ellis Theorem. Section 5 completes the proof of the Gärtner–Ellis
Theorem. Section 6 discusses a general criterion for the existence of an LDP
without using a moment generating function. Section 7 briefly reviews the
fundamentals of optimal transportation, and computes, following Berman [5],
the Legendre transform of Wasserstein distance as well as identifies the
candidate rate function for a family of Monge–Ampère equations (34) related to
the Ricci continuity method [29, 30]. Section 8 presents the proof of
Berman–Hultgren’s Theorem 8.8, showing an LDP for a sequence of empirical
measures arising from theta functions on Abelian varieties (although we do not
go into any of the underlying complex geometry, which is beautifully presented
in Hultgren’s work and in fact is one of the novelties of his work [18]). The
rate function is related to optimal transport, and the whole construction is
intimately related to solutions of the “master equation” (34). Most of Section
8 is devoted to our approach described above to the proof of Theorem 8.8,
culminating in §8.1, and in §8.2 we present the original proof of Berman and
Hultgren, and briefly compare the two approaches.

##  2 Monge–Ampère and probability

The Laplace and Poisson equations have myriad probabilistic connections and
interpretations, e.g., through Brownian motion, eigenfunctions, nodal sets [7,
20, 36]. Being the higher-dimensional analogue of these equations, one would
expect similar, albeit more complicated, relations between the (homogeneous or
non-homogeneous) Monge–Ampère equation and probability.

Perhaps Gaveau was the first to pioneer such relations, when he discovered
that the solution to the complex Monge–Ampère equation can be expressed as the
value function of a stochastic optimal control problem and found a semi-group
that can be studied in relation to a parabolic version of the Monge–Ampère
equation [13, 14, 15]. This generalized the classical probabilistic
representation of the solution of the Laplace equation in one complex
dimension. Another fundamental relation was discovered by Krylov who proved
$C^{1,1}$ a priori estimates for the real Monge–Ampère equation, among other
results [22, 21, 23, 24]. We refer to Delarue [8] for excellent lecture notes
that survey, expand, and give a pedagogical point of view on both Gaveau’s and
Krylov’s achievements (and also cover the complex case for the latter).
Another type of relation between Monge–Ampère and probability arises in the
theory of optimal transportation (see, e.g., Villani [32, 33]) where one seeks
a map pushing forward one probability measure into another. Indeed, the
optimal (cost-minimizing) map can be expressed as the gradient of a convex
function and the push-forward equation becomes a real Monge–Ampère equation.

Another classical connection appears through the theory of Markov semigroups,
which in turn are closely related to the heat kernel. In this context
hypercontractivity plays a central role and leads to (logarithmic and regular)
Sobolev inequalities. This goes back to work of Gross [16]. For our anecdotal
storytelling we mention that Bakry and Bakry–Ledoux [3, 4] showed how to use
these ideas to establish Sobolev and diameter estimates in the presence of
positive Ricci curvature. This was then applied in the setting of a degenerate
complex Monge–Ampère equation [19, Proposition 6.2] to by-pass standard
“Riemannian” proofs that do not readily apply in the degenerate setting.

A spectacular relation between Monge–Ampère equations and probability was
discovered by Zelditch who together with collaborators studied several
instances where large deviation principles (LDP) make their appearance in
complex geometry [34, 35, 12]. In particular, Song–Zelditch found a large
deviation principle that underlies the canonical Bergman approximation scheme
[10, 25] for the Cauchy problem for the homogeneous real Monge–Ampère equation
(this equation governs initial value geodesics in the space of Kähler metrics
with toric symmetry) [31].

Berman subsequently discovered that an LDP holds also in the quite distinct
setting of the second boundary value problem for non-homogeneous real
Monge–Ampère equation [5] that appears naturally in the setting of toric
Kähler manifolds as well as optimal transport. Since the gradient image in
this setting is a polytope, there are issues with the corners and the boundary
that render the computations more involved. For that reason, the subsequent
follow-up work of Hultgren is more appropriate for our exposition, as in the
setting of Abelian varieties that he studies the gradient image is a torus,
while the main features of Berman’s work are still present. The sections of
the line bundles over Abelian varieties, theta functions, are more complicated
to represent than the simple toric monomials that appear in the case of toric
varieties, but that is not a steep price to pay for the lack of boundary.
Although outside the scope of these notes, we mention that Berman also
discovered an LDP in a sort of complex version of his aforementioned toric
result in the case $\beta>0$, where the toric variety is replaced by a
polarized complex manifold and the role of the permanental point process is
played by a determinantal point process [6].

##  3 Large deviation principles

We will be interested in asymptotic behavior, or more precisely, the
asymptotic concentration, of a sequence of probability spaces

$({\mathcal{X}},{\mathcal{A}},\mu_{n}),$

indexed by $n\in\mathbb{N}$. Here, $({\mathcal{X}},{\mathcal{A}})$ is a
measure space, i.e., ${\mathcal{X}}$ is a set, also called the sample space,
consisting of all possible outcomes, and ${\mathcal{A}}$ is a $\sigma$-algebra
(the collection of measurable sets in ${\mathcal{X}}$), and $\\{\mu_{n}\\}$
are probability measures on $({\mathcal{X}},{\mathcal{A}})$, i.e., functions
$\mu_{n}:{\mathcal{A}}\rightarrow[0,\infty]$ satisfying $\mu_{n}(\emptyset)=0$
and $\mu_{n}(\cup_{i}A_{i})=\sum_{i}\mu_{n}(A_{i})$ whenever $A_{k}\cap
A_{l}=\emptyset$ for all $k,l$, and with total mass
$\mu_{n}({\mathcal{X}})=1$. The last property is what makes a general measure
a probability measure. Often, it is customary to omit ${\mathcal{A}}$ from the
notation and refer to the triple $({\mathcal{X}},{\mathcal{A}},\mu_{n})$
simply by the notation $\mu_{n}\in P({\mathcal{X}})$, where $P({\mathcal{X}})$
denotes the space of probability measures on $({\mathcal{X}},{\mathcal{A}})$.

######  Definition 3.1.

We say that $\\{({\mathcal{X}},{\mathcal{A}},\mu_{n})\\}_{n}$ (or, for
brevity, sometimes just $\\{\mu_{n}\\}_{n})$ satisfies a large deviation
principle with normalization $r_{n}\nearrow\infty$ (and denote this statement
by LDP$(\mu_{n},r_{n})$) if there exists a lower semicontinuous function
$I:{\mathcal{X}}\rightarrow[0,\infty]$ such that

$\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(O)\geq-\inf_{O}I,\qquad\forall\;O\hbox{\
\ open in \ }{\mathcal{X}},$

and

$\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(C)\leq-\inf_{C}I,\qquad\forall\;C\hbox{\
\ closed in \ }{\mathcal{X}}.$

Under mild assumptions on ${\mathcal{X}}$, there is actually no ambiguity in
the rate function $I$ [26, Theorem 2.13]. Here is where the stipulation that
the rate function be lower semicontinuous is relevant.

######  Lemma 3.2.

Suppose ${\mathcal{X}}$ is a regular topological space. Then,

$I(x)=\sup\Big{\\{}-\liminf\frac{1}{r_{n}}\log\mu_{n}(O):O\ni x,O\hbox{\ \ is
an open set in }{\mathcal{X}}\Big{\\}}.$

######  Remark 3.3.

For a sort of converse see Proposition 6.1.

######  Remark 3.4.

The definition of a regular topological space will be given in the proof
shortly.

###### Proof.

Define $I$ by the above formula. Suppose that LDP$(\mu_{n},r_{n})$ holds with
rate function $F$. By Definition 3.1, whenever $O\hbox{\ \ is an open set in
}{\mathcal{X}}$ with $O\ni x$,

$F(x)\geq\inf_{O}F\geq-\liminf\frac{1}{r_{n}}\log\mu_{n}(O).$

Taking the supremum over all such $O$ does not change the left hand side,
while the right hand side becomes $I(x)$. Thus, $F\geq I$.

Conversely, fix $x$ and let $c$ be such that $c<F(x)$. It suffices to show
that $c\leq I(x)$. Indeed, the assumption on ${\mathcal{X}}$ means that any
point can be separated from any closed set not containing it by means of
disjoint open sets. Thus, we can separate $x$ from the closed set $\\{F\leq
c\\}\not\ni x$, i.e., choose open $G\ni x$ with $\overline{G}\cap\\{F\leq
c\\}=\emptyset$, i.e., $\overline{G}\subset\\{F>c\\}$. Now, since $F$ is lower
semicontinuous its inf over any closed set is attained. In particular,
$\inf_{\overline{G}}F\geq c$. (Note that we could not otherwise conclude
$c\leq\inf_{\\{F>c\\}}F$!) Thus,

$c\leq\inf_{\overline{G}}F\leq-\limsup\frac{1}{r_{n}}\log\mu_{n}(\overline{G})\leq-\liminf\frac{1}{r_{n}}\log\mu_{n}({G})\leq
I(x),$

so $F(x)\leq I(x)$, concluding the proof. ∎

The fact that the function $I$ is nonnegative is crucial: it means probability
of events (an event is an element of ${\mathcal{A}}$) is exponentially
decaying in general, with rate

‘$r_{n}\times$ infimum of $I$ over the closure of the event’.

Of particular interest are therefore the zeros of the rate function, i.e., the
events $I^{-1}(0)$ (when this set is non-empty; it is always non-empty if the
rate function is good [9, p. 4], i.e., $I$ has compact sub-level sets in
${\mathcal{X}}$). The significance of zeros is nicely captured in terms of
random variables, which we now turn to discuss.

######  Remark 3.5.

Note that by setting $O=C={\mathcal{X}}$ it follows that $\inf I=0$.

$\star$ $\star$ $\star$

Probability measures and random variables can often be interchanged in the
discussion, and by abuse of terminology this will sometimes be the case. Let
us briefly discuss the terminology involved. Let
$({\mathcal{X}},{\mathcal{A}},\mu)$ be a probability space and let
$({\mathcal{Y}},{\mathcal{B}})$ be a measure space (a typical example is
$\mathbb{R}$ with ${\mathcal{B}}$ being the usual Borel sets). A random
variable  with values in ${\mathcal{Y}}$ is a measurable function
$X:{\mathcal{X}}\rightarrow{\mathcal{Y}}$ (here, measurable takes into account
both ${\mathcal{A}}$ and ${\mathcal{B}}$). To such an $X$ one may associate a
probability space $({\mathcal{Y}},{\mathcal{B}},\nu)$ defined by

$\nu(B):=\mu(\\{x\in{\mathcal{X}}\,:\,X(x)\in B\\}),\hbox{\ \ for
$B\in{\mathcal{B}}$}$

(the previous formula is often written, with some abuse, as
$\nu(B):=\mu\\{X\in B\\}$). In other words, $\nu(B):=\mu(X^{-1}(B))$, or,

$\nu=X_{\\#}\mu.$

One also refers to $\nu$ as the law  of $X$. Note that often when discussing
the random variable $X$ the “background space”
$({\mathcal{X}},{\mathcal{A}},\mu)$ is completely auxiliary/irrelevant since
one is completely focused on $({\mathcal{Y}},{\mathcal{B}},\nu)$. Thus, often
one does not distinguish between $X$ and the resulting or pushed-forward
measure $\nu$.

$\star$ $\star$ $\star$

When the sequence of probability spaces

$({\mathcal{X}},{\mathcal{A}},\mu_{n})$

happen to correspond to the laws of a sequence of random variables $X_{n}$ (on
some auxiliary probability space
$(\widetilde{\mathcal{X}},\widetilde{\mathcal{A}},\widetilde{\mu})$) with
values in ${\mathcal{X}}$, the zeros of the rate function have the following
meaning. We say that $x\in\hbox{${\mathcal{X}}$ }$ is a limiting value of
$\\{X_{n}\\}$ with probability $c$ if

$\lim_{n}\widetilde{\mu}(\\{|X_{n}-x|<\epsilon\\})=\lim_{n}\mu_{n}(B_{\epsilon}(x))=c,$

for all $\epsilon>0$ small.

######  Lemma 3.6.

Consider a sequence of random variables $X_{n}$ whose laws $\mu_{n}$ satisfy
LDP$(\mu_{n},r_{n})$. Suppose that $x\in\hbox{${\mathcal{X}}$ }$ is a limiting
value of $\\{X_{n}\\}$ with probability $c>0$ (independent of $n$). Then $x\in
I^{-1}(0)$. In fact, $x\in I^{-1}(0)$ whenever
$\frac{1}{r_{n}}\log\mu_{n}(\\{|X_{n}-x|<\epsilon\\})\rightarrow 0$.

In other words, $x\in I^{-1}(0)$ whenever $x\in\hbox{${\mathcal{X}}$ }$ is a
“limiting value of $X_{n}$ with probability decaying slower than $e^{-Cr_{n}}$
(for some $C>0$).”

###### Proof.

One has

$\inf_{\overline{B_{\epsilon}(x)}}I\leq-\limsup\frac{1}{r_{n}}\log\mu_{n}(X_{n}\in\overline{B_{\epsilon}(x)})=-\limsup\frac{1}{r_{n}}\log\widetilde{\mu}_{n}(X_{n}^{-1}(\overline{B_{\epsilon}(x)}))=0.$

Letting $\epsilon\rightarrow 0$ and using $I\geq 0$ and lower semicontinuity
guarantees $I(x)=0$ since $I\geq 0$. ∎

One particular situation of practical interest is when $I^{-1}(0)$ is a
singleton. In that case a sort of converse of the previous statement holds.

######  Corollary 3.7.

Suppose that the sequence of probability spaces
$({\mathcal{X}},{\mathcal{A}},\mu_{n})$ satisfies LDP$(\mu_{n},r_{n})$ with a
good rate function $I$ (i.e., $I$ has compact sub-level sets in
${\mathcal{X}}$) and that $I^{-1}(0)=\\{x\\}\subset\hbox{${\mathcal{X}}$}$.
Then $\mu_{n}\rightarrow\delta_{x}$ weakly.

###### Proof.

First, note that:

######  Claim 3.8.

For all closed $C\subset{\mathcal{X}}$,

$\limsup\mu_{n}(C)\leq\delta_{x}(C).$

###### Proof.

Indeed, this is trivial when $x\in C$ since then the right-hand side equals 1.
Otherwise,

$\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(C)\leq-\inf_{C}I=:-\epsilon<0,$

since $I$ is good and so the infimum is attained, and by assumption it cannot
be zero as $x$ is the only zero of the nonnegative function $I$. Thus, for $n$
large

$\frac{1}{r_{n}}\log\mu_{n}(C)\leq-\inf_{C}I=-\epsilon,$

so $\mu_{n}(C)<e^{-r_{n}\epsilon}$ and recalling that $r_{n}\nearrow\infty$
(Definition 3.1), $\limsup\mu_{n}(C)=0=\delta_{x}(C)$ as desired. ∎

The proof now follows from the so-called portmanteau theorem, but we give the
quick proof for completeness. Note that Claim 3.8 implies

$\liminf\mu_{n}(O)\geq\delta_{x}(O),$

for all open $O\subset{\mathcal{X}}$ (by looking at $C=\hbox{${\mathcal{X}}$
}\setminus O$). To show the convergence is equivalent to showing

$\lim\int_{{\mathcal{X}}}f\mu_{n}=\int_{{\mathcal{X}}}f\delta_{x},$

for all bounded continuous functions $f$. Indeed, if $a\leq f\leq b$,

$\displaystyle\liminf\int_{{\mathcal{X}}}f\mu_{n}$
$\displaystyle=\liminf\int_{a}^{b}\mu_{n}\\{f>t\\}dt$
$\displaystyle\geq\int_{a}^{b}\liminf\mu_{n}\\{f>t\\}dt$
$\displaystyle\geq\int_{a}^{b}\delta_{x}\\{f>t\\}dt$
$\displaystyle=\int_{{\mathcal{X}}}f\delta_{x}.$

Repeating the above computation for $-f$ gives
$\limsup\int_{{\mathcal{X}}}f\mu_{n}\leq\int_{{\mathcal{X}}}f\delta_{x}$, so
Corollary 3.7 follows. ∎

##  4 Moment generating functions

The logarithm of the moment generating function of the sequence of probability
spaces $({\mathcal{X}},{\mathcal{A}},\mu_{n})$ with normalization
$\\{r_{n}\\}$ is defined by

$p(\theta):=\lim\frac{1}{r_{n}}\log\int_{{\mathcal{X}}}e^{r_{n}\langle\theta,x\rangle}\mu_{n}(x),$

assuming the limit exists and is finite, for each
$\theta\in\hbox{${\mathcal{X}}^{*}$}$. (For example, if $\hbox{${\mathcal{X}}$
}=\mathbb{R}^{n}$ then $\hbox{${\mathcal{X}}^{*}$ }=\mathbb{R}^{n}$, and if
$\hbox{${\mathcal{X}}$ }=P(\mathbb{R}^{d})$ then $\hbox{${\mathcal{X}}^{*}$
}=C^{0}(\mathbb{R}^{d})$.)

A generating function encodes a lot of information, as discovered by Gärtner,
and rediscovered by Ellis. The following theorem holds for rather general
${\mathcal{X}}$ but we will prove it for $\hbox{${\mathcal{X}}$
}=\mathbb{R}^{n}$ although the proof essentially works verbatim for any
locally convex topological vector space ${\mathcal{X}}$ under the assumption
of exponential tightness of the sequence of measures (defined in §5.2). Being
a novice in the field, the author will follow Berman and Zelditch and refer to
the next theorem as the Gärtner–Ellis Theorem, although a more accurate
attribution of credit is given in the historical notes in Dembo–Zeitouni to
which the reader is warmly referred to for much more accurate statements of
all the results on LDPs that we discuss in these notes [9, §2.3].

In general, exponential tightness is a necessary assumption (which is
automatic for ${\mathcal{X}}=\hbox{$\mathbb{R}^{n}$}$ (see Lemma 5.5) and
${\mathcal{X}}=P(X)$ for $X$ a compact manifold). In the following we denote
by $f^{\star}$ the Legendre dual of $f$ [28, p. 104],

$f^{\star}(y):=\sup_{x}[\langle x,y\rangle-f(x)].$ (1)

(We will later use this same definition more generally for functions on
abstract spaces where the pairing will be taken to be the natural one in each
setting.)

######  Theorem 4.1.

Suppose that the moment generating function $p$ of the sequence of probability
spaces $({\mathcal{X}},{\mathcal{A}},\mu_{n})$ with normalization
$\\{r_{n}\\}$ is well defined and Gateaux differentiable. Then
LDP$(\mu_{n},r_{n})$ with rate function $p^{\star}$.

Before proving the Gärtner–Ellis Theorem let us prove two famous corollaries
thereof.

###  4.1 Cramér’s Theorem

Let $\\{X_{i}\\}_{i=1}^{n}$ be independent, identically distributed, random
variables (i.i.d.r.v.) on $\widetilde{\mathcal{X}}$ with values in
$\mathbb{R}$. This means that the law of $X_{i}$ is equal to some $\mu\in
P(\mathbb{R})$ regardless of $i$. The sample mean  is by definition the random
variable with values in $\mathbb{R}$,

$S_{n}:=\sum X_{i}/n.$

This is the “probability” notation. Recalling that a random variable is really
a function leads to a more precise notation. The random variable $S_{n}$ is
the measurable function
$S_{n}:\widetilde{\mathcal{X}}^{n}\rightarrow\mathbb{R}$

$(x_{1},\ldots,x_{n})\mapsto[X_{1}(x_{1})+\ldots X_{n}(x_{n})]/n.$

This is really the composition

$(x_{1},\ldots,x_{n})\mapsto(X_{1}(x_{1}),\ldots,X_{n}(x_{n}))\mapsto[X_{1}(x_{1})+\ldots
X_{n}(x_{n})]/n,$

and so the law of $S_{n}$ is the push forward of the law of the
$\mathbb{R}^{n}$-valued random variable

$X_{1}\otimes\cdots\otimes X_{n}:=(X_{1},\ldots,X_{n})$

under the “mean map”

$s_{n}:(k_{1},\ldots,k_{n})\mapsto\sum k_{i}/n.$

The law of $X_{1}\otimes\cdots\otimes X_{n}$ is $\mu\otimes\cdots\otimes\mu$.
Thus, the law of $S_{n}$ is $\mu_{n}:=(s_{n})_{\\#}\mu^{\otimes n}$.

######  Corollary 4.2.

Suppose that $\mu=fdx$ with $f\in C^{0}(\mathbb{R})$ and with compact support.
LDP$(\mu_{n},n)$ with rate function $p^{\star}*$.

###### Proof.

Set $\theta:=(\theta_{1},\ldots,\theta_{n})\in\hbox{$\mathbb{R}^{n}$}$. The
moment generating function is

$\displaystyle p(\theta)$
$\displaystyle=\lim\frac{1}{n}\log\int_{\mathbb{R}}e^{nx\theta}\mu_{n}(x)$ (2)
$\displaystyle=\lim\frac{1}{n}\log\int_{\mathbb{R}^{n}}e^{n\langle
s_{n}(a_{1},\ldots,a_{n})\theta}\mu^{\otimes n}(a_{1},\ldots,a_{n})$
$\displaystyle=\lim\frac{1}{n}\log\int_{\mathbb{R}}e^{a_{1}\theta}\mu(a_{1})\cdots\int_{\mathbb{R}}e^{a_{n}\theta}\mu(a_{n})$
$\displaystyle=\lim\frac{1}{n}\log\Big{(}\int_{\mathbb{R}}e^{a\theta}\mu(a)^{n}\Big{)}^{n}$
$\displaystyle=\log\int_{\mathbb{R}}e^{a\theta}\mu(a)$

This is $C^{1}$ because of the assumption on $\mu$ so we are done by Theorem
4.1. ∎

###  4.2 Sanov’s theorem

The projection via the mean map gives rather crude information. Set
$X^{n}:=X\otimes\cdots\otimes X$. Another sequence of measures that can be
obtained from the $n$-fold product via the “empirical” map
$\delta^{n}:X^{n}\rightarrow P(X)$,

$\displaystyle\delta^{n}(x_{1},\ldots,x_{n}):=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}.$

The measures

$\displaystyle\Gamma_{n}:=(\delta_{n})_{\\#}\mu^{\otimes n}\in P(X),$ (3)

all live on the same space and therefore can be studied via a large deviation
principle, if the associated moment generating function exists. Note that
$\Gamma_{n}$ is the law of the random variable $\delta^{n}:(X^{n},\mu^{\otimes
n})\rightarrow P(X),$ i.e., of the random measure  $\delta^{n}$ (where the
randomness is determined by $\mu^{\otimes n}$, i.e., by sampling $n$ points in
$X$ independently, each according to $\mu$).

Define the entropy functional $\hbox{\rm Ent}:P(X)\times
P(X)\rightarrow\mathbb{R}$,

$\displaystyle\hbox{\rm Ent}(\mu,\nu):=\int_{X}\log\frac{\nu}{\mu}\nu,$ (4)

whenever $\nu$ is absolutely continuous with respect to $\mu$, and $\infty$
otherwise.

######  Corollary 4.3.

Suppose that $\mu=fdx$ with $f\in C^{0}(X)$ and with compact support.
LDP$(\Gamma_{n},n)$ with rate function $\hbox{\rm Ent}(\mu,\,\cdot\,)$.

###### Proof.

Now ${\mathcal{X}}=P(X)$.  Let $\theta\in C^{0}_{b}(X)={\mathcal{X}}^{*}$. The
moment generating function is

$\displaystyle p(\theta)$
$\displaystyle=\lim\frac{1}{n}\log\int_{P(X)}e^{n\langle\theta,\nu\rangle}\Gamma_{n}(\nu)$
(5)
$\displaystyle=\lim\frac{1}{n}\log\int_{P(X)}e^{n\langle\theta,\nu\rangle}(\delta_{n})_{\\#}\mu^{\otimes
n}$
$\displaystyle=\lim\frac{1}{n}\log\int_{X^{n}}e^{n\langle\theta,\delta^{n}(x_{1},\ldots,x_{n})\rangle}\mu(x_{1})\otimes\cdots\mu(x_{n})$
$\displaystyle=\lim\frac{1}{n}\log\int_{X^{n}}e^{n\langle\theta,\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}\rangle}\mu(x_{1})\otimes\cdots\mu(x_{n})$
$\displaystyle=\lim\frac{1}{n}\log\int_{X^{n}}e^{\sum_{i=1}^{n}\theta(x_{i})}\mu(x_{1})\otimes\cdots\mu(x_{n})$
$\displaystyle=\lim\frac{1}{n}\log\Big{(}\int_{X}e^{\theta}\mu\Big{)}^{n}$
$\displaystyle=\log\int_{X}e^{\theta}\mu.$

This is $C^{1}$ because of the assumption on $\mu$ so we are done by Theorem
4.1 and Lemma 4.4 below. ∎

Define $I:C^{0}(X)\rightarrow\mathbb{R}$,

$\displaystyle I_{\mu}(\theta):=\log\int_{X}e^{\theta}\mu.$ (6)

Recall the definition of the Legendre transform (1), where in the following
lemma the pairing is taken to be the usual “integration pairing”’ between
functions and measures.

######  Lemma 4.4.

The Legendre transform of $\hbox{\rm Ent}(\mu,\,\cdot\,)$ is $I_{\mu}$ and
vice versa.

###### Proof.

First, $I_{\mu}$ is convex on $C(X)$ since it is a moment generating function
(see Lemma 4.5). Alternatively, the arguments in the proof of Lemma 4.5 show
convexity. We will show that Legendre transform of $I_{\mu}$ is $\hbox{\rm
Ent}(\mu,\,\cdot\,)$ which therefore will imply that the latter is also
convex. We claim that

$\displaystyle\hbox{\rm
Ent}(\mu,\nu)+I_{\mu}(\theta)\geq\langle\theta,\nu\rangle.$ (7)

Indeed,

$\displaystyle I_{\mu}(\theta)-\langle\theta,\nu\rangle$
$\displaystyle=\log\int_{X}e^{\theta}\mu-\langle\theta,\nu\rangle$
$\displaystyle=\log\int_{X}e^{\theta}\frac{\mu}{\nu}\nu-\langle\theta,\nu\rangle$
$\displaystyle\geq\int_{X}\log\Big{(}e^{\theta}\frac{\mu}{\nu}\Big{)}\nu-\langle\theta,\nu\rangle$
$\displaystyle=\int_{X}\Big{(}\theta+\log\frac{\mu}{\nu}\Big{)}\nu-\langle\theta,\nu\rangle=-\hbox{\rm
Ent}(\mu,\nu),$

with equality if and only if $\nu=e^{\theta}\mu/\int e^{\theta}\mu$ (so that
$\nu\in P(X)$). Thus, $\hbox{\rm Ent}(\mu,\nu)\geq
I_{\mu}^{\star}(\nu):=\sup_{\theta}[\langle\theta,\nu\rangle-
I_{\mu}(\theta)]$. On the other hand, putting $\theta=\log\frac{\nu}{\mu}$,

$\Big{\langle}\log\frac{\nu}{\mu},\nu\Big{\rangle}-I_{\mu}\Big{(}\log\frac{\nu}{\mu}\Big{)}=\hbox{\rm
Ent}(\mu,\nu)-0,$

so $\hbox{\rm Ent}(\mu,\nu)\leq\sup_{\theta}[\langle\theta,\nu\rangle-
I_{\mu}(\theta)]$. Thus, $\hbox{\rm Ent}(\mu,\nu)=I_{\mu}^{\star}(\nu)$ and so
in particular from the general property of the Legendre transform (1) (see
also [28, p. 104]),

$f(x)+f^{\star}(y)\geq\langle x,y\rangle,$ (8)

it follows that (7) holds, as claimed. Equation (7) gives,

$\sup_{\nu}\big{[}\langle\theta,\nu\rangle-\hbox{\rm Ent}(\mu,\nu)\big{]}\leq
I_{\mu}(\theta),$

and now putting $\nu=e^{\theta}\mu/\int e^{\theta}\mu$ we see equality is
attained, so $I_{\mu}$ is the Legendre transform of $\hbox{\rm
Ent}(\mu,\,\cdot\,)$, concluding the proof. ∎

###  4.3 Properties of the moment generating function

######  Lemma 4.5.

The moment generating function is convex.

###### Proof.

The pointwise limit of a sequence of convex functions is convex (one way to
think about it is in terms of the epigraphs— and clearly the limits of convex
sets is a convex sets, and the limits of epigraphs is moreover an epigraph).
Thus, it suffices to show that

$\frac{1}{r_{n}}\log\int_{\hbox{${\mathcal{X}}$
}}e^{r_{n}\langle\theta,x\rangle}\mu_{n}(x)$

is a convex function. Indeed, since
$||fg||_{L^{1}(\mu)}\leq||f||_{L^{2}(\mu)}||g||_{L^{2}(\mu)}$,

$\displaystyle\frac{1}{r_{n}}\log\int_{\hbox{${\mathcal{X}}$
}}e^{r_{n}\langle(\theta_{1}+\theta_{2})/2,x\rangle}\mu_{n}(x)$
$\displaystyle=\frac{1}{r_{n}}\log\int_{\hbox{${\mathcal{X}}$
}}\sqrt{e^{r_{n}\langle\theta_{1},x\rangle}}\sqrt{e^{r_{n}\langle\theta_{2},x\rangle}}\mu_{n}(x)$
$\displaystyle\leq\frac{1}{r_{n}}\log\Bigg{(}\sqrt{\int_{\hbox{${\mathcal{X}}$
}}e^{r_{n}\langle\theta_{1},x\rangle}\mu_{n}(x)}\sqrt{\int_{\hbox{${\mathcal{X}}$
}}e^{r_{n}\langle\theta_{2},x\rangle}\mu_{n}(x)}\Bigg{)}$
$\displaystyle=\frac{1}{2}\Bigg{(}\frac{1}{r_{n}}\log{\int_{\hbox{${\mathcal{X}}$
}}e^{r_{n}\langle\theta_{1},x\rangle}\mu_{n}(x)}+\frac{1}{r_{n}}\log{\int_{\hbox{${\mathcal{X}}$
}}e^{r_{n}\langle\theta_{2},x\rangle}\mu_{n}(x)}\Bigg{)},$

as desired. ∎

######  Lemma 4.6.

$p^{\star}$ is convex and nonnegative.

###### Proof.

By definition

$p^{\star}(x):=\sup_{\theta}[\langle x,\theta\rangle-p(\theta)]$

is a supremum of affine functions, hence it is convex. Plugging in $\theta=0$
and using that $p(0)=0$ it follows that $p^{\star}(x)\geq 0$. ∎

The reader that compares the statement of Theorem 4.1 to that in some books
might note that one does not really need to assume the moment generating
function is differentiable and certain weaker assumptions are enough. One of
them though is automatic from convexity:

######  Lemma 4.7.

If there exists a small ball $B$ about the origin on which $p<\infty$ then
$p>-\infty$ everywhere.

###### Proof.

This is a general fact about convex functions that can be proved as follows:

$p(0)\leq\frac{1}{1+C}p(-C\theta)+\frac{C}{1+C}p(\theta),$

so

$\frac{C}{1+C}p(\theta)\geq p(0)-\frac{1}{1+C}p(-C\theta).$

Now, choose $C>0$ small enough so that $C\theta\in B$ and note $p(0)=0$. ∎

##  5 Proof of the Gärtner–Ellis Theorem

The goal of this section is to give a proof of Theorem 4.1. The proof of the
upper bound (the one about close sets) is a little easier and so we will go
over it at first. There are two main steps: first, prove the upper bound for
compact sets; second, show that compact sets capture the general case.

###  5.1 The upper bound for compact sets

The upper bound for compact sets is sometimes called the weak upper bound LDP.
Let $C\subset\hbox{${\mathcal{X}}$ }$ then be a compact set. We claim that

$\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(C)\leq-\inf_{C}p^{\star}.$

Fix $\delta>0$. For each $x\in\hbox{${\mathcal{X}}$ }$ let
$y(x)\in\hbox{${\mathcal{X}}^{*}$}$ satisfy $\langle
x,y(x)\rangle-p(y(x))>p^{\star}(x)-\delta$ and let $B_{x}^{\delta,y(x)}$ be a
neighborhood of $x\in\hbox{${\mathcal{X}}$ }$ defined as follows

$B_{x}^{\delta,y(x)}:=\\{z\in\hbox{${\mathcal{X}}$ }\,:\,|\langle
z,y(x)\rangle-\langle x,y(x)\rangle|<\delta\\}.$

Finitely many neighborhoods of affine subspaces
$B_{x_{1}}^{\delta,y_{1}(x_{1})},\ldots,B_{x_{m}}^{\delta,y_{m}(x_{m})}$ cover
$C$ by compactness. Observe that asymptotically we reduce the calculations for
the “left-hand side” to one ball:

$\displaystyle\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(C)$
$\displaystyle\leq\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\sum_{i=1}^{m}\mu_{n}(B_{x_{i}}^{\delta,y_{i}(x_{i})})$
$\displaystyle=\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\big{(}m\sup_{i\in\\{1,\ldots
m\\}}\mu_{n}(B_{x_{i}}^{\delta,y_{i}(x_{i})})\big{)}$
$\displaystyle=\limsup_{n\rightarrow\infty}\bigg{[}\frac{1}{r_{n}}\log
m+\frac{1}{r_{n}}\log\sup_{i\in\\{1,\ldots
m\\}}\mu_{n}(B_{x_{i}}^{\delta,y_{i}(x_{i})})\bigg{]}$
$\displaystyle=\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\sup_{i\in\\{1,\ldots
m\\}}\mu_{n}(B_{x_{i}}^{\delta,y_{i}(x_{i})}).$

Now,

$\displaystyle\mu_{n}(B_{x_{i}}^{\delta,y_{i}(x_{i})})$
$\displaystyle=\int_{B_{x_{i}}^{\delta,y_{i}(x_{i})}}\mu_{n}(z)$
$\displaystyle=\int_{B_{x_{i}}^{\delta,y_{i}(x_{i})}}e^{r_{n}\langle
z,y_{i}(x_{i})\rangle}e^{-r_{n}\langle z,y_{i}(x_{i})\rangle}\mu_{n}$
$\displaystyle\leq e^{\delta-r_{n}\langle
x_{i},y_{i}(x_{i})\rangle}\int_{B_{x_{i}}^{\delta,y_{i}(x_{i})}}e^{r_{n}\langle
z,y_{i}(x_{i})\rangle}\mu_{n}$ $\displaystyle\leq e^{\delta-r_{n}\langle
x_{i},y_{i}(x_{i})\rangle}\int_{{\mathcal{X}}}e^{r_{n}\langle
z,y_{i}(x_{i})\rangle}\mu_{n}$

(integration in the $z$ variable). Taking log and the limit,

$\displaystyle\limsup\frac{1}{r_{n}}\log\mu_{n}(B_{x_{i}}^{\delta,y_{i}(x_{i})})$
$\displaystyle\leq-\langle
x_{i},y_{i}(x_{i})\rangle+\delta+p(y_{i}(x_{i}))\leq-p^{\star}(x_{i})+2\delta\leq-\inf_{C}p^{\star}+2\delta.$

Letting $\delta$ tend to zero completes the argument.

###  5.2 Exponential tightness

######  Definition 5.1.

A sequence of probability measures $\\{\mu_{n}\\}\subset P({\mathcal{X}})$ is
exponentially tight with normalization $r_{n}$ is for each $b\in(0,\infty)$
there exists a compact set $K_{b}\subset\hbox{${\mathcal{X}}$ }$ such that

$\limsup\frac{1}{r_{n}}\log\mu_{n}(\hbox{${\mathcal{X}}$ }\setminus
K_{b})\leq-b.$

######  Remark 5.2.

The point of course is that $K_{b}$ is independent of $n$.

######  Remark 5.3.

Note, of course, that exponential tightness is automatic if ${\mathcal{X}}$ is
compact (or if there is a compact set containing the support of all the
$\mu_{n}$)! In particular, note that ${\mathcal{X}}=P(B)$ (for some compact
(finite-dimensional) manifold $B$) is a compact set by Prokhorov’s theorem
[33, p. 43],[2, Theorem 1.3]: Let ${\mathcal{X}}$ be a Polish space and
$P\subset P({\mathcal{X}})$; then $P$ is pre-compact for the week topology if
and only if for every $\epsilon>0$ there is a compact set
$K_{\epsilon}\subset\hbox{${\mathcal{X}}$ }$ such that
$\mu(\hbox{${\mathcal{X}}$ }\setminus K_{\epsilon})\leq\epsilon$ for all
$\mu\in P$.

######  Lemma 5.4.

Suppose that the large deviation upper bound inequality holds for
$(\mu_{n},r_{n})$ for all compact sets. Suppose also that sequence of
probability measures $\\{\mu_{n}\\}\subset P({\mathcal{X}})$ is exponentially
tight with normalization $r_{n}$. Then the large deviation upper bound
inequality holds.

###### Proof.

Then equality hold for all compact sets by assumption. So consider a close set
$F$ that is not necessarily compact. Of course, $\mu_{n}(F)\leq\mu_{n}(F\cap
K_{b})+\mu_{n}(\hbox{${\mathcal{X}}$ }\setminus K_{b})$. This is a very coarse
inequality (since ${\mathcal{X}}\setminus K_{b}$ is a large set!), but it does
the job since $\mu_{n}(\hbox{${\mathcal{X}}$ }\setminus K_{b})$ is uniformly
small and $F\cap K_{b}$ is compact (so we can apply to large deviation upper
bound to it):

$\displaystyle\limsup\frac{1}{r_{n}}\log\mu_{n}(F)$
$\displaystyle\leq\limsup\frac{1}{r_{n}}\log[\mu_{n}(F\cap
K_{b})+\mu_{n}(\hbox{${\mathcal{X}}$ }\setminus K_{b})]$
$\displaystyle\leq{\operatorname{max}}\\{-b,\limsup\frac{1}{r_{n}}\log\mu_{n}(F\cap
K_{b})\\}$ $\displaystyle\leq{\operatorname{max}}\\{-b,-\inf_{F\cap
K_{b}}I\\}$ $\displaystyle\leq{\operatorname{max}}\\{-b,-\inf_{F}I\\},$

and by choosing $b>\inf_{F}I$ (recall $F$ is closed and $I$ lsc and so the
infimum is attained and $I>-\infty$ by assumption) we get
$\limsup\frac{1}{r_{n}}\log\mu_{n}(F)\leq-\inf_{F}I$. ∎

Thus, to complete the proof of the upper bound it remains to show:

######  Lemma 5.5.

The sequence of probability measures $\\{\mu_{n}\\}\subset P({\mathcal{X}})$
is exponentially tight with normalization $r_{n}$.

###### Proof.

For this proof we assume ${\mathcal{X}}=\mathbb{R}^{n}$ (otherwise, one needs
to incorporate the exponential tightness assumption into the assumptions of
Theorem 4.1). This follows directly from the assumption that a moment
generating function exists. Indeed, choose a coordinate $x_{i}$ and bound the
tail in that direction:

$\displaystyle\mu_{n}\\{x_{i}\geq b\\}$ $\displaystyle=\int_{\\{x_{i}\geq
b\\}}e^{-r_{n}\langle\theta,x\rangle}e^{r_{n}\langle\theta,x\rangle}\mu_{n}(x)$
$\displaystyle\leq e^{-r_{n}b|\theta|}\int_{\\{x_{i}\geq
b\\}}e^{r_{n}\langle\theta,x\rangle}\mu_{n}(x)$ $\displaystyle\leq
e^{-r_{n}b|\theta|}\int_{{\mathcal{X}}}e^{r_{n}\langle\theta,x\rangle}\mu_{n}(x)$
$\displaystyle=e^{-r_{n}b|\theta|}p_{n}(\theta)$

Now,

$\frac{1}{r_{n}}\log p_{n}(\theta)=p(\theta)+o(1),$

so

$p_{n}(\theta)=e^{r_{n}(p(\theta)+o(1))}.$

So, fixing $\theta$ and then choosing $b>0$ sufficiently large ($p(\theta)$ is
finite!), and summing over all coordinate directions concludes the proof. ∎

###  5.3 The lower bound

Our goal is to show that

$\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(O)\geq-\inf_{O}p^{\star},\qquad\forall\;O\hbox{\
\ open in \ }{\mathcal{X}}.$

Fix an open set $O$ and a point $z\in O$ where $\inf_{O}p^{\star}$ is attained
up to some $\epsilon$. First, as in the proof of the upper bound, we will show
that $\frac{1}{r_{n}}\log\mu_{n}(O)$ is essentially equal to
$\frac{1}{r_{n}}\log\mu_{n}(B_{\delta})$ for some ball $B_{\delta}$ containing
$z$. Indeed, for any $B$ and any $\sigma\in{\mathcal{X}}^{*}$,

$\displaystyle\frac{1}{r_{n}}\log\mu_{n}(B)$
$\displaystyle=\frac{1}{r_{n}}\log\int_{B}e^{-r_{n}\langle
z,y_{i}\rangle}e^{r_{n}\langle z,y_{i}\rangle}\mu_{n}(z)$ (9)

We want to do essentially the same computation as for the upper bound, except
that now of course the inequality

$\int_{B}e^{r_{n}\langle
z,y_{i}\rangle}\mu_{n}\leq\int_{{\mathcal{X}}}e^{r_{n}\langle
z,y_{i}\rangle}\mu_{n}$

goes in the wrong direction. To remedy that, we need to identify some way of
localizing the integral so that, at least asymptotically, the integrals are
equal. The key is to notice that the relevant point for localizing is

$\sigma:=(\nabla p)^{-1}(z).$

Consider

$e^{\langle\sigma,\,\cdot\,\rangle}\mu_{n},$

or, rather, the associated probability measures

$\nu_{\sigma,n}:=e^{\langle\sigma,\,\cdot\,\rangle}\mu_{n}\bigg{/}\int_{{\mathcal{X}}}e^{\langle\sigma,y\rangle}\mu_{n}(y).$

######  Lemma 5.6.

The sequence of probability measures $\\{\nu_{\sigma,n}\\}$ localizes around
$z=\nabla p(\sigma)$. More precisely, we have the upper bound large deviation
inequality for $\\{(\nu_{\sigma,n},r_{n})\\}$ with rate function
$p^{\star}-\langle\sigma,\,\cdot\,\rangle+p(\sigma).$

######  Remark 5.7.

Recall that

$\displaystyle p^{\star}(z)=\langle\sigma,z\rangle-p(\sigma),$ (10)

and

$\displaystyle
p^{\star}(\,\cdot\,)+p(\sigma)>\langle\sigma,\,\cdot\,\rangle\qquad\hbox{away
from $z$}.$ (11)

We postpone the proof of Lemma 5.6 to the end of the section.

Thus, the rate function in the statement is nonnegative with a unique zero at
$z$. Thus the desired localization:

######  Corollary 5.8.

For any $\delta>0$,

$\lim_{n}\nu_{\sigma,n}(B_{\delta}^{z})=1.$

###### Proof.

It suffices to show that

$\limsup_{n}\frac{1}{r_{n}}\log\nu_{\sigma,n}({\mathcal{X}}\setminus
B_{\delta}^{z})<0.$

By the large deviation upper bound inequality for
$\\{(\nu_{\sigma,n},r_{n})\\}$ and (11) (note ${\mathcal{X}}\setminus
B_{\delta}^{z}$ is closed!),

$\limsup_{n}\frac{1}{r_{n}}\log\nu_{\sigma,n}({\mathcal{X}}\setminus
B_{\delta}^{z})\leq-\inf_{x\not\in
B_{\delta}^{z}}[p^{\star}(x)-\langle\sigma,x\rangle+p(\sigma)]\leq-C,$

for some $C=C(\delta)$, at desired. ∎

Thus, as we wished,

$\int_{B_{\delta}^{z}}\nu_{\sigma,n}=\int_{{\mathcal{X}}}\nu_{\sigma,n}+o(1)=1+o(1).$

Now we are ready to go back to (9),

$\displaystyle\frac{1}{r_{n}}\log\mu_{n}(B_{\delta}^{z})$
$\displaystyle=\frac{1}{r_{n}}\log\int_{B_{\delta}^{z}}e^{-r_{n}\langle\sigma,x\rangle}e^{r_{n}\langle\sigma,x\rangle}\mu_{n}(z)$
$\displaystyle=\frac{1}{r_{n}}\log\int_{B_{\delta}^{z}}e^{-r_{n}\langle\sigma,x\rangle}p_{n}(\sigma)\nu_{\sigma,n}(x)$
$\displaystyle=p(\sigma)+o(1)+\frac{1}{r_{n}}\log\int_{B_{\delta}^{z}}e^{-r_{n}\langle\sigma,x\rangle}\nu_{\sigma,n}(x)$
$\displaystyle\geq
p(\sigma)+o(1)+\frac{1}{r_{n}}\log\inf_{B_{\delta}^{z}}e^{-r_{n}\langle\sigma,x\rangle}+\frac{1}{r_{n}}\log\int_{B_{\delta}^{z}}\nu_{\sigma,n}(x)$
$\displaystyle\geq p(\sigma)+o(1)-\langle\sigma,z\rangle-\delta+o(1)$
$\displaystyle=-p^{\star}(z)+o(1)-\delta,$

where we used Corollary 5.8 and (10). Letting first $n$ go to infinity and
then $\delta$ go to zero concludes the proof.

###### Proof of Lemma 5.6.

First, observe that the Legendre transform of

$p(\,\cdot\,+\sigma)-p(\sigma)$

is

$\displaystyle p^{\star}-\langle\sigma,\,\cdot\,\rangle+p(\sigma).$ (12)

Thus, it suffices to show that the moment generating function of
$\\{\nu_{\sigma,n}\\}$ is $p(\,\cdot\,+\sigma)-p(\sigma)$. Indeed,

$\displaystyle\lim\frac{1}{r_{n}}\log\int_{{\mathcal{X}}}e^{r_{n}\langle\theta,x\rangle}\nu_{\sigma,n}(x)$
$\displaystyle=\lim\frac{1}{r_{n}}\log\int_{{\mathcal{X}}}e^{r_{n}\langle\theta,x\rangle}e^{\langle\sigma,x\rangle}\mu_{n}(x)\bigg{/}p_{n}(\sigma)$
$\displaystyle=-p(\sigma)\lim\frac{1}{r_{n}}\log\int_{{\mathcal{X}}}e^{r_{n}\langle\theta+\sigma,x\rangle}\mu_{n}(x)$
$\displaystyle=-p(\sigma)+p(\theta+\sigma).$

All the assumptions of Theorem 4.1 are met for this generating function since
they are met for $p$. Under those assumptions we have already established the
upper bound inequality in Theorem 4.1. Therefore, we have the upper bound
large deviation inequality for $\\{(\nu_{\sigma,n},r_{n})\\}$ with rate
function (12). ∎

##  6 LDP without moment generating functions

Sometimes, a large deviation principle holds even when the assumptions of
Theorem 4.1 are not satisfied. For one, a moment generating function may not
exist. Also, the rate function can sometimes be nonconvex (not that Theorem
4.1 guarantees the rate function will be convex, being the Legendre transform
of the moment generating function). The following result nevertheless
characterizes large deviation principles and gives a useful tool to show their
existence. It is sort of a converse for Lemma 3.2.

######  Proposition 6.1.

Let ${\mathcal{X}}$ be a compact metric space. LDP$\,(\mu_{n},r_{n})$ if and
only if

$\displaystyle\lim_{d\rightarrow
0}\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d}(x))=\lim_{d\rightarrow
0}\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d}(x)),\quad\forall
x\in\hbox{${\mathcal{X}}$}.$ (13)

The rate function is then equal to minus (13).

###### Proof.

$\underline{\Longleftarrow}$: Suppose (13) holds, and denote either side by
$-g(x)$. Note that $g$ is indeed a rate function: it is evidently not
negative, and it is lower semicontinuous because the super level sets
$\\{g>a\\}$ are open as if $g(x)>a$, i.e., $-g(x)<-a$, then because the limits
in (13) are decreasing in $d$, then for some $B_{d}(x)$,

$\displaystyle\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d}(x))<-a,$

so for every $y\in B_{d}(x)$ choosing $d^{\prime}$ so that
$B_{d^{\prime}}(y)\subset B_{d}(x)$,

$\displaystyle\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d^{\prime}}(y))\leq\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d}(x))<-a,$

so $-g(y)<-a$.

To prove the lower bound, let $O\in{\mathcal{X}}$ be open, fix $\epsilon>0$,
and let $x\in O$ be such that $g(x)\leq\inf_{O}g+\epsilon$, and let $d>0$ be
such that $B_{d}(x)\subset O$. Then

$\displaystyle\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(O)$
$\displaystyle\geq\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{\delta}(x))$
$\displaystyle\geq\lim_{d\rightarrow
0}\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{\delta}(x))$
$\displaystyle=-g(x)=\geq-\inf_{O}g-\epsilon.$

Now let $\epsilon$ tend to zero.

To prove the upper bound, let $C\in{\mathcal{X}}$ be closed. Because
${\mathcal{X}}$ is compact, so is $C$. Similar to the proof of §5.1 we cover
$F$ with finitely many balls and then

$\displaystyle\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(C)$
$\displaystyle\leq\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\sum_{i=1}^{m}\mu_{n}(B_{d_{i}}(x_{i}))$
$\displaystyle=\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\big{(}m\sup_{i\in\\{1,\ldots
m\\}}\mu_{n}(B_{d_{i}}(x_{i}))\big{)}$
$\displaystyle=\limsup_{n\rightarrow\infty}\bigg{[}\frac{1}{r_{n}}\log
m+\frac{1}{r_{n}}\log\sup_{i\in\\{1,\ldots
m\\}}\mu_{n}(B_{d_{i}}(x_{i}))\bigg{]}$
$\displaystyle=\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\sup_{i\in\\{1,\ldots
m\\}}\mu_{n}(B_{d_{i}}(x_{i}))$
$\displaystyle={\operatorname{max}}_{i\in\\{1,\ldots
m\\}}\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d_{i}}(x_{i}))$
$\displaystyle=\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d_{1}}(x_{1})),$

where the last equality is without loss of generality. Fix $\epsilon>0$. By
(13), for each $x\in\hbox{${\mathcal{X}}$ }$ there exists $d(x,\epsilon)>0$
such that

$\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d(x,\epsilon)}(x))\leq{\operatorname{max}}\\{-g(x)+\epsilon,-1/\epsilon\\}$

(note that if $g$ is finite one can simplify the right-hand side to
$-g(x)+\epsilon$). Now, cover $C$ with the balls $\cup_{x\in
F}B_{d(x,\epsilon)}(x)$; then, by compactness of $C$ we may choose a finite
sub-cover, and thus, we may assume that we have chosen
$d_{1}=d(x_{1},\epsilon)$! Thus,

$\displaystyle\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(C)$
$\displaystyle\leq\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d_{1}}(x_{1}))$
$\displaystyle\leq{\operatorname{max}}\\{-g(x_{1})+\epsilon,-1/\epsilon\\},$

and letting $\epsilon$ tend to zero,

$\displaystyle\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(C)$
$\displaystyle\leq-g(x_{1})\leq-\inf_{F}g.$

$\underline{\Longrightarrow}$: Conversely, suppose LDP$\,(\mu_{n},r_{n})$ with
rate function $I$. By the large deviation lower bound,

$I(x)\geq\inf_{O}I\geq-\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(O),$

for any open set $O$ containing $x$, so putting $O=B_{d}(x)$ and supping over
$d$,

$I(x)\geq-\lim_{d\rightarrow
0}\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d}(x)).$

By the large deviation upper bound,

$-\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(\overline{B_{d}(x)})\geq\inf_{\overline{B_{d}(x)}}I,$

so

$I(x)\geq-\lim_{d\rightarrow
0}\liminf_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(B_{d}(x))\geq-\lim_{d\rightarrow
0}\limsup_{n\rightarrow\infty}\frac{1}{r_{n}}\log\mu_{n}(\overline{B_{d}(x)})\geq\lim_{d\rightarrow
0}\inf_{\overline{B_{d}(x)}}I,$

and it suffices to show that

$\lim_{d\rightarrow 0}\inf_{\overline{B_{d}(x)}}I\geq I(x).$

If not, there exists $x_{k}$ such that $\lim_{k}I(x_{k})<I(x)$ and
$x_{k}\rightarrow x$, contradicting lower semicontinuity of $I$. ∎

##  7 Optimal transport

The problem of optimally transporting a given probability measure $\mu\in
P(X)$ (the source measure) to another given probability measure $\nu\in P(Y)$
(the target measure) has a long history, going back to Monge in the 18th
century. It is the problem of finding a measurable map $T:X\rightarrow Y$
satisfying

$\displaystyle T_{\\#}\mu=\nu$ (14)

and minimizing

$\int_{X}c(x,T(x))\mu(x),$

where $c:X\times Y\rightarrow\mathbb{R}$ is some given cost function,
typically $c(x,y)=|x-y|^{2}$. This integral is the total cost, and
$c(x,T(x))\mu(dx)$ is the infinitesimal cost of transporting $x$ to $T(x)$,
with $\mu(dx)$ measuring the amount of mass at the source point $x$. By abuse
of notation we denote the latter by $\mu(x)$ and not $d\mu(x)$ or $\mu(dx)$.

As in previous sections, one should think of $X=Y=\mathbb{R}^{n}$ or
$X=Y=P(\mathbb{R}^{d})$ as the typical examples in our course for the
underlying spaces. Typical examples for the measures to be transported include
uniform measures $1_{\Omega}$ (for a unit-volume set $\Omega$) and the
empirical measures

$\displaystyle\delta^{n}(x_{1},\ldots,x_{n}):=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}}.$

Choosing both the source and the target measures to be empirical measures with
the same number of point masses (i.e., choosing $\mu$ and $\nu$ in the image
of $\delta^{n}$ for the same $n$) gives rise to the so-called discrete optimal
transport problem.  The solution is then given by a permutation $\sigma\in
S_{n}$ on the set of $n$ letters, satisfying

$\displaystyle\sum_{i=1}^{n}c(x_{i},y_{i})\leq\sum_{i=1}^{n}c(x_{i},y_{\sigma(i)}).$
(15)

In the prototypical case of squared distance cost some cancellations give that

$\displaystyle\sum_{i=1}^{n}|x_{i}-y_{i}|^{2}\leq\sum_{i=1}^{n}|x_{i}-y_{\sigma(i)}|^{2}$

can be rewritten as

$\displaystyle\sum_{i=1}^{n}-\langle
x_{i},y_{i}\rangle\leq\sum_{i=1}^{n}-\langle x_{i},y_{\sigma(i)}\rangle.$ (16)

So, the cost $|x-y|^{2}$ is really ‘equivalent’ to the cost $-\langle
x,y\rangle$. More generally, if $c(x,y)=d(x,y)+f(x)+g(y)$ then $c$ and $d$ are
equivalent:

$\int_{X}c(x,T(x))\mu(x)=\int_{X}d(x,T(x))\mu(x)+\int_{X}f\mu+\int_{X}g(T(x))\mu=\int_{X}d(x,T(x))\mu(x)+\int_{X}f\mu+\int_{Y}g\nu$

(as $\int_{X}f\mu+\int_{Y}g\nu$ is a constant completely determined by the
“data” $\mu,\nu$), where in the last equation we used that

$\int_{X}g\circ T\mu=\int_{Y}g\nu,$

by (14) [32, (9)].

More generally, one can search for an optimal transportation plan. Given a
product space, say $X\times Y$, equipped with projection maps $\pi_{X}:X\times
Y\rightarrow X$ and $\pi_{Y}:X\times Y\rightarrow Y$, the marginals of a
measure $\gamma\in P(X\times Y)$ are $(\pi_{X})_{\\#}\gamma$ and
$(\pi_{Y})_{\\#}\gamma$.

######  Definition 7.1.

A transportation plan is a probability measure $\gamma\in P(X\times Y)$ whose
marginals are $\mu$ and $\nu$. We denote this by $\gamma\in\Pi(\mu,\nu)$.

I.e., $\gamma(A\times Y)=\mu(A)$ and $\gamma(X\times B)=\nu(B)$ for all Borel
$A\subset X$ and $B\subset Y$

######  Definition 7.2.

An optimal transportation plan  is a transportation plan minimizing

$\int_{X\times Y}c\gamma.$

The “best” transport plan is the one coming from transport map $T:X\rightarrow
Y$. Denote by $\operatorname{Id}\otimes T:X\rightarrow X\times Y$ the map
$x\mapsto(x,T(x))$. Indeed, $\gamma:=(\operatorname{Id}\otimes
T)_{\\#}\mu\in\Pi(\mu,\nu)$ since $(\operatorname{Id}\otimes
T)_{\\#}\mu(A\times Y)=\mu\big{(}(\operatorname{Id}\otimes T)^{-1}(A\times
Y)\big{)}=\mu(A)$ and $(\operatorname{Id}\otimes T)_{\\#}\mu(X\times
B)=\mu\big{(}(\operatorname{Id}\otimes T)^{-1}(X\times
B)\big{)}=\mu(T^{-1}(B))=\nu(B)$ since $T_{\\#}\mu=\nu$. Our goal will be to
show that under some natural assumptions the optimal  plan must be of such a
form, i.e., supported on the graph of a map.

For example, in the case of empirical measures, a transportation plan must be
coming from a map represented by a permutation (in other words, it must be
supported on the graph of a permutation in the product space): if one of the
source points is not in $\operatorname{supp}\gamma$ then the first marginal
condition is violated ($\gamma(\\{x_{i}\\}\times Y)=0$ while
$\mu\\{x_{i}\\}=1/n$ but $\gamma(A\times Y)=\mu(A)$), while if one of the
target points is not in $\operatorname{supp}\gamma$ then the second marginal
condition is violated. Thus $\sigma\in S_{n}$, or more precisely,

$\gamma:=\frac{1}{n}\sum\delta_{(x_{i},y_{\sigma(i)})}=\delta_{{\operatorname{gr}}(T)},$

(where $T:x_{i}\mapsto y_{\sigma(i)}$) is optimal if and only if (16) holds.

###  7.1 From the discrete problem to the general one

A beautiful part of the story is that the discrete problem actually is the key
to understanding the general transport problem. Equation (16) leads to the
following definition (we replace $n$ in (16) with $m$ for the following
discussion).

######  Definition 7.3.

A set $A\subset X\times Y$ is cyclically monotone if (16) holds for any
$\\{(x_{i},y_{i})\\}_{i=1}^{m}\subset A$, $m\in\mathbb{N}$, and any $\sigma\in
S_{m}$.

Cyclical monotonicity essentially characterizes convexity. More precisely, the
graph of the sub differential of a convex function $f$ is cyclically monotone:
if $y_{i}\in\partial f(x_{i})$

$f(z)\geq f(x_{i})+\langle z-x_{i},y\rangle,\quad\forall z,$

so taking $z=x_{i+1}$ (with $x_{m+1}=x_{1}$) and adding up the equations
yields (16). Conversely, to a cyclically monotone set $A$ we can associate a
convex function $f_{A}$ such that $A\subset{\operatorname{gr}}(\partial
f_{A})$ as follows. Fix $(x_{0},y_{0})\in A$ and set

$f_{A}(x):=\sup_{m\in\mathbb{N}}\sup_{\\{(x_{i},y_{i})\\}_{i=1}^{m}\subset
A}\Big{\\{}\langle x-x_{m},y_{m}\rangle+\langle
x_{m}-x_{m-1},y_{m-1}\rangle+\ldots+\langle
x_{1}-x_{0},y_{0}\rangle\Big{\\}}.$

Note that $f_{A}$ is not $\pm\infty$ :

######  Claim 7.4.

$f_{A}(x_{0})=0$.

######  Remark 7.5.

We will eventually prove much more, namely, that $f_{A}$ is nowhere
$\pm\infty$.

###### Proof.

First, $f_{A}(x_{0})\leq 0$ from (16) with $m$ replaced by $m+1$ and
$\sigma(i)=i+1$. Second, $f_{A}(x_{0})\geq 0$ by putting $m=1$ and
$(x_{1},y_{1})=(x_{0},y_{0})$ in the definition of $f_{A}$. ∎

Finally, if $(a,b)\in A$, want to show $b\in\partial f_{A}(a)$ (the sub-
differential of $f_{A}$), i.e.,

$\displaystyle f_{A}(z)\geq f_{A}(a)+\langle z-a,b\rangle,\quad\forall z.$
(17)

Given any $\epsilon>0$ there is some $m\in\mathbb{N}$ and some
$\\{(x_{i},y_{i})\\}_{i=1}^{m}\subset A$ such that

$\displaystyle f_{A}(a)-\epsilon=\langle a-x_{m},y_{m}\rangle+\langle
x_{m}-x_{m-1},y_{m-1}\rangle+\ldots+\langle x_{1}-x_{0},y_{0}\rangle.$ (18)

Thus,

$f_{A}(a)+\langle z-a,b\rangle=\epsilon+\langle z-a,b\rangle+\langle
a-x_{m},y_{m}\rangle+\langle x_{m}-x_{m-1},y_{m-1}\rangle+\ldots+\langle
x_{1}-x_{0},y_{0}\rangle\leq\epsilon+f_{A}(z),$

putting $m+1$ and $\\{(x_{i},y_{i})\\}_{i=1}^{m}\cup\\{(a,b)\\}$ in the
definition of $f_{A}$. Letting $\epsilon\rightarrow 0$ concludes the proof of
(17).

######  Exercise 7.6.

Find the mistake in the previous argument.

Solution. The problem was that we were implicitly assuming that
$f_{A}(a)<\infty.$ Indeed, if $f_{A}(a)=\infty$ one cannot, given any
$\epsilon>0$, find $\\{(x_{i},y_{i})\\}_{i=1}^{m}\subset A$ such that (18)
holds. Instead, let $t\in\mathbb{R}$ be any number satisfying $t<f_{A}(a)$
(possibly, $f_{A}(a)=\infty$). Now, there do exist, by definition,
$\\{(x_{i},y_{i})\\}_{i=1}^{m}\subset A$ such that

$\displaystyle t<\langle a-x_{m},y_{m}\rangle+\langle
x_{m}-x_{m-1},y_{m-1}\rangle+\ldots+\langle x_{1}-x_{0},y_{0}\rangle.$ (19)

Thus, for all $z$,

$\displaystyle t+\langle z-a,b\rangle<\langle z-a,b\rangle+\langle
a-x_{m},y_{m}\rangle+\langle x_{m}-x_{m-1},y_{m-1}\rangle+\ldots+\langle
x_{1}-x_{0},y_{0}\rangle\leq f_{A}(z),$ (20)

by putting $m+1$ and $\\{(x_{i},y_{i})\\}_{i=1}^{m}\cup\\{(a,b)\\}$ in the
definition of $f_{A}$. Supping over all $t$ in (20),

$f_{A}(a)+\langle z-a,b\rangle=\sup_{t<f_{A}(a)}t+\langle z-a,b\rangle\leq
f_{A}(z),$

as desired, i.e., $b\in\partial f_{A}(a)$, unless $f_{A}(a)=\infty$ (in which
case $\partial f_{A}(a)=\emptyset$ by definition). To exclude this, i.e., to
show $f_{A}$ is always finite, we put $z=0$ in (20), and use Claim 7.4,

$t+\langle 0-a,b\rangle<f_{A}(0)=0,$

so we get the a priori estimate

$t<\langle a,b\rangle,\qquad\hbox{for any $t<f_{A}(a)$}.$

Hence, $f_{A}(a)=\sup_{t<f_{A}(a)}t\leq\langle a,b\rangle$ and in particular
$f_{A}(a)$ is finite (obviously $f_{A}>-\infty$ since it is a supremum of
finite quantities over a nonempty set).

Recall the definition of the sub-differential $\partial f$ (17) of a convex
function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$. The graph of $\partial f$ is
defined as ${\operatorname{gr}}(\partial
f):=\\{(x,y)\,:\,x\in\mathbb{R}^{n},y\in\partial f(x)\\}.$ Thus, we have
shown:

######  Theorem 7.7.

(Rockafellar’s Theorem) A set $A\subset\mathbb{R}^{n}\times\mathbb{R}^{n}$ is
cyclically monotone if and only if $A\subset{\operatorname{gr}}(\partial f)$
for a convex function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$.

######  Remark 7.8.

Note, again, that part of the conclusion of the theorem is that $f$ is finite
(which should not come as a surprise, as also the set $A$ is “finite-valued”
by assumption; the converse direction is obvious since if $f$ is finite-valued
then so is $\partial f$). In fact,

$f_{A}(x)\leq\inf_{(x,y)\in A}\langle x,y\rangle\leq
h_{\\{x\\}\times\mathbb{R}^{n}\cap A}(x),$

where $h_{K}$ is the support function of the set $K$ with equality in the last
inequality if $A$ is graphical (i.e., of the form
${\operatorname{gr}}(\partial f)$ with $f$ as above).

The Fundamental Theorem of OT gives the final chain connecting the discrete
problem to the continuous problem: the support of an optimal transport plan is
cyclically monotone. Thus, by a previous observation it is contained in the
graph of the sub differential of a convex function. Since a convex function is
differentiable away from a (Lesbegue) measure zero set as measures
$(\operatorname{Id}\otimes\partial f)_{\\#}\mu=(\operatorname{Id}\otimes\nabla
f)_{\\#}\mu$ where on the right hand side by $\nabla f$ we mean (by some abuse
of notation) the gradient map restricted to those $x\in\mathbb{R}^{n}$ where
$\partial f(x)$ is a singleton (that we then denote by $\nabla f(x)$); note
also that assuming $\mu$ is absolutely continuous, Lebesgue measure zero sets
are also $\mu$-measure zero sets. Thus, we have come full circle, and solved
the original transportation problem in terms of a map.

######  Theorem 7.9.

(Fundamental Theorem of Optimal Transport)  Let $\gamma\in\Pi(\mu,\nu)$. Then,

$\gamma$ optimal $\Leftrightarrow$ $\operatorname{supp}\gamma$ is cyclically
monotone $\Leftrightarrow$ exists $f$ convex such that
$\operatorname{supp}\gamma\subset{\operatorname{gr}}(\partial f)$.

###### Proof.

By Theorem 7.7, it suffices to show the first equivalence, but we will
actually only use the hard part of Theorem 7.7 and proceed to prove the
implications cyclically. First, suppose that for some $\gamma\in\Pi(\mu,\nu)$,
$\operatorname{supp}\gamma$ is cyclically monotone. By Theorem 7.7, there
exists $f$ convex such that
$\operatorname{supp}\gamma\subset{\operatorname{gr}}(\partial f)$. Thus, for
every $\tilde{\gamma}\in\Pi(\mu,\nu)$,

$\displaystyle\int_{X\times Y}-\langle x,y\rangle\gamma$
$\displaystyle=\int_{\operatorname{supp}\gamma}-\langle x,y\rangle\gamma$ (21)
$\displaystyle=\int_{\operatorname{supp}\gamma}[-f(x)-f^{\star}(y)]\gamma$
$\displaystyle=-\int_{X}f\mu-\int_{Y}f^{\star}\nu.$
$\displaystyle=\int_{X\times Y}[-f(x)-f^{\star}(y)]\tilde{\gamma}$
$\displaystyle\leq\int_{X\times Y}-\langle x,y\rangle\tilde{\gamma},$

so by definition $\gamma$ is optimal.

Next, assume that $\gamma$ is optimal. We want to show that
$\operatorname{supp}\gamma$ is cyclically monotone. Fix
$\\{(x_{i},y_{i})\\}_{i=1}^{m}\subset\operatorname{supp}\gamma$. To that end,
we carefully construct $\tilde{\gamma}\in\Pi(\mu,\nu)$ of the form
$\tilde{\gamma}:=\gamma+\eta$ with

$\displaystyle 0\leq\int_{X\times Y}-\langle
x,y\rangle\tilde{\gamma}-\int_{X\times Y}-\langle
x,y\rangle\gamma\approx\sum_{i=1}^{n}-\langle
x_{i},y_{\sigma(i)}\rangle-\sum_{i=1}^{n}-\langle x_{i},y_{i}\rangle.$ (22)

Of course, the idea is to construct the positive part of $\eta$ to be
concentrated near $\\{(x_{i},y_{\sigma(i)})\\}_{i=1}^{m}$ and the negative
part of $\eta$ to be concentrated near $\\{(x_{i},y_{i})\\}_{i=1}^{m}$. We
have to do this in such a way that $\gamma+\eta$ is still admissible (i.e., a
transport plan). Equivalently,
$(\pi_{X})_{\\#}\eta=0,\,(\pi_{Y})_{\\#}\eta=0$.

For the construction, we fix $\epsilon>0$. Set

$\Gamma:=\prod_{i=1}^{m}\frac{\gamma|_{B_{\epsilon}(x_{i})\times
B_{\epsilon}(y_{i})}}{|\gamma\big{(}B_{\epsilon}(x_{i})\times
B_{\epsilon}(y_{i})\big{)}|}$

This is an auxiliary probability measure on $P\big{(}(X\times Y)^{m}\big{)}$.
It is useful, because it’s marginals allow us to cyclically modify the way
$\gamma$ transports: in order to transport $B_{\epsilon}(x_{i})$ to
$B_{\epsilon}(y_{\sigma(i)})$ instead of to $B_{\epsilon}(y_{i})$ we would add

$(\pi_{B_{\epsilon}(x_{i})},\pi_{B_{\epsilon}(y_{\sigma(i)})})_{\\#}\Gamma-(\pi_{B_{\epsilon}(x_{i})},\pi_{B_{\epsilon}(y_{i})})_{\\#}\Gamma.$

to $\gamma$. So, overall, we set

$\displaystyle\eta:=\frac{\min_{i}|\gamma\big{(}B_{\epsilon}(x_{i})\times
B_{\epsilon}(y_{i})\big{)}|}{m}\sum_{i=1}^{m}\Big{[}(\pi_{B_{\epsilon}(x_{i})},\pi_{B_{\epsilon}(y_{\sigma(i)})})_{\\#}\Gamma-(\pi_{B_{\epsilon}(x_{i})},\pi_{B_{\epsilon}(y_{i})})_{\\#}\Gamma\Big{]}.$
(23)

The constant ${\min_{i}|\gamma\big{(}B_{\epsilon}(x_{i})\times
B_{\epsilon}(y_{i})\big{)}|}/{m}$ in front of some ensures that $\gamma+\eta$
is still a positive measure (recalling that
$|\gamma\big{(}B_{\epsilon}(x_{i})\times B_{\epsilon}(y_{i})\big{)}|$ appears
in the denominator of $\Gamma$, so the largest negative term inside the
brackets in (23) is ${\min_{i}|\gamma\big{(}B_{\epsilon}(x_{i})\times
B_{\epsilon}(y_{i})\big{)}|}$ and there are at most $m$ of these negative
terms). Next, to show $(\pi_{Y})_{\\#}\eta=0$ amounts to $\eta(X\times B)=0$
for each $B$, and indeed, up to a positive factor
$(\pi_{Y})_{\\#}\eta(B)=\eta(X\times B)$ equals

$\displaystyle\sum_{i=1}^{m}\Big{[}(\pi_{B_{\epsilon}(x_{i})},\pi_{B_{\epsilon}(y_{\sigma(i)})})_{\\#}\Gamma(X\times
B)-(\pi_{B_{\epsilon}(x_{i})},\pi_{B_{\epsilon}(y_{i})})_{\\#}\Gamma(X\times
B)\Big{]}$ $\displaystyle=\sum_{i=1}^{m}\Gamma(X\times Y\times\cdots\times
X\mskip-25.0mu\buildrel\hbox{\rmfoot$\sigma(i)$-th
slot}\over{\times}\mskip-25.0muB\times\cdots\times X\times Y)$
$\displaystyle\quad-\sum_{i=1}^{m}\Gamma(X\times Y\times\cdots\times
X\mskip-15.0mu\buildrel\hbox{\rmfoot$i$-th
slot}\over{\times}\mskip-15.0muB\times\cdots\times X\times Y)=0$

Finally, $\,(\pi_{X})_{\\#}\eta=0$ is easier as

$\displaystyle\sum_{i=1}^{m}\Big{[}(\pi_{B_{\epsilon}(x_{i})},\pi_{B_{\epsilon}(y_{\sigma(i)})})_{\\#}\Gamma(A\times
Y)-(\pi_{B_{\epsilon}(x_{i})},\pi_{B_{\epsilon}(y_{i})})_{\\#}\Gamma(A\times
Y)\Big{]}$ $\displaystyle=\sum_{i=1}^{m}\Gamma(X\times Y\times\cdots\times
A\mskip-25.0mu\buildrel\hbox{\rmfoot$\sigma(i)$-th
slot}\over{\times}\mskip-25.0muY\times\cdots\times X\times Y)$
$\displaystyle\quad-\sum_{i=1}^{m}\Gamma(X\times Y\times\cdots\times
A\mskip-15.0mu\buildrel\hbox{\rmfoot$i$-th
slot}\over{\times}\mskip-15.0muY\times\cdots\times X\times
Y)=\sum_{i=1}^{m}0=0$

(i.e., is term-by-term zero).

Thus, we have shown (22) up to $o(\epsilon)$. Letting $\epsilon\rightarrow 0$
proves (16), as claimed. ∎

###  7.2 Dual formulation

A rather immediate consequence of Theorems 7.7 and 7.9 is the following dual
formulation of the optimal transportation problem in terms of an optimization
problem on functions  instead of measures.

######  Theorem 7.10.

Let $c(x,y)=-\langle x,y\rangle$.

$\inf_{\gamma\in\Pi(\mu,\nu)}\int_{X\times Y}c\gamma=\sup_{f(x)+g(y)\leq
c(x,y)}\Big{[}\int_{X}f\mu+\int_{Y}g\nu\Big{]}.$ (24)

###### Proof.

According to Lemma 7.12 there exists $\gamma$ realizing the infimum on the
left-hand side. Let $f,g$ be such that $f(x)+g(y)\leq-\langle x,y\rangle$.
Then

$\int_{X\times Y}c\gamma\geq\int_{X\times
Y}(f(x)+g(y))\gamma=\int_{X}f\mu+\int_{Y}g\nu.$

It thus remains to show

$\displaystyle\int_{X\times Y}c\gamma\leq\sup_{f(x)+g(y)\leq
c(x,y)}\Big{[}\int_{X}f\mu+\int_{Y}g\nu\Big{]}.$ (25)

Theorems 7.7 and 7.9 imply that
$\operatorname{supp}\,\gamma\subset{\operatorname{gr}}(\nabla\phi)$ for some
convex function $\phi$. Since $\phi(x)+\phi^{\star}(y)\geq-c(x,y)$ with the
quality if and only if $(x,y)\in{\operatorname{gr}}(\partial\phi)$,

$\displaystyle\int_{X\times Y}c\gamma$
$\displaystyle=\int_{\operatorname{supp}\gamma}c\gamma$
$\displaystyle=\int_{{\operatorname{gr}}(\partial\phi)}c\gamma$
$\displaystyle=\int_{X\times Y}[-\phi(x)-\phi^{\star}(y)]\gamma$
$\displaystyle=\int_{X\times Y}[-\phi(x)-\phi^{\star}(y)]\gamma$
$\displaystyle=-\int_{X}\phi\mu-\int_{Y}\phi^{\star}\nu.$

Thus, (25) holds as already the pair $(f,g)=(-\phi,-\phi^{\star})$ equals the
left-hand side. ∎

In fact, we saw that the dual formulation can be given in terms of a single
(and convex) function. Also, we play a bit with the signs, to get:

######  Corollary 7.11.

(Dual formulation of optimal transportation)

$\sup_{\gamma\in\Pi(\mu,\nu)}\int_{X\times Y}\langle
x,y\rangle\gamma=\inf_{f\in
C(X)}\Big{[}\int_{X}f\mu+\int_{Y}f^{\star}\nu\Big{]}=\inf_{f\in\operatorname{Cvx}(X)}\Big{[}\int_{X}f\mu+\int_{Y}f^{\star}\nu\Big{]}.$

######  Lemma 7.12.

The infimum on the left hand side of (24) is attained.

###### Proof.

The proof follows Ambrosio–Gigli who work in a more general setting [2, §1.1].
Since $c:X\times Y\rightarrow\mathbb{R}$ is continuous (in fact, lower
semicontinuous is enough, with slightly more work [2, Theorem 1.2]) then
$\gamma\mapsto\int c\gamma$ is continuous with respect to the weak topology.
Since

$\displaystyle\gamma(X\times Y\setminus K_{1}\times K_{2})\leq\mu(X\setminus
K_{1})+\mu(Y\setminus K_{2}),$ (26)

for any  $\gamma\in\Pi(\mu,\nu)$, it follows that $\Pi(\mu,\nu)$ satisfies the
assumptions of Prokhorov’s Theorem (see [2, Theorem 1.3]): indeed, the right-
hand side of (26) can be made arbitrarily small by Ulam’s Theorem (any Borel
probability measure on a Polish space is concentrated on a compact set up to
an arbitrarily small error) applied to the Polish measure spaces $(X,\mu)$ and
$(Y,\nu)$. Thus, $\Pi(\mu,\nu)$ is pre-compact. The closure of a pre-compact
set is by definition compact, it suffices to show that $\Pi(\mu,\nu)$ is
actually closed (with respect to the weak topology), but this is immediate
since $\int f\mu=\int f(x)\gamma_{n}\rightarrow\int f(x)\gamma=\int f\mu$
(note that $(x,y)\mapsto f(x)$ for $f\in C(X)$ is in $C(X\times Y)$ so then
$\alpha\mapsto\int f(x)\alpha$ is continuous with respect to the weak
topology) and similarly for the other marginal. Since a lower semicontinuous
functional attains its infimum on a compact set, we are done. ∎

###  7.3 The Legendre transform of Wasserstein distance

Denote by

$\displaystyle C(X):=C^{0}(X)\cap L^{\infty}(X)$ (27)

the continuous and bounded functions on $X$.

Let $J_{\nu}:C(X)\rightarrow\mathbb{R}$ be

$\displaystyle J_{\nu}(f):=\int_{Y}f^{\star}\nu.$ (28)

Denote by $W_{2}^{2}:P(X)\times P(Y)\rightarrow\mathbb{R}$

$\displaystyle W_{2}^{2}(\mu,\nu):=\inf_{\gamma\in\Pi(\mu,\nu)}\int_{X\times
Y}c\gamma$ (29)

the Wasserstein distance between $\mu$ and $\nu$. It will be convenient to
extend this functional to ${\mathcal{M}}(X)\times{\mathcal{M}}(Y)$ “by
infinity,” namely

$W_{2}^{2}(\mu,\nu):=\infty$

if either $\mu\not\in P(X)$ or $\nu\not\in P(Y)$.

Our work so far can be summarized in terms of Legendre duality these two
functionals: indeed, for any $\mu\in P(X)$,

$\displaystyle-W_{2}^{2}(\mu,\nu)$ $\displaystyle=\inf_{f\in
C(X)}\Big{[}\int_{X}f\mu+\int_{Y}f^{\star}\nu\Big{]}$
$\displaystyle=-\sup_{f\in C(X)}\Big{[}\langle f,-\mu\rangle-
J_{\nu}(f)\Big{]}=-J_{\nu}^{\star}(-\mu),$

while if $\mu\in{\mathcal{M}}(X)$ but $\mu\not\in P(X)$ then since
$(f+C)^{\star}=f^{\star}-C$ we see $\langle f+C,-\mu\rangle-J(f+C)=\langle
f,-\mu\rangle-J_{\nu}(f)+C(1-\mu(X))$ which can be made arbitrarily large if
$\mu(X)\not=1$, which is to say that $J_{\nu}^{\star}(-\mu)=\infty$, i.e., we
have

$\displaystyle W_{2}^{2}(\mu,\nu)=J_{\nu}^{\star}(-\mu).$ (30)

The following theorem summarizes this and more. This is the first time the
Monge–Ampère operator

$\displaystyle\operatorname{MA}_{\nu}f:=(\nabla f^{\star})_{\\#}\nu$ (31)

makes its appearance.

######  Remark 7.13.

When $\nu=dx$ this reduces to the well-known Monge–Ampère operator

$\operatorname{MA}f=d\nabla f:=d\frac{\partial f}{\partial
x_{1}}\wedge\cdots\wedge d\frac{\partial f}{\partial x_{n}},$

since

$\int_{X}F(\nabla f^{\star})_{\\#}dx=\int_{Y}F\circ(\nabla
f^{\star})dx=\int_{Y}F\circ(\nabla f)^{-1}dx=\int_{X}Fd\nabla
f(x)=\int_{X}F\det\nabla f(x).$

When $f\in C^{2}$ then $\operatorname{MA}f=\det\nabla^{2}f$.

######  Theorem 7.14.

$J_{\nu}$ and $W_{2}^{2}(-\,\cdot\,,\nu)$ are convex, lower semicontinuous,
and Legendre dual to each other. $J_{\nu}$ is Gateaux differentiable and

$\displaystyle dJ_{\nu}|_{f}=-\operatorname{MA}_{\nu}f.$ (32)

###### Proof.

$\bullet\,\,$First, note that $J_{\nu}$ is actually continuous: if $C(X)\ni
f_{j}\rightarrow f$ in $C^{0}$ then $f_{j}^{\star}\rightarrow f^{\star}$
pointwise and hence uniformly [28, Theorem 10.8] so $J$ is continuous.

$\bullet\,\,$Convexity of $J$ is elementary:

$\displaystyle J_{\nu}\Big{(}\frac{\theta+\chi}{2}\Big{)}$
$\displaystyle=\int_{Y}\sup_{x}\Big{[}\langle
x,y\rangle-\frac{\theta(x)+\chi(x)}{2}\Big{]}\nu$
$\displaystyle\leq\frac{1}{2}\int_{Y}\sup_{x}[\langle
x,y\rangle-\theta(x)]\nu+\frac{1}{2}\int_{Y}\sup_{x}[\langle
x,y\rangle-\chi(x)]\nu$
$\displaystyle=\frac{1}{2}J_{\nu}(\theta)+\frac{1}{2}J_{\nu}(\chi).$

$\bullet\,\,$Convexity of $W_{2}^{2}(-\,\cdot\,,\nu)$ then follows from (30),
being the supremum of affine functionals, which also implies lower semi-
continuity (the supremum of continuous functions).

$\bullet\,\,$Legendre duality was already proven in (30).

$\bullet\,\,$Legendre duality implies that

$\displaystyle J_{\nu}(f)+W_{2}^{2}(\mu,\nu)\geq-\langle f,\mu\rangle.$ (33)

Fix $f$. To show Gateaux differentiability and (32) it suffices to show that
there exists exactly one $\mu$ for which equality is attained, and that then
$\mu=\operatorname{MA}_{\nu}f$. Define $\mu=:(\nabla f^{\star})_{\\#}\nu$. By
Theorem 7.9 and Corollary 7.11 then $(\operatorname{Id}\otimes\nabla
f)_{\\#}\mu\in\Pi(\mu,\nu)$ is an optimal transport plan and

$W_{2}^{2}(\mu,\nu)=-\langle f,\mu\rangle-\langle
f^{\star},\nu\rangle=-\langle f,\mu\rangle-J_{\nu}(f).$

Now, $\mu=(\nabla f^{\star})_{\\#}\nu=\operatorname{MA}_{\nu}f$ by definition.
Thus, it suffices to show that this $\mu$ is the only one attaining equality
in (33), i.e., it suffices to show that $J$ is strictly convex. Suppose
$\alpha$ is another such measure, i.e.,

$W_{2}^{2}(\alpha,\nu)=-\langle f,\alpha\rangle-\langle f^{\star},\nu\rangle.$

From Theorem 7.9 and Corollary 7.11 $(\operatorname{Id}\otimes\nabla
f)_{\\#}\alpha\in\Pi(\alpha,\nu)$ is an optimal transport plan and
$\alpha=(\nabla f^{\star})_{\\#}\nu$ so $\alpha=\mu$. ∎

###  7.4 Rate function for Monge–Ampère

Let $\beta\in\mathbb{R}$ and let

$\mu_{0}\in P(X)$

be a fixed reference probability measure. We are interested in the
Monge–Ampère equation

$\displaystyle\operatorname{MA}_{\nu}f=e^{\beta
f}\mu_{0}\Big{/}\int_{X}e^{\beta f}\mu_{0}.$ (34)

Define $F_{\beta,\nu}:C(X)\rightarrow\mathbb{R}$ by

$\displaystyle
F_{\beta,\mu_{0},\nu}(\theta):=\frac{1}{\beta}I_{\mu_{0}}(\beta\theta)+J_{\nu}(\theta).$
(35)

By (32) and the proof of Lemma 4.4:

######  Lemma 7.15.

$F_{\beta,\mu_{0},\nu}$ is Gateaux differentiable and

$\displaystyle dF_{\beta,\mu_{0},\nu}|_{\theta}=e^{\beta
f}\mu_{0}\Big{/}\int_{X}e^{\beta f}\mu_{0}-\operatorname{MA}_{\nu}f.$ (36)

Finally, we can define the rate function underlining the Monge–Ampère
equation:

$\displaystyle G_{\beta,\mu_{0},\nu}:=\beta W^{2}_{2}(\,\cdot\,,\nu)+\hbox{\rm
Ent}(\mu_{0},\,\cdot\,)+C,$ (37)

where $C$ is a constant that will guarantee the function is nonnegative and
zero at its minimum.

######  Proposition 7.16.

Assume that $F_{\beta,\mu_{0},\nu}$ admits a unique (up to a constant)
minimizer $\phi_{\min}$. Then $G_{\beta,\mu_{0},\nu}$ admits a unique
minimizer $\mu=\operatorname{MA}_{\nu}\phi_{\min}$. The converse is also true.

Before going into the proof, let us motivate it with a general observation
about Legendre duals in finite dimensions. If

$F=f_{1}+f_{2}$

is the sum of two differentiable strictly convex functions, and $x$ is the
unique minimum of $F$ then

$G(y):=f_{1}^{\star}(y)+f_{2}^{\star}(-y)$

has a unique minimum at $df_{1}(x)$. Indeed,

$df_{1}(x)=-df_{2}(x)$

while ($G$ is differentiable since $f_{1}^{\star}$ and $f_{2}^{\star}$ are by
the strict convexity of $f_{1},f_{2}$ [28, Theorem 26.3])

$dG(y)=df_{1}^{\star}(y)-df_{2}^{\star}(-y)=(df_{1})^{-1}(y)-(df_{2})^{-1}(-y)$

and setting $y=df_{1}(x)=-df_{2}(x)$

$dG(y)=(df_{1})^{-1}(df_{1}(x))-(df_{2})^{-1}(--df_{2}(x))=x-x=0.$

Thus, $y$ is a critical point of the convex function $G$, hence a minimum
point. This is the only minimum point since the proof is reversible: if
$dG(\tilde{y})=0$ we get
$df_{1}^{\star}(\tilde{y})=df_{2}^{\star}(-\tilde{y})$ so
$df_{1}(\tilde{x})=-df_{2}(\tilde{x})$ for
$\tilde{x}=df_{1}^{\star}(\tilde{y})$, so then $\tilde{x}$ is a critical point
of $F$, hence a minimum, so then $x=\tilde{x}$ since by assumption $x$ was the
unique minimum. Thus $df_{1}^{\star}(y)=df_{1}^{\star}(\tilde{y})$ implying
$y=\tilde{y}$ if $f_{1}^{\star}$ is strictly convex, but this follows from
differentiability of $f_{1}$ [28, Theorem 26.3].

###### Proof.

Essentially, the conclusion of the finite-dimensional discussion above holds
also in our situation by chasing through the definitions and avoiding the use
of [28, Theorem 26.3]. Here goes.

First, by Theorem 7.14 and (8),

$\displaystyle W_{2}^{2}(\mu,\nu)+J_{\nu}(f)\geq-\langle
f,\mu\rangle,\qquad\hbox{equality if and only if
$\mu=\operatorname{MA}_{\nu}f$}.$

Second, by Lemma 4.4 and (8),

$\displaystyle\hbox{\rm Ent}(\mu_{0},\mu)+I_{\mu_{0}}(f)\geq\langle
f,\mu\rangle,\qquad\hbox{equality if and only if
$\mu=e^{f}\mu_{0}/\int_{X}e^{f}\mu_{0}$}.$

Let $\phi_{\min}$ be the minimizer of $F_{\beta,\mu_{0},\nu}$. By Lemma 7.15

$\displaystyle\operatorname{MA}_{\nu}\phi_{\min}=e^{\beta\phi_{\min}}\mu_{0}\Big{/}\int_{X}e^{\beta\phi_{\min}}\mu_{0}.$
(38)

$\bullet\,\,$Assume first $\beta>0$. Then setting $f=\phi_{\min}$ and
$f=\beta\phi_{\min}$, respectively, in the inequalities above

$\displaystyle G_{\beta,\mu_{0},\nu}(\mu)$ $\displaystyle=\beta
W^{2}_{2}(\mu,\nu)+\hbox{\rm Ent}(\mu_{0},\mu)+C,$
$\displaystyle\geq-\beta\langle\phi_{\min},\mu\rangle-\beta
J_{\nu}(\phi_{\min})-I_{\mu_{0}}(\beta\phi_{\min})+\langle\beta\phi_{\min},\mu\rangle$
$\displaystyle=-\beta J_{\nu}(\phi_{\min})-I_{\mu_{0}}(\beta\phi_{\min})$
$\displaystyle=-\beta F_{\beta,\mu_{0},\nu}(\phi_{\min}),$

with equality if and only if
$\mu=e^{\beta\phi_{\min}}\mu_{0}/\int_{X}e^{\beta\phi_{\min}}\mu_{0}=\operatorname{MA}_{\nu}\phi_{\min}$.
Note that $-\beta F_{\beta,\mu_{0},\nu}(\phi_{\min})$ is some constant
independent of $\mu$. Thus, $\mu=\operatorname{MA}_{\nu}\phi_{\min}$ is the
unique minimizer of $G_{\beta,\mu_{0},\nu}$.

$\bullet\,\,$Assume now that $\beta<0$. Fix $\mu\in{\mathcal{M}}(X)$. Let
$\phi\in C(X)$ be such that equality hold in (33). Now applying above argument
to $f=\phi$ and $f=\beta\phi$, respectively, gives

$\displaystyle G_{\beta,\mu_{0},\nu}(\mu)\geq-\beta
F_{\beta,\mu_{0},\nu}(\phi)\geq-\beta F_{\beta,\mu_{0},\nu}(\phi_{\min}),$

(the last inequality simply because $\phi_{\min}$ is a minimizer of
$F_{\beta,\mu_{0},\nu}$ and $\beta<0$) with equality in the first inequality
if and only if $\mu=e^{\beta\phi}\mu_{0}/\int_{X}e^{\beta\phi}\mu_{0}$ and in
the second inequality if and only if $\phi=\phi_{\min}$ so overall
$\mu=e^{\beta\phi_{\min}}\mu_{0}/\int_{X}e^{\beta\phi_{\min}}\mu_{0}=\operatorname{MA}_{\nu}\phi_{\min}$
by (38). ∎

######  Remark 7.17.

We leave the details for the simpler case $\beta=0$ to the reader (in this
special case the Wasserstein distance does not even appear, and one is
basically reduced to Sanov’s Theorem (Corollary 4.3)). Of course, one has to
also define $F_{0,\mu_{0},\nu}$ appropriately by taking the derivative at
$\beta=0$ of (35).

##  8 Moment generating function for Monge–Ampère

Our goal is now to construct a sequence of probability measures on $P(X)$
(i.e., random measures, or elements of $P(P(X))$) whose moment generating
function (for some normalization) is precisely $G_{\beta,\mu_{0},\nu}$.

Naturally, in view of Sanov’s Theorem (Corollary 4.3), the entropy term in
$G_{\beta,\mu_{0},\nu}$ will come from $\mu_{0}^{\otimes n}$. To obtain the
Wasserstein distance term we will need to multiply the symmetric measure by a
symmetric function that captures discrete optimal transport distance. Here is
the key observation [11, Theorem 3.2]. Let
$H_{n^{d}}:X^{n^{d}}\rightarrow\mathbb{R}$ (the reader can basically consider
the examples (40) and (41) although the next lemma is more general). Set

$\Gamma_{\beta,n}:=\delta^{n^{d}}_{\\#}\Big{(}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes{n^{d}}}\Big{)}\Big{/}Z_{\beta,n}\in P(P(X)),$

with $Z_{\beta,n}:=\int_{X^{n^{d}}}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes{n^{d}}}$ is the normalizing constant guaranteeing
that $\Gamma_{\beta,n}$ is a probability measure; let

$\displaystyle C_{\beta}:=\lim_{n}\frac{1}{n^{d}}\log Z_{\beta,n},$ (39)

where the limit exists and is finite according to Claim 8.3 below.

######  Lemma 8.1.

Let $E:P(X)\rightarrow\mathbb{R}$ be continuous and let
$H_{n^{d}}:X^{n^{d}}\rightarrow\mathbb{R}$. Suppose that
$\lim_{n\rightarrow\infty}||H_{n^{d}}/n^{d}-E\circ\delta^{n^{d}}||_{L^{\infty}(X^{n^{d}})}=0$.
Then LDP$(\Gamma_{\beta,n},{n^{d}})$ with rate function $\beta E+\hbox{\rm
Ent}(\mu_{0},\,\cdot\,)+C_{\beta,n}$, where

$C_{\beta}=-\inf_{\mu}\big{[}\beta E(\mu)+\hbox{\rm
Ent}({\mu_{0}},\mu)\big{]}.$

######  Remark 8.2.

In some sense, the constant $C_{\beta}$ has to equal this value if this
function is to be a rate function, indeed this way the infimum is equal to
zero, as it must by Remark 3.5.

###### Proof.

This does not seem to follow easily from a moment generating function
computation. Instead, we use the more direct criterion given by Proposition
6.1. Now ${\mathcal{X}}=P(X)$, with balls taken with respect to the
$p$-Wasserstein distance ($p\in[1,\infty)$). Here we need the fact that when
$X$ is compact, $P(X)$ equipped with the $p$-Wasserstein distance function is
a compact metric space [2, §2], [33] (the point is that “$p$-Wasserstein
distance metrizes the weak topology” and that $P(X)$ is compact with respect
to the weak topology). We compute (and apply Claim 8.3 below),

$\displaystyle\lim_{e\rightarrow
0}\limsup_{n\rightarrow\infty}\frac{1}{n^{d}}\log\Gamma_{\beta,n}(B_{e}(\mu))$
$\displaystyle=\lim_{e\rightarrow
0}\limsup_{n\rightarrow\infty}\frac{1}{n^{d}}\log\int_{(\delta^{n^{d}})^{-1}(B_{e}(\mu))}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes n^{d}}-C_{\beta,n}$
$\displaystyle=\lim_{e\rightarrow
0}\limsup_{n\rightarrow\infty}\frac{1}{n^{d}}\log\int_{(\delta^{n^{d}})^{-1}(B_{e}(\mu))}e^{-\beta
n^{d}(E\circ\delta^{n}+o(1))}\mu_{0}^{\otimes n^{d}}-C_{\beta,n}$
$\displaystyle=-\beta E(\mu)+\lim_{e\rightarrow
0}\limsup_{n\rightarrow\infty}\frac{1}{n^{d}}\log\int_{(\delta^{n^{d}})^{-1}(B_{e}(\mu))}\mu_{0}^{\otimes
n^{d}}-C_{\beta,n}$ $\displaystyle=-\beta E(\mu)-\hbox{\rm
Ent}({\mu_{0}},\mu)-C_{\beta,n},$

by Corollary 4.3 and Proposition 6.1 (remembering the minus sign in the
latter). Similarly for the liminf. Applying Proposition 6.1 again, we are
done. ∎

######  Claim 8.3.

The limit (39) exists and is finite. In fact,

$C_{\beta,n}=-\inf_{\mu}\big{[}\beta E(\mu)+\hbox{\rm
Ent}({\mu_{0}},\mu)\big{]}.$

###### Proof.

By our previous computation the limit is bounded below, indeed, for any $e>0$
and any $\mu$,

$\displaystyle\liminf_{n}\frac{1}{n^{d}}\log Z_{\beta,n}$
$\displaystyle=\liminf_{n}\frac{1}{n^{d}}\log\int_{X^{n^{d}}}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes{n^{d}}}$
$\displaystyle\geq\liminf_{n}\frac{1}{n^{d}}\log\int_{(\delta^{n^{d}})^{-1}(B_{e}(\mu))}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes{n^{d}}},$

so for every $\mu$,

$\displaystyle\liminf_{n}\frac{1}{n^{d}}\log Z_{\beta,n}$
$\displaystyle\geq-\beta E(\mu)-\hbox{\rm Ent}({\mu_{0}},\mu)$
$\displaystyle\geq\sup_{\mu}\big{[}-\beta E(\mu)-\hbox{\rm
Ent}({\mu_{0}},\mu)\big{]}$ $\displaystyle=-\inf_{\mu}\big{[}\beta
E(\mu)+\hbox{\rm Ent}({\mu_{0}},\mu)\big{]},$

and so,

$\displaystyle\limsup_{n}\frac{1}{n^{d}}\log Z_{\beta,n}$
$\displaystyle\geq-\inf_{\mu}\big{[}\beta E(\mu)+\hbox{\rm
Ent}({\mu_{0}},\mu)\big{]}.$

Finally, by compactness of $P(X)$, fix $e>0$ and cover the space with
finitely-many balls $B_{e}(\mu_{1}),\ldots,B_{e}(\mu_{k})$. Then, of course,

$\displaystyle Z_{\beta,n}$
$\displaystyle=\int_{P(X)}(\delta^{n^{d}})_{\\#}\Big{(}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes{n^{d}}}\Big{)}$
$\displaystyle=\int_{(\delta^{n^{d}})^{-1}(P(X))}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes{n^{d}}}$
$\displaystyle\leq\sum_{j=1}^{k}\int_{(\delta^{n^{d}})^{-1}(B_{e}(\mu_{j}))}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes{n^{d}}}$ $\displaystyle\leq
k\sup_{j}\int_{(\delta^{n^{d}})^{-1}(B_{e}(\mu_{j}))}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes{n^{d}}},$

so

$\displaystyle\liminf_{n}\frac{1}{n^{d}}\log Z_{\beta,n}$
$\displaystyle\leq\liminf_{n}\frac{1}{n^{d}}\log
k+\liminf_{n}\frac{1}{n^{d}}\log\sup_{j}\int_{(\delta^{n^{d}})^{-1}(B_{e}(\mu_{j}))}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes{n^{d}}}$
$\displaystyle=\liminf_{n}\frac{1}{n^{d}}\log\sup_{j}\int_{(\delta^{n^{d}})^{-1}(B_{e}(\mu_{j}))}e^{-\beta
H_{n^{d}}}\mu_{0}^{\otimes{n^{d}}}$ $\displaystyle=\sup_{j}\big{[}-\beta
E(\mu_{j})-\hbox{\rm Ent}({\mu_{0}},\mu_{j})\big{]}$
$\displaystyle=-\inf_{j}\big{[}\beta E(\mu_{j})+\hbox{\rm
Ent}({\mu_{0}},\mu_{j})\big{]}$ $\displaystyle\leq-\inf_{\mu}\big{[}\beta
E(\mu)+\hbox{\rm Ent}({\mu_{0}},\mu)\big{]}.$

Similarly,

$\displaystyle\limsup_{n}\frac{1}{n^{d}}\log
Z_{\beta,n}\leq-\inf_{\mu}\big{[}\beta E(\mu)+\hbox{\rm
Ent}({\mu_{0}},\mu)\big{]},$

so we conclude $C_{\beta,n}=\lim_{n}\frac{1}{n^{d}}\log Z_{\beta,n}$ exists
and equals $-\inf_{\mu}\big{[}\beta E(\mu)+\hbox{\rm
Ent}({\mu_{0}},\mu)\big{]}$. ∎

###  8.1 Finite-dimensional approximations of Wasserstein distance

In view of Lemma 8.1, Proposition 7.16 (and (37)), it remains for us to
construct functions $\\{H_{n}\\}$ that approximate the (pull-back under the
empirical map of the) Wasserstein distance $W^{2}_{2}(\,\cdot\,,\nu)$. We will
do this in the special case $\nu=dx$.

Let $n\in\mathbb{N}$. There are $n^{d}$ $1/n$-lattice points of the cube
$[0,1]^{d}$, and we denote them by $p_{1},\ldots,p_{n^{d}}$. Set

$\phi^{(n)}_{i}(x):=\sum_{m\in\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}.$

A sort of “theta function” for the real torus

$\mathbb{T}:=\mathbb{R}^{d}/\mathbb{Z}^{d}.$

There are two sorts of symmetric functions on $\mathbb{T}^{n^{d}}$ one may
cook up from the $\phi_{i}$’s. First, consider the matrix

$\Phi(x_{1},\ldots,x_{n}):=[\phi^{(n)}_{i}(x_{j})]_{i,j=1}^{n^{d}}.$

Which functions $f$ of $\Phi(x_{1},\ldots,x_{n})$ are invariant under
permutations, i.e., satisfy

$f(\Phi(x_{1},\ldots,x_{n}))=f(\Phi(x_{\sigma(1)},\ldots,x_{\sigma(n)}))?$

In other words, which functions of a matrix are invariant under permutations
of rows? Note that the determinant is only invariant up to a sign. However,
the permanent is fully invariant. First,

$\displaystyle
H_{n}(x_{1},\ldots,x_{n}):=-\frac{1}{n}\log\operatorname{per}\Phi(x_{1},\ldots,x_{n}).$
(40)

Here,

$\operatorname{per}A:=\sum_{\sigma\in
S_{n^{d}}}\prod_{i=1}^{n^{d}}A_{i\sigma(i)}.$

Second,

$\displaystyle
H_{n}(x_{1},\ldots,x_{n}):=-\frac{1}{n}\log\operatorname{per}_{\operatorname{strop}}\Phi(x_{1},\ldots,x_{n}).$
(41)

Here, the semi-tropical permanent  is obtained from the permanent by replacing
summation by supremum,

$\operatorname{per}_{\operatorname{strop}}A:=\sup_{\sigma\in
S_{n^{d}}}\prod_{i=1}^{n^{d}}A_{i\sigma(i)}.$

######  Lemma 8.4.

For both (40) and (41),
$\lim_{n\rightarrow\infty}||H_{n}/n^{d}-W_{2}^{2}\big{(}dx,\delta^{n}(\,\cdot\,)\big{)}||_{L^{\infty}(X^{n})}=0$.

###### Proof.

Since $\delta^{n^{d}}(p_{1},\ldots,p_{n^{d}})\rightarrow dx$ weakly (the
points are dense and uniformly distributed) then in view of Claim 8.5 below,
it suffices to show that

$\lim_{n\rightarrow\infty}||H_{n}/n^{d}-W_{2}^{2}\big{(}\delta^{n^{d}}(p_{1},\ldots,p_{n^{d}}),\delta^{n^{d}}(\,\cdot\,)\big{)}||_{L^{\infty}(X^{n^{d}})}=0.$

This is a nice simplification since we have an explicit formula for the
Wasserstein distance on the image of the empirical map! Indeed [32, p. 5],

$W_{2}^{2}\big{(}\delta^{n^{d}}(p_{1},\ldots,p_{n^{d}}),\delta^{n^{d}}(x_{1},\ldots,x_{n^{d}})\big{)}=\inf_{\sigma\in
S_{n^{d}}}\sum d(p_{i},x_{\sigma(i)})^{2}.$

It is now a simple exercise to complete the proof using Claims 8.6 and 8.7
below. ∎

######  Claim 8.5.

Let $M$ be compact manifold. Let $x_{1},\ldots,x_{k}\in M$ and
$p_{1},\ldots,p_{k}\in M$. Suppose that
$\delta^{k}(p_{1},\ldots,p_{k})\rightarrow\nu$ weakly. Then

$\lim_{k}||W_{2}^{2}\big{(}\delta^{k}(p_{1},\ldots,p_{k}),\delta^{k}(\,\cdot\,)\big{)}-W_{2}^{2}\big{(}\nu,\delta^{k}(\,\cdot\,)\big{)}||_{L^{\infty}(X^{k})}=0.$

###### Proof.

Wasserstein distance is a distance function (see [32, 33]), hence,

$\big{|}W_{2}\big{(}\delta^{k}(p_{1},\ldots,p_{k}),\delta^{k}(x_{1},\ldots,x_{k})\big{)}-W_{2}\big{(}\nu,\delta^{k}(x_{1},\ldots,x_{k})\big{)}\big{|}\leq
W_{2}\big{(}\delta^{k}(p_{1},\ldots,p_{k}),\nu\big{)},$

with the right-hand side independent of $x_{1},\ldots,x_{k}$. On a compact
manifold weak convergence implies convergence in the Wasserstein distance,
hence the right-hand side converges to zero as $k$ tends to infinity. Finally,

$\displaystyle\big{|}W^{2}_{2}\big{(}\delta^{k}(p_{1},\ldots,p_{k}),\delta^{k}(x_{1},\ldots,x_{k})\big{)}-W^{2}_{2}\big{(}\nu,\delta^{k}(x_{1},\ldots,x_{k})\big{)}\big{|}$
$\displaystyle\qquad\leq\big{(}W_{2}(\delta^{k}(p_{1},\ldots,p_{k}),\delta^{k}(x_{1},\ldots,x_{k}))+W_{2}\big{(}\nu,\delta^{k}(x_{1},\ldots,x_{k})\big{)}\big{)}W_{2}\big{(}\delta^{k}(p_{1},\ldots,p_{k}),\nu\big{)}$
$\displaystyle\qquad\leq\big{(}2W_{2}\big{(}\delta^{k}(p_{1},\ldots,p_{k}),\delta^{k}(x_{1},\ldots,x_{k})\big{)}+o(1)\big{)}W_{2}(\delta^{k}(p_{1},\ldots,p_{k}),\nu)$
$\displaystyle\qquad\leq\big{(}2\frac{1}{k}\sum
d(x_{i},p_{i})^{2}+o(1)\big{)}W_{2}\big{(}\delta^{k}(p_{1},\ldots,p_{k}),\nu\big{)}$
$\displaystyle\qquad\leq\big{(}C(M)+o(1)\big{)}W_{2}\big{(}\delta^{k}(p_{1},\ldots,p_{k}),\nu\big{)},$

since compactness implies the diameter is bounded. This concludes the proof.∎

######  Claim 8.6.

Let $F:S_{n^{d}}\rightarrow(0,\infty)$. Then

$\frac{1}{n^{d+1}}\log\sup_{\sigma}F(\sigma)=\frac{1}{n^{d+1}}\log\sum_{\sigma}F(\sigma)+o(1).$

###### Proof.

Of course,

$\frac{1}{n^{d+1}}\log\sup_{\sigma}F(\sigma)\leq\frac{1}{n^{d+1}}\log\sum_{\sigma}F(\sigma).$

Conversely,

$\frac{1}{n^{d+1}}\log\sum_{\sigma}F(\sigma)\leq\frac{1}{n^{d+1}}\log
n^{d}\sup_{\sigma}F(\sigma).$

and by Stirling $\frac{1}{n^{d+1}}\log n^{d}=o(1)$. ∎

######  Claim 8.7.

$-\frac{1}{n}\log\phi^{(n)}_{i}(x)=d(p_{i},x)^{2}+o(1)$.

###### Proof.

By definition,

$d(p_{i},x)^{2}=\inf_{m\in\mathbb{Z}^{d}}|x-p_{i}-m|^{2}.$

Now, of course,

$\frac{1}{n}\log\phi^{(n)}_{i}(x)=\frac{1}{n}\log\sum_{m\in\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}\geq\frac{1}{n}\log\sup_{m\in\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}=-d(p_{i},x)^{2}.$

Conversely, for every $\epsilon>0$ there exists $C,R>0$ such that

$\sum_{m\in\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}\leq\sum_{m\in
B_{R}(0)\cap\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}+\epsilon\leq C\sum_{m\in
B_{R}(0)\cap\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}.$

Assuming, without loss of generality, that
$\sup_{m\in\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}$ is obtained in $B_{R}(0)$, we
have

$\sum_{m\in B_{R}(0)\cap\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}\leq
CR^{d}\sup_{m\in\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}},$

so

$\displaystyle\frac{1}{n}\log\phi^{(n)}_{i}(x)$
$\displaystyle=\frac{1}{n}\log\sum_{m\in\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}$
$\displaystyle\leq\frac{1}{n}\log C+\frac{1}{n}\log\sup_{m\in
B_{R}(0)\cap\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}$ $\displaystyle\leq
o(1)+\frac{1}{n}\log CR^{d}\sup_{m\in\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}$
$\displaystyle=o(1)+\frac{1}{n}\log\sup_{m\in\mathbb{Z}^{d}}e^{-n|x-p_{i}-m|^{2}}$
$\displaystyle=o(1)-d(p_{i},x)^{2},$

where $o(1)$ depends on $R$, but goes to zero as $n$ tends to infinity (for
$R$ fixed). Letting $n$ tend to infinity concludes the proof. ∎

Finally, we obtain the following theorem due to Berman [5, Theorem 1.1] and
Hultgren [18, Theorem 3.2].

######  Theorem 8.8.

For both (40) and (41), LDP$(\Gamma_{\beta,n},n^{d})$ with rate function
$G_{\beta,\mu_{0},dx}$. The set $G_{\beta,\mu_{0},dx}^{-1}(0)$ is a singleton
precisely when (34) has a unique solution.

###### Proof.

The first statement follows from Lemmas 8.1 and 8.4. The second statement
follows from Proposition 7.16. ∎

###  8.2 An alternative proof—zero temperature approach

We were lucky enough to find finite-dimensional approximations to the main
functional we were interested in (for all $\beta$ at once). Here is an
alternative approach, due to Berman in the permanental/Monge–Ampère setting,
which allows to ‘reverse engineer’ the main functional by computing the limit
of the moment generating functions when $\beta=\beta_{n}=n\rightarrow\infty$.
This is an easier task because in this “zero-temprature limit” the entropy
contribution disappears. This is a standard method in the field and its
benefit in this setting is that when writing out the moment generating
functions explicitly, the symmetry in the Hamiltonians can be exploited to
reduce much of the complexity. Once an explicit formula for the limit is
attained [5, Proposition 5.3], [18, Lemma 3.8], the Gärtner–Ellis Theorem can
be invoked to deduce an LDP for this “zero-temperature” case (stated as a part
of Theorem 1.1 in Berman’s paper [5] and as Theorem 3.6 in Hultgren’s article
[18]). This LDP can then be used to deduce Lemma 8.4 above (corresponding to
Lemma 4.9 in [5] and Lemma 3.14 in [18]), after which Theorem 8.8 is proved as
in the previous section. This original approach of Berman and Hultgren to
proving Theorem 8.8 also can be made to work in the case we are no longer on
the torus, but rather on a non-compact manifold, as in the toric setting. The
reason we chose the proof we presented above is that we found it slightly more
pedagogical to directly deal with all $\beta$ at once and avoid this extra use
of the Gartner–Ellis theorem.

We will now explain the main part of the alternative argument for Theorem 8.8,
that as just mentioned, was the original proof. Namely, how to prove the LDP
when $\beta=\beta_{k}=k\rightarrow\infty$. Here is the main observation:

######  Lemma 8.9.

Let $H_{n}:X^{n^{d}}\rightarrow\mathbb{R}$ be given by (40) or (41). Set

$\Gamma_{n,n}:=\delta^{n^{d}}_{\\#}\Big{(}e^{-nH_{n}}\mu_{0}^{\otimes{n^{d}}}\Big{)}\Big{/}Z_{n,n}\in
P(P(X)).$

Then LDP$(\Gamma_{n,n},n^{d+1})$ with rate function $W_{2}^{2}(dx,\,\cdot\,)$.

###### Proof.

This time, we can use Theorem 4.1. By Claim 8.10 below,
$\lim\frac{1}{n^{d+1}}\log Z_{n,n}=0$. Thus, assuming (40), the moment
generating function simplifies as follows,

$\displaystyle p(\theta)$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{P(X)}e^{n^{d+1}\langle\theta,\nu\rangle}\Gamma_{n,n}(\nu)$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}e^{n^{d+1}\langle\theta,\delta^{n^{d}}(\,\cdot\,)\rangle}\Big{(}e^{-nH_{n}}\mu_{0}^{\otimes
n^{d}}\Big{)}$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}e^{n^{d+1}\langle\theta,\delta^{n^{d}}(x_{1},\ldots,x_{n^{d}})\rangle}e^{-nH_{n}(x_{1},\ldots,x_{n^{d}})}\mu_{0}(x_{1})\otimes\cdots\mu_{0}(x_{n^{d}})$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}e^{n^{d+1}n^{-d}\sum_{i=1}^{n^{d}}\theta(x_{i})}e^{-nH_{n}(x_{1},\ldots,x_{n^{d}})}\mu_{0}(x_{1})\otimes\cdots\mu_{0}(x_{n^{d}})$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}e^{n\sum_{i=1}^{n^{d}}\theta(x_{i})}\sum_{\sigma}\prod\phi^{(n)}_{i}(x_{\sigma(i)})\mu_{0}(x_{1})\otimes\cdots\mu_{0}(x_{n^{d}})$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}\sum_{\sigma}\prod\Big{[}e^{n\theta(x_{\sigma(i)})}\phi^{(n)}_{i}(x_{\sigma(i)})\Big{]}\mu_{0}(x_{1})\otimes\cdots\mu_{0}(x_{n^{d}})$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}n^{d}!\prod\Big{[}e^{n\theta(x_{i})}\phi^{(n)}_{i}(x_{i})\Big{]}\mu_{0}(x_{1})\otimes\cdots\mu_{0}(x_{n^{d}})$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}\prod\Big{[}e^{n\theta(x_{i})}\phi^{(n)}_{i}(x_{i})\Big{]}\mu_{0}(x_{1})\otimes\cdots\mu_{0}(x_{n^{d}})$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\prod\Big{[}\int_{X}e^{n\theta}\phi^{(n)}_{i}\mu_{0}\Big{]}$
$\displaystyle=\lim\frac{1}{n^{d}}\sum_{i=1}^{n^{d}}\frac{1}{n}\log\Big{[}\int_{X}e^{n\theta}\phi^{(n)}_{i}\mu_{0}\Big{]}.$

By Claim 8.7, $-\frac{1}{n}\log\phi^{(n)}_{i}(x)=d(p_{i},x)^{2}+o(1)$. and by
Claim 8.13 below we thus have

$\displaystyle p(\theta)$
$\displaystyle=\lim\frac{1}{n^{d}}\sum_{i=1}^{n^{d}}\big{[}(-\theta)^{\star}(p_{i})+o(1)\big{]}=\lim\big{\langle}\delta^{n^{d}}(p_{1},\ldots,p_{n^{d}}),(-\theta)^{\star}\big{\rangle}=\int_{X}((-\theta)^{\star}dx,$

since $\delta^{k}(p_{1},\ldots,p_{k})\rightarrow dx$. Thus, by Theorems 4.1
and 7.14 we are done. ∎

######  Claim 8.10.

$\lim\frac{1}{n^{d+1}}\log Z_{n,n}=0$.

In fact, we will give a rate of decay, $\frac{1}{n^{d+1}}\log Z_{n,n}=O(1/n)$.

######  Remark 8.11.

It actually suffices to show that $\lim\frac{1}{n^{d+1}}\log Z_{n,n}$
exists—it then must be zero: by Theorem 4.1, once we have a large deviation
principle and we know that the rate function is $W_{2}^{2}(dx,\,\cdot\,)$ up
to a constant, then we can determine that constant by the fact that the
infimum of the rate function must be zero (Remark 3.5). Since $\inf
W_{2}^{2}(dx,\,\cdot\,)=0$ (attained for $dx$), we get the constant must be
zero. At any rate, we will prove Claim 8.10 directly.

######  Remark 8.12.

In fact, here is a quick proof: $\lim_{n}\frac{1}{n^{d+1}}\log Z_{n,n}=p(0)$,
which, by the previous computation, equals $\int 0^{\star}=0$.

###### Proof.

We compute,

$\displaystyle\lim\frac{1}{n^{d+1}}\log Z_{n,n}$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}\operatorname{per}[\phi^{(n)}_{i}(x_{j})]\mu_{0}^{\otimes
n^{d}}$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}\sum_{\sigma}\prod_{i=1}^{n^{d}}\phi^{(n)}_{i}(x_{\sigma(i)})\mu_{0}(x_{1})\otimes\cdots\mu_{0}(x_{n^{d}})$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}\sum_{\sigma}\prod_{i=1}^{n^{d}}\phi^{(n)}_{i}(x_{i})\mu_{0}(x_{1})\otimes\cdots\mu_{0}(x_{n^{d}})$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}n^{d}!\prod\phi^{(n)}_{i}(x_{i})\mu_{0}(x_{1})\otimes\cdots\mu_{0}(x_{n^{d}})$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\int_{X^{n^{d}}}\prod\phi^{(n)}_{i}(x_{i})\mu_{0}(x_{1})\otimes\cdots\mu_{0}(x_{n^{d}})$
$\displaystyle=\lim\frac{1}{n^{d+1}}\log\prod\int_{X}\phi^{(n)}_{i}\mu_{0}$
$\displaystyle=\lim\frac{1}{n^{d}}\sum_{i=1}^{n^{d}}\frac{1}{n}\log||\phi^{(n)}_{i}||_{L^{1}(\mu_{0})}\leq
C_{n},$

where $C_{n}:=\sup_{i=1,\ldots
n^{d}}\frac{1}{n}\log||\phi^{(n)}_{i}||_{L^{1}(\mu_{0})}$. Now, it remains to
estimate $C_{n}$. By Claim 8.7,
$-\frac{1}{n}\log\phi^{(n)}_{i}(x)=d(p_{i},x)^{2}+o(1)$, so

$\displaystyle\frac{1}{n}\log||\phi^{(n)}_{i}||_{L^{1}(\mu_{0})}$
$\displaystyle\leq\frac{1}{n}\log||e^{-n(d(p_{i},x)^{2}+o(1))}||_{L^{1}(\mu_{0})}=O(1/n).$

Since $i$ was arbitrary, $C_{n}=O(1/n)$ and we are done. ∎

######  Claim 8.13.

$\lim_{k\rightarrow\infty}\frac{1}{k}\log\int
e^{k(d(x,y)^{2}-f(x))}dx=f^{\star}(y)$.

###### Proof.

Of course,
$\lim_{k\rightarrow\infty}||F||_{L^{k}(X,\mu)}=||F||_{L^{\infty}(X)}$ for
continuous $F$ and compact $X$ and probability $\mu$. By definition,
$\sup_{x}[d(x,y)^{2}-f(x)]=f^{\star}(y)$. So,

$\displaystyle\lim_{k\rightarrow\infty}\frac{1}{k}\log\int
e^{k(d(x,y)^{2}-f(x))}dx$
$\displaystyle=\lim_{k\rightarrow\infty}\log||e^{d(x,y)^{2}-f(x)}||_{L^{k}(dx)}$
$\displaystyle=\log||e^{d(x,y)^{2}-f(x)}||_{L^{\infty}}$
$\displaystyle=||d(x,y)^{2}-f(x)||_{L^{\infty}}$ $\displaystyle=f^{\star}(y),$

as desired. ∎

The alternative proof of Theorem 8.8 (that is actually the original proof in
[18]) is now a consequence. The point is that once we know there is a large
deviation principle for $\beta\rightarrow\infty$ we can use Proposition 6.1
and Sanov’s Corollary 4.3 to deduce the convergence in Lemma 8.4 in an
argument which provide a formal converse of Lemma 8.1 above, valid in the
$\beta\rightarrow\infty$ case (see Lemma 4.9 in [5] or the proof of Theorem
3.2 in [18]). After that we get the LDP in Theorem 8.8 by applying Lemma 8.4
as above.

## Acknowledgments

Many thanks to R. Berman, J. Hultgren, O. Zeitouni, and S. Zelditch for many
discussions on these topics and to them and to the referees for many detailed
comments/corrections on this manuscript, to them and I. Cheltsov for the
encouragement to write these notes, and to J. Hultgren also for enlightening
lectures at UMD on [18] in September 2017. Finally, it is a real privilege to
dedicate this article to Steve Zelditch whose theorems and vision have been
nothing short of pioneering both in complex geometry and in its relations to
probability and microlocal analysis, and whose guidance, generosity, and
encouragement have been invaluable in my own pursuits over the years. This
work was supported by NSF grants DMS-1515703,1906370, and a Sloan Research
Fellowship.

## References

  * [1]
  * [2] L. Ambrosio, N. Gigli, A user’s guide to optimal transport, version downloaded in 2011 from https://cvgmt.sns.it/paper/195/
  * [3] D. Bakry, L’hypercontractivité et son utilisation en théorie des semigroupes, in Lectures on Probability Theory (Saint-Flour, 1992), Lecture Notes in Math. 1581, 1994, pp. 1–114.
  * [4] D. Bakry and M. Ledoux, Sobolev inequalities and Myers’s diameter theorem for an abstract Markov generator, Duke Math. J. 85 (1996), 253–270.
  * [5] R. Berman, Statistical mechanics of permanents, real Monge–Amper̀e equations and optimal transport, preprint, arxiv:1302.4045.
  * [6] R. Berman, Large deviations for Gibbs measures with singular Hamiltonians and emergence of Kähler–Einstein metrics, Comm. Math. Phys. 354 (2017), 1133–1172.
  * [7] K.L. Chung, Green, Brown, and Probability and Brownian motion on the line, World Scientific, 2002.
  * [8] F. Delarue, Probabilistic approach to regularity, in: Complex Monge–Ampère equations and geodesics in the space of Kähler metrics (V. Guedj, Ed.), Lecture Notes in Math. 2038, 2011, pp. 55–198.
  * [9] A. Dembo, O. Zeitouni, Large deviation techniques and applications, 2nd Ed., Springer, 1998.
  * [10] S.K. Donaldson, Scalar curvature and projective embeddings I, J. Differential Geom. 59 (2001), 479–522.
  * [11] R.S. Ellis, K. Haven, B. Turkington, Large Deviation Principles and complete equivalence and nonequivalence results for pure and mixed ensembles, J. Statist. Phys. 101 (2000), 999–1064.
  * [12] R. Feng, S. Zelditch, Large deviations for zeros of $P(\phi)_{2}$ random polynomials, J. Stat. Phys. 143 (2011), 619–635.
  * [13] B. Gaveau, Méthodes de contrôle optimale en analyse complexe. I. Résolution d’équations de Monge–Ampère, J. Functional Anal. 25 (1977), 391–411.
  * [14] B. Gaveau, Méthodes de contrôle optimale en analyse complexe. II. Équation de Monge–Ampère dans certains domaines faiblement pseudoconvexes, Bull. Soc. Math. France 102 (1978), 101–128.
  * [15] B. Gaveau, Méthodes de contrôle optimale en analyse complexe ou réelle. III. Diffusion d’équations des fonctions plurisousharmoniques ou convexes, J. Functional Anal. 32 (1979), 228–253.
  * [16] L. Gross, Logarithmic Sobolev inequalities, Amer. J. Math. 97 (1976), 1061–1083.
  * [17] J. Hultgren, Real and complex Monge–Ampère equations, statistical mechanics and canonical metrics, Ph.D. Thesis, Chalmers University of Technology and University of Gothenburg, 2018.
  * [18] J. Hultgren, Permanental Point Processes on Real Tori, Theta Functions and Monge–Ampére Equations, Annales Fac. sci. Toulouse: Mathḿatiques 28 (2019), 11–65.
  * [19] T. Jeffres, R. Mazzeo, Y.A. Rubinstein, Kahler-Einstein metrics with edge singularities, (with an appendix by C. Li and Y.A. Rubinstein), Annals of Math. 183 (2016), 95–176.
  * [20] I. Karatzas, S.E. Shreve, Brownian motion and Stochastic Calculus (2nd Ed.), Springer, 1991.
  * [21] N.V. Krylov, Nonlinear elliptic and parabolic equations of the second order, D. Reidel Publishing, 1987.
  * [22] N.V. Krlylov, Smoothness of the payoff function for a controllable diffusion process in a domain, Izv. Akad. Nauk SSSR Ser. Mat. 53 (1989), 66–96; translation in Math. USSR-Izv. 34 (1990), 65–95.
  * [23] N.V. Krylov, Moment estimates for the quasiderivatives, with respect to the initial data, of solutions of stochastic equations and their application, Math. USSR-Sb. 64 (1989), 505–526.
  * [24] N.V. Krylov,On control of diffusion processes on a surface in Euclidean space. Math. USSR-Sb. 65 (1990), 185–203.
  * [25] D.H. Phong, J. Sturm, The Monge–Ampère operator and geodesics in the space of Kähler potentials, Invent. Math. 166 (2006), 125–149.
  * [26] F. Rassoul-Agha, T. Seppäläinen, A Course on Large Deviations with an Introduction to Gibbs Measures, Amer. Math. Soc., 2015.
  * [27] J. Rauch, B.A. Taylor, The Dirichlet problem for the multidimensional Monge-Ampère equation, Rocky Mountain J. Math. 7 (1977), 345–364.
  * [28] R. T. Rockafellar, Convex analysis, Princeton University Press, 1970.
  * [29] Y.A. Rubinstein, Some discretizations of geometric evolution equations and the Ricci iteration on the space of Kähler metrics, Adv. Math. 218 (2008), 1526–1565.
  * [30] Y.A. Rubinstein, Smooth and singular Kähler–Einstein metrics, in: Geometric and Spectral Analysis, (P. Albin et al., Eds.), Contemp. Math. 630, Amer. Math. Soc. and Centre de Recherches Mathématiques, 2014, pp. 45–138.
  * [31] J. Song, S. Zelditch, Test configurations, large deviations and geodesic rays on toric varieties, Adv. Math. 229 (2012), 2338–2378.
  * [32] C. Villani, Topics in optimal transportation, Amer. Math. Soc., 2003.
  * [33] C. Villani, Optimal transport, Springer, 2009.
  * [34] O. Zeitouni, S. Zelditch, Large deviations of empirical measures of zeros of random polynomials, Int. Math. Res. Not. (2010) 3935–3992.
  * [35] S. Zelditch, Large deviations of empirical measures of zeros on Riemann surfaces. Int. Math. Res. Not. (2013), 592–664
  * [36] S. Zelditch, Eigenfunctions of the Laplacian on a Riemannian Manifold, Amer. Math. Soc., 2017.

University of Maryland

<EMAIL_ADDRESS>