11institutetext: Department of Engineering, University of Cambridge, 11email:
<EMAIL_ADDRESS>22institutetext: Statistical Laboratory, University of
Cambridge, 22email<EMAIL_ADDRESS>
# The Feature-First Block Model

Lawrence Tray 11 Ioannis Kontoyiannis 22

###### Abstract

Labelled networks are an important class of data, naturally appearing in
numerous applications in science and engineering. A typical inference goal is
to determine how the vertex labels (or features) affect the network’s
structure. In this work, we introduce a new generative model, the feature-
first block model (FFBM), that facilitates the use of rich queries on labelled
networks. We develop a Bayesian framework and devise a two-level Markov chain
Monte Carlo approach to efficiently sample from the relevant posterior
distribution of the FFBM parameters. This allows us to infer if and how the
observed vertex-features affect macro-structure. We apply the proposed methods
to a variety of network data to extract the most important features along
which the vertices are partitioned. The main advantages of the proposed
approach are that the whole feature-space is used automatically and that
features can be rank-ordered implicitly according to impact.

###### Keywords:

Stochastic Block Model Labelled Networks Inference.

##  1 Introduction

Many real-world networks exhibit strong community structure, with most nodes
belonging to densely connected clusters. Finding ways to recover the latent
communities from the observed graph is an important task in many applications,
including compression [1] and link prediction [4]. In this work, we examine
vertex-labelled networks, referring to the labels as features. A typical goal
is to determine whether a given feature impacts graphical structure. Answering
this requires a random graph model; the standard is the stochastic block model
(SBM) [7]. Numerous variants of the SBM have been proposed, e.g., the MMSBM
[2] and OSBM [14], but these do not include features in the graph generation
process.

To analyse a labelled network using one of the simple SBM variants, a typical
procedure would be to partition the graph into blocks grouped by distinct
values of the feature of interest. The associated model can then be used to
test for evidence of heterogeneous connectivity between the feature-grouped
blocks. Nevertheless, this approach can only consider disjoint feature sets
and the feature-grouped blocks are often an unnatural partition of the graph.

We would instead prefer to partition the graph into its most natural blocks
and then find which of the available features – if any – best predict the
resulting partition. Thus motivated, we present a novel framework for
modelling labelled networks, which we call the feature-first block model
(FFBM). This is an extension of the SBM to labelled networks.

##  2 Preliminaries

We first need a model for community-like structure in a network. For this we
adopt the widely-used stochastic block model (SBM). This is a latent variable
model where each vertex belongs to a single block and the probability two
vertices are connected depends only on the block memberships of each.
Specifically, we will use the microcanonical variant of the SBM, proposed by
Peixoto [10]. To allow for degree-variability between members of the same
block, we adopt the following degree-corrected formulation (DC-SBM):

######  Definition 1 (Microcanonical DC-SBM)

Let $N\geq 1$ denote the number of vertices in an undirected graph with $E$
edges. The block memberships are encoded by a vector $b\in[B]^{N}$, where $B$
is the number of non-empty blocks.111For each integer $K\geq 1$, we use the
notation $[K]:=\\{1,2,\ldots,K\\}$. Let $e=(e_{rs})$ be the $B\times B$
symmetric matrix of edge counts between blocks, such that $e_{rs}$ is the
number of edges from block $r$ to block $s$. Let $k=(k_{i})$ denote a vector
of length $N$, with $k_{i}$ being the degree of vertex $i$.

The graph’s adjacency matrix $A\in\\{0,1\\}^{N\times N}$ is generated by
placing edges uniformly at random, conditional on the constraints imposed by
$b$, $e$ and $k$ being satisfied. Specifically, if $A\sim\mbox{\rm DC-
SBM}_{\rm MC}(b,e,k)$, then with probability 1 it satisfies, for all
$r,s\in[B]$ and all $i\in[N]$:

$e_{rs}=\sum_{i,j\in[N]}A_{ij}\mathbbm{1}\\{b_{i}=r\\}\mathbbm{1}\\{b_{j}=s\\}\qquad\textrm{and}\qquad
k_{i}=\sum_{j\in[N]}A_{ij}.$ (1)

##  3 Feature-First Block Model

In this section we propose a novel generative model for labelled networks. We
call this the feature-first block model (FFBM), illustrated in Figure 1.

Let $N$ denote the number of vertices, $B$ the number of blocks and ${\cal X}$
the set of values each feature can take. We define the vector
$x_{i}\in\mathcal{X}^{D}$ as the feature vector for vertex $i$, where $D$ is
the number of features associated with each vertex. For example, in the
datasets we analyse, we deal with binary feature flags (denoting the
presence/absence of each feature), so $\mathcal{X}=\\{0,1\\}$. We write $X$
for the $N\times D$ feature matrix containing the feature vectors
$\\{x_{i}\\}_{i=1}^{N}$ as its rows.

For the FFBM, we start with the feature matrix $X$ and generate a random
vector of block memberships $b\in[B]^{N}$. For each vertex $i$, the block
membership $b_{i}\in[B]$ is generated based on the feature vector $x_{i}$,
independently between vertices. The conditional distribution of $b_{i}$ given
$x_{i}$ also depends on a collection of weight vectors
$\theta=\\{w_{k}\\}_{k=1}^{B}$, where each $w_{k}$ has dimension $D$. We will
later find it convenient to write $\theta$ as a $B\times D$ matrix of weights
$W$. Specifically, the distribution of $b$ given $X$ and $\theta$ is,

$p(b|X,\theta)=\prod_{i\in[N]}p(b_{i}|x_{i},\theta)=\prod_{i\in[N]}\phi_{b_{i}}(x_{i};\theta)=\prod_{i\in[N]}\frac{\exp\left(w_{b_{i}}^{T}x_{i}\right)}{\sum_{k\in[B]}\exp\left(w_{k}^{T}x_{i}\right)}.$
(2)

Note that $\phi_{b_{i}}$ has the form of a softmax activation function. More
complex models based on different choices for the distributions $\phi_{b_{i}}$
above are also possible, but then deriving meaning from the inferred parameter
distributions is more difficult.

$X$$b$$A$$\theta$$\psi$ Figure 1: The Feature-First Block Model (FFBM)

Once the block memberships $b$ have been generated, we then draw the graph $A$
from the microcanonical DC-SBM with additional parameters
$\psi=\\{\psi_{e},\psi_{k}\\}$:

$A\sim\textrm{DC-SBM}_{\textrm{MC}}(b,\psi_{e},\psi_{k}).$ (3)

###  3.1 Prior selection

To complete the description of our Bayesian framework, priors on $\theta$ and
$\psi$ must also be specified. We place a Gaussian prior on $\theta$ such that
each element of $\theta$ has an independent ${\cal N}(0,\sigma_{\theta}^{2})$
prior, with hyperparameter $\sigma_{\theta}^{2}$:

$p(\theta)\sim\mathcal{N}\left(\theta;0,\sigma_{\theta}^{2}I\right).$ (4)

This choice of prior gives a very simple form for the conditional distribution
of the block membership vector $b$ given $X$; it is a uniform distribution:

$p(b|X)=\int p(b|X,\theta)p(\theta)d\theta=B^{-N}.$ (5)

The proof is given in Appendix 0.A.1. This is an important simplification as
evaluating $p(b|X)$ does not require an expensive integration over $\theta$
nor does it depend on $X$. Peixoto [10] proposes careful choices for the
priors on the additional microcanonical SBM parameters $\psi$, which we adopt
without repeating their exact form here. The idea is to write the joint
distribution on $(b,e,k)$ as a product of conditionals,
$p(b,e,k)=p(b)p(e|b)p(k|e,b)=p(b)p(\psi|b)$. In our case, conditioning on $X$
is also necessary, leading to,
$p(b,\psi|X)=p(b|X)p(\psi|b,X)=p(b|X)p(\psi|b),$ where we used the fact $\psi$
and $X$ are conditionally independent given $b$. All that concerns the main
argument is that $p(\psi|b)$ has an easily computable form.

##  4 Inference

Having completed the definition of the FFBM, we wish to leverage it to perform
inference. Specifically, given a labelled network $(A,X)$, we wish to infer if
and how the observed features $X$ impact the graphical structure $A$.
Formally, this means characterising the posterior distribution:
$p(\theta|A,X)\propto p(\theta)\cdot p(A|X,\theta).$ Although the prior is
easily computable, computing the likelihood requires summing over all latent
block-states, $p(A|X,\theta)=\sum_{b\in[B]^{N}}p(A|b)P(b|X,\theta)$, which is
clearly impractical. In fact, this approach is doubly intractable as we would
also need to compute the normalising constant $p(A|X)$. Therefore, following
standard Bayesian practice, instead we aim to draw samples from the posterior,

$\theta^{(t)}\sim p(\theta|A,X).$ (6)

We propose an iterative Markov chain Monte Carlo (MCMC) approach to obtain
these samples $\\{\theta^{(t)}\\}$. We first draw a sample $b^{(t)}$ from the
block membership posterior, and then use $b^{(t)}$ to obtain a corresponding
sample $\theta^{(t)}$:

$b^{(t)}\stackrel{{\scriptstyle\rm
distr}}{{\approx}}p\big{(}b|A,X\big{)}\quad\textrm{then}\quad\theta^{(t)}\stackrel{{\scriptstyle\rm
distr}}{{\approx}}p\big{(}\theta|X,b^{(t)}\big{)},$ (7)

where these approximations become exact as the number of MCMC iterations
$t\to\infty$. As described in the following subsections, this can be
implemented through a two-level Markov chain via the Metropolis-Hastings (MH)
algorithm [5]. The splitting of the Markov chain into two levels allows us to
side-step the summation over all latent $b\in[B]^{N}$ required to directly
compute the likelihood, $p(A|X,\theta)$. The resulting $\theta^{(t)}$ samples
are asymptotically unbiased in that the expectation of their distribution
converges to the true posterior:

$\lim_{t\to\infty}\mathbb{E}_{b^{(t)}}\left[p\left(\theta|X,b^{(t)}\right)\right]=\sum_{b\in[B]^{N}}p(\theta|X,b)p(b|A,X)=p(\theta|A,X).$
(8)

This is an example of a pseudo-marginal approach; see, e.g., Andrieu and
Roberts [3] for a detailed rigorous derivation based on (8).

$b^{(t)}$$b^{\prime}$$b^{(t+1)}$$\theta^{(t)}$$\theta^{\prime}$$\theta^{(t+1)}$$\sim
q_{b}(b^{(t)},b^{\prime}|A)$$\alpha_{b}(b,b^{\prime}|A)$$1-\alpha_{b}$$\sim
q_{\theta}(\theta^{(t)},\theta^{\prime}|X,b^{(t)})$$\alpha_{\theta}(\theta,\theta^{\prime}|X,b^{(t)})$$1-\alpha_{\theta}$
Figure 2: $\theta$-sample generation.

Figure 2 shows an overview of the proposed method, with $q$ and $\alpha$
denoting the MH proposal distribution and acceptance probability respectively.
Note the importance of the simplification in (5). As evaluating $p(b|X)$ does
not depend on $X$, we do not need $X$ to sample $b$. And on the other level,
in order to obtain samples for $\theta$ we use only $b$ but not $A$, as
$(\theta\perp\\!\\!\\!\perp A)|b$.

