\section{Introduction}
The concept of non-secret common randomness generation was initially introduced by Ahlswede and Csiszár in \cite{part2} for its high relevance in the theory of message identification \cite{identification}, since it may allow a significant increase in the identification capacity of channels\cite{part2,trafo,Ahlswede2021}.

The identification scheme is conceptually different from the classical transmission scheme proposed by Shannon \cite{shannon}. In fact, in the identification framework, the sender is not interested in what the received message is. He rather wants to know if a specific message of special interest to him has been sent or not. Naturally, the sender has no knowledge of that message. Otherwise, the problem would be trivial.
The identification  scheme has striking applications  in digital watermarking \cite{Moulin,watermarkingahlswede, watermarking}. It is also highly relevant in many practical applications which require robust and ultra-reliable low latency information exchange including several machine-to-machine
and human-to-machine systems \cite{applications}, the tactile internet \cite{tactiles} and industry 4.0 \cite{industrie40}. 

Several models for CR generation were introduced in \cite{part2} including the two-source model, which consists of 
two terminals who observe independent and identically distributed (i.i.d.) samples from a known
discrete random source, and who wish to generate a shared random variable with the largest possible probability of agreement by communicating as little as possible.

In \cite{part2}, the authors considered the case when the terminals are allowed to communicate over a classical perfect channel as well as the case when the terminals communicate over a  classical noisy channel. A single-letter expression for the CR capacity 
  for both cases was derived in \cite{part2}. 
  The CR capacity is defined as the maximum amount of shared random variable per channel use. It has been shown in \cite{part2} that the CR capacity can be always  attained with nearly uniform random variables. This is the most convenient form of CR  particularly in the context of key generation \cite{part1}\cite{Maurer}, where further constraints on secrecy are imposed. In our work, however, we will not impose any secrecy requirements.
Later, the results on CR capacity  have been extended in \cite{CRgaussian} to Gaussian channels for their practical relevance in many communication situations such as satellite and deep space
communication links\cite{practicalgaussian}, wired and wireless communications, etc.

  We consider the two-source model for uniform common randomness (UCR) generation in which the two terminals aim to agree on a common uniform or nearly uniform random variable with high probability by communicating as little as possible over an arbitrary single-user channel.
The main contribution of our work consists in establishing a general formula for the UCR capacity  that holds for arbitrary point-to-point channels. In our proof of the UCR capacity formula, we will make use of a well-known result of \cite{verduhan}, which is a general formula  characterizing the transmission capacity of arbitrary channels based on the inf-information rate between the channel inputs and outputs. It is worth-mentioning that no further assumption on stationarity, ergodicity or any kind of  information stability is imposed.  
 For ease of notation, we will assume in the proof of the UCR capacity that the channel input and output alphabets are finite. However, our result does not depend on that assumption.

\textit{Outline:} The rest of the paper is structured as follows. In Section \ref{sec2}, we present our system model for CR generation, review the definition of an achievable transmission and UCR rate  and present our main result. Section \ref{converseproof} is devoted to the proof of the converse of the UCR capacity, where inspired by \cite{strongconverse}, we will use a change of measure argument. In Section \ref{directpart}, we prove the achievability part by extending the UCR generation scheme introduced by Ahlswede and Csiszár to arbitrary single-user channels. Section \ref{conclusion} contains concluding remarks and proposes a potential future work in this field. 

\textit{Notation:} Throughout the paper,  $\log$ is taken to  base 2. For any set $\mathcal E,$ $\mathcal E^c$ refers to its complement.  For any random variable $X$ with distribution $P_X,$ $\text{supp}(P_X)$ refers to its support. For any random variables $X$ and $Y$ with respective probability distribution $P_{X}$ and $P_{Y}$, $D(P_{X}||P_{Y})$ denotes the relative entropy between $P_X$ and $P_Y.$
\section{System Model and Definitions}
\label{sec2}
\subsection{System Model}
\label{systemmodel}
Let a discrete memoryless multiple source (DMMS) $P_{XY}$ with two components, with  generic variables $X$ and $Y$ on alphabets $\mathcal{X}$ and $\mathcal{Y}$, respectively, be given. The DMMS emits i.i.d. samples of $(X,Y).$
Suppose that the outputs of $X$ are observed only by Terminal $A$ and those of $Y$ only by Terminal $B.$ We further assume that the joint distribution of $(X,Y)$ is known to both terminals.
Terminal $A$
can communicate with Terminal $B$ over an arbitrary single-user channel $W,$ defined as an arbitrary sequence of $n$-dimensional conditional distributions from $\mathcal T^n$ to $\mathcal Z^n$, where $\mathcal T$ and $\mathcal Z$ are the  input and output alphabets, respectively.
There are no other resources available to any of the terminals. 
\begin{definition}
A CR-generation protocol of block-length $n$ consists of:
\begin{enumerate}
    \item A function $\Phi$ that maps $X^n$ into a random variable $K$ with alphabet $\mathcal{K}$ generated by Terminal $A.$
    \item A function $\Lambda$ that maps $X^n$ into the input sequence $T^n=(T_1,\hdots,T_n).$
    \item A function $\Psi$ that maps $Y^n$ and the  output sequence $Z^n=(Z_1,\hdots, Z_n)$ into a random variable $L$ with alphabet $\mathcal{K}$ generated by Terminal $B.$
\end{enumerate}
Such a protocol induces a pair of random variables $(K,L)$ whose joint distribution is determined by $P_{XY}$ and by the channel $W$. Such a pair of random variables $(K,L)$ is called permissible.
This is illustrated in Fig. \ref{CRprotocol}.
\end{definition}
\begin{figure}
\centering
\input{figcorrelated_SISO}
\caption{Two-source model for CR generation with unidirectional communication over an arbitrary point-to-point channel $W.$}
\label{CRprotocol}
\end{figure}
\subsection{Achievable Rate and Capacity}
We define first an acheivable UCR rate and the UCR capacity. The uniformity of the random variable $K$ is measured using the total variation distance between $P_K$ and $P_{\text{unif}}$, where $P_{\text{unif}}$ is the uniform distribution on $\mathcal K.$ This total variation distance is denoted by $$ d(P_{K},P_{\text{unif}})=\frac{1}{2}\sum_{k\in \mathcal K}\lvert P_{K}(k)-\frac{1}{\lvert \mathcal K \rvert} \rvert.$$
\begin{definition} 
\label{ucrrate}
 A number $H$ is called an achievable UCR rate  if there exists a non-negative constant $c$ such that for every $\alpha>0,$ $\beta>0,$ $\delta>0$  and for sufficiently large $n$ there exists a permissible  pair of random variables $(K,L)$ such that
\begin{equation}
   \mathbb P\left[K\neq L\right]\leq \alpha, 
    \label{errorcorrelated}
\end{equation}
\begin{equation}
    |\mathcal{K}|\leq 2^{cn},
    \label{cardinalitycorrelated}
\end{equation}
\begin{equation}
 d(P_{K},P_{\text{unif}}) \leq \beta,
  \label{uniformity}
\end{equation}
\begin{equation}
    \frac{1}{n}H(K)> H-\delta,
     \label{ratecorrelated}
\end{equation}
where the constant $\alpha>0$ in \eqref{errorcorrelated} corresponds to an upper bound on the error probability from the CR generation perspective and where $\beta>0$ in \eqref{uniformity} is an upper-bound on the total variation distance between the distribution of $K$ and the uniform distribution on $\mathcal K.$
\end{definition}
\begin{remark}
Together with \eqref{errorcorrelated}, the technical condition  \eqref{cardinalitycorrelated} ensures for every $\epsilon>0$ and sufficiently large block-length $n$ that 
\begin{align}
    \bigg| \frac{H(K)}{n}-\frac{H(L)}{n} \bigg| \leq \epsilon. \nonumber
