TITLE: Closed set in uniform norm?
QUESTION [0 upvotes]: Let $\Omega$ be a bounded open set of $\mathbb R^d$ and consider the space $C^1(\overline \Omega)$ equipped with the norm
$$
|| f || = \max_{x \in \overline \Omega} |f(x)| + \sum_{j=1}^d \max_{x \in \overline \Omega} |\partial_j f(x)|.
$$
Moreover, consider the set $A := \{ f \in C^1(\overline \Omega) \mid (\exists \, g \in C(\overline\Omega)) \ f=x_1 g \quad \text{in} \quad  \overline \Omega \}$.
Is $A$ closed set?
I've tried taking $\{f_n\}_{n\geq 1} \subset A$ such that $||f_n-f|| \xrightarrow{n\to\infty}0$, for some $f \in C^1(\overline \Omega)$, but I haven't been able to show that $f=x_1 g$, for some $g \in C(\overline\Omega)$.
This impossibility to show my statement just make me think that maybe it is false. Although, I haven't found a counterexample yet.

REPLY [1 votes]: Ok, by the form of the norm, it is complete, so if $f_n$ is a cauchy sequence, then the limit is in the space. So convergence=cauchy sequence. That fact also establishes that $g$ is in the space. And a set $S$ is closed in a normed space if every convergent sequence of elements in the set $S$, has the limit in the set $S$, so if we gave us a convergent sequence, it is the same thing as if we gave us a cauchy sequence.


text:
\begin{document}

\title{Empirical Coordination for Joint Source-Channel Coding}

\author{\IEEEauthorblockN{Ma\"{e}l Le Treust}\\
\IEEEauthorblockA{
ETIS, CNRS UMR8051, ENSEA, Université de Cergy-Pontoise,\\
6, avenue du Ponceau,\\
95014 CERGY-PONTOISE CEDEX,\\
FRANCE\\
Email: mael.le-treust@ensea.fr}
}

\maketitle

\begin{abstract}
We investigate the problem of simultaneous transmission and coordination for a point-to-point communication model. The encoder and decoder choose their symbols/actions (i.e. channel input and decoder output) in order to transmit information and to coordinate themselves. This paradigm has promising repercussions for future decentralized networks. Exploiting the coordination capabilities, devices can implement decentralized policies that are coordinated. Exploiting transmission capabilities, devices choose their actions (power control, the channel allocation) in order to encode  additional embedded information (channel state information, future allocations). The feasible trade-offs between transmissions and coordinations are characterized using joint probability distributions over the source and channel symbols. Encoder and decoder implement a coding scheme such that the empirical frequency of symbols are close to target joint probability distribution. We characterize the set of achievable probability distribution for a point-to-point source-channel model with strictly-causal and causal decoding. Compared to classical coding results, the coordination requirement induces a stronger information constraint. We determine optimal trade-offs between transmission and coordination by maximizing a utility function over the set of achievable probability distribution.
\end{abstract}

\begin{IEEEkeywords}
Shannon Theory, Empirical Coordination, Joint Source-Channel Coding Problem, Empirical Distribution of Symbols, Strictly Causal Decoding.
\end{IEEEkeywords}

\IEEEpeerreviewmaketitle

\section{Introduction}\label{sec:Introduction}

Transmission and coordination paradigms are promising challenges for future communication networks. We investigate both paradigms simultaneously considering a simple model of point-to-point  communication represented by Fig. \ref{fig:1CwithChannel}. Encoder and decoder transmit informations and coordinate their actions (i.e. channel input and decoder output). We determine the optimal trade-off between both objectives, coordination and transmission, using a two-step approach. First, we characterize the set of joint probability distributions the encoder and the decoder can achieve with empirical frequency of symbols of source and channel. Second, we determine optimal transmission/coordination trade-off  by maximizing a utility function over the corresponding set of joint probability distributions.

This paradigms have been investigated recently in the literature. Empirical coordination of symbols was investigated in \cite{WeissmanOrdentlich05}, for $k$ consecutive symbols and in \cite{KramerSavari07} from a quantum coding perspective. In \cite{CuffPermuterCover10}, the authors consider the coordination of actions, nodes can implement in a network with communication constraints. They propose two different notions of coordination referred as empirical coordination and strong coordination. In some cases, both notions coincide as soon as nodes have enough common randomness. Practical coding schemes based on polar codes are proposed in \cite{BlascoThobabenSkoglund12}, in order to achieve empirical coordination and in \cite{BlochLuzziKliewer12}, in order to achieve strong coordination.
In \cite{AsnaniPermuterWeissman13}, the authors investigate coordination for multi-terminal network by considering two decoders that cooperate using cribbing functions. Strong coordination for a three-terminal line network was studied in \cite{BlochKliewer13} and inner/outer bounds for the coordination capacity region are derived.
In \cite{BereyhiBahramiMirmohseniAref13}, the authors investigate the empirical coordination capacity region of a triangular multi-terminal network for which they also provide inner and outer bounds.

Problems of coordination and transmission have also been investigated in the literature of game theory especially in  \cite{GossnerHernandezNeyman06}.
\begin{figure}[!ht]
\begin{center}
\psset{xunit=1cm,yunit=1cm}
\begin{pspicture}(0,-0.5)(7.5,1.5)
\pscircle(0,0.5){0.5}
\psframe(1.5,0)(2.5,1)
\pscircle(4,0.5){0.5}
\psframe(5.5,0)(6.5,1)
\psline[linewidth=1pt]{->}(0.5,0.5)(1.5,0.5)
\psline[linewidth=1pt]{->}(2.5,0.5)(3.5,0.5)
\psline[linewidth=1pt]{->}(4.5,0.5)(5.5,0.5)
\psline[linewidth=1pt]{->}(6.5,0.5)(7.5,0.5)

\rput[u](1,0.8){$U^n$}

\rput[u](3,0.8){$X^{i-1}$}
\rput[u](5,0.8){$Y^{i-1}$}
\rput[u](7,0.8){${V}_i$}
\rput(0,0.5){$\PP_{\sf{u}}$}
\rput(2,0.5){$\C$}
\rput(4,0.5){$\mc{T}_{\sf{y|x}}$}
\rput(6,0.5){$\D$}

\end{pspicture}
\caption{Encoder and Decoder implement a coding scheme such that empirical frequency of symbols are close to joint probability distribution  $\QQ$ defined over $\mc{U} \times \mc{X} \times \mc{Y} \times \mc{V} $. Equivalently, sequences of symbols $(U^n ,X^n,Y^n,V^n) \in A_{\varepsilon}^{{\star}{n}}(\QQ)$ are jointly typical for probability distribution $\QQ$. The decoder is strictly causal, i.e. $V_i = g(Y^{i-1})$ for all instant $i\in\{1, \ldots ,n\}$. We characterize the set of probability distributions $\QQ$ that are achievable.}
\label{fig:1CwithChannel}
\end{center}
\end{figure}

The authors consider a point-to-point communication model with an information source and a perfect channel. They characterize the set of joint distribution, the encoder and the decoder can implement over the empirical frequency of symbols of source and channel. This set of achievable joint distribution is used to maximize a utility function that incites the encoder and decoder to coordinate their actions with the information source. Since the decoder does not observe the information source, transmission is necessary for the coordination to be possible. Strictly causal decoding is assumed since the encoder and decoder choose their action simultaneously. The results of \cite{GossnerHernandezNeyman06} has been extended in \cite{Cuff(ImplicitCoordination)10} where the strictly causal observation of source symbols by the decoder has been removed without changing the information constraint. The case of imperfect channel between the encoder and the decoder is stated without proof in \cite{GossnerHernandezNeyman06} and is characterized in \cite{SamsonBenjaminISIT13}. The authors apply their result to  the scenario of interference channel in which power control is used to encode embedded data about the channel states information (CSI).

The paradigm of simultaneous transmission and coordination proposes very promising developments in information and communication theories, especially for decentralized networks. Exploiting the coordination capabilities, devices can organize themselves in order to implement decentralized and coordinated policies. Exploiting transmission capabilities,  devices can use power control, channel allocation, amplitude or frequency, in order to encode additional information as CSI, future power control or channel allocations. This problematic reinforces the connection between the literatures of information theory and game theory following \cite{LetreustZaidiLasaulce(Allerton)11}, \cite{BerryTse(ShannonMetNash)11} and \cite{LetreustLasaulce(DGAA)12}.

In this paper, we determine the transmissions and coordinations that are feasible using a set of joint probability distribution over the symbols of source and channel. We investigate a simple point-to-point source-channel problem with i.i.d. information source and memoryless transition probability represented by Fig. \ref{fig:1CwithChannel}. Encoder and decoder choose their actions (i.e. channel input and decoder output) in order to implement  empirical distribution over sequences of symbols of source and channel. We assume  a strictly causal decoding, i.e. at each instant, the decoder returns a symbol/action based on the observation of the past channel outputs. This assumption allows to investigate on-line coordination between encoder and decoder that choose their actions simultaneously. This hypothesis has no impact if only transmission is studied but modifies the information constraint as soon as coordination is required. Compared to classical results for joint source-channel coding \cite{shannon-bell-1948}, the coordination requirement induces a stronger information constraint.

Sec. \ref{sec:ModelDefinition} presents the channel model under investigation and the notions of achievable empirical distribution and strictly causal decoding. In Sec. \ref{sec:MainResult}, we characterize the set of achievable empirical distribution. Sec. \ref{sec:PreviousWork} compare this result with previous works existing in the literature. Sec. \ref{sec:DistortionCost} relates our result to the problem of achievable source-distortion and channel-cost. Sec. \ref{sec:ExampleBSBSC} provides a simple example of binary information source and binary symmetric channel. In Sec. \ref{sec:ConvexOptimization}, we prove that the set of achievable empirical distribution is convex. An example of utility maximization is stated in Sec. \ref{sec:ExampleMatchingPennies}. In Sec. \ref{sec:CwithChannel}, we consider a causal decoding instead of strictly causal decoding. Sec. \ref{sec:Conclusion} concludes the article and the proof of the main results are presented in App. \ref{sec:ProofDecomposition}, \ref{sec:ProofAchievability}, \ref{sec:ProofConverse}, \ref{sec:CardinalityBound}, \ref{sec:ProofCoro} and \ref{sec:ProofTheoConvex}.

\section{System Model}\label{sec:ModelDefinition}

The problem under investigation is depicted in Fig. \ref{fig:1CwithChannel}. Capital letter $U$ denotes the random variable and lowercase letter $u\in\mc{U}$ denote the realization. We denote by $U^n$, $X^n$, $Y^n$, $V^n$ the sequences of random variables of the source symbols $u^n=(u_1,\ldots,u_n)\in\mc{U}^n$, of channel inputs $x^n\in\mc{X}^n$, of channel outputs $y^n\in\mc{Y}^n$ and of outputs of the decoder $v^n\in\mc{V}^n$. We assume the sets $\mc{U}$, $\mc{X}$, $\mc{Y}$ and $\mc{V}$ are discrete and $\mc{U}^n$ denote the $n$-time cartesian product of set $\mc{U}$.  Notation $\Delta(\mc{X})$ stands for the set of the probability distributions $\PP(X)$ over the set $\mc{X}$. The variational distance between probabilities $\QQ$ and $\PP$ is denoted by $||\QQ - \PP||_{\sf{v}}= 1/2\cdot \sum_{x\in\mc{X}} |\QQ(x) - \PP(x)|$. The Markov chain property is denoted by $Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  U$ and it holds if for all $(u,x,y)$, we have $\QQ(y|x,u) = \QQ(y|x)$. The information source is i.i.d. distributed with $\PP_{\sf{u}}$ and the channel is memoryless  with transition probability $\mc{T}_{\sf{y|x}}$. The statistics of $\PP_{\sf{u}}$ and $\mc{T}_{\sf{y|x}}$ are known by both encoder $\C$ and decoder $\D$.

Coding Process: A sequence of source symbols $u^n\in\mc{U}^n$ is drawn from the i.i.d. probability distribution defined by equation \eqref{eq:SourceProba}. Encoder $\C$ observes $u^n\in\mc{U}^n$  and sends a sequence of channel inputs $x^n\in\mc{X}^n$. The sequence of channel outputs $y^n \in \mc{Y}^n$ is drawn according to the discrete and memoryless transition probability defined by equation (\ref{eq:TransitionProba}).
\begin{eqnarray}
\mc{P}_{\sf{u}}^{\otimes n}(u^n)= \prod_{i=1}^n \mc{P}_{\sf{u}}(u_i),\label{eq:SourceProba}\\
\mc{T}^{\otimes n}(y^n|x^n)= \prod_{i=1}^n \mc{T}(y_i|x_i).\label{eq:TransitionProba}
\end{eqnarray}
We consider that the decoder is strictly causal. At instant $i\in\{1,\ldots,n\}$, decoder $\D$ observes the sequence of past channel outputs $y^{i-1} = (y_1,\ldots,y_{i-1}) \in \mc{Y}^{i-1}$ and returns a output symbol $v_i \in \mc{V}_i$. The objective of this work is to characterizes the set of empirical distribution $\QQ \in \Delta(\mc{U} \times \mc{X} \times \mc{Y} \times \mc{V}  ) $ that are achievable, i.e. for which the encoder and decoder can implement sequences of symbols  $(U^n ,X^n,Y^n,V^n) \in A_{\varepsilon}^{{\star}{n}}(\QQ)$ that are jointly typical for probability distribution $\QQ$ with high probability. The definition of typical sequences is stated pp. 27 in \cite{ElGammalKim(book)11}.

\begin{definition}\label{def:Code}
A  code $c\in\mc{C}(n)$ with strictly-causal decoder is a tuple of functions $c=(f,\{g_i\}_{i=1}^n)$ defined by equations \eqref{eq:1CausalCodeSource1} and \eqref{eq:1CausalCodeSource2} .
\begin{eqnarray}
&f& : \mc{U}^n  \longrightarrow \mc{X}^n ,\label{eq:1CausalCodeSource1}\\
&g_i& : \mc{Y}^{i-1}  \longrightarrow \mc{V},\qquad i = 1,\ldots,n.\label{eq:1CausalCodeSource2}
\end{eqnarray}
The empirical distribution ${Q}^n \in \Delta(\mc{U}\times \mc{X}\times \mc{Y} \times\mc{V})$ of sequences $(u^n,x^n,y^n,v^n)\in \mc{U}^n\times \mc{X}^n \times \mc{Y}^n \times\mc{V}^n$ is defined by equation \eqref{eq:EmpiricalDistribution} where $\textsf{N}(u|u^n)$ denotes the number of occurrence of symbol $u \in \mc{U}$ in sequence $u^n \in \mc{U}^n$.
\begin{eqnarray}
{Q}^n(u,x,y,v) &=& \frac{\textsf{N}(u,x,y,v|u^n,x^n,y^n,v^n)}{n},\nonumber \\
&& \forall  (u,x,y,v) \in \mc{U}\times \mc{X}\times \mc{Y} \times\mc{V}.\label{eq:EmpiricalDistribution}
\end{eqnarray}
Fix a target probability distribution $\QQ \in \Delta(\mc{U} \times \mc{X} \times \mc{Y} \times \mc{V}  )$, the error probability of the code $c\in\mc{C}(n)$ is defined by equation \eqref{eq:ErrorProba}.
\begin{eqnarray}
\PP_{\textsf{e}}(c) = \PP_c\bigg(\Big|\Big|Q^n - \QQ \Big|\Big|_{\sf{v}}\geq \varepsilon\bigg),\label{eq:ErrorProba}
\end{eqnarray}
where $Q^n \in \Delta(\mc{U}\times \mc{X}\times \mc{Y} \times\mc{V})$ is the random variable of the empirical distribution of the sequences of symbols $(U^n,X^n,Y^n,V^n)\in \mc{U}^n\times \mc{X}^n \times \mc{Y}^n \times\mc{V}^n$ induced by the code $c \in \mc{C}(n)$, probabilities $\PP_{\sf{u}}$ and $\mc{T}_{\sf{y|x}}$.
\end{definition}

\begin{definition}
A probability distribution $\QQ \in  \Delta(\mc{U} \times \mc{X} \times \mc{Y} \times \mc{V}  )$ is achievable if for all $\varepsilon>0$, there exists a $\bar{n}\in \N$ such that for all $n \geq \bar{n}$ there exists a code $c\in\mc{C}(n)$ that satisfies:
\begin{eqnarray}
\PP_{\textsf{e}}(c)  = \PP_c\bigg(\Big|\Big|Q^n - \QQ \Big|\Big|_{\sf{v}}\geq \varepsilon\bigg)\leq \varepsilon.
\end{eqnarray}
\end{definition}
If the error probability $\PP_{\textsf{e}}(c)$ is small, the empirical frequency of symbols $(u,x,y,v) \in \mc{U}\times \mc{X}\times \mc{Y} \times\mc{V}$ is close to the probability distribution $\QQ(u,x,y,v)$, i.e. the sequence of symbols $(u^n,x^n,y^n,v^n)\in A_{\varepsilon}^{{\star}{n}}(\QQ)$ are jointly typical for distribution $\QQ(u,x,y,v)$, with large probability. In that case, encoder and decoder can implement a coding scheme such that the sequences of symbols are coordinated empirically.

\section{Strictly Causal Decoding}\label{sec:MainResult}

We consider a fixed probability distribution of the source $\PP_{u}$ and a fixed transition probability of the channel $\mc{T}_{y|x}$. For a strictly causal decoder, we characterize the set of probability distribution $\QQ(u,x,y,v) \in  \Delta(\mc{U} \times \mc{X} \times \mc{Y} \times \mc{V}  )$ that are achievable.

\begin{theorem}[Strictly Causal Decoding] $\qquad\qquad\qquad\qquad$\label{theo:1CwithChannel}
$1)$ The probability distribution $\QQ(u,x,y,v)$ is achievable if and only if it decomposes as follows:
\begin{eqnarray}
\begin{cases}
&\QQ(u) = \PP_{u}(u),\\
& \QQ(y|x) = \mc{T}(y | x ),\\
&Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  (U,V) , \\
&\PP_{u}(u)   \otimes \QQ(x,v | u) \otimes  \mc{T}(y | x ) \text{ is achievable}.
\end{cases}
\end{eqnarray}
$2)$ The probability distribution $\PP_{u}(u)   \otimes \QQ(x,v | u) \otimes  \mc{T}(y | x )$ is achievable if:
\begin{eqnarray}
\max_{\tilde{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I( U ; V  ,W  )  \bigg) > 0 ,  \label{eq:1CwithChannel1}
\end{eqnarray}
$ 3)$ The probability distribution $\PP_{u}(u)   \otimes \QQ(x ,v | u) \otimes  \mc{T}(y | x )$ is not achievable if:
\begin{eqnarray}
\max_{\tilde{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) < 0  ,  \label{eq:1CwithChannel2}
\end{eqnarray}
where $\Q$ is the set of distributions $\tilde{\QQ}   \in  \Delta(\mc{U}   \times \mc{W} \times \mc{X} \times \mc{Y} \times \mc{V}  )$ with auxiliary random variable $W$, that satisfy:
\begin{eqnarray*}
\begin{cases}
\sum_{w\in \mc{W}} \tilde{\QQ}(u,x,w,y,v) =  \PP_{u}(u)   \otimes \QQ(x ,v | u) \otimes  \mc{T}(y | x ), \\
Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  (U,V,W ).
\end{cases}
\end{eqnarray*}
The auxiliary random variable $W$ lies in a set $\mc{W}$ with cardinality bound $ |\mc{W}| \leq  |\mc{U}|  \cdot  |\mc{X}| \cdot |\mc{V}| +1$. Denote by $\mc{A}$ the set of transition probabilities $\QQ(x,v | u)$ that are achievable:
\begin{small}
\begin{eqnarray}
\mc{A} &=& \bigg\{\QQ(x,v | u) , \text{ s.t. } \max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) > 0 \bigg\}.\nonumber\\ &&
\end{eqnarray}
\end{small}
\end{theorem}