###  4.1 Sampling block memberships

To generate the required $b$-samples, we adopt the MCMC procedure of [9],
which relies on writing the posterior in the following form,

$p(b|A,X)\propto p(A|b,X)\cdot p(b|X)=\pi_{b}(b),$ (9)

where $\pi_{b}(\cdot)$ denotes the un-normalised target density. Since we are
using the microcanonical SBM formulation, there is only one value of $\psi$
that is compatible with the given $(A,b)$ pair; recall the constraints in (1).
We denote this value $\psi^{*}=\\{\psi_{k}^{*},\psi_{e}^{*}\\}$. Therefore,
the summation over all $\psi$ needed to evaluate $p(A|b,X)$ reduces to just
the single $\psi^{*}$ term: $p(A|b,X)=\sum_{\psi}\nolimits
p(A,\psi|b,X)=p(A,\psi^{*}|b,X)$. In this context, the microcanonical entropy
of the configuration $b$ is,

$S(b)\coloneqq-\log\pi_{b}(b)=-\Big{(}\log p(A|b,\psi^{*})+\log
p(\psi^{*},b|X)\Big{)},$ (10)

which can be thought of as the optimal “description length” of the graph. This
expression will later be employed to help evaluate experimental results. The
exact form of the proposal $q_{b}$ is explored thoroughly in [9] and not
repeated here. We use the `graph-tool` [11] library for Python, which
implements this algorithm. The only modification is in the prior $p(b)$ that
we replace with $p(b|X)=B^{-N}$, which cancels out in the MH accept-reject
step as it is independent of $b$.

###  4.2 Sampling feature-to-block generator parameters

The target distribution for the required $\theta$-samples is the posterior of
$\theta$ given the values of the pair $(X,b)$. We write this as,

$\pi_{\theta}(\theta)\propto p(\theta|X,b)\propto
p(b|X,\theta)p(\theta)\propto\exp\left(-U(\theta)\right),$ (11)

where $U(\theta)$ denotes the negative log-posterior. Let
$y_{ij}\coloneqq\mathbbm{1}\left\\{b_{i}=j\right\\}$ and
$a_{ij}\coloneqq\phi_{j}(x_{i};\theta)$. Discarding constant terms,
$U(\theta)$ can be expressed as,

$U(\theta)=\left(\sum_{i\in[N]}\sum_{j\in[B]}y_{ij}\log\frac{1}{a_{ij}}\right)+\frac{1}{2\sigma_{\theta}^{2}}\|\theta\|^{2}=N\cdot\mathcal{L}(\theta)+\frac{1}{2\sigma_{\theta}^{2}}\|\theta\|^{2};$
(12)

see Appendix 0.A.2. The function $U(\theta)$ is a typical objective function
for neural network training. The first term $N\cdot\mathcal{L}(\theta)$ is
introduced by the likelihood and represents the cross-entropy between the
graph-predicted and feature-predicted block memberships. The second term,
introduced by the prior, brings a form of regularisation, guarding against
over-fitting. In order to draw samples from the posterior
$\pi_{\theta}\propto\exp(-U)$ we adopt the Metropolis-adjusted Langevin
algorithm (MALA) [12], which uses $\nabla U$ to bias the proposal towards
regions of higher density. Given the current sample $\theta$, a proposed new
sample $\theta^{\prime}$ is generated from,

$\theta^{\prime}\sim
q_{\theta}\big{(}\theta,\theta^{\prime}\big{)}=\mathcal{N}\big{(}\theta^{\prime};\theta-h\nabla
U(\theta),2hI\big{)},$

where $\xi\sim\mathcal{N}(0,I)$ and $h$ is a step-size parameter which may
vary with the sample index. Without the injected noise term $\xi$, MALA is
equivalent to gradient descent. We require $\xi$ to fully explore the
parameter space. The term $\nabla U$ has an easy to compute analytic form
(derived in Appendix 0.A.2).

###  4.3 Sampling sequence

So far, each $\theta^{(t)}$ update has used its corresponding $b^{(t)}$
sample. This means the evaluation of $U^{(t)}$ and $\nabla U^{(t)}$ has high
variance, leading to longer burn-in and possibly slower MCMC convergence. The
only link between $b^{(t)}$ and $\theta^{(t)}$ is in the evaluation of
$U^{(t)}$ and $\nabla U^{(t)}$ which depends only on the matrix $y^{(t)}$ with
entries $y_{ij}^{(t)}\coloneqq\mathbbm{1}\\{b_{i}^{(t)}=j\\}$. We would rather
deal with the expectation of each $y_{ij}^{(t)}$:

$\mathbb{E}\left[y_{ij}^{(t)}\right]=\mathbb{E}_{b^{(t)}}\left[\mathbbm{1}\left(b_{i}^{(t)}=j\right)\right]=p(b_{i}=j|A,X).$
(13)

An unbiased estimate for this can be obtained using the thinned $b$-samples
after burn-in. Let $\mathcal{T}_{b}$ denote the retained set of indices for
the $b$-samples and $\mathcal{T}_{\theta}$ similarly for the $\theta$-chain.
The unbiased estimate for $y_{ij}^{(t)}$ is then:

$\hat{y}_{ij}\coloneqq\frac{1}{|\mathcal{T}_{b}|}\sum_{t\in\mathcal{T}_{b}}y_{ij}^{(t)}=\frac{1}{|\mathcal{T}_{b}|}\sum_{t\in\mathcal{T}_{b}}\mathbbm{1}\\{b_{i}^{(t)}=j\\}.$
(14)

The same matrix $\hat{y}$ is used in each $\theta^{(t)}$ update step. This
way, it is not necessary to run the $b$ and $\theta$ Markov chains
concurrently. Instead, we run the $b$-chain to completion and use it to
generate $\hat{y}$ also allowing us to vary the lengths of each.

###  4.4 Dimensionality reduction

The complexity of evaluating $U$ and $\nabla U$ is linear in the dimension of
the feature space $D$, so there is computational incentive to reduce $D$.
Given the samples $\left\\{\theta^{(t)}\right\\}$, we can compute the
empirical mean and standard deviation of each component of $\theta$. Switching
to the matrix notation $W$ for $\theta$, let:

$\hat{\mu}_{ij}\coloneqq\frac{1}{|\mathcal{T}_{\theta}|}\sum_{t\in\mathcal{T}_{\theta}}W_{ij}^{(t)}\qquad\textrm{and}\qquad\hat{\sigma}_{ij}^{2}\coloneqq\frac{1}{|\mathcal{T}_{\theta}|}\sum_{t\in\mathcal{T}_{\theta}}\left(W_{ij}^{(t)}-\hat{\mu}_{ij}\right)^{2}.$
(15)

A simple heuristic to discard the least important features requires specifying
a cutoff $c>0$ and a multiplier $k>0$. We define the function
$\mathcal{F}_{i}(j)$ as in (16) and only keep features with indices
$d\in\mathcal{D}^{\prime}$, where $\mathcal{D}^{\prime}$ is given in (17).

$\displaystyle\mathcal{F}_{i}(j)$
$\displaystyle\coloneqq(\hat{\mu}_{ij}-k\hat{\sigma}_{ij},\hat{\mu}_{ij}+k\hat{\sigma}_{ij})\cap(-c,+c),$
(16) $\displaystyle\mathcal{D}^{\prime}$
$\displaystyle\coloneqq\left\\{j\in[D]:\exists i\in[B]\textrm{ s.t.
}\mathcal{F}_{i}(j)=\emptyset\right\\}.$ (17)

Intuitively, this means discarding any feature $j$ for which
$(\hat{\mu}_{ij}-k\hat{\sigma}_{ij},\hat{\mu}_{ij}+k\hat{\sigma}_{ij})$
overlaps with $(-c,c)$ for all $i$. If we were to use the Laplace
approximation for the posterior
$p(W_{ij}|A,X)\approx\mathcal{N}(W_{ij};\hat{\mu}_{ij},\hat{\sigma}_{ij}^{2})$,
then this would be analogous to a hypothesis test on the magnitude of $W_{ij}$
compared to $c$ with multiplier $k$ in (16) determining the degree of
significance of the result. Conversely, if we want to fix the number of
dimensions in our reduced feature set $|\mathcal{D}^{\prime}|=D^{\prime}$, the
problem then becomes finding the largest value of $c$ such that
$|\mathcal{D}^{\prime}|=D^{\prime}$ given $k=k_{0}$:

$c^{*}=\operatorname*{arg\,max}\\{c>0\;:\;|\mathcal{D}^{\prime}|=D^{\prime},k=k_{0}\\}.$
(18)

##  5 Experimental results

We apply our proposed methods to a variety of labelled networks:

  * •

Political books [8] ($N=105,E=441,D=3$) – network of Amazon political books
published close to the 2004 presidential election. Two books are connected if
they were frequently co-purchased. Vertex features encode the political
affiliation of the author (liberal, conservative, or neutral).

  * •

Primary school dynamic contacts [13] ($N=238,E=5539,D=13$) – network of 238
individuals (students and teachers), with edges denoting face-to-face contacts
at a primary school in Lyon, France. The vertex features are class membership
(one of 10 values: 1A-5B), gender (male, female), and status (teacher,
student). We choose to analyse just the second day of results.

  * •

Facebook egonet [6] ($N=747,E=30025,D=480$) – network of Facebook users with
edges denoting “friends”. Vertex features are fully anonymised and encode
information about each user’s education history, languages spoken, gender,
home-town, birthday etc. We focus on the egonet with id 1912.

For reference, the inferred partitions for all of these are given on Figure 3.
We employ the following metrics to assess model performance. First, the
average description length per entity (nodes and edges) $\bar{S}_{e}$ used to
gauge the SBM fit is defined as:

$\bar{S}_{e}\coloneqq\frac{1}{(N+E)|\mathcal{T}_{b}|}\sum_{t\in\mathcal{T}_{b}}S\left(b^{(t)}\right).$
(19)

Next, to assess the performance of the feature-to-block predictor, the vertex
set $[N]$ is partitioned at random so that a constant fraction $f$ of vertices
form the training set $\mathcal{G}_{0}$ and the remainder form the test set
$\mathcal{G}_{1}$. The $b$-chain is run using the whole network but only
vertices $v\in\mathcal{G}_{0}$ are used for the $\theta$-chain. Then the the
average cross-entropy loss over each set is used to gauge the quality of the
fit,

$\bar{\mathcal{L}}_{\star}\coloneqq\frac{1}{|\mathcal{T}_{\theta}|}\sum_{t\in\mathcal{T}_{\theta}}\mathcal{L}_{\star}^{(t)},\quad\textrm{where}\quad\mathcal{L}_{\star}^{(t)}\coloneqq\frac{1}{|\mathcal{G}_{\star}|}\sum_{i\in\mathcal{G}_{\star}}\sum_{j\in[B]}\hat{y}_{ij}\log\frac{1}{\phi_{j}\left(x_{i};\theta^{(t)}\right)},$
(20)