\end{align}
\end{remark}
\begin{definition} 
The UCR capacity $C_{UCR}(P_{XY},W)$ is the maximum achievable UCR rate.
\end{definition}
Next, we define an achievable transmission rate and the transmission capacity of the channel $W.$ For this purpose, we begin by providing the definition of a transmission code for the channel $W.$
\begin{definition}
\label{defcode}
A transmission-code $\Gamma$ of block-length $n$ and size \footnote{\text{This is the same notation used in} \cite{codingtheorems}.} $\lVert \Gamma \rVert $  for the channel $W$ is a family of pairs of codewords and decoding regions $\left\{(\bs{t}_\ell,\ensuremath{\mathcal{D}}_\ell): \ell=1,\ldots,\lVert \Gamma \rVert \right\}$ such that for all $\ell,j \in \{1,\ldots,\lVert \Gamma \rVert\}$  
\begin{align}
&\ensuremath{\mathcal{D}}_\ell \cap \ensuremath{\mathcal{D}}_j = \emptyset,\quad \ell \neq j. \nonumber
\end{align}The maximum error probability is expressed as 
\begin{align}
    e(\Gamma)=\underset{\ell \in \{1,\ldots,\lVert \Gamma \rVert\}}{\max}W({\ensuremath{\mathcal{D}}_\ell^{c}}|\mathbf{t}_\ell). \nonumber
\end{align}
\end{definition}
\begin{definition}
\label{deftransmissionrate}
   A real number $R$ is called an \textit{achievable} transmission rate of the channel $W$ if for every $\theta,\delta>0$ there exists a code sequence $(\Gamma_n)_{n=1}^\infty$, where each code $\Gamma_n$ of block-length $n$ is defined according to Definition \ref{defcode},  such that
    \[
        \frac{\log\lVert \Gamma_n\rVert}{n}\geq R-\delta
    \]
    and
    \begin{align}
        e(\Gamma_n)\leq\theta
        \nonumber
    \end{align}
    for sufficiently large $n.$ 
\end{definition}
\begin{definition}
The transmission capacity of the channel $W$ is the maximum achievable transmission rate for $W$ and it is denoted by $C(W).$
\end{definition}
\begin{remark}
Throughout the paper, we consider the maximum error probability criterion. The transmission capacity remains unchanged under the average error probability criterion. 
\end{remark}
A general formula for the transmission capacity was established in \cite{verduhan} and it is illustrated in the following theorem:
\begin{theorem}
\label{generalcapacityformula} \cite{verduhan}
A general formula of the transmission capacity of an arbitrary channel $W$ is equal to 
\begin{align}
C(W)=\underset{\bs{T}}{\sup} \ \underline{I}(\bs{T},\bs{Z}),
\nonumber \end{align}
where $\bs{T}$ is an input process in the form of a sequence of finite-dimensional distributions $\bs{T}=\{T^n=(T_1,\hdots,T_n)\}_{n=1}^{\infty}$
and where $\bs{Z}=\{Z^n=(Z_1,\hdots,Z_n)\}_{n=1}^{\infty}$ is the corresponding output sequence of finite-dimensional distributions induced by $\bs{T}$ via the channel $W.$ Furthermore, $\underline{I}(\bs{T},\bs{Z})$ denotes the inf-information rate between $\bs{T}$ and $\bs{Z},$ which is defined as 
$$ \sup\left\{R: \underset{n\rightarrow\infty}{\lim} \mathbb P\left[\frac{1}{n}i(T^n;Z^n)\leq R \right]=0  \right\},  $$
where $i(T^n;Z^n)$ is the information density of the channel $W.$
\end{theorem}
\subsection{Main Result}
\label{mainresult}
In this section, we give a general formula for the UCR capacity for the model presented in Section \ref{systemmodel}.
\begin{theorem}
For the model in Fig \ref{CRprotocol}, the UCR capacity $C_{UCR}(P_{XY},W)$ is equal to
\begin{equation}
    C_{UCR}(P_{XY},W)= \underset{\substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq C(W)}}}}{\max} I(U;X),
    \nonumber
\end{equation}
with $C(W)$ being the transmission capacity of the channel $W$.
\label{main theorem}
\end{theorem}
The converse proof of Theorem \ref{main theorem} is provided in Section \ref{converseproof} and the direct proof is provided in Section \ref{directpart}.
\section{Converse Proof of Theorem \ref{main theorem}}
\label{converseproof}
Let $(K,L)$ be a permissible pair according to a fixed CR-generation protocol of block-length $n,$ as introduced in Section \ref{systemmodel}. We recall that the latter consists of:
\begin{enumerate}
    \item A function $\Phi$ that maps $X^n$ into a random variable $K$ with alphabet $\mathcal{K}$ generated by Terminal $A.$
    \item A function $\Lambda$ that maps $X^n$ into the input sequence $T^n=(T_1,\hdots,T_n).$
    \item A function $\Psi$ that maps $Y^n$ and the  output sequence $Z^n=(Z_1,\hdots, Z_n) $ into a random variable $L$ with alphabet $\mathcal{K}$ generated by Terminal $B.$