Proof of Theorem \ref{theo:1CwithChannel} is stated in Appendices \ref{sec:ProofDecomposition}, \ref{sec:ProofAchievability}, \ref{sec:ProofConverse} and \ref{sec:CardinalityBound}. In the following, we refer to equation \eqref{eq:1CwithChannel1} as information constraint.

\begin{remark}[Decomposition Probability]
The probability distribution with auxiliary random variable $W$ decomposes as follows:
\begin{small}
\begin{eqnarray*}
\tilde{\QQ}(u,x,w,y,v)  = \PP_{u}(u)   \otimes  {\QQ}(x,v | u) \otimes  \tilde{\QQ}(w | u,x,v) \otimes  \mc{T}(y | x )  .
\end{eqnarray*}
\end{small}
Hence, the maximum in equation \eqref{eq:1CwithChannel1} can be also taken over the transition probability $\tilde{\QQ}(w | u,x,v)$.
\end{remark}

In the coding scheme proposed by Shannon  \cite{shannon-bell-1948}, for the joint source-channel problem, the channel inputs $X^n$ are not jointly typical with the source sequences $(U^n,V^n)$. In this approach, there is a tension between transmitting information and generating coordinated symbols. Auxiliary random variable $W$ characterizes this tension and correlate efficiently the channel inputs $X$ with the sequences $(U,V)$. The notion of separation stated in \cite{shannon-bell-1948} does not hold anymore since the random variables of the source are coordinated with the random variables of the channel.

\begin{remark}[Markov Chain]
The strictly causal decoding induces a Markov chain $Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  V$. Since $V_i = g_i(Y^{i-1})$, the output $V_i$ of the decoder depends on the channel output $Y_i$ only through $X_i$ .
\end{remark}

\begin{remark}[Trivial Coding Scheme]
Probability distribution $\PP_{u}(u)   \otimes \QQ(x| u) \otimes  \mc{T}(y | x ) \otimes \QQ(v)$ is achievable using a trivial coding scheme. Encoder observes $U^n$ and chooses a sequence $X^n$ with i.i.d. transition probability $\QQ^{\otimes n}(x| u)$ and decoder chooses a sequence $V^n$ with i.i.d.  probability distribution $\QQ^{\otimes n}(v)$.
In that case, no auxiliary random variable $W$ is needed for the coding process and the corresponding information constraint is null:
\begin{eqnarray}
 I( W;Y  |V )  -   I(  U ; V  ,W  )  =0 .  \label{eq:1CwithChannel3}
\end{eqnarray}
As stated in Remark 3.5, pp. 43 in \cite{ElGammalKim(book)11}, some probability distributions are achievable even if the information constraint \eqref{eq:1CwithChannel3} is null.
\begin{eqnarray}
\QQ^1&=& \PP_{u}(u)   \otimes \QQ(x| u) \otimes  \mc{T}(y | x ) \otimes \QQ(v),\\
\QQ^2&=& \PP_{u}(u)   \otimes \QQ(x| u) \otimes  \mc{T}(y | x ) \otimes \QQ(v|u,x).
\end{eqnarray}
probability distribution $\QQ^1$ is achievable using a trivial coding scheme and probability distribution $\QQ^2$ is achievable using a coding scheme with an information constraint stated in Theorem \ref{theo:1CwithChannel}. The goal of the coding scheme is to induce correlations between random variables $V$ and $(U,X)$.
\end{remark}

\section{Comparison with previous results}\label{sec:PreviousWork}

In this section, we compare the result of Theorem \ref{theo:1CwithChannel} with the previous results stated in \cite{shannon-bell-1948}, \cite{GossnerHernandezNeyman06}, \cite{Cuff(ImplicitCoordination)10}, \cite{SamsonBenjaminISIT13}. In the case of lossless transmission investigated by Shannon in \cite{shannon-bell-1948}, the information source is perfectly recovered by the decoder $V = U$. The corresponding empirical distribution is $\QQ(U,V) = \PP_{\sf{u}} (U)\otimes \UN _{\{V = U\}}$. In that case, the random variables of the channel $(X,Y)$ are not necessarily correlated with the random variables of the source $(U,V)$. This provides more degrees of freedom in order to transmit the source symbols $U$ to the decoder.

\begin{corollary}\label{coro:Shannon}
Consider that the random variables of the channel $ (X  ,Y )$ are independent of the random variables of the source $ (U  ,V )$. Theorem \ref{theo:1CwithChannel} reduces to the following information constraint:
\begin{eqnarray}
&\max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) & > 0 \\
\Longleftrightarrow&   I(X  ;Y  )   -  I(U ;V )  &>0.
\end{eqnarray}
The optimal auxiliary random variable $W =X $ should be equal to the channel inputs.
\end{corollary}

\begin{proof}

Since the random variables of the channel $ (X  ,Y )$ are independent of the random variables of the source $ (U  ,V )$, we have:
\begin{eqnarray}
&&   \max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) \\
&=&     \max_{{\QQ}\in \Q} \bigg( I(V  ,W;Y )  -   I(  U ; V  ,W  )  \bigg)  .
\end{eqnarray}
Let us compare the above expression with the one stated in Corollary \ref{coro:Shannon} inspired by Shannon's results \cite{shannon-bell-1948}.
\begin{eqnarray}
&&  I(X  ;Y  )  - I(U ;V ) -  \big(  I(V  ,W;Y )  -  I(  U ; V  ,W  ) \big) \nonumber \\
&=&  I(X  ;Y  )   -   I(V  ,W;Y )  +  I(  U ; W   |V ) \big)  \\
&=&  I(V  ,W, X  ;Y  )   -   I(V  ,W;Y )  +  I(  U ; W   |V ) \\
&=&  I(X  ;Y |V  ,W  )   +  I(  U ; W  |V )  \geq 0.
\end{eqnarray}
The second equality is due to the Markov chain $Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  (W ,U,V)$. Then, for every auxiliary random variable $W$, we have the following inequality:
\begin{eqnarray}
I(X  ;Y  )  - I(U ;V )  \geq    I( W;Y  |V ) -  I(  U ; V  ,W  ) .
\end{eqnarray}
In particular if we choose auxiliary random variable $W =X $ independent of $(U ,V )$, we have equality:
\begin{eqnarray}
 I( W;Y  |V )  -  I(  U ; V  ,W  )
 &=&  I( X;Y  |V )  -  I(  U ; V  ,X  ) \nonumber \\
  &=&   I( X;Y   )  -  I(  U ; V    ).
\end{eqnarray}
Hence, the optimal auxiliary random variable $W =X $ should be equal to the channel inputs and we have the following equality:
\begin{eqnarray}
\max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg)=  I(X  ;Y  )  - I(U ;V ).

\end{eqnarray}

This concludes the proof of Corollary \ref{coro:Shannon}.
\end{proof}

\begin{remark}
If the random variables of the channel $(X,Y)$ are independent of the random variables of the source $(U,V)$, the strictly causal decoding provides the same information constraint as the causal or non-causal decoding. This is not true anymore when $(X,Y)$ are correlated with $(U,V)$.
\end{remark}

\begin{corollary}\label{coro:IndepRV}
Suppose that the transition probability $\QQ_{xv|u} \in \mc{A}$ is achievable. Hence the product of marginal probability distributions $\QQ_{x} \otimes \QQ_{v|u}  \in \mc{A}$ is also achievable.
\end{corollary}

\begin{proof}

From Corollary \ref{coro:Shannon}, the information constraint that correspond to the product of marginal probability distributions $\QQ_{x} \otimes \QQ_{v|u} $ is always greater than  the information constraint that correspond to probability distribution $\QQ_{xv|u} \in \mc{A}$:
\begin{small}
\begin{eqnarray}
 I(X  ;Y  )  - I(U ;V ) > \max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) >0.
\end{eqnarray}
\end{small}
The above inequality is detailed in the proof of Corollary \ref{coro:Shannon} and this concludes the proof of Corollary \ref{coro:IndepRV}.
\end{proof}

In \cite{GossnerHernandezNeyman06}, \cite{Cuff(ImplicitCoordination)10} and \cite{SamsonBenjaminISIT13}, the random variables of the channel $(X,Y)$ are correlated with the random variables of the source $(U,V)$. Corollaries \ref{coro:PerfectChannel} and \ref{coro:PastSource} prove our result reduces to previous results when considering the perfect  channel $Y  =X $ \cite{GossnerHernandezNeyman06}, \cite{Cuff(ImplicitCoordination)10} and the channel with strictly-causal feedback $U^{i-1}$ from the source \cite{SamsonBenjaminISIT13}. In both cases, the optimal auxiliary random variable $W =X $ is equal to the channel inputs.

\begin{corollary}\label{coro:PerfectChannel}
Consider a perfect  channel $Y  =X $. Theorem \ref{theo:1CwithChannel} reduces to the result stated in \cite{GossnerHernandezNeyman06} and \cite{Cuff(ImplicitCoordination)10}:
\begin{eqnarray}
&\max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) & > 0 \\
\Longleftrightarrow&H(X |V)   - I(U ;X,V )   &>0.
\end{eqnarray}
\end{corollary}

\begin{corollary}\label{coro:PastSource}
Consider at instant $i\in\{1, \ldots, n\}$, the decoder observes the channel outputs $Y^{i-1}$ and the past symbols $U^{i-1}$ of the information source. Theorem \ref{theo:1CwithChannel} reduces to the result stated in \cite{SamsonBenjaminISIT13}:
\begin{eqnarray}
&\max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) & > 0 \\
\Longleftrightarrow& I(X  ;Y  |   U  ,V )   - I(U ;X )  &>0.
\end{eqnarray}