where $\star\in\\{0,1\\}$ toggles between the training and test sets and
$\hat{y}_{ij}$ is defined in (14). Nevertheless, the cross-entropy loss is a
coarse measure of fit. A new measure, specific to each detected block, can be
defined as follows. Let $\mathcal{B}_{\star}(j)$ be the set of vertices with
maximum a posteriori probability of belonging to block $j$,
$\mathcal{B}_{\star}(j)\coloneqq\\{i\in\mathcal{G}_{\star}:\hat{b}_{i}=j\\},$
where $\hat{b}_{i}\coloneqq\operatorname*{arg\,max}_{j}\hat{y}_{ij},$ and
define the block-accuracy for block $j$ as,

$\eta_{\star}(j)\coloneqq\frac{1}{|\mathcal{B}_{\star}(j)|\cdot|\mathcal{T}_{\theta}|}\sum_{i\in\mathcal{B}_{\star}(j)}\sum_{t\in\mathcal{T}_{\theta}}\mathbbm{1}\left\\{\hat{b}_{i}=\operatorname*{arg\,max}_{j}\phi_{j}\left(x_{i};\theta^{(t)}\right)\right\\}.$
(21)

This effectively tests whether the feature-to-block and graph-to-block
predictions agree in their largest component. For the higher-dimensional
datasets, we also apply the dimensionality reduction method of Section 4.4. We
then retrain the feature-block predictor using only the retained feature set
$\mathcal{D}^{\prime}$, and report the log-loss over the training and test
sets for the reduced classifier – denoted $\bar{\mathcal{L}}_{0}^{\prime}$ and
$\bar{\mathcal{L}}_{1}^{\prime}$ respectively.

(a) Polbooks

(b) Primary school

(c) Facebook egonet

(d) Block Legend

Figure 3: Networks laid out and coloured according to inferred block
memberships for a given experiment iteration. Visualisation performed using
graph-tool [11]. Table 1: Experimental results averaged over $n=10$ iterations
(mean $\pm$ std. dev.).

Dataset | $B$ | $D$ | $D^{\prime}$ | $\bar{S}_{e}$ | $\bar{\mathcal{L}}_{0}$ | $\bar{\mathcal{L}}_{1}$ | $c^{*}$ | $\bar{\mathcal{L}}_{0}^{\prime}$ | $\bar{\mathcal{L}}_{1}^{\prime}$
---|---|---|---|---|---|---|---|---|---
Polbooks | 3 | 3 | – | $2.250\pm 0.000$ | $0.563\pm 0.042$ | $0.595\pm 0.089$ | – | – | –
School | 10 | 13 | 10 | $1.894\pm 0.004$ | $0.787\pm 0.127$ | $0.885\pm 0.129$ | $1.198\pm 0.249$ | $0.793\pm 0.132$ | $0.853\pm 0.132$
FB egonet | 10 | 480 | 10 | $1.626\pm 0.003$ | $1.326\pm 0.043$ | $1.538\pm 0.069$ | $0.94\pm 0.019$ | $1.580\pm 0.150$ | $1.605\pm 0.106$

(a) Political books

(b) Primary school

(c) Facebook egonet

Figure 4: Top $D^{\prime}$ $\theta$-samples for each dataset. Coarse steps on
x-axis give block index and the fine steps denote give index. Dotted line is
$\pm c^{*}$.

(a) Political books

(b) Primary school

(c) Facebook egonet

Figure 5: Per-block accuracy $\eta(j)$ for each dataset.

Table 1 summarises the results for each experiment. We see that the
dimensionality reduction procedure brings the training and test losses closer.
This indicates that the retained features are indeed well correlated with the
underlying graphical partition and that the approach generalises correctly.
The test loss variance is higher than the training loss variance as the test
set is smaller and so more susceptible to variability in its construction. The
average description length per entity of the graph, $\bar{S}_{e}$, has very
small variance, suggesting that the detected communities can be found reliably
(to within an arbitrary relabelling of blocks).

#### Political books.

We choose to partition the network into $B=3$ communities as we only have this
many distinct values for political affiliation. From Figure 4(a) we see that
all 3 blocks have a distinct political affiliation as their largest positive
component. Furthermore, the training and test losses from Table 1 are very
similar and both are low in magnitude. This is strong evidence that political
affiliation is a very appropriate explanatory variable for the overall network
structure. However, from Figure 5(a) we see that block 1 has low accuracy.
This suggests that detected block 1 is not solely composed of “neutral” books
but also contains some “liberal” and “conservative” authors. Examining Figure
3(a), we see the majority of paths between blocks 2 and 3 go through block 1.
Block 1 is in effect a bridge between the “conservative” and “liberal” blocks
so it is unsurprising that some of these leak into block 1.

#### Primary school.

We choose the number of communities $B=10$, in line with the total number of
school classes. Only the pupils’ class memberships (1A-5B) survive the
dimensionality-reduction process (Figure 4(b)); gender and teacher/student
status have been discarded, meaning these are poor predictors of overall
macro-structure. Almost all blocks are composed of a single class. However,
some blocks have two comparably strong classes as their predictors (e.g.
blocks 2 and 5). Conversely, some classes are found to extend over two
detected blocks (class 2B spans blocks 8 and 9) but we do not have a feature
which explains the division. Figure 5(b) shows excellent accuracy for most
blocks. In fact the only blocks with low accuracy are those with a ‘school-
class’ feature that spans two blocks, such that we cannot reliably distinguish
between the two. This is more pronounced when we apply hard classification
rather than cross-entropy loss. It is possible that there are unobserved
features here which explain this divide.

#### Facebook egonet.

The retained features (Figure 4(c)) are those that best explain the high-level
community structure. The majority of these are education related.
Nevertheless, for $D^{\prime}=10$ we only have good explanations for some of
the detected blocks; several blocks in Figure 4(c) do not have high-magnitude
components. This is further emphasised by the disparate accuracies in Figure
5(c). For a high-dimensional feature-space, it is likely that a particular
feature may uniquely identify a small set of vertices; if these are all in the
same block, then the classifier may overfit despite the penalty imposed by the
prior. Indeed, we see in Figure 4(c) that the feature ‘birthday-5’ has a very
high weight as it relates to block 1 – but it is unlikely that birthdays
determine graphical structure.

##  6 Conclusion

The proposed Feature-First Block Model (FFBM) is a new generative model for
labelled networks. It is a hierarchical Bayesian model, well-suited for
describing how features affect network structure. The Bayesian inference tools
developed in this work facilitate the identification of vertex features that
are in some way correlated with the network’s graphical structure.
Consequently, finding the features that best describe the most pronounced
partition, makes it possible in practice to examine the existence of – and to
make a case for – causal relationships.

An efficient MCMC algorithm is developed for sampling from the posterior
distribution of the relevant parameters in the FFBM; the main idea is to
divide up the graph into its most natural partition under the associated
parameter values, and then to determine whether the vertex features can
accurately explain the partition. Through several applications on empirical
network data, this approach is shown to be effective at extracting and
describing the most natural communities in a labelled network. Nevertheless,
it can only currently explain the structure at the macroscopic scale. Future
work will benefit from extending the FFBM to a further hierarchical model, so
that the structure of the network can be explained at all scales of interest.

##  Appendix 0.A Appendix

###  0.A.1 Derivation of $p(b|X)$

We determine the form of $p(b|X)$ by integrating out the parameters $\theta$.
From the definitions, we have:

$\displaystyle p(b|X)$ $\displaystyle=\int p(b,\theta|X)d\theta=\int
p(b|X,\theta)p(\theta|X)d\theta=\int\prod_{i\in[N]}\phi_{b_{i}}(x_{i};\theta)p(\theta)d\theta$
$\displaystyle=\prod_{i\in[N]}\int\frac{\exp(w_{b_{i}}^{T}x_{i})\prod_{j\in[B]}\mathcal{N}(w_{j};0,\sigma_{\theta}^{2}I)}{\sum_{k\in[B]}\exp(w_{k}^{T}x_{i})}dw_{1:B}.$

The key observation here is that the value of the integral is independent of
the value of $b_{i}\in[B]$ as the integrand has the same form regardless of
$b_{i}$. This is because the prior is the same for each $w_{j}$. Therefore,
the integral can only be a function of $x_{i}$ and $\sigma_{\theta}^{2}$,
which means that, as a function of $b$, $p(b|X)\propto 1$. As $b$ takes values
in $[B]^{N}$, we necessarily have: $p(b|X)=1/\big{|}[B]^{N}\big{|}=B^{-N}$.

###  0.A.2 Derivation of $U(\theta)$ and $\nabla U(\theta)$

Recall from (11) in Section 4.2 that,

$\pi_{\theta}(\theta)\propto p(\theta|X,b)\propto
p(b|X,\theta)p(\theta)\propto\exp\left(-U(\theta)\right),$

so that $U$ can be expressed as,

$U(\theta)=-\left(\log p(b|X,\theta)+\log p(\theta)\right)+\textrm{const}.$

Writing, $y_{ij}\coloneqq\mathbbm{1}\left\\{b_{i}=j\right\\}$ and
$a_{ij}\coloneqq\phi_{j}(x_{i};\theta)$ as before, we have that,

$\log p(b|X,\theta)=\sum_{i\in[N]}\sum_{j\in[B]}y_{ij}\log
a_{ij}\quad\textrm{and}\quad\log p(\theta)=-\frac{DB}{2}\log
2\pi-\frac{1}{2\sigma_{\theta}^{2}}\|\theta\|^{2},$

where $\|\theta\|^{2}=\sum_{i}\theta_{i}^{2}=\sum_{j\in[B]}\|w_{j}\|^{2}$ is
the Euclidean norm of the vector of parameters $\theta$. Therefore, discarding
constant terms, we obtain,

$U(\theta)=\left(\sum_{i\in[N]}\sum_{j\in[B]}y_{ij}\log\frac{1}{a_{ij}}\right)+\frac{1}{2\sigma_{\theta}^{2}}\|\theta\|^{2}.$
(22)

Now to find $\nabla U(\theta)$, we need to compute each of its components,
$\nicefrac{{\partial U}}{{\partial w_{k}}}$, for $k\in[B]$. To that end, we
first compute,

$\displaystyle\frac{\partial a_{ij}}{\partial w_{k}}$
$\displaystyle=\frac{x_{i}\exp(w_{j}^{T}x_{i})\delta_{jk}\cdot\sum_{r\in[B]}\exp(w_{r}^{T}x_{i})-\exp(w_{j}^{T}x_{i})\cdot
x_{i}\exp(w_{k}^{T}x_{i})}{\left(\sum_{r\in[B]}\exp(w_{r}^{T}x_{i})\right)^{2}}$
$\displaystyle=x_{i}\left(a_{ij}\delta_{jk}-a_{ij}a_{ik}\right),$ (23)

where $\delta_{jk}\coloneqq\mathbbm{1}\left\\{j=k\right\\}$, and we also
easily find,

