# Grid entropy in a ”choose the best of $D$ samples” model

Alexandru Gatea

Department of Mathematics, University of Toronto
<EMAIL_ADDRESS>
###### Abstract

Grid entropy is a deterministic quantity inherent to lattice models which
captures the entropy of empirical measures along paths that converge weakly to
a given target measure. In this paper, we study the limiting behaviour of
empirical measures in a model consisting of repeatedly taking $D$ samples from
a distribution and picking out one according to an omniscient ”strategy.” We
show that the set of limit points of empirical measures is almost surely the
same whether or not we restrict ourselves to strategies which make the choices
independently of all past and future choices, and furthermore, that this set
coincides with the set of measures with finite grid entropy. This set is
convex and weakly compact; we characterize its extreme points as those given
by a natural ”greedy” deterministic strategy and we compute the grid entropy
of said extreme points to be 0. This yields a description of the set of limit
points of empirical measures as the closed convex hull of measures given by a
density which is $D\cdot Beta(1,D)$ distributed. We also derive a simplified
version of a grid entropy-based variational formula for Gibbs Free Energy for
this model, and we present the dual formula for grid entropy.

###### Contents

  1. 1 Introduction
  2. 2 Definitions and Results
  3. 3 Preliminaries
    1. 3.1 More on Strategies
    2. 3.2 Coupling the Edge Weights with I.I.D. Uniforms
    3. 3.3 Grid Entropy
    4. 3.4 Measure-Preserving Bijections in ${\mathbb{R}}^{n}$
  4. 4 Reducing the Problem
    1. 4.1 Expected Value of Empirical Measures
    2. 4.2 What Happens with Independent Strategies
  5. 5 Single-Edge Strategies Revisited
    1. 5.1 Single-Edge Strategies in Terms of Conditional Probabilities
    2. 5.2 ”Consistent” Single-Edge Strategies
    3. 5.3 Closure of $\\{\sigma_{\vec{p}}\\}$
  6. 6 Extreme Points of $\\{\sigma_{\vec{p}}\\}$
    1. 6.1 Deterministic Single-Edge Strategies
    2. 6.2 ”Weight Tuples” of Single-Edge Strategies
    3. 6.3 ”Weight Tuples” of the Extreme Points
    4. 6.4 Theorem 13
    5. 6.5 The Discrete Case with Example
  7. 7 Grid Entropy in this Model
    1. 7.1 Grid Entropy of Extreme Points
    2. 7.2 Grid Entropy via Gibbs Free Energy
  8. 8 Next Steps
  9. 9 Acknowledgments

##  1 Introduction

Random sampling is a fundamental area of study in statistics. Countless
processes can be simulated as Monte Carlo experiments, with far-reaching
applications in a range of fields from biology and economics to business. A
rather simple but ubiquitous and surprisingly non-trivial experiment is that
of taking $D$ samples from a distribution and picking out one of these samples
according to some omniscient ”strategy.”

This problem is dual to K-means clustering, a well-studied process where one
groups a large set of samples into a fixed $K$ number of buckets in order to
minimize an error function called the quadratic distortion (see [LP20] for
state-of-the-art).

We frame our model in the realm of percolation theory and ask what is the
limiting behaviour of empirical measures along the event-dependent path of
choices. Answering this question provides a gold mine of information about the
model - normalized passage time along a path, after all, is just the identity
function integrated against the path’s empirical measure.

Recent efforts have gone into better understanding the weak convergence of
empirical measures. Some, such as [Rie21] and [Lei20], establish upper bounds
on the rate of Wasserstein convergence of empirical measures to the Markov
invariant measure/i.i.d. measure respectively they are sampled from. Others
focus on describing the limits of empirical measures.

In [Bat20], Bates shows that the set $\mathcal{R}$ of limit points of
normalized empirical measures along paths in a generic lattice model is
deterministic and derives an explicit variational formula for the limit shape
of first passage time as the minimum value of a linear functional over this
deterministic set.

In [Gat22], this author builds on Bates’ paper by developing the notion of
grid entropy, a deterministic quantity capturing not just whether a certain
target measure is a limit point of empirical measures. Grid entropy has
previously appeared in [RAS14]. [Gat22] proposes a novel approach, realizing
grid entropy both as a subadditive limit of entropies of paths with empirical
measure within an $\epsilon$-Levy-Prokhorov distance of the target measure,
and as the critical exponent of canonical order statistics associated with the
Levy-Prokhorov metric, something a priori only known for i.i.d. Bernoulli$p)$
edge labels (see [Car10]). Though using different approaches, both this author
and Rassoul-Agha et al establish the same convex duality between grid entropy
and Gibbs Free Energy. Furthermore, this author observes that Bates’ set
$\mathcal{R}$ almost surely coincides with the set of probability measures
with finite grid entropy:

$\mathcal{R}=\\{\nu\ \mbox{prob meas}:||\nu||>-\infty\\}\ \mbox{a.s.}$

One limitation of [Gat22] is that only empirical measures along deterministic
or polymer paths are considered, rather than allowing for arbitrary mixtures
of paths. Even in [Bat20], the focus is mainly on empirical measures along
geodesics. In this paper, we seek to rectify this by studying empirical
measures along _random_ paths (picked according to some probabilistic
”strategy,” which may or may not yield geodesics or polymer paths). We will
show that $\mathcal{R}$ is still the set of limit points, whether or not we
assume the strategy is omniscient.

Another deficiency is that grid entropy and the set $\mathcal{R}$, like limit
shape and other quantities in this area, are not known to be explicitly
computable in most cases. One noteworthy exception is the paper [MSZ21] by
Martin, in which an explicit formula for the weak limits of empirical measures
along geodesics is derived in the solvable Exponential LPP on
${\mathbb{Z}}^{2}$ model. Also, in [Bat20] it is established that replacing
the lattice ${\mathbb{Z}}^{D}$ by the infinite complete $D$-ary tree
$\mathcal{T}_{D}$, the set $\mathcal{R}$ can be precisely described as a
specific sublevel of relative entropy (in terms of $D$).

The $D$-ary tree is in a way the dual model to the one we explore in this
paper, and as one might expect, we will be able to give a description of
$\mathcal{R}$ in our setting too. We will precisely characterize the extreme
points of $\mathcal{R}$ as those measures whose density is $D\cdot Beta(1,D)$
distributed; $\mathcal{R}$ is then the closed convex hull of these measures.

In addition, we compute the grid entropy of the extreme points of
$\mathcal{R}$ to be 0, and we give a simplification of a general formula for
grid entropy from [Gat22] for this model.

##  2 Definitions and Results

Let us be more precise about our setup and goals. We consider vertices on
${\mathbb{Z}}_{\geq 0}$, $D$ parallel edges $(e_{i}^{1},\ldots,e_{i}^{D})$ for
every $i\geq 0$, and an i.i.d. array of edge labels $U_{i}^{j}\sim$ Unif[0,1].
We denote by $\Lambda$ the Lebesgue measure on $[0,1]$.

It is convenient to work on the compact space $\mathcal{M}_{1}$ of probability
measures on [0,1], and as we will explain in Section 3.2 we do not lose any
generality by restricting to this setting.

$e_{0}^{2}$$e_{0}^{1}$$e_{0}^{3}$$e_{1}^{2}$$e_{1}^{1}$$e_{1}^{3}$$0$$1$$2$

Next, we wish to formalize the notion of strategies. These will be probability
measures on the product space coupling the environment $(U_{i}^{j})_{i\geq
0,1\leq j\leq D}$ with the infinite target sequence of indices of the $U_{i}$
corresponding to the choices $(X_{i})_{i\geq 0}$.

######  Definition.

A strategy is a probability measure $\chi$ on the product space
$([0,1]^{D})^{{\mathbb{Z}}_{\geq 0}}\times\\{1,\ldots,D\\}^{{\mathbb{Z}}_{\geq
0}}$ s.t. the marginal distribution of the first coordinate (the environment
$(U_{i}^{j})\in([0,1]^{D})^{{\mathbb{Z}}_{\geq 0}}$) is a sequence of i.i.d.
Unif[0,1].

We denote by $(J_{i})_{i\geq 0}$ the second coordinate (a random sequence of
indices) and define the random vector of choices

$(X_{0}(\chi),X_{1}(\chi),\ldots):=(U_{0}^{J_{0}},U_{1}^{J_{1}},\ldots)$

Denote by $\frac{1}{n}\mu_{0\rightarrow n}(\chi)$ the empirical measures of
this vector:

$\frac{1}{n}\mu_{0\rightarrow
n}(\chi)=\frac{1}{n}\sum\limits_{i=0}^{n-1}\delta_{X_{i}(\chi)}\in\mathcal{M}_{1}$

Also, let $\sigma_{\chi}^{i}$ be the law of $X_{i}(\chi)$.

######  Remark.

If $\chi$ conditioned on the environment is a delta mass for a.a. environments
$(U_{i}^{j})$ with respect to the product measure $(\Lambda^{\times
D})_{\infty}$, it means that the strategy picks exactly one sequence
$(x_{i})_{i\geq 0}$ for each set of observed labels. In other words, the
strategy is deterministic.

######  Definition.

We also define (strategy-free) empirical measures along a fixed path
$\pi:0\rightarrow n$ consisting of edges
$(e_{0}^{j_{0}},\ldots,e_{n-1}^{j_{n-1}})$ by

$\frac{1}{n}\mu_{\pi}=\frac{1}{n}\sum_{i=0}^{n-1}\delta_{U_{i}^{j_{i}}}$

An important type of strategy is one which chooses each $X_{k}$ independent of
$(U_{i}^{j})_{i\neq k,1\leq j\leq D}$, the observed values from all but the
$k$th trial. These are $\chi$ which are infinite products of measures arising
from ”single-edge strategies,” i.e. micro-strategies operating at the
individual trial level. We call such $\chi$ ”independent strategies,” as they
give rise to independent $X_{i}$.

######  Definition.

A single-edge strategy is a probability measure $\psi$ on the product space
$([0,1]^{D})\times\\{1,\ldots,D\\}$ s.t. the marginal distribution of the
first coordinate $(U^{j})_{1\leq j\leq D}$ is a sequence of $D$ i.i.d.
Unif[0,1]. We denote by $J$ the second coordinate (a random index) and define
the random choice

$X(\psi):=U^{J}$

Also, let $\sigma_{\psi}$ be the law of $X(\psi)$.

######  Remark.

If $\psi$ conditioned on $(U^{j})_{1\leq j\leq D}$ is a delta mass for a.a.
$(u^{j})_{1\leq j\leq D}$ with respect to the product measure $\Lambda^{\times
D}$, it means that the single-edge strategy picks exactly one sequence $x$ for
each set of $D$ observed labels, so $\psi$ is deterministic.

A single-edge strategy $\psi$ is completely determined by the
$\psi$-conditional probabilities
$p_{k}:[0,1]^{D}\rightarrow[0,1]$, $1\leq k\leq D$ defined as

$p_{k}(u_{1},\ldots,u_{D}):=P_{\psi}[J=k\mid(U^{j})_{1\leq j\leq
D}=(u^{j})_{1\leq j\leq D}]$

We expand on this in more detail in Section 5.1. The key takeaway is that we
may interchangeably refer to both $\psi$ and $\vec{p}$ as a single-edge
strategy, and therefore we define
$X(\vec{p}):=X(\psi),\sigma_{\vec{p}}:=\sigma_{\psi}$.

In this paper we are interested in the weak limit points of
$\frac{1}{n}\mu_{0\rightarrow n}(\chi)$. As it turns out, this set of limit
points almost surely coincides with the set of limit points of
$\frac{1}{n}\mu_{0\rightarrow n}(\chi)$ over independent strategies $\chi$
only, with the distributions $\sigma_{\vec{p}}$ over single-edge strategies
$\vec{p}$, as well as with the set $\mathcal{R}$ of probability measures with
finite grid entropy. The following theorem is the main objective of Section 4
.

######  Theorem A.

A.s. we have

$\displaystyle\mathcal{R}$ $\displaystyle=\bigg{\\{}\mbox{limit pts of}\
\frac{1}{n}\mu_{0\rightarrow n}(\chi):\mbox{strategies}\ \chi\bigg{\\}}$
$\displaystyle=\bigg{\\{}\mbox{limit pts of}\ \frac{1}{n}\mu_{0\rightarrow
n}(\chi):\mbox{independent strategies}\ \chi\bigg{\\}}$
$\displaystyle=\bigg{\\{}\sigma_{\vec{p}}:\mbox{single-edge strategies}\
\vec{p}\bigg{\\}}$

This reduces the problem to working with single-edge strategies $\vec{p}$,
which are simpler to handle than generic strategies. Moreover, every
$\sigma_{\vec{p}}$ can be achieved by a ”consistent” single-edge strategy
$\vec{p}$ with the properties that $p_{1}(\vec{u})$ is invariant under
1-fixing permutations in $S_{D}$ and
$p_{k}(\vec{u})=p_{1}(u_{D-k+2},\ldots,u_{1},\ldots,u_{D-k+1})\ \forall k$.

Now, the sets from Theorem A are convex and weakly compact. In Section 6 we
fully characterize their extreme points.

######  Theorem B.

Let $\vec{p}$ be a single-edge strategy. The following are equivalent:

  1. (i)

$\sigma_{\vec{p}}$ is an extreme point

  2. (ii)

Any consistent single-edge strategy achieving $\sigma_{\vec{p}}$ must be
deterministic.

  3. (iii)

$\sigma_{\vec{p}}$ has a density $f_{\vec{p}}$ which is not constant on sets
of positive $\Lambda$-measure and $\sigma_{\vec{p}}$ is given by the following
single-edge strategy $\vec{q}$:

$q_{k}(u_{1},\ldots,u_{D})=\textbf{1}_{\\{f_{\vec{p}}(u_{k})\geq
f_{\vec{p}}(u_{i})\ \forall i\\}}\ \mbox{for $\Lambda^{\times D}$-a.a.}\
(u_{1},\ldots,u_{D})$

In other words, $\sigma_{\vec{p}}$ is achieved by the deterministic greedy
single-edge strategy ”choose whichever label yields a higher value when
evaluating the density $f_{\vec{p}}$.”

  4. (iv)

$\sigma_{\vec{p}}$ has a density $f_{\vec{p}}$ s.t.
$\frac{1}{D}f_{\vec{p}}(Unif[0,1])\sim\mbox{Beta}(1,D)$.

As an immediate corollary, $\mathcal{R}$ is the closed convex hull of these
measures.

######  Remark.

It is important to stress that Theorem B holds even in a more general setting
where the i.i.d. labels $U_{i}^{j}$ follow some finite mean distribution on
$\mathcal{R}$ that is not necessarily Unif[0,1]. The only caveat is that the
value distribution of the densities $f_{\vec{p}}$ of extreme points might not
have as explicit a form as $D\cdot Beta(1,D$); however, the value distribution
of the densities $f_{\vec{p}}$ is still identical to the value distribution of
$f_{MAX}$, whatever that may be.

######  Remark.

In fact, Theorem B holds in a discrete setting as well. If the i.i.d. labels
$U^{j}$ are Unif$\\{1,\ldots,K\\}$ then the convex set of consistent single-
edge strategies forms a permutohedron of order $K$.

Figure 1: Permutohedron of order 4, [Hol]

The following is the discrete analogue of Theorem B.

######  Theorem B’.

Let $\vec{p}$ be a single-edge strategy. The following are equivalent:

  1. (i)

$\sigma_{\vec{p}}$ is an extreme point

  2. (ii)

Any consistent single-edge strategy achieving $\sigma_{\vec{p}}$ must be
deterministic.

  3. (iii)

$\sigma_{\vec{p}}$ is given by the single-edge strategy ”choose whichever
label is maximal with respect to the ordering $\alpha(1)<\cdots<\alpha(K)$”
for some permutation $\alpha\in S_{K}$.

  4. (iv)

$\sigma_{\vec{p}}$ has a probability mass function whose value distribution is

$\bigg{\\{}\frac{1}{K^{D}},\frac{2^{D}-1}{K^{D}},\frac{3^{D}-2^{D}}{K^{D}},\ldots,\frac{K^{D}-(K-1)^{D}}{K^{D}}\bigg{\\}}$

The ordering mentioned in (iii) gives the natural bijection between the
extreme consistent single-edge strategies and the extreme points of the
permutohedron. For example, the extreme point $1342$ corresponds to the
single-edge strategy of choosing the maximal $u^{i}$ according to the ordering
$1<3<4<2$, hence the bijection maps

$1342\mapsto\sigma_{1342}=\frac{1}{4^{D}}\delta_{1}+\frac{2^{D}-1}{4^{D}}\delta_{3}+\frac{3^{D}-2^{D}}{4^{D}}\delta_{4}+\frac{4^{D}-3^{D}}{4^{D}}\delta_{2}$

This bijection extends to a bijection between the entire permutohedron and
$\mathcal{R}$ by taking convex combinations. We walk through an explicit
example of this phenomenon in Section 6.5.

Generally speaking there is no known way of computing grid entropy, however,
it amazingly can be computed to be 0 for these extreme points. This
effectively means that a.s. the number of paths $0\rightarrow n$ with
empirical measures weakly converging to any one of these extreme points is
$e^{o(n)}$.

######  Theorem C.

Let $\sigma_{\vec{p}}$ be an extreme point. Then

$||\sigma_{\vec{p}}||=0$

Whether _every_ measure in $\mathcal{R}$ with grid entropy 0 is an extreme
point remains an open question.

Section 7 focuses on this result, as well as simplified formulas for the Gibbs
Free Energy and grid entropy in this model.

######  Theorem D.

Suppose $\tau:[0,1]\rightarrow{\mathbb{R}}$ is a bounded measurable function.
Then Gibbs Free Energy with respect to $\tau$ is given by

$G(\tau)=E\bigg{[}\log\sum_{j=1}^{D}e^{\tau(U^{j})}\bigg{]}\ \mbox{a.s.}$

where $U^{j}$ are i.i.d. Unif[0,1]. For all probability measures $\nu$, grid
entropy is given by

$-||\nu||=\sup_{\tau}\bigg{[}\langle\tau,\nu\rangle-G(\tau)\bigg{]}=\sup_{\tau}\bigg{[}\langle\tau,\nu\rangle-E\bigg{[}\log\sum_{j=1}^{D}e^{\tau(U^{j})}\bigg{]}\bigg{]}$

where the supremum is over bounded measurable functions
$\tau:[0,1]\rightarrow{\mathbb{R}}$ and where $\langle\tau,\nu\rangle$ denotes
the integral $\int_{0}^{1}\tau(u)d\nu$.

######  Remark.

This theorem actually holds for measurable $\tau$ s.t.
$E[e^{\beta\tau(U)}]<\infty$ for $U\sim Unif[0,1]$ and can easily be extended
to all measurable $\tau$ by truncating $\tau$ in $\langle\tau,\nu\rangle$ at
some $C>0$ and taking a supremum over $C$ of the variational formula. We leave
the details to the reader and focus on the bounded $\tau$ case.

But first we delve deeper into the setup and known relevant results.

##  3 Preliminaries

###  3.1 More on Strategies

We list some miscellaneous observations about strategies.

It is trivial to see that the sets of strategies $\chi$, of single-edge
strategies $\psi$, of distributions $\sigma_{\chi}^{i}$ for strategies $\chi$
and $i\geq 0$, and of $\sigma_{\psi}$ for single-edge strategies $\psi$ are
each closed under convex combinations. The extreme points of the sets of
strategies/single-edge strategies are clearly the sets of deterministic
strategies/single-edge strategies respectively.

Moreover, if $\chi$ is an independent strategy corresponding to a sequence
$(\psi_{i})$ of single-edge strategies then
$\sigma_{\chi}^{i}=\sigma_{\psi_{i}}\ \forall i\geq 0$. In particular, this
implies