\end{enumerate}
We further assume that $(K,L)$ satisfies $\eqref{errorcorrelated}$  $\eqref{cardinalitycorrelated},$ \eqref{uniformity} and $\eqref{ratecorrelated}$, with $\alpha>0$ being an upper-bound on the error probability from the CR generation perspective and with $\beta>0$ being  an upper-bound on the total variation distance between the distribution of $K$ and the uniform distribution on $\mathcal K.$
We are going to show for some $\alpha'(n)>0$ that
\begin{align}
    \frac{H(K)}{n} \leq \underset{ \substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq C(W)+\alpha'(n)}}}}{\max} I(U;X), \nonumber 
\end{align}
 where $\underset{n\rightarrow \infty}{\lim}\alpha'(n)$ can be made arbitrarily small.
In our proof, we will use  the following lemma: 
\begin{lemma} (Lemma 17.12 in \cite{codingtheorems})
For arbitrary random variables $S$ and $R$ and sequences of random variables $X^{n}$ and $Y^{n}$, it holds that
\begin{align}
 &I(S;X^{n}|R)-I(S;Y^{n}|R) \nonumber \\ 
 &=\sum_{i=1}^{n} I(S;X_{i}|X_{1},\dots, X_{i-1}, Y_{i+1},\dots, Y_{n},R) \nonumber \\ &\quad -\sum_{i=1}^{n} I(S;Y_{i}|X_{1},\dots, X_{i-1}, Y_{i+1},\dots, Y_{n},R) \nonumber \\
 &=n[I(S;X_{J}|V)-I(S;Y_{J}|V)],\nonumber
\end{align}
where $V=(X_{1},\dots, X_{J-1},Y_{J+1},\dots, Y_{n},R,J)$, with $J$ being a random variable independent of $R$,\ $S$, \ $X^{n}$ \ and $Y^{n}$ and uniformly distributed on $\{1 ,\dots, n \}$.
\label{lemma1}
\end{lemma}
Let $J$ be a random variable uniformly distributed on $\{1,\dots, n\}$ and independent of $K$, $X^n$ and $Y^n$. We further define $U=(K,X_{1},\dots, X_{J-1},Y_{J+1},\dots, Y_{n},J).$ It holds that $U \circlearrow{X_J} \circlearrow{Y_J}.$ \\
Notice  that
{{\begin{align}
H(K)&\overset{(a)}{=}H(K)-H(K|X^{n})\nonumber\\
&=I(K;X^{n}) \nonumber\\
&\overset{(b)}{=}\sum_{i=1}^{n} I(K;X_{i}|X_{1},\dots, X_{i-1}) \nonumber\\
&=n I(K;X_{J}|X_{1},\dots, X_{J-1},J) \nonumber\\
&\overset{(c)}{\leq }n I(U;X_{J}), \nonumber
\end{align}}} where $(a)$ follows because $K=\Phi(X^n)$ and $(b)$ and $(c)$ follow from the chain rule for mutual information.
Applying Lemma \ref{lemma1} for $S=K$, $R=\varnothing$ with $V=(X_1,\hdots, X_{J-1},Y_{J+1},\hdots, Y_{n},J)$ yields
\begin{align}
&I(K;X^{n})-I(K;Y^{n}) 
\nonumber \\&=n[I(K;X_{J}|V)-I(K;Y_{J}|V)] \nonumber\\
&\overset{(a)}{=}n[I(KV;X_{J})-I(K;V)-I(KV;Y_{J})+I(K;V)] \nonumber\\
&\overset{(b)}{=}n[I(U;X_{J})-I(U;Y_{J})], 
\label{UhilfsvariableMIMO1}
\end{align}
where $(a)$ follows from the chain rule for mutual information and $(b)$ follows from $U=(K,V)$. \\
It results using (\ref{UhilfsvariableMIMO1}) that
\begin{align}
n[I(U;X_{J})-I(U;Y_{J})]
&=I(K;X^{n})-I(K;Y^{n}) \nonumber\\
&=H(K)-I(K;Y^{n})\nonumber \\ 
&=H(K|Y^n).
\nonumber
\end{align}
The next step is to show that
\begin{align}
    \frac{H(K|Y^n)}{n}\leq C(W)+\alpha'(n),
\label{toprove} \end{align}
where $\underset{n\rightarrow \infty}{\lim} \alpha'(n)$ can be made arbitrarily small.
In order to prove \eqref{toprove}, we will use a change of measure argument.
\begin{comment}
\subsection{If $\alpha+\beta \geq \frac{1}{2}$}
In this case, it holds
\begin{align}
    \frac{1}{n}H(K|Y^n)&=\frac{1}{n}H(K|Y^n,Z^n)+\frac{1}{n}I(K;Z^n|Y^n) \nonumber
\end{align}
On the one hand, we have
\begin{align}
    \frac{1}{n}H(K|Y^n,Z^n) &\leq \frac{1}{n} H(K|\Psi(Y^n,Z^n)) \nonumber \\
    &=\frac{1}{n} H(K|L) \nonumber \\
    &\overset{(a)}{\leq} \frac{1}{n}\left(1+\mathbb P\left[K\neq L\right] \log\lvert \mathcal K\rvert \right) \nonumber \\
    &\overset{(b)}{\leq} \frac{1}{n}+\alpha c,
\nonumber \end{align}
where $(a)$ follows from Fano's inequality and where $(b)$ follows from \eqref{errorcorrelated} and \eqref{cardinalitycorrelated}.
On the other hand, it holds that
\begin{align} 
\frac{1}{n} I(K;Z^{n}|Y^{n})&\leq \frac{1}{n} I(X^{n}K;Z^{n}|Y^{n}) \nonumber\\
& \overset{(a)}{\leq }\frac{1}{n} I(T^n;Z^n|Y^{n})  \nonumber \\
& =  \frac{1}{n} h(Z^n|Y^{n})-\frac{1}{n}  h(Z^n|T^n,Y^{n}) \nonumber \\
& \overset{(b)}{=} \frac{1}{n}  h(Z^n|Y^{n})-\frac{1}{n}  h(Z^n|T^n) \nonumber \\
& \overset{(c)}{\leq }   \frac{1}{n} h(Z^n)-\frac{1}{n}  h(Z^n|T^n) \nonumber \\
& = \frac{1}{n} I(T^n;Z^n)  \nonumber 
\end{align}
where $(a)$ follows from the Data Processing Inequality because $Y^{n}\circlearrow{X^{n}K}\circlearrow{T^n}\circlearrow{Z^{n}}$ forms a Markov chain, $(b)$ follows because $Y^{n}\circlearrow{X^{n}K}\circlearrow{T^n}\circlearrow{Z^{n}}$ forms a Markov chain and $(c)$ follow because conditioning does not increase entropy.
Therefore, for $\alpha+\beta\geq \frac{1}{2}$
\begin{align}
    \frac{1}{n}H(K|Y^n)\leq \frac{1}{n}+\alpha c+\frac{1}{n} I(T^n,Z^n).
\nonumber \end{align}
\end{comment}
Assume without loss of generality that $\alpha+\beta<\frac{1}{2}.$
Let $\epsilon$ any positive constant satisfying for sufficiently large $n$
\begin{align}
    2(\alpha+\beta) <\mathbb P\left[\frac{1}{n}i(T^n;Z^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon \right]. \nonumber
    \end{align}
    Since
\begin{align}
   \underline{I}(\bs{T};\bs{Z}) 
   = \sup\left\{R: \underset{n\rightarrow\infty}{\lim} \mathbb P\left[\frac{1}{n}i(T^n;Z^n)\leq R \right]=0  \right\},\nonumber
 \end{align}
  and since $0<2(\alpha+\beta)<1,$  we know that such an $\epsilon>0$ exists.
    It follows that
    \begin{align}
       0\leq \mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]<1-2(\alpha+\beta). \label{choiceepsilon}
    \end{align}
    Let $\gamma=2\log\left(\frac{4}{1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]}\right).$ 
    \begin{lemma}
    \label{boundgamma}
    It holds that
        \begin{align}
        4<\gamma<2\log\frac{4}{\alpha+\beta}.
    \nonumber \end{align}
    \end{lemma}
    \begin{proof}
    We have
        \begin{align}
       0\leq \mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]<1-2(\alpha+\beta). 
    \nonumber \end{align}
    This implies that
    \begin{align}
       \alpha+\beta\leq \alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]<1-(\alpha+\beta)
    \nonumber \end{align}
    which yields
    \begin{align}
        \alpha+\beta< 1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]\leq 1-(\alpha+\beta).
    \nonumber \end{align} 
    Therefore
    \begin{align}
        4<\frac{4}{1-(\alpha+\beta)}\leq \frac{4}{1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]}<\frac{4}{\alpha+\beta}.
    \nonumber \end{align}
    It follows that
    \begin{align}
        4=2\log4<\gamma<2\log\frac{4}{\alpha+\beta}.
    \nonumber \end{align}
    \end{proof}
Consider now the sets
\begin{align}
    \mathcal L=\{ k\in \mathcal K: \log\frac{1}{P_{K}(k)} \geq \log\lvert \mathcal K \rvert -\frac{\gamma}{2}     \}
\nonumber \end{align}
and
\begin{align}
    \mathcal D=\{ (k,y^n)\in \mathcal K\times \mathcal Y^n:  \log\frac{1}{P_{K|Y^n}(k|y^n)} \geq \log \lvert \mathcal K \rvert -\gamma \}.
\nonumber \end{align}
\begin{lemma}
\label{boundprobsett}
It holds that
\begin{align}
\mathbb P\left[K\in \mathcal L \right]\geq 1-(\beta+2^{-\frac{\gamma}{2}}).
\nonumber \end{align}
\end{lemma}
\begin{proof}
By using a standard argument in information-spectrum methods (see Lemma 2.1.2 in \cite{infspectrum}), we have using \eqref{uniformity}
\begin{align}
    \beta &\overset{(a)}{\geq}  d(P_{K},P_{\text{unif}})\nonumber \\
    &\overset{(b)}{\geq}  \mathbb P[ K \notin \mathcal L]-P_{\text{unif}}(\mathcal L^c) \nonumber \\
    &\overset{(c)}{\geq} \mathbb P[ K \notin \mathcal L]-2^{-\frac{\gamma}{2}},