$\frac{\partial}{\partial w_{k}}\|\theta\|^{2}=\frac{\partial}{\partial
w_{k}}\left(\sum_{r\in[B]}\|w_{r}\|^{2}\right)=2w_{k}.$ (24)

Combining the expression for $U(\theta)$ in (22) and the expressions of (23)
and (24), we obtain,

$\displaystyle\frac{\partial U}{\partial w_{k}}$
$\displaystyle=\sum_{i\in[N]}\sum_{j\in[B]}y_{ij}\left(-\frac{x_{i}}{a_{ij}}\left(a_{ij}\delta_{jk}-a_{ij}a_{ik}\right)\right)+\frac{w_{k}}{\sigma_{\theta}^{2}}$
$\displaystyle=-\left(\sum_{i\in[N]}\Big{\\{}x_{i}(y_{ik}-a_{ik})\Big{\\}}-\frac{w_{k}}{\sigma_{\theta}^{2}}\right).$
(25)

This can be computed efficiently through matrix operations. The only property
of $y_{ij}$ we have used in the derivation is the constraint
$\sum_{j\in[B]}y_{ij}=1$, for all $i$.

###  0.A.3 Implementation details

Full source code is available at:

https://github.com/LozzaTray/Jormungandr-code

Table 2 contains all hyper-parameter values used in our experiments. The set
of retained samples are generated as,
$\mathcal{T}_{\star}=\\{T_{\star}\kappa_{\star}+i\lambda_{\star}:0\leq
i\leq\lfloor T_{\star}(1-\kappa_{\star})/\lambda_{\star}\rfloor\\}.$

Table 2: Hyper-parameter values for each experiment. Dataset | $B$ | $f$ | $\sigma_{\theta}$ | $T_{b}$ | $\kappa_{b}$ | $\lambda_{b}$ | $T_{\theta}$ | $\kappa_{\theta}$ | $\lambda_{\theta}$ | $k$ | $D^{\prime}$ | $T_{\theta}^{\prime}$ | $\kappa_{\theta}^{\prime}$ | $\lambda_{\theta}^{\prime}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Polbooks | 3 | 0.7 | 1 | 1,000 | 0.2 | 5 | 10,000 | 0.4 | 10 | – | – | – | – | –
School | 10 | 0.7 | 1 | 1,000 | 0.2 | 5 | 10,000 | 0.4 | 10 | 1 | 10 | 10,000 | 0.4 | 10
FB egonet | 10 | 0.7 | 1 | 1,000 | 0.2 | 5 | 10,000 | 0.4 | 10 | 1 | 10 | 10,000 | 0.4 | 10

## References

  * [1] Abbe, E.: Graph compression: The effect of clusters. In: 54th Annual Allerton Conference on Communication, Control, and Computing. pp. 1–8 (2016)
  * [2] Airoldi, E.M., Blei, D., Fienberg, S., Xing, E.: Mixed membership stochastic blockmodels. In: Koller, D., Schuurmans, D., Bengio, Y., Bottou, L. (eds.) Advances in Neural Information Processing Systems. vol. 21 (2009)
  * [3] Andrieu, C., Roberts, G.O.: The pseudo-marginal approach for efficient Monte Carlo computations. The Annals of Statistics 37(2), 697–725 (2009)
  * [4] Gaucher, S., Klopp, O., Robin, G.: Outliers detection in networks with missing links. Computational Statistics & Data Analysis 164, 107308 (2021)
  * [5] Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1), 97–109 (1970)
  * [6] Leskovec, J., Mcauley, J.: Learning to discover social circles in ego networks. In: Pereira, F., Burges, C.J.C., Bottou, L., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems. vol. 25 (2012)
  * [7] Nowicki, K., Snijders, T.A.B.: Estimation and prediction for stochastic blockstructures. Journal of the American Statistical Association 96(455), 1077–1087 (2001)
  * [8] Pasternak, B., Ivask, I.: Four unpublished letters. Books Abroad 44(2), 196–200 (1970)
  * [9] Peixoto, T.P.: Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models. Physical Review E 89(1) (2014)
  * [10] Peixoto, T.P.: Nonparametric Bayesian inference of the microcanonical stochastic block model. Physical Review E 95(1) (2017)
  * [11] Peixoto, T.: The graph-tool Python library. figshare (2014), figshare.com/articles/graph_tool/1164194
  * [12] Roberts, G.O., Tweedie, R.L.: Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli 2(4), 341–363 (1996)
  * [13] Stehlé, J., Voirin, N., Barrat, A., Cattuto, C., Isella, L., Pinton, J.F., Quaggiotto, M., Van den Broeck, W., Régis, C., Lina, B., Vanhems, P.: High-resolution measurements of face-to-face contact patterns in a primary school. PLoS ONE 6(8), 1–13 (2011)
  * [14] Zhu, J., Song, J., Chen, B.: Max-margin nonparametric latent feature models for link prediction. arXiv preprint cs.LG:1602.07428 (2016)


# The most exciting game

Julio Backhoff-Veraguas and Mathias Beiglböck

###### Abstract.

Motivated by a problem posed by Aldous [2, 1] our goal is to find the maximal-
entropy win-martingale:

In a sports game between two teams, the chance the home team wins is initially
$x_{0}\in(0,1)$ and finally 0 or 1. As an idealization we take a continuous
time interval $[0,1]$ and consider the process $M=(M_{t})_{t\in[0,1]}$ giving
the probability at time $t$ that the home team wins. This is a martingale
which we idealize further to have continuous paths. We consider the problem to
find the most random martingale $M$ of this type, where ‘most random’ is
interpreted as a maximal entropy criterion. We observe that this max-entropy
win-martingale $M$ also minimizes specific relative entropy with respect to
Brownian motion in the sense of Gantert [20] and use this to prove that $M$ is
characterized by the stochastic differential equation

$dM_{t}=\frac{\sin(\pi M_{t})}{\pi\sqrt{1-t}}\,dB_{t}.$

To derive the form of the optimizer we use a scaling argument together with a
new first order condition for martingale optimal transport which may be of
interest in its own right.

###### Key words and phrases:

Entropy, specific relative entropy, prediction markets, max-entropy win-
martingale, Martingale optimal transport

We thank David Aldous for pointing us to the problem posed in [2, 1] and
suggesting the connection to specific relative entropy. We also acknowledge
support by the Austrian Science Fund FWF through projects P36835, Y0782, and
P35197

##  1\. Introduction

###  1.1. Main result

We write $\mathcal{M}^{c}_{x_{0}}$ for the set of laws of continuous
martingales with time-index set $[0,1]$ which have absolutely continuous
quadratic variation and start in $x_{0}$. The subset
$\mathcal{M}^{c}_{x_{0},\text{win}}$ of _win-martingales_ consist of those
martingales which terminate in either $0$ or $1$. Win-martingales appear
naturally as models for prediction markets (cf. [3]).

In our main result we characterize the win-martingale which is closest to
Brownian motion in that it minimizes the _specific relative entropy $h$_ (in
the sense of Gantert [20]) w.r.t. Wiener measure $\mathbb{W}^{x_{0}}$ started
at $x_{0}$.

######  Theorem 1.1.

Let $x_{0}\in(0,1)$. Then the minimization problem

$\displaystyle\inf\\{h(\mathbb{Q}|\mathbb{W}^{x_{0}}):\mathbb{Q}\in\mathcal{M}^{c}_{x_{0},\text{win}}\\}$
(1.1)

has a unique solution which is given through the SDE

$\displaystyle dM_{t}=\frac{\sin(\pi M_{t})}{\pi\sqrt{1-t}}\,dB_{t},\quad
M_{0}=x_{0}.$ (1.2)

Gantert [20] defines specific relative entropy $h$ as the scaled limit of
relative entropies associated to appropriate time-discretizations of
$\mathbb{Q}$ and $\mathbb{W}^{x_{0}}$. For sufficiently regular $\mathbb{Q}$,
it is known (cf. [20, 7]) that

$\displaystyle\textstyle
h(\mathbb{Q}|\mathbb{W}^{x_{0}})=\frac{1}{2}\mathbb{E}_{\mathbb{Q}}\left[\int_{0}^{1}\\{\Sigma_{t}-\log(\Sigma_{t})-1\\}\,dt\right],$
(1.3)

where $\Sigma_{t}$ stands for the density of the quadratic variation for the
canonical process under $\mathbb{Q}$ at time $t$ (see [20, 18]). For us it is
important to directly use the quantity in (1.3), we discuss this in Section 3
below.

Aldous [2, 1] considers the problem of determining the win martingale which
maximizes entropy. To make this precise Aldous considers classical Shannon
entropy and win martingales in a discretized setting. He provides heuristics
for the existence of a scaling limit and suggests a PDE that should be
satisfied by this limit. In this paper we observe that (discrete time)
martingales which _maximize_ Shannon entropy _minimize_ relative entropy
w.r.t. discretized Wiener measure as used by Gantert [20]. This observation
indicates that (1.1) is an appropriate way to define the max-entropy win-
martingale directly in continuous time. Indeed, we verify that the martingale
$M$ specified in (1.2) solves the PDE suggested by Aldous and we refer to $M$
as _Aldous martingale_.

Figure 1. Two typical paths of the Aldous martingale for a fair game
($M_{0}=0.5$).

Figure 2. Two typical paths of the Bass martingale
$X_{t}:=\Phi(B_{t}/\sqrt{1-t})$ from $0.5$ to $Bernoulli(0.5)$.

Figure 3. Many simulated paths of the Aldous martingale for a fair game.

Figure 4. Many simulated paths of the Bass martingale.

In Figures 2 to 4 we compare simulations of the Aldous and the Bass
martingale. The Bass martingale was introduced in [8, 5, 6] an is the
martingale with specified initial and terminal distribution which minimizes
the _adapted Wasserstein distance_ to Brownian motion.

Note added in revision: briefly after making our note available to the arxiv,
and independently from us, Guo, Possamaï and Reisinger presented a different
solution to Aldous’ problem based on PDE-techniques and unrelated to the
concept of specific entropy. Importantly, while the article of Guo, Possamaï
and Reisinger [21] as well as the present note yield solutions of the same
PDE, the respective solutions satisfy different boundary conditions.

###  1.2. Outline of the paper

In Section 2 we will discuss martingale transport problems in discrete time
which optimize an entropy criterion. In particular we detail that maximization
of Shannon entropy corresponds precisely to minimization of relative entropy
with respect to discretized Wiener measure.

In Section 3 we discuss specific relative entropy in the sense of Gantert
[20]. We also observe that the Aldous martingale provides a counterexample to
a conjecture posed in [20] about the representation of specific relative
entropy.

In Section 4 we derive a new first order condition for martingale transport
problems in continuous time. Together with a scaling argument for optimizers
of (1.1) this allows to identify the Aldous martingale (1.2) as a candidate
optimizer.

Finally, in Section 5 we use verification arguments to obtain that (1.2)
indeed solves (1.1). In particular, the optimal value of (1.1) is equal to

$\frac{x_{0}(1-x_{0})-1}{2}-\log\left(\frac{\sin(\pi x_{0})}{\pi}\right).$

##  2\. Maximization of entropy and minimization of relative entropy