$\\{\sigma_{\chi}^{i}:\mbox{independent strategies}\
\chi\\}=\\{\sigma_{\psi}:\mbox{single-edge strategies}\ \psi\\}\ \forall i\geq
0$ (1)

In fact, observe that for any strategy $\chi$ and $i\geq 0$ if we define the
strategy $\chi^{\prime}$ to be the measure determined on product sets by

$\chi^{\prime}(A\times B):=\chi((0\ i)A\times(0\ i)B)\ \forall\
\mbox{measurable}\ A\subseteq([0,1]^{D})^{{\mathbb{Z}}_{\geq
0}},B\subseteq(\\{1,\ldots,D\\})^{{\mathbb{Z}}_{\geq 0}}$

where $(0\ i)C$ swaps the 0th and $i$th coordinates of sequences in $C$, then
this is easily checked to be a strategy with

$\sigma_{\chi}^{i}=\sigma_{\chi^{\prime}}^{0}$

Therefore

$\\{\sigma_{\chi}^{i}:\mbox{strategies}\
\chi\\}=\\{\sigma_{\chi}^{0}:\mbox{strategies}\ \chi\\}\ \forall i\geq 0$ (2)

###  3.2 Coupling the Edge Weights with I.I.D. Uniforms

We briefly explain why we can work in the setting of edge labels
$U_{i}^{j}\sim Unif[0,1]$ without losing generality.

Suppose instead we start with i.i.d. edge weights $(\tau_{i}^{j})_{i\geq
0,1\leq j\leq D}\sim\theta$ for some distribution $\theta$ on ${\mathbb{R}}$
with finite mean. We can then couple the environment to uniform random
variables as is done in [Bat20, Sect. 2.1]. More specifically, we let our the
$\tau_{i}^{j}$ be given by

$\tau_{i}^{j}=\tau(U_{i}^{j})$

for a measurable function $\tau:[0,1]\rightarrow{\mathbb{R}}$ and i.i.d.
$U_{i}^{j}\sim Unif[0,1]$. If we let $F_{\theta}$ be the cumulative
distribution function of $\theta$ then the quantile function

$F_{\theta}^{-}(t):=\inf\\{t\in{\mathbb{R}}:F_{\theta}(t)\geq x\\}$

is an example of such a $\tau$; however, our results hold for any such $\tau$
chosen so we let $\tau$ be arbitrary.

We can move from the simplified $(\Lambda,[0,1])$ setting we wish to work in
to the initial $(\theta,{\mathbb{R}})$ setting by applying the
$\tau$-pushforward.

Now, as mentioned in Theorem A, we show that, in the $(\Lambda,[0,1])$
setting, the set of limit points of the empirical measures
$\frac{1}{n}\mu_{0\rightarrow n}(\chi)$ a.s. coincides with $\mathcal{R}$,
which is shown in 1 to a.s. coincide with the set of limit points of
(strategy-free) empirical measures $\frac{1}{n}\mu_{\pi_{n}}$ along paths
$\pi_{n}:0\rightarrow n$.

We do not lose generality by performing this coupling because a.s.,
$\frac{1}{n_{k}}\mu_{\pi_{n_{k}}}\Rightarrow\nu$ implies
$\tau_{\ast}(\frac{1}{n_{k}}\mu_{\pi_{n_{k}}})\Rightarrow\tau_{\ast}(\nu)$.
This is proved in [Bat20, Lemma 6.15]. In fact, if we take $\tau$ to be the
quantile function and we assume $\theta$ has continuous cdf $F_{\theta}$ then
this implication becomes an if and only if, as seen in [Gat22, Lemma 5].

###  3.3 Grid Entropy

######  Definition.

The Levy-Prokhorov metric on the space $\mathcal{M}_{+}$ of finite non-
negative Borel measures on $[0,1]$ is defined by

$\rho(\mu,\nu)=\inf\\{\epsilon>0:\mu(A)\leq\nu(A^{\epsilon})+\epsilon\
\mbox{and}\ \nu(A)\leq\mu(A^{\epsilon})+\epsilon\ \forall
A\in\mathcal{B}([0,1])\\}$

It is standard that the Levy-Prokhorov metric $\rho$ metrizes weak
convergence. Some elementary properties include that the Levy-Prokhorov metric
is upper bounded by total variation and it satisfies a certain subadditivity:

$\rho(\mu_{1}+\mu_{2},\nu_{1}+\nu_{2})\leq\rho(\mu_{1},\nu_{1})+\rho(\mu_{2},\nu_{2})$

For $t\geq 0$ let $\mathcal{M}_{t}$ denote the space of non-negative Borel
measures on $[0,1]$ with total mass $t$.

In a concurrent paper [Gat22], this author studies not just the convergence of
empirical measures in a lattice model such as ours but the _entropy_ of
empirical measures converging to a certain weak limit.

Three quite different but equivalent definitions of grid entropy are given in
said paper, and they are linked to the original description of this entropy
provided in a 2014 paper [RAS14] by Rassoul-Agha and Seppäläinen. Here we work
with the two most relevant to our needs, coming from [Gat22]. Note that in the
setting of [Gat22], both direction-fixed and direction-free grid entropy are
considered, but in the model we focus on in this paper there is but one unit
direction so we will use the direction-free versions of the results from
[Gat22].

We go into a brief description of this work, as fits our needs in this paper.

Fix any $t\geq 0$ and a target measure $\nu$. We consider the order statistics
of the Levy-Prokhorov distance between $\nu$ and the empirical measures
$\frac{1}{n}\mu_{\pi}$ varying over all $D^{\lfloor nt\rfloor}$ possible
origin-anchored, length $\lfloor nt\rfloor$ paths $\pi$. That is, for every
$n\in{\mathbb{N}}$ we let

$\min_{\pi:0\rightarrow\lfloor
nt\rfloor}^{1}\rho\bigg{(}\frac{1}{n}\mu_{\pi},\nu\bigg{)}\leq\min_{\pi:0\rightarrow\lfloor
nt\rfloor}^{2}\rho\bigg{(}\frac{1}{n}\mu_{\pi},\nu\bigg{)}\leq\ldots\leq\min_{\pi:0\rightarrow\lfloor
nt\rfloor}^{D^{\lfloor
nt\rfloor}}\rho\bigg{(}\frac{1}{n}\mu_{\pi},\nu\bigg{)}$

denote the order statistics value of $\rho(\frac{1}{n}\mu_{\pi},\nu)$. It is
convenient to define

$\min_{\pi:0\rightarrow\lfloor
nt\rfloor}^{j}\rho\bigg{(}\frac{1}{n}\mu_{\pi},\nu\bigg{)}:=+\infty\
\mbox{for}\ j>D^{\lfloor nt\rfloor}$

These order statistics and the paths corresponding to them are of course
event-dependent. However, the following theorem from [Gat22] shows there is a
deterministic critical exponent where the empirical measures along the paths
corresponding to these order statistics change from converging a.s. to $\nu$
to a.s. diverging away from $\nu$. This critical exponent turns out to be
precisely the negative convex conjugate of Gibbs Free Energy. We state the
full theorem as presented in [Gat22], noting that part (i) has been previously
shown in [Car10] to hold in the case of Bernoulli edge labels, and that parts
(ii) and (iv) follow immediately from the earlier work of Rassoul-Agha and
Seppäläinen [RAS14].

######  Theorem 1.

  1.   2. (i)

For any target measure $\nu\in\mathcal{M}$, its grid entropy is defined to be
the deterministic quantity

$\displaystyle||\nu||$ $\displaystyle:=\sup\bigg{\\{}\alpha\geq
0:\lim_{n\rightarrow\infty}\min_{\pi:0\rightarrow\lfloor nt\rfloor}^{\lfloor
e^{\alpha n}\rfloor}\rho\bigg{(}\frac{1}{n}\mu_{\pi},\nu\bigg{)}=0\
\mbox{a.s.}\bigg{\\}}$ $\displaystyle\in\\{-\infty\\}\cup[0,t\log D]$

where the value is $-\infty$ if the set of $\alpha$’s is empty. Then grid
entropy is the critical exponent where the
$\min\limits_{\pi:0\rightarrow\lfloor nt\rfloor}^{\lfloor e^{\alpha
n}\rfloor}\rho(\frac{1}{n}\mu_{\pi},\nu)$ change from converging to 0 to a.s.
having a $\liminf\limits_{n\rightarrow\infty}>0$.
For example, the grid entropy of the original distribution, $\Lambda$, is
maximal:
$||\Lambda||=t\log D$.

  3. (ii)

Grid entropy is positive-homogeneous, satisfies the reverse-triangle
inequality

$||\nu||+||\xi||\leq||\nu+\xi||$

and is concave and upper-semicontinuous in $\nu$.

  4. (iii)

Consider the deterministic, weakly closed set

$\mathcal{R}^{t}:=\\{\nu\in\mathcal{M}:||\nu||\geq 0\\}$

Then $\mathcal{R}^{t}\subseteq\mathcal{M}_{t}$, $\nu\ll\Lambda\
\forall\nu\in\mathcal{R}^{t}$ and

$\mathcal{R}^{t}=\bigg{\\{}\mbox{limit pts of}\ \frac{1}{n}\mu_{\pi}\
\mbox{for}\ \pi:0\rightarrow\lfloor nt\rfloor\bigg{\\}}\ \mbox{a.s.}$

  5. (iv)

Grid entropy is the negative convex conjugate of $\beta$-Gibbs Free Energy.
More concretely, for $\beta>0$,

$-||\nu||=\sup_{\tau}\bigg{[}\beta\langle\tau,\nu\rangle-
G_{t}^{\beta}(\tau)\bigg{]}\ \forall\nu\in\mathcal{M}_{t}$ (3)

where the supremum is taken over bounded measurable
$\tau:[0,1]\rightarrow{\mathbb{R}}$, where
$\langle\tau,\nu\rangle=\int_{0}^{1}\tau(u)d\nu$, where $G_{t}^{\beta}(\tau)$
is the length $t$ $\beta$-Gibbs Free Energy

$G_{t}^{\beta}(\tau):=\lim_{n\rightarrow\infty}\frac{1}{n}\log\sum_{\pi:0\rightarrow\lfloor
nt\rfloor}e^{\beta T(\pi)}$

and where
$T(\pi)=\sum\limits_{e\in\pi}\tau(U_{e})=\langle\tau,\mu_{\pi}\rangle$ is the
passage time along $\pi$.

  6. (v)

Any $\nu\in\mathcal{R}^{t}$ satisfies the following upper bound on the sum of
the grid entropy and the relative entropy with respect to Lebesgue measure on
[0,1]:

$tD_{KL}(\nu||\Lambda)+||\nu||\leq t\log D$

where $D_{KL}$ denotes relative entropy (or Kullback-Leibler divergence).

######  Remark.

An immediate but highly non-trivial consequence of (i) is the existence of
random length $\lfloor nt\rfloor$ paths whose empirical measures converge
weakly to a given target $\nu\in\mathcal{R}^{t}$ a.s.. Indeed, the event-
dependent paths corresponding to $\min\limits_{\pi:0\rightarrow\lfloor
nt\rfloor}^{1}\rho(\frac{1}{n}\mu_{\pi},\nu)$ do the job.

######  Remark.

(i), seen as the statement that the negative convex conjugate of Gibbs Free
Energy is the critical exponent of the order statistics
$\min_{\pi:0\rightarrow\lfloor nt\rfloor}^{j}\rho(\frac{1}{n}\mu_{\pi},\nu)$,
has been previously proved in the case of Bernoulli($p$) edge labels in
[Car10] [Corollary 2].

By positive-homogeneity it suffices to work with the case $t=1$. For the sake
of notation we drop the 1 in $\mathcal{R}^{1},G_{1}^{\beta}(\tau)$ for the
rest of the paper.

Once we determine the extreme points of $\mathcal{R}$, we compute their grid
entropies to be 0. We also give a limit-free formula for the $\beta$-Gibbs
Free Energy $G^{\beta}(\tau)$ in our model, which renders the convex duality
formula (3) more practical.

###  3.4 Measure-Preserving Bijections in ${\mathbb{R}}^{n}$

We will encounter measure-preserving bijections in ${\mathbb{R}}$, so we
briefly outline the required notions in this section.

######  Definition.

Let $\mathcal{B}({\mathbb{R}}^{n})$ denote the Borel $\sigma$-algebra of
${\mathbb{R}}^{n}$ and let $\mu$ be a Borel probability measure on
${\mathbb{R}}^{n}$. Let $A,A^{\prime}\in\mathcal{B}({\mathbb{R}}^{n})$ with
$\mu(A^{\prime})=\mu(A)>0$. A bijection $\phi:A\rightarrow A^{\prime}$ is said
to be $\mu$-measure-preserving if $\mu(B)=\mu(\phi(B))$ for all
$B\in\mathcal{B}({\mathbb{R}}^{n}),B\subseteq A$.

Nishiura proves in [Nis98, Theorem 4] the existence of a $\mu$-measure-
preserving bijection between Borel sets of equal, positive but not full
$\mu$-measure, given that $\mu$ is nonatomic. We will only need the following
simplified version of this theorem.

######  Theorem 2.

Suppose $\theta$ is a Borel probability measure on $[0,1]$ that is absolutely
continuous with respect to Lebesgue measure $\Lambda$ on $[0,1]$. Let
$A,A^{\prime}\in\mathcal{B}([0,1])$ s.t.
$\theta(A)=\theta(A^{\prime})\in(0,1)$. Then there exists a $\theta$-measure-
preserving bijection $\phi:A\rightarrow A^{\prime}$.

Preliminaries finished, our next goal is to show that we may restrict
ourselves to working with single-edge strategies without losing generality.

##  4 Reducing the Problem

Over the course of this section, we prove the following theorem, which allows
us to reduce the problem of describing the set of limit points of the
empirical measures $\frac{1}{n}\mu_{0\rightarrow n}(\chi)$ to characterizing
the set of achievable distributions $\sigma_{\psi}$ for single-edge strategies
$\psi$.

######  Theorem 3.

A.s., the following sets are equal:

  1. (i)

$\\{\mbox{limit pts of}\ \frac{1}{n}\mu_{0\rightarrow n}(\chi):\mbox{
strategies}\ \chi\\}$

  2. (ii)

$\mathcal{R}:=\\{\nu\in\mathcal{M}_{1}:||\nu||\geq 0\\}$

  3. (iii)

$\\{\sigma_{\chi}^{0}:\mbox{ strategies}\ \chi\\}$

  4. (iv)

$\\{\sigma_{\psi}:\mbox{single-edge strategies}\ \psi\\}$

  5. (v)

$\\{\mbox{limit pts of}\ \frac{1}{n}\mu_{0\rightarrow
n}(\chi):\mbox{independent strategies}\ \chi\\}$

  6. (vi)

$\\{\mbox{limit pts of}\ \frac{1}{n}\mu_{0\rightarrow n}(\chi):\mbox{i.i.d.
strategies}\ \chi\\}$

######  Remark.

A priori it not clear that (iii)-(iv) are weakly closed. We show this as part
of our proof.

We argue via a chain of inclusions. We begin with the most trivial of these.

######  Lemma 4.

A.s. we have

$\bigg{\\{}\mbox{limit pts of}\ \frac{1}{n}\mu_{0\rightarrow n}(\chi):\mbox{
strategies}\ \chi\bigg{\\}}\subseteq\mathcal{R}$

###### Proof.

Fix a strategy $\chi$. Suppose $\frac{1}{n_{k}}\mu_{0\rightarrow
n_{k}}(\chi)\Rightarrow\nu$ for some observed edge labels
$(u_{i}^{j})_{i\geq 0,1\leq j\leq D}$. Then letting $\pi_{n}:0\rightarrow n$
be the paths corresponding to the indices
$(J_{0}(\chi),\ldots,J_{n-1}(\chi))$ conditioned on these same observed edge
labels, we get
$\frac{1}{n_{k}}\mu_{\pi_{n_{k}}}=\frac{1}{n_{k}}\mu_{0\rightarrow
n_{k}}(\chi)\Rightarrow\nu$. Thus $\nu$ is a limit point of the
$\frac{1}{n}\mu_{\pi}$.

The desired inclusion follows from

$\mathcal{R}=\bigg{\\{}\mbox{limit pts of}\ \frac{1}{n}\mu_{\pi}:\mbox{
paths}\ \pi:0\rightarrow n\bigg{\\}}\ \mbox{a.s.}\ \mbox{by Theorem
\ref{gridEntropyPart1}(iii)}$

∎

###  4.1 Expected Value of Empirical Measures

For any strategy $\chi$,

$E[\delta_{X_{i}(\chi)}]=\int_{[0,1]}\delta_{x}d\sigma_{\chi}^{i}(x)=\sigma_{\chi}^{i}\
\mbox{and}\ E\bigg{[}\frac{1}{n}\mu_{0\rightarrow
n}(\chi)\bigg{]}=\frac{1}{n}\sum_{i=0}^{n-1}\sigma^{i}_{\chi}$

Recalling (2) and the fact that $\\{\sigma^{0}_{\chi}:\mbox{strategies}\
\chi\\}$ is closed under convex combinations, it follows that every
$E[\frac{1}{n}\mu_{0\rightarrow n}(\chi)]$ is contained in
$\\{\sigma^{0}_{\chi}:\mbox{strategies}\ \chi\\}$. Therefore

$\displaystyle\bigg{\\{}E\bigg{[}\frac{1}{n}\mu_{0\rightarrow
n}(\chi)\bigg{]}:\mbox{ strategies}\ \chi\bigg{\\}}$
$\displaystyle=\\{E[\delta_{X_{0}(\chi)}]:\mbox{ strategies}\ \chi\\}$
$\displaystyle=\\{\sigma_{\chi}^{0}:\mbox{ strategies}\ \chi\\}$

Also it is clear that

$\\{E[\delta_{X(\psi)}]:\mbox{single-edge strategies}\
\psi\\}=\\{\sigma_{\psi}:\mbox{ single-edge strategies}\ \psi\\}$

A simple Tonelli argument establishes that the closures of the two sets above
coincide.

######  Lemma 5.

$\mbox{cl}\\{\sigma_{\psi}:\mbox{ single-edge strategies}\
\psi\\}=\mbox{cl}\\{\sigma^{0}_{\chi}:\mbox{ strategies}\ \chi\\}$

###### Proof.

By (1) $\\{\sigma_{\psi}\\}=\\{\sigma^{0}_{\chi}:\mbox{indep strategies}\
\chi\\}$ so it suffices to show

$\mbox{cl}\\{\sigma_{\psi}:\mbox{ single-edge strategies}\
\psi\\}\supseteq\\{\sigma^{0}_{\chi}:\mbox{ strategies}\ \chi\\}$

Given a strategy $\chi$ and observed ”future” edge labels $(u_{i}^{j})_{i\geq
1,1\leq j\leq D}\in[0,1]^{{\mathbb{Z}}_{\geq 1}}$, define
$\psi_{(u_{i}^{j})_{i\geq 1,1\leq j\leq D}}$ to be $\chi$ conditioned on the
rest of the environment $(u_{i}^{j})_{i\geq 1,1\leq j\leq D}$.

The $\psi_{(u_{i}^{j})_{i\geq 1,1\leq j\leq D}}$ are easily seen to be single-
edge strategies. Since integrating over the entire environment
$(U_{i}^{j})_{i\geq 0,1\leq j\leq D}$ is equivalent to integrating over
$(U_{0}^{j})_{1\leq j\leq D}$ first and then over $(U_{i}^{j})_{i\geq 1,1\leq
j\leq D}$, we have