\end{corollary}

Proofs of Corollaries \ref{coro:PerfectChannel} and \ref{coro:PastSource} are stated in App. \ref{sec:ProofCoro}.

\section{Trade-Off between Source Distortion and Channel Cost}\label{sec:DistortionCost}

In this section, we relates the result stated in Theorem \ref{theo:1CwithChannel} to the trade-off between source distortion (see pp. 57 in \cite{ElGammalKim(book)11}) and channel cost (see pp. 47 in \cite{ElGammalKim(book)11}). We characterize the pairs of achievable Distortion-Cost $(\textsf{D}^{\star},\textsf{C}^{\star})$ in terms of transition probability $\QQ(x,v | u)\in {\mc{A}}$ that are achievable.
\begin{definition}
A distortion function evaluates the distortion between the source symbol $u \in \mc{U}$ and the output of the decoder $v \in \mc{V}$:
\begin{eqnarray}
d : \mc{U} \times  \mc{V} \mapsto \R.
\end{eqnarray}
A channel cost function evaluates the cost of the input symbol $x \in \mc{X}$ of the channel:
\begin{eqnarray}
c : \mc{X} \mapsto \R.
\end{eqnarray}
\end{definition}

\begin{definition}
The pair of Distortion-Cost $(\textsf{D}^{\star},\textsf{C}^{\star})$ is achievable if for all $ \varepsilon >0$,  there exists $\bar{n}$ such that for all $n\geq\bar{n}$, there exists a code $c\in \mc{C}(n)$ such that:
\begin{eqnarray}
\E\bigg[ \frac{1}{n} \sum_{i=1}^n d(U_i ,V_i ) \bigg] &\leq& \textsf{D}^{\star} + \varepsilon ,\\
\E\bigg[ \frac{1}{n} \sum_{i=1}^n c(X_i ) \bigg] &\leq& \textsf{C}^{\star}+ \varepsilon.
\end{eqnarray}
\end{definition}
Since $\mc{A} $ is a subset of $\R^K$ with $K = |\mc{U}   \times  \mc{X} \times \mc{Y} \times \mc{V}  |$, the closure $\bar{\mc{A}}$ of the set $\mc{A}$ is defined by:
\begin{small}
\begin{eqnarray}
\bar{\mc{A}}= \bigg\{\QQ_{\sf{xv|u}} , \text{ s.t. } \max_{{\QQ}_{\sf{w|uxv}}} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) \geq 0 \bigg\}. \label{eq:closureA}
\end{eqnarray}
\end{small}

\begin{theorem}[Trade-Off Distrotion Cost]\label{theo:DistortionCost}
The three following assertions are equivalent:
\begin{itemize}
\item[$\bullet$] The pair of distortion-cost $(\textsf{D}^{\star},\textsf{C}^{\star})$ is achievable.\\
\item[$\bullet$] The pair of distortion-cost $(\textsf{D}^{\star},\textsf{C}^{\star})$ satisfies:
\begin{eqnarray}
\max_{\QQ_{\sf{x}}, \atop \E_{\sf{x}}(c)\leq \textsf{C}^{\star}} I( X;Y )  -  \min_{\QQ_{\sf{v|u}}, \atop \E_{\sf{uv}}(d)\leq \textsf{D}^{\star}} I(  U ; V   )\geq 0.\label{eq:CostDistortion}
\end{eqnarray}
\item[$\bullet$] There exists a probability distribution $ \QQ\in \bar{\mc{A}}$ such that:
\begin{eqnarray}
\E_{\QQ}\Big[d(U,V)\Big] &\leq \textsf{D}^{\star},\\
\E_{\QQ}\Big[c(X)\Big] &\leq \textsf{C}^{\star}.
\end{eqnarray}
\end{itemize}
\end{theorem}

\begin{remark}
Suppose that the pair of distortion-cost $(\textsf{D}^{\star},\textsf{C}^{\star})$ leads to an equality in the equation \eqref{eq:CostDistortion}:
\begin{eqnarray}
\max_{\QQ_{\sf{x}}, \atop \E_{\sf{x}}(c)\leq \textsf{C}^{\star}} I( X;Y )  =  \min_{\QQ_{\sf{v|u}}, \atop \E_{\sf{uv}}(d)\leq \textsf{D}^{\star}} I(  U ; V   ),\label{eq:Equality}
\end{eqnarray}
Denote by $\QQ_{\sf{x}}^{\star}$ and $\QQ_{\sf{v|u}}^{\star}$ the distribution that achieves the maximum and the minimum. There exists a sequence of distribution $(\QQ_{\sf{x}}^k)_{k\geq1}$ (resp. $(\QQ_{\sf{v|u}}^k)_{k\geq1}$) that converges to $\QQ_{\sf{x}}^{\star}$ (resp. to $\QQ_{\sf{v|u}}^{\star}$) such that for all $k\geq 1$,  joint probability distribution $\QQ_{\sf{x}}^k \otimes \QQ_{\sf{v|u}}^k \in \mc{A}$ achievable:
 \begin{eqnarray}
 I_{\QQ_{\sf{xy}}^k}( X;Y )  >   I_{\QQ_{\sf{uv}}^k}(  U ; V   ).
\end{eqnarray}
Hence the pairs of distortion-cost $(\textsf{D}^k,\textsf{C}^{^k})$ that correspond to $\QQ_{\sf{x}}^k \otimes \QQ_{\sf{v|u}}^k \in \mc{A}$ are achievable and converges to $(\textsf{D}^{\star},\textsf{C}^{\star})$. This proves that the pair of distortion-cost $(\textsf{D}^{\star},\textsf{C}^{\star})$ is achievable even if the corresponding probability distribution $\QQ_{\sf{x}}^{\star} \otimes\QQ_{\sf{v|u}}^{\star} \notin \mc{A}$ is not achievable.
\end{remark}

\begin{proof}

The separation result, page 66 in \cite{ElGammalKim(book)11}, states that the first and second assertions are equivalent. We prove that the equivalence between the second  and the third assertion.
\begin{small}
\begin{eqnarray}
&&\max_{\QQ_{\sf{x}}, \atop \E_{\sf{x}}(c)\leq \textsf{C}^{\star}} I( X;Y )  -  \min_{\QQ_{\sf{v|u}}, \atop \E_{\sf{uv}}(d)\leq \textsf{D}^{\star}} I(  U ; V   )\\
&=&\max_{\QQ_{\sf{x}}, \QQ_{\sf{v|u}} \atop \E_{\sf{x}}(c)\leq \textsf{C}^{\star},  \E_{\sf{uv}}(d)\leq \textsf{D}^{\star}}  \bigg( I( X;Y )  -  I(  U ; V  ) \bigg)\\
&=&\max_{\QQ_{\sf{x}}, \QQ_{\sf{v|u}} \atop \E_{\sf{x}}(c)\leq \textsf{C}^{\star},  \E_{\sf{uv}}(d)\leq \textsf{D}^{\star}}  \Bigg( \max_{{\QQ}_{w|uvx} } \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) \Bigg).\nonumber\\&&
\end{eqnarray}
\end{small}
The third equality comes from Corollary \ref{coro:Shannon} since  the random variables of the channel $ (X  ,Y )$ are independent of the random variables of the source $ (U  ,V )$. We have the following equivalences:
\begin{footnotesize}
\begin{eqnarray*}
&&\max_{\QQ_{\sf{x}}, \atop \E_{\sf{x}}(c)\leq \textsf{C}^{\star}} I( X;Y )  -  \min_{\QQ_{\sf{v|u}}, \atop \E_{\sf{uv}}(d)\leq \textsf{D}^{\star}} I(  U ; V   )\geq 0 \\
&\Longleftrightarrow&\max_{\QQ_{\sf{x}}, \QQ_{\sf{v|u}} \atop \E_{\sf{x}}(c)\leq \textsf{C}^{\star},  \E_{\sf{uv}}(d)\leq \textsf{D}^{\star}}  \Bigg( \max_{{\QQ}_{w|uvx} } \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) \Bigg)\geq 0 \\
&\Longleftrightarrow& \exists \; \QQ_{\sf{x}}\otimes \QQ_{\sf{v|u}} \in \bar{A} \text{ s.t. } \E_{\sf{x}}(c)\leq \textsf{C}^{\star} \text{ and }  \E_{\sf{uv}}(d)\leq \textsf{D}^{\star}.
\end{eqnarray*}
\end{footnotesize}
In words, there exists a probability distribution $ \QQ\in \bar{\mc{A}}$ such that $\E_{\QQ}\big[d(U,V)\big]  \leq \textsf{D}^{\star}$ and $\E_{\QQ}\big[c(X)\big] \leq \textsf{C}^{\star}$.
This concludes the proof of Theorem \ref{theo:DistortionCost}.
\end{proof}

\section{Example with Binary Source and Binary Symmetric Channel}\label{sec:ExampleBSBSC}

We consider a binary information source and a binary symmetric channel with set of two symbols $\mc{U} = \mc{X} = \mc{Y} = \mc{V} = \{0,1\}$ as represented by Fig. \ref{fig:JointSourceChannelProblem2x2b}. The information source depends on parameter $p\in [0,1]$ and the channel depends on parameter $\varepsilon \in [0,1]$.
  \begin{figure}[ht]
\begin{center}
\psset{xunit=0.6cm,yunit=0.6cm}
\begin{pspicture}(-1,-1)(15,3.5)
\rput(0,1.5){$p$}
\rput(0,0.5){$1-p$}
\rput(1,2.5){$U$}
\rput(1,1.5){$0$}
\rput(1,0.5){$1$}
\psframe(2,0)(3,2)
\rput(2.5,1){$\C$}
\rput(4,2.5){$X$}
\rput(4,1.5){$0$}
\rput(4,0.5){$1$}
\psline{->}(5,1.5)(9,1.5)
\psline{->}(5,0.5)(9,0.5)
\psline[linewidth=0.5pt, linestyle = dashed]{->}(5,1.5)(9,0.5)
\psline[linewidth=0.5pt, linestyle = dashed]{->}(5,0.5)(9,1.5)
\rput(7,1.8){$1 - \varepsilon$}
\rput(7,0.1){$1 - \varepsilon$}
\rput(8.5,1){$\varepsilon$}
\rput(10,2.5){$Y$}
\rput(10,1.5){$0$}
\rput(10,0.5){$1$}
\psframe(11,0)(12,2)
\rput(11.5,1){$\D$}
\rput(13,2.5){$V$}
\rput(13,1.5){$0$}
\rput(13,0.5){$1$}
\end{pspicture}
\caption{Binary information source and binary symmetric channel with parameters $p\in [0,1]$ and $\varepsilon \in [0,1]$}\label{fig:JointSourceChannelProblem2x2b}
\end{center}
\end{figure}
Consider the distortion function and cost function given by equations \eqref{eq:ExDistortion} and \eqref{eq:ExCost}.
\begin{eqnarray}
d(u,v) &=& \UN_{\{u=v\}},\label{eq:ExDistortion}\\
c(x) &=& \UN_{\{x=1\}}.\label{eq:ExCost}
\end{eqnarray}
The minimal distortion is achieved when the outputs symbols of the decoder $V = U$ are equal to the source symbols $U$. The minimal cost is achieved when only the symbol $X = 0$ is implemented for the transmission, hence no transmission occurs.
We consider the following probability distribution $\QQ_{\sf{x}}(X =0 ) = \alpha$, $\QQ_{\sf{x}}(X =1 ) = 1 - \alpha$,
and the transition probability$\QQ_{\sf{v|u}}$ represented by Fig. \ref{fig:MarginalProbability} with $\beta \in [0,1]$.
 \begin{figure}[ht]
\begin{center}
\psset{xunit=0.8cm,yunit=0.8cm}
\begin{pspicture}(3,-0.5)(10,3)

\rput(4,2.5){$U$}
\rput(4,1.5){$0$}
\rput(4,0.5){$1$}
\psline{->}(5,1.5)(9,1.5)
\psline{->}(5,0.5)(9,0.5)
\psline[linewidth=0.5pt, linestyle = dashed]{->}(5,1.5)(9,0.5)
\psline[linewidth=0.5pt, linestyle = dashed]{->}(5,0.5)(9,1.5)
\rput(7,1.8){$1 - \beta$}
\rput(7,0.1){$1 - \beta$}
\rput(8.5,1){$\beta$}
\rput(10,2.5){$V$}
\rput(10,1.5){$0$}
\rput(10,0.5){$1$}
\end{pspicture}
\caption{Transition probability $\QQ_{\sf{v|u}}$ depending on parameter $\beta\in [0,1]$.}\label{fig:MarginalProbability}
\end{center}
\end{figure}
Consider the communication problem represented by Fig. \ref{fig:JointSourceChannelProblem2x2b}. Mutual information writes:
\begin{eqnarray*}
I( X;Y  )   &=& H( Y) - H( Y | X)\\
&=& H_b\Big( \alpha\cdot \varepsilon + (1- \alpha) \cdot (1- \varepsilon) \Big) - H_b\Big(\varepsilon\Big),\\

I(  U;V  )   &=& H( V) - H( V |  U)\\
&=& H_b\Big( \beta\cdot p + (1- \beta) \cdot (1- p) \Big) - H_b\Big(\beta\Big).
\end{eqnarray*}
The information constraint writes:
\begin{eqnarray*}
&&I( X;Y  )  -  I(  U;V  ) \\
&=& H_b\Big( \alpha\cdot \varepsilon + (1- \alpha) \cdot (1- \varepsilon) \Big)+ H_b\Big(\beta\Big)  \\
&-& H_b\Big(\varepsilon\Big) - H_b\Big( \beta\cdot p + (1- \beta) \cdot (1- p) \Big) .
\end{eqnarray*}
The distortion and cost functions are defined by equation \eqref{eq:ExDistortion} and \eqref{eq:ExCost}:
\begin{eqnarray}
\E_{\QQ^{\star}}\Big[d(U,V)\Big]  &=&\sum_{u,v} \PP_u(u) \cdot \QQ_{v|u}(v|u) \cdot  \UN_{\{u=v\}} \\
&=& \PP_u(u = 0) \cdot \QQ_{v|u}(v =1|u=0)  \\
&+& \PP_u(u = 1) \cdot \QQ_{v|u}(v =0|u=1) ,\\
&=& p \cdot \beta  + (1 - p) \cdot \beta = \beta ,\\
\E_{\QQ^{\star}}\Big[c(X)\Big] &=& \sum_{x} \QQ_{x}(x)\cdot \UN_{\{x=1\}} = \QQ_{x}(x=1) = \alpha.\nonumber\\&&
\end{eqnarray}
\begin{figure}[ht!]
\centering
\includegraphics[width=0.4\textwidth]{TradeOffDistortionCost2014_06_16.eps}
\caption{Region of achievable Distortion-Cost $(\textsf{D},\textsf{C})$ depending on source and channel parameters $( \varepsilon,p) \in \{(0.05,0.5) ;  (0.25,0.25); (0.25,0.5)\}$.}
\label{fig:TradeOffDistortionCost2014_03_11}
 \end{figure}