\nonumber \end{align}
where $(a)$ follows from \eqref{uniformity}, $(b)$ follows from Lemma 2.1.2 in \cite{infspectrum} and $(c)$ follows because
\begin{align}
    P_{\text{unif}}(\mathcal L^c)&=\sum_{k\in \mathcal L^c} \frac{1}{\lvert \mathcal K \rvert} \nonumber \\
    &\leq \sum_{k\in \mathcal L^c} 2^{-\frac{\gamma}{2}} P_{K}(k) \nonumber \\
    &\leq 2^{-\frac{\gamma}{2}}. \nonumber
\end{align}
Therefore
\begin{align}
    \mathbb P[ K \notin \mathcal L] \leq \beta+2^{-\frac{\gamma}{2}}.
\nonumber \end{align}
This proves Lemma \ref{boundprobsett}.
\end{proof}
\begin{lemma}
\label{boundprobsetd}
It holds that
\begin{align}
  \mathbb P \left[(K,Y^n)\in \mathcal D\right]  \geq 1-(\beta+2\times 2^{-\frac{\gamma}{2}}). \nonumber
\end{align}
\end{lemma}
\begin{proof}
We have
\begin{align}
    &\mathbb P \left[(K,Y^n)\in \mathcal D\right]\nonumber \\ &\geq \sum_{k \in \mathcal L} \mathbb P \left [(K,Y^n)\in \mathcal D|K=k\right]P_{K}(k) \nonumber \\
    &=\sum_{k \in \mathcal L}  \mathbb P\left[\log\frac{1}{P_{K|Y^n}(k|Y^n)} \geq \log\lvert\mathcal K\rvert-\gamma  \right] P_{K}(k) \nonumber \\
    &=\sum_{k \in \mathcal L}  \mathbb P\left[P_{K|Y^n}(k|Y^n)\leq 2^{\gamma-\log\lvert\mathcal K\rvert} \right] P_{K}(k)\nonumber \\
     &\geq\sum_{k \in \mathcal L}  \mathbb P\left[P_{K|Y^n}(k|Y^n)< 2^{\gamma-\log\lvert\mathcal K\rvert} \right] P_{K}(k)\nonumber \\
    &\overset{(a)}{\geq}\sum_{k\in \mathcal L}\left(1-\frac{P_{K}(k)}{2^{\gamma-\log\lvert \mathcal K\rvert}}\right) P_{K}(k) \nonumber \\
    &\overset{(b)}{\geq}\left(1-\frac{2^{\frac{\gamma}{2}-\log\lvert\mathcal K\rvert}}{2^{\gamma-\log\lvert\mathcal K\rvert}}\right) \sum_{k\in \mathcal L} P_{K}(k) \nonumber \\
    &=(1-2^{-\frac{\gamma}{2}})\mathbb P\left[ K \in \mathcal L\right] \nonumber \\
    &\overset{(c)}{\geq}(1-2^{-\frac{\gamma}{2}})\left(1-(\beta+2^{-\frac{\gamma}{2}})\right) \nonumber \\
    &=1-(\beta+2^{-\frac{\gamma}{2}})-2^{-\frac{\gamma}{2}}+2^{-\frac{\gamma}{2}}(\beta+2^{-\frac{\gamma}{2}}) \nonumber \\
    &\geq 1-(\beta+2\times 2^{-\frac{\gamma}{2}}), \nonumber
   \end{align}
  where $(a)$ follows from Markov's inequality since $P_{K}(k)=\mathbb E\left[P_{K|Y^n}(k|Y^n)\right],$ $(b)$ follows because for $k\in \mathcal L,$  we know that $P_{K}(k) \leq 2^{\frac{\gamma}{2}-\log\lvert\mathcal K\rvert},$ $(c)$ and $(d)$ follows from Lemma \ref{boundprobsett}.
  This proves Lemma \ref{boundprobsetd}.
\end{proof}

Define the sets
\begin{align}
     \mathcal S_{1} =\{ (x^n,z^n): \frac{1}{n} i(\Lambda(x^n);z^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon\},\nonumber
\end{align}
\begin{align}
    \mathcal S_{2}=\{(x^n,y^n,z^n): \Phi(x^n)=\Psi(y^n,z^n)   \}, \nonumber
\end{align}
and
\begin{align}
    \mathcal S_{3}=\{(x^n,y^n): (\Phi(x^n),y^n)\in \mathcal D\}. \nonumber
\end{align}

\begin{comment}
\begin{lemma}
\label{finitevariance}
\begin{align}
\sigma_{S}^2=\mathrm{var}(S)<\infty. \nonumber
\end{align}
\end{lemma}
\end{comment}
\begin{comment}
\begin{proof}
Define $P_{\mathrm{min}}= \underset{(x,y) \in \mathcal X\times \mathcal Y}{\min}\mathbb P\left[ X=x|Y=y\right]>0.$
We have
\begin{align}
    \mathrm{var}(S) 
    &\leq \mathbb E \left[ S^2\right] \nonumber \\
    &=\mathbb E \left[ \log^2\left(\frac{1}{\mathbb P\left[\Phi(X^n)|Y^n\right]}\right)  \right) \nonumber \\
    &\leq  \mathbb E \left[ \log^2\left(\frac{1}{\mathbb P\left[X^n|Y^n\right]}\right)  \right] \nonumber \\
    &= \mathbb E \left[ \log^2\left(\frac{1}{\mathbb P\left[X|Y\right]^n}\right)  \right] \nonumber \\
    &\leq \mathbb E \left[ \log^2\left(\frac{1}{{P_{\mathrm{min}}}^n}\right)  \right] \nonumber \\
    &=n^2\log^2\left(\frac{1}{{P_{\mathrm{min}}}} \right) \nonumber \\
    &<\infty \nonumber.
\end{align}
\end{proof}
Let $\gamma>0.$ Let $\epsilon(n)$ be any positive constant such that \begin{align} \mathbb P\left[\frac{1}{n}i(T^n;Z^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon(n) \right]> \frac{\sigma_S^2}{\sigma_S^2+n^2\gamma^2}.
\label{epsilonn}
\end{align}
Since $\frac{\sigma_S^2}{\sigma_S^2+n^2\gamma^2}<1$  and  since  $\mathbb P\left[\frac{1}{n}i(T^n;Z^n) \leq \underline{I}(\bs{T};\bs{Z})\right]=0,$ we know that an $\epsilon(n)>0$ satisfying \eqref{epsilonn} exists.  

Define
\begin{align}
    &\mathcal D_1 \nonumber \\
    &=\{ (x^n,y^n): H(K|Y^n) \leq \log\left(\frac{1}{\mathbb P\left[K=\Phi(x^n)|Y^n=y^n\right]}\right)+n\gamma\} \nonumber
\end{align}
and
\begin{align}
     &\mathcal D_2 \nonumber \\
    &=\{ (x^n,z^n): \frac{1}{n} i(\Lambda(x^n);z^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon(n)\}
\nonumber \end{align}
\end{comment}

Let $\mathcal S=\mathcal S_{1} \cap \mathcal S_{2} \cap \mathcal S_{3}.$ 
Inspired by \cite{strongconverse}, we change the probability measure by defining
\begin{align}
  P_{\tilde{X}^n,\tilde{Y}^n,\tilde{Z}^n}(x^n,y^n,z^n)=\frac{P_{X^n,Y^n,Z^n}(x^n,y^n,z^n)\mathbbm{1}\left[(x^n,y^n,z^n)\in \mathcal S  \right]}{\mathbb P \left[(X^n,Y^n,Z^n) \in \mathcal S\right]}, \nonumber
\end{align}
where $\mathbbm{1}[\cdot]$ is the indicator function.

Let $(\tilde{X}^n,\tilde{Y}^n,\tilde{Z}^n) \sim P_{\tilde{X}^n,\tilde{Y}^n,\tilde{Z}^n}.$
In order to show that $(\tilde{X}^n,\tilde{Y}^n,\tilde{Z}^n)$ is well-defined, we will show that $\mathbb P\left[(X^n,Y^n,Z^n)\in \mathcal S \right]>0$ in what follows.
\begin{lemma}
\label{probS}
It holds that
\begin{align*}
   \mathbb P \left[ (X^n,Y^n,Z^n)\in \mathcal S\right]>\frac{\alpha+\beta}{2}>0. \nonumber  
\end{align*}
\end{lemma}
\begin{proof}
We have
\begin{align}
    &\mathbb P\left[ (X^n,Y^n,Z^n) \in \mathcal S\right] \nonumber \\
    &\geq 1- \mathbb P\left[(X^n,Y^n) \notin \mathcal S_{3}\right]-\mathbb P\left[(X^n,Y^n,Z^n) \notin \mathcal S_{2}\right] - \mathbb P\left[(X^n,Z^n)\notin \mathcal S_{1}\right]
    \nonumber \\
   &= 1-\mathbb P\left[(K,Y^n)\notin\mathcal D\right]-\mathbb P\left[K\neq L\right] -\mathbb P\left[(X^n,Z^n)\notin \mathcal S_{1}\right]  \nonumber \\
   &\overset{(a)}{\geq} 1-(\beta+2\times 2^{-\frac{\gamma}{2}})-\alpha -\mathbb P\left[(X^n,Z^n)\notin \mathcal S_{1}\right] \nonumber \\
   &=1-(\beta+2\times 2^{-\frac{\gamma}{2}})-\alpha-\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right] \nonumber \\
   &=1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]-  2\times2^{-\frac{\gamma}{2}}\nonumber \\
   &\overset{(b)}{=}\frac{1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]}{2} \nonumber \\
   &\overset{(c)}{>}\frac{\alpha+\beta}{2}.