$\sigma_{\chi}^{0}=\int_{([0,1]^{D})^{{\mathbb{Z}}_{\geq
1}}}\sigma_{\psi_{(u_{i}^{j})_{i\geq 1,1\leq j\leq
D}}}d\Lambda^{\infty}((u_{i}^{j})_{i\geq 1,1\leq j\leq D})$

By convexity and weak closure it follows that

$\sigma_{\chi}^{0}\in\mbox{cl}\\{\sigma_{\psi}:\mbox{ single-edge strategies}\
\psi\\}$

∎

Next, we show that this closure of $\\{\sigma_{\chi}^{0}:\mbox{strategies}\
\chi\\}$ contains all probability measures with finite grid entropy.

######  Lemma 6.

We have

$\mathcal{R}:=\\{\nu\in\mathcal{M}_{1}:||\nu||\geq
0\\}\subseteq\mbox{cl}\\{E[\delta_{X_{0}(\chi)}]:\mbox{ strategies}\ \chi\\}$

as deterministic sets.

###### Proof.

Suppose this is not the case, say
$\exists\nu\in\mathcal{R}\cap(\mbox{cl}\\{E[\delta_{X_{0}(\chi)}]:\mbox{
strategies}\ \chi\\})^{C}$. Thus there exists $\epsilon>0$ s.t.
$B_{\epsilon}(\nu)\cap cl\\{E[\delta_{X_{0}(\chi)}]:\chi\\}=\emptyset$.

Let $\pi_{n}:0\rightarrow n$ be the environment-dependent path corresponding
to $\min\limits_{\pi:0\rightarrow n}^{1}\rho(\frac{1}{n}\mu_{\pi},\nu)$. It is
crucial to note that $\pi_{n}$ depends on the observed edge labels
$((U_{i}^{j})_{0\leq i<n,1\leq j\leq D})$ of the first $n$ trials only.

By definition of grid entropy, $\frac{1}{n}\mu_{\pi_{n}}\Rightarrow\nu$ a.s..
In particular, we get convergence in probability:

$\lim_{n\rightarrow\infty}P\bigg{(}\rho\bigg{(}\frac{1}{n}\mu_{\pi_{n}},\nu\bigg{)}\geq\frac{\epsilon}{2}\bigg{)}=0$

Thus $\exists n\in{\mathbb{N}}$ s.t.

$P\bigg{(}\rho\bigg{(}\frac{1}{n}\mu_{\pi_{n}},\nu\bigg{)}\geq\frac{\epsilon}{2}\bigg{)}<\frac{\epsilon}{4}$

We claim that $\rho(E[\frac{1}{n}\mu_{\pi_{n}}],\nu)<\epsilon$. Let
$\mathcal{E}$ be the event
$\\{\rho(\frac{1}{n}\mu_{\pi_{n}},\nu)\geq\frac{\epsilon}{2}\\}$ so
$P(\mathcal{E})<\frac{\epsilon}{4}$. We split the expectation:

$E\bigg{[}\frac{1}{n}\mu_{\pi_{n}}\bigg{]}=\int_{\mathcal{E}}\frac{1}{n}\mu_{\pi_{n}}dP+\int_{\mathcal{E}^{C}}\frac{1}{n}\mu_{\pi_{n}}dP$

Since the Levy-Prokhorov metric is upper bounded by the total variation, then

$\rho\bigg{(}\int_{\mathcal{E}}\frac{1}{n}\mu_{\pi_{n}}dP,\nu\cdot
P(\mathcal{E})\bigg{)}\leq\bigg{(}\bigg{|}\bigg{|}\frac{1}{n}\mu_{\pi_{n}}\bigg{|}\bigg{|}_{TV}+||\nu||_{TV}\bigg{)}P(\mathcal{E})=2P(\mathcal{E})<\frac{\epsilon}{2}$

On $\mathcal{E}^{C}$, we have
$\rho(\frac{1}{n}\mu_{\pi_{n}},\nu)<\frac{\epsilon}{2}$. By definition of
$\rho$, for all measurable $A\in\mathcal{B}([0,1])$,

$\displaystyle\bigg{(}\int_{\mathcal{E}^{C}}\frac{1}{n}\mu_{\pi_{n}}dP\bigg{)}(A)$
$\displaystyle=\int_{\mathcal{E}^{C}}\frac{1}{n}\mu_{\pi_{n}}(A)dP$
$\displaystyle\leq\int_{\mathcal{E}^{C}}\nu(A^{\frac{\epsilon}{2}})+\frac{\epsilon}{2}dP\leq\nu(A^{\frac{\epsilon}{2}})P(\mathcal{E}^{C})+\frac{\epsilon}{2}$

and similarly

$\displaystyle\nu(A)P(\mathcal{E}^{C})$
$\displaystyle=\int_{\mathcal{E}^{C}}\nu(A)dP$
$\displaystyle\leq\int_{G^{C}}\frac{1}{n}\mu_{\pi_{n}}(A^{\frac{\epsilon}{2}})+\frac{\epsilon}{2}dP\leq\bigg{(}\int_{\mathcal{E}^{C}}\frac{1}{n}\mu_{\pi_{n}}dP\bigg{)}(A^{\frac{\epsilon}{2}})+\frac{\epsilon}{2}$

hence

$\rho\bigg{(}\int_{\mathcal{E}^{C}}\frac{1}{n}\mu_{\pi_{n}}dP,\nu
P(\mathcal{E}^{C})\bigg{)}\leq\frac{\epsilon}{2}$

By subadditivity of $\rho$,

$\displaystyle\rho\bigg{(}E\bigg{[}\frac{1}{n}\mu_{\pi_{n}}\bigg{]},\nu\bigg{)}$
$\displaystyle=\rho\bigg{(}\int_{\mathcal{E}}\frac{1}{n}\mu_{\pi_{n}}dP+\int_{\mathcal{E}^{C}}\frac{1}{n}\mu_{\pi_{n}}dP,\nu
P(\mathcal{E})+\nu P(\mathcal{E}^{C})\bigg{)}$
$\displaystyle\leq\rho\bigg{(}\int_{\mathcal{E}}\frac{1}{n}\mu_{\pi_{n}}dP,\nu
P(\mathcal{E})\bigg{)}+\rho\bigg{(}\int_{\mathcal{E}^{C}}\frac{1}{n}\mu_{\pi_{n}}dP,\nu
P(\mathcal{E}^{C})\bigg{)}$ $\displaystyle<\epsilon$

It remains to construct a strategy $\chi$ for which
$\frac{1}{n}\mu_{\pi_{n}}=\frac{1}{n}\mu_{0\rightarrow n}(\chi)$ for this
fixed $n$. But this is trivial since conditioned on the observed edge labels
$(U_{i}^{j})_{0\leq i\leq n-1,1\leq j\leq D}$ from the first $n$ trials,
$\pi_{n}$ is a deterministic path $0\rightarrow n$ (namely the one which
minimizes $\rho(\frac{1}{n}\mu_{\pi},\nu)$).

To be concrete, consider the product measure $\chi^{\prime}$ on
$([0,1]^{D})^{{\mathbb{Z}}_{\geq n}}\times\\{1,\ldots,D\\}^{{\mathbb{Z}}_{\geq
n}}$ given by

$\chi^{\prime}=\Lambda^{\infty}\times\delta_{(1,1,\ldots)}$

Heuristically, $\chi^{\prime}$ is a partial strategy always picking the ”top”
edge label $U_{i}^{1}$ for $i\geq n$.

Also let $\chi^{\prime\prime}$ be the measure on
$([0,1]^{D})^{{\mathbb{Z}}_{0\leq
i<n}}\times\\{1,\ldots,D\\}^{{\mathbb{Z}}_{0\leq i<n}}$ determined by

$\displaystyle\chi^{\prime\prime}(A\times\\{(j_{0},\ldots,j_{n-1})\\})$
$\displaystyle=\Lambda^{\infty}(\\{(u_{i}^{j})_{0\leq i<n,1\leq j\leq D}\in
A:\pi_{n}((u_{i}^{j})_{0\leq i<n,1\leq j\leq D})=(j_{0},\ldots,j_{n-1})\\})$

$\forall A\in\mathcal{B}(([0,1]^{D})^{{\mathbb{Z}}_{0\leq
i<n}}),(j_{i})_{0\leq i<n}\in\\{1,\ldots,D\\}^{{\mathbb{Z}}_{0\leq i<n}}$
where $\pi_{n}((u_{i}^{j})_{0\leq i<n,1\leq j\leq D})$ denotes the sequence of
$n$ indices $(j_{0},\ldots,j_{n-1})$ corresponding to the path $\pi_{n}$ when
the first $n$ trials yield observed labels $(u_{i}^{j})_{0\leq i<n,1\leq j\leq
D}$. That is, conditioned on the observed values from the first $n$ trials,
$\chi^{\prime\prime}$ always picks the path corresponding to $\pi_{n}$.

Now consider the strategy $\chi=\chi^{\prime\prime}\times\chi^{\prime}$.
$\mu_{0\rightarrow n}(\chi)=\mu_{\pi_{n}}$ hence
$E[\frac{1}{n}\mu_{\pi_{n}}]=E[\frac{1}{n}\mu_{0\rightarrow n}(\chi)]$.

This contradicts

$B_{\epsilon}(\nu)\cap cl\bigg{\\{}E\bigg{[}\frac{1}{n}\mu_{0\rightarrow
n}(\chi)\bigg{]}:\chi\bigg{\\}}=B_{\epsilon}(\nu)\cap
cl\\{E[\delta_{X_{0}(\chi)}]:\chi\\}=\emptyset$

∎

Combining Lemmas 4-6, we get that a.s., (vi) $\subseteq$ (v) $\subseteq$ (i)
$\subseteq$ (ii) $\subseteq$ cl(iii) = cl(iv) in Theorem 3. To complete the
proof we only need to show the last inclusion cl (iv) $\subseteq$ (vi) and the
fact that (iv) is weakly closed.

###  4.2 What Happens with Independent Strategies

Let us now focus on the case of independent strategies. Recall that these look
like $\chi=\bigtimes\limits_{i=0}^{\infty}\psi_{i}$ where $(\psi_{i})_{i\geq
0}$ are single-edge strategies.

First, consider the even simpler case of i.i.d. strategies $\chi$, where all
the $\psi_{i}$ are identical, resulting in i.i.d. $X_{i}$. Then the Glivenko-
Cantelli Theorem [Dur19, Thm. 2.4.7] gives that a.s. the empirical measures
$\frac{1}{n}\mu_{0\rightarrow n}(\chi)$ converge weakly to the common law of
the $X_{i}$’s, $\sigma_{\psi_{0}}$.

######  Theorem 7 (Glivenko-Cantelli Theorem).

Let $F_{\gamma}$ be the cumulative distribution function of $\gamma$, let
$Y_{i}\sim\gamma$ be i.i.d. random variables and let

$F_{n}(y)=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}_{\\{Y_{i}\leq y\\}}$

be the cumulative distribution functions of the empirical measures. Then

$\sup_{y}|F_{n}(y)-F_{\gamma}(y)|\rightarrow 0\ \mbox{a.s. as}\
n\rightarrow\infty$

As an immediate corollary we get the outstanding inclusion (vi) $\supseteq$ cl
(iv) mentioned at the end of Section 4.1.

######  Corollary 8.

A.s. we have

$\bigg{\\{}\mbox{limit pts of}\ \frac{1}{n}\mu_{0\rightarrow n}(\chi):\
\mbox{i.i.d. strategies $\chi$}\bigg{\\}}\supseteq
cl\\{\sigma_{\psi}:\mbox{single-edge strategies}\ \psi\\}$

###### Proof.

Fix a dense subset $\mathcal{O}$ of the deterministic, weakly compact set cl
(iv) s.t. $\mathcal{O}\subseteq\mbox{(iv).}$ For every
$\sigma_{\psi}\in\mathcal{O}$, apply Theorem 7 to the i.i.d. strategy
$\chi=\bigtimes\limits_{i=0}^{\infty}\psi$ to get
$\frac{1}{n}\mu_{0\rightarrow n}(\chi)\Rightarrow\sigma_{\psi}$ a.s..
Therefore $\mathcal{O}\subseteq$ (vi) a.s.. The inclusion follows since (vi)
is weakly closed.
∎

Thus we have shown that the sets (i), (ii), cl(iii), cl(iv), (v), (vi) in
Theorem 3 are equal a.s..

Before proceeding to look further into single-edge strategies, it is worth
mentioning a version of the Glivenko-Cantelli Theorem for independent but not
necessarily i.d. sequences from [Wel81]. It gives further insight into the
limit points of the empirical measures $\frac{1}{n}\mu_{0\rightarrow n}(\chi)$
for independent strategies $\chi$.

######  Theorem 9.

Let $Y_{i}$ be a sequence of independent random variables with distributions
$\sigma_{i}$. Define
$\overline{\sigma}_{n}=\frac{1}{n}(\sigma_{0}+\ldots+\sigma_{n-1})$ to be the
averages of these distributions and let
$\frac{1}{n}\mu_{n}=\frac{1}{n}(\delta_{Y_{0}}+\ldots+\delta_{Y_{n-1}})$ be
the empirical measures. If $\\{\overline{\sigma}_{n}\\}$ is tight then
$\rho(\overline{\sigma}_{n},\frac{1}{n}\mu_{n})\rightarrow 0$ a.s..

In our case, $\mathcal{M}_{1}$ is weakly compact so any sequence of
probability measures in $\mathcal{M}_{1}$ is tight.

Thus, for independent strategies
$\chi=\bigtimes\limits_{i=0}^{\infty}\psi_{i}$ with $\psi_{i}$ single-edge
strategies, we have
$\rho(\overline{\sigma_{n}},\frac{1}{n}\mu_{0\rightarrow n}(\chi))\rightarrow
0\ \mbox{a.s.}$ where $\overline{\sigma_{n}}$ denote the averages of the
distributions of $X_{i}(\chi)$:

$\overline{\sigma}_{n}=\frac{1}{n}(\sigma^{0}_{\chi}+\ldots+\sigma^{n-1}_{\chi})=\frac{1}{n}(\sigma_{\psi_{0}}+\ldots+\sigma_{\psi_{n-1}})=\sigma_{\frac{1}{n}(\psi_{0}+\ldots+\psi_{n-1})}$

This not only confirms that cl(iv) and (v) are equal, but it tells us that
a.s. the empirical measures $\frac{1}{n}\mu_{0\rightarrow n}(\chi)$ for
independent strategies $\chi$ have the exact same limit points as the
distributions $\sigma_{\frac{1}{n}(\psi_{0}+\ldots+\psi_{n-1})}$ corresponding
to the law of $X$ chosen according to the average of the single-edge
strategies $\psi_{i}$.

##  5 Single-Edge Strategies Revisited

###  5.1 Single-Edge Strategies in Terms of Conditional Probabilities

From what we have shown thus far, we only need to focus on single-edge
strategies, as the set of limit points of empirical measures
$\frac{1}{n}\mu_{0\rightarrow n}(\chi)$ coincides with

$cl\\{\sigma_{\psi}:\mbox{single-edge strategies}\ \psi\\}$

Rather than using the measure definition of single-edge strategies, it is more
practical to work with the vector $\vec{p}$ of conditional probabilities
defined as

$p_{k}(u_{1},\ldots,u_{D}):=P_{\psi}[J=k\mid(U^{j})_{1\leq j\leq
D}=(u^{j})_{1\leq j\leq D}]$

Then $\psi$ evaluated on product sets is given by

$\psi(A\times
B)=\int_{A}\sum_{j=1}^{D}p_{j}(u_{1},\ldots,u_{D})\mathbf{1}_{\\{j\in B\\}}\
d\Lambda^{D}(u_{1},\ldots,u_{D})\ \forall
A\in\mathcal{B}([0,1]^{D}),B\subseteq\\{1,\ldots,D\\}$ (4)

and $\sum\limits_{j=1}^{D}p_{j}\equiv 1$ everywhere.

Intuitively, each $p_{k}(u_{1},\ldots,u_{D})$ is the probability of choosing
$u_{k}$ when the observed samples are $(u_{1},\ldots,u_{D})$. This justifies
the term ”single-edge strategy,” because $\vec{p}$ is prescribing the strategy
by which we make our choice once we have the $D$ observed samples.

Of course, the vector $\vec{p}=(p_{1},\ldots,p_{D})$ determines $\psi$ by (4).
And if all the $p_{j}$ are 0-1 valued $\Lambda^{\times D}$-a.e. then the
single-edge strategy $\psi$ is deterministic.

Even though different $\vec{p}$ may give rise to the same $\psi$, we conflate
the two notions and call both $\psi$ and $\vec{p}$ the single-edge strategy.
We use $X(\vec{p}),X(\chi)$ and $\sigma_{\vec{p}},\sigma_{\psi}$ and
$F_{\vec{p}},F_{\psi}$ interchangeably. At the end of the day, all that
matters is whether two vectors $\vec{p},\vec{q}$ yield the same law
$\sigma_{\vec{p}}$ of $X(\vec{p})$.

We may now write the cumulative distribution function of $\sigma_{\vec{p}}$ in
terms of $\vec{p}$:

$\begin{split}F_{\vec{p}}(y)&=\int_{[0,1]^{D}}\sum_{j=1}^{D}p_{j}(u_{1},\ldots,u_{D})\mathbf{1}_{[0,y]}(u_{j})d\Lambda^{D}(u_{1},\ldots,u_{D})\\\
&=\int_{[0,y]\times[0,1]^{D-1}}p_{1}(u_{1},\ldots,u_{D})d\Lambda^{D}(u_{1},\ldots,u_{D})\\\
&+\ldots+\int_{[0,1]^{D-1}\times[0,y]}p_{D}(u_{1},\ldots,u_{D})d\Lambda^{D}(u_{1},\ldots,u_{D})\end{split}$
(5)

Therefore $\sigma_{\vec{p}}\ll\Lambda$ with density

$\begin{split}f_{\vec{p}}(y)&=\int_{[0,1]^{D-1}}p_{1}(y,u_{2},\ldots,u_{D})d\Lambda^{D-1}(u_{2},\ldots,u_{D})\\\
&+\cdots+\int_{[0,1]^{D-1}}p_{D}(u_{1},\ldots,u_{D-1},y)d\Lambda^{D-1}(u_{1},\ldots,u_{D-1})\end{split}$
(6)

It is clear that $f_{\vec{p}}\in[0,D]$.

Let us give an example that will make everything clear. Consider the
deterministic single-edge strategy $\vec{p}^{MAX}$ that always chooses the
maximum of the observed edge labels. In our notation,

$p_{j}^{MAX}(u_{1},\ldots,u_{D})=\mathbf{1}_{\\{u_{j}\geq u_{k}\ \forall 1\leq
k\leq D\\}}$

The resulting distribution $\sigma_{MAX}$ has cdf

$F_{MAX}(y)=P(U^{j}\leq y\ \forall 1\leq j\leq D)=y^{D}$

and density

$f_{MAX}(y)=Dy^{D-1}$

This single-edge strategy plays a crucial role later in our description of the
extreme points of $\\{\sigma_{\vec{p}}\\}$.

We will also be interested in single-edge strategies ”scrambled” by a
$\Lambda$-measure-preserving bijection.

######  Definition.

Let $\vec{p}$ be a single-edge strategy and let $\phi:[0,1]\rightarrow[0,1]$
be a $\Lambda$-measure-preserving bijection. We define $\vec{p}^{\phi}$ to be
the single-edge strategy with coordinate functions

$p_{j}^{\phi}(u_{1},\ldots,u_{D}):=p_{j}(\phi(u_{1}),\ldots,\phi(u_{D}))$

It is clear that $\sum p_{j}^{\phi}\equiv 1$ still so it is a valid single-
edge strategy. Furthermore, since $\phi$ is measure-preserving with respect to
$\Lambda$, then by a change of variables in the integral formula for
$f_{\vec{p}}$ we get