Fig. \ref{fig:TradeOffDistortionCost2014_03_11} represents three regions of achievable pairs of distortion-cost corresponding to the source and channel parameters $( \varepsilon,p) \in \{(0.05,0.5) ;  (0.25,0.25); (0.25,0.5)\}$. The smaller parameters correspond to the larger region. Fig.  \ref{fig:TradeOffDistortionCost2014_03_11}  illustrates the trade-off between source distortion and channel cost.
\begin{itemize}
\item[$\bullet$] The minimal cost $\textsf{C}^{\star}=0$ is achieved with a distortion $\textsf{D}^{\star}=0.5$. This correspond to the situation where  no transmission occurs. The channel input is always $X=0$ and the output of the decoder $V$ is drawn with uniform and i.i.d. probability distribution $\QQ_v = (0.5,0.5)$. Remark that no distribution correspond to the pair of distortion-cost $\Big(\E_{\QQ^{\star}}\big[d(U,V)\big] , \E_{\QQ^{\star}}\big[c(X)\big] \Big) = (1,0)$, since in that case the output of the decoder $V$ should be  correlated with the source symbols $V \neq U$ whereas transmission is impossible.
\item[$\bullet$] The minimal distortion $\textsf{D}^{\star} \in\{0.05,0.216,0.25\}$ is achieved with a cost $\textsf{C}^{\star}=0.5$. This correspond to the channel capacity where the channel inputs $X$ are distributed uniformly $\QQ_x = (0.5,0.5)$. Remark that no distribution correspond to the pair of distortion-cost $\Big(\E_{\QQ^{\star}}\big[d(U,V)\big] , \E_{\QQ^{\star}}\big[c(X)\big] \Big)  \in\{ (0.05,1),  (0.216,1),  (0.25,1) \}$,  since in that case the channel input is always $X=1$, no transmission is possible and the random variable $V$ cannot be correlated with $U$.
\end{itemize}

\section{Convex Optimisation Problem}\label{sec:ConvexOptimization}

In this section, we prove that the set of achievable empirical distribution stated in Theorem \ref{theo:1CwithChannel} is convex. This result has strong consequences for the maximization problem of a given utility function over the set of achievable empirical distributions. We consider a utility function defined as follows over the symbols of the source and the channel:
\begin{eqnarray}
\upsilon : \mc{U} \times \mc{X} \times \mc{Y} \times \mc{V}   \mapsto \R.
\end{eqnarray}
The utility function captures the objective of the coding process. For example, it can represent a distortion measure, a channel cost or the objective function of players of a game as in \cite{GossnerHernandezNeyman06}. We consider the transmitters choose appropriately the sequences of symbols in order to maximize the utility function.
\begin{example}
Consider the utility function $\upsilon (u,x,y,v) = \UN_{\{v = u\}}$. Its maximum is achieved when the outputs of the decoder $V$ are equal to the source symbols $U$. The choice of the symbol of the channel $(X,Y)$ has no influence on the utility function. The joint source-channel results stated in \cite{shannon-bell-1948} concludes that the utility $\upsilon (u,x,y,v) = 1$ can be achieved if $\max_{\QQ_{\sf{x}}}I( X;Y )  - H(U ) >0$ and utility $\upsilon (u,x,y,v) = 1$ cannot be achieved  if $\max_{\QQ_{\sf{x}}}I( X;Y )  - H(U ) <0$.
\end{example}

This approach is based on the expected utility function $\E_{\sf{uxyv}} \big[ \upsilon(U ,X ,Y ,V )\big]$ and the set of achievable probability distribution $\QQ_{\sf{xv|u}} \in \mc{A}$ characterized by Theorem \ref{theo:1CwithChannel}. Probability distribution $\QQ_{\sf{xv|u}}$ induces a joint probability distribution $\QQ_{\sf{uxyv}}  = \PP_{u}  \otimes \QQ_{\sf{xv|u}} \otimes  \mc{T}_{\sf{y|x}}$ that is used to compute the expected utility $\E_{\sf{uxyv}} \big[ \upsilon (U ,X ,Y ,V ) \big]$. For every utility function, we determine the optimal coding scheme based on this optimization problem:
\begin{eqnarray}
\sup_{\QQ_{\sf{xv|u}} \in \mc{A}}\E_{\sf{uxyv}} \bigg[ \upsilon(U ,X ,Y ,V )\bigg],\label{eq:OptimisationProblem1}
\end{eqnarray}
where $\mc{A}$ is the set of achievable probability distribution $\QQ_{\sf{xv|u}}$:
\begin{eqnarray*}
\mc{A} = \bigg\{  \QQ_{\sf{xv|u}} ,\text{ s.t. }\max_{{\QQ}_{\sf{w|uxv}}} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) > 0\bigg\}.
\end{eqnarray*}
Recall that we denote by $\bar{\mc{A}}$ the closure of the set of transition probability $\QQ_{\sf{xv|u}}$ that are achievable:

\begin{eqnarray*}
\bar{\mc{A}}  = \bigg\{  \QQ_{\sf{xv|u}} ,\text{ s.t. }\max_{{\QQ}_{\sf{w|uxv}}} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) \geq 0\bigg\}.
\end{eqnarray*}
The supremum over the open set $\mc{A}$ is the supremum over the closure $\bar{\mc{A}}$. Since $\bar{\mc{A}}$ is a closed and bounded subset of $\R^K$, it is a compact set. Function $\E_{\sf{uxyv}} \big[ \upsilon(U ,X ,Y ,V )\big] $ is continuous over a compact set $\bar{\mc{A}}$. The supremum over $\bar{\mc{A}}$ is a maximum:
\begin{eqnarray}
&&\sup_{\QQ_{\sf{xv|u}} \in \mc{A}}\E_{\sf{uxyv}} \bigg[ \upsilon(U ,X ,Y ,V )\bigg] \\
&=& \sup_{\QQ_{\sf{xv|u}} \in \bar{\mc{A}}}\E_{\sf{uxyv}} \bigg[ \upsilon(U ,X ,Y ,V )\bigg]\\
&=& \max_{\QQ_{\sf{xv|u}}\in \bar{\mc{A}} }\E_{\sf{uxyv}} \bigg[ \upsilon(U ,X ,Y ,V )\bigg].\label{eq:SupOptimisationProblem2}
\end{eqnarray}
The supremum over the set $\mc{A}$ is equal to a maximum over the set $\bar{\mc{A}}$.

\begin{theorem}\label{theo:ConvexProblem}
The optimization problem stated in equation \eqref{eq:OptimisationProblem} is a convex optimization problem.
\begin{eqnarray}
\max_{\QQ_{\sf{xv|u}} \in\bar{\mc{A}}}\E_{\sf{uxyv}} \bigg[ \upsilon(U ,X ,Y ,V )\bigg].\label{eq:OptimisationProblem}
\end{eqnarray}
\end{theorem}
The proof of Theorem \ref{theo:ConvexProblem} is stated in App. \ref{sec:ProofTheoConvex}.

\begin{remark}
Since the criteria $\E_{\sf{uxyv}} \big[ \upsilon(U ,X ,Y ,V )\big]$ is linear in $\QQ_{\sf{xv|u}}$ and the set $\bar{\mc{A}}$ is convex, the optimal solution of the optimization problem \eqref{eq:OptimisationProblem} lies on the boundary of the set $\bar{\mc{A}}$. Denote by $\texttt{bd}(\bar{\mc{A}}) $  the subset of the boundary of $\bar{\mc{A}}$ where the information constraint is null:
\begin{small}
\begin{eqnarray*}
\texttt{bd}(\bar{\mc{A}}) = \bigg\{  \QQ_{\sf{xv|u}} ,\text{ s.t. }\max_{{\QQ}_{\sf{w|uxv}}} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) = 0\bigg\}.
\end{eqnarray*}
\end{small}
Probability distributions $\QQ_{\sf{xv|u}} $ that satisfies equation $\max_{{\QQ}_{\sf{w|uxv}}} \big( I( W;Y  |V )  -   I(  U ; V  ,W  )  \big) = 0$ are possible solutions for the optimisation problem:
\begin{eqnarray}
\max_{\QQ_{\sf{xv|u}} \in\bar{\mc{A}}}\E_{\sf{uxyv}} \bigg[ \upsilon(U ,X ,Y ,V )\bigg].
\end{eqnarray}
\end{remark}

Based on this remark, we propose a simple algorithm in order to find the optimal solution of the optimization problem \eqref{eq:OptimisationProblem}.
\begin{algorithm}
\begin{itemize}
\item[1)] Remove the information constraint. Find the transition probability  $\QQ^{\star}_{\sf{xv|u}}$ that achieves the maximum in optimization problem \eqref{eq:OptimisationProblemSans} with no-information constraint.
\begin{eqnarray}
\max_{\QQ_{\sf{xv|u}}}\E_{\sf{uxyv}} \bigg[ \upsilon(U ,X ,Y ,V )\bigg].\label{eq:OptimisationProblemSans}
\end{eqnarray}
\item[2)] Check whether the optimal transition probability  $\QQ^{\star}_{\sf{xv|u}} $ belong to the set of achievable transition probability $\QQ^{\star}_{xv|u}\in \bar{\mc{A}}$ or not, i.e. check whether the information constraint \eqref{eq:InfoConstraintTest} is positive or not.
\begin{eqnarray}
\max_{{\QQ}_{\sf{w|uxv}}}  \bigg( I_{\QQ^{\star}}( W ;Y  |V  )  -   I_{\QQ^{\star}}(  U ; V  ,W)   \bigg) \lessgtr 0.\label{eq:InfoConstraintTest}
\end{eqnarray}
\item[3)] If the information constraint \eqref{eq:InfoConstraintTest} is positive, then $\QQ^{\star}_{\sf{xv|u}}$ is the optimal solution.
\item[4)] If the information constraint \eqref{eq:InfoConstraintTest} is strictly negative, then the optimal solution lies on the subset of the boundary where the information constraint is null. Find the transition probability $\QQ^{\diamond}_{\sf{xv|u}} \in \texttt{bd}(\bar{\mc{A}}) $ of the optimization problem \eqref{eq:OptimisationProblemBis}  with equality constraint:
\begin{eqnarray}
\max_{\QQ_{\sf{xv|u}} \in  \texttt{bd}(\bar{\mc{A}})}\E_{\sf{uxyv}} \bigg[ \upsilon(U ,X ,Y ,V )\bigg]  \label{eq:OptimisationProblemBis}.
\end{eqnarray}
\end{itemize}
\end{algorithm}

\section{Example: Coordination with the Source}\label{sec:ExampleMatchingPennies}

We investigate the example of the binary information source and a binary symmetric channel, introduced in Sec. \ref{sec:ExampleBSBSC} and represented by Fig. \ref{fig:JointSourceChannelProblem2x2b}. Consider the utility function  defined by Fig. \ref{fig:MatchingPennies}. This utility is associated to a coordination game introduced in \cite{GossnerHernandezNeyman06} in which the encoder and the decoder try to coordinate their output symbols $X$ and $V$ with the information source $U$. The maximal utility is achieved when the encoder and the decoder implement the same symbol as the source symbol $X =V = U$, i.e. the sequences of symbols $X^n$ and $V^n$ are jointly typical with $U^n$ for probability distribution $\PP_{\sf{u}} \otimes \UN_{\{\sf{x} =\sf{v} = \sf{u}\}}$. \\
 \begin{figure}[ht]
\begin{center}
\psset{xunit=0.6cm,yunit=0.6cm}
\begin{pspicture}(-19,-1)(5,4.5)
\psframe(-10,0)(-6,3)
\psline(-10,1.5)(-6,1.5)
\psline(-8,0)(-8,3)
\rput(-9,2.25){$0$}
\rput(-7,2.25){$0$}
\rput(-9,0.75){$0$}
\rput(-7,0.75){$1$}

\rput(-11,2.25){$X=0$}
\rput(-11,0.75){$X=1$}
\rput(-17,2.25){$X=0$}
\rput(-17,0.75){$X=1$}
\rput(-9,3.3){$V=0$}
\rput(-7,3.3){$V=1$}
\rput(-15,3.3){$V=0$}
\rput(-13,3.3){$V=1$}
\rput(-14,-0.8){$U=0$}
\rput(-8,-0.8){$U=1$}
\psframe(-16,0)(-12,3)
\psline(-16,1.5)(-12,1.5)
\psline(-14,0)(-14,3)
\rput(-15,2.25){$1$}
\rput(-13,2.25){$0$}
\rput(-15,0.75){$0$}
\rput(-13,0.75){$0$}
 \end{pspicture}
 \caption{Utility function $\upsilon:\mc{U} \times \mc{X} \times \mc{V} \mapsto \R $. Coordination with the Source} \label{fig:MatchingPennies}
\end{center}
\end{figure}

\begin{itemize}
\item[$\bullet$] First trivial solution: Encoder implements the same symbol as the source symbol $X = U$. The solution is not optimal since the decoder has no information about the  information source.\\
\item[$\bullet$] Second trivial solution: Encoder transmit to the decoder the sequence of future source symbols in order the decoder can implement the same symbols in future slots $V = U$. This solution is not optimal since the encoder can not coordinate with the source. \\
\item[$\bullet$] Optimal solution is based on a coding scheme that implements a trade-off between transmission and coordination in order to maximize the utility function. Information constraint stated in equation \eqref{eq:1CwithChannel1} characterizes the set of achievable probability distribution. \\
\end{itemize}

We investigate the achievable probability distribution that maximizes the utility function in order to determine the optimal solution for this transmission/coordination trade-off. The information constraint stated in equation \eqref{eq:1CwithChannel1} of Theorem \ref{theo:1CwithChannel} depends on an auxiliary random variable $W$ that is difficult to characterize. In this example, we consider lower and upper bounds  on the information constraint. The lower bound is obtained by letting $W =X$ in the information constraint of Theorem \ref{theo:1CwithChannel} as stated in equation \eqref{eq:ICMatchingPenniesLow}.
\begin{footnotesize}
\begin{eqnarray}
\max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) \geq I( X;Y  |V )  -   I(  U ; V  ,X  )  >0. \label{eq:ICMatchingPenniesLow}
\end{eqnarray}
\end{footnotesize}
The upper bound comes from the main result stated in  \cite{SamsonBenjaminISIT13}, in which the decoder has an additional information. The information constraint is stated in equation \eqref{eq:ICMatchingPenniesUp}.
\begin{footnotesize}
\begin{eqnarray}
 I( X;Y  | U ,V )  -   I(  U ; V   )\geq  \max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg)  >0.\label{eq:ICMatchingPenniesUp}