\nonumber \end{align}
where $(a)$ follows from Lemma \ref{boundprobsetd} and from \eqref{errorcorrelated}, $(b)$ follows because for $\gamma=2\log\left(\frac{4}{1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]}\right),$ we have
\begin{align}
    2\times2^{-\frac{\gamma}{2}}=\frac{1-\left[\alpha+\beta+\mathbb P\left[\frac{1}{n}i(T^n;Z^n) > \underline{I}(\bs{T};\bs{Z})+\epsilon \right]\right]}{2}
\nonumber \end{align}and $(c)$ follows from  \eqref{choiceepsilon}.




This proves Lemma \ref{probS}.
\end{proof}
Consider an execution of the protocol for input $(\tilde{X}^n,\tilde{Y}^n)\sim P_{\tilde{X}^n,\tilde{Y^n}}.$
Let $\tilde{K}=\Phi(\tilde{X}^n).$ Let $\tilde{T}^n=\Lambda(\tilde{X}^n)$ be the new channel input sequence. $\tilde{Z}^n$ is then its corresponding output sequence. We further define $\tilde{L}=\Psi(\tilde{Y}^n,\tilde{Z}^n).$ Here, $\tilde{K}$ is equal to $\tilde{L}$ with probability one. Furthermore, since for every $(x^n,y^n,z^n)\in \mathcal S,$ 
\begin{align}
      \frac{1}{n}i\left(\Lambda(x^n),z^n\right)\leq \underline{I}(\bs{T};\bs{Z})+\epsilon, \nonumber
\end{align}
we have
\begin{align}
    \mathbb E\left[ \frac{1}{n}i\left(\Lambda(\tilde{X}^n),\tilde{Z}^n\right)\right]\leq \underline{I}(\bs{T};\bs{Z})+\epsilon.