$f_{\vec{p}^{\phi}}=f_{\vec{p}}\circ\phi$

The following lemma collects some basic facts about single-edge strategies.

######  Lemma 10.

Let $\vec{p}$ be a single-edge strategy.

  1. (i)

For any Borel set $A\in\mathcal{B}([0,1])$,

$\Lambda(A)^{D}\leq\sigma_{\vec{p}}(A)\leq 1-(1-\Lambda(A))^{D}$

In particular, $X(\vec{p}^{MAX})$ stochastically dominates $X(\vec{p})$ and
$\sigma_{\vec{p}}\ll\Lambda,\Lambda\ll\sigma_{\vec{p}}$.

  2. (ii)

We have

$\sup_{\phi}E[\sigma_{\vec{p}^{\phi}}]\leq E[\sigma_{MAX}]$

where the supremum is taken over $\Lambda$-measure-preserving bijections
$\phi:[0,1]\rightarrow[0,1]$.

  3. (iii)

Convex combinations of single-edge strategies $\vec{p}$ translate to convex
combinations of $\sigma_{\vec{p}},f_{\vec{p}},F_{\vec{p}}$.

######  Remark.

It is not clear whether the supremum in (ii) is achieved, but this is beyond
the scope of this paper.

###### Proof.

(i) If all $D$ edge labels $u_{1},\ldots,u_{D}$ are in the set $A$, then so
must be the edge label chosen from among them. Therefore
$\Lambda(A)^{D}\leq\sigma_{\vec{p}}(A)$. The other inequality follows by
replacing $A$ with $A^{C}$.

Recalling that $F_{MAX}(y)=y^{D}$, we get

$F_{MAX}(y)\leq F_{\vec{p}}(y)\ \forall y$

(ii) For any $\Lambda$-measure-preserving bijection $\phi$, we apply the tail
integral formula for expectation and use (i) to get

$E[\sigma_{\vec{p}^{\phi}}]=\int_{0}^{1}1-F_{\vec{p}^{\phi}}(t)dt\leq\int_{0}^{1}1-F_{MAX}(t)dt=E[\sigma_{MAX}]$

(iii) For single-edge strategies $\vec{p},\vec{q}$ and $t\in[0,1]$,
$t\vec{p}+(1-t)\vec{q}$ is itself a single-edge strategy with

$F_{t\vec{p}+(1-t)\vec{q}}=tF_{\vec{p}}+(1-t)F_{\vec{q}},\
f_{t\vec{p}+(1-t)\vec{q}}=tf_{\vec{p}}+(1-t)f_{\vec{q}},\
\mu_{t\vec{p}+(1-t)\vec{q}}=t\sigma_{\vec{p}}+(1-t)\sigma_{\vec{q}}$

∎

###  5.2 ”Consistent” Single-Edge Strategies

Before proceeding further, we explain why we can restrict ourselves to single-
edge strategies $\vec{p}$ with some convenient symmetries that render
$\vec{p}$ consistent.

We say a permutation $\iota\in S_{D}$ acts on a $D$-tuple $\vec{u}$ by
applying $\iota$ to the indices:

$\iota(\vec{u})=(u_{\iota(1)},\ldots,u_{\iota(D)})$

######  Lemma 11.

Let $\vec{p}$ be any single-edge strategy. Then there exists another single-
edge strategy $\vec{q}$ that gives rise to the same distribution
$\sigma_{\vec{p}}=\sigma_{\vec{q}}$ s.t. $\forall x\in[0,1],1\leq i\leq D$

$f_{\vec{p}}(x)=f_{\vec{q}}(x)=D\int_{[0,1]^{D-1}}q_{i}(u_{1},u_{2},\ldots,x,\ldots,u_{D})d\Lambda^{D-1}(u_{1},\ldots,\widehat{u_{i}},\ldots,u_{D})$
(7)

where the $x$ occurs at position $i$, s.t.

$q_{1}(\iota_{i}(\vec{u}))=q_{2}(\iota_{i-1}(\vec{u}))=\ldots=q_{D}(\iota_{i+1}(\vec{u}))\
\forall 1\leq i\leq D\ \forall\vec{u}$ (8)

where each $\iota_{j}$ is the cyclic shift

$\iota_{j}(\vec{u})=(u_{j},u_{j+1},\ldots,u_{D},u_{1},\ldots,u_{j-1})$

and s.t.

$q_{i}(\vec{u})=q_{i}(\iota(\vec{u}))\ \forall 1\leq i\leq
D,\forall\vec{u},\mbox{and}\ \forall\iota\in S_{D}\ \mbox{with}\ \iota(i)=i$
(9)

######  Remark.

The new single-edge strategy $\vec{q}$ is consistent across all permutations
of a tuple $\vec{u}$. That is, given an unordered tuple $(u_{1},\ldots,u_{D})$
we can say that $\vec{q}$ chooses each $u_{i}$ with probability $t_{i}$. Then
every $q_{j}(\iota(\vec{u}))$ for $\iota\in S_{D}$ picks out the probability
$t_{\iota(j)}$ i.e. $q_{j}$ outputs the probability of choosing the $j$th
entry in its input tuple.

Furthermore, both the density $f_{\vec{q}}$ and the entire single-edge
strategy $\vec{q}$ are uniquely determined by any one of the $q_{i}$. That is,
given a measurable function $q_{i}:[0,1]^{D}\rightarrow[0,1]$ whose integral
over $[0,1]^{D}$ with respect to the product measure $\Lambda^{\times D}$ is
$\frac{1}{D}$, which is invariant under permutations in $S_{D}$ fixing $i$,
and which satisfies

$\sum_{j}q_{i}(\iota_{j}(\vec{u}))=1\ \forall\vec{u}$

we can use cyclic shifts to define a valid corresponding single-edge strategy
$\vec{q}$ (that satisfies $\sum q_{j}\equiv 1$ and $\int_{[0,1]^{D}}q_{j}\
d\Lambda^{\times D}=\frac{1}{D}$) and we can compute $f_{\vec{q}}$ directly
from $q_{i}$.

######  Remark.

It is easy to check that $\vec{p}^{MAX}$ satisfies (7)-(9). Furthermore, if
$\vec{p}$ is a consistent single-edge strategy and
$\phi:[0,1]\rightarrow[0,1]$ is a $\Lambda$-measure-preserving bijection then
so is $\vec{p}^{\phi}$.

###### Proof.

The intuition is that we take the average of the original $p_{i}$ over the
desired symmetries. We do this in two steps. For each $1\leq i\leq D$ define

$p_{i}^{\prime}(\vec{u}):=\frac{p_{1}(\iota_{i}(\vec{u}))+p_{2}(\iota_{i-1}(\vec{u}))+\ldots+p_{i}(\iota_{1}(\vec{u}))+\ldots
p_{D}(\iota_{i+1}(\vec{u}))}{D}$
$q_{i}(\vec{u})=\frac{1}{(D-1)!}\sum_{\iota\in
S_{D},\iota(i)=i}p_{i}^{\prime}(u_{\iota(1)},u_{\iota(2)}\ldots,u_{\iota(D)})$

A straightforward computation shows that $\vec{q}$ satisfies the required
properties (7)-(9). ∎

For the rest of the paper we restrict ourselves to these consistent single-
edge strategies, which will simplify our computations.

###  5.3 Closure of $\\{\sigma_{\vec{p}}\\}$

The last remaining part of Theorem 3 is to show that the set of distributions
$\sigma_{\vec{p}}$ is weakly closed.

######  Theorem 12.

$\\{\sigma_{\vec{p}}:\mbox{ single-edge strategies}\ \vec{p}\\}$ is weakly
closed

###### Proof.

Suppose $\sigma_{\vec{p}^{n}}\Rightarrow\xi$ for some consistent single-edge
strategies $\vec{p}^{n}$. We seek a single-edge strategy yielding the
distribution $\xi$.

Consider any $n$. Let $\nu_{\vec{p}^{n}}$ be the distribution on $[0,1]^{D}$
given by integration against
$Dp_{1}^{n}d\Lambda^{\times D}$. Observe that (7) implies

$f_{\vec{p}^{n}}(y)=\int_{[0,1]^{D-1}}Dp_{1}^{n}(y,u_{2},\ldots,u_{D})d\Lambda^{D-1}(u_{2},\ldots,u_{D})$

so $\sigma_{\vec{p}^{n}}$ is just the first coordinate marginal of
$\nu_{\vec{p}^{n}}$.

Compactness yields a weakly convergent subsequence
$\nu_{\vec{p}^{n_{j}}}\Rightarrow\nu$. By a standard argument, since
$Dp_{1}^{n}$ are uniformly bounded by $D$, then $\nu\ll\Lambda^{\times D}$ and
has a density of the form $Dp_{1}$ for some measurable function
$p_{1}:[0,1]^{D}\rightarrow[0,1]$. This along with the fact that
$\int_{[0,1]^{D}}p_{1}d\Lambda^{\times D}=\frac{1}{D}$ are enough for $p_{1}$
to give rise to a single-edge strategy $\vec{p}$ by the first Remark following
Lemma 11.

But then the corresponding first coordinate marginals must also converge
weakly, so we get $\sigma_{\vec{p}^{n_{j}}}\Rightarrow\xi^{\prime}$ where
$\xi^{\prime}$ is the corresponding marginal of $\nu$:

$\xi^{\prime}(A)=\int_{A\times[0,1]^{D-1}}Dp_{1}d\Lambda^{D}=\sigma_{\vec{p}}(A)\
\forall A\in\mathcal{B}([0,1])$

Thus $\xi^{\prime}=\sigma_{\vec{p}}$. On the other hand,
$\sigma_{\vec{p}^{n}}\Rightarrow\xi$ so by uniqueness of weak limits,
$\xi=\xi^{\prime}=\sigma_{\vec{p}}$. ∎

Therefore the set of possible distributions $\\{\sigma_{\vec{p}}\\}$ of
$X(\vec{p})$ over single-edge strategies $\vec{p}$ almost surely coincides
with the set of limit points of the empirical measures
$\frac{1}{n}\mu_{0\rightarrow n}(\chi)$ over all strategies $\chi$. In
particular these have the same extreme points.

##  6 Extreme Points of $\\{\sigma_{\vec{p}}\\}$

Our goal in this section is to characterize the extreme points of the possible
distributions of $X$ we can observe as we vary the underlying single-edge
strategy. It turns out that the extreme points of $\\{\sigma_{\vec{p}}:\mbox{
single-edge strategies}\ \vec{p}\\}$ are precisely those $\sigma_{\vec{p}}$
which have scramblings with mean converging to the mean of $\sigma_{MAX}$, or,
equivalently, those $\sigma_{\vec{p}}$ with deterministic $\vec{p}$.

######  Theorem 13.

Let $\vec{p}$ be a single-edge strategy. The following are equivalent:

  1. (i)

$\sigma_{\vec{p}}$ is an extreme point

  2. (ii)

Any consistent single-edge strategy achieving $\sigma_{\vec{p}}$ must be
deterministic

  3. (iii)

$f_{\vec{p}}$ is not constant on sets of positive $\Lambda$-measure and
$\sigma_{\vec{p}}$ is given by the following single-edge strategy $\vec{q}$:

$q_{k}(u_{1},\ldots,u_{D})=\textbf{1}_{\\{f_{\vec{p}}(u_{k})\geq
f_{\vec{p}}(u_{i})\ \forall i\\}}\ \mbox{for $\Lambda^{\times D}$-a.a.}\
(u_{1},\ldots,u_{D})$

In other words, $\sigma_{\vec{p}}$ is achieved by the deterministic single-
edge strategy ”choose
whichever label yields a higher value when evaluating the density
$f_{\vec{p}}$”

  4. (iv)

$\sup_{\phi}E[\sigma_{\vec{p}^{\phi}}]=E[\sigma_{MAX}]$

  5. (v)

For $U\sim[0,1]$ if $f_{\vec{p}}(U),f_{MAX}(U)$ as $[0,D]$-valued random
variables on the probability space $([0,1],\mathcal{B}([0,1]),\Lambda)$, then
they have the same distribution. That is,

$P(f_{\vec{p}}\leq x)=P(f_{MAX}\leq x)\ \forall x$

######  Remark.

Since $f_{MAX}(y)=Dy^{D-1}$ on $[0,1]$ then
$\frac{1}{D}f_{MAX}\sim\mbox{Beta}(D,1)$. Thus (v) implies that for
$U\sim\mbox{Unif}[0,1]$, $f_{\vec{p}}(U)$ has a continuous probability
distribution.

We prove this theorem over the next couple of sections.

###  6.1 Deterministic Single-Edge Strategies

We begin by characterizing the extreme points of the set of distributions
$\\{\sigma_{\vec{p}}\\}$ in terms of deterministic single-edge strategies.

######  Lemma 14.

(i) $\Leftrightarrow$ (ii) in Theorem 13

###### Proof.

We prove both contrapositives.

First, consider a distribution $\sigma_{\vec{p}}$ achieved by a non-
deterministic consistent single-edge strategy $\vec{p}$, i.e. a single-edge
strategy satisfying (7)-(9). We will construct a set of positive
$\Lambda^{\times D}$ measure on which we perturb $p_{1}$ in a way that allows
us to write $\vec{p}$ as a non-trivial average of two single-edge strategies
$\vec{q},\vec{r}$.

By our assumption, there exists $0<\epsilon<\frac{1}{2}$ s.t. the set

$A=\\{\vec{u}:p_{1}(\vec{u})\in(\epsilon,1-\epsilon),p_{1}(\vec{u})\geq
p_{1}(\iota_{i}(\vec{u}))\ \forall 1\leq i\leq D\\}\ \mbox{has positive
$\Lambda^{\times D}$ measure}$

where $\iota_{i}$ are the cyclic shifts as before. Then there are
$a_{1}<b_{1},a_{2}<b_{2}$ s.t. $[a_{1},b_{1}],[a_{2},b_{2}]$ are disjoint and

$A^{\prime}=A\cap[a_{1},b_{1}]\times[a_{2},b_{2}]^{D-1}\ \mbox{has positive
$\Lambda^{\times D}$ measure}$

The purpose of this is to ensure that the first coordinate in a tuple in
$A^{\prime}$ cannot appear in any other position in another tuple in
$A^{\prime}$.

By (8), the fact that $p_{1}(\vec{u})<1-\epsilon$ on $A^{\prime}$, and the
definition of single-edge strategies,

$\sum_{k=2}^{D}p_{1}(\iota_{k}(\vec{u}))=\sum_{k=2}^{D}p_{k}(\vec{u})=1-p_{1}(\vec{u})>\epsilon\
\forall\vec{u}\in A^{\prime}$

Hence for any $\vec{u}\in A^{\prime}$, there exists $2\leq k\leq D$ s.t.
$p_{1}(\iota_{k}(\vec{u}))>\frac{\epsilon}{D}$. It follows that there is
$2\leq k\leq D$ s.t.

$A^{\prime\prime}=\bigg{\\{}\vec{u}\in
A^{\prime}:p_{1}(\iota_{k}(\vec{u}))\in\bigg{(}\frac{\epsilon}{D},1-\epsilon\bigg{)}\bigg{\\}}\
\mbox{has positive $\Lambda^{\times D}$ measure}$

Define

$q_{1}:=p_{1}+\frac{\epsilon}{D!}\sum_{\iota\in
S_{D},\iota(1)=1}(\mathbf{1}_{\iota(A^{\prime\prime})}-\mathbf{1}_{\iota(\iota_{k}^{-1}(A^{\prime\prime}))}),r_{1}:=p_{1}+\frac{\epsilon}{D!}\sum_{\iota\in
S_{D},\iota(1)=1}(-\mathbf{1}_{\iota(A^{\prime\prime})}+\mathbf{1}_{\iota(\iota_{k}^{-1}(A^{\prime\prime}))})$

It is clear that $q_{1},r_{1}$ average to $p_{1}$, and are both invariant
under permutations in $S_{D}$ fixing 1. Since
$p_{1}(\vec{u})\in(\frac{\epsilon}{D},1-\epsilon)\
\forall\vec{u}\in\iota(A^{\prime\prime})\cup\iota(\iota_{k}^{-1}(A^{\prime\prime}))\
\forall\iota\in S_{D},\iota(1)=1$ then both $q_{1},r_{1}$ have ranges in
$[0,1]$. Also, note that

$\int_{[0,1]^{D}}\mathbf{1}_{\iota(B)}d\Lambda^{\times D}=\Lambda^{\times
D}(B)\ \forall B\in\mathcal{B}([0,1]^{D}),\iota\in S_{D}$

so it follows that

$\int_{[0,1]^{D}}q_{1}d\Lambda^{\times
D}=\int_{[0,1]^{D}}r_{1}d\Lambda^{\times
D}=\int_{[0,1]^{D}}p_{1}d\Lambda^{\times D}=\frac{1}{D}$

Finally, note that by a simple counting argument, for any $\vec{u}$,

$\sum_{i}\sum_{\iota\in
S_{D},\iota(1)=1}\mathbf{1}_{\iota(A^{\prime\prime})}(\iota_{i}(\vec{u}))=\sum_{\iota\in
S_{D}}\mathbf{1}_{\iota(A^{\prime\prime})}(\vec{u})=\sum_{i}\sum_{\iota\in
S_{D},\iota(1)=1}\mathbf{1}_{\iota(\iota_{k}^{-1}(A^{\prime\prime}))}(\iota_{i}(\vec{u}))$

so

$\sum_{i}q_{1}(\iota_{i}(\vec{u}))=\sum_{i}r_{1}(\iota_{i}(\vec{u}))=\sum_{i}p_{1}(\iota_{i}(\vec{u}))=1\
\forall\vec{u}$

Thus $q_{1},r_{1}$ are valid probability functions which average to $p_{1}$.
By the remark after Lemma 11, these uniquely determine single-edge strategies
$\vec{q},\vec{r}$ whose average is $\vec{p}$. Thus $f_{\vec{p}}$ is the
average of $f_{\vec{q}},f_{\vec{r}}$. It remains to show this convex
combination is non-trivial.

Consider any $\vec{u}=(u_{1},u_{2},\ldots,u_{D})$ with
$u_{1}\in[a_{1},b_{1}]$. For any $\iota\in S_{D},\iota(1)=1$,

$\iota^{-1}(k)\neq 1\Rightarrow u_{\iota^{-1}(k)}\in[a_{2},b_{2}]\Rightarrow
u_{\iota^{-1}(k)}\notin[a_{1},b_{1}]\Rightarrow\vec{u}\notin\iota(\iota_{k}^{-1}(A^{\prime\prime}))$

It follows that

$q_{1}(\vec{u})=p_{1}(\vec{u})+\frac{\epsilon}{D!}\sum_{\iota\in
S_{D},\iota(1)=1}\mathbf{1}_{\iota(A^{\prime\prime})}(\vec{u})\geq
p_{1}(\vec{u})+\frac{\epsilon}{D!}\mathbf{1}_{A^{\prime\prime}}(\vec{u})$

so by (7),

$f_{\vec{q}}(u_{1})\geq
f_{\vec{p}}(u_{1})+\frac{\epsilon}{(D-1)!}\int_{[0,1]^{D-1}}\mathbf{1}_{A^{\prime\prime}}(u_{1},u_{2},\ldots,u_{D})\
d\Lambda^{\times(D-1)}(u_{2},\ldots,u_{D})$

Since $\Lambda^{\times D}(A^{\prime\prime})>0$ then there is $\delta>0$ and a
Borel set $B\subset[a_{1},b_{1}]$ with $\Lambda(B)>0$ s.t. the integral above
is $\geq\delta$ for $u_{1}\in B$. It follows that $f_{\vec{q}}\geq
f_{\vec{p}}+\frac{\epsilon}{(D-1)!}\delta$ on $B$ so the convex combination is
non-trivial. Therefore $\sigma_{\vec{p}}$ is not an extreme point.