\end{eqnarray}
\end{footnotesize}

 \begin{figure}[ht]
\begin{center}
\psset{xunit=0.6cm,yunit=0.6cm}
\begin{pspicture}(-19,-1)(5,4.5)
\psframe(-10,0)(-6,3)
\psline(-10,1.5)(-6,1.5)
\psline(-8,0)(-8,3)
\rput(-9,2.25){$\frac{1 - \gamma}{6}$}
\rput(-7,2.25){$\frac{1 - \gamma}{6}$}
\rput(-9,0.75){$\frac{1 - \gamma}{6}$}
\rput(-7,0.75){$\frac{\gamma}{2}$}

\rput(-11,2.25){$X=0$}
\rput(-11,0.75){$X=1$}
\rput(-17,2.25){$X=0$}
\rput(-17,0.75){$X=1$}
\rput(-9,3.3){$V=0$}
\rput(-7,3.3){$V=1$}
\rput(-15,3.3){$V=0$}
\rput(-13,3.3){$V=1$}
\rput(-14,-0.8){$U=0$}
\rput(-8,-0.8){$U=1$}
\psframe(-16,0)(-12,3)
\psline(-16,1.5)(-12,1.5)
\psline(-14,0)(-14,3)
\rput(-15,2.25){$\frac{\gamma}{2}$}
\rput(-13,2.25){$\frac{1 - \gamma}{6}$}
\rput(-15,0.75){$\frac{1 - \gamma}{6}$}
\rput(-13,0.75){$\frac{1 - \gamma}{6}$}
 \end{pspicture}
 \caption{Optimal probability distribution for the utility function "Coordination with the Information Source" presented in Fig. \ref{fig:MatchingPennies}. Utility is equal to parameter $\gamma\in [0,1]$.}\label{fig:OptimalProbaMatchingPennies}
\end{center}
\end{figure}
As stated in \cite{GossnerHernandezNeyman06}, the utility function presented in Fig. \ref{fig:MatchingPennies} is symmetric, hence the empirical distribution that maximizes the utility function is given by Fig. \ref{fig:OptimalProbaMatchingPennies} with probability parameter $\gamma\in [0,1]$. We suppose that the source parameter is $p=\frac{1}{2}$ and we determine the lower and upper bounds over the information constraint of Theorem \ref{theo:1CwithChannel}. We investigate the impact of this bounds on
 the utility function stated in Fig. \ref{fig:MatchingPennies}. We compare this results to the one stated in  \cite{GossnerHernandezNeyman06}  \cite{Cuff(ImplicitCoordination)10} and \cite{SamsonBenjaminISIT13}.

\begin{proposition}\label{prop:InformationConstraintMP}
The upper and lower bounds on equation \eqref{eq:1CwithChannel1} are given by equations \eqref{eq:LowerBound} and \eqref{eq:UpperBound}:
\begin{eqnarray}
&&I( X;Y  |V )  -   I(  U ; V  ,X  )  \nonumber\\
&=& H_b(\gamma) + (1-\gamma) \cdot \log_2(3) - 1 - H_b\bigg(\frac{2}{3} -  \frac{2\gamma}{3} \bigg)  \nonumber\\
&-& H_b(\varepsilon) + H_b\bigg(\frac{2}{3} - \frac{2\gamma}{3}  +  \varepsilon \cdot \frac{4\gamma - 1}{3}  \bigg).\label{eq:LowerBound}
\end{eqnarray}

\begin{eqnarray}
&&I( X;Y  |  U,V )  -   I(  U ; V   ) \nonumber \\
&=& H_b(\gamma) + (1-\gamma) \cdot \log_2(3) - 1 -  H_b(\varepsilon) \nonumber \\
&+&  \frac{2\gamma + 1}{3} \cdot \Bigg( H_b\bigg( (1 - \varepsilon ) \cdot \frac{3\gamma}{2\gamma + 1}  +  \varepsilon \cdot  \frac{1 - \gamma}{2\gamma + 1}  \bigg) \nonumber\\
&-&  H_b\bigg( \frac{3\gamma}{2\gamma + 1} \bigg) \Bigg) . \label{eq:UpperBound}
\end{eqnarray}
\end{proposition}

The proof of Proposition \ref{prop:InformationConstraintMP} follows entropy calculation.

\begin{remark}
Note that when $\varepsilon=0$, the information constraints \eqref{eq:LowerBound} and \eqref{eq:UpperBound} reduce to the one stated in \cite{GossnerHernandezNeyman06}  and  \cite{Cuff(ImplicitCoordination)10}:
\begin{eqnarray}
H( X   |V )  -   I(  U ; V  ,X  ) = H_b(\gamma) + (1-\gamma) \cdot \log_2(3) - 1 .
\end{eqnarray}
\end{remark}

 \begin{figure}[ht!]
\centering
\includegraphics[width=0.5\textwidth]{InformationConstraintPlot2014_03_21.eps}
\caption{Information constraint depending on the probability parameter $\gamma\in [0,1]$ for different values of the channel parameter $\varepsilon \in \{0,0.25,0.5\}$.}\label{fig:InformationConstraintPlot2014_03_04}
 \end{figure}

  \begin{figure}[ht!]
\centering
\includegraphics[width=0.5\textwidth]{InformationConstraintUtility2014_03_21.eps}
\caption{Optimal utility/probability parameter $\gamma\in [0,1]$ depending on the channel parameter $\varepsilon \in [0,0.5]$.}
\label{fig:InformationConstraintUtility2014_03_04}
 \end{figure}

Fig. \ref{fig:InformationConstraintPlot2014_03_04} and \ref{fig:InformationConstraintUtility2014_03_04} represent numerical simulations based on the lower bound and upper bound stated in equations \eqref{eq:LowerBound} and \eqref{eq:UpperBound}  for different values of the channel parameter $\varepsilon$ and probability parameter $\gamma$. The information constraint is concave in probability parameter $\gamma\in [0,1]$. The maximum of the information constraint is achieved by parameter $\gamma = 0.25$ that corresponds to the uniform probability distribution over  symbols $\mc{U}\times \mc{X}\times\mc{V}$. The maximum of the utility is achieved by parameter $\gamma^{\star}\in [0,1]$ that is a root of the information constraint.

\begin{itemize}
\item[$\bullet$] If the channel is perfect, i.e. $\varepsilon =0$, the optimal solution corresponds to the one presented in  \cite{GossnerHernandezNeyman06}  and \cite{SamsonBenjaminISIT13}. The optimal utility that can be achieved by the encoder and the decoder is more than 0.81 and the optimal probability distribution $\QQ^{\star}$ is given by parameter $\gamma^{\star} \simeq 0.81$ solution of the equation $H_b(\gamma) + (1-\gamma) \cdot \log_2(3)  =1$.
\item[$\bullet$] If the channel parameter is $\varepsilon =0.5$, then the channel outputs are statistically independent of the channel inputs and the optimal utility is 0.25. It correspond to the situation where the random variables  $X$ and $V$ are uniform and random variables $U$, $X$ and $V$  are mutually independent. This strategy does not requires any information transmission and 0.25 is the minimal utility that can be achieved.
\item[$\bullet$] If the channel parameter is $\varepsilon \in ]0,0.5[$, then Fig. \ref{fig:InformationConstraintUtility2014_03_04} provides lower and upper bounds on the optimal utility that can be achieved by the encoder and decoder. The optimal probability parameter $\gamma^{\star}$ is a root of the information constraint as in Fig. \ref{fig:InformationConstraintPlot2014_03_04}.  For example, if the channel parameter is $\varepsilon = 0.25$, the optimal utility belongs to the interval $\upsilon^{\star} \in [0.54,0.575]$. Even if the channel is noisy, the encoder, the decoder and the source are perfectly coordinated more than half of the time.
\end{itemize}

\section{Causal Decoding}\label{sec:CwithChannel}

In this section, we consider causal decoding instead of strictly-causal decoding for a fixed probability distribution of the source $\PP_{u}$ and a fixed transition probability of the channel $\mc{T}_{y|x}$.  At instant $i\in\{1,\ldots,n\}$, decoder $\D$ observes the sequence of past and current channel outputs $y^{i} = (y_1,\ldots,y_{i}) \in \mc{Y}^{i}$ and returns an output symbol $v_i \in \mc{V}_i$. We characterize the set of empirical distribution $\QQ \in \Delta(\mc{U} \times \mc{X} \times \mc{Y} \times \mc{V}  ) $ that are achievable, i.e. the encoder and decoder can implement sequences of symbols  $(U^n ,X^n,Y^n,V^n) \in A_{\varepsilon}^{{\star}{n}}(\QQ)$ that are jointly typical for distribution $\QQ(u,x,y,v)$, with large probability.

\begin{figure}[!ht]
\begin{center}
\psset{xunit=1cm,yunit=1cm}
\begin{pspicture}(0,-0.5)(7.5,1.5)
\pscircle(0,0.5){0.5}
\psframe(1.5,0)(2.5,1)
\pscircle(4,0.5){0.5}
\psframe(5.5,0)(6.5,1)
\psline[linewidth=1pt]{->}(0.5,0.5)(1.5,0.5)
\psline[linewidth=1pt]{->}(2.5,0.5)(3.5,0.5)
\psline[linewidth=1pt]{->}(4.5,0.5)(5.5,0.5)
\psline[linewidth=1pt]{->}(6.5,0.5)(7.5,0.5)

\rput[u](1,0.8){$U^n$}

\rput[u](3,0.8){$X^{i}$}
\rput[u](5,0.8){$Y^{i}$}
\rput[u](7,0.8){${V}_i$}
\rput(0,0.5){$\PP_{\sf{u}}$}
\rput(2,0.5){$\C$}
\rput(4,0.5){$\mc{T}_{\sf{y|x}}$}
\rput(6,0.5){$\D$}

\end{pspicture}
\caption{The decoder is causal $V_i = g(Y^{i})$ for all $i\in\{1, \ldots ,n\}$. Theorem \ref{theo:CwithChannel} characterizes the probability distributions $\QQ(u,x,y,v)$ that are achievable using two auxiliary random variables $W_1$  and $W_2$.}\label{fig:CwithChannel}
\end{center}
\end{figure}

\begin{theorem}[Causal Decoding]$\qquad\qquad\qquad\qquad\qquad$\label{theo:CwithChannel}
$1)$ The probability distribution $\QQ(u,x,y,v)$ is achievable if and only if it decomposes as follows:
\begin{eqnarray*}
\begin{cases}
&\QQ(u) = \PP_{u}(u),\\
& \QQ(y|x) = \mc{T}(y | x ),\\
&Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  U , \\
&\PP_{u}(u)   \otimes \QQ(x | u) \otimes  \mc{T}(y | x )\otimes \QQ(v | u,x,y) \text{ is achievable}.
\end{cases}
\end{eqnarray*}
$2)$ The probability distribution  $\PP_{u}(u)   \otimes \QQ(x | u) \otimes  \mc{T}(y | x )\otimes \QQ(v | u,x,y)$ is achievable if:
\begin{eqnarray}
\max_{\tilde{\QQ}\in \Q} \bigg( I( W_1;Y  |W_2 )  -  I( W_1, W_2 ; U   ) \bigg) > 0 ,  \label{eq:CwithChannel1}
\end{eqnarray}
$3)$ The probability distribution  $\PP_{u}(u)   \otimes \QQ(x | u) \otimes  \mc{T}(y | x )\otimes \QQ(v | u,x,y)$ is not achievable if:
\begin{eqnarray}
\max_{\tilde{\QQ}\in \Q} \bigg(I( W_1;Y  |W_2 )  -  I( W_1, W_2 ; U   ) \bigg) < 0  ,  \label{eq:CwithChannel2}
\end{eqnarray}
where $\Q$ is the set of distributions $\tilde{\QQ}   \in  \Delta(\mc{U}    \times \mc{X} \times \mc{W}_1  \times \mc{W}_2 \times \mc{Y} \times \mc{V}  )$ with auxiliary random variables that satisfy:
\begin{eqnarray*}
\begin{cases}
\sum_{w_1\in \mc{W}_1,\atop w_2\in \mc{W}_2} \tilde{\QQ}(u,x,w_1,w_2,y,v) \\
\quad =  \PP_{u}(u)   \otimes \QQ(x | u) \otimes  \mc{T}(y | x )\otimes \QQ(v | u,x,y), \\
Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  ( U,W_1 ,W_2),\\
V  -\!\!\!\!\minuso\!\!\!\!- (Y,W_2)    -\!\!\!\!\minuso\!\!\!\!-  ( U ,X,W_1).\\
\end{cases}
\end{eqnarray*}
The cardinalities of the support of auxiliary random variables $W_1$ and $W_2$ are bounded by $|\mc{W}_1| \leq   |\mc{U}|  \cdot   |\mc{X}|  +1$ and $|\mc{W}_2| \leq   |\mc{U}|  \cdot   |\mc{X}|  +1$.
\end{theorem}
The probability distribution with auxiliary random variables $W_1$ and $W_2$ decomposes as follows:
\begin{eqnarray*}
&&\tilde{\QQ}(u,x,w_1,w_2,y,v)   \nonumber\\
&=& \PP_{u}(u)   \otimes  \tilde{\QQ}(x,w_1,w_2 | u) \otimes  \mc{T}(y | x )   \otimes  \tilde{\QQ}(v | w_2 ,y ) .
\end{eqnarray*}
Auxiliary random variable  $W_2$ is used to correlate  the output of the decoder $V$ with the channel output $Y$. Auxiliary random variable $W_1$ is used to correlate  the channel inputs $X$ with the sequences $(U,W_2)$. Intuitively, $W_1$ is related to random variable $X$ whereas $W_2$ is related to random variable $V$.