\nonumber \end{align}
Therefore
\begin{align}
    \frac{1}{n}I(\tilde{T}^n;\tilde{Z}^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon. \label{upperboundnewmutinf} \end{align}
\begin{lemma} It holds that
\label{upperboundlogcardinality}
\begin{align}
    \log \lvert \mathcal K \rvert  &\leq \log\frac{32}{ (\alpha+\beta)^3}+H(\tilde{K}|\tilde{Y}^n). \nonumber
\end{align}
\end{lemma}
\begin{proof}
For any $(k,y^n) \in \text{supp}(P_{\tilde{K},\tilde{Y}^n}),$ we have
\begin{align}
   \frac{P_{\tilde{K},\tilde{Y}^n}(k,y^n)}{P_{Y^n}(y^n)}\nonumber 
    &=\frac{1}{P_{Y^n}(y^n)}\sum_{\substack{x^n,z^n \\(x^n,y^n,z^n)\in \mathcal S \\ \Phi(x^n)=k}} P_{\tilde{X}^n,\tilde{Y}^n,\tilde{Z}^n}(x^n,y^n,z^n)\nonumber \\
    &=\frac{1}{P_{Y^n}(y^n)}\sum_{\substack{x^n,z^n \\(x^n,y^n,z^n)\in \mathcal S \\ \Phi(x^n)=k}} \frac{P_{X^n,Y^n,Z^n}(x^n,y^n,z^n)}{\mathbb P\left[(X^n,Y^n,Z^n)\in \mathcal S\right]} \nonumber \\
      &\leq \frac{P_{K,Y^n}(k,y^n)}{P_{Y^n}(y^n)\mathbb P\left[(X^n,Y^n,Z^n)\in \mathcal S\right]} \nonumber \\
       &= \frac{P_{K|Y^n}(k|y^n)}{\mathbb P\left[(X^n,Y^n,Z^n)\in \mathcal S\right]}  \nonumber\\
         &\overset{(a)}{\leq} \frac{2^{\gamma}}{\lvert \mathcal K \rvert \mathbb P\left[(X^n,Y^n,Z^n)\in \mathcal S\right]} \nonumber \\
    &\overset{(b)}{\leq} \frac{\left(\frac{4}{\alpha+\beta}\right)^2}{\lvert \mathcal K \rvert \frac{(\alpha+\beta)}{2}} \nonumber \\
    &=\frac{32}{\lvert \mathcal K \rvert (\alpha+\beta)^3},
\nonumber \end{align}
where $(a)$ follows because $(k,y^n)\in \mathcal D$ and $(b)$ follows from Lemma \ref{boundgamma} and from Lemma \ref{probS}.

Therefore for every $(k,y^n) \in \text{supp}(P_{\tilde{K},\tilde{Y}^n}),$ we have
\begin{align}
    \lvert \mathcal K \rvert \leq \frac{32}{ (\alpha+\beta)^3} \frac{1}{\frac{P_{\tilde{K},\tilde{Y}^n}(k,y^n)}{P_{Y^n}(y^n)}}. \nonumber
\end{align}
This implies that for any $(k,y^n) \in \text{supp}(P_{\tilde{K},\tilde{Y}^n}),$ we have
\begin{align}
\log\lvert \mathcal K \rvert &\leq \log\frac{32}{ (\alpha+\beta)^3}-\log\frac{P_{\tilde{K},\tilde{Y}^n}(k,y^n)}{P_{Y^n}(y^n)} \nonumber 
\end{align}
As a result, it follows that
\begin{align}
 \log \lvert \mathcal K \rvert  &\leq \log\frac{32}{ (\alpha+\beta)^3}+\underset{(k,y^n)\in \text{supp}(P_{\tilde{K},\tilde{Y}^n})}{\min}-\log\frac{P_{\tilde{K},\tilde{Y}^n}(k,y^n)}{P_{Y^n}(y^n)} \nonumber   
\end{align}
Now, it holds that
\begin{align}
    &\underset{(k,y^n)\in \text{supp}(P_{\tilde{K},\tilde{Y}^n})}{\min}-\log\frac{P_{\tilde{K},\tilde{Y}^n}(k,y^n)}{P_{Y^n}(y^n)} \nonumber \\ &\leq \mathbb E\left[-\log\frac{P_{\tilde{K},\tilde{Y}^n}(\tilde{K},\tilde{Y}^n)}{P_{Y^n}(\tilde{Y}^n)}\right] \nonumber \\ 
    &=\mathbb E\left[-\log P_{\tilde{K}|\tilde{Y}^n}(\tilde{K}|\tilde{Y}^n) \right]-\mathbb E\left[\log\frac{P_{\tilde{Y}^n}(\tilde{Y}^n)}{P_{Y^n}(\tilde{Y}^n)}\right]\nonumber \\
    &=H(\tilde{K}|\tilde{Y}^n)-D(P_{\tilde{Y}^n}||P_{Y^n}) \nonumber \\ \nonumber \\
    &\leq H(\tilde{K}|\tilde{Y}^n). \nonumber
\end{align}
It follows that
\begin{align}
\log \lvert \mathcal K \rvert  &\leq \log\frac{32}{ (\alpha+\beta)^3}+H(\tilde{K}|\tilde{Y}^n). \nonumber
\end{align}
This completes the proof of the lemma.
\end{proof}
Now, we continue with the converse proof. It holds using lemma \ref{upperboundlogcardinality} that
\begin{align}
   \frac{1}{n} H(K|Y^n) &\leq \frac{1}{n}\log \lvert \mathcal K \rvert\nonumber \\
   &\leq \frac{1}{n}H(\tilde{K}|\tilde{Y}^n)+\frac{1}{n}\log\frac{32}{ (\alpha+\beta)^3}.
\label{entropyentropytilde}
\end{align}

We have
\begin{equation}
\frac{1}{n}H(\tilde{K}|\tilde{Y}^{n})=\frac{1}{n}I(\tilde{K};\tilde{Z}^{n}|\tilde{Y}^{n})+\frac{1}{n}H(\tilde{K}|\tilde{Y}^{n},\tilde{Z}^{n}) \label{entropyKtilconditionedYtilde}
\end{equation}
On the one hand, it holds that
\begin{align} 
\frac{1}{n} I(\tilde{K};\tilde{Z}^{n}|\tilde{Y}^{n})&\leq \frac{1}{n} I(\tilde{X}^{n}\tilde{K};\tilde{Z}^{n}|\tilde{Y}^{n}) \nonumber\\
& \overset{(a)}{\leq }\frac{1}{n} I(\tilde{T}^n;\tilde{Z}^n|\tilde{Y}^{n})  \nonumber \\
& =  \frac{1}{n} H(\tilde{Z}^n|\tilde{Y}^{n})-\frac{1}{n}  H(\tilde{Z}^n|\tilde{T}^n,\tilde{Y}^{n}) \nonumber \\
& \overset{(b)}{=} \frac{1}{n}  H(\tilde{Z}^n|\tilde{Y}^{n})-\frac{1}{n}  H(\tilde{Z}^n|\tilde{T}^n) \nonumber \\
& \overset{(c)}{\leq }   \frac{1}{n} H(\tilde{Z}^n)-\frac{1}{n}  H(\tilde{Z}^n|\tilde{T}^n) \nonumber \\
& = \frac{1}{n} I(\tilde{T}^n;\tilde{Z}^n)  \nonumber \\
&\overset{(d)}{\leq} \underline{I}(\bs{T};\bs{Z})+\epsilon,
\nonumber
\end{align}
where $(a)$ follows from the Data Processing Inequality because $\tilde{Y}^{n}\circlearrow{\tilde{X}^{n}\tilde{K}}\circlearrow{\tilde{T}^n}\circlearrow{\tilde{Z}^{n}}$ forms a Markov chain, $(b)$ follows because $\tilde{Y}^{n}\circlearrow{\tilde{X}^{n}\tilde{K}}\circlearrow{\tilde{T}^n}\circlearrow{\tilde{Z}^{n}}$ forms a Markov chain, $(c)$ follows because conditioning does not increase entropy and $(d)$ follows from \eqref{upperboundnewmutinf}.

On the other hand, since $\tilde{K}$ is equal to $\tilde{L}=\Psi(\tilde{Y}^n,\tilde{Z}^n)$ with probability one, it holds that
$$H(\tilde{K}|\tilde{Y}^n,\tilde{Z}^n)=0.$$ 

As a result, we have using  \eqref{entropyKtilconditionedYtilde}
\begin{align}
    \frac{1}{n}H(\tilde{K}|\tilde{Y}^n)&\leq \underline{I}(\bs{T};\bs{Z})+\epsilon. \nonumber 
\end{align}


From \eqref{entropyentropytilde}, it follows that for $\alpha+\beta<\frac{1}{2}$
\begin{align}
    \frac{1}{n}H(K|Y^n)\leq \underline{I}(\bs{T};\bs{Z})+\epsilon+\frac{1}{n}\log\frac{32}{ (\alpha+\beta)^3}. \nonumber
\end{align}



Since $\alpha,\beta>0$ can be chosen arbitrarily, we can choose them to be arbitrarily small. It follows that $ 2(\alpha+\beta)$ is arbitrarily small. From the definition of $\underline{I}(\bs{T};\bs{Z}),$ we know that 
 for any $\zeta>0,$
 \begin{align}
    0< \underset{n\rightarrow\infty}{\lim}\mathbb P\left[\frac{1}{n}i(T^n;Z^n) \leq \underline{I}(\bs{T};\bs{Z})+\zeta \right]. \nonumber
 \end{align}
 Therefore, by choosing $\alpha$ and $\beta$ to be arbitrarily small positive constants, we can choose an arbitrarily small $\epsilon>0$ satisfying 
  \begin{align}
      2(\alpha+\beta)< \underset{n\rightarrow\infty}{\lim}\mathbb P\left[\frac{1}{n}i(T^n;Z^n) \leq \underline{I}(\bs{T};\bs{Z})+\epsilon \right]. \nonumber
 \end{align}

 As a result, 
 \begin{align}
     \frac{H(K|Y^n)}{n}\leq \underline{I}(\bs{T};\bs{Z})+\alpha'(n) \nonumber
 \end{align}
for some $\alpha'(n),$ where $\underset{n\rightarrow \infty}{\lim}\alpha'(n)$ can be made arbitrarily small for $\alpha,\beta,\epsilon$ chosen arbitrarily small.
 From Theorem \ref{generalcapacityformula}, we know that
 \begin{align}
     \underline{I}(\bs{T};\bs{Z})\leq C(W).\nonumber
 \end{align}
We deduce then that
  \begin{align}
     \frac{H(K|Y^n)}{n}\leq C(W)+\alpha'(n). \nonumber
 \end{align}
 
Since the joint distribution of $X_{J}$ and $Y_{J}$ is equal to $P_{XY}$, $\frac{H(K)}{n}$ is upper-bounded by $I(U;X)$ subject to $I(U;X)-I(U;Y) \leq C(W) + \alpha'(n)$ with $U$ satisfying $U \circlearrow{X} \circlearrow{Y}$. As a result, it holds that
\begin{align}
    \frac{H(K)}{n} \leq \underset{ \substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq C(W)+\alpha'(n)}}}}{\max} I(U;X).
    \nonumber
\end{align}
\section{Direct Proof of Theorem \ref{main theorem}}
\label{directpart}
The proof of the direct part is rather standard. It suffices to  extend the UCR generation scheme provided in \cite{part2} to arbitrary single-user channels.
\subsubsection{If $ C(W)=0$} In this case, no communication over the channel is possible. Therefore, it follows from \cite{part2} that
    \begin{align}
C_{UCR}(P_{XY},W) &= 
  \underset{ \substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq 0}}}}{\max} I(U;X)  \nonumber \\
  &=  \underset{ \substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq C(W)}}}}{\max} I(U;X).  \nonumber