Now suppose $\sigma_{\vec{p}}$ is not an extreme point, say
$\sigma_{\vec{p}}=t\sigma_{\vec{q}}+(1-t)\sigma_{\vec{r}}$ for some consistent
single-edge strategies $\vec{q},\vec{r}$ with
$\sigma_{\vec{q}}\neq\sigma_{\vec{r}}$. Then $\sigma_{\vec{p}}$ is achieved by
the single-edge strategy $t\vec{q}+(1-t)\vec{r}$, which trivially satisfies
(7)-(9) so is consistent. Since $\vec{q},\vec{r}$ have range in $[0,1]$ and
differ on some set of positive $\Lambda^{\times D}$-measure then on this same
set $t\vec{q}+(1-t)\vec{r}$ is not $\\{0,1\\}$-valued. Thus $\sigma_{\vec{p}}$
is achieved by a non-deterministic single-edge strategy satisfying (7)-(9). ∎

###  6.2 ”Weight Tuples” of Single-Edge Strategies

$\sigma_{\vec{p}}$ being an extreme point will give us further properties
relating to $(D+1)$-tuples
$(u_{1},\ldots,u_{D+1})$, but these properties hold a.s. and we must be extra
careful about which tuples living in measure 0 sets we are excluding. We need
some setup to address this issue.

Let $\vec{p}$ be a consistent single-edge strategy s.t. $\sigma_{\vec{p}}$ is
an extreme point. By Lemma 14, $p_{1}$ is 0-1 valued $\Lambda^{\times
D}$-a.e.. Also, the set of tuples in $[0,1]^{D}$ with two or more duplicates
has $\Lambda^{\times D}$-measure 0. Define

$S:=\\{\mbox{ordered}\ (u_{1},\ldots,u_{D})\in{\mathbb{R}}^{D}\ \mbox{
duplicate-free s.t.}\ p_{1}(u_{1},\ldots,u_{D})\in\\{0,1\\}\\}$

to be the set of ”good” ordered $D$-tuples we consider. Note that
$\Lambda^{D}(S)=1$. Once we prove more a.s. properties of the elements of $S$,
we will amend this definition of $S$ accordingly.

Combining the fact that $p_{1}$ is 0-1 valued on $S$ and the remark after
Lemma 11, we see that $p_{1}$ is equivalent to a choice function taking in
_unordered_ tuples $(u_{1},\ldots,u_{D})$ and outputting one of the
coordinates $u_{j}$; then for any $\iota\in S_{D}$,
$p_{1}(\iota(\vec{u}))=\mathbf{1}_{\\{j=\iota(1)\\}}$ i.e. $p_{1}$ returns
whether or not the first coordinate of the input ordered tuple is the choice
associated with the corresponding unordered tuple.

Let

$T=\left\\{\begin{array}[]{l}\mbox{ordered}\
(u_{1},\ldots,u_{D+1})\in[0,1]^{D+1}\ \mbox{ s.t.}\\\ \mbox{all $(D+1)!$
ordered subtuples of size $D$ are in $S$}\end{array}\right\\}$

It is clear that $\Lambda^{\times(D+1)}(T)=1$ and the tuples in $T$ contain no
duplicate entries. $T$ is the set of ”good” ordered $(D+1)$-tuples we restrict
ourselves to.

For ordered $(D+1)$-tuples in $T$, we wish to study the possible sets of
choices we can make for the $(D+1)!$ ordered subtuples of size $D$. Since the
choice for some $\vec{u}\in[0,1]^{D}$ is also the choice for $\iota(\vec{u})$
for all $\iota\in S_{D}$, then rather than keeping a factor of $D!$
everywhere, we instead consider the possible sets of choices we can make for
the $D+1$ _unordered_ subtuples of size $D$. We can encode these choices as an
ordered ”weight tuple” $(w_{1},\ldots,w_{D+1})$ where $w_{j}$ is the number of
times $u_{j}$ is the choice made. In terms of the consistent single-edge
strategy $\vec{p}$,

$w_{j}=w_{j}(u_{1},\ldots,u_{D+1}):=\sum_{1\leq k\leq D+1,k\neq
j}p_{1}(u_{j},u_{1},\ldots,\widehat{u_{j}},\ldots,\widehat{u_{k}},\ldots,u_{D+1})$
(10)

For example, the weight tuple $(D,1,0,\ldots,0)$ corresponds to the choices

$(u_{1},\ldots,\widehat{u_{k}},\ldots,u_{D+1})\mapsto u_{1}\ \forall 2\leq
k\leq D+1\ \mbox{and}\ (u_{2},\ldots,u_{D+1})\mapsto u_{2}$

Note that each $u_{j}$ appears in exactly $D$ of the $D+1$ $D$-subtuples and
there is exactly one choice for each subtuple so

$w_{i}\in\\{0,1,\ldots,D\\}\ \forall 1\leq i\leq D+1,\sum w_{i}\equiv D+1$
(11)

Even though a weight tuple may correspond to more than one set of choices for
the $D+1$ $D$-subtuples, it is easily checked that every valid weight tuple
(satisfying (11)) corresponds to at least one set of choices.

The following flow chart summarizes this process:

Start with ordered $(D+1)$-tuple $(u_{1},\ldots,u_{D+1})\in T$Consider the
choice for each unordered $D$-subtuple
$(u_{1},\ldots,\widehat{u_{k}},\ldots,u_{D+1})$. Count occurrences of each
$u_{j}$ among these choices.Get an ordered $(D+1$)-weight tuple
$(w_{1},\ldots,w_{D+1})$ satisfying (11)

One last observation we make about the weight tuples is that they can be used
to compute the density $f_{\vec{p}}$ directly. Fix any $1\leq j\leq D+1$.
Observe that (7) with a change of variables gives

$\begin{split}f_{\vec{p}}(t)&=D\int_{[0,1]^{D-1}}p_{1}(t,u_{2},\ldots,u_{D})d\Lambda^{D-1}(u_{2},\ldots,u_{D})\\\
&=\sum_{1\leq k\leq D+1,k\neq
j}\int_{[0,1]^{D-1}}p_{1}(t,u_{1},\ldots,\widehat{u_{j}},\ldots,\widehat{u_{k}},\ldots,u_{D+1})\\\
&\qquad\qquad\qquad
d\Lambda^{D-1}(u_{1},\ldots,\widehat{u_{j}},\ldots,\widehat{u_{k}},\ldots,u_{D+1})\end{split}$

But $\Lambda$ is a probability measure so we can integrate everything against
$du_{k}$ without changing the value:

$\begin{split}f_{\vec{p}}(t)&=\sum_{1\leq k\leq D+1,k\neq
j}\int_{[0,1]^{D}}p_{1}(t,u_{1},\ldots,\widehat{u_{j}},\ldots,\widehat{u_{k}},\ldots,u_{D+1})d\Lambda^{D}(u_{1},\ldots,\widehat{u_{j}},\ldots,u_{D+1})\\\
&=\int_{[0,1]^{D}}w_{j}(u_{1},\ldots,t,\ldots,u_{D+1})d\Lambda^{D}(u_{1},\ldots,\widehat{u_{j}},\ldots,u_{D+1})\
\mbox{by \eqref{equation4}}\end{split}$ (12)

where $t$ occurs in position $j$. Note that the above formula holds for any
$t$ for which

$\\{(u_{1},\ldots,u_{j-1},u_{j+1},\ldots,u_{D+1})|(u_{1},\ldots,u_{j-1},t,u_{j+1},\ldots,u_{D+1})\in
T\\}\ \mbox{has}\ \Lambda^{\times D}-\mbox{measure 1}$

i.e. it holds for $t$ in a set of $\Lambda$-measure 1.

###  6.3 ”Weight Tuples” of the Extreme Points

We claim that $\sigma_{\vec{p}}$ being an extreme point implies that
$\Lambda^{\times(D+1)}$-almost all weight tuples must be a permutation of
$(D,1,0,\ldots,0)$. That means that almost all $(D+1)$-tuples in $T$ have one
coordinate that ”dominates” the others in terms of the choice function, and
this behaviour will imply precisely that $f_{\vec{p}}$ can be approximated by
”scrambles” of $f_{MAX}$.

######  Lemma 15.

Suppose $\vec{p}$ is a consistent, single-edge strategy s.t.
$\sigma_{\vec{p}}$ is an extreme point. For $\Lambda^{\times(D+1)}$-a.a.
ordered tuples in $T$, the corresponding weight tuple is a permutation of
$(D,1,0,\ldots,0)$.

###### Proof.

We sketch the details of the proof in the case $D\geq 3$. The case $D=2$ is
similar.

Suppose the claim is false, say the set $U$ of ordered $(D+1)$-tuples
$(u_{1},\ldots,u_{D+1})\in T$ whose weight tuple $(w_{1},\ldots,w_{D+1})$ is
not a permutation of $(D,1,0,\ldots,0)$ has positive
$\Lambda^{\times(D+1)}$-measure. Note that $U$ is clearly invariant under
permutations in $S_{D+1}$.

We follow a similar approach as in the proof of Lemma 14, in that we seek
write $\vec{p}$ as a convex combination of two new single-edge strategies
$\vec{q},\vec{r}$ obtained by perturbing $\vec{p}$.

First, we further restrict $U$. There exist $a_{i}<b_{i}$ s.t. $[a_{i},b_{i}]$
are pairwise disjoint and s.t.

$U^{\prime}:=U\cap[a_{1},b_{1}]\times\cdots\times[a_{D+1},b_{D+1}]\ \mbox{has
positive $\Lambda^{\times(D+1)}$ measure}$

In this way, each coordinate in a tuple in $U^{\prime}$ cannot appear in any
other position in another tuple in $U^{\prime}$.

Now consider any $(u_{1},\ldots,u_{D+1})\in U^{\prime}$ so it has a maximal
weight $1\leq w_{K}\leq D-1$ in its weight tuple. If $w_{K}\geq 2$ then either
there exists $i\neq K$ s.t. $w_{i}\geq 2$ or there are at least two $i\neq K$
s.t. $w_{i}=1$ (this is because $\sum w_{m}=D+1$ and $w_{K}\leq D-1$). In
either case, we can pick $I\neq K$ so that the choice for
$(u_{1},\ldots,\widehat{u_{K}},\ldots,u_{D+1})$ is not $u_{I}$, hence there is
another $D$-subtuple containing $u_{K}$ for which the choice is $u_{I}$.
Furthermore, since $w_{K}\geq 2$, then there also is a $D$-subtuple containing
$u_{I}$ for which the choice is $u_{K}$. On the other hand, if $w_{K}=1$ then
$w_{m}=1\ \forall m$. If $(u_{m_{1}},\ldots,u_{m_{D}})$ is the $D$-subtuple
for which the choice is $u_{K}$ then of the remaining $D-1\geq 2$ coordinates
$u_{m_{n}}$ with $m_{n}\neq K$ at least one, call it $u_{I}$, is the choice
for a $D$-subtuple other than $(u_{1},\ldots,\widehat{u_{K}},\ldots,u_{D+1})$,
i.e. for a $D$-subtuple containing $u_{K}$.

Since this holds for all $\vec{u}\in U^{\prime}$ then there exist distinct
$1\leq I,J,K,L\leq D+1$ s.t.

$U^{\prime\prime}:=\left\\{\vec{u}\in U^{\prime}\
\middle|\begin{array}[]{l}1\leq w_{I},\ \mbox{and}\ w_{m}\leq w_{K}\ \forall
m,\ \mbox{and}\\\ \mbox{ the choice for the $D$-subtuple
$(u_{1},\ldots,\widehat{u_{J}},\ldots,u_{D+1})$ is $u_{I}$, and}\\\ \mbox{ the
choice for the $D$-subtuple $(u_{1},\ldots,\widehat{u_{L}},\ldots,u_{D+1})$ is
$u_{K}$}\end{array}\right\\}$

has positive $\Lambda^{\times(D+1)}$ measure.

The idea is that we write the weight tuples for $(D+1)$-tuples in
$U^{\prime\prime}$ as averages of two different weight tuples, and use these
new weight tuples to obtain two new non-trivial, valid single-edge strategies
whose densities average to $f_{\vec{p}}$.

Consider any $\vec{u}\in U^{\prime\prime}$. We can write the corresponding
weight tuple $(w_{1},\ldots,w_{D+1})$ as an average of two other weight
tuples:

$(\ldots,w_{I},\ldots,w_{K},\ldots)=\frac{1}{2}(\ldots,w_{I}+1,\ldots,w_{K}-1,\ldots)+\frac{1}{2}(\ldots,w_{I}-1,\ldots,w_{K}+1,\ldots)$

The weight tuple $(\ldots,w_{I}+1,\ldots,w_{K}-1,\ldots)$ can be achieved
simply by changing the choice of
$(u_{1},\ldots,\widehat{u_{L}},\ldots,u_{D+1})$ from $u_{K}$ to $u_{I}$,
whereas the weight tuple $(\ldots,w_{I}-1,\ldots,w_{K}+1,\ldots)$ can be
achieved by changing the choice of
$(u_{1},\ldots,\widehat{u_{J}},\ldots,u_{D+1})$ from $u_{I}$ to $u_{K}$. It is
trivial to see that these two new tuples are also valid weight tuples that
satisfy (11) so they correspond to new single-edge strategies
$\vec{q},\vec{r}$ respectively. By (12), we see that $f_{\vec{p}}(y)$ is the
average of $f_{\vec{q}}(y),f_{\vec{r}}(y)$.

The only difference in the $D=2$ case is that the new weight tuples are
achieved by making two changes to the choice function rather than one.

It remains to check that this average is non-trivial. Let

$V:=\\{u_{K}:\exists u_{1},\ldots,\widehat{u_{K}},\ldots,u_{D+1}\ \mbox{s.t.}\
(u_{1},\ldots,u_{D+1})\in U^{\prime\prime}\\}$

and for $x\in[0,1]$ let

$W^{x}:=\\{(u_{1},\ldots,\widehat{u_{K}},\ldots,u_{D+1}):\
(u_{1},\ldots,,u_{K-1},x,u_{K+1},\ldots,u_{D+1})\in U^{\prime\prime}\\}$

Then $\Lambda^{(D+1)\times}(U^{\prime\prime})>0$ implies $\Lambda(V)>0$ and
for $\Lambda$-a.a. $u_{K}\in V$, $\Lambda^{\times D}(W^{u_{K}})>0$.

Let us consider how the function
$w_{K}(\cdot,\ldots,\cdot,u_{K},\cdot,\ldots,\cdot):[0,1]^{D}\rightarrow\\{0,1,\ldots,D\\}$
changes from $\vec{p}$ to $\vec{r}$ for any given fixed $u_{K}\in V$. On
$W^{u_{K}}$, $w_{K}(\cdot,\ldots,\cdot,u_{K},\cdot,\ldots,\cdot)$ increases by
1 by construction of $\vec{r}$. Note that $u_{K}$ can only appear in the $K$th
coordinate of a tuple in $U^{\prime\prime}$ (by construction of
$U^{\prime\prime}$) hence $w_{K}(\cdot,\ldots,\cdot,u_{K},\cdot,\ldots,\cdot)$
either remains unchanged or increases by 1 off of $W^{u_{K}}$ (because the
only way it decreases by 1 is if $u_{K}$ had appeared at index $I$ in a tuple
in $U^{\prime\prime}$). Thus, for any $u_{K}\in V$,

$f_{\vec{r}}(u_{K})\geq f_{\vec{p}}(u_{K})+\Lambda^{\times D}(W^{u_{K}})$

by (12). It follows that $\sigma_{\vec{r}}\neq\sigma_{\vec{p}}$ so this is
indeed a non-trivial convex combination. This contradicts the assumption that
$\sigma_{\vec{p}}$ was an extreme point. Therefore
$\Lambda^{\times(D+1)}$-a.a. weight tuples must be a permutation of
$(D,1,0,\ldots,0)$. ∎

We amend our definition of ”good” $(D+1)$-tuples:

$T^{\prime}:=\\{(u_{1},\ldots,u_{D+1})\in T:(w_{1},\ldots,w_{D+1})\ \mbox{is a
perm. of }\ (D,1,0,\ldots,0)\\}$

We still have $\Lambda^{\times(D+1)}(T^{\prime})=1$ (provided of course that
$\sigma_{\vec{p}}$ is an extreme point).

We now prove the (i) $\Rightarrow$ (ii) direction of Theorem 13. We split the
proof into several claims.

######  Lemma 16.

Let $\sigma_{\vec{p}}$ be an extreme point.
(i) Suppose $(u_{1},\ldots,u_{D+1})\in T^{\prime}$ and $u_{i}$ has weight $D$
in $(u_{1},\ldots,u_{D+1})$. Then for any $1\leq j\leq D+1$, $j\neq i$ and any
$u_{j}^{\prime}$ s.t.
$(u_{1},\ldots,u_{j-1},u_{j}^{\prime},u_{j+1},\ldots,u_{D+1})\in T^{\prime}$,
either $u_{i}$ or $u_{j}^{\prime}$ has weight $D$ in
$(u_{1},\ldots,u_{j-1},u_{j}^{\prime},u_{j+1},\ldots,u_{D+1})$.

(ii) Suppose $(u_{1},u_{1}^{\prime},u_{2},\ldots,u_{D})\in T^{\prime}$. Then
in the corresponding weight tuple, $u_{1}^{\prime}$ has weight $D$ and $u_{1}$
has weight 0 if and only if

$p_{1}(u_{1},u_{2},u_{3},\ldots,u_{D})<p_{1}(u_{1}^{\prime},u_{2},u_{3},\ldots,u_{D})$

(iii) For $\Lambda^{\times 2}$-a.a. $(u_{1},u_{1}^{\prime})$, if

$p_{1}(u_{1},u_{2},u_{3},\ldots,u_{D})<p_{1}(u_{1}^{\prime},u_{2},u_{3},\ldots,u_{D})$

on a set of positive $\Lambda^{\times(D-1)}$ measure then

$p_{1}(u_{1},u_{2},u_{3},\ldots,u_{D})\leq
p_{1}(u_{1}^{\prime},u_{2},u_{3},\ldots,u_{D})$

for $\Lambda^{\times(D-1)}$-a.a. $(u_{2},\ldots,u_{D})$.

(iv) For $\Lambda^{\times 2}$-a.a. $(u_{1},u_{1}^{\prime})$, if
$f_{\vec{p}}(u_{1})\leq f_{\vec{p}}(u_{1}^{\prime})$ then

$p_{1}(u_{1},u_{2},u_{3},\ldots,u_{D})\leq
p_{1}(u_{1}^{\prime},u_{2},u_{3},\ldots,u_{D})$

for $\Lambda^{\times(D-1)}$-a.a. $(u_{2},\ldots,u_{D})$.

(v) $f_{\vec{p}}$ is not constant on any set of positive $\Lambda$ measure.

(vi) For $\Lambda^{\times D}$-a.a. $(u_{1},\ldots,u_{D})$,

$p_{1}(u_{1},\ldots,u_{D})\geq\mathbf{1}_{\\{f_{\vec{p}}(u_{1})\geq
f_{\vec{p}}(u_{i})\ \forall i\\}}$

(vii) For $\Lambda^{\times D}$-a.a. $(u_{1},\ldots,u_{D})$,

$p_{1}(u_{1},\ldots,u_{D})=\mathbf{1}_{\\{f_{\vec{p}}(u_{1})\geq
f_{\vec{p}}(u_{i})\ \forall i\\}}$

######  Remark.