\begin{ScketchProof}
\end{ScketchProof}
The proof of Theorem \ref{theo:CwithChannel} relies on the proof of Theorem \ref{theo:1CwithChannel} stated in App. \ref{sec:ProofDecomposition}, \ref{sec:ProofAchievability} and App. \ref{sec:ProofConverse}.
\begin{itemize}
\item[$1)$] Decomposition of the probability distribution. The joint  distribution $\QQ(u,x,y,v)$ should satisfy the marginal  distribution given by the source $\PP_{u}(u)$, the channel $\mc{T}(y|x)$ and the Markov chain property $Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  U$.
\item[$2)$] Achievability can be obtained by replacing random variable $V$ with auxiliary random variable $W_2$. The main difference appears at the decoder. In bloc $b+1 \in \N$, decoder returns the sequence $V^n_{b+1}$ drawn from the transition probability $\QQ_{\sf{v|yw_2}}^{\otimes n}$  depending on the current sequence of channel output $Y^n_{b+1}$ and decoded sequence $W^n_{2,b+1}(m)$ corresponding to index $m\in \mc{M}_{\sf{M}} $. Remark that both Markov chains $Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  ( U,W_1 ,W_2)$ and $V  -\!\!\!\!\minuso\!\!\!\!- (Y,W_2)    -\!\!\!\!\minuso\!\!\!\!-  ( U ,X,W_1)$ are satisfied.
\item[$3)$] The converse proof is obtained using the auxiliary random variables $W_{1,i} =  U^n_{i+1}$ and $W_{2,i} = Y^{i-1}$ in equation \eqref{eq:Conv1CwithChannel2}. The Markov chain $Y_i  -\!\!\!\!\minuso\!\!\!\!-X_i   -\!\!\!\!\minuso\!\!\!\!-  ( U_i,W_{1,i} , W_{2,i})$ is satisfied since  $Y_i$ is not included in $(W_{1,i} , W_{2,i})$. The Markov chain $V_i  -\!\!\!\!\minuso\!\!\!\!- (Y_i ,W_{2,i})   -\!\!\!\!\minuso\!\!\!\!-  ( U_i,X_i,W_{1,i} )$ is satisfied since  $Y^{i-1}$ is  included in $W_{2,i}$ and the causal decoding function writes $V_i = g_i(Y_i ,Y^{i-1})$ for all $i\in \{1,\ldots,n\}$.
\end{itemize}
This concludes the scketch of the proof of Theorem \ref{theo:CwithChannel}.

\section{Conclusion}\label{sec:Conclusion}

In this paper, we investigate the trade-off between transmission and coordination for a point-to-point communication problem with strictly causal and causal decoding. The encoder and decoder choose sequences of symbols in order to transmit information and to coordinate themselves. This paradigm has promising consequences for future decentralized networks since devices can coordinate more efficiently and transmit embedded additional information. We characterize the information constraint that determines the set of achievable probabilities distribution for a point-to-point model.  Optimal trade-offs between transmission and coordination are obtained directly by maximizing a utility function over the set of achievable probability distribution.

\appendices

\section{Decomposition of probability distribution of Theorem \ref{theo:1CwithChannel}}\label{sec:ProofDecomposition}

As stated in assertion $1)$ of Theorem \ref{theo:1CwithChannel}, the joint distribution $\QQ(u,x,y,v)$ should satisfy the marginal distribution given by the source $\PP_{u}(u)$, the channel $\mc{T}(y|x)$ and the Markov chain property $Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  (U,V)$.

Suppose the following conditions are satisfied.
\begin{eqnarray}
\begin{cases}
&\QQ(u) = \PP_{u}(u),\\
& \QQ(y|x) = \mc{T}(y | x ),\\
&Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  (U,V) , \\
&\PP_{u}(u)   \otimes \QQ(x,v | u) \otimes  \mc{T}(y | x ) \text{ is achievable}.
\end{cases}
\end{eqnarray}
Then, the probability distribution $\QQ(u,x,y,v) = \PP_{u}(u)   \otimes \QQ(x,v | u) \otimes  \mc{T}(y | x ) \in  \Delta(\mc{U} \times \mc{X} \times \mc{Y} \times \mc{V}  )$ is achievable.

In order to prove the converse, we consider a probability distribution $\QQ(u,x,y,v) $ whose marginal satisfies $\QQ_{\sf{u}} \neq \PP_{\sf{u}}$. This implies that the error probability $\PP_{\textsf{e}}(c)$ do not converges to zero as $n$ goes to infinity. Hence $\QQ(u,x,y,v) $ is not achievable. The same argument is used to prove that the probability distribution $\QQ(u,x,y,v) $ satisfies the marginal transition probability $ \QQ(y|x) = \mc{T}(y | x )$. The Markov chain $Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  (U,V)$ comes from the definition of the memoryless channel $\mc{T}(y | x )$ and from the strictly causal decoding that implies at instant $i\in \{1,\ldots, n\}$, random variable $V_i$ is a function of $Y^{i-1}$ and depends on  $Y_i$ only through $X_i$. Hence  at each instant $i\in \{1,\ldots, n\}$, the channel output satisfies the Markov chain $Y_i  -\!\!\!\!\minuso\!\!\!\!-X_i    -\!\!\!\!\minuso\!\!\!\!- (U_i, V_i)$.

This concludes the proof of the decomposition of probability distribution stated in assertion $1)$ of Theorem \ref{theo:1CwithChannel}.

\section{Achievability  of Theorem \ref{theo:1CwithChannel}}\label{sec:ProofAchievability}

In order to prove assertion $2)$ of Theorem \ref{theo:1CwithChannel}, we fix probability distribution $\QQ^{\star}_{\sf{uxyv}}$ and we consider the transition probability  $\QQ^{\star}_{\sf{w|uxv}} $ that achieves the maximum in \eqref{eq:1CwithChannel1}.
There exists a $\delta>0$  and a rate $\sf{R}\geq 0$ such that :
 \begin{eqnarray}
I( W;Y  ,V )    - \delta =\textsf{R} =  I( W; V ,  U) +  I( V; U   ) + 2\delta .
\end{eqnarray}
Note that the information constraint decomposes as follows:
\begin{eqnarray}
&&I( W;Y  |V )  -  I(  U ; V  ,W  )\\
  &=& I( W;Y  ,V )  -   I(  U ; V  ,W  )  - I( W; V)\\
&=& I( W;Y  ,V )    - I( W; V ,  U) -  I( V; U   ).
\end{eqnarray}
We prove that for all $\varepsilon>0$, there exists a $\bar{n}\in \N$ larger than $(n_1,n_2,n_3,n_4)$, given by equations \eqref{eq:1CwithChannelEvent2}, \eqref{eq:1CwithChannelEvent3} and \eqref{eq:1CwithChannelEvent4}, such that for all $n \geq \bar{n}$ there exists a strictly causal code $c \in \mc{C}$  that satisfies:
\begin{eqnarray}
\PP_c\bigg(\Big|\Big|Q^n - \QQ^{\star}_{\sf{uxyv}} \Big|\Big|_{\sf{v}} \geq \varepsilon\bigg)\leq \varepsilon.
\end{eqnarray}
\begin{figure}[!ht]
\begin{center}
\psset{xunit=0.5cm,yunit=0.5cm}
\begin{pspicture}(-0.5,-3.5)(14,10)
\psline[linewidth=2pt](0,-2)(14,-2)
\psline[linewidth=2pt](0,0)(14,0)
\psline[linewidth=2pt](0,2)(14,2)
\psline[linewidth=2pt](0,4)(14,4)
\psline[linewidth=2pt](0,6)(14,6)
\psline[linewidth=2pt](0,8)(14,8)
\psline[linewidth=0.5pt,linestyle=dashed ](2,-3)(2,9)
\psline[linewidth=0.5pt,linestyle=dashed ](4,-3)(4,9)
\psline[linewidth=0.5pt,linestyle=dashed ](6,-3)(6,9)
\psline[linewidth=0.5pt,linestyle=dashed ](8,-3)(8,9)
\psline[linewidth=0.5pt,linestyle=dashed ](10,-3)(10,9)
\psline[linewidth=0.5pt,linestyle=dashed ](13,-3)(13,9)
\rput[u](-0.5,8){$U^n$}
\rput[u](-0.5,6){$V^n$}
\rput[u](-0.5,4){$W^n$}
\rput[u](-0.5,2){$X^n$}
\rput[u](-0.5,0){$Y^n$}
\rput[u](-0.5,-2){$\hat{V}^n$}
\rput[u](3,8.8){$b-1$}
\rput[u](5,8.8){$b$}
\rput[u](7,8.8){$b+1$}
\rput[u](9,8.8){$b+2$}
\pspolygon[fillstyle=vlines*,linecolor=red,hatchcolor = red](6,7.8)(6,8.2)(8,8.2)(8,7.8)
\pspolygon[fillstyle=vlines*,linecolor=red,hatchcolor = red](6,5.8)(6,6.2)(8,6.2)(8,5.8)
\pspolygon[fillstyle=vlines*,linecolor=red,hatchcolor = red](4,3.8)(4,4.2)(6,4.2)(6,3.8)
\pspolygon[fillstyle=vlines*,linecolor=red,hatchcolor = red](4,1.8)(4,2.2)(6,2.2)(6,1.8)
\pspolygon[fillstyle=vlines*,linecolor=red,hatchcolor = red](4,-0.2)(4,0.2)(6,0.2)(6,-0.2)
\pspolygon[fillstyle=vlines*,linecolor=red,hatchcolor = red](6,-2.2)(6,-1.8)(8,-1.8)(8,-2.2)
\psline[linewidth=1.5pt,linecolor=red  ]{->}(7,7.7)(7,6.3)
\psline[linewidth=1.5pt,linecolor=red  ]{->}(7,5.7)(5,4.3)
\psline[linewidth=1.5pt,linecolor=red ]{->}(5,3.7)(5,2.2)
\psline[linewidth=1.5pt,linecolor=red ]{->}(5,1.7)(5,0.2)
\psline[linewidth=1.5pt,linecolor=red ]{->}(5,-0.3)(7,-1.8)
\pspolygon[fillstyle=vlines*,linecolor=blue,hatchcolor = blue](8,7.8)(8,8.2)(10,8.2)(10,7.8)
\pspolygon[fillstyle=vlines*,linecolor=blue,hatchcolor = blue](8,5.8)(8,6.2)(10,6.2)(10,5.8)
\pspolygon[fillstyle=vlines*,linecolor=blue,hatchcolor = blue](6,3.8)(6,4.2)(8,4.2)(8,3.8)
\pspolygon[fillstyle=vlines*,linecolor=blue,hatchcolor = blue](6,1.8)(6,2.2)(8,2.2)(8,1.8)
\pspolygon[fillstyle=vlines*,linecolor=blue,hatchcolor = blue](6,-0.2)(6,0.2)(8,0.2)(8,-0.2)
\pspolygon[fillstyle=vlines*,linecolor=blue,hatchcolor = blue](8,-2.2)(8,-1.8)(10,-1.8)(10,-2.2)
\psline[linewidth=1.5pt,linecolor=blue  ]{->}(9,7.7)(9,6.3)
\psline[linewidth=1.5pt,linecolor=blue  ]{->}(9,5.7)(7,4.3)
\psline[linewidth=1.5pt,linecolor=blue ]{->}(7,3.7)(7,2.2)
\psline[linewidth=1.5pt,linecolor=blue ]{->}(7,1.7)(7,0.2)
\psline[linewidth=1.5pt,linecolor=blue ]{->}(7,-0.3)(9,-1.8)
\pspolygon[fillstyle=vlines*,linecolor=vert,hatchcolor = vert](4,7.8)(4,8.2)(6,8.2)(6,7.8)
\pspolygon[fillstyle=vlines*,linecolor=vert,hatchcolor = vert](4,5.8)(4,6.2)(6,6.2)(6,5.8)
\pspolygon[fillstyle=vlines*,linecolor=vert,hatchcolor = vert](2,3.8)(2,4.2)(4,4.2)(4,3.8)
\pspolygon[fillstyle=vlines*,linecolor=vert,hatchcolor = vert](2,1.8)(2,2.2)(4,2.2)(4,1.8)
\pspolygon[fillstyle=vlines*,linecolor=vert,hatchcolor = vert](2,-0.2)(2,0.2)(4,0.2)(4,-0.2)
\pspolygon[fillstyle=vlines*,linecolor=vert,hatchcolor = vert](4,-2.2)(4,-1.8)(6,-1.8)(6,-2.2)
\psline[linewidth=1.5pt,linecolor=vert  ]{->}(5,7.7)(5,6.3)
\psline[linewidth=1.5pt,linecolor=vert  ]{->}(5,5.7)(3,4.3)
\psline[linewidth=1.5pt,linecolor=vert ]{->}(3,3.7)(3,2.2)
\psline[linewidth=1.5pt,linecolor=vert ]{->}(3,1.7)(3,0.2)
\psline[linewidth=1.5pt,linecolor=vert ]{->}(3,-0.3)(5,-1.8)
\end{pspicture}

\end{center}
\label{fig:Ach1CwithChannel}
\end{figure}
\textit{Random Code.} We consider a block-Markov random code $c\in \mc{C}(n)$ defined over $B\in \N$ blocs of length $n\in \N$. The total length of the code is denoted by $N = n\cdot B\in \N$.
\begin{itemize}
\item[$\bullet$] \textit{Random codebook.} Generates $| \mc{M}_{\sf{M}}   |= 2^{n   \sf{R}_{\sf{M}}   } $ sequences $V^n(m)$  drawn from the i.i.d. probability distribution $\QQ_{\sf{v}}^{\otimes n} $ with index  $m\in \mc{M}_{\sf{M}} $. Generates $| \mc{M}_{\sf{M}}   |= 2^{n (  \sf{R}_{\sf{M}}  +  \sf{R}_{\sf{L}} ) } $ sequences $W^n(m,l)$  drawn from the i.i.d. probability distribution $\QQ_{\sf{w}}^{\otimes n} $ with indexes  $(m,l) \in \mc{M}_{\sf{M}}  \times \mc{M}_{\sf{L}} $. \\
\item[$\bullet$] \textit{Encoding function.} At bloc $b\in \{1,\ldots B-1\}$, the encoder observes the sequence of source symbols $U^n_{b+1} \in  \mc{U}^n$ of the next bloc $b+1$ and finds an index $m\in \mc{M}_{\sf{M}}$ such that the sequences  $(U^n_{b+1},V^n_{b+1}(m)) \in A_{\varepsilon}^{{\star}{n}}$ are jointly typical. Encoder observes the sequence of symbols $(U^n_{b},V^n_{b}) \in  \mc{U}^n \times  \mc{V}^n$ of the current bloc $b$ and finds the index $l\in \mc{M}_{\sf{L}}$ such that the sequences  $(U^n_{b},V^n_{b},W^n_b(m,l) ) \in A_{\varepsilon}^{{\star}{n}}$ are jointly typical. Encoder sends the sequence $X^n_b$  drawn from the transition probability $\QQ_{\sf{x|uvw}}^{\otimes n}$  depending on the sequences $(U^n_{b},V^n_{b},W^n_b(m,l))$ of  bloc $b\in \N$.\\
\item[$\bullet$] \textit{Decoding function.} At the end of bloc $b\in \{1,\ldots B-1\}$, the decoder observes the sequence $Y^n_b$ and recall the sequence $V^n_b$ of bloc $b \in \N$. It finds the indexes $(m,l) \in \mc{M}_{\sf{M}}   \times \mc{M}_{\sf{L}} $ such that  $W^n_{b}(m,l)  \in A_{\varepsilon}^{{\star}{n}}(Y^n_b ,V^n_b )$ is jointly typical with  sequences $(Y^n_b,V^n_b ) $ of bloc $b\in \N$. In the next bloc $b+1 \in \N$, it returns the sequence $V^n_{b+1}(m)$  that correspond to the index $m\in \mc{M}_{\sf{M}} $.\\
\item[$\bullet$] \textit{First and Last blocs.} Over the first bloc, decoder $\D$ returns an arbitrary sequence of symbols $V_1^n \in \mc{V}^n$. Over the last bloc, encoder $\C$ send a sequence of symbols $X_B^n \in \mc{X}^n$ jointly typical with the sequences $(U_B^n,V_B^n)  \in \mc{U}^n \times \mc{V}^n$.
\end{itemize}
\textit{Expected error probability.} We define the following error events for an arbitrary bloc $b\in\N$.