\end{align}
\subsubsection{If $ C(W)>0$} We extend the coding scheme provided in \cite{part2} to arbitary single-user channels. By continuity, it suffices to show that 
$$ \underset{ \substack{U \\{\substack{U \circlearrow{X} \circlearrow{Y}\\ I(U;X)-I(U;Y) \leq C'}}}}{\max} I(U;X)  $$ is an achievable  UCR rate for every $C'<C(W).$
Let $U$ be a random variable satisfying $U \circlearrow{X} \circlearrow{Y}$ and $I(U;X)-I(U;Y) \leq C'$. Let the maximum error probability $\alpha>0.$ Let $\delta,\beta>0.$ We are going to show that $H=I(U;X)$ is an achievable UCR rate. Without loss of generality, assume that the distribution of $U$ is a possible type for block-length $n$.
For some $\mu>0,$ we let
{{\begin{align}
N_{1}&=\lfloor 2^{n[I(U;X)-I(U;Y)+3\mu]} \rfloor \nonumber\\
N_{2}&=\lfloor 2^{n[I(U;Y)-2\mu]}\rfloor. \nonumber
\end{align}}}For each pair $(i,j)$ with $1\leq i \leq N_{1}$ and $1\leq j \leq N_{2}$, we define a random sequence $\bs{U}_{i,j}\in\mathcal{U}^n$ of type $P_{U}$. Let $\mathbf M=\bs{U}_{1,1},\hdots, \bs{U}_{N_{1},N_{2}}$  be the joint random variable of all $\bs{U}_{i,j}s.$ We further define the following two sets which depend on $\mathbf M$:
\begin{align}
    S_{1}(\mathbf M)&=\{(\bs{x},\bs{y}):(\Phi(\bs{x}),\bs{x},\bs{y}) \in \mathcal{T}_{U,X,Y}^{n}\} \nonumber
\end{align} and
\begin{align}
    S_{2}(\mathbf M)=\{(\bs{x},\bs{y}):(\bs{x},\bs{y}) \in S_{1}(\mathbf M) \ \text{s.t.} \ \exists \ \bs{U}_{i,\ell}\neq\bs{U}_{i,j}=\Phi(\bs{x}) \nonumber \\   \text{jointly} \ UY\text{-typical with} \ \bs{y} \ (\text{with the same first index} \ i)
\}.\nonumber
\end{align}
It is proved in \cite{part2} that
\begin{align}
    \mathbb{E}_{\mathbf M}\left[ \mathbb P\left[(X^n,Y^n)\notin  S_{1}(\mathbf M)\right]+\mathbb P\left[(X^n,Y^n)\in  S_{2}(\mathbf M)\right]\right]\leq \zeta(n),
    \label{averagebeta}
\end{align}
where $\zeta(n) \leq \frac{\alpha}{2}$ for sufficiently large $n$. 
We choose a realization $\mathbf m=\bs{u}_{1,1},\hdots, \bs{u}_{N_1,N_2}$ satisfying:
\begin{align}
\mathbb P\left[(X^n,Y^n)\notin  S_{1}(\mathbf m)\right]+\mathbb P\left[(X^n,Y^n)\in  S_{2}(\mathbf m)\right]\leq \beta.
\nonumber \end{align} 
From \eqref{averagebeta}, we know that such a realization exists.
We assume that each $\bs{u}_{i,j}, i=1\hdots N_1, j=1\hdots N_2,$  is known to both terminals.  
This means that  $N_{1}$ codebooks $C_{i}, 1\leq i \leq N_{1}$, are known to both terminals, where each codebook contains $N_{2}$ sequences, $ \bs{u}_{i,j}, \ j=1,\hdots, N_2$. 

Let $\bs{x}$ be any realization of $X^n$ and $\bs{y}$ be any realization of $Y^n.$
\begin{comment}
It holds for every $X$-typical $\bs{x}$ that $$\mathbb P[\exists (i,j) \ \text{s.t} \ \bs{U}_{ij} \in \mathcal{T}_{U|X}^{n}\left(\bs{x}\right)|X^{n}=\bs{x}]\geq 1-2^{-2^{nc'}},$$ for a suitable $c'>0,$ as in the proof of  Theorem 4.1 in \cite{part2}. 
\end{comment}
 Let $\Phi(\bs{x})=\bs{u}_{ij}$, if $\bs{u}_{ij}$ is jointly $UX$-typical with $\bs{x}$ (either one if there are several).
 Let $f_1(\bs{x})=i$ if $\Phi(\bs{x}) \in C_{i}$.  If no such a $\bs{u}_{i,j}$ exists, then $f_1(\bs{x})=N_1+1$ and $\Phi(\bs{x})$ is set to a constant sequence $\bs{u}_0$ different from all the ${\bs{u}_{ij}}'s$, jointly $UX$-typical with none of the realizations of $X^n$ and known to both terminals.
  \begin{remark}
 It holds that  $$S_{3}^{c}(\mathbf m)\subseteq S_{1}^{c}(\mathbf m),$$
 where
 \begin{align}
     S_{3}(\mathbf m)=\{\bs{x}: \exists (i,j) \ \text{s.t} \ (\bs{u}_{ij},\bs{x}) \in \mathcal{T}_{U,X}^{n}\}. \nonumber
 \end{align}
 \end{remark}
  Since $ C'<C(W)$, we choose $\mu$ to be sufficiently small such that
      \begin{align}
     \frac{\log \lVert f_1 \rVert}{n}&=\frac{\log(N_1+1)}{n} \nonumber \\
     &\leq C(W)-\mu',
     \label{inequalitylogfSISO}
      \end{align}
for some $\mu'>0,$
 The message $i^\star=f_1(\bs{x})$, with $i^\star\in\{1,\hdots,N_1+1\}$, is encoded to a sequence $\bs{t}$ using a code sequence $(\Gamma^\star_n)_{n=1}^{\infty}$ with rate $\frac{\log \lvert \Gamma^\star_n \rvert}{n}=\frac{\log \lVert f_1 \rVert}{n}$ satisfying \eqref{inequalitylogfSISO}
 and with error probability $e(\Gamma^\star_n)$ satisfying for sufficiently large $n$
 \begin{align}
     e(\Gamma^\star_n) \leq \theta 
 \nonumber \end{align}
where $\theta$ is  a positive constant satisfying $\theta\leq \frac{\alpha}{2}.$ 
  \color{black}
  Here, $\lVert f_1 \rVert$ refers to the cardinality of the set of messages $\{i^\star:i^\star=1,\hdots,N_1+1\}
$.
  From the definition of the transmission capacity, we know that such a code sequence exists. The sequence $\bs{t}$ is sent over the single-user channel. Let $\bs{z}$ be the channel output sequence. Terminal $B$ decodes the message $\tilde{i}^\star$ from the knowledge of $\bs{z}.$
Let $\Psi(\bs{y},\bs{z})=\bs{u}_{\tilde{i}^\star,j}$ if $\bs{u}_{\tilde{i}^\star,j}$ and $\bs{y}$ are jointly $UY$-typical . If there is no such a $\bs{u}_{\tilde{i}^\star,j}$ or there are several, we set $\Psi(\bs{y},\bs{z})=\bs{u}_0$ (since $K$ and $L$ must have the same alphabet).
Now, we are going to show that the requirements in $\eqref{errorcorrelated},$  $\eqref{cardinalitycorrelated},$ \eqref{uniformity} and $\eqref{ratecorrelated}$ are satisfied.
Clearly, (\ref{cardinalitycorrelated}) is satisfied  for $c=H(X)+\mu+1$  because
{{\begin{align}
|\mathcal{K}|&=N_1 N_2+1 \nonumber \\
             &\leq  2^{n\left[I(U;X)+\mu\right]}+1 \nonumber \\
             &\leq2^{n\left[H(X)+\mu+1\right]}.\nonumber
\end{align}}}We define next for any $(i,j)\in \{1,\hdots,n\}\times\{1,\hdots,n\}$  the set
$$\mathcal R=\{ \bs{x}\in\mathcal{X}^{n} \ \text{s.t.} \ (\bs{u}_{i,j},\bs{x}) \ \text{jointly} \ UX\text{-typical}\}.$$
Then, it holds that 
\begin{align}
\mathbb P[K=\bs{u}_{i,j}] &=\sum_{\bs{x}\in\mathcal R}\mathbb P[K=\bs{u}_{i,j}|X^n=\bs{x}]P_{X}^n(\bs{x}) +\sum_{\bs{x}\in\mathcal R^c}\mathbb P[K=\bs{u}_{i,j}|X^n=\bs{x}]P_{X}^n(\bs{x}) \nonumber \\
&\overset{(\RM{1})}{=}\sum_{\bs{x}\in\mathcal R}\mathbb P[K=\bs{u}_{i,j}|X^n=\bs{x}]P_{X}^n(\bs{x}) \nonumber \\
&\leq \sum_{\bs{x}\in\mathcal R}P_{X}^n(\bs{x}) \nonumber \\
&=P_{X}^{n}(\{\bs{x}: (\bs{u}_{i,j},\bs{x}) \ \text{jointly} \ UX\text{-typical}\}) \nonumber\\
& = 2^{-nI(U;X)-\kappa(n)}, \nonumber
\end{align}
for some $\kappa(n)>0$ with $\underset{n\rightarrow \infty}{\lim} \frac{\kappa(n)}{n}=0$,
where (\RM{1}) follows because for  $(\bs{u}_{i,j},\mathbf{x})$ being not jointly $UX$-typical, we have $\mathbb P[K=\bs{u}_{i,j}|X^n=\bs{x}]=0.$ This yields
{{\begin{align}
H(K)\geq nI(U;X)-\kappa'(n)
\nonumber \end{align}}}
for some $\kappa'(n)>0$ with $\underset{n\rightarrow \infty}{\lim} \frac{\kappa'(n)}{n}=0.$
Therefore, for sufficiently large $n,$ it holds that
\begin{align}
    \frac{H(K)}{n}>H-\delta. \nonumber
\end{align}
Thus, (\ref{ratecorrelated}) is satisfied.
Now, we have
\begin{align}
    d(P_{K},P_{\text{unif}})=\frac{1}{2}\sum_{k\in \mathcal K}\lvert P_{K}(k)-\frac{1}{\lvert \mathcal K \rvert} \rvert \leq \kappa''(n)
\nonumber \end{align}
for some $\kappa''(n)>0$ with $\underset{n\rightarrow\infty}{\lim} \kappa''(n)=0.$ Therefore, for sufficiently large $n,$ $\kappa''(n)\leq \beta.$ This proves \eqref{uniformity}.

 Now, it remains to prove that \eqref{errorcorrelated} is satisfied. For this purpose, we define the following event:
\begin{align}
    \mathcal{D}_{\mathbf m}= ``\Phi(X^n) \ \text{is equal to none of the} \  {\bs{u}_{i,j}}'s". \nonumber
\end{align}
We denote its complement by $\mathcal D_{\mathbf m}^{c}.$
We further define $I^\star=f_1(X^n)$ to be the random message generated by Terminal $A$ and  $\tilde{I}^\star$ to be the random message decoded by Terminal $B$. 
We have
\begin{align}
    \mathbb P[K\neq L] \nonumber &=\mathbb P[K\neq L|I^\star=\tilde{I}^\star]\mathbb P[I^\star=\tilde{I}^\star] + \mathbb P[K\neq L|I^\star\neq \tilde{I}^\star]\mathbb P[I^\star\neq\tilde{I}^\star] \nonumber \\
        &\leq \mathbb P[K\neq L|I^\star=\tilde{I}^\star]+ \mathbb P[I^\star\neq\tilde{I}^\star].\nonumber
\end{align}
Here,
\begin{align}
    \mathbb P[K\neq L|I^\star=\tilde{I}^\star] 
   &= \mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}]\mathbb P[\mathcal{D}_{\mathbf m}|I^\star=\tilde{I}^\star] + \mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}^c]\mathbb P[\mathcal{D}_{\mathbf m}^c|I^\star=\tilde{I}^\star] \nonumber \\
   &\overset{(\RM{1})}{=}\mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}^c]\mathbb P[\mathcal{D}_{\mathbf m}^c|I^\star=\tilde{I}^\star] \nonumber \\
   &\leq \mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}^c],\nonumber