We give heuristics to aid in understanding these claims:
(i) If $u_{i}$ is the dominant choice in $(u_{1},\ldots,u_{D+1})$ then $u_{i}$
can never be dominated by one of the $u_{j}$ for $i\neq j$ in tuples
containing $u_{i}$ and $u_{j}$.
(ii) Dominance can be determined by evaluating $p_{1}$.
(iii) If $u_{1}^{\prime}$ dominates $u_{1}$ once then $u_{1}^{\prime}$ almost
always dominate $u_{1}$.
(iv) The ordering imposed by domination coincides with the ordering imposed by
the values of $f_{\vec{p}}$.
(vii) $u_{1}$ is the choice in $(u_{1},\ldots,u_{D})$ if and only of $u_{1}$
maximizes the value of $f_{\vec{p}}$.

###### Proof.

(i) Let $1\leq i\leq D$ be the index for which $u_{i}$ has weight $D$ in
$(u_{1},\ldots,u_{D+1})$. Recall that this means we have the choices

$(u_{1},\ldots,\widehat{u_{\ell}},\ldots,u_{D+1})\mapsto u_{i}\
\forall\ell\neq i$

Taking $\ell=j$, this means $u_{i}$ has weight 1 or $D$ in
$(u_{1},\ldots,u_{j-1},u_{j}^{\prime},u_{j+1},\ldots,u_{D+1})$ (because this
$(D+1)$-tuple is in $T^{\prime}$). If it is $D$, we are done. If it is 1, the
fact that we have the choice

$(u_{1},\ldots,u_{j-1},u_{j+1},\ldots,u_{D+1})\mapsto u_{i}$

implies no $u_{k},k\neq j$ can have weight $D$ so $u_{j}^{\prime}$ must have
weight $D$ in
$(u_{1},\ldots,u_{j-1},u_{j}^{\prime},u_{j+1},\ldots,u_{D+1})$.

(ii) Recall that $p_{1}$ is 0-1 valued on $D$-subtuples of tuples in
$T^{\prime}$. We have the following sequence of if-and-only-if statements:

$\displaystyle
p_{1}(u_{1},u_{2},u_{3},\ldots,u_{D})<p_{1}(u_{1}^{\prime},u_{2},u_{3},\ldots,u_{D})$
$\displaystyle\Leftrightarrow
p_{1}(u_{1},u_{2},u_{3},\ldots,u_{D})=0,p_{1}(u_{1}^{\prime},u_{2},u_{3},\ldots,u_{D})=1$
$\displaystyle\Leftrightarrow(u_{1},u_{2},u_{3},\ldots,u_{D})\mapsto u_{i}\
\mbox{for some}\ 2\leq i\leq D\ \mbox{and}\
(u_{1}^{\prime},u_{2},u_{3},\ldots,u_{D})\mapsto u_{1}^{\prime}$

Now if $u_{1}^{\prime}$ has weight $D$ and $u_{1}$ has weight 0 in
$(u_{1},u_{1}^{\prime},u_{2},\ldots,u_{D}$), then we must have

$(u_{1},u_{2},u_{3},\ldots,u_{D})\mapsto u_{i}\ \mbox{for some}\ 2\leq i\leq
D\ \mbox{and}\ (u_{1}^{\prime},u_{2},u_{3},\ldots,u_{D})\mapsto
u_{1}^{\prime}$ (13)

On the other hand, if we know (13) then the weight of $u_{i}$ cannot be $D$
since the choice for $(u_{1}^{\prime},u_{2},\ldots,u_{i},\ldots,u_{D})$ is
$u_{1}^{\prime}$. Thus $u_{i}$ has weight 1, so $u_{1}^{\prime}$ has weight
$D$ and $u_{1}$ has weight 0.

(iii) Consider $u_{1},u_{1}^{\prime}$ s.t.
$(u_{1},u_{1}^{\prime},u_{2},\ldots,u_{D})\in T^{\prime}$ for
$\Lambda^{\times(D-1)}$-a.a. $(u_{2},\ldots,u_{D})$. This clearly holds for
$\Lambda^{\times 2}$-a.a. $(u_{1},u_{1}^{\prime})$ with $u_{1}\neq
u_{1}^{\prime}$. Let

$U=\\{(u_{2},\ldots,u_{D}):(u_{1},u_{1}^{\prime},u_{2},\ldots,u_{D})\in
T^{\prime},p_{1}(u_{1},u_{2},u_{3},\ldots,u_{D})<p_{1}(u_{1}^{\prime},u_{2},u_{3},\ldots,u_{D})\\}$

so $\Lambda^{\times(D-1)}(U)>0$ by assumption.

Consider any $(u_{2},\ldots,u_{D})\in U$ and $u_{2}^{\prime}$ s.t.
$(u_{1},u_{1}^{\prime},u_{2}^{\prime},u_{3},\ldots,u_{D})\in T^{\prime}$. By
(ii), $u_{1}^{\prime}$ has weight $D$ and $u_{1}$ has weight 0 in the weight
tuple for $(u_{1},u_{1}^{\prime},u_{2},u_{3},\ldots,u_{D})$. By (i), it
follows that either $u_{1}^{\prime}$ or $u_{2}^{\prime}$ has weight $D$ in
$(u_{1},u_{1}^{\prime},u_{2}^{\prime},u_{3},\ldots,u_{D})$. By the
contrapositive of (ii),

$p_{1}(u_{1},u_{2}^{\prime},u_{3},\ldots,u_{D})\leq
p_{1}(u_{1}^{\prime},u_{2}^{\prime},u_{3},\ldots,u_{D})$

Note that for $\Lambda^{\times 2}$-a.a. $(u_{1},u_{1}^{\prime})$ it is true
that for $\Lambda^{\times(D-1)}(U)>0$ of $(u_{2},\ldots,u_{D})\in U$ and
$\Lambda$-a.a. $u_{2}^{\prime}\in{\mathbb{R}}$ we have
$(u_{1},u_{1}^{\prime},u_{2}^{\prime},u_{3},\ldots,u_{D})\in T^{\prime}$ and
the inequality above holds.

We repeat this argument, ”replacing” $u_{2},u_{3},\ldots,u_{D}$ with
$\Lambda$-almost arbitrary
$u_{2}^{\prime},u_{3}^{\prime},\ldots,u_{D}^{\prime}$ and noting the invariant
that one of $u_{1}^{\prime},\ldots,u_{k}^{\prime}$ has weight of $D$ in the
weight tuple of
$(u_{1},u_{1}^{\prime},u_{2}^{\prime},\ldots,u_{k}^{\prime},u_{k+1},\ldots,u_{D})\in
T^{\prime}$ (which means we may apply (ii) to replace $u_{k+1}$ with
$\Lambda$-almost arbitrary $u_{k+1}^{\prime}$). Thus, for $\Lambda^{\times
2}$-a.a. $(u_{1},u_{1}^{\prime})$,

$p_{1}(u_{1},u_{2}^{\prime},u_{3}^{\prime},\ldots,u_{D}^{\prime})\leq
p_{1}(u_{1}^{\prime},u_{2}^{\prime},u_{3}^{\prime},\ldots,u_{D}^{\prime})$

for $\Lambda^{(D-1)}$-a.a. $(u_{2}^{\prime},\ldots,u_{D}^{\prime})$.

(iv) This follows immediately from (iii) and (7).

(v) Suppose $f_{\vec{p}}$ is constant on a set $V$ with $\Lambda(V)>0$. By
(iv), can restrict $V$ to a set $V^{\prime}$ with
$\Lambda(V^{\prime})=\Lambda(V)>0$ s.t. for all distinct
$u_{1},u_{2},\ldots,u_{D+1}\in V^{\prime}$, $(u_{1},\ldots,u_{D+1})\in
T^{\prime}$ and

$p_{1}(u_{i},u_{2},\ldots,\widehat{u_{i}},\ldots,\widehat{u_{j}},\ldots,u_{D+1})=p_{1}(u_{j},u_{2},\ldots,\widehat{u_{i}},\ldots,\widehat{u_{j}},\ldots,u_{D+1})\
\forall i,j$

We claim this is impossible.

Consider distinct $u_{1},\ldots,u_{D+1}\in V^{\prime}$. Suppose $u_{i}$ has
weight $D$ and $u_{k}$ has weight 1 in the corresponding weight tuple. Pick
$j\notin\\{i,k\\}$ (which exists since $D+1\geq 3$). Then $u_{j}$ has weight 0
in the corresponding weight tuple. But this implies the contradiction

$1=p_{1}(u_{i},u_{2},\ldots,\widehat{u_{i}},\ldots,\widehat{u_{j}},\ldots,u_{D+1})=p_{1}(u_{j},u_{2},\ldots,\widehat{u_{i}},\ldots,\widehat{u_{j}},\ldots,u_{D+1})=0$

Therefore $f_{\vec{p}}$ is not constant on any set of positive
$\Lambda$-measure.

(vi) It suffices to show that for $\Lambda$-a.a. $u_{1}$, we have

$p_{1}(u_{1},u_{2},\ldots,u_{D})=1$

for all but a $\Lambda^{\times(D-1)}$-null subset of tuples
$(u_{2},\ldots,u_{D})\in\bigg{(}f_{\vec{p}}^{-1}([0,f_{\vec{p}}(u_{1})])\bigg{)}^{D-1}$.

Suppose not, say there is a set $G$ of $u_{1}$ of $\Lambda$-positive measure
on which

$p_{1}(u_{1},u_{2},\ldots,u_{D})=0$

for a tuples $(u_{2},\ldots,u_{D})$ in a set
$H_{u_{1}}\subseteq\bigg{(}f_{\vec{p}}^{-1}([0,f_{\vec{p}}(u_{1})])\bigg{)}^{D-1}$
of $\Lambda^{\times(D-1)}$-positive measure. By (iv), for $\Lambda$-a.a.
$u_{1}\in G$,

$0=p_{1}(u_{1},u_{2},\ldots,u_{D})\geq p_{1}(u_{D+1},u_{2},\ldots,u_{D})$

for $\Lambda$-a.a. $u_{D+1}\in f_{\vec{p}}^{-1}([0,f_{\vec{p}}(u_{1})])$ and
$\Lambda^{\times(D-1)}$-a.a. $(u_{2},\ldots,u_{D})\in H_{u_{1}}$. In
particular, there exists $2\leq i\leq D$ and a subset
$H_{u_{1}}^{\prime}\subset H_{u_{1}}$ of positive $\Lambda^{D}$-measure s.t.
the choice for $(u_{1},u_{2},\ldots,u_{D})$ is $u_{i}$ and s.t. for
$\Lambda$-a.a. $u_{D+1}\in f_{\vec{p}}^{-1}([0,f_{\vec{p}}(u_{1})])$ we have

$p_{1}(u_{1},u_{2},\ldots,u_{D})=p_{1}(u_{D+1},u_{2},\ldots,u_{D})=0$ (14)

For each such tuple consider the weight of $u_{i}$ in
$(u_{1},\ldots,u_{D+1})$; it must be 1 or $D$ and if it were 1 then the choice
$(u_{1},u_{2},\ldots,u_{D})\mapsto u_{i}$ implies none of $u_{2},\ldots,u_{D}$
can have weight $D$ so $u_{D+1}$ must have weight $D$, contradicting
$p_{1}(u_{D+1},u_{2},\ldots,u_{D})=0$. Thus $u_{i}$ has weight $D$ in
$(u_{1},\ldots,u_{D+1})$ so we must have the choice
$(u_{D+1},u_{2},\ldots,u_{D})\mapsto u_{i}$. Therefore

$p_{1}(u_{i},u_{2},\ldots,u_{i-1},u_{D+1},u_{i+1},\ldots,u_{D})=1$ (15)

Since (14) holds for $\Lambda$-a.a. $u_{D+1}\in
f_{\vec{p}}^{-1}([0,f_{\vec{p}}(u_{1})])$ and $\Lambda^{\times(D-1)}$-a.a.
$(u_{2},\ldots,u_{D})\in H_{u_{1}}^{\prime}$, then there is a set of tuples
$(u_{2},\ldots,u_{D+1})$ of positive $\Lambda^{\times D}$-measure for which
(14) (hence (15)) holds for both $(u_{2},\ldots,u_{D+1})$ and
$(u_{2},\ldots,u_{i-1},u_{D+1},u_{i+1},\ldots,u_{D},u_{i})$ (i.e. it holds
with the values $u_{i},u_{D+1}$ swapped). Combining the two sets of (14), (15)
gives the contradiction

$0=p_{1}(u_{i},u_{2},\ldots,u_{i-1},u_{D+1},u_{i+1},\ldots,u_{D})=1$

(vii) By (v) and (vi), for $\Lambda^{\times D}$-a.a. $(u_{1},\ldots,u_{D})$,
$f_{\vec{p}}(u_{i})$ are distinct and

$p_{1}(u_{k},u_{1},\ldots,\widehat{u_{k}},\ldots,u_{D})\geq\mathbf{1}_{\\{f_{\vec{p}}(u_{k})\geq
f_{\vec{p}}(u_{i})\ \forall i\\}}\ \forall k$

Consider any such $(u_{1},\ldots,u_{D})$ and let $u_{k}$ maximize
$f_{\vec{p}}$. Then

$p_{1}(u_{k},u_{1},\ldots,\widehat{u_{k}},\ldots,u_{D})=\mathbf{1}_{\\{f_{\vec{p}}(u_{k})\geq
f_{\vec{p}}(u_{i})\ \forall i\\}}=1$

so the choice for $(u_{1},\ldots,u_{D})$ is $u_{k}$. It follows that for all
other $j\neq k$,

$p_{1}(u_{j},u_{1},\ldots,\widehat{u_{j}},\ldots,u_{D})=0=\mathbf{1}_{\\{f_{\vec{p}}(u_{j})\geq
f_{\vec{p}}(u_{i})\ \forall i\\}}$

We have shown that the a.s. inequality in (vi) is an a.s. equality. ∎

The next lemma shows that (ii) implies (iii) in Theorem 13.

######  Lemma 17.

Suppose $\vec{p}$ is a single-edge strategy s.t.

  1. (i)

$f_{\vec{p}}$ is not constant on any set of positive $\Lambda$ measure, and

  2. (ii)

$p_{k}(u_{1},\ldots,u_{D})=\textbf{1}_{\\{f_{\vec{p}}(u_{k})\geq
f_{\vec{p}}(u_{i})\ \forall i\\}}\ \mbox{for $\Lambda^{\times D}$-a.a.}\
(u_{1},\ldots,u_{D})\ \forall 1\leq k\leq D$

Then $\sup_{\phi}E[\sigma_{\vec{p}^{\phi}}]=E[\sigma_{MAX}]$ where the
supremum is taken over $\Lambda$-measure-preserving bijections
$\phi:[0,1]\rightarrow[0,1]$.

###### Proof.

We begin by constructing a sequence $(\phi_{n})$ of $\Lambda$-measure-
preserving bijections for which

$\mathbf{1}_{\\{f_{\vec{p}}(\phi_{n}(u_{1}))\geq f_{\vec{p}}(\phi_{n}(u_{i}))\
\forall i\\}}\rightarrow\mathbf{1}_{\\{u_{1}\geq u_{i}\ \forall i\\}}\
\mbox{$\Lambda^{\times D}$-a.s.}$ (16)

Consider any $n\in{\mathbb{N}}$. By (i), inverse images of singletons
$f_{\vec{p}}(\\{c\\})$ have $\Lambda$-measure 0. There exist $0=a_{0}^{n}\leq
a_{1}^{n}\leq\cdots\leq a_{D2^{n}}^{n}=1$ s.t.

$\Lambda([a_{i}^{n},a_{i+1}^{n}))=\Lambda\bigg{(}f_{\vec{p}}^{-1}\bigg{(}\bigg{[}\frac{i}{2^{n}},\frac{i+1}{2^{n}}\bigg{)}\bigg{)}\bigg{)}\
\forall 0\leq i\leq D2^{n}-1$ (17)

The indices stop at $D2^{n}-1$ since the range of $f_{\vec{p}}$ is a subset of
$[0,D]$. Clearly, we can make it so that the partition for $n+1$ refines the
one for $n$, for all $n$.

We construct $\phi_{n}$ by pasting together $\Lambda$-measure-preserving
bijections we get from Theorem 2 between sets

$[a_{i}^{n},a_{i+1}^{n})\rightarrow
f_{\vec{p}}^{-1}\bigg{(}\bigg{[}\frac{i}{2^{n}},\frac{i+1}{2^{n}}\bigg{)}\bigg{)}$

for $0\leq i\leq D2^{n}-1$ for which
$f_{\vec{p}}^{-1}([\frac{i}{2^{n}},\frac{i+1}{2^{n}}))$ has positive
$\Lambda$-measure. Then for each such $i$,
$f_{\vec{p}^{\phi_{n}}}=f_{\vec{p}}\circ\phi_{n}$ is a map

$[a_{i}^{n},a_{i+1}^{n})\rightarrow\bigg{[}\frac{i}{2^{n}},\frac{i+1}{2^{n}}\bigg{)}$

Let us show (16). It suffices to show that for $\Lambda^{\times 2}$-a.a.
$(u_{1},u_{2})$ we have

$\mathbf{1}_{\\{f_{\vec{p}}(\phi_{n}(u_{1}))\geq
f_{\vec{p}}(\phi_{n}(u_{2}))\\}}\rightarrow\mathbf{1}_{\\{u_{1}\geq u_{2}\\}}$

since multiplying $D-1$ of these sequences of indicators gives $\eqref{24}$.

By (i), the sets $f_{\vec{p}}^{-1}(\\{c\\})$ have $\Lambda$-measure 0 hence it
follows that for $\Lambda^{\times 2}$-a.a. $(u_{1},u_{2})$ we have
$f_{\vec{p}}(u_{1})\neq f_{\vec{p}}(u_{2})$. Consider any such $u_{1},u_{2}$.
Since $\Lambda([a_{i}^{n},a_{i+1}^{n}))\downarrow 0$ as $n\rightarrow\infty$
(because $\Lambda\ll$ Lebesgue measure), then for large enough $n$, $u_{1}$
and $u_{2}$ are in different intervals of the form $[a_{i}^{n},a_{i+1}^{n})$
and they stay in these intervals (because the partitions get progressively
more refined). Thus
$f_{\vec{p}}\circ\phi_{n}(u_{1}),f_{\vec{p}}\circ\phi_{n}(u_{2})$ are in
different intervals of the form $[\frac{i}{2^{n}},\frac{i+1}{2^{n}})$ and the
order is preserved:

$u_{1}<u_{2}\Leftrightarrow
u_{1}\in[a_{i_{1}}^{n},a_{i_{1}+1}^{n}),u_{2}\in[a_{i_{2}}^{n},a_{i_{2}+1}^{n})\
\mbox{with}\ i_{1}<i_{2}\Leftrightarrow
f_{\vec{p}}\circ\phi_{n}(u_{1})<f_{\vec{p}}\circ\phi_{n}(u_{2})$

Therefore we get (16).

Recall that $\vec{p}^{\phi_{n}}$ are themselves consistent single-edge
strategies. Using (ii) and (5), it follows that for any $t\in[0,1]$,

$\begin{split}1-F_{\vec{p}^{\phi_{n}}}(t)&=D\int_{[t,1]\times[0,1]^{D-1}}p_{1}(\phi_{n}(\vec{u}))d\Lambda^{D}(u_{1},\ldots,u_{D})\\\
&=D\int_{[t,1]\times[0,1]^{D-1}}\mathbf{1}_{\\{f_{\vec{p}}(\phi_{n}(u_{1}))\geq
f_{\vec{p}}(\phi_{n}(u_{i}))\ \forall
i\\}}d\Lambda^{D}(u_{1},\ldots,u_{D})\end{split}$ (18)

By (16) and the Bounded Convergence Theorem, this last expression converges to
the integral of the density $f_{MAX}$:

$\begin{split}&D\int_{[t,1]\times[0,1]^{D-1}}\mathbf{1}_{\\{f_{\vec{p}}(\phi_{n}(u_{1}))\geq
f_{\vec{p}}(\phi_{n}(u_{i}))\ \forall i\\}}d\Lambda^{D}(u_{1},\ldots,u_{D})\\\
&\rightarrow D\int_{[t,1]\times[0,1]^{D-1}}\mathbf{1}_{\\{u_{k}\geq u_{i}\
\forall i\\}}d\Lambda^{D}(u_{1},\ldots,u_{D})\\\
&=\int_{t}^{1}f_{MAX}(u_{1})du_{1}\\\ &=1-F_{MAX}(t)\end{split}$

But we already established that $F_{\vec{q}}\geq F_{MAX}$ for any single-edge
strategy $\vec{q}$. Therefore $F_{\vec{p}^{\phi_{n}}}\rightarrow F_{MAX}$
pointwise from below hence $E[\sigma_{\vec{p}^{\phi_{n}}}]\rightarrow
E[\sigma_{MAX}]$ by the Bounded Convergence Theorem combined with the tail
integral formula for expectation. ∎

###  6.4 Theorem 13

We wish to prove the rest of Theorem 13, but first we make some useful
observations about $\sigma_{MAX}$.

######  Lemma 18.

Let $f_{MAX}^{-}$ be the quantile function

$f_{MAX}^{-}(t)=\inf\\{x:t\leq f_{MAX}(x)\\}$

Then treating $f_{MAX}$ itself as a $[0,D]$-valued random variable on the
probability space
$([0,1],\mathcal{B}([0,1]),\Lambda)$,

$P(f_{MAX}\leq t)=f_{MAX}^{-}(t)\ \forall t$

In particular,

$P(f_{MAX}\leq f_{MAX}(y))=y\ \forall y$

###### Proof.

This is trivial since the density $f_{MAX}(y)=Dy^{D-1}$ is invertible so the
quantile function $f_{MAX}^{-}$ is just its inverse.

∎

To prove Theorem 13, we need one more short lemma exploring what
$\sup_{\phi}E[\sigma_{\vec{p}^{\phi}}]=E[\sigma_{MAX}]$ tells us.

######  Lemma 19.

Let $\vec{p}$ be a single-edge strategy and $\phi_{n}:[0,1]\rightarrow[0,1]$
be $\Lambda$-measure-preserving bijections s.t.
$E[\sigma_{\vec{p}^{\phi}}]\uparrow E[\sigma_{MAX}]$. Then there is a
subsequence $\phi_{n_{j}}$ s.t. $F_{\vec{p}^{\phi_{n_{j}}}}(y)\rightarrow
F_{MAX}(y)$,
$f_{\vec{p}^{\phi_{n_{j}}}}(y)=f_{\vec{p}}\circ\phi_{n_{j}}(y)\rightarrow
f_{MAX}(y)$ $\Lambda$-a.e. and almost uniformly on compact subsets of $[0,1]$.

###### Proof.

By the tail integral formula for expectation,

$\int_{0}^{1}F_{\vec{p}^{\phi_{n}}}(t)-F_{MAX}(t)dt=E[\sigma_{MAX}]-E[\sigma_{\vec{p}^{\phi}}]\downarrow
0$

where the integrands $F_{\vec{p}^{\phi_{n}}}(t)-F_{MAX}(t)$ are non-negative
from Lemma 10 (i), hence this is $L^{1}$ convergence. It follows that there
exists a subsequence $n_{j}$ s.t. $F_{\vec{p}^{\phi_{n_{j}}}}(t)\rightarrow
F_{MAX}(t)$ a.e. and a.u. on compact subsets of $[0,1]$. The latter
convergence gives us that $f_{\vec{p}^{\phi_{n_{j}}}}(t)\rightarrow
f_{MAX}(t)$ a.e. and a.u. on compact subsets of $[0,1]$. ∎

We are now ready to prove Theorem 13 in its entirety.

######  Theorem 13.

Let $\vec{p}$ be a single-edge strategy. The following are equivalent:

  1. (i)

$\sigma_{\vec{p}}$ is an extreme point

  2. (ii)

Any consistent single-edge strategy achieving $\sigma_{\vec{p}}$ must be
deterministic

  3. (iii)

$f_{\vec{p}}$ is not constant on sets of positive $\Lambda$-measure and
$\sigma_{\vec{p}}$ is given by the following single-edge strategy $\vec{q}$:

$q_{k}(u_{1},\ldots,u_{D})=\textbf{1}_{\\{f_{\vec{p}}(u_{k})\geq
f_{\vec{p}}(u_{i})\ \forall i\\}}\ \mbox{for $\Lambda^{\times D}$-a.a.}\
(u_{1},\ldots,u_{D})$

In other words, $\sigma_{\vec{p}}$ is achieved by the deterministic single-
edge strategy ”choose whichever label yields a higher value when evaluating
the density $f_{\vec{p}}$”

  4. (iv)

$\sup_{\phi}E[\sigma_{\vec{p}^{\phi}}]=E[\sigma_{MAX}]$

  5. (v)

For $U\sim[0,1]$ if $f_{\vec{p}}(U),f_{MAX}(U)$ as $[0,D]$-valued random
variables on the probability space $([0,1],\mathcal{B}([0,1]),\Lambda)$, then
they have the same distribution. That is,

$P(f_{\vec{p}}\leq t)=P(f_{MAX}\leq
t)=\bigg{(}\frac{t}{D}\bigg{)}^{\frac{1}{D-1}}\ \forall t\in[0,D]$

###### Proof.

(i) $\Leftrightarrow$ (ii), (i) $\Rightarrow$ (iii), (iii) $\Rightarrow$ (iv)
These are given by Lemmas 14, 16, 17.

(iv) $\Rightarrow$ (i) Suppose (iv) holds but $\sigma_{\vec{p}}$ is not an
extreme point. Since Radon-Nikodym derivatives are additive, then

$f_{\vec{p}}=\alpha f_{\vec{q}}+(1-\alpha)f_{\vec{r}}$

for $\alpha\in(0,1)$ and single-edge strategies $\vec{q},\vec{r}$ s.t.
$f_{\vec{p}}\neq f_{\vec{q}}$ on a set of positive $\Lambda$ measure.

Take $\phi_{n}$ $\Lambda$-measure-preserving bijections s.t.
$E[\sigma_{\vec{p}^{\phi_{n}}}]\uparrow E[\sigma_{MAX}]$. Then

$\alpha
E[\sigma_{\vec{q}^{\phi_{n}}}]+(1-\alpha)E[\sigma_{\vec{r}^{\phi_{n}}}]\uparrow\alpha
E[\sigma_{MAX}]+(1-\alpha)E[\sigma_{MAX}]$

where $E[\sigma_{\vec{q}^{\phi_{n}}}],E[\sigma_{\vec{r}^{\phi_{n}}}]\leq
E[\sigma_{MAX}]$. It follows that

$E[\sigma_{\vec{q}^{\phi_{n}}}],E[\sigma_{\vec{r}^{\phi_{n}}}]\uparrow
E[\sigma_{MAX}]$

By Lemma 19, there is a subsequence $\phi_{n_{j}}$ s.t.

$f_{\vec{q}}\circ\phi_{n_{j}},f_{\vec{r}}\circ\phi_{n_{j}}\rightarrow f_{MAX}$

$\Lambda$-a.e. and $\Lambda$-a.u. on compact subsets of $[0,1]$.

Since $f_{\vec{q}}\neq f_{\vec{r}}$ on a set of positive $\Lambda$-measure
then $\exists\epsilon>0$ s.t.

$Q:=\\{x:|f_{\vec{q}}(x)-f_{\vec{r}}(x)|\geq\epsilon\\}$

has measure $\delta:=\Lambda(Q)>0$. Now, by the choice of $\phi_{n_{j}}$,
there is a subset $R\subset[0,1]$ of $\Lambda$ measure $\leq\frac{\delta}{2}$
s.t. $f_{\vec{q}}\circ\phi_{n_{j}},f_{\vec{r}}\circ\phi_{n_{j}}\rightarrow
f_{MAX}$ uniformly on $[0,1]\setminus R$. In particular, $\exists
J\in{\mathbb{N}}$ s.t. for all $j\geq J$ and $y\in[0,1]\cap R$ we have

$|f_{\vec{q}}\circ\phi_{n_{j}}(y)-f_{MAX}(y)|,|f_{\vec{r}}\circ\phi_{n_{j}}(y)-f_{MAX}(y)|<\frac{\epsilon}{2}\Rightarrow|f_{\vec{q}}\circ\phi_{n_{j}}(y)-f_{\vec{r}}\circ\phi_{n_{j}}(y)|<\epsilon$

Thus

$\phi_{n_{J}}([0,1]\setminus R)\subseteq[0,1]\setminus Q$ (19)

But $\phi_{n_{J}}$ is $\Lambda$-measure-preserving and

$\displaystyle\Lambda(\phi_{n_{J}}([0,1]\setminus R))$
$\displaystyle=\Lambda([0,1])-\Lambda(R)$
$\displaystyle\geq\Lambda([0,1]-\frac{\delta}{2}$
$\displaystyle>\Lambda([0,1])-\Lambda(Q)$
$\displaystyle=\Lambda([0,1]\setminus Q)$

Contradiction of (19). Therefore $\sigma_{\vec{p}}$ is an extreme point.

(iv) $\Rightarrow$ (v) Take $\phi_{n}$ $\Lambda$-measure-preserving bijections
s.t. $E[\sigma_{\vec{p}^{\phi_{n}}}]\uparrow E[\sigma_{MAX}]$. By Lemma 19
there is a subsequence $\phi_{n_{j}}$ s.t.
$f_{\vec{p}^{\phi_{n_{j}}}}=f_{\vec{p}}\circ\phi_{n_{j}}\rightarrow f_{MAX}$
$\Lambda$-a.e and a.u. on compact subsets of $[0,1]$.

Now for any $z\in[0,1]$,

$P(f_{\vec{p}}\leq
z)=\Lambda(f_{\vec{p}}^{-1}([0,z]))=\Lambda((f_{\vec{p}^{\phi_{n_{j}}}})^{-1}([0,z]))$

We claim this last expression equals
$\Lambda(f_{MAX}^{-1}([0,z]))=P(f_{MAX}\leq z)$.

Suppose $P(f_{\vec{p}}\leq z)\neq P(f_{MAX}\leq z)$ for some $z$, say
$P(f_{\vec{p}}\leq z)<\Lambda(f_{MAX}^{-1}([0,z]))$; the $>$ case is very
similar. By continuity from below and since
$\Lambda(f_{MAX}^{-1}(\\{z\\}))=0$, there exists $\delta>0$ s.t.

$\Lambda(f_{\vec{p}}^{-1}([0,z]))<\Lambda(f_{MAX}^{-1}([0,z-\delta]))$

By a.u. convergence on $[0,1]$, there is a subset $R\subset[0,1]$ off of which
$f_{\vec{p}}\circ\phi_{n_{j}}\rightarrow f_{MAX}$ uniformly s.t. $\Lambda(R)$
is sufficiently small so that for all $j$,

$\Lambda((f_{\vec{p}}\circ\phi_{n_{j}})^{-1}([0,z]))=\Lambda(f_{\vec{p}}^{-1}([0,z]))<\Lambda(f_{MAX}^{-1}([0,z-\delta])\cap[0,1]\setminus
R)$ (20)

Uniform convergence gives a $J$ s.t. for all $j\geq J$ and all $t\in
f_{MAX}^{-1}([0,z-\delta])\cap[0,1]\setminus R$,

$f_{\vec{p}}\circ\phi_{n_{j}}(t)\in(f_{MAX}(t)-\delta,f_{MAX}(t)+\delta)\cap[0,\infty)\subseteq[0,z]$

(here we use the fact that $f_{\vec{p}}$ is a non-negative function). Thus

$f_{MAX}^{-1}([0,z-\delta])\cap[0,1]\setminus
R\subseteq(f_{\vec{p}}\circ\phi_{n_{j}})^{-1}([0,z])$

which is a contradiction of (20). Therefore

$P(f_{\vec{p}}\leq z)=P(f_{MAX}\leq z)=f_{MAX}^{-}(z)$

where the last inequality holds by Lemma 18. The expression on the right is
precisely $(\frac{z}{D})^{\frac{1}{D-1}}$.

(v) $\Rightarrow$ (iv) We construct $\Lambda$-measure-preserving bijections
$\phi_{n}:[0,1]\rightarrow[0,1]$ s.t.
$E[\sigma_{\vec{p}^{\phi_{n}}}]\rightarrow E[\sigma_{MAX}]$.

Consider any $n$. By (v) combined with Lemma 18, for any
$z\in\\{0,1,\ldots,2^{n}-1\\}$ we have

$\displaystyle\Lambda\bigg{(}f_{\vec{p}}^{-1}\bigg{(}\bigg{[}f_{MAX}\bigg{(}\frac{z}{2^{n}}\bigg{)},f_{MAX}\bigg{(}\frac{z+1}{2^{n}}\bigg{)}\bigg{)}\bigg{)}\bigg{)}$
$\displaystyle=P\bigg{(}f_{MAX}\bigg{(}\frac{z}{2^{n}}\bigg{)}\leq
f_{\vec{p}}<f_{MAX}\bigg{(}\frac{z+1}{2^{n}}\bigg{)}\bigg{)}$
$\displaystyle=P\bigg{(}f_{MAX}\bigg{(}\frac{z}{2^{n}}\bigg{)}\leq
f_{MAX}<f_{MAX}\bigg{(}\frac{z+1}{2^{n}}\bigg{)}\bigg{)}$
$\displaystyle=\Lambda\bigg{(}\bigg{[}\frac{z}{2^{n}},\frac{z+1}{2^{n}}\bigg{)}\bigg{)}$

We construct $\phi_{n}$ by pasting together $\Lambda$-measure-preserving
bijections we get from Theorem 2 between sets

$\bigg{[}\frac{z}{2^{n}},\frac{z+1}{2^{n}}\bigg{)}\rightarrow
f_{\vec{p}}^{-1}\bigg{(}\bigg{[}f_{MAX}\bigg{(}\frac{z}{2^{n}}\bigg{)},f_{MAX}\bigg{(}\frac{z+1}{2^{n}}\bigg{)}\bigg{)}\bigg{)}$

Then for each $z$, $f_{\vec{p}^{\phi_{n}}}=f_{\vec{p}}\circ\phi_{n}$ is a map

$\bigg{[}\frac{z}{2^{n}},\frac{z+1}{2^{n}}\bigg{)}\rightarrow\bigg{[}f_{MAX}\bigg{(}\frac{z}{2^{n}}\bigg{)},f_{MAX}\bigg{(}\frac{z+1}{2^{n}}\bigg{)}\bigg{)}$

We now compute the expectation of each $X(\vec{p}^{\phi_{n}})$:

$\displaystyle E[X(p^{MAX})]$ $\displaystyle\geq E[X_{0}(\vec{p}^{\phi_{n}})]$
$\displaystyle=\sum_{z=0}^{2^{n}-1}\int_{\frac{z}{2^{n}}}^{\frac{z+1}{2^{n}}}f_{\vec{p}}(\phi_{n}(t))t\
dt$
$\displaystyle\geq\sum_{z=0}^{2^{n}-1}\int_{\frac{z}{2^{n}}}^{\frac{z+1}{2^{n}}}f_{MAX}\bigg{(}\frac{z}{2^{n}}\bigg{)}t\
dt$

But $f_{MAX}(t)t$ is nondecreasing hence is of bounded variation on $[0,1]$
hence this lower bound converges to $E[X(p^{MAX})]$ as $n\rightarrow\infty$.
Thus

$E[\sigma_{MAX}]=E[X(p^{MAX})]=\sup_{n}E[X(\vec{p}^{\phi_{n}})]=\sup_{\phi}E[\sigma_{\vec{p}^{\phi}}]$

as desired. ∎

By the Krein-Milman Theorem, $\mathcal{R}$ is exactly the closed convex hull
of its extreme points. Thus we obtain a description of the set of limit points
of empirical measures.

As a final remark, observe that we only used the compactness of the space
$\mathcal{M}_{1}$ of probability measures on [0,1] to reduce from generic
strategies to single-edge strategies. Furthermore, the fact that $\Lambda$ has
nice formulas for its cdf and pdf was convenient but unnecessary. The proof of
this theorem could be tweaked to hold with $\Lambda$ replaced by an arbitrary
distribution $\theta$ on ${\mathbb{R}}$ with finite mean. We could thus get a
similar characterization for the extreme points of
$\\{\sigma_{\psi}:\mbox{single-edge strategies}\ \psi\\}$. The only caveats
would be that this set might not coincide with $\\{\mbox{limit points of }\
\frac{1}{n}\mu_{0\rightarrow n}(\chi):\ \mbox{strategies}\ \chi\\}$ and that
the value distribution of the densities $f_{\vec{p}}$ of extreme points might
not have as nice a form as $D\cdot Beta(1,D)$.

###  6.5 The Discrete Case with Example

The same argument with the weight tuples can be used to show a discrete
version of Theorem 13, where the i.i.d. labels $U^{j}$ are
$Unif\\{1,\ldots,K\\}$.

######  Theorem 13’.

Let $\vec{p}$ be a single-edge strategy. The following are equivalent

  1. (i)

$\sigma_{\vec{p}}$ is an extreme point

  2. (ii)

Any consistent single-edge strategy achieving $\sigma_{\vec{p}}$ must be
deterministic.

  3. (iii)

$\sigma_{\vec{p}}$ is given by the single-edge strategy ”choose whichever
label is maximal with respect to the ordering $\alpha(1)<\cdots<\alpha(K)$”
for some $\alpha\in S_{K}$.

  4. (iv)

There exists a permutation $\beta\in S_{K}$ s.t.
$\vec{p}(\beta(\vec{u}))=\vec{p}^{MAX}(\vec{u})\ \forall\vec{u}$.

  5. (v)

$\sigma_{\vec{p}}$ has a probability mass function whose value distribution is

$\bigg{\\{}\frac{1}{K^{D}},\frac{2^{D}-1}{K^{D}},\frac{3^{D}-2^{D}}{K^{D}},\ldots,\frac{K^{D}-(K-1)^{D}}{K^{D}}\bigg{\\}}$

Let us begin by highlighting the main differences between Theorems 13 and 13’.
In the continuous case, the extreme points are those $\sigma_{\vec{p}}$
achieved by the deterministic single-edge strategy of choosing whichever
$u_{i}$ maximizes the value of the density $f_{\vec{p}}$, or equivalently
those $\sigma_{\vec{p}}$ whose density has the same value distribution as
$\sigma_{MAX}=Dx^{D-1}dx$ (namely $D\cdot\mbox{Beta}(1,D)$). Contrast this
with the discrete case, where the extreme points are those $\sigma_{\vec{p}}$
achieved by the deterministic single-edge strategy of choosing whichever
$u_{i}$ maximizes the value of the probability mass function, or equivalently
those $\sigma_{\vec{p}}$ whose pmf has the same value distribution as
$\sigma_{MAX}=\frac{1}{K^{D}}\delta_{1}+\frac{2^{D}-1}{K^{D}}\delta_{2}+\cdots+\frac{K^{D}-(K-1)^{D}}{K^{D}}\delta_{K}$.
Furthermore, in the discrete case, if we write the extremal $\sigma_{\vec{p}}$
as

$\sigma_{\vec{p}}=\frac{1}{K^{D}}\delta_{\alpha(1)}+\frac{2^{D}-1}{K^{D}}\delta_{\alpha(2)}+\cdots+\frac{K^{D}-(K-1)^{D}}{K^{D}}\delta_{\alpha(K)}$

for some permutation $\alpha\in S_{K}$ then clearly the single-edge strategy
of choosing whichever $u_{i}$ maximizes the value of the pmf can be
equivalently described as the single-edge strategy of choosing whichever
$u_{i}$ is maximal according to the ordering
$\alpha(1)<\alpha(2)<\cdots<\alpha(K)$. It is easy to see that this $\alpha$
satisfies $\vec{p}(\alpha^{-1}(\vec{u}))=\vec{p}^{MAX}(\vec{u})$ (which is
where (iv) above comes from).

In the discrete setting, the existence of this $\alpha\in S_{K}$ leads to a
natural bijection between the extreme points of the permutohedron and of
$\mathcal{R}$, the set of achievable distributions $\\{\sigma_{\vec{p}}\\}$,
by mapping $\sigma_{\vec{p}}$ to the ordering $\alpha(1)<\cdots<\alpha(K)$
associated with it.

Since convex combinations of single-edge strategies translate to convex
combinations of the distributions $\sigma_{\vec{p}}$ then this bijection
extends to a bijection between the permutohedron and $\mathcal{R}$. Of course,
the permutohedron is the same for different $D$ but the bijection depends on
$D$.

It is also worth noting that our proof of Theorem 13 adapted to this discrete
setting becomes much simpler and more intuitive. Recall we showed that a
consistent and deterministic single-edge strategy is one which induces an
ordering on the possible values of the edge labels in the sense that $y$
”dominates” $x$ if and only if the choice for $\vec{u}$ is never $x$ if both
$x$ and $y$ appear in $\vec{u}$. In the discrete case, there are only $K$
possible values of the edge labels so immediately this gives the ordering
$\alpha(1)<\cdots<\alpha(K)$ from which Theorem 13’ follows.

As an example, let us briefly work through the $D=2,K=4$ discrete case.

Figure 2: Permutohedron of order 4, [Hol]

The bijection between the extreme points of the permutohedron of order 4 and
the extreme points of the set of consistent single-edge strategies goes as
follows:

$1342\mapsto\sigma_{1342}=\frac{1}{16}\delta_{1}+\frac{2^{2}-1}{16}\delta_{3}+\frac{3^{2}-2^{2}}{16}\delta_{4}+\frac{4^{2}-3^{2}}{16}\delta_{2}$

where $\sigma_{1342}$ is the distribution obtained by choosing whichever of
the samples $u^{1},u^{2}\in\\{1,2,3,4\\}$ is maximal with respect to the
ordering $1<3<4<2$.

It is plain to see that all the deterministic consistent single-edge
strategies correspond to such an ordering, and the corresponding distribution
has a pmf with the same value distribution
$\\{\frac{1}{16},\frac{3}{16},\frac{5}{16},\frac{7}{16}\\}$.

##  7 Grid Entropy in this Model

In this short section, we compute the grid entropy of the extreme points
described in the previous section and we describe grid entropy in general
using a simplified formula for the Gibbs Free Energy.

###  7.1 Grid Entropy of Extreme Points

Recall that the extreme points of $\\{\sigma_{\vec{p}}\\}$ are given by the
single-edge strategy of choosing whichever edge label maximizes the density
$f_{\vec{p}}$. We show that such extreme points $\sigma_{\vec{p}}$ have grid
entropy 0.

However, we first need a short lemma about the partial averages of the
expectations of order statistics being bounded away from 0.

######  Lemma 20.

Let $Z_{i}\sim\theta,i\geq 0$ be i.i.d. random variables s.t. $\theta$ is a
distribution on ${\mathbb{R}}$ with cdf $F_{\theta}$ satisfying
$F_{\theta}(0)=0$. Consider the order statistics $Z_{0:n}\leq\cdots\leq
Z_{n:n}$. Then there exists a constant $C>0$ s.t. for large enough $n$,

$\frac{1}{n}\sum_{k=0}^{\lfloor n\epsilon\rfloor}E[Z_{k:n}]\geq C$

######  Remark.

We allow for the case where some of these expected values may be $\infty$.

###### Proof.

Observe that half the terms in this sum are bounded below by
$E[Z_{\lfloor\frac{n\epsilon}{2}\rfloor:n}]$ hence

$\frac{1}{n}\sum_{k=0}^{\lfloor
n\epsilon\rfloor}E[Z_{k:n}]\geq\frac{1}{n}\bigg{\lfloor}\frac{n\epsilon}{2}\bigg{\rfloor}E[Z_{\lfloor\frac{n\epsilon}{2}\rfloor:n}]$

Thus it suffices to find $C>0$ s.t. for large $n$,
$E[Z_{\lfloor\frac{n\epsilon}{2}\rfloor:n}]\geq\frac{1}{2}C$.

By right-continuity of the cdf $F_{\theta}$, we can take $C>0$ s.t.
$F_{\theta}(C)\leq\frac{1}{8}\epsilon$.

Consider the i.i.d. Bernoulli random variables $\textbf{1}_{\\{Z_{i}\leq
C\\}}$ with success probability $F_{\theta}(C)$. Then Markov’s Inequality
yields

$P(Z_{\lfloor\frac{n\epsilon}{2}\rfloor:n}\leq C)=P\bigg{(}\\#\mbox{successes
in
Bin($n,F_{\theta}(C)$)}\geq\bigg{\lfloor}\frac{n\epsilon}{2}\bigg{\rfloor}\bigg{)}\leq\frac{nF_{\theta}(C)}{\lfloor\frac{n\epsilon}{2}\rfloor}\leq\frac{1}{2}$