As noted above, Aldous [2, 1] poses the problem to determine the _maximal-
entropy win-martingale_. To assign a rigorous meaning to the maximal entropy
(in the sense of Shannon ) criterion, his starting point is a formulation in a
discrete time, discrete space setting. It is then argued, that a natural
scaling limit should exist. The goal of this section is to explain the
connection between maximization of entropy and minimization of relative
entropy w.r.t. the Gaussian random walk / discritized Wiener measure as used
in Gantert’s definition of specific relative entropy. We emphasize that this
section is technically not required for the results in this article. Rather
the point we want to make is that the notion of specific relative entropy
allows to pose the problem directly in the continuous time setup.

We deviate from the setting of [2, 1] in that we consider discrete time (for
now) martingales which are allowed to take values on the real line. We also
allow for general prescribed initial and terminal distributions $\mu,\nu$
which are in convex order. For $T\in{\mathbb{N}}$ we write $(X_{t})_{t=0}^{T}$
for the canonical process on the path space $\mathbb{R}^{T+1}$. We denote by
$M_{T}(\mu,\nu)$ the set of all martingale transport plans, that is,
martingale measures $\mathbb{Q}$ on $\mathbb{R}^{T+1}$ such that
$X_{0}(\mathbb{Q})=\mu,X_{T}(\mathbb{Q})=\nu$. We then consider the maximal
entropy transport problem

$\displaystyle\max_{\mathbb{Q}\in M_{T}(\mu,\nu)}H(\mathbb{Q})\quad\text{where
}H(\mathbb{Q})=\begin{cases}-\int_{\mathbb{R}^{T+1}}q(x)\log
q(x)\,dx&\mathbb{Q}=q\cdot\lambda_{T+1}\\\ -\infty&\text{else}\end{cases},$
(2.1)

where $\lambda_{d}$ denotes Lebesgue measure on $\mathbb{R}^{d}$. Note that
(2.1) can be finite only if $\mu,\nu$ are absolutely continuous, which we will
tacitly assume. We write

$\gamma_{T}(x_{0},\ldots,x_{T})\propto
f_{0}(x_{0})\exp{\left(\frac{1}{2\sigma^{2}}\sum_{i=1}^{T}(x_{i}-x_{i-1})^{2}\right)}$

for the density of the Gaussian random walk with start in
$f_{0}\cdot\lambda_{1}$. For $\mathbb{Q}=q\cdot\lambda_{T+1}\in
M_{T}(\mu,\nu)$ the relative entropy $H(\mathbb{Q}|\gamma_{T})$ satisfies

$\displaystyle H(\mathbb{Q}|\gamma_{T})$
$\displaystyle:=\int\log\frac{q}{\gamma_{T}}\,d\mathbb{Q}=\int q(x)\log
q(x)\,dx-\int\log\gamma_{T}d\mathbb{Q}=$
$\displaystyle=-H(\mathbb{Q})+\frac{T}{2}\log(2\pi\sigma^{2})-\int\log
f_{0}\,d\mu+\int\sum_{t=1}^{T}\frac{(x_{i}-x_{i-1})^{2}}{2\sigma^{2}}\,d\mathbb{Q}(x_{0},\ldots,x_{T})$
$\displaystyle=-H(\mathbb{Q})+\frac{T}{2}\log(2\pi\sigma^{2})-\int\log
f_{0}\,d\mu+\frac{1}{2\sigma^{2}}\left(\int x_{T}^{2}\,d\nu(x_{T})-\int
x_{0}^{2}\,d\mu(x_{0})\right).$

We thus find that, up to additive constants, maximization of Shannon entropy
in (2.1) corresponds precisely to minimization of relative entropy w.r.t. the
Gaussian random walk. Note that the choice of $f_{0}$ is, up to integrability
issues, not important for this argument.

##  3\. On specific relative entropy

We write $X=(X_{t})_{t\in[0,1]}$ for the canonical process on Wiener space
$C=C([0,1])$, and also consider the discretized process

$X^{n}:=(X_{k/n})_{k=0,\ldots,n}.$

We further consider a probability $\mathbb{Q}$ and denote the Wiener measure
with start in $x_{0}$ by ${\mathbb{W}}^{x_{0}}$. Gantert [20] defines the
specific relative entropy of $\mathbb{Q}$ w.r.t. ${\mathbb{W}}^{x_{0}}$ as the
limit of scaled relative entropies of the discretization of $\mathbb{Q}$
w.r.t. the Gaussian random walk, i.e.

$\displaystyle
h(\mathbb{Q}|{\mathbb{W}}^{x_{0}})=\lim_{n\to\infty}\frac{1}{n}H(X^{n}(\mathbb{Q})|X^{n}({\mathbb{W}}^{x_{0}}))$
(3.1)

whenever this limit exists.

The specific relative entropy is meaningful even in situations where measures
singular to each other are being compared. This is the case of continuous
martingale laws, which typically have infinite relative entropy but may still
have a finite specific relative entropy. Gantert [20, Kapitel II.4] shows that
$h$ is the rate function in a large deviations principle associated to a
randomized Donsker-type approximation of Brownian motion. The specific
relative entropy is also studied by Föllmer [18, 17] who uses it to establish
Talagrand-type inequalities on the Wiener space beyond the absolutely
continuous case. In particular he proves that the squared adapted Wasserstein
distance between a continuous martingale and Brownian motion is bounded from
above by twice the specific relative entropy. The quantity (3.1) is also
considered independently by Cohen and Dolinsky [15], where it plays a role in
the derivation of the scaling limit of utility indifference prices. On the
other hand, formula (1.3), as well as similar expressions, appeared in the
work of Avellaneda, Friedman, Holmes and Samperi [4] concerning model
calibration in finance.

According to [20] (in particular situations) and to [7] (for all sufficiently
regular martingale diffusions), we have the alternative expression

$\displaystyle
h(\mathbb{Q}|\mathbb{W}^{x_{0}})=\frac{1}{2}\mathbb{E}_{\mathbb{Q}}\left[\int_{0}^{1}\\{\Sigma_{t}-\log(\Sigma_{t})-1\\}\,dt\right],$
(3.2)

where $\Sigma_{t}$ stands for the density of the quadratic variation at time
$t$ for the canonical process under $\mathbb{Q}$. More generally [20, 18] show
that

$\displaystyle\liminf_{n\to\infty}\frac{1}{n}H(X^{n}(\mathbb{Q})|X^{n}({\mathbb{W}}^{x_{0}}))\geq\frac{1}{2}\mathbb{E}_{\mathbb{Q}}\left[\int_{0}^{1}\\{\Sigma_{t}-\log(\Sigma_{t})-1\\}\,dt\right],$
(3.3)

for all martingales, and conjecture that equality should hold for all
martingales (with absolutely continuous quadratic variation). We will see in
Section 5 that the Aldous martingale has finite specific entropy when using
the representation in the r.h.s. of (3.2). However
$H(X^{n}(\mathbb{Q})|X^{n}({\mathbb{W}}^{x_{0}}))=\infty$ for all
$n\in{\mathbb{N}}$ for _any_ win martingale, since
$X_{1}(\mathbb{Q})\in\\{0,1\\}$ $\mathbb{Q}$-a.s. For this reason (3.2) fails
even in the class of time-inhomogeneous diffusions, and it is crucial that we
use the representation in (1.3) / (3.2) as our definition of specific relative
entropy.

##  4\. First order conditions for martingale optimal transport

Following [22, 10, 14, 19] martingale versions of the classical transport
problem (see e.g. [25, 26, 24, 16] for recent monographs) are often considered
due to applications in mathematical finance but admit further applications,
e.g. to the Skorokhod problem [9, 12]. In analogy to classical optimal
transport, necessary and sufficient conditions for optimality have been
established for martingale transport (MOT) problems in discrete time ([11,
13]) but not so much is known for the continuous time problem.

We derive here a new first order condition for martingale transport in
continuous time which we then use to determine the structure of a candidate
optimizer for (1.1). Specifically, we consider the following MOT problem

$\displaystyle\inf\left\\{\mathbb{E}_{\mathbb{Q}}\left[\int_{0}^{1}c\left(t,X_{t},\Sigma_{t}\right)dt\right]:\mathbb{Q}\in\mathcal{M}^{c}([0,1]),\,X_{0}(\mathbb{Q})=\mu,X_{1}(\mathbb{Q})=\nu\right\\},$
(4.1)

where $\mathcal{M}^{c}([0,1])$ denotes the set of martingale measures on $C$
with an absolutely continuous quadratic variation, we denote by $X$ the
canonical process and by $\Sigma$ the density of its quadratic variation. As
above, we assumes $\mu\leq\nu$ in convex order, so that
$\mathcal{M}^{c}([0,1])$ is non empty.

######  Lemma 4.1.

[First order condition for MOT] Consider the MOT problem (4.1), and suppose
that $c$ is differentiable in its last variable, that $\mathbb{Q}$ is an
optimizer, and that

$t\mapsto
L_{t}:=\Sigma_{t}\partial_{\Sigma}c(t,X_{t},\Sigma_{t})-c(t,X_{t},\Sigma_{t}),$

is a continuous $\mathbb{Q}$-semimartingale. Then $(L_{t})_{t\in[0,1)}$ is a
martingale under $\mathbb{Q}$.

Of course if $c=c(\Sigma)$ is either convex or concave one can write
$xc^{\prime}(x)-c(x)=c^{*}\circ c^{\prime}(x)$ by the definition of the
convex/concave conjugate $c^{*}$.

###### Proof.

Consider now $H$ an absolutely continuous adapted process satisfying

$H_{0}=0=H_{1}\,\,\,\text{ and }\,\,\,h_{t}:=H_{t}^{\prime}\in(-1,1).$

It follows that for all $0\leq\varepsilon\leq 1$ the function

$\tau^{\varepsilon}_{t}=t+\varepsilon H_{t},$

defines a time change. Namely, this is a continuous increasing adapted process
starting at $0$ and ending at $1$. The time-changed martingale
$\omega^{\varepsilon}_{t}:=X_{\tau^{\varepsilon}_{t}}$ has the same starting
and final marginals, and so it must be suboptimal for the MOT problem. Since
the density of the quadratic variation of $\omega^{\varepsilon}_{t}$ is

$\Sigma_{\tau^{\varepsilon}_{t}}\cdot(\tau^{\varepsilon}_{t})^{\prime},$

we compute that the cost associated to $\omega^{\varepsilon}_{t}$ is

${\mathbb{E}}_{\mathbb{Q}}\int_{0}^{1}c\left(\tau^{\varepsilon}_{t},\omega^{\varepsilon}_{t},\Sigma_{\tau^{\varepsilon}_{t}}\cdot(\tau^{\varepsilon}_{t})^{\prime}\right)dt={\mathbb{E}}_{\mathbb{Q}}\int_{0}^{1}c\left(s,X_{s},\Sigma_{s}\cdot\\{(\tau^{\varepsilon}_{\cdot})^{\prime}\circ(\tau^{\varepsilon}_{s})^{-1}\right\\})\frac{ds}{(\tau^{\varepsilon}_{\cdot})^{\prime}\circ(\tau^{\varepsilon}_{s})^{-1}}.$