\begin{itemize}
\item[$\bullet$]$E_1 =\bigg\{   u^n_{b+1}     \notin A_{\varepsilon}^{{\star}{n}} \bigg\}$.\\
There exists a  $n_1\in \N$ such that for all $n\geq n_1$, the expected probability of event $E_1$ is below $\varepsilon>0$. Properties of typical sequences are stated pp. 26 in \cite{ElGammalKim(book)11}.
\item[$\bullet$]$E_2 =\bigg\{ \forall  m\in \mc{M}_{\sf{M}} ,\quad v^n_{b+1}(m) \notin A_{\varepsilon}^{{\star}{n}}(u^n_{b+1} ) \bigg\}$.\\
Equation \eqref{eq:1CwithChannelEvent2} implies that $ \exists n_2\in \N$ such that $ \forall n\geq n_2$, the expected probability of $E_2$ is below $\varepsilon>0$.
The mutual covering lemma is stated pp. 208 in \cite{ElGammalKim(book)11}.
 \begin{eqnarray}
 \textsf{R}  & \geq&  I( V ; U    )  + \delta  .\label{eq:1CwithChannelEvent2}
\end{eqnarray}
\item[$\bullet$]$E_3 =\bigg\{ \forall  l\in \mc{M}_{\sf{L}} ,\quad w^n_{b}(m,l) \notin A_{\varepsilon}^{{\star}{n}}(u^n_{b} ,v^n_{b}  ) \bigg\}$.\\
Equation \eqref{eq:1CwithChannelEvent3} implies that $ \exists n_3\in \N$ such that $ \forall n\geq n_3$, the expected probability of $E_3$ is below $\varepsilon>0$. The mutual covering lemma is stated pp. 208 in \cite{ElGammalKim(book)11}.
 \begin{eqnarray}
 \textsf{R}  & \geq&  I( W ; U ,V )  + \delta   . \label{eq:1CwithChannelEvent3}
\end{eqnarray}
The sequences $(u^n_{b} ,v^n_{b} )$ are supposed to be jointly typical, i.e. event $E_2$ was not realized. \\
\item[$\bullet$]
\begin{small}$E_4 =\bigg\{ \exists (m',l') \neq (m ,l),\text{ s.t. }  w^n_{b}(m',l') \in A_{\varepsilon}^{{\star}{n}}(y^n_b, v^n_b  ) \bigg\}$.\end{small}\\
Equation \eqref{eq:1CwithChannelEvent4} implies that $ \exists n_4\in \N$ such that $ \forall n\geq n_4$, the expected probability of $E_4$ is below $\varepsilon>0$. The packing lemma stated pp. 46 in \cite{ElGammalKim(book)11}.
 \begin{eqnarray}
  \textsf{R}    & \leq&  I( W;Y,V)  -  \delta  . \label{eq:1CwithChannelEvent4}
\end{eqnarray}
The sequences $(y^n_{b} ,v^n_{b} )$ are supposed to be jointly typical, i.e. events $E_2$ and $E_3$ were not realized.
\end{itemize}
There exists a code $c^{\star} \in \mc{C}(n)$ with an error probability over each bloc $b\in\N$ below $4 \varepsilon$ for all $n\geq \bar{n} \geq \max(n_1,n_2,n_3,n_4)$. We denote by $\widetilde{Q}^N \in \Delta(\mc{U}\times \mc{X}\times \mc{Y}\times \mc{V} )$, the empirical distribution of symbols over every blocs $b \in \{2,\ldots ,B\}$ removing the first bloc and we show $\widetilde{Q}^N$ is close to the empirical distribution $Q^N$ over all the $B$ blocks, for a number of bloc $B\in \N$ sufficiently large. Denote by $Q_1$ is the empirical distribution of symbols over the first bloc.
\begin{eqnarray*}
&&\Big|\Big|{Q}^N  - \widetilde{Q}^N\Big|\Big|_{\sf{v}} \\
&=& \Big|\Big|\frac{1}{B} \cdot \Big( (B-1) \cdot \widetilde{Q}^N +  Q_1\Big)  - \widetilde{Q}^N\Big|\Big|_{\sf{v}}\\
&=& \frac{1}{B} \cdot  \Big|\Big|   Q_1 - \widetilde{Q}^N \Big|\Big|_{\sf{v}} \leq  \frac{2}{B} \cdot  \Big|\mc{U} \times \mc{X} \times\mc{V}  \Big| \leq \varepsilon.
\end{eqnarray*}
Then, the expected error probability is bounded by $\varepsilon$.
\begin{eqnarray*}
&&\E_c\bigg[ \PP_{\sf{e}}({c}) \bigg]\\
 &=&  \E_c\bigg[ \PP\bigg(\Big|\Big|{Q}^N - \QQ  \Big|\Big|_{\sf{v}}\geq 2\varepsilon\bigg) \bigg] \\
&=&  \E_c\bigg[ \PP\bigg(\Big|\Big|{Q}^N  - \widetilde{Q}^N + \widetilde{Q}^N - \QQ \Big|\Big|_{\sf{v}}\geq 2\varepsilon\bigg) \bigg] \\
&\leq&  \E_c\bigg[ \PP\bigg(\Big|\Big|{Q}^N  - \widetilde{Q}^N\Big|\Big| + \Big|\Big|\widetilde{Q}^N - \QQ \Big|\Big|_{\sf{v}}\geq 2\varepsilon\bigg) \bigg] \\
&\leq&  \E_c\bigg[ \PP\bigg(  \Big|\Big|\widetilde{Q}^N - \QQ \Big|\Big|_{\sf{v}}\geq 2\varepsilon -  \frac{2}{B} \cdot  \Big|\mc{U} \times \mc{X} \times\mc{V}  \Big|  \bigg) \bigg] \\
&\leq&  \E_c\bigg[ \PP\bigg(  \Big|\Big|\widetilde{Q}^N - \QQ \Big|\Big|_{\sf{v}}\geq \varepsilon \bigg) \bigg] \leq  1 - \bigg(1 - 4{\varepsilon}   \bigg)^{B-1}.
\end{eqnarray*}
This implies the existence of a code $c^{\star} \in \mc{C}(N)$ with an error probability below $4 \varepsilon$ for all $N\geq B \cdot \bar{n} \geq B \cdot \max(n_1,n_2,n_3,n_4)$.

\section{Converse of Theorem \ref{theo:1CwithChannel}}\label{sec:ProofConverse}

In order to prove assertion $3)$ of Theorem \ref{theo:1CwithChannel}, we consider a sequence of code $(c(n))_{n\geq1}$ that achieve the probability distribution $\QQ_{\sf{uxyv}}^{\star} $. We have the following equations:
\begin{eqnarray}
0&=& \sum_{i=1}^n I(Y_i  ;  U^n_{i+1}| Y^{i-1}) - \sum_{i=1}^n I( U_i  ;   Y^{i-1} | U^n_{i+1}) \label{eq:Conv1CwithChannel1} \\
&=& \sum_{i=1}^n I(Y_i  ;  U^n_{i+1}| Y^{i-1}) - \sum_{i=1}^n I( U_i  ;   Y^{i-1} , U^n_{i+1}) \label{eq:Conv1CwithChannel2} \\
&=& \sum_{i=1}^n I(Y_i  ;  U^n_{i+1}| Y^{i-1}, V_i ) - \sum_{i=1}^n I( U_i  ;   Y^{i-1} , V_i , U^n_{i+1}) \nonumber\\&&\label{eq:Conv1CwithChannel2b} \\
&\leq& \sum_{i=1}^n I(Y_i  ;  U^n_{i+1}| Y^{i-1}, V_i ) - \sum_{i=1}^n I( U_i  ;    V_i , U^n_{i+1}) \label{eq:Conv1CwithChannel2c} \\
&=& \sum_{i=1}^n I(Y_i  ;  U^n_{i+1}| V_i ) - \sum_{i=1}^n I( U_i  ;   V_i , U^n_{i+1}) \label{eq:Conv1CwithChannel3} \\
&=& \sum_{i=1}^n I(Y_i  ; W_i | V_i ) - \sum_{i=1}^n I( U_i  ;   V_i ,W_i ) \label{eq:Conv1CwithChannel4} \\
&\leq&  n \cdot  \max_{\tilde{\QQ}\in \Q}   \bigg(  I( W ; Y |V  )  -    I(  U ; V  ,W  )  \bigg).  \label{eq:Conv1CwithChannel5}
\end{eqnarray}
Equation \eqref{eq:Conv1CwithChannel1} is the Csiszar Sum Identity.\\
Equation \eqref{eq:Conv1CwithChannel2} comes from the i.i.d. property of the information sources $U$  that implies $ I( U_i ; U^n_{i+1} ) = 0$.\\
Equation \eqref{eq:Conv1CwithChannel2b} comes from the strictly causal decoding function writes $V_i = g_i(Y^{i-1})$ for all $i\in \{1,\ldots,n\}$, hence $V_i$ is a deterministic function of $Y^{i-1}$ and it can be added in the mutual informations.\\
Equation \eqref{eq:Conv1CwithChannel2c} comes from the  property of the mutual information.\\
Equation \eqref{eq:Conv1CwithChannel3} comes from the strictly causal decoding $V_i  = g(Y^{i-1})$ that is deterministic. The property of the mutual information implies $I(Y_i  ;  U^n_{i+1}| Y^{i-1}  )  - I(Y_i  ;  U^n_{i+1}| Y^{i-1}, V_i )  = I(V_i  ;  U^n_{i+1}| Y^{i-1}  )  - I(V_i  ;  U^n_{i+1}| Y^{i-1}, Y_i ) =0$ since $H(V_i  | Y^{i-1}) = 0$.\\
Equation \eqref{eq:Conv1CwithChannel4} comes from the introduction of the auxiliary random variable $W_i =  U^n_{i+1}$. The Markov chain $Y_i  -\!\!\!\!\minuso\!\!\!\!-X_i   -\!\!\!\!\minuso\!\!\!\!-  (W_i ,U_i,V_i)$ is satisfied since   $Y_i$ is not included in $W_i$.  \\
Equation \eqref{eq:Conv1CwithChannel5} comes from taking the maximum over the set of auxiliary random variables that satisfy the empirical distribution constraints and the Markov chain  $Y -\!\!\!\!\minuso\!\!\!\!-X  -\!\!\!\!\minuso\!\!\!\!- (W, U,V)$.

\section{Bound on the Cardinality of $|\mc{W}|$}\label{sec:CardinalityBound}

This result is based on the Lemma of Fenchel-Eggleston-Carathéodory.

\begin{lemma}[Cardinality Bound]\label{lemma:CardinalityBound1C}
The cardinality of the set of auxiliary random variable $W$ is bounded by $|\mc{W}| \leq   |\mc{U}|  \cdot   |\mc{X}| \cdot |\mc{V}| +1$.
\end{lemma}

\begin{proof}{Lemma \ref{lemma:CardinalityBound1C}}\\
Consider the following continuous functions from $\Delta(\mc{U} \times\mc{X} \times  \mc{V})$ into $\R$:
\begin{eqnarray*}
h_i\Big(\PP_{\sf{uxv|w}}\Big) =
\begin{cases}
\PP_{\sf{uxv|w}} (i) ,\; \text{ for } i=\big\{ 1,\ldots,  |\mc{U}|  \cdot  |\mc{X}| \cdot |\mc{V}| -1\big\},\\
H(Y|V) ,\quad \text{ for } i=  |\mc{U}|  \cdot  |\mc{X}| \cdot |\mc{V}|,\\
H(U|V)  ,\quad \text{ for } i=  |\mc{U}|  \cdot  |\mc{X}| \cdot |\mc{V}| +1.
\end{cases}
\end{eqnarray*}
Support Lemma stated pp. 631 in \cite{ElGammalKim(book)11}, implies that there exists an auxiliary random variable $W' \sim \PP_{\sf{w}'}$  defined on a  set $\mc{W}'$ with finite cardinality $|\mc{W}'|\leq  |\mc{U}|  \cdot   |\mc{X}| \cdot |\mc{V}| +1 $ such that:
\begin{eqnarray*}
H(Y|V,W)  &=& \int_{\mc{W}} H(Y|V,W = w) d \PP_{\sf{w}}(w)  \\
&=&   \sum_{w'\in\mc{W}'} H(Y|V,W' = w')  \PP_{\sf{w}'}(w')\\
&=& H(Y|V,W'),\\
H(U|V,W)  &=& \int_{\mc{W}} H(U|V,W = w) d \PP_{\sf{w}}(w)  \\
&=&   \sum_{w'\in\mc{W}'} H(U|V,W' = w')  \PP_{\sf{w}'}(w') \\
&=& H(U|V,W'),\\
\PP(U,V,X,Y) &=& \int_{\mc{W}} \PP(U,V,X,Y |W = w) d \PP_{\sf{w}}(w) \\
&=& \sum_{w'\in\mc{W}'} \PP(U,V,X,Y |W' = w') \PP_{\sf{w}'}(w') ,
\end{eqnarray*}
for all $ (u,x,v)$ indexed by $i=\big\{ 1,\ldots,  |\mc{U}|  \cdot  |\mc{X}|  -1\big\}$ and hence for all $ (u,x,v) \in \mc{U} \times  \mc{X} \times  \mc{V}  $.
Hence, the entropies $H(Y  |V )$ and $H(  U  )$ are  preserved and the information constraint writes:
\begin{eqnarray*}
&&I( W;Y  |V )  -   I(  U ; V  ,W  ) \\
 &= & H(Y  |V )  - H( Y  |V, W )  -   H(  U  )  + H(  U |V  ,W  ) \\
 &= & H(Y  |V )  - H( Y  |V, W' )  -   H(  U  )  + H(  U |V  ,W'  ) \\
&=& I( W';Y  |V )  -   I(  U ; V  ,W'  ) ,
\end{eqnarray*}
with $ |\mc{W}'| \leq  |\mc{U}|  \cdot  |\mc{X}| \cdot |\mc{V}| +1$. This concludes the proof of the bound on the cardinality of the support of the auxiliary random variable.
\end{proof}

\section{Proof of Corollaries \ref{coro:PerfectChannel} and \ref{coro:PastSource} }\label{sec:ProofCoro}

[Proof of Corollary \ref{coro:PerfectChannel}] Since the channel is perfect $Y  =X $, we have:
\begin{eqnarray}
 &&  \max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) \\
&=&  \max_{{\QQ}\in \Q} \bigg( I( W;X  |V )  -   I(  U ; V  ,W  )  \bigg).
\end{eqnarray}
Let us compare the above expression with the one stated in \cite{GossnerHernandezNeyman06} and \cite{Cuff(ImplicitCoordination)10}.
\begin{eqnarray}
&&  H(X |V)   - I(U ;X,V ) -  \big(  I( W;X  |V )  -  I(  U ; V  ,W  ) \big)  \nonumber\\
&=& H( X |  U , V, W )  + I( X ;  U ,  W | V )\nonumber \\
&-& I(U ;X,V ) -   I( W;X  |V )  + I(  U ; V  ,W  ) \\
&=& H( X |  U , V, W )  + I( X ;  U |  W , V ) \nonumber \\
&-& I(U ;X,V )  + I(  U ; V  ,W  ) \\
&=& H( X |  U , V, W )  + I( X , W , V ;  U  )  - I(U ;X,V ) \\
&=& H( X |  U , V, W )  + I( W ;  U  | X , V   )\geq 0.
\end{eqnarray}
For every auxiliary random variable $W$ we have the following inequality:
\begin{eqnarray}
 H(X |V)   - I(U ;X,V ) \geq    I( W;X  |V )  -  I(  U ; V  ,W  ) .
\end{eqnarray}
In particular if we choose auxiliary random variable $W =X $, we have equality:
\begin{eqnarray}
 I( W;X  |V )  -  I(  U ; V  ,W  ) =  H(X  |V )  -  I(  U ; V  ,X  ).
\end{eqnarray}
Hence, the optimal auxiliary random variable $W =X $ is equal to the channel inputs and we have the following equality:
\begin{small}
\begin{eqnarray}
\max_{{\QQ}\in \Q} \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg) = H(X |V)   - I(U ;X,V )  .
\end{eqnarray}
\end{small}
This concludes the proof of Corollary \ref{coro:PerfectChannel}.\\