for large $n$ by the choice of $C$. It follows that

$E[Z_{\lfloor\frac{n\epsilon}{2}\rfloor:n}]\geq\frac{1}{2}C$

for large $n$, which completes the proof. ∎

######  Theorem 21.

Fix $\tau:[0,1]\rightarrow{\mathbb{R}}$ measurable and bounded s.t. $\tau$ is
not constant on sets of positive $\Lambda$ measure, and consider the single-
edge strategy of picking the maximal $\tau(U^{j})$ over $1\leq j\leq D$, given
by

$\vec{p}(u_{1},\ldots,u_{D})=\textbf{1}_{\\{\tau(u_{k})\geq\tau(u_{i})\
\forall i\\}}$

Then $||\sigma_{\vec{p}}||=0$.

######  Remark.

The types of strategies considered in this theorem are deterministic so the
resulting $\sigma_{\vec{p}}$ are all extreme points by Theorem 13. On the
other hand, Theorem 13 establishes that all extreme points can be realized as
$\sigma_{\vec{p}}$ for a single-edge strategy $\vec{p}$ choosing whichever
observed label maximizes the density $f_{\vec{p}}\in[0,D]$ where
$f_{\vec{p}}(\mbox{Unif}[0,1])$ is the $D\cdot\mbox{Beta}(D,1)$ distribution.
Thus Theorem 21 captures what happens for all extreme points.

###### Proof.

Suppose $||\sigma_{\vec{p}}||>\delta>0$. Let $\alpha=\frac{\delta}{\ln 2}$.
For $n\in{\mathbb{N}}$ and $1\leq m_{n}\leq\lfloor e^{n\delta}\rfloor=\lfloor
2^{n\alpha}\rfloor$ consider the event-dependent paths $\pi_{n,m_{n}}$
corresponding to

$\min_{\pi:0\rightarrow
n}^{m_{n}}\rho\bigg{(}\frac{1}{n}\mu_{\pi},\sigma_{\vec{p}}\bigg{)}$

Since $\delta<||\sigma_{\vec{p}}||$ then by definition of grid entropy,

$\min_{\pi:0\rightarrow n}^{\lfloor
e^{n\delta}\rfloor}\rho\bigg{(}\frac{1}{n}\mu_{\pi},\sigma_{\vec{p}}\bigg{)}\rightarrow
0\ \mbox{a.s.}$

hence $\frac{1}{n}\mu_{\pi_{n,m_{n}}}\Rightarrow\sigma_{\vec{p}}$ a.s.
regardless of the sequence $(m_{n})$.

Also for $i\geq 0$ define the random variables

$Y_{i}:=\max\limits_{1\leq j\leq
D}(\tau(U_{i}^{j})),Y_{i}^{\prime}=\mbox{2nd}\ \max\limits_{1\leq j\leq
D}(\tau(U_{i}^{j})),Z_{i}:=Y_{i}-Y_{i}^{\prime}$

Now it is a classic result that for $\epsilon>0$,

$\sum_{i=0}^{\lfloor n\epsilon\rfloor}\binom{n}{i}\leq 2^{nL}\ \mbox{with}\
L=L(\epsilon)=\epsilon\log\epsilon+(1-\epsilon)\log(1-\epsilon)$

Take $\epsilon>0$ small enough so that $L+\epsilon\log(D-1)<\frac{1}{2}\alpha$
and take $N\in{\mathbb{N}}$ so that $\forall n\geq N$,
$2^{nL}(D-1)^{n\epsilon}<\lfloor 2^{n\alpha}\rfloor$.

Consider any $n\geq N$. Then the number of paths $\pi:0\rightarrow n$ with
$<\lceil n\epsilon\rceil$ of its edges not having the maximal edge label in
their trial is at most

$\sum_{i=0}^{\lfloor n\epsilon\rfloor}\binom{n}{i}(D-1)^{i}\leq
2^{nL}(D-1)^{n\epsilon}<\lfloor 2^{n\alpha}\rfloor$

By the Pigeonhole Principle, there is an event-dependent path
$\pi_{n,m_{n}}:\vec{0}\rightarrow n$ s.t. at least $\lceil n\epsilon\rceil$ of
its edges do not have the maximal edge label in their trial. Let
$\pi_{n,m_{n}}$ have edges $e_{0}^{j_{0}},\ldots,e_{n-1}^{j_{n-1}}$ and let
$I_{n}\subseteq\\{0,\ldots,n-1\\},|I_{n}|=\lceil n\epsilon\rceil$ be a set of
indices $i$ for which $\tau(U_{i}^{j_{i}})\neq Y_{i}$.

We compute an upper bound for the passage time along $\pi_{n,m_{n}}$ (with
respect to $\tau$) by splitting the sum over the edges with index in $I_{n}$
and those not in $I_{n}$:

$\displaystyle\langle\tau,\frac{1}{n}\mu_{\pi_{n,m_{n}}}\rangle$
$\displaystyle=\frac{1}{n}\sum_{i=0}^{n-1}\tau(U_{i}^{j_{i}})$
$\displaystyle\leq\frac{1}{n}\sum_{i\in I_{n}^{C}}\max_{1\leq j\leq
D}(\tau(U_{i}^{j}))+\frac{1}{n}\sum_{i\in I_{n}}\mbox{2nd}\max_{1\leq j\leq
D}(\tau(U_{i}^{j}))$ $\displaystyle=\frac{1}{n}\sum_{i\in
I_{n}^{C}}Y_{i}+\frac{1}{n}\sum_{i\in I_{n}}Y_{i}^{\prime}$

On the other hand, the passage time along the $\tau$-optimal path
$\pi_{0\rightarrow n}(\vec{p})$ is

$\langle\tau,\frac{1}{n}\mu_{\pi_{n}(\vec{p})}\rangle=\frac{1}{n}\sum_{i=0}^{n-1}\max_{1\leq
j\leq D}(\tau(U_{i}^{j}))=\frac{1}{n}\sum_{i=0}^{n-1}Y_{i}$

hence

$\langle\tau,\frac{1}{n}\mu_{\pi_{n}(\vec{p})}\rangle-\langle\tau,\frac{1}{n}\mu_{\pi_{n,m_{n}}}\rangle\geq\frac{1}{n}\sum_{i\in
I_{n}}(Y_{i}-Y_{i}^{\prime})=\frac{1}{n}\sum_{i\in
I_{n}}Z_{i}\geq\frac{1}{n}\sum_{k=0}^{\lfloor n\epsilon\rfloor}Z_{k:n}$ (21)

Now $Z_{i}$ are i.i.d., non-negative and satisfy

$\displaystyle P(Z_{i}=0)$ $\displaystyle=P\bigg{(}\max\limits_{1\leq j\leq
D}(\tau(U_{i}^{j}))=\mbox{2nd}\ \max\limits_{1\leq j\leq
D}(\tau(U_{i}^{j}))\bigg{)}$ $\displaystyle\leq P(\exists 1\leq
j_{1}<j_{2}\leq D\ \mbox{s.t.}\ \tau(U_{i}^{j_{1}})=\tau(U_{i}^{j_{2}}))$
$\displaystyle=0$

since $\tau$ is not constant on sets of positive $\Lambda$ measure. Thus we
can take the expectation in (21) and apply Lemma 20 to get that $\exists C>0$
s.t.

$E\bigg{[}\langle\tau,\frac{1}{n}\mu_{\pi_{n}(\vec{p})}\rangle-\langle\tau,\frac{1}{n}\mu_{\pi_{n,m_{n}}}\rangle\bigg{]}\geq\frac{1}{n}\sum_{k=0}^{\lfloor
n\epsilon\rfloor}E[Z_{k:n}]\geq C$ (22)

for large $n$.

Now, by assumption,
$\frac{1}{n}\mu_{\pi_{n,m_{n}}}\Rightarrow\sigma_{\vec{p}}$ a.s.. On the other
hand, by nature of the model, the $\tau$-optimal length $m$ path
$\pi_{m}(\vec{p})$ contains the $\tau$-optimal length $n$ path
$\pi_{n}(\vec{p})$ for any $m\geq n$; thus we can apply the Glivenko-Cantelli
Theorem (Theorem 7) to get that the empirical measures
$\frac{1}{n}\mu_{\pi_{n}(\vec{p})}$ converge weakly to $\sigma_{\vec{p}}$
a.s.. Recall from Section 3.2 that a.s. the pushforward $\tau_{\ast}$
preserves weak limits of empirical measures so

$\displaystyle\langle\tau,\frac{1}{n}\mu_{\pi_{n}(\vec{p})}\rangle-\langle\tau,\frac{1}{n}\mu_{\pi_{n,m_{n}}}\rangle$
$\displaystyle=\langle
1,\tau_{\ast}(\frac{1}{n}\mu_{\pi_{n}(\vec{p})})\rangle-\langle
1,\tau_{\ast}(\frac{1}{n}\mu_{\pi_{n,m_{n}}})\rangle$
$\displaystyle\rightarrow\langle
1,\tau_{\ast}(\sigma_{\vec{p}})\rangle-\langle
1,\tau_{\ast}(\sigma_{\vec{p}})\rangle$ $\displaystyle=0$

a.s.. But $\tau$ is bounded so by the Bounded Convergence Theorem we get

$E\bigg{[}\langle\tau,\frac{1}{n}\mu_{\pi_{n}(\vec{p})}\rangle-\langle\tau,\frac{1}{n}\mu_{\pi_{n,m_{n}}}\rangle\bigg{]}=0$

which contradicts (22). Thus $||\sigma_{\vec{p}}||=0$. ∎

###  7.2 Grid Entropy via Gibbs Free Energy

Fix $\beta>0$. Suppose $\tau:[0,1]\rightarrow{\mathbb{R}}$ is a bounded
measurable function. From the definition of $\beta$-Gibbs Free Energy,

$G^{\beta}(\tau):=\lim_{n\rightarrow\infty}\frac{1}{n}\log\sum_{\pi:0\rightarrow
n}e^{\beta
T(\pi)}=\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=0}^{n-1}\log\sum_{j=1}^{D}e^{\beta\tau(U_{i}^{j})}\
\mbox{a.s.}$

But $\log\sum\limits_{j=1}^{D}e^{\beta\tau(U_{i}^{j})}$ are i.i.d. in $i$
hence by the SLLN,

$G^{\beta}(\tau)=E\bigg{[}\log\sum_{j=1}^{D}e^{\beta\tau(U^{j})}\bigg{]}\
\mbox{a.s.}$

where $U^{j}$ are i.i.d. Unif[0,1].

Of course, grid entropy is simply the negative convex conjugate of
$\beta$-Gibbs Free Energy by Theorem 1:

$-||\nu||=\sup_{\tau}\bigg{[}\beta\langle\tau,\nu\rangle-G^{\beta}(\tau)\bigg{]}=\sup_{\tau}\bigg{[}\beta\langle\tau,\nu\rangle-E\bigg{[}\log\sum_{j=1}^{D}e^{\beta\tau(U^{j})}\bigg{]}\bigg{]}\
\forall\nu\in\mathcal{M}$ (23)

where the supremum is over bounded measurable functions
$\tau:[0,1]\rightarrow{\mathbb{R}}$ and where $\langle\tau,\nu\rangle$ denotes
the integral $\int_{0}^{1}\tau(u)d\nu$.

##  8 Next Steps

We have characterized the extreme points of the set of limit points of
empirical measures and have shown that these extreme points have grid entropy
0. A natural next question is whether only the extreme points have grid
entropy 0.

Recalling that grid entropy is concave, another key question to ask is whether
it is strictly concave in the model used in this paper; this might provide
insights on whether it is strictly concave in general, which would imply that
the Gibbs Free Energy is strictly concave, a major open research problem.

Furthermore, it would be nice to compute grid entropy of non-extremal points,
and also try to describe the subset of $\mathcal{R}$ of maximizers for the
variational formula for the Gibbs Free Energy presented in Section 5.2 of
[Gat22].

These are all questions well worth exploring in the future.

##  9 Acknowledgments

I would like to thank my friends and family for their continual support during
my graduate studies. Special thanks goes to my advisor Bálint Virág, for his
patience, guidance, and optimism in the face of setbacks. Finally, this work
would not have been possible without the funding from my NSERC Canadian
Graduate Scholarship-Doctoral.

## References

  * [Bat20] Erik Bates, _Empirical distributions, geodesic lengths, and a variational formula in first-passage percolation_ , arXiv preprint:2006.12580 (2020).
  * [Car10] Philippe Carmona, _Directed polymer in random environment and last passage percolation_ , ESAIM: Probability and Statistics 14 (2010), 263–270.
  * [Dur19] Rick Durrett, _Probability: theory and examples_ , vol. 49, Cambridge university press, 2019.
  * [Gat22] Alexandru Gatea, _Grid entropy in last passage percolation — a superadditive critical exponent approach_ , arXiv:2209.14478 (2022).
  * [Hol] Alexander E. Holroyd, _A sorting networks picture gallery_ , https://personal.math.ubc.ca/~holroyd/sort/ [Accessed: July 2022].
  * [Lei20] Jing Lei, _Convergence and concentration of empirical measures under wasserstein distance in unbounded functional spaces_ , Bernoulli 26 (2020), no. 1, 767–798.
  * [LP20] Yating Liu and Gilles Pagès, _Convergence rate of optimal quantization and application to the clustering performance of the empirical measure._ , J. Mach. Learn. Res. 21 (2020), no. 86, 1–36.
  * [MSZ21] James B Martin, Allan Sly, and Lingfu Zhang, _Convergence of the environment seen from geodesics in exponential last-passage percolation_ , arXiv preprint:2106.05242 (2021).
  * [Nis98] Togo Nishiura, _Measure-preserving maps of $\mathbb{R}^{n}$_, Real Analysis Exchange (1998), 837–842.
  * [RAS14] Firas Rassoul-Agha and Timo Seppäläinen, _Quenched point-to-point free energy for random walks in random potentials_ , Probability Theory and Related Fields 158 (2014), no. 3, 711–750.
  * [Rie21] Adrian Riekert, _Wasserstein convergence rate for empirical measures of markov chains_ , arXiv preprint:2101.06936 (2021).
  * [Wel81] Jon A Wellner, _A glivenko-cantelli theorem for empirical measures of independent but non-identically distributed random variables_ , Stochastic Processes and their Applications 11 (1981), no. 3, 309–312.