Since
$(\tau^{\varepsilon}_{\cdot})^{\prime}\circ(\tau^{\varepsilon}_{s})^{-1}=1+h_{(\tau^{\varepsilon}_{s})^{-1}}$,
we have

${\mathbb{E}}_{\mathbb{Q}}\int_{0}^{1}c\left(\tau^{\varepsilon}_{t},\omega^{\varepsilon}_{t},\Sigma_{\tau^{\varepsilon}_{t}}\cdot(\tau^{\varepsilon}_{t})^{\prime}\right)dt={\mathbb{E}}_{\mathbb{Q}}\int_{0}^{1}c\left(s,X_{s},\Sigma_{s}\\{1+h_{(\tau^{\varepsilon}_{s})^{-1}}\\}\right)\frac{ds}{1+h_{(\tau^{\varepsilon}_{s})^{-1}}}.$

Then a few computations reveal that

$\frac{d}{d\varepsilon}\Big{|}_{\varepsilon=0}\,{\mathbb{E}}_{\mathbb{Q}}\int_{0}^{1}c\left(\tau^{\varepsilon}_{t},\omega^{\varepsilon}_{t},\Sigma_{\tau^{\varepsilon}_{t}}\cdot(\tau^{\varepsilon}_{t})^{\prime}\right)dt={\mathbb{E}}_{\mathbb{Q}}\int_{0}^{1}\\{-c(s,X_{s},\Sigma_{s})+\partial_{\Sigma}c(s,X_{s},\Sigma_{s})\Sigma_{s}\\}h_{s}ds=0,$

for all $h=H^{\prime}$ as above. From this, and integration by parts, we have
that ${\mathbb{E}}_{\mathbb{Q}}\int_{0}^{1}H_{t}dL_{t}$ is equal to zero, for
all $H$ as above and with $L$ as in the statement of this lemma. We conclude
that $L$ must be a martingale for $t\in[0,1)$. ∎

Going back to (1.1), that is, $c(\Sigma)=\frac{1}{2}[\Sigma-\log(\Sigma)-1]$,
$\mu=\delta_{x_{0}}$, $\nu=x_{0}\delta_{1}+(1-x_{0})\delta_{0}$, the previous
lemma shows that if $\mathbb{Q}$ is optimal then

$t\mapsto\log(\Sigma_{t}),$

is a martingale under $\mathbb{Q}$. Passing to the notation where
$\Sigma=\sigma^{2}$ denotes the density of the quadratic variation, we also
conclude that

$t\mapsto\log(\sigma_{t}),$

is a martingale (we convene that $\sigma$ is the positive square root of
$\sigma^{2}$). If the coefficient $\sigma$ is Markovian, then the process
$\log(\sigma_{t})$ can only be a martingale if

$\displaystyle\left(\partial_{t}+\frac{1}{2}\sigma^{2}\partial^{2}_{xx}\right)\log\circ\sigma=0,$
(4.2)

We emphasize that this is exactly the PDE suggest by Aldous [2] for the
scaling limit of maximum entropy win martingales.

We will use this piece of information to obtain a candidate optimizer for the
problem at hand. To obtain further intuition on the structure of $\sigma$,
note the goal is to find the win martingale as close as possible to Brownian
motion, formalized by an entropy criterion. By the chain rule of entropy, this
suggests, independently of the behavior of the optimizer $M$ before it reaches
a level $m$ at time $t$, that the behavior from that time point on should be
optimal again. First of all, this indicates that the optimal $\sigma$ is
Markovian/feedback, so

$dM_{t}=\sigma(t,M_{t})dBt.$

In fact, due to special nature of the constraint to be a win martingale, we
can make even stronger guesses concerning the structure of $\sigma$: If we
start the optimization problem at time $t$ at level $M_{t}=x$ we face again
the problem to be as close as possible to Brownian motion subject to being a
martingale which terminates at time $1$ in a Bernoulli distribution. That is,
we face the very same optimization problem as at time $0$ apart from the fact
that the time horizon is now $1-t$ rather than $1$ in the original problem. We
thus expect the optimizer to be the same as the original optimizer, scaled by
the factor $1-t$, that is, run at a speed which is higher by a factor of
$\frac{1}{1-t}.$ As volatility is the square root of quadratic variation this
amounts to

$\displaystyle\sigma(t,x)=\frac{1}{\sqrt{1-t}}\sigma(1,x).$ (4.3)

Writing $\sigma(x):=\sigma(1,x)$ and plugging (4.3) into (4.2) yields

$\displaystyle\left(\partial_{t}+\frac{\sigma^{2}(x)}{2(1-t)}\partial^{2}_{xx}\right)\left(-\frac{1}{2}\log(1-t)+\log(\sigma(x))\right)=0,$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle-\frac{1}{2}\frac{1}{1-t}=\frac{1}{2}\frac{1}{1-t}\sigma^{2}(x)\left(\frac{\sigma^{\prime\prime}(x)\sigma(x)-(\sigma^{\prime}(x))^{2}}{\sigma(x)^{2}}\right)$
$\displaystyle\Leftrightarrow\quad$ $\displaystyle\hskip
22.76219pt-1=\sigma^{\prime\prime}(x)\sigma(x)-(\sigma^{\prime}(x))^{2}.$

This ODE is solved by $\sigma(x)=\frac{1}{\alpha}\sin(\alpha x+\beta)$ for
real constants $\alpha,\beta$. As the optimizer is supposed to terminate in
$0$ or $1$, the only reasonable choice here is $\alpha=\pi,\beta=0$. All in
all, our Ansatz for the optimal $\sigma$ is

$\bar{\sigma}(t,x):=\frac{\sin(\pi x)}{\pi\sqrt{1-t}}.$

##  5\. Optimality of the Ansatz

We denote by $\bar{M}^{s,x}$ the martingale which starts from time $s\leq 1$
at the position $x\in[0,1]$ and is determined by $\bar{\sigma}$. On $[s,1)$ it
satisfies the SDE

$d\bar{M}^{s,x}_{t}=\frac{\sin(\pi\bar{M}^{s,x}_{t})}{\pi\sqrt{1-t}}dB_{t}$

We remark that for all $\varepsilon$ small enough the coefficient
$\bar{\sigma}$ is smooth and has bounded derivatives of all orders for
$t\in(s,1-\varepsilon)$. In particular the above SDE admits a unique strong
solution on $[s,1)$. Observe that, for $x\in\\{0,1\\}$, if $M^{s,x}_{\ell}=0$
then also $M^{s,x}_{t}=0$ for all $t\in(\ell,1)$. In particular then we have
$0\leq\inf_{t\in[s,1)}\bar{M}_{t}^{s,x}\leq\sup_{t\in[s,1)}\bar{M}_{t}^{s,x}\leq
1$ a.s. Hence the martingale is bounded in $L^{p}$ for every $p$ and in
particular $\bar{M}^{x,s}_{1}:=\lim_{t\to 1}\bar{M}^{x,s}_{t}$ exists a.s. and
in $L^{2}$. Thus $\bar{M}^{x,s}_{1}\in[0,1]$ and
$\mathbb{E}[\langle\bar{M}^{x,s}\rangle_{1}]<\infty$, hence also

$\mathbb{E}\left[\int_{s}^{1}\frac{\sin^{2}(\pi\bar{M}^{s,x}_{t})}{1-t}dt\right]<\infty,$

and in particular
$\int_{s}^{1}\frac{\sin^{2}(\pi\bar{M}^{s,x}_{t})}{1-t}dt<\infty$ a.s. We
conclude that the event $\\{\bar{M}^{s,x}_{1}\in(0,1)\\}$ is negligible since
on this event
$\int_{s}^{1}\frac{\sin^{2}(\pi\bar{M}^{s,x}_{t})}{1-t}dt=+\infty$.

We summarise this discussion:

######  Lemma 5.1.

$\bar{M}^{s,x}$ is well-defined on the whole interval $[s,1]$, it is a
continuous martingale bounded in every $L^{p}$, and it satisfies
$\bar{M}^{s,x}_{1}\in\\{0,1\\}$ a.s. (implying that $\bar{M}^{s,x}_{1}\sim
Bernoulli(x)$).

In fact we have a bit more:

######  Lemma 5.2.

Let $x\in(0,1)=:I$. If $\tau$ denotes the first time that $\bar{M}^{s,x}$
exits $I$, then $\tau=1$ a.s.

###### Proof.

Wlog $s=0$. We define, for $t\in\mathbb{R}_{+}$, the martingale
$M_{t}:=\bar{M}^{0,x}_{1-\exp(-t)}$. Hence

$\langle
M\rangle_{t}=\int_{0}^{1-\exp(-t)}\frac{\sin^{2}(\pi\bar{M}^{0,x}_{u})}{\pi^{2}(1-u)}du=\int_{0}^{t}\frac{\sin^{2}(\pi
M_{s})}{\pi^{2}}ds,$

where we employed the change of variables $s=-\log(1-u)$. Hence $M$ satisfies
the SDE on $\mathbb{R}_{+}$

$dM_{t}=\frac{\sin(\pi M_{t})}{\pi}dW_{t},$

with $M_{0}=x\in I$. Observe that $\sigma^{2}(z):=\frac{\sin^{2}(\pi
z)}{\pi^{2}}>0$ for $z\in I$, and that $1/\sigma^{2}(z)$ is upper bounded on
every compact interval contained in $I$. Hence we can apply Feller’s test for
explosions (see e.g. [23, Theorem 5.29]), according to which $M$ does not
leave $I$ in finite time (a.s.) if and only if the function

$V(y):=\int_{1/2}^{y}\frac{y-z}{\sin^{2}(\pi z)}dz$

satisfies $V(0+)=V(1-)=\infty$. The latter is clearly fulfilled. ∎

######  Lemma 5.3.

The process $L_{t}:=\log\frac{\sin(\pi\bar{M}^{s,x}_{t})}{\pi\sqrt{1-t}}$ is a
martingale on $[0,1)$.

###### Proof.

Let $f(t,z):=\log\frac{\sin(\pi z)}{\pi\sqrt{1-t}}$ so
$L_{t}=f(t,\bar{M}^{s,x}_{t})$. Hence $\partial_{z}f=\frac{\pi\cos(\pi
z)}{\sin(\pi z)}$ and so

$\int_{s}^{s^{\prime}}\partial_{z}f(t,\bar{M}^{s,x}_{t})d\bar{M}^{s,x}_{t}=\int_{s}^{s^{\prime}}\frac{\cos(\pi\bar{M}^{s,x}_{t})}{\sqrt{1-t}}dB_{t},$

which is a local martingale bounded in $L^{1}$ as long as
$t\in[0,1-\varepsilon]$. Hence it is an actual martingale on
$[0,1-\varepsilon]$ for $0<\varepsilon<1$ arbitrary, and thus also a
martingale on $[0,1)$. On the other hand