[Proof of Corollary \ref{coro:PastSource}]
At instant $i\in\{1, \ldots, n\}$, the decoder observes the sequences $(Y^{i-1}, U^{i-1})$. Hence, the decoding condition writes $I( W;Y , U  |V ) $ instead of  $I( W;Y   |V ) $. This gives the following equations:
\begin{small}
\begin{eqnarray}
&&   \max_{{\QQ}\in \Q} \bigg( I( W;Y , U  |V )  -   I(  U ; V  ,W  )  \bigg) \\
&=&  \max_{{\QQ}\in \Q} \bigg(  I( W;Y | U  ,V ) +  I( W; U  |V ) -   I(  U ; V  ,W  )  \bigg)\\
&=&  \max_{{\QQ}\in \Q} \bigg(  I( W;Y | U  ,V )  -   I(  U ; V  )  \bigg)\\
&=&   I( X;Y | U  ,V )  -   I(  U ; V  )  .
\end{eqnarray}
\end{small}
The term $ I( W;Y | U  ,V ) $ is maximal with auxiliary random variable $W =X$ since there is a Markov chain $Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  (W ,U,V)$. This concludes the proof of Corollary \ref{coro:PastSource}.

\section{Proof of Theorem \ref{theo:ConvexProblem}}\label{sec:ProofTheoConvex}

First, we remark that the maximum is taken over the transition probability $\QQ(x,v | u)$ since the probability distributions $\PP_{u}(u)$ and $ \mc{T}(y | x )$ are given. Expected utility $\E_{\sf{uxyv}} [ \upsilon(U ,X ,Y ,V )]$ is a linear combination of transition probability $\QQ(x,v | u)$. Second, by definition the set $\bar{\mc{A}}$ is compact. It remains to prove that the set of achievable transition probability  $\bar{\mc{A}}$ is a convex set.

We investigates the  mapping $\Delta$ defined by equation \eqref{eq:MappingDelta} and we prove it is concave in the transition probability $\QQ(x,v | u)$
\begin{eqnarray}
\Delta : \QQ(x,v | u) \mapsto  \max_{ \QQ(w | u, x,v) } \bigg( I( W;Y  |V )  -   I(  U ; V  ,W  )  \bigg).\label{eq:MappingDelta}
\end{eqnarray}
For all $\lambda\in[0,1]$, for all $\QQ^1(x,v | u)$, $\QQ^2(x,v | u)$ we prove that mapping $\Delta$ is concave, i.e. satisfies equation \eqref{eq:ConcaveMappingDelta}:
\begin{eqnarray}
&&\lambda \cdot \Delta\Big(\QQ^1(x,v | u)\Big) +  (1 - \lambda) \cdot \Delta\Big(\QQ^2(x,v | u)\Big)\nonumber  \\
&\leq& \Delta\Big(\lambda \cdot\QQ^1(x,v | u) + (1 - \lambda) \cdot\QQ^2(x,v | u) \Big).\label{eq:ConcaveMappingDelta}
\end{eqnarray}
We denote by $\QQ^{\star1}(w |u,x,v )$ and $\QQ^{\star2}(w |u,x,v )$ the probabilities that achieves the maximum in equations \eqref{eq:ConcaveProba1} and \eqref{eq:ConcaveProba2} defined w.r.t. transition probabilities $\QQ^1(x,v | u)$ and $\QQ^2(x,v | u)$:
\begin{eqnarray}
&\max_{ \QQ^1(w | u, x,v) } \bigg( I_{\QQ^1}( W;Y  |V )  -   I_{\QQ^1}(  U ; V  ,W  )  \bigg),\label{eq:ConcaveProba1} \\% \text{ defined w.r.t. probability }\QQ^1(x,v | u),\\
&\max_{ \QQ^2(w | u, x,v) } \bigg( I_{\QQ^2}( W;Y  |V )  -   I_{\QQ^2}(  U ; V  ,W  )  \bigg). \label{eq:ConcaveProba2}
\end{eqnarray}
We define an auxiliary random variable $Z\in\{1,2\}$ independent of $U$ such that $\PP(Z = 1) = \lambda$ and $\PP(Z = 2) = 1 - \lambda$ and:
\begin{eqnarray}
\QQ^{\star} (x,v,w | u,z=1) =  \QQ^1(x,v | u) \cdot \QQ^{\star1}(w |u,x,v ), \label{eq:ConcaveProba3}\\
\QQ^{\star} (x,v,w | u,z=2) =  \QQ^2(x,v | u) \cdot \QQ^{\star2}(w |u,x,v ). \label{eq:ConcaveProba4}
\end{eqnarray}
This defines the transition probability $\QQ^{\star} (x,v | u)$ as a convex combination of $\QQ^1(x,v | u)$ and $\QQ^2(x,v | u)$:
\begin{eqnarray}
&&\QQ^{\star} (x,v | u)\\
&=& \sum_{w,z}\QQ^{\star} (x,v,w,z | u) \\
&=&  \sum_{w,z}  \PP(z) \cdot   \QQ^{\star} (x,v,w | u,z)  \\
&=&   \sum_{w}  \lambda \cdot   \QQ^{\star} (x,v,w | u,z=1) \\
&+&  \sum_{w}  (1 - \lambda) \cdot   \QQ^{\star} (x,v,w | u,z=2)   \\
&=&     \sum_{w}\lambda \cdot  \QQ^1(x,v | u) \cdot \QQ^{\star1}(w |u,x,v ) \\
&+&   \sum_{w}(1 - \lambda) \cdot   \QQ^2(x,v | u) \cdot\QQ^{\star2}(w |u,x,v )   \\
&=&     \lambda \cdot  \QQ^1(x,v | u) \cdot \sum_{w}\QQ^{\star1}(w |u,x,v ) \\
&+&   (1 - \lambda) \cdot   \QQ^2(x,v | u) \cdot \sum_{w} \QQ^{\star2}(w |u,x,v )   \\
&=&     \lambda \cdot  \QQ^1(x,v | u)  +   (1 - \lambda) \cdot   \QQ^2(x,v | u)   .
\end{eqnarray}
We have the following equations:
\begin{small}
\begin{eqnarray}
&&\lambda \cdot  \Delta\Big(\QQ^1(x,v | u)\Big) +  (1 - \lambda) \cdot \Delta\Big(\QQ^2(x,v | u)\Big) \nonumber\\
&=&\lambda \cdot \max_{ \QQ^1(w | u, x,v) } \bigg( I_{Q^1}( W;Y  |V )  -   I_{Q^1}(  U ; V  ,W  )  \bigg)  \nonumber\\
&+& (1 - \lambda) \cdot \max_{ \QQ^2(w | u, x,v) } \bigg( I_{Q^2}( W;Y  |V )  -   I_{Q^2}(  U ; V  ,W  )  \bigg) \nonumber\\&&\label{eq:Concavity2} \\
&=& \lambda \cdot  \bigg( I_{\QQ^{\star1}}( W;Y  |V )  -   I_{\QQ^{\star1}}(  U ; V  ,W  )  \bigg)  \\
&+& (1 - \lambda) \cdot  \bigg( I_{\QQ^{\star2}}( W;Y  |V )  -   I_{\QQ^{\star2}}(  U ; V  ,W  )  \bigg) \label{eq:Concavity3} \\
&=& \lambda \cdot  \bigg( I_{\QQ^{\star}}( W;Y  |V,  Z = 1 )  -   I_{\QQ^{\star}}(  U ; V  ,W  |   Z = 1)  \bigg)    \nonumber\\
&+& (1 - \lambda) \cdot  \bigg( I_{\QQ^{\star}}( W;Y  |V,  Z = 2 )  -   I_{\QQ^{\star}}(  U ; V  ,W|   Z = 2  )  \bigg)\nonumber\\&& \label{eq:Concavity4} \\
&=& I_{\QQ^{\star}}( W;Y  |V,  Z  )  -   I_{\QQ^{\star}}(  U ; V  ,W  |   Z )  \label{eq:Concavity5} \\
&\leq&  I_{\QQ^{\star}}( W,  Z;Y  |V  )  -   I_{\QQ^{\star}}(  U ; V  ,W  |   Z )  \label{eq:Concavity6} \\
&=&  I_{\QQ^{\star}}( W,  Z;Y  |V  )  -   I_{\QQ^{\star}}(  U ; V  ,W ,   Z )  \label{eq:Concavity7} \\
&=&  I_{\QQ^{\star}}( W' ;Y  |V  )  -   I_{\QQ^{\star}}(  U ; V  ,W' )  \label{eq:Concavity8} \\
&=&  \max_{ \QQ^{\star}(w'' | u, x,v) } \bigg( I_{\QQ^{\star}}( W'' ;Y  |V  )  -   I_{\QQ^{\star}}(  U ; V  ,W'' )   \bigg) \label{eq:Concavity9} \\
&=& \Delta\Big(\QQ^{\star}(x,v | u)\Big)  \label{eq:Concavity10} \\
&=& \Delta\Big( \lambda \cdot  \QQ^1(x,v | u)  +   (1 - \lambda) \cdot   \QQ^2(x,v | u)  \Big). \label{eq:Concavity11}
\end{eqnarray}
\end{small}
Equations  \eqref{eq:Concavity2} and  \eqref{eq:Concavity3} follows from the definitions of the mapping $\Delta\big(\QQ(x,v | u)\big)$ and probabilities $\QQ^{\star1}$ and $\QQ^{\star2}$ in equations \eqref{eq:ConcaveProba1} and \eqref{eq:ConcaveProba2}.\\
Equation  \eqref{eq:Concavity4} comes from the introduction of the auxiliary random variable $Z$ and the definition of transition probability $\QQ^{\star} (x,v,w | u,z) $ in equations \eqref{eq:ConcaveProba3} and \eqref{eq:ConcaveProba4}.\\
Equation  \eqref{eq:Concavity5} comes from the definition of the mutual information.\\
Equation  \eqref{eq:Concavity6} comes from the property of the mutual information.\\
Equation  \eqref{eq:Concavity7} comes from the fact that random variables $U$ and $Z$ are independent, hence $I_{\QQ^{\star}}(  U ;  Z )=0$.\\
Equation  \eqref{eq:Concavity8} comes from the  introduction of the auxiliary random variable $W' = (W, Z) $. Random variable $W' = (W, Z) $ satisfies the Markov chain $Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  (W' ,U,V)$.\\
Equation  \eqref{eq:Concavity9} comes from taking the maximum over the transition probability $\QQ^{\star}(w'' | u, x,v)$ that satisfies the Markov chain $Y  -\!\!\!\!\minuso\!\!\!\!-X    -\!\!\!\!\minuso\!\!\!\!-  (W'' ,U,V)$.\\
Equation \eqref{eq:Concavity10} follows from the definition of the mapping $\Delta\big(\QQ(x,v | u)\big)$ in equation  \eqref{eq:MappingDelta}.\\
Equation \eqref{eq:Concavity11} follows from the definition of transition probability $\QQ^{\star} (x,v | u)  = \lambda \cdot  \QQ^1(x,v | u)  +   (1 - \lambda) \cdot   \QQ^2(x,v | u) $ of the mapping $\Delta\big(\QQ(x,v | u)\big)$.

Using the same arguments for any convex combination, we prove that the mapping $\Delta$ is concave in transition probability $\QQ^{\star} (x,v | u)$. By definition $\mc{A}$ is the set of probabilities $ \QQ(x,v | u) $ such that $\Delta\Big( \QQ^{\star} (x,v | u)\Big)\geq 0$. The concavity property implies $  \Delta\Big( \lambda \cdot  \QQ^1(x,v | u)  +   (1 - \lambda) \cdot   \QQ^2(x,v | u)  \Big) \geq \lambda \cdot  \Delta\Big(\QQ^1(x,v | u)\Big) +  (1 - \lambda) \cdot \Delta\Big(\QQ^2(x,v | u)\Big) \geq0$, hence the convex combination $\lambda \cdot  \QQ^1(x,v | u)  +   (1 - \lambda) \cdot   \QQ^2(x,v | u)$ also belong to $\bar{\mc{A}}$. This proves that $\bar{\mc{A}}$ is a convex set and the optimization problem stated in equation \eqref{eq:OptimisationProblem} of Theorem \ref{theo:ConvexProblem} is a convex optimization problem.

\section*{Acknowledgment}

The author would like to thank Samson Lasaulce and Benjamin Larrousse for useful conversations.

\bibliographystyle{ieeetr}

config: arxiv