\end{align}
where $(\RM{1})$ follows from $\mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}]=0,$ since conditioned on  $I^\star=\tilde{I}^\star$ and $\mathcal{D}_{\mathbf m}$, we know that $K$ and $L$ are both equal to $\bs{u}_0$.
It follows that
\begin{align}
    \mathbb P[K\neq L] 
    &\leq \mathbb P[K\neq L|I^\star=\tilde{I}^\star,\mathcal{D}_{\mathbf m}^c]+ \mathbb P[I^\star\neq\tilde{I}^\star] \nonumber \\
    &\leq \mathbb P\left[(X^n,Y^n)\in  S_{1}^{c}(\mathbf m)\cup S_{2}(\mathbf m)\right]+\mathbb P[I^\star\neq\tilde{I}^\star] \nonumber \\
    &\overset{(a)}{=}\mathbb P\left[(X^n,Y^n)\notin  S_{1}(\mathbf m)\right]+\mathbb P\left[(X^n,Y^n)\in  S_{2}(\mathbf m)\right] +\mathbb P[I^\star\neq\tilde{I}^\star] \nonumber \\
    &\leq \zeta(n)+ \mathbb P[I^\star\neq\tilde{I}^\star],\nonumber\\
    &\leq \zeta(n)+\theta \nonumber \\
    &\leq \alpha.
\nonumber \end{align}
where $(a)$ follows because $S_{1}^{c}(\mathbf m)$ and $S_{2}(\mathbf m)$ are disjoint. 
This completes the direct proof of Theorem .

\section{Conclusion}
\label{conclusion}
In our work, we studied the problem of UCR generation over arbitrary point-to-point channels. We established a general expression for the UCR capacity that holds for arbitrary single-user channels by making use of the transmission capacity formula elaborated  in \cite{verduhan}.  As a future work, it would be interesting to investigate the problem of CR generation in the multi-user setting.