$\displaystyle\partial_{t}f(t,z)+\frac{\bar{\sigma}(t,z)}{2}\partial^{2}_{zz}f(t,z)$
$\displaystyle=\partial_{t}f(t,z)+\frac{\sin^{2}(\pi
z)}{2\pi^{2}(1-t)}\partial^{2}_{zz}f(t,z)$
$\displaystyle=\frac{1}{2(1-t)}+\frac{\sin^{2}(\pi
z)}{2\pi^{2}(1-t)}\partial_{z}\left(\frac{\pi\cos(\pi z)}{\sin(\pi z)}\right)$
$\displaystyle=\frac{1}{2(1-t)}-\frac{1}{2(1-t)}\\{\sin^{2}(\pi
z)+\cos^{2}(\pi z)\\}$ $\displaystyle=0.$

Hence

$L_{t}=L_{s}+\int_{s}^{t}\frac{\cos(\pi\bar{M}^{s,x}_{u})}{\sqrt{1-u}}dB_{u},$

and we conclude. ∎

Associated to the martingale $\bar{M}$ we define its cost

$\displaystyle\bar{v}(s,x):=\frac{1}{2}\mathbb{E}\left[\int_{s}^{1}\left\\{\frac{\sin^{2}(\pi\bar{M}^{s,x}_{t})}{\pi^{2}(1-t)}-2\log\frac{\sin(\pi\bar{M}^{s,x}_{t})}{\pi\sqrt{1-t}}-1\right\\}dt\right].$
(5.1)

######  Lemma 5.4.

We have

$\bar{v}(s,x)=\frac{x-x^{2}-1+s}{2}-(1-s)\log\left(\frac{\sin(\pi
x)}{\pi\sqrt{1-s}}\right).$

###### Proof.

Clearly

$\frac{1}{2}\mathbb{E}\left[\int_{s}^{1}\left\\{\frac{\sin^{2}(\pi\bar{M}^{s,x}_{t})}{\pi^{2}(1-t)}-1\right\\}dt\right]=\frac{1}{2}\mathbb{E}[(\bar{M}^{s,x}_{1})^{2}-(\bar{M}^{s,x}_{s})^{2}+s-1]=\frac{x-x^{2}-1+s}{2}.$

On the other hand, owing to Lemma 5.3 we have

$\mathbb{E}\left[\int_{s}^{1}\log\frac{\sin(\pi\bar{M}^{s,x}_{t})}{\pi\sqrt{1-t}}dt\right]=\int_{s}^{1}\mathbb{E}\left[\log\frac{\sin(\pi\bar{M}^{s,x}_{t})}{\pi\sqrt{1-t}}\right]dt=(1-s)\log\frac{\sin(\pi
x)}{\pi\sqrt{1-s}},$

where the exchange between expectation and integral is justified by the fact
that $\log(1-t)$ is integrable on $[s,1]$ and
$\log(\sin(\pi\bar{M}^{s,x}_{t}))$ has a constant sign. We conclude. ∎

######  Lemma 5.5.

$\bar{\sigma}^{2}(t,x)$ is the unique minimizer of the function

$[0,\infty)\ni\Sigma\mapsto\Sigma\partial^{2}_{xx}\bar{v}(t,x)+\Sigma-\log\Sigma.$

###### Proof.

The function in the statement is strictly convex so its unique minimizer can
be found by equating its derivative to zero. This means
$\partial^{2}_{xx}\bar{v}(t,x)+1=1/\Sigma$. So we only have to check that

$\bar{\sigma}^{2}(t,x):=\frac{\sin^{2}(\pi
x)}{\pi^{2}(1-t)}=\frac{1}{1+\partial^{2}_{xx}\bar{v}(t,x)}.$

But from Lemma 5.4 we have

$\partial^{2}_{xx}\bar{v}(t,x)=\frac{\pi^{2}(1-t)}{\sin^{2}(\pi x)}-1,$

which concludes the proof. ∎

######  Lemma 5.6.

On $(0,1)\times(0,1)$ we have

$\partial_{t}\bar{v}(t,x)+\frac{1}{2}\inf_{\Sigma\geq
0}\,\\{\Sigma\,\partial^{2}_{xx}\bar{v}(t,x)+\Sigma-\log\Sigma-1\\}=0.$

###### Proof.

By (5.1) we have that

$t\mapsto\bar{v}(t,\bar{M}^{0,x})+\frac{1}{2}\int_{0}^{t}\\{\bar{\sigma}^{2}(\bar{M}^{0,x}_{u})-\log\bar{\sigma}^{2}(\bar{M}^{0,x}_{u})-1\\}du$

is a martingale. Since $\bar{M}^{0,x}$ does not leave $(0,1)$ this means that

$\partial\bar{v}(t,z)+\frac{1}{2}\bar{\sigma}^{2}(t,z)\partial_{zz}\bar{v}(t,z)+\frac{1}{2}\\{\bar{\sigma}^{2}(t,z)-\log\bar{\sigma}^{2}(t,z)-1\\}=0.$

But then by Lemma 5.5 the l.h.s. above is equal to
$\partial_{t}\bar{v}(t,x)+\frac{1}{2}\inf_{\Sigma\geq
0}\,\\{\Sigma\,\partial^{2}_{xx}\bar{v}(t,x)+\Sigma-\log\Sigma-1\\}$. ∎

######  Lemma 5.7.

For $s\in[0,1)$ and $x\in(0,1)$ let

$\tilde{v}(s,x):=\frac{x-x^{2}-1+s}{2}-(1-s)\log\left(\frac{\sqrt{x(1-x)}}{\sqrt{1-s}}\right),$

and

$v(s,x):=\inf\frac{1}{2}\mathbb{E}\left[\int_{s}^{1}\left\\{\sigma_{t}^{2}-\log(\sigma_{t}^{2})-1\right\\}dt\right],$

where the infimum runs over all martingales $M$ on $[s,1]$, starting at $x$,
satisfying $dM_{t}=\sigma dW_{t}$, and such that $M_{1}\in\\{0,1\\}$.

Then $v(\cdot,\cdot)\geq\tilde{v}(\cdot,\cdot)$ and there is
$\delta\in(0,\infty)$ such that

$\displaystyle\left|2\tilde{v}(s,x)-\bar{v}(s,x)\right|\leq\frac{|x-x^{2}-1+s+(1-s)\log(1-s)|}{2}+\delta\cdot(1-s).$
(5.2)

###### Proof.

By Jensen’s inequality

$\mathbb{E}\left[\int_{s}^{1}\left\\{\sigma_{t}^{2}-\log(\sigma_{t}^{2})-1\right\\}dt\right]\geq\mathbb{E}\left[\int_{s}^{1}\sigma_{t}^{2}dt\right]-(1-s)\log\left(\frac{\mathbb{E}\left[\int_{s}^{1}\sigma_{t}^{2}dt\right]}{1-s}\right)-(1-s).$

If $M$ participates in the infimum defining $v(s,x)$, then $M_{1}\sim B(x)$
and so
$\mathbb{E}\left[\int_{s}^{1}\sigma_{t}^{2}dt\right]=\mathbb{E}[M_{1}^{2}-M_{s}^{2}]=x-x^{2}=x(1-x)$.
This shows that $v\geq\tilde{v}$. On the other hand

$\displaystyle 2\tilde{v}(s,x)-\bar{v}(s,x)$
$\displaystyle=\frac{x-x^{2}-1+s+(1-s)\log(1-s)}{2}-(1-s)\log\left(\frac{\pi
x(1-x)}{\sin(\pi x)}\right),$

and we obtain (5.2) by noticing that

$0<\inf_{x\in[0,1]}\frac{\pi x(1-x)}{\sin(\pi x)}\leq\sup_{x\in[0,1]}\frac{\pi
x(1-x)}{\sin(\pi x)}<+\infty.$

∎

######  Lemma 5.8.

Let $M$ be feasible for our minimization problem (started from $x_{0}$ at time
0), and denote by $\Sigma_{t}$ the density of its quadratic variation. Suppose
that $\mathbb{E}[\int_{0}^{1}\log\Sigma_{t}dt]$ is finite, that $M_{t}$ does
not leave the interval $(0,1)$ until time $t=1$, and that the process
$t\mapsto\int_{0}^{t}(1-s)\cot(\pi M_{s})dM_{s}$ is a martingale on $[0,1]$.
Then the process

$t\mapsto
R_{t}^{M}:=\bar{v}(t,M_{t})+\frac{1}{2}\int_{0}^{t}\\{\Sigma_{s}-\log\Sigma_{s}-1\\}ds$

is a submartingale on $[0,1]$, and it is actually a martingale on $[0,1]$ for
$M=\bar{M}^{0,x_{0}}$ and $\Sigma_{t}=\bar{\sigma}(t,\bar{M}^{0,x_{0}}_{t})$.

###### Proof.

By Lemma 5.6 we have

$\partial_{t}\bar{v}(t,M_{t})+\frac{1}{2}\\{\Sigma_{t}\partial^{2}_{xx}\bar{v}(t,M_{t})+\Sigma_{t}-\log\Sigma_{t}-1\\}\geq
0,$

from which, thanks to Ito formula, the local submartingale property of $R^{M}$
follows. To check that this process is an actual submartingale, we need to
establish that $\int_{0}^{t}\partial_{x}\bar{v}(s,M_{s})dM_{s}$ is a
martingale. But

$\int_{0}^{t}\partial_{x}\bar{v}(s,M_{s})dM_{s}=\int_{0}^{t}\left\\{\frac{1-2M_{s}}{2}-\pi(1-s)\cot(\pi
M_{s})\right\\}dM_{s},$

which by assumption is indeed a martingale.

On the other hand, for $M=\bar{M}^{0,x_{0}}$ and
$\Sigma_{t}=\bar{\sigma}(t,\bar{M}^{0,x_{0}}_{t})$ we have

$\partial_{t}\bar{v}(t,\bar{M}^{0,x_{0}}_{t})+\frac{1}{2}\\{\bar{\sigma}(\bar{M}^{0,x_{0}}_{t})^{2}\partial^{2}_{xx}\bar{v}(t,\bar{M}^{s,x_{0}}_{t})+\bar{\sigma}(\bar{M}^{0,x_{0}}_{t})^{2}-\log\bar{\sigma}(\bar{M}^{0,x_{0}}_{t})^{2}-1\\}=0,$

so by the same token the process $R^{\bar{M}}$ is a local martingale. This
time around

$\int_{0}^{t}\partial_{x}\bar{v}(s,\bar{M}^{0,x_{0}}_{s})d\bar{M}^{0,x_{0}}_{s}=\int_{0}^{t}\left\\{\frac{1-2\bar{M}^{0,x_{0}}_{s}}{2}-\pi(1-s)\cot(\pi\bar{M}^{0,x_{0}}_{s})\right\\}\frac{\sin(\pi\bar{M}^{0,x_{0}}_{s})}{\pi\sqrt{1-s}}dB_{s},$

which is a martingale. We conclude that $R^{\bar{M}}$ is a martingale. ∎

We can now carry on the verification argument, showing the optimality of
$\bar{M}$:

###### Proof.

If $M$ fulfils the assumptions in Lemma 5.8, then we have

$\displaystyle\mathbb{E}\left[\frac{1}{2}\int_{0}^{1}\\{\Sigma_{s}-\log\Sigma_{s}-1\\}ds\right]$
$\displaystyle=\mathbb{E}\left[\bar{v}(1,M_{1})+\frac{1}{2}\int_{0}^{1}\\{\Sigma_{s}-\log\Sigma_{s}-1\\}ds\right]$
$\displaystyle\geq\bar{v}(0,x_{0})$
$\displaystyle=\mathbb{E}\left[\bar{v}(1,\bar{M}^{0,x_{0}}_{1})+\frac{1}{2}\int_{0}^{1}\\{\bar{\sigma}(\bar{M}^{0,x_{0}}_{s})^{2}-\log\bar{\sigma}(\bar{M}^{0,x_{0}}_{s})^{2}-1\\}ds\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{2}\int_{0}^{1}\\{\bar{\sigma}(\bar{M}^{0,x_{0}}_{s})^{2}-\log\bar{\sigma}(\bar{M}^{0,x_{0}}_{s})^{2}-1\\}ds\right],$

showing that $\bar{M}^{0,x_{0}}$ is better than $M$ (i.e. $M$ is sub-optimal
compared to $\bar{M}^{0,x_{0}}$).

Let now $M$ be feasible and wlog such that
$\mathbb{E}[\int_{0}^{1}\log\Sigma_{t}dt]$ is finite. For $\varepsilon$ small
we define $\tau^{\varepsilon}:=\inf\\{t:M_{t}\leq\varepsilon\text{ or
}M_{t}\geq 1-\varepsilon\\}$. We then define the martingale $M^{\varepsilon}$
as follows: for $t\leq
t^{\varepsilon}:=\min\\{1-\varepsilon,\tau^{\varepsilon}\\}$ we set
$M^{\varepsilon}_{t}:=M_{t}$, whereas for $t\in(t^{\varepsilon},1]$ we set
$M^{\varepsilon}_{t}:=\bar{M}^{t^{\varepsilon},M_{t^{\varepsilon}}}_{t}$.
Hence $M^{\varepsilon}$ is just the continuous pasting (concatenation) of $M$
and $\bar{M}$ at time $t^{\varepsilon}$. One easily checks that
$M^{\varepsilon}$ fulfils the assumptions in Lemma 5.8, for all
$\varepsilon>0$. If $\Sigma^{\varepsilon}$ is the density of the quadratic
variation of $M^{\varepsilon}$, then

$\displaystyle\frac{1}{2}\mathbb{E}\left[\int_{0}^{1}\\{\Sigma^{\varepsilon}_{t}-\log\Sigma^{\varepsilon}_{t}-1\\}dt\right]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\mathbb{E}\left[\int_{0}^{t^{\varepsilon}}\\{\Sigma_{t}-\log\Sigma_{t}-1\\}dt\right]+\frac{1}{2}\mathbb{E}\left[\int^{1}_{t^{\varepsilon}}\\{\bar{\sigma}^{2}(t,\bar{M}_{t}^{t^{\varepsilon},M_{t^{\varepsilon}}})-\log\bar{\sigma}^{2}(t,\bar{M}_{t}^{t^{\varepsilon},M_{t^{\varepsilon}}})-1\\}dt\right]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\mathbb{E}\left[\int_{0}^{t^{\varepsilon}}\\{\Sigma_{t}-\log\Sigma_{t}-1\\}dt\right]+\mathbb{E}[\bar{v}(t^{\varepsilon},M_{t^{\varepsilon}})].$

For the time being let us assume that

$\displaystyle\limsup_{\varepsilon\searrow
0}\mathbb{E}[\bar{v}(t^{\varepsilon},M_{t^{\varepsilon}})]=0.$ (5.3)

Then, since $t^{\varepsilon}\nearrow 1$ as $\varepsilon\searrow 0$, this would
entail

$\limsup_{\varepsilon\to
0}\frac{1}{2}\mathbb{E}\left[\int_{0}^{1}\\{\Sigma^{\varepsilon}_{t}-\log\Sigma^{\varepsilon}_{t}-1\\}dt\right]\leq\frac{1}{2}\mathbb{E}\left[\int_{0}^{1}\\{\Sigma_{t}-\log\Sigma_{t}-1\\}dt\right],$

so that $M$ is sub-optimal compared to $\bar{M}^{0,x_{0}}$. Hence to finish
the proof we have to establish (5.3). For this purpose, owing to (5.2), it is
enough to check that

$\displaystyle\limsup_{\varepsilon\searrow
0}\mathbb{E}[\tilde{v}(t^{\varepsilon},M_{t^{\varepsilon}})]\leq 0,$ (5.4)

with $\tilde{v}$ defined in Lemma 5.7. Taking $v$ from that same lemma, we
find

$\displaystyle\frac{1}{2}\mathbb{E}\left[\int_{0}^{1}\\{\Sigma_{t}-\log\Sigma_{t}-1\\}dt\right]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\mathbb{E}\left[\int_{0}^{t^{\varepsilon}}\\{\Sigma_{t}-\log\Sigma_{t}-1\\}dt\right]+\frac{1}{2}\mathbb{E}\left[\int_{t^{\varepsilon}}^{1}\\{\Sigma_{t}-\log\Sigma_{t}-1\\}dt\right]$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\mathbb{E}\left[\int_{0}^{t^{\varepsilon}}\\{\Sigma_{t}-\log\Sigma_{t}-1\\}dt\right]+\mathbb{E}[v(t^{\varepsilon},M_{t^{\varepsilon}})]$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\mathbb{E}\left[\int_{0}^{t^{\varepsilon}}\\{\Sigma_{t}-\log\Sigma_{t}-1\\}dt\right]+\mathbb{E}[\tilde{v}(t^{\varepsilon},M_{t^{\varepsilon}})],$

as $v\geq\tilde{v}$. Since $\mathbb{E}[\int_{0}^{1}\log\Sigma_{t}dt]$ is
finite, we can derive (5.4) from this. ∎

We close this part remarking on the uniqueness of optimizers to Problem (1.1):
As the previous proofs show, the only way for $\Sigma$ to be optimal is by
making

$\partial_{t}\bar{v}(t,M_{t})+\frac{1}{2}\\{\Sigma_{t}\partial^{2}_{xx}\bar{v}(t,M_{t})+\Sigma_{t}-\log\Sigma_{t}-1\\}$

be equal to zero. By Lemma 5.5 this is only achieved by the Aldous martingale.

## References

  * [1] D. Aldous.  notes, https://www.stat.berkeley.edu/ aldous/Research/OP/ent-MG.pdf.
  * [2] D. Aldous.  What is the max-entropy win-probability martingale?  https://www.stat.berkeley.edu/ aldous/Research/OP/maxentmg.html.
  * [3] D. Aldous.  Using prediction market data to illustrate undergraduate probability.  The American Mathematical Monthly, 120(7):pp. 583–593, 2013.
  * [4] M. Avellaneda.  Calibrating volatility surfaces via relative-entropy minimization.  Quantitative Finance, 1(1):42–51, 2001.
  * [5] J. Backhoff-Veraguas, M. Beiglböck, M. Huesmann, and S. Källblad.  Martingale Benamou-Brenier: a probabilistic perspective.  Ann. Probab., 48(5):2258–2289, 2020.
  * [6] J. Backhoff Veraguas, M. Beiglböck, W. Schachermayer, and B. Tschiderer.  The structure of martingale benamou–brenier in multiple dimensions.  ArXiv e-prints, 2023.
  * [7] J. Backhoff-Veraguas and C. Unterberger.  On the specific relative entropy between martingale diffusions on the line.  2022\.
  * [8] R. Bass.  Skorokhod embedding via stochastic integrals.  In J. Azéma and M. Yor, editors, Séminaire de Probabilités XVII 1981/82, number 986 in Lecture Notes in Mathematics, pages 221–224. Springer, 1983.
  * [9] M. Beiglböck, A. Cox, and M. Huesmann.  Optimal transport and Skorokhod embedding.  Invent. Math., 208(2):327–400, 2017.
  * [10] M. Beiglböck, P. Henry-Labordère, and F. Penkner.  Model-independent bounds for option prices: A mass transport approach.  Finance Stoch., 17(3):477–501, 2013.
  * [11] M. Beiglböck and N. Juillet.  Shadow couplings.  Trans. Amer. Math. Soc., to appear, 2021.
  * [12] M. Beiglböck, M. Nutz, and F. Stebegg.  Fine properties of the optimal Skorokhod embedding problem.  J. Eur. Math. Soc. (JEMS), 24(4):1389–1429, 2022.
  * [13] M. Beiglböck, M. Nutz, and N. Touzi.  Complete duality for martingale optimal transport on the line.  Ann. Probab., 45(5):3038–3074, 2017.
  * [14] B. Bouchard and M. Nutz.  Arbitrage and duality in nondominated discrete-time models.  The Annals of Applied Probability, 25(2):823–859, 2015.
  * [15] A. Cohen and Y. Dolinsky.  A scaling limit for utility indifference prices in the discretised bachelier model.  Finance and Stochastics, 26(2):335–358, 2022.
  * [16] A. Figalli and F. Glaudo.  An invitation to optimal transport, Wasserstein distances, and gradient flows.  EMS Textbooks in Mathematics. EMS Press, Berlin, [2021] ©2021.
  * [17] H. Föllmer.  Doob decomposition, Dirichlet processes, and entropies on Wiener space.  In Dirichlet forms and related topics, volume 394 of Springer Proc. Math. Stat., pages 119–141. Springer, Singapore, [2022] ©2022.
  * [18] H. Föllmer.  Optimal couplings on Wiener space and an extension of Talagrand’s transport inequality.  In Stochastic analysis, filtering, and stochastic optimization, pages 147–175. Springer, Cham, [2022] ©2022.
  * [19] A. Galichon, P. Henry-Labordère, and N. Touzi.  A stochastic control approach to no-arbitrage bounds given marginals, with an application to lookback options.  Ann. Appl. Probab., 24(1):312–336, 2014.
  * [20] N. Gantert.  Einige grosse Abweichungen der Brownschen Bewegung, volume 224 of Bonner Mathematische Schriften [Bonn Mathematical Publications].  Universität Bonn, Mathematisches Institut, Bonn, 1991.  Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn, Bonn, 1991.
  * [21] G. Guo, D. Possamaï, and C. Reisinger.  Randomness and early termination: what makes a game exciting?, 2023.
  * [22] D. Hobson and A. Neuberger.  Robust bounds for forward start options.  Math. Finance, 22(1):31–56, 2012.
  * [23] I. Karatzas and S. Shreve.  Brownian motion and stochastic calculus, volume 113.  Springer Science & Business Media, 2012.
  * [24] F. Santambrogio.  Optimal transport for applied mathematicians, volume 87 of Progress in Nonlinear Differential Equations and their Applications.  Birkhäuser/Springer, Cham, 2015.  Calculus of variations, PDEs, and modeling.
  * [25] C. Villani.  Topics in optimal transportation, volume 58 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2003.
  * [26] C. Villani.  Optimal Transport. Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften.  Springer, 2009.