text:
\section{Introduction}
As part of the Internet of Things (IoT), sensor applications are rapidly increasing, thanks to lower cost and better performance of sensors.
One of the major  theoretical challenges in this respect is sensor networks with multiple sensors  collecting correlated data, which they communicate to one or multiple decision centers. Of special practical and theoretical interest  is to study the tradeoff between the quality of the decisions taken at the centers and  the required  communication resources. In this work, following the approach in  \cite{Csiszar86, Han}, we consider problems where decision centers have to decide on a binary hypothesis $\mathcal{H}=0$ or $\mathcal{H}=1$ that determines the underlying joint probability mass function (pmf) of all the terminals' observations. Our goal is to characterize the set of possible \emph{type-II error exponents} (i.e., the error exponent in deciding $\hat{\mathcal{H}}=0$ when in fact $\mathcal{H}=1$) as a function of the available communication rates such that the \emph{type-I error probabilities} (i.e., error probabilities of deciding  $\hat{\mathcal{H}}=1$ when in fact $\mathcal{H}=0$) vanish as the lengths of the observations grow.
Previous works on this \emph{exponent-rate region}  considered  communication scenarios over dedicated noise-free links from one or many transmitters to a single decision center \cite{Csiszar86,Amari,Wagner}  or from a single transmitter to two decision centers \cite{Michele, Roy,PierreISIT}. The hypothesis testing problem from a signal processing perspective has been studied in several works \cite{Varshney, Veer, Tara, Poor,Nanda}. Recently, simple interactive communication scenarios were also considered \cite{Lai1,Lai2,Kim}, as well as hypothesis testing over \emph{noisy} communication channels \cite{Gunduz,Michele,Sadaf-IT}.  All these distributed hypothesis testing problems are open in the general case; exact solutions have only been found for instances of ``testing against independence'' \cite{Csiszar86} and of ``testing against conditional independence'' \cite{Wagner}. ``Testing against independence'' refers to a scenario where the observations' joint pmf under $\mathcal{H}=1$ is the product of the marginal pmfs under $\mathcal{H}=0$, and ``testing against conditional independence'' refers to a scenario where this independence holds only conditional on some sub-sequence that is observed at the receiver and that has the same joint distribution with the sensor's observations under both hypotheses.

The focus of this paper is on the \emph{two-hop network} depicted in Fig.~\ref{cascade}. We model a situation with three sensors and two decision centers. The first terminal (the transmitter) models a simple sensor that observes an $n$-length sequence $X^n$. The second terminal (the relay) includes both a sensor observing the $n$-length sequence $Y^n$ and a decision center which produces the guess $\hat{\mathcal{H}}_y\in\{0,1\}$. Similarly, the third terminal (the receiver) includes a sensor observing $Z^n$ and a decision center producing the guess  $\hat{\mathcal{H}}_z\in\{0,1\}$. Communication is directed and in two stages. The transmitter communicates directly with the relay over a noise-free link of rate $R>0$, but it cannot directly communicate with the receiver, e.g.,  because the receiver is too far away. Such a restriction is particularly relevant for modern IoT applications where sensors are desired to consume very little energy so as to last for decades without the batteries being replaced.  On the other hand, the receiver is assumed  to be sufficiently close to the relay so that the relay  can communicate directly with it over a  noise-free link of rate $T>0$. The task of the relay is not only to communicate information about its own observation to the receiver but also to \emph{process and forward} information that it receives from the transmitter. Two-hop networks have previously been studied in information theory for source coding or coordination. These problems are open in general. Solutions to special cases were presented in \cite{Yamamoto,CuffSu, Diggavi,Cuff-coordination, Tandon, Chia,Weissman,Ahmadi}.
	\begin{figure}[t]
		\centering
		\includegraphics[scale=0.27]{cascade_new-eps-converted-to.pdf}
		\caption{Hypothesis testing over a single-relay multi-hop channel}
		\label{cascade}
	\end{figure}

	In this paper, we propose two coding and testing schemes for binary hypothesis testing over the two-hop relay network. The two schemes apply two different
		 source coding schemes  for the two-hop relay network to convey quantization information about the distributed observations to the relay and the receiver, and combine these schemes with
		  a \emph{unanimous decision-forwarding} strategy. In this latter strategy, each of the terminals tests whether its reconstructed source sequences are jointly typical with its own observation under the null hypothesis $\mathcal{H}=0$. If the test is positive and the
	preceding terminals have also decided on $\hat{\mathcal{H}}=0$, then the terminal declares this null hypothesis $\hat{\mathcal{H}}=0$. Otherwise it declares the alternative hypothesis $\hat{\mathcal{H}}=1$. In both cases, it forwards its decision to the  next terminal.

	We characterize the relay and the receiver type-II error exponents  achieved by our schemes. Our  first scheme employs source coding without binning, which allows for a relatively simple  characterization of the achieved exponents. Our  second scheme employs source coding with binning and achieves larger exponents in some cases. However, with binning, the error exponent for $\hat{\mathcal{H}}_y$ is characterized by two competing exponents  and the exponent for $\hat{\mathcal{H}}_z$ by four competing exponents. They are thus more complicated to evaluate.

	In the  second part of the manuscript, we focus on two {cases}: the first is where $X^n \to Y^n \to Z^n$ forms a Markov chain under both hypotheses, and the second is where $X^n \to Z^n \to Y^n$ forms a Markov chain under both hypotheses. The first case models an extreme situation where  the relay lies in between the transmitter and the receiver, and thus the signals at the sensor and the receiver are conditionally independent given the signal at the relay. In such a situation, the two-hop network models, for example, short-range wireless communication where the sensor's signal only reaches the relay but not the more distant receiver. The second case models a situation
 where the receiver lies in between the sensor and the relay, and thus the signals at the transmitter and the relay are conditionally independent given the signal at the receiver. In such a situation,  the two-hop network models, for example, communication in a cellular system where  the relay is a powerful {base station} and all communication goes through this {base station}.

 We show that, in the first case where $X^n \to Y^n \to Z^n$, our schemes simplify considerably in the sense that the source coding scheme for the two-hop relay network  decouples into two independent point-to-point source coding schemes. In other words, it suffices to send quantization information about $X^n$ from the transmitter to the relay and, independently thereof,  to send quantization information about  $Y^n$ from the relay to the receiver (while also employing unanimous decision-forwarding) This contrasts the general scheme where the relay combines the quantization information about $X^n$ with its own observation $Y^n$ to create some kind of jointly processed quantization information to send to the receiver. The receiver error exponent achieved by  the simplified scheme equals the sum of the exponent at the relay and the exponent achieved over the point-to-point link from the relay to the receiver, but, to compute the second exponent, we modify the pmf of the relay's observation under $\mathcal{H}=1$ to being the same as its pmf under $\mathcal{H}=0$. These simplified expressions are proved to be optimal in different special cases of testing against independence (achieved without binning) and testing against conditional independence (with binning). The focus of this paper is on \emph{weak converses} where the type-I errors are also required to vanish asymptotically as $n\to \infty$. The existence of a \emph{strong converse} for one of these special cases, i.e., a proof that the same exponents are optimal also when type-I error probability  $\epsilon>0$ is tolerated,  was recently  proved in \cite{Tan}.

	For the second case where $X^n\to Z^n \to Y^n$, we present optimality results (in the weak converse sense) for two special cases. In the first special case, $P_{YZ}$ is same under both hypothesis, so $Y^n$ by itself is of no interest to the receiver. For rates $T\ge R$, the optimal strategy is for the relay to ignore its own observation and simply forward the transmitter's message to the receiver. Interestingly, this simple forwarding strategy can become suboptimal when $T<R$, because then the relay can act as a ``coordinator'' to reduce the communication rate $T$ to the receiver. We present an example where the relay's own observation $Y^n$ allows the relay to extract the relevant portion of $X^n$, and thus to reduce the required rate to the receiver $T$. In the second special case, $P_{XZ}$ is same under both hypothesis, and for sufficiently large $T$ the optimal strategy for the relay is to ignore all communication from the transmitter. Again, using an example, we show that for small $T$ the transmitter can be useful by playing the role of a coordinator who reveals to the relay which portions of $Y^n$ are  relevant to the  receiver.

	Lastly, as a side-result, we also present a detailed analysis of the Shimokawa-Han-Amari \cite{Amari} coding and testing scheme with binning for the point-to-point hypothesis testing problem. Previously this analysis has only appeared in Japanese \cite{Japanese}.

We conclude this introduction with remarks on notation and an outline of the paper.

\subsection{Notation}
We mostly follow the notation in \cite{ElGamal}.  Random variables are denoted by capital letters, e.g., $X,$ $Y,$ and their realizations by lower-case letters, e.g., $x,$ $y$.  Script symbols  such as $\mathcal{X}$ and $\mathcal{Y}$ stand for alphabets of  random variables, and $\mathcal{X}^n$ and $\mathcal{Y}^n$ for the corresponding $n$-fold Cartesian products.  Sequences of random variables $(X_i,...,X_j)$ and realizations $(x_i,\ldots, x_j)$ are  abbreviated by $X_i^j$ and $x_{i}^j$.  When $i=1$, then we also use $X^j$ and $x^j$ instead of $X_1^j$ and $x_{1}^j$.

Generally, we write the probability mass function (pmf) of a discrete random variable $X$  as $P_X$; but we use $Q_X$ to indicate the pmf under hypothesis $\mathcal{H}=1$ when it is different from the pmf under $\mathcal{H}=0$. The conditional pmf of $X$ given $Y$  is written as  $P_{X|Y}$ (or as $Q_{X|Y}$ when $\mathcal{H}=1$). The distributions of $X^n$, $Y^n$ and $(X^n,Y^n)$ under the same hypothesis are denoted by $P_{X^n}$, $P_{Y^n}$ and $P_{X^nY^n}$, respectively. The notation $P_{XY}^n$ denotes the $n$-fold product distribution, i.e.,
 for every $(x^n,y^n)\in\mathcal{X}^n\times \mathcal{Y}^n$, we have:
\begin{align}
P_{XY}^n(x^n,y^n)=\prod_{i=1}^n P_{XY}(x_i,y_i).
\end{align}

The term   $D(P\| Q)$ stands for  the Kullback-Leibler (KL) divergence between two pmfs $P$ and $Q$ over the same alphabet.
We use $\textnormal{tp}(\cdot)$ to denote the \emph{joint type} of a tuple.  For a joint type $\pi_{ABC}$ over alphabet $\mathcal{A}\times \mathcal{B}\times \mathcal{C}$, we denote by $I_{\pi_{ABC}}(A;B|C)$ the mutual information assuming that the random triple $(A,B,C)$ has  pmf  $\pi_{ABC}$; similarly for the entropy $H_{\pi_{ABC}}(A)$ and the conditional entropy $H_{\pi_{ABC}} (A|B)$. Sometimes we abbreviate $\pi_{ABC}$ by $\pi$. Also, when $\pi_{ABC}$ has been defined and is clear from the context, we write $\pi_{A}$ or $\pi_{AB}$ for the corresponding subtypes. When the type $\pi_{ABC}$ coincides with the actual pmf of a triple $(A,B,C)$, we  omit the subscript and simply write $H(A)$, $H(A|B)$, and $I(A;B|C)$.

For a given $P_X$ and a constant $\mu>0$, the set of sequences with the same type $P_X$ is denoted by $\mathcal{T}^n(P_X)$. We use  $\mathcal{T}_{\mu}^n(P_X)$ to denote the set of \emph{$\mu$-typical sequences} in $\mathcal{X}^n$:
\begin{equation}\label{eq:typical}
\mathcal{T}_{\mu}^n(P_X)=\Bigg\{x^n\colon \;\bigg| \frac{ | \{i\colon x_i=x\}|}{n}-P_X(x)\bigg|\leq \mu P_X(x), \quad\forall x\in\mathcal{X}\Bigg\},
\end{equation}
where $|\{i\colon x_i=x\}|$ is the number of positions where the sequence $x^n$ equals  $x$.
Similarly,   $\mathcal{T}_{\mu}^n(P_{XY})$ stands for the set of \emph{jointly $\mu$-typical sequences} whose definition is as in \eqref{eq:typical} with $x$ replaced by $(x,y)$.

The expectation operator is written as $\mathbb{E}[\cdot]$. The notation $\mathcal{U}\{a,\ldots, b\}$ is used to indicate a uniform distribution over the set $\{a,\ldots, b\}$; for the uniform distribution over $\{0,1\}$ we also use $\mathcal{B}(1/2)$.
The $\log$ function is  taken with base $2$. Finally, we abbreviate left-hand side and right-hand side by LHS and RHS.

\subsection{Paper Outline} The remainder of the paper is organized as follows.
	Section~\ref{seccascade} presents the problem description. Section~\ref{sec:no_binning}  presents a coding and testing scheme without binning and the exponent region it achieves.  Section~\ref{sec:binning} presents an improved scheme employing binning and the corresponding achievable exponent region. Sections~\ref{sec:MarkovXYZ}  and \ref{sec:MarkovXZY} study the proposed achievable regions when the Markov chains $X^n \to Y^n \to Z^n$ and $X^n \to Z^n \to Y^n$ hold, respectively.   The paper is concluded in Section~\ref{sec:conclusion} and by technical appendices.

\section{Detailed Problem Description}\label{seccascade}

Consider the multi-hop hypothesis testing problem with three terminals in Fig.~\ref{cascade}. The first terminal in the system, the \emph{transmitter},  observes the sequence $X^n$, the second terminal, the \emph{relay}, observes the sequence $Y^n$, and the third terminal, the \emph{receiver}, observes the sequence $Z^n$.  Under the null hypothesis
\begin{align}
\mathcal{H}=0\colon \quad (X^n,Y^n,Z^n)\sim \text{i.i.d.}\; P_{XYZ},
\end{align}
whereas under the alternative hypothesis
\begin{align}
\mathcal{H}=1\colon \quad (X^n,Y^n,Z^n)\sim \text{i.i.d.}\; Q_{XYZ},
\end{align}
for two given pmfs $P_{XYZ}$ and $Q_{XYZ}$.

The problem encompasses a noise-free bit-pipe of rate $R$ from the transmitter to the relay and a noise-free bit pipe of rate $T$ from the relay to the receiver. That means, after observing $X^n$, the transmitter computes the message $M=\phi^{(n)}(X^n)$ using a possibly stochastic encoding function $\phi^{(n)}\colon \mathcal{X}^n\to \{0,...,\lfloor 2^{nR}\rfloor\}$ and sends it to the relay. The relay, after observing $Y^n$ and receiving $M$, computes the message   $B=\phi_y^{(n)}(M,Y^n)$ using  a possibly  stochastic encoding function
$\phi_y^{(n)}\colon\mathcal{Y}^n\times \{0,...,\lfloor 2^{nR}\rfloor \}\to \{0,...,\lfloor 2^{nT}\rfloor\}$ and sends it to the receiver.

The goal of the communication is that, based on their own observations and the received messages, the relay and the receiver can decide  on the hypothesis $\mathcal{H}$.
The relay thus produces  the guess
\begin{align}
\hat{\mathcal{H}}_y=g_y^{(n)}(Y^n,M)
\end{align}
using a guessing function $g_y^{(n)}\colon\mathcal{Y}^n\times \{0,....,\lfloor 2^{nR}\rfloor\}\to \{0,1\}$,
and the receiver produces the guess
\begin{align}
\hat{\mathcal{H}}_z=g_z^{(n)}(Z^n,B)
\end{align}
using a guessing function $g_z^{(n)}\colon\mathcal{Z}^n\times \{0,...,\lfloor 2^{nT}\rfloor \}\to \{0,1\}$.

\begin{definition}\label{cascadedef}
	For each $\epsilon \in (0,1)$, we say that the exponent-rate tuple $(\eta,\theta,R, T)$ is $\epsilon$-achievable if there exists a sequence of encoding and decoding functions $(\phi^{(n)},\phi_y^{(n)},g_y^{(n)},g_z^{(n)})$, $n=1,2,\ldots$, such that the corresponding sequences of type-I  and type-II error probabilities at the relay
	\begin{align}
	\alpha_{y,n}&:{=} \Pr[\hat{\mathcal{H}}_y=1|\mathcal{H}=0],\\
	\beta_{y,n}&:{=} \Pr[\hat{\mathcal{H}}_y=0|\mathcal{H}=1],
	\end{align}
	and at the receiver
	\begin{align}
	\alpha_{z,n}&:{=} \Pr[\hat{\mathcal{H}}_z=1|\mathcal{H}=0],
	\\
	\beta_{z,n}&:{=} \Pr[\hat{\mathcal{H}}_z=0|\mathcal{H}=1],
	\end{align}
	satisfy
	\begin{align}
	\alpha_{y,n}&\leq \epsilon,\label{def1b}\\
	\alpha_{z,n} & \leq \epsilon, \label{def1a}
	\end{align}
	and
	\begin{align}
	-\varlimsup_{n\to \infty}\frac{1}{n}\log\beta_{y,n}&\geq \theta_y, \label{def2b}\\
	-\varlimsup_{n\to \infty}\frac{1}{n}\log\beta_{z,n}&\geq \theta_z.\label{def2a}
	\end{align}
\end{definition}
\begin{definition}\label{def} For given rates $(R,T)$, we define the \emph{exponent-rate region $\mathcal{E}^*(R,T)$} as the closure of all non-negative  pairs $(\theta_y,\theta_z)$ for which $(\theta_y,\theta_z,R,T)$ is $\epsilon$-achievable for every $\epsilon\in(0,1)$.
\end{definition}

\begin{remark}
In this paper we do not attempt to prove any ``strong converse.'' A strong converse in hypothesis testing would claim that the best achievable type-II error exponents for a given type-I error probability $\epsilon\in(0,1)$ does not depend on the value of $\epsilon$. For some special cases of the setting in Fig.~\ref{cascade}, a strong converse has recently been studied in \cite{Tan}.
\end{remark}

\section{A Coding  and Testing Scheme without Binning}\label{sec:no_binning}
 In this section we present  a first coding and testing scheme and characterize the achieved exponent-rate region using a relatively simple expression. The scheme is improved in the next section; the exponent-rate region achieved by the improved scheme is however more involved and includes multiple competing exponents.

 \subsection{The Coding and Testing Scheme} \label{sec:scheme}

Fix $\mu>0$, an arbitrary blocklength $n$, and  joint conditional pmfs $P_{SU|X}$ and $P_{V|SUY}$ over   finite auxiliary alphabets $\mathcal{S}$, $\mathcal{U}$, and $\mathcal{V}$. Define  the joint pmf
\begin{equation}\label{eq:dist}
P_{SUVXYZ}=P_{XYZ}P_{SU|X}P_{V|SUY}
\end{equation} and the following nonnegative rates, which are calculated according to the  distribution in \eqref{eq:dist} and $\mu$:
\begin{align}
R_s&:{=}I(X;S)+\mu,\label{casnb1}\\
R_u&:{=}I(U;X|S)+\mu,\label{casnb2}\\
R_v&:{=}I(V;Y,U|S)+\mu.\label{casnb3}
\end{align}
Later, we shall choose the joint distributions in such a way that $R\ge R_s+R_u$ and $T\ge R_s+R_v$.

\underline{\textit{Code Construction}:} First, we randomly generate codewords
\begin{equation}
\mathcal{C}_{S}:=
\left\{S^n(i)\colon \ i \in \{1,\ldots,\lfloor2^{nR_s}\rfloor\} \right\}
\end{equation}
by picking all entries i.i.d. according to $P_S$. Then, for each $i\in \{1,\ldots,\lfloor2^{nR_s}\rfloor\}$, we randomly generate codewords
\begin{equation}
\mathcal{C}_{U}(i):=\left\{U^n(j|i)\colon\ j \in \{1,\ldots,\lfloor2^{nR_u}\rfloor\} \right\}
\end{equation} by choosing for each $t\in\{1,\ldots,n\}$ and $j \in \{1,\ldots,\lfloor2^{nR_u}\rfloor\}$, the $t$-th component  $U_t(j|i)$ of codeword $U^n(j|i)$ independently according to the conditional distribution $P_{U|S}(\cdot|S_t(i))$, where $S_t(i)$ denotes the $t$-th component of the codeword $S^n(i)$.  For each $i\in \{1,\ldots,\lfloor2^{nR_s}\rfloor\}$, generate also codewords
\begin{equation}
\mathcal{C}_{V}(i):=\left\{V^n(k|i)\colon k \in \{1,\ldots,\lfloor2^{nR_v}\rfloor\} \right\}
\end{equation} by choosing for each $t\in\{1,\ldots,n\}$ and $k \in \{1,\ldots,\lfloor2^{nR_v}\rfloor\}$ the $t$-th component $V_t(k|i)$ of codeword $V^n(k|i)$   independently according to the conditional distribution $P_{V|S}(\cdot|S_t(i))$.

Reveal the realizations $\{s^n(i)\}$, $\{u^n(j|i)\}$, and $\{v^n(k|i)\}$ of the random code constructions to all terminals.
\vspace{2mm}

\underline{\textit{Transmitter}:} Given that it observes the sequence $X^n=x^n$, the transmitter looks for a pair of indices $(i,j)$ such that
\begin{align}
(s^n(i),u^n(j|i),x^n)\in \mathcal{T}_{\mu/4}^{n}(P_{SUX}).
\end{align}
If successful, it picks one such pair uniformly at random and sends
\begin{equation}
M=(i,j)
\end{equation} to the relay.
Otherwise, it sends $M=0$.

\underline{\textit{Relay}:} Assume  that the relay observes the sequence $Y^n=y^n$ and receives the message $M=m$. If $m=0$, it declares $\hat{\mathcal{H}}_y=1$ and sends $b=0$ to the receiver. Otherwise, it decomposes  $m=(i,j)$ and
looks for  an index $k$ such that
\begin{align}
(s^n(i),u^n(j|i),v^n(k|i),y^n)\in \mathcal{T}_{\mu/2}^{n}(P_{SUVY}).
\end{align}
If such an index $k$ exists,
the relay declares $\hat{\mathcal{H}}_y=1$ and sends the pair
\begin{equation}
B=(i,k)
\end{equation}
to the receiver. Otherwise, it declares $\hat{\mathcal{H}}_y=1$ and sends the message $B=0$.

\underline{\textit{Receiver}:} Assume that the receiver observes $Z^n=z^n$ and receives message $B=b$ from the relay.
If $b=0$, the receiver declares $\hat{\mathcal{H}}_z=1$.
Otherwise, it decomposes $b=(i,k)$ and checks whether
\begin{equation}
(s^n(i),v^n(k|i),z^n)\in \mathcal{T}_{\mu}^{n}(P_{SVZ}).
\end{equation}
If the typicality check is successful, the receiver declares $\hat{\mathcal{H}}_z=0$. Otherwise, it declares $\hat{\mathcal{H}}_z=1$.
\vspace{3mm}

\subsection{Achievable Exponent-Rate Region}
	We present the exponent region achieved by the preceding scheme.

 Given two conditional pmfs $P_{SU|X}$ and $P_{V|SUY}$, define $\mathcal{E}_{\textnormal{nobin}} (P_{SU|X}, P_{V|SUY})$ as the set of all  pairs $(\theta_y, \theta_z)$ that satisfy
 	\begin{align}
 	\theta_y &\leq \min_{\substack{\tilde{P}_{SUXY}:\\\tilde{P}_{SUX}=P_{SUX}\\\tilde{P}_{SUY}=P_{SUY}}}D(\tilde{P}_{SUXY}\|P_{SU|X}Q_{XY}),\label{casach1}\\
 	\theta_z&\leq \min_{\substack{\tilde{P}_{SUVXYZ}:\\\tilde{P}_{SUX}=P_{SUX}\\\tilde{P}_{SUVY}=P_{SUVY}\\\tilde{P}_{SVZ}=P_{SVZ}}}D(\tilde{P}_{SUVXYZ}\|P_{SU|X}P_{V|SUY}Q_{XYZ}),\label{casach2}
 	\end{align}
 	where the joint pmf $P_{SUVXYZ}$ is defined as in \eqref{eq:dist} and $P_{SUX}$, $P_{SUY}$, $P_{SUVY}$ and $P_{SVZ}$ are marginals of this pmf.

 	Define further the exponent region
 	\begin{equation}\label{eq:Eidef}
\mathcal{E}_{\textnormal{nobin}}(R,T) := \bigcup_{P_{SU|X}, P_{V|SUY} }\mathcal{E}_{\textnormal{nobin}} (P_{SU|X}, P_{V|SUY})
  	\end{equation}
  	where the union is over all pairs of conditional pmfs $(P_{SU|X}, P_{V|SUY})$ satisfying
  	 	\begin{align}
  	 	R&\geq I(S,U;X),\label{casach3}\\
  	 	T&\geq I(X;S)+I(V;Y,U|S)\label{casach4}
  	 	\end{align}
  	 	and the  mutual informations are again calculated according to the joint pmf defined in \eqref{eq:dist}.

\begin{theorem}[Achievable Region without Binning]\label{cascadeachnb}
For any pair of nonnegative rates $R,T \geq 0$, the set $\mathcal{E}_\textnormal{nobin}(R,T)$ is achievable:
\begin{equation}
\mathcal{E}_{\textnormal{nobin}}(R,T) \subseteq \mathcal{E}^*(R,T)
\end{equation}
\end{theorem}
\begin{IEEEproof} See Appendix \ref{cascadeachnbpr}.\end{IEEEproof}

In the above theorem, it suffices to consider auxiliary random variables $S$, $U$, and $V$ over alphabets $\mathcal{S}$, $\mathcal{U}$, and $\mathcal{V}$ whose sizes satisfy:  $|\mathcal{S}| \leq |\mathcal{X}| + 4$, $|\mathcal{U}| \leq |\mathcal{X}|\cdot|\mathcal{S}|+3$ and $|\mathcal{V}| \leq |\mathcal{U}|\cdot|\mathcal{S}|\cdot |\mathcal{Y}|+2$. This follows by simple applications of Caratheodory's theorem.

\section{An Improved Scheme with Binning}\label{sec:binning}
In source coding, it is well known that binning can decrease the required rate of communication when observations at different terminals are correlated. The same holds for hypothesis testing.
Before extending our coding and testing scheme from the previous section  to include binning, for completeness, we provide a detailed proof of the Shimokawa, Han, and Amari error exponent \cite{Amari} achieved over a point-to-point link when using binning.  So far, a detailed proof was available only in  Japanese \cite{Japanese}.
\subsection{Point-to-Point Link}

\begin{figure}[t!]
	\centering
	\includegraphics[scale=0.27]{p2p-eps-converted-to.pdf}
	\caption{Hypothesis testing over a point-to-point channel}
	\label{p2p}
\end{figure}
Consider the network in Fig.~\ref{p2p}, which can be obtained as a special case from the previously introduced two-hop relay network by setting $T=0$ and $Z$ a constant that is the same under both hypotheses. In this case, the exponent  $\theta_z$ cannot be positive and is uninteresting. The system performance is then  characterized by the exponent $\theta_y$, and  for the purpose of this subsection, the relay can be regarded  as the final receiver. Therefore, in the remainder of this subsection, we call the terminal that observes $Y^n$ ``the receiver". We make the following definition:
\begin{definition} Consider a single-hop system with only transmitter and receiver.
The exponent-rate function $\theta^* (R)$ is the supremum of all $\epsilon$-achievable error exponents for a given rate $R$, i.e.,
	\begin{align}
	\theta^* (R) := \sup\ \{\theta_y \geq 0\colon (\theta_y, 0, R,0)\;\text{is}\;\epsilon\text{-achievable}\; \forall \epsilon>0\}.
	\end{align}
	\end{definition}

	We recall the lower bound  on $\theta^*(R)$ in \cite{Amari}, after presenting a coding and testing scheme that achieves this exponent. (The presented scheme slightly deviates  from the scheme in \cite{Amari}.)

\subsubsection{Coding and Testing Scheme}\label{sec:binning_scheme}

Fix $\mu>0$, a sufficiently large blocklength $n$, and the conditional pmf $P_{S|X}$ over a finite auxiliary alphabet $\mathcal{S}$. Define the joint pmf
\begin{equation}\label{eq:PSXY}
P_{SXY}=P_{XY}P_{S|X}
\end{equation
and, if $R> I(S;X)$ define  the nonnegative rate $R'=0$ and otherwise choose	 $R'$ such that
\begin{align}
R+R'& \geq  I(X;S)+\mu,\label{cas1binp2pb}\\
R' &< I(Y;S).\label{rateKLH}
\end{align}
In the following coding scheme, when $R\leq I(S;X)$, we distribute the $s^n$-codewords in bins. Instead of sending the complete index of the chosen $s^n$, the transmitter sends only its bin number to the receiver. The receiver then selects the $s^n$ codeword from the indicated bin that is ``most-compatible" with its local observation $Y^n$, and makes its decision based on this selected codeword. By performing binning, the transmitter and the receiver can use a smaller communication rate, but the error probabilities may be higher.

\underline{\textit{Code Construction}:} Construct a random codebook
	\begin{align}
\mathcal{C}_{S}:=	\{S^n(m, \ell)\colon \ m \in\{1,...,\lfloor 2^{nR}\rfloor \},\ell\in\{1,...,\lfloor 2^{nR'}\rfloor \}\},\label{lembin0}
	\end{align}
	by drawing all entries of all codewords i.i.d. according to the chosen distribution $P_S$.

	Reveal the realization $\{s^n(m,\ell)\}$ of the random codebook to both terminals.
	\vspace{2mm}

\underline{\textit{Transmitter}:} Given that it observes the sequence $X^n=x^n$, the transmitter looks for indices $(m,\ell)$ such that
\begin{align}\label{eq:typical_encoding}
(s^n(m,\ell),x^n)\in \mathcal{T}_{\mu/2}^n(P_{SX}).
\end{align}
If successful, it picks one of these indices uniformly at random and sends the index $M=m$ to the relay. Otherwise, it sends $M=0$.
\vspace{2mm}

\underline{\textit{Receiver}:} Assume that the receiver observes $Y^n=y^n$ and receives the message $M=m$ from the transmitter. If $m=0$, the receiver declares $\hat{\mathcal{H}}=1$. Otherwise, it looks for an index $\ell'\in \{1,...,\lfloor 2^{nR'}\rfloor \}$ that minimizes $H_{\text{tp}(s^n(m, \ell''),y^n)}(S|Y)$ among all $\ell''$ satisfying $s^n(m,\ell'')\in\mathcal{T}_{\mu}^n(P_S)$.\footnote{Notice that because $m\neq 0$, there exists at least one codeword $s^n(m,\ell')\in \mathcal{T}_{\mu}^n(P_S)$ in bin $m$.} Then it checks whether
$$(s^n(m,\ell'),y^n)\in \mathcal{T}_{\mu}^n(P_{SY}),$$
and  declares $\hat{\mathcal{H}}=0$ if this typicality check is successful and $\hat{\mathcal{H}}=1$ otherwise.
 \vspace{3mm}

\subsubsection{Result on the Error Exponent}
The scheme described in the previous subsection yields the following lower bound on the exponent-rate function.

\vspace{2mm}

\begin{theorem}[\cite{Amari}]\label{thm_binning} For every choice of the conditional distribution $P_{S|X}$ satisfying that $R\ge I(S;X|Y)$, the exponent-rate function $\theta^*(R)$ is lower-bounded as
	\begin{align}
	\theta^*(R) &\geq  \min \Bigg\{ \min_{\substack{\tilde{P}_{SXY}:\\\tilde{P}_{SX}=P_{SX}\\\tilde{P}_{SY}=P_{SY}}} D(\tilde{P}_{SXY}\|P_{S|X}Q_{XY}), \nonumber \\
	& \hspace{2cm} \min_{\substack{\tilde{P}_{SXY}:\\\tilde{P}_{SX}=P_{SX}\\\tilde{P}_Y=P_Y\\H(S|Y) \leq H_{\tilde{P}_{SY}}(S|Y)}} D(\tilde{P}_{SXY}\|P_{S|X}Q_{XY})+ R-I(S;X|Y)\Bigg\}.\label{ach}
	\end{align}
For a choice of $P_{S|X}$ such that $R\geq  I(S;X)$, the bound can be tightened to
	\begin{align}
	\theta^*(R) &\geq  \min_{\substack{\tilde{P}_{SXY}:\\\tilde{P}_{SX}=P_{SX}\\\tilde{P}_{SY}=P_{SY}}} D(\tilde{P}_{SXY}\|P_{S|X}Q_{XY}),\label{eq:LB}
	\end{align}
Here   mutual informations
 and the entropy $H(S|Y)$ in the miniminization constraint are calculated according to the joint pmf in \eqref{eq:PSXY} and the chosen conditional pmf $P_{S|X}$.
\end{theorem}
\begin{IEEEproof}When $R\geq I(S;X)$,  our scheme does not use binning and an analysis similar to Appendix~\ref{cascadeachnbpr} (the analysis of the multi-hop scheme without binning) yields the desired result. When $R<I(S;X)$, our scheme uses binning and is analyzed in Appendix \ref{thm1pr}.\end{IEEEproof}

In the above theorem, it suffices to consider  auxiliary random variables $S$ over alphabets $\mathcal{S}$ whose sizes satisfy:  $|\mathcal{S}| \leq |\mathcal{X}| + 2$.

The inequality in Theorem \ref{thm_binning} holds with equality in  the  special cases of \emph{testing against independence} \cite{Csiszar86}, where  $Q_{XY}=P_X \cdot P_Y$,\footnote{There is no need to apply the coding scheme with binning to attain the optimal error exponent in this case, see \cite{Csiszar86}.} and of \emph{testing against conditional independence} \cite{Wagner}, where $Y$ decomposes as $Y=(Y_{\textnormal{C}},Y_{\textnormal{H}})$ and $Q_{XY_{\textnormal{C}}Y_{\textnormal{H}}}=P_{XY_{\textnormal{C}}} P_{Y_{\textnormal{H}}|Y_{\textnormal{C}}}$.

\subsection{The Two-Hop Relay Network}\label{sec:cascade_binning}

We turn back to the two-hop relay network and propose an improved coding and testing scheme employing binning.

\subsubsection{Coding and Testing Scheme}

Fix $\mu>0$, an arbitrary blocklength $n$, and  joint conditional pmfs $P_{SU|X}$ and $P_{V|SUY}$ over   finite auxiliary alphabets $\mathcal{S}$, $\mathcal{U}$, and $\mathcal{V}$. Define  the joint pmf $P_{SUVXYZ}=P_{XYZ}P_{SU|X}P_{V|SUY}$ and the following nonnegative rates, which are calculated according to the chosen distribution,
\begin{subequations}\label{eq:rates_cascd}
\begin{align}
R_s&= I(X;S)+\mu,\label{cas1bin}\\
R_u+R'_u&= I(U;X|S)+\mu,\label{cas2bin}\\
R_v+R'_v&= I(V;Y,U|S)+\mu,\label{cas3bin}\\
R'_u&\leq I(U;Y|S),\label{cas5bin}\\
R'_v&\leq I(V;Z|S).\label{cas6bin}
\end{align}
\end{subequations}
The joint distributions are chosen  in such a way that
\begin{IEEEeqnarray}{rCl}
	R& \ge &R_s+R_u \\
	T & \ge  & R_s+R_v.
	\end{IEEEeqnarray}

In the following coding scheme, the transmitter distributes the $u^n$ codewords in bins, and sends the bin number of the chosen $u^n$ to the relay. The relay looks in that bin for the  $u^n$ codeword that is ``most compatible" with its local observation $Y^n$. Similarly, the relay and the receiver perform binning on $v^n$. Note that for simplicity and ease of exposition, we do not bin the $s^n$ codewords.

\underline{\textit{Code Construction}:} Construct a random codebook $$\mathcal{C}_{S}= \{S^n(i) \colon  \;\;   i\in\{1, ..., \lfloor 2^{nR_s}\rfloor\} \}$$
by selecting each entry of the $n$-length codeword $s^n(i)$ in an i.i.d. manner according to the pmf $P_{S}$. Then, for each $i$,  generate random codebooks
$$\mathcal{C}_{U}(i)=\{U^n(j,e|i)\colon \;\; j\in \{1,...,\lfloor 2^{nR_u}\rfloor\},\; e\in \{1,...,\lfloor 2^{nR'_u}\rfloor\}\}$$
and
$$\mathcal{C}_{V}(i)=\{V^n(k,f|i)\colon \; \; k\in \{1,...,\lfloor 2^{nR_v}\rfloor \},\; f\in \{1,...,\lfloor 2^{nR'_v}\rfloor \}\}$$
 by selecting for each $t\in\{1,\ldots, n\}$, the $t$-th components $U_t(j,e|i)$ and $V_t(k,f|i)$  of  the  codewords $U^n(j,e|i)$ and $V^n(k,f|i)$ independently using the conditional pmfs $P_{U|S}(\cdot|S_t(i))$ and $P_{V|S}(\cdot|S_t(i))$, where $S_t(i)$ denotes the $t$-th component of codeword $S^n(i)$.

 Reveal the realizations $\{s^n(i)\}$, $\{u^n(j,e|i)\}$, and $\{v^n(k,f|i)\}$ of the random codebooks to all terminals

\vspace{2mm}

\underline{\textit{Transmitter}:} Given that the transmitter observes the sequence $X^n=x^n$, it looks for indices $(i,j,e)$ such that
\begin{align}\label{eq:typical_cascade_encoding}
(s^n(i),u^n(j,e|i),x^n)\in \mathcal{T}_{\mu/4}^n(P_{SUX}).
\end{align}
If successful, it picks one such triple uniformly at random, and sends the first two indices of the triple:
\begin{align}
M= (i,j)
\end{align}
to the relay. Otherwise, it sends $M=0$.
\vspace{2mm}

\underline{\textit{Relay}:} Assume that the relay observes the sequence $Y^n=y^n$ and receives the message $M=m$. If $m=0$, it declares $\hat{\mathcal{H}}_y=1$ and sends $B=0$ to the receiver. Otherwise, it looks for an index $e'$ which minimizes $H_{\text{tp}(s^n(i),u^n(j,e''|i),y^n)}(U|S,Y)$ among all $e''$ satisfying $(s^n(i),u^n(j,e''|i))\in \mathcal{T}_{\mu/2}^n(P_{SU})$.
It then looks for  indices $(k,f)$ such that
\begin{align}
(s^n(i),u^n(j,e'|i),v^n(k,f|i),y^n)\in \mathcal{T}_{\mu/2}^n(P_{SUVY}).
\end{align}
If successful, it declares $\hat{\mathcal{H}}_y=0$ and picks one of these index pairs uniformly at random. It then sends the corresponding indices
\begin{align}
B=(i,k)
\end{align}
 to the receiver. Otherwise, it declares $\hat{\mathcal{H}}_y=1$ and sends the message $B=0$ to the receiver.
\vspace{2mm}

\underline{\textit{Receiver}:} Assume that the receiver observes $Z^n=z^n$ and receives message $B=b$ from the relay. If $b=0$, the receiver declares $\hat{\mathcal{H}}_z=1$. Otherwise, it looks for an index $f'$ which minimizes $H_{\text{tp}(s^n(i),v^n(k,f''|i),z^n)}(V|S,Z)$ among all $f''$ satisfying $(s^n(i),v^n(k,f''|i))\in \mathcal{T}_{\mu/2}^n(P_{SV})$.
Then, it checks whether
\begin{align}
(s^n(i),v^n(k,f'|i),z^n)\in \mathcal{T}_{\mu}^n (P_{SVZ}).
\end{align}
If successful, the receiver declares $\hat{\mathcal{H}}_z=0$. Otherwise, it declares $\hat{\mathcal{H}}_z=1$.
\vspace{2mm}

\subsubsection{Result on the Exponent-Rate  Region}
The coding scheme in the previous subsection establishes the following theorem.

For any pair of conditional pmfs $P_{US|X}$ and $P_{V|SUY}$, let  $\mathcal{E}_{\textnormal{bin}}(P_{US|X}, P_{V|SUY})$ denote the set of all exponent-pairs $(\theta_y,\theta_z)$ that satisfy
		\begin{align}
		\theta_y &\leq \min \{ \theta_y^{(1)},\theta_y^{(2)}\},\label{casach1bin}\\
		\theta_z&\leq \min\{\theta_z^{(i)}\colon i=1,...,4\},\label{casach2bin}
		\end{align}
where
\begin{subequations}\label{eq:theta10}
	\begin{IEEEeqnarray}{rCl}
		\theta_y^{(1)} &:=& \min_{\substack{\tilde{P}_{SUXY}:\\\tilde{P}_{SUX}=P_{SUX}\\\tilde{P}_{SUY}=P_{SUY}}} D(\tilde{P}_{SUXY}\|P_{SU|X}Q_{XY}),\\[1ex]

	\theta_y^{(2)}  &:=& \min_{\substack{\tilde{P}_{SUXY}:\\\tilde{P}_{SUX}=P_{SUX}\\\tilde{P}_{SY}=P_{SY}\\H(U|S,Y)\leq H_{\tilde{P}}(U|S,Y)}}\!\!\!\!  D(\tilde{P}_{SUXY}\|P_{SU|X}Q_{XY})+R-I(S,U;X)+I(U;Y|S),	\\[1ex]

	\theta_z^{(1)}  &:=& \min_{\substack{\tilde{P}_{SUVXYZ}:\\\tilde{P}_{SUX}=P_{SUX}\\\tilde{P}_{SUVY}=P_{SUVY}\\\tilde{P}_{SVZ}=P_{SVZ}}}\!\!\!\!  D(\tilde{P}_{SUVXYZ}\|P_{SU|X}P_{V|SUY}Q_{XYZ}),\label{th1last}\\[2ex]

		\theta_z^{(2)}  &:=&\!\!\! \min_{\substack{\tilde{P}_{SUVXYZ}:\\\tilde{P}_{SUX}=P_{SUX}\\\tilde{P}_{SVY}=P_{SVY}\\\tilde{P}_{SVZ}=P_{SVZ}\\H(U|S,Y)\leq H_{\tilde{P}}(U|S,Y)}}\!\!\!\!\!\!\!\!\!\! D(\tilde{P}_{SUVXYZ}\| P_{SU|X}P_{V|SY}Q_{XYZ})+R-I(S,U;X) + I(U;Y|S) \\[1ex]

	\theta_z^{(3)}  &:=& \min_{\substack{\tilde{P}_{SUVXYZ}:\\\tilde{P}_{SUX}=P_{SUX}\\\tilde{P}_{SUVY}=P_{SUVY}\\\tilde{P}_{SZ}=P_{SZ}\\H(V|S,Z)\leq H_{\tilde{P}}(V|S,Z)}} \!\!\!\! D(\tilde{P}_{SUVXYZ}\|P_{SU|X}P_{V|SUY}Q_{XYZ})+T-I(S;X)-I(V;Y,U|S)+I(V;Z|S),\\[1ex]

	\theta_z^{(4)} &:=& \min_{\substack{\tilde{P}_{SUVXYZ}:\\\tilde{P}_{SUX}=P_{SUX}\\\tilde{P}_{SVY}=P_{SVY}\\\tilde{P}_{SZ}=P_{SZ}\\H(U|S,Y)\leq H_{\tilde{P}}(U|S,Y)\\H(V|S,Z)\leq H_{\tilde{P}}(V|S,Z)}}\!\!\!\! D(\tilde{P}_{SUVXYZ}\| P_{SU|X}P_{V|SY}Q_{XYZ}) \nonumber \\
	& & \hspace{4cm}+ R+T-I(S,U;X)-I(X;S)-I(V;U,Y|S)+I(U;Y|S)+I(V;Z|S),
	\end{IEEEeqnarray}
\end{subequations}
where the mutual information and entropy terms, as well as  the marginals $P_{SUX}$, $P_{SUVY}$, $P_{SVY}$,  $P_{SVZ}$, and $P_{SZ}$ are calculated with respect to the joint pmf
\begin{equation}\label{eq:joint}
P_{SUVXYZ} = P_{US|X}P_{V|USY} P_{XYZ}.
\end{equation}
Define then the exponent-rate region
\begin{equation}
 \mathcal{E}_{\textnormal{bin}}(R,T):=
 \bigcup_{(P_{US|X},P_{V|USY})}   \mathcal{E}_{\textnormal{bin}}(P_{US|X},P_{V|USY})
 \end{equation}
 where the union is over all pairs of conditional distributions so that
 the rate constraints
\begin{align}
R&\geq I(S,U;X)-I(U;Y|S),\label{casach5bin}\\
T&\geq I(V;Y,U|S)-I(V;Z|S)+I(S;X),\label{casach7bin}
\end{align}
are satisfied when the mutual informations are calculated according to the joint pmf in \eqref{eq:joint}.

\begin{theorem}[Achievable Region with Binning]\label{thm:casbin} For any positive rate-pair $(R,T)$:
	\begin{equation}
	\mathcal{E}_{\textnormal{bin}}(R,T) \subseteq 	\mathcal{E}^*(R,T).
	\end{equation}
\end{theorem}

\begin{IEEEproof} See Appendix \ref{casbinpr}.\end{IEEEproof}
\medskip

For each choice of conditional pmfs $P_{US|X}$ and $P_{V|USY}$, the achievable exponents-region $\mathcal{E}_{\textnormal{bin}}(P_{US|X}, P_{V|USY})$ is characterized through two competing  exponents at the relay and four competing  exponents at the receiver, see \eqref{casach1bin} and \eqref{casach2bin}. Extending
 	our scheme by
binning also the $s^n$ codewords achieves an  exponents region that  is characterized by three competing  exponents at the relay and ten competing exponents at the receiver.	Details are omitted for brevity.

\section{The Special Case ``$X^n \to Y^n \to Z^n$ Under Both Hypotheses"}\label{sec:MarkovXYZ}
Consider a situation  where  the relay lies in between the transmitter and the receiver, and thus the signals at the sensor and the receiver are conditionally independent given the signal at the relay. In this situation, the two-hop relay network seems particularly adequate for modelling short-range wireless communication.

Assume that the pmfs $P_{XYZ}$ and $Q_{XYZ}$ decompose as
\begin{align}
P_{XYZ} &= P_X\cdot P_{Y|X}\cdot P_{Z|Y},\label{case0a}\\
Q_{XYZ} &= Q_X\cdot Q_{Y|X}\cdot Q_{Z|Y}.\label{case0b}
\end{align}

We start by showing that in this special case the compression mechanisms in the previously-presented coding and testing schemes can be simplified. There is no need to send compression information from the transmitter to the receiver. Hence, the message sent from the relay to the receiver consists only of the relay's own guess and compression information of the relay's observation.
Technically, this means that the expressions for  $\mathcal{E}_\textnormal{nobin}(R,T)$ and $\mathcal{E}_\textnormal{bin}(R,T)$ can be simplified for this special case by setting $S$ to be a constant, and choosing $V$ to be conditionally independent of $U$ given $Y$. In the following, we use the subscript ``dcpled'' to refer to the region of this special case, which stands for ``decoupled''. Here, the transmitter-relay and relay-receiver links are basically decoupled from each other thanks to the Markov chain $X\to Y\to Z$.

\subsection{Simplified Exponent Regions}
Given two conditional pmfs $P_{U|X}$ and $P_{V|Y}$, define the exponents region
 $\mathcal{E}_{\textnormal{dcpled}}(P_{U|X}, P_{V|Y})$ as the set of all  pairs $(\theta_y, \theta_z)$ that satisfy
\begin{align}
\theta_y &\leq \min_{\substack{\tilde{P}_{UXY}:\\\tilde{P}_{UX}=P_{UX}\\\tilde{P}_{UY}=P_{UY}}}D(\tilde{P}_{UXY}\|P_{U|X}Q_{XY}),\\
\theta_z&\leq\min_{\substack{\tilde{P}_{UXY}:\\\tilde{P}_{UX}=P_{UX}\\\tilde{P}_{UY}=P_{UY}}}D(\tilde{P}_{UXY}\|P_{U|X}Q_{XY}) + \min_{\substack{\tilde{P}_{VYZ}:\\\tilde{P}_{VY}=P_{VY}\\\tilde{P}_{VZ}=P_{VZ}}}  \mathbb{E}_{P_{Y}}\Big[  D(\tilde{P}_{VZ|Y}\|P_{V|Y}Q_{Z|Y})\Big],
\end{align}
where $P_{UY}$ and $P_{VZ}$ indicate the marginals of the joint pmfs $P_{U|X}P_{XY}$ and $P_{V|Y} P_{YZ}$, and further define
\begin{equation}
\mathcal{E}_\textnormal{dcpled}(R,T) := \bigcup_{P_{U|X}, P_{V|Y} }\mathcal{E}_{\textnormal{dcpled}} (P_{U|X}, P_{V|Y})
\end{equation}
where the union is over all pairs of conditional pmfs $(P_{U|X}, P_{V|Y})$ satisfying
\begin{align}
R&\geq I(U;X),\label{casach3b}\\
T&\geq I(V;Y)\label{casach4b}
\end{align}
for  mutual informations that are calculated according to the joint pmfs $P_{UX}=P_{U|X}P_X$ and $P_{VY}=P_{V|Y}P_Y$.

\begin{proposition}[Simplified Achievable Region Without Binnning]\label{prop:Markov}
	If \eqref{case0a} and \eqref{case0b} hold,
	then
	\begin{equation}
	\mathcal{E}_\textnormal{dcpled} (R,T) = \mathcal{E}_{\textnormal{nobin}}(R,T).
	\end{equation}
\end{proposition}
\begin{IEEEproof}
	See Appendix~\ref{app:proof_prop}.
\end{IEEEproof}

In the above proposition, it suffices to consider auxiliary random variables $U$ and $V$ over alphabets $\mathcal{U}$ and $\mathcal{V}$ whose sizes satisfy:  $|\mathcal{U}| \leq |\mathcal{X}|+1$ and $|\mathcal{V}| \leq  |\mathcal{Y}|+1$.

\bigskip

Similarly, given two conditional pmfs $P_{U|X}$ and $P_{V|Y}$, let  $\mathcal{E}_{\textnormal{bin,dcpled}}(P_{U|X}, P_{V|Y})$ denote the set of all exponent-pairs $(\theta_y,\theta_z)$ that satisfy
		\begin{subequations}
	\begin{IEEEeqnarray}{rCl}
		\theta_y &\leq& \min \Big\{ \min_{\substack{\tilde{P}_{UXY}:\\\tilde{P}_{UX}=P_{UX}\\\tilde{P}_{UY}=P_{UY}}} D(\tilde{P}_{UXY}\|P_{U|X}Q_{XY}),\; \min_{\substack{\tilde{P}_{UXY}:\\\tilde{P}_{UX}=P_{UX}\\\tilde{P}_{Y}=P_{Y}\\H(U|Y)\leq H_{\tilde{P}}(U|Y)}}\!\!\!\!  D(\tilde{P}_{UXY}\|P_{U|X}Q_{XY})+R-I(U;X|Y)\Big\}
		\end{IEEEeqnarray}
		and
		\begin{IEEEeqnarray}{rCl}
	\theta_z & \leq & \min \Big\{ \min_{\substack{\tilde{P}_{UXY}:\\\tilde{P}_{UX}=P_{UX}\\\tilde{P}_{UY}=P_{UY}}} D(\tilde{P}_{UXY}\|P_{U|X}Q_{XY}),\; \min_{\substack{\tilde{P}_{UXY}:\\\tilde{P}_{UX}=P_{UX}\\\tilde{P}_{Y}=P_{Y}\\H(U|Y)\leq H_{\tilde{P}}(U|Y)}}\!\!\!\!  D(\tilde{P}_{UXY}\|P_{U|X}Q_{XY})+R-I(U;X|Y)\Big\}  \nonumber \\[2ex]
	& & +  \min\Big\{  \min_{\substack{\tilde{P}_{VZ|Y}:\\\tilde{P}_{VY}=P_{VY}\\\tilde{P}_{VZ}=P_{VZ}}}  \mathbb{E}_{P_{Y}}\Big[  D(\tilde{P}_{VZ|Y}\|P_{V|Y}Q_{Z|Y})\Big]  , \min_{\substack{\tilde{P}_{VZ|Y}:\\\tilde{P}_{VY}=P_{VY}\\\tilde{P}_{Z}=P_{Z}\\H(V|Z)\leq H_{\tilde{P}}(V|Z)}} \!\!\!\!  \mathbb{E}_{P_{Y}}\Big[  D(\tilde{P}_{VZ|Y}\|P_{V|Y}Q_{Z|Y})\Big]+T-I(V;Y|Z)\Big\},\nonumber\\\label{eq:simpletheta_zbinning}
	\end{IEEEeqnarray}
\end{subequations}
 where the mutual information and entropy terms, as well as  the marginals $P_{SUX}$, $P_{SUVY}$, $P_{SVY}$,  $P_{SVZ}$, and $P_{SZ}$ are calculated with respect to the joint pmf
\begin{equation}\label{eq:joint2}
P_{SUVXYZ} = P_{US|X}P_{V|USY} P_{XYZ}.
\end{equation}
Further define
\begin{equation}
 \mathcal{E}_{\textnormal{bin,dcpled}}(R,T):=
 \bigcup_{{P_{U|X},P_{V|Y}}}   \mathcal{E}_{\textnormal{bin,dcpled}}(P_{U|X},P_{V|Y})
 \end{equation}
 where the union is over all pairs of conditional distributions for which
 the rate constraints
\begin{align}
R&\geq I(U;X|Y),\label{casach5bin}\\
T&\geq I(V;Y|Z),\label{casach7bin}
\end{align}
are satisfied when the mutual informations are calculated according to the joint pmf in \eqref{eq:joint2}.

\begin{proposition}[Simplified Achievable Region With Binnning]\label{cor-bin-state}
	If \eqref{case0a} and \eqref{case0b} hold,
	then
	\begin{equation}
	\mathcal{E}_ \textnormal{bin,dcpled} (R,T) = \mathcal{E}_{\textnormal{bin}}(R,T).
	\end{equation}
\end{proposition}
\begin{IEEEproof}
The inclusion $\mathcal{E}_ \textnormal{bin,dcpled} (R,T) \subseteq \mathcal{E}_{\textnormal{bin}}(R,T)$ follows by restricting to $U$ and $V$ to be conditionally independent given $Y$ and $S$ to be a constant. The proof of inclusion
$\mathcal{E}_{\textnormal{bin,dcpled}} (R,T) \supseteq \mathcal{E}_{\textnormal{bin}}(R,T)$ is sketched in Appendix~\ref{app:inclusion2}.
\end{IEEEproof}

\medskip

\begin{remark} For both Propositions~\ref{prop:Markov} and \ref{cor-bin-state}, the exponent at the receiver equals the sum of two exponents: the first is the exponent at the relay (i.e., the exponent attained over the transmitter-relay link), and the second is the exponent on the isolated relay-receiver link, but with $Q_{YZ}$ replaced by $P_Y Q_{Z|Y}$.
\end{remark}

\subsection{Optimality Results}
In the following, we prove optimality of the achievable region in Proposition~\ref{cor-bin-state} for some cases of ``testing against conditional independence'' under the Markov conditions \eqref{case0a} and \eqref{case0b}. In the following examples, if the random variables $Y_{\textnormal{C}}$ and $Z_{\textnormal{C}}$ are constants, then the setups reduce to ``testing against independence". For ``testing against independence", achievability can also be established using  the simpler Proposition~\ref{prop:Markov}. In other words,  the optimal exponents can also be achieved without binning.
\bigskip

\subsubsection{Special Case 1}
Assume that the relay's and the receiver's observations decompose as
\begin{IEEEeqnarray}{rCl}
	Y & = &(Y_{\textnormal{C}},Y_{\textnormal{H}}) \label{SI1}\\
	Z & = & (Y_{\textnormal{C}},Z_{\textnormal{C}},Z_{\textnormal{H}})
	\end{IEEEeqnarray}
	and
	\begin{align}
\textnormal{under } \mathcal{H}=0 &\colon \qquad  \big(X^n,Y_{\textnormal{C}}^{n},Y_{\textnormal{H}}^n,Z_{\textnormal{C}}^n, Z_{\textnormal{H}}^n\big)\;\text{i.i.d.}\; \sim  P_{X|Y_{\textnormal{C}}Y_{\textnormal{H}}}\cdot P_{Y_{\textnormal{C}}Y_{\textnormal{H}}Z_{\textnormal{C}}Z_{\textnormal{H}}},\label{SI2b}\\
\textnormal{under }\mathcal{H}=1 &\colon \qquad  \big(X^n,Y_{\textnormal{C}}^{n},Y_{\textnormal{H}}^n,Z_{\textnormal{C}}^n, Z_{\textnormal{H}}^n\big)\;\text{i.i.d.}\; \sim P_{X|Y_{\textnormal{C}}}\cdot P_{Y_{\textnormal{H}}|Y_{\textnormal{C}}Z_{\textnormal{C}}}\cdot P_{Y_{\textnormal{C}}Z_{\textnormal{C}}Z_{\textnormal{H}}}.\label{SI2}
\end{align}
 The  following corollary shows that in this case, the receiver's optimal error exponent  equals the \emph{sum} of the optimal error exponent at the relay and the optimal error exponent achieved over the isolated relay-receiver link.

\begin{corollary}\label{SIthm} If  \eqref{SI1}--\eqref{SI2} hold, the exponent-rate  region $\mathcal{E}^*(R,T)$ is the set of all nonnegative pairs $(\theta_y,\theta_z)$ that satisfy
	\begin{align}
	\theta_y &\leq I(U;Y|Y_{\textnormal{C}}),\\
	\theta_z &\leq I(U;Y|Y_{\textnormal{C}})+I(V;Z|Z_{\textnormal{C}},Y_{\textnormal{C}}),\label{thbinopt}
	\end{align}
		for some auxiliary random variables $(U,V)$ satisfying the Markov chains $U\to X\to Y$ and $V\to Y\to Z$ and the rate constraints
	\begin{align}
	R &\geq I(U;X|Y_{\textnormal{C}}),\\
	T &\geq I(V;Y|Y_{\textnormal{C}},Z_{\textnormal{C}}),
	\end{align}
and where $Y=(Y_{\textnormal{C}},Y_{\textnormal{H}})$, $Z=(Z_{\textnormal{C}},Z_{\textnormal{H}})$, and $(X,Y_{\textnormal{C}},Y_{\textnormal{H}},Z_{\textnormal{C}}, Z_{\textnormal{H}}) \sim  P_{X|Y_{\textnormal{C}}Y_{\textnormal{H}}}\cdot P_{Y_{\textnormal{C}}Y_{\textnormal{H}}Z_{\textnormal{C}}Z_{\textnormal{H}}}$.
	\end{corollary}
\begin{IEEEproof} Achievability follows by simplifying Proposition~\ref{cor-bin-state}. For  this special case, since $R \geq I(U;X|Y_{\textnormal{C}})$ and $T\geq I(V;Y|Y_{\textnormal{C}},Z_{\textnormal{C}})$, exponents $\theta_{z}^{(2)},\theta_{z}^{(3)},\theta_{z}^{(4)}$ become inactive in view of $\theta_{z}^{(1)}$. The converse is proved in Appendix~\ref{SIproof}.
	\end{IEEEproof}

In the above theorem it suffices to consider auxiliary random variables $U$ and $V$ over alphabets  $\mathcal{U}$ and $\mathcal{V}$ whose sizes satisfy:  $|\mathcal{U}| \leq |\mathcal{X}| + 2$ and $|\mathcal{V}| \leq |\mathcal{Y}|+1$.

\begin{remark}
If we set $Y_{\textnormal{C}}$ and $Z_{\textnormal{C}}$ to constants, then this special case reduces to one where
\begin{IEEEeqnarray}{rCl}
P_{XYZ} & = & P_{XY}\cdot P_{Z|Y}\\
Q_{XYZ} & = & P_X\cdot P_{Y} \cdot P_Z.
\end{IEEEeqnarray}
The exponent-region then becomes the set of all nonnegative pairs $(\theta_y, \theta_z)$  that satisfy
	\begin{align}
	\theta_y &\leq I(U;Y),\label{thm2aa}\\
	\theta_z &\leq I(U;Y)+I(V;Z),\label{thm2bb}
	\end{align}
	for a pair of auxiliary random variables $U$ and $V$ satisfying the Markov chains  $U\to X\to Y$ and $V\to Y \to Z$  and the rate constraints
	\begin{align}
	R &\geq I(U;X)\label{thm2cc}\\
		T &\geq I(V;Y).\label{thm2d}
	\end{align}
Furthermore, the exponent-rate region can be obtained using Proposition~\ref{prop:Markov}.
\end{remark}

\bigskip

\subsubsection{Special Case 2}

Assume that the receiver's observation decomposes as
\begin{IEEEeqnarray}{rCl} \label{eq:decomp1}
	Z & = & (Z_{\textnormal{C}},Z_{\textnormal{H}})
	\end{IEEEeqnarray}
	and
	\begin{align}
\textnormal{under } \mathcal{H}=0 &\colon \qquad  \big(X^n,Y^n,Z_{\textnormal{C}}^n, Z_{\textnormal{H}}^n\big)\;\text{i.i.d.}\; \sim  P_{XYZ_{\textnormal{C}}Z_{\textnormal{H}}}, \label{eq:hyp1}\\
\textnormal{under }\mathcal{H}=1 &\colon \qquad  \big(X^n, Y^n,Z_{\textnormal{C}}^n, Z_{\textnormal{H}}^n\big)\;\text{i.i.d.}\; \sim P_{X YZ_{\textnormal{C}}}\cdot  P_{Z_{\textnormal{H}}|Z_{\textnormal{C}}}.\label{eq:hyp2}
\end{align}
In this case, the relay cannot obtain a positive exponent since $(X^n,Y^n)\sim P_{XY}$  under both hypotheses. Moreover, as the following corollary shows, the relay can completely ignore the message from the transmitter and act as if it was the transmitter of a simple point-to-point setup \cite{Han}.
\begin{corollary}\label{prop1b} Assume \eqref{eq:decomp1}--\eqref{eq:hyp2}.
	The exponent-rate region $\mathcal{E}^*(R,T)$ is the set of all nonnegative pairs $(\theta_y, \theta_z)$  that satisfy
	\begin{align}
	\theta_y &=0\\
	\theta_z &\leq I(V;Z_{\textnormal{H}}|Z_{\textnormal{C}})\label{thm:oneb}
	\end{align}
	for an auxiliary random variable $V$ satisfying the Markov chain  $V\to Y \to Z$  and the rate constraint
	\begin{align}
	T &\geq I(V;Y|Z_{\textnormal{C}}),
	\end{align}
where $Z=(Z_{\textnormal{C}},Z_{\textnormal{H}})$, and $(X,Y,Z_{\textnormal{C}}, Z_{\textnormal{H}}) \sim  P_{XYZ_{\textnormal{C}}Z_{\textnormal{H}}}$.
		(No constraint involves the rate $R$.)
\end{corollary}
\begin{IEEEproof} Achievability follows by specializing Proposition~\ref{cor-bin-state} to  $U = 0$ (deterministically) and then simplifying the expressions. In particular, notice that, since $T\geq I(V;Y |Z_{\textnormal{C}})$, exponents  $\theta_{z}^{(2)},\theta_{z}^{(3)},\theta_{z}^{(4)}$ become inactive in view of $\theta_{z}^{(1)}$. The converse is standard; details can be found in Appendix~\ref{app:convCor}.
\end{IEEEproof}

\begin{remark}
If we set $Z_{\textnormal{C}}$ to a constant, then the problem reduces to one where
\begin{IEEEeqnarray}{rCl}
P_{XYZ} & = & P_{XY} \cdot P_{Z|Y}\\
Q_{XYZ} & = & P_{XY} \cdot P_Z.
\end{IEEEeqnarray}
The exponent-rate region then becomes the set of all nonnegative pairs $(\theta_y, \theta_z)$  that satisfy
	\begin{align}
	\theta_y &=0,\\
	\theta_z &\leq I(V;Z),
	\end{align}
	for an auxiliary random variable $V$ satisfying the Markov chain  $V\to Y \to Z$  and the rate constraint
	\begin{align}
	T &\geq I(V;Y).
	\end{align}
The region is again achievable using Proposition~\ref{prop:Markov}.
\end{remark}

\bigskip

\subsubsection{Special Case 3}

Assume that the relay's  observation decomposes as
\begin{IEEEeqnarray}{rCl}
	Y & = &(Y_{\textnormal{C}},Y_{\textnormal{H}}), \label{eq:set1}
		\end{IEEEeqnarray}
	and
	\begin{align}
\textnormal{under } \mathcal{H}=0 &\colon \qquad  \big(X^n,Y_{\textnormal{C}}^{n},Y_{\textnormal{H}}^n,Z^n\big)\;\text{i.i.d.}\; \sim  P_{XY_{\textnormal{C}}Y_{\textnormal{H}} Z},\\
\textnormal{under }\mathcal{H}=1 &\colon \qquad  \big(X^n,Y_{\textnormal{C}}^{n},Y_{\textnormal{H}}^n,Z^n\big)\;\text{i.i.d.}\; \sim P_{X|Y_{\textnormal{C}}}\cdot P_{Y_{\textnormal{C}}Y_{\textnormal{H}} Z}.\label{eq:set3}
\end{align}
\medskip

As the following corollary shows, in this case the  optimal strategy is to let the relay decide on the hypothesis, and let the receiver simply follow this decision. It thus suffices that the relay forwards its decision to the receiver.  No quantization information is needed at the receiver.

\begin{corollary}\label{prop1c} Assume \eqref{eq:set1}--\eqref{eq:set3} hold.
	The exponent-rate region $\mathcal{E}^*(R,T)$ is the set of all nonnegative pairs $(\theta_y, \theta_z)$  that satisfy
	\begin{align}
	\theta_y &\leq I(U;Y_{\textnormal{H}}|Y_{\textnormal{C}})\\
	\theta_z &\leq I(U;Y_{\textnormal{H}}|Y_{\textnormal{C}}),
	\end{align}
	for an auxiliary random variable $U$ satisfying the Markov chain  $U\to X \to (Y,Z)$  and the rate constraint
	\begin{align}
	R &\geq I(U;X|Y_{\textnormal{C}}),
	\end{align}
	where $Y=(Y_{\textnormal{C}},Y_{\textnormal{H}})$ and $(X,Y_{\textnormal{C}},Y_{\textnormal{H}},Z_{\textnormal{C}}, Z_{\textnormal{H}}) \sim  P_{XY_{\textnormal{C}}Y_{\textnormal{H}} Z}$.
	(No constraint involves the rate $T$.)
\end{corollary}
\begin{IEEEproof} Achievability follows by specializing Proposition~\ref{cor-bin-state} to  $V$ being a constant and simplifying the expressions. The converse is similar to the proof of the converse to Corollary~\ref{prop1b}. \end{IEEEproof}

\begin{remark}
If we set $Y_{\textnormal{C}}$ to a constant, then the problem becomes one where
\begin{IEEEeqnarray}{rCl}
P_{XYZ} = P_{X|Y} \cdot P_{YZ}\\
Q_{XYZ} = P_X \cdot P_{YZ}.
\end{IEEEeqnarray}
The exponent-rate region then becomes the set of all nonnegative pairs $(\theta_y, \theta_z)$  that satisfy
	\begin{align}
	\theta_y &\leq I(U;Y)\\
	\theta_z &\leq I(U;Y),
	\end{align}
	for an auxiliary random variable $U$ satisfying the Markov chain  $U\to X \to (Y,Z)$  and the rate constraint
	\begin{align}
	R &\geq I(U;X).
	\end{align}
	The region is achievable using Proposition~\ref{prop:Markov}.
\end{remark}

\vspace{3mm}

\section{The Special Case ``$X^n\to Z^n \to Y^n$ Under Both Hypotheses"}\label{sec:MarkovXZY}

We consider a setup where $X^n \to Z^n \to Y^n$ forms a Markov chain under both hypotheses. {This setting models a situation where  the receiver lies in between the transmitter and the relay, and thus the signals at the sensor and the relay are conditionally independent given the signal at the receiver (decision center).} The two-hop network can still be an adequate communication model if all the communication from the transmitter to the receiver needs to be directed {through} the relay. This is for example the case in cellular systems where the relay is associated with a base station.

We treat two special cases: 1) same $P_{YZ}$ under both hypotheses, and 2) same $P_{XZ}$ under both hypotheses. Combined with the Markov chain $X \to Z \to Y$, these assumptions seem to suggest that the receiver cannot improve its error exponent by learning information about the observations  at  the relay (for case 1) or about the observations at the transmitter (for case 2). As we shall see, this holds only if the rates of communication are sufficiently high.  Otherwise, information about observations at both the transmitter and the relay can be combined to reduce the required rate of communication and thus also improve the performance of the system.
In this section we shall not employ binning, i.e., all achievability results below follow from Theorem~\ref{cascadeachnb}.

\bigskip
\subsection{Special Case 1: Same $P_{YZ}$ under both Hypotheses}

Consider first the setup where the pmfs $P_{XYZ}$ and $Q_{XYZ}$ decompose as
\begin{align}
P_{XYZ} &= P_{X|Z}\cdot P_{YZ},\label{case3a}\\
Q_{XYZ}&=P_X\cdot P_{YZ}.\label{case3b}
\end{align}
Since the pair of sequences $(Y^n,Z^n)$ has the same joint distribution under both hypotheses, no positive error exponent $\theta_z$ is possible when the message~$B$ sent from the relay to the receiver is only a function of $Y^n$ but not of the incoming message $M$. The structure of \eqref{case3a} and \eqref{case3b} might even suggest that $Y^n$ was not useful at the receiver and that the relay should simply forward a function of its incoming message $M$.
Proposition~\ref{thm4} shows that this strategy is optimal when $T\geq R$, i.e., when the relay can forward the entire message to the receiver. On the other hand, Example~\ref{example1} shows that it can be suboptimal when $T<R$.
\vspace{3mm}
\begin{proposition}\label{thm4} Assume conditions (\ref{case3a}) and (\ref{case3b}) and
	\begin{equation}
T\geq R.\label{eq:TlargerR}
	\end{equation}
	Then the exponent-rate region $\mathcal{E}(R,T)$ is  the set of all nonnegative pairs $( \theta_y,\theta_z)$ that satisfy
	\begin{align}
	\theta_y &\leq I(S;Y)\\
	\theta_z &\leq I(S;Z)\label{thetarec}
	\end{align}
	for some auxiliary random variable $S$ satisfying the Markov chain $S\to X\to (Y,Z)$ and the rate constraint
	\begin{align}
	 R\geq I(S;X),
	\end{align}
	where  $(X,Y,Z) \sim  P_{X|Z}\cdot P_{YZ}$.
\end{proposition}
\begin{IEEEproof} For achievability, specialize Theorem \ref{cascadeachnb} to $S=U=V$.
	  The converse is proved in Appendix~\ref{convthm4}.
\end{IEEEproof}
\vspace{3mm}

We next consider an example that satisfies assumptions~\eqref{case3a} and \eqref{case3b}, but not \eqref{eq:TlargerR}. We assume $R\ge H(X),$ so the transmitter can reliably describe the sequence $X^n$ to the relay.
When $T \geq R$, by Proposition~\ref{thm4}, the optimal strategy at the relay is to forward the incoming message $B=M$, i.e., to describe the entire $X^n$ to the receiver.
In this example, to achieve the same exponent, it suffices that the relay describes only part of $X^n$, the choice of which depends on the relay's own observations $Y^n$. Thus, the relay only requires a rate $T$ that is smaller than $R$.
\vspace{3mm}

\begin{example}\label{example1} Let under both hypotheses $\mathcal{H}=0$ and $\mathcal{H}=1$:
	\begin{equation}
	X\sim \mathcal{B}(1/2) \quad \textnormal{and} \quad Y \sim\mathcal{B}(1/2)\nonumber
	\end{equation}
	be independent of each other.
	Also, let $N \sim \mathcal{B}(1/2)$  be independent  of the pair $(X,Y)$, and
	$$ Z=(Z',Y) \qquad \textnormal{where} \quad Z'=\begin{cases} X& \textnormal{if }Y=0 \textnormal{ and } \mathcal{H}=0 \\  N & \textnormal{otherwise.}
	\end{cases}.
	$$
	Let $P_{XYZ}$ denote the joint pmf under $\mathcal{H}=0$ and $Q_{XYZ}$ the joint pmf under $\mathcal{H}=1$.

	Notice that the triple  $(X,Y,Z)$ satisfies conditions (\ref{case3a}) and (\ref{case3b}). Moreover, since $P_{XY}=Q_{XY}$, the error exponent $\theta_y$ cannot be larger than  zero, and we   focus on the  error exponent $\theta_z$ achievable at the receiver. Notice that the conditional pmf
	\begin{equation}\label{eq:same}
	P_{XZ|Y=1}= Q_{XZ|Y=1}
	\end{equation}  The idea of our scheme is thus that the relay describes only the symbols
	\begin{equation}\{X_t \colon t\in\{1,\ldots, n\},Y_t=0 \}
	\end{equation}
to the receiver. All other symbols are useless for distinguishing the two hypotheses.
Specifically, we specialize the scheme  in Subsection~\ref{sec:scheme} to the choice of random variables
\begin{subequations}\label{eq:choice_auxiliary}
\begin{IEEEeqnarray}{rCl}
S &  &\textnormal{a constant}\\
U & =& X\\
 V& = & \begin{cases}U & \textnormal{if } Y=0 \\
U'& \textnormal{otherwise,}
\end{cases}
\end{IEEEeqnarray}
\end{subequations}
where $U'\sim \mathcal{B}(1/2)$ is independent of all other random variables.
Evaluating Theorem~\ref{cascadeachnb} for this choice
 proves achievability of the following error exponent at the receiver:
 \begin{align}
 \label{eq:th}
 \min_{\substack{\tilde{P}_{VXYZ}:\\\tilde{P}_{VXY}=P_{VXY}\\\tilde{P}_{VZ}=P_{VZ}}} D(\tilde{P}_{VXYZ}\|P_{V|XY}Q_{XYZ})  &\stackrel{(a)}{\geq } D({P}_{VZ}\|Q_{VZ}) \\
  &=D({P}_{VYZ'}\| Q_{VYZ'}) \\
    &\stackrel{(b)}{= } \mathbb{E}_{P_Y}[ D({P}_{VZ'|Y}\| Q_{VZ'|Y})] \\
  &\stackrel{(c)}{= } P_Y(0) \cdot D({P}_{VZ'|Y=0}\| Q_{VZ'|Y=0})  \\
 & = P_Y(0)\cdot  I(Z';V|Y=0)\\
  & = P_Y(0)\cdot  I(X;V|Y=0)\\
& = 1/2 H(X) =1/2,
 \end{align}
 where the pmfs $P_{VXY}$, $P_{VZ}$, $P_{VYZ'}$ and the pmfs $Q_{VZ}$, $Q_{VYZ'}$ are obtained from the  definitions in \eqref{eq:choice_auxiliary} and the pmfs $P_{XYZ}$ and $Q_{XYZ}$, respectively, and mutual informations are calculated according to the joint pmf $P_{VXYZ'}$ defined through \eqref{eq:choice_auxiliary} and $P_{XYZ}$.
 In the above, $(a)$ holds
 	by the data-processing inequality, and by the second condition in the minimization; $(b)$ holds by the chain rule of KL-divergence and because $P_Y=Q_Y$; and $(c)$ holds because  $Q_{VZ'|Y=0}=P_{V|Y=0}\cdot P_{Z'|Y=0}$ whereas $Q_{VZ'|Y=1}=P_{VZ'|Y=1}$.

 The scheme requires rates
 $$R=H(X)=1$$ and $$T=I(V;Y,U) \stackrel{(d)}{=}  I(V;X|Y)  \stackrel{(e)}{=} P_Y(0) \cdot I(V;X|Y=0) = 1/2,$$
 where $(d)$ holds because $V$ is independent of $Y$ and $(e)$ holds because $V$ is also independent of $X$ unless $Y=0$.

The error exponent in \eqref{eq:th} coincides with the largest exponent $D(P_{XYZ} \| Q_{XYZ})$ that is possible even in a fully centralized setup. We argue in the following that, provided $R=1$ and $T<1$, this error exponent cannot be achieved when the relay simply sends a function of the message $M$ to the receiver.
Notice that the setup incorporating only the transmitter and the receiver is a standard ``testing against independence" two-terminal setup \cite{Csiszar86} with  largest possible exponent equal to:
\begin{eqnarray}
\max_{P_{S|X} \colon T \geq I(S;X)} I(S;Z) &\stackrel{(f)}{=} & \max_{P_{S|X} \colon T \geq I(S;X)}  I(S;Z'|Y)\nonumber\\
&=&1- \min_{P_{S|X} \colon T \geq I(S;X)}  H(Z'|Y,S)\nonumber\\
&=&1- \min_{P_{S|X} \colon H(X|S)\geq 1-T} \frac{1}{2}\cdot H(X|S)-\frac{1}{2}\nonumber\\
& \leq & \frac{1}{2} T,\label{th1}
\end{eqnarray}
where
$(f)$ holds because $Z=(Z',Y)$ and because $(X,S)$ are independent of $Y$. This shows that the optimal exponent $1/2$ cannot be achieved if the relay simply sends a function of the incoming message whenever $T< 1$.

\end{example}
\bigskip
\subsection{Special Case 2: Same $P_{XZ}$ under both Hypotheses}
\vspace{3mm}
Consider next  a setup where
\begin{align}
P_{XYZ} &= P_{XZ}\cdot P_{Y|Z},\label{case2a}\\
Q_{XYZ} &= P_{XZ}\cdot P_Y.\label{case2b}
\end{align}
Notice that the pair of sequences $(X^n, Z^n)$ has the same joint pmf under both hypotheses. Thus, when the relay simply forwards the incoming message $M$ without conveying additional information about its observation $Y^n$ to the receiver, no positive error exponent $\theta_z$ is possible. On the contrary, as the following proposition shows, if
\begin{equation}\label{eq:const_T}
T \geq H(Y),
\end{equation}
then forwarding message $M$ to the receiver is useless, and  it suffices that the message $B$ sent from the relay to the receiver describes $Y^n$. In other words, under constraint \eqref{eq:const_T}, the optimal  error exponent $\theta_z$  coincides with the optimal error exponent of a point-to-point system that consists only of the relay and the receiver. The three-terminal multi-hop setup with a  transmitter observing $X^n$ can however achieve larger error exponent $\theta_z$ than the point-to-point system when \eqref{eq:const_T} does not hold. This is shown through
 Example~\ref{ex:2} ahead.
\bigskip

\begin{proposition}\label{thm3} Assume (\ref{case2a})--\eqref{eq:const_T}. Under these assumptions, the exponent-rate region $\mathcal{E}^*(R,T)$ is  the set of all nonnegative pairs $( \theta_y,\theta_z)$ that satisfy
	\begin{align}
	\theta_y &\leq I(U;Y),\label{thm3aa}\\
	\theta_z &\leq I(Y;Z),\label{thm3bb}
	\end{align}
	for some auxiliary random variable $U$ satisfying the Markov chain $U\to X\to (Y,Z)$ and the rate constraint
	\begin{align}
	R &\geq I(U;X),\label{thm3cc}
	\end{align}
\end{proposition}
where  $(X,Y,Z) \sim  P_{XZ}\cdot P_{Y|Z}$.
\begin{IEEEproof} Achievability follows by specializing Theorem \ref{cascadeachnb} to $S=U$ and $V=Y$. The converse for \eqref{thm3aa} is the same as in the point-to-point setting (without receiver). The converse for \eqref{thm3bb} follows by Stein's lemma (without communication constraints) \cite{Cover}.
\end{IEEEproof}

\bigskip
We next consider an example where assumptions \eqref{case2a} and \eqref{case2b} hold, but not~\eqref{eq:const_T}.

\bigskip

\begin{example}\label{ex:2}
 Let under both hypotheses $\mathcal{H}=0$ and $\mathcal{H}=1$:	\begin{equation}
	X\sim \mathcal{B}(1/2) \quad \textnormal{and} \quad Y \sim \mathcal{B}(1/2)\nonumber
	\end{equation}
	be independent of each other.
	Also, let $N \sim \mathcal{B}(1/2)$  be independent of the pair $(X,Y)$, and
	$$ Z=(Z',X) \qquad \textnormal{where} \quad Z'=\begin{cases} Y & \textnormal{if }X=0 \textnormal{ and } \mathcal{H}=0 \\  N & \textnormal{otherwise.}
	\end{cases}
	$$
The described triple  $(X,Y,Z)$ satisfies conditions (\ref{case2a}) and (\ref{case2b}).
Moreover, since the pmf of the sequences  $(X^n,Y^n)$ is the same under both hypotheses, the best error exponent $\theta_y$ is zero, so we focus on the receiver's error exponent $\theta_z$. 	By Proposition~\ref{thm3}, the largest error exponent $\theta_z$  that is achievable is \begin{equation}
\label{eq:optimal}
\theta_z^\star=I(Y;Z)=I(Y;Z'|X)=1/2.
\end{equation}
As we show in the following, $\theta^\star_z$ is achievable with $T=1/2$. To see this, notice that
\begin{equation}
	P_{YZ|X=1}= Q_{YZ|X=1}.
\end{equation}
It thus suffices that the relay conveys the values of its observations $\{Y_t \colon t\in\{1,\ldots,n\},X_t=0\}$ to the receiver. This is achieved by specializing the coding and testing scheme of Subsection~\ref{sec:scheme} to the choice of $S$ being a constant and
\begin{IEEEeqnarray*}{rCl}
U & = & \begin{cases}0 & \textnormal{if } X=0 \\
1 & \textnormal{otherwise}
\end{cases} \\
 V& = & \begin{cases}Y& \textnormal{if } U=0 \\
Y' & \textnormal{otherwise},
\end{cases}
\end{IEEEeqnarray*}
where $Y'\sim\mathcal{B}(1/2)$ is independent of $(X,Y,Z)$.
By  Theorem \ref{cascadeachnb}, the scheme requires rates
 $$R=I(U;X)=H(U)=1$$ and $$T=I(V;Y,U)= P_U(0)\cdot I(V;Y|U=0) = 1/2.$$
 It achieves the optimal error exponent $\theta_z^\star$ in \eqref{eq:optimal}:
  \begin{IEEEeqnarray}{rCl}
  \lefteqn{\min_{\substack{\tilde{P}_{UVXYZ}  \colon \\ \tilde{P}_{UX}=P_{UX} \\ \tilde{P}_{UVY}=P_{UVY} \\ \tilde{P}_{VZ} = P_{VZ}}} D( \tilde{P}_{UVXYZ} \| P_{U|X}  P_{V|UY} Q_{XYZ})} \qquad  \nonumber \\
   & \stackrel{(a)}{\geq} & D(P_{VZ} \| Q_{VZ}) \\
   & = &  \mathbb{E}_{{P}_{X}}\big[  D({P}_{VZ'|X} \|    Q_{VZ'|X}) \big] \nonumber \\
   & \stackrel{(b)}= & P_X(0) D({P}_{VZ'|X=0} \|    P_{V|X=0} P_{Z'|X=0})\nonumber \\
   &= & P_X(0) I(V;Z'|X=0) \nonumber \\
   &=&  1/2,\label{eq:theta}
 \end{IEEEeqnarray}
 where $(a)$ holds by the data-processing inequality for KL-divergences and by defining $Q_{VZ}$ to be the marginal of the joint pmf $P_{U|X}P_{V|UY}Q_{XYZ}$; and $(b)$ holds because $Q_{VZ'|X=0}=P_{V|X=0}P_{Z'|X=0}$ whereas $Q_{VZ'|X=1}=P_{VZ'|X=1}$.

 Using similar arguments as in Example~\ref{example1}, it can be shown that the optimal error exponent $\theta^\star_z$ in \eqref{eq:optimal} cannot be achieved without the transmitter's help when $T<1$.
 \end{example}

\section{Concluding Remarks}\label{sec:conclusion}

The paper presents  coding and testing schemes for a two-hop relay network, and  the corresponding exponent-rate region. The schemes combine cascade source coding with a unanimous decision-forwarding strategy where the receiver decides on the null hypothesis only if both the transmitter and relay have decided on it. The schemes are shown to attain the entire exponent-rate region for some cases of testing against independence or testing against conditional independence when the Markov chain $X^n\to Y^n\to Z^n$ holds. In these cases, the source coding part of our  coding schemes simplifies to independent source codes for the transmitter-to-relay link and for  the relay-to-receiver link. The proposed schemes are also shown to be optimal in some special cases when the Markov chain $X^n\to Z^n\to Y^n$ holds. For large enough communication rates and when testing against independence, it is again optimal to employ independent source codes for the two links. But, when the rate on the relay-to-receiver link is small, this simplification can be suboptimal.

One of our coding schemes employs binning to decrease the required rates of communication. Binning makes the characterization of the achievable exponent region much more involved. For the proposed scheme we have two competing exponents for the error exponent at the relay and four competing exponents for the error exponent at the receiver. Notice that, in our scheme, we only bin the satellite codebooks but not the cloud-center codebooks. Further performance improvement might be obtained by binning also the cloud center; this would however lead to an expression with ten competing exponents at the receiver.

\section{Acknowledgement}

The authors would like to thank Pierre Escamilla and Abdellatif Zaidi for  helpful discussions, and Associate Editor Shun Watanabe and the anonymous reviewers for their valuable comments.

\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv


priority in service and will do our best to offer our customers with high quality products and excellent service. for Stadium Lighting Pole , Stadium Light Pole , Road Lighting Pole , do not hesitate to call us.
"We will make just about every exertion for being excellent and perfect, and speed up our actions for standing during the rank of worldwide top-grade and high-tech enterprises for Stadium Lighting Pole , Stadium Light Pole , Road Lighting Pole , With a fully integrated operation system our company has won a good fame for our high quality goods reasonable prices and good services. Meanwhile we have established a strict quality management system conducted in material incoming processing and delivery. Abiding by the principle of "Credit first and customer supremacy" we sincerely welcome clients from home and abroad to cooperate with us and advance together to create a brilliant future.


The slim 5' wide x 7' tall design is ideal for batting cage tunnels, athletic facilities, or any outdoor field. The curved side is designed to completely protect the pitcher's upper body. The straight side can be used for softball or short toss. Features a 1-1/2" galvanized steel frame and a #48 braided double-knotted nylon pillowcase net. Easy bolt together assembly.
© Odeys 2017. All rights reserved. You may not, except with our express written permission, distribute, download or commercially exploit the content. Nor may you transmit it or store it in any other website or other form of electronic retrieval system.


WFTO Africa & ME has the pleasure to share with you a series of training manuals aims to improve the financial independence and capacities of women involved in fair trade activities.
The development of these materials was an outcome of Leadership & Business Skills for Women Fair Trade Producers under WIEGO Global Trade Programme, in partnership with fair trade organizations in Africa. Specifically, it developed out of the trainings done in Ghana, Kenya, and Uganda. Both the project and production of these manuals received support from Funding Leadership and Opportunities for Women (FLOW), Government of the Netherlands, Ministry of Foreign Affairs.
The thinking behind this initiative was the recognition that strong business skills help women run productive enterprises and earn much-needed income. Information on markets and buyers lets them create the right products and sell them at a fair price. And leadership skills allow women to form effective self-help groups and achieve equality in their member associations. Together, these skills can dramatically improve the livelihoods of poor women producers.
Between 2013 and 2015, thousands of informal women workers gained skills through their fair trade organizations in Ghana (cocoa farmers), Kenya (handicraft producers), and Uganda (coffee farmers and handicraft producers). To maximize the number of women who gained the skills to succeed, the project relied on a cascading approach to training. Knowledge and skill spread from country-level networks to fair trade groups and individual members, then to grassroots groups. This created a sustainable base beyond the life of the project.
The training materials are a living testimony of a process that combined the learning and best practices from the three project countries. It consists of seven modules focused on women's leadership, governance and business skills. Anchored on bottom-up approach that utilizes local expertise and a participatory process, the training materials is a hallmark of innovation and creativity that speaks to informal women workers, particularly in Africa, but can be applied in other contexts outside the region as well. The series goes through the steps of leadership development; cooperative and independent financing; and the broadening business skills such as product consistency and pricing. You are welcome to download and use these training modules for your training activities, and remember to acknowledge the source. Download from the following links.
The Secretariat of WFTO Africa & Middle East - a region that includes all the countries in Africa, the Middle East, Madagascar and Mauritius - is based in Nairobi, Kenya. It is responsible for the planning, coordination and execution of the services, projects and programmes being implemented by the network.
:|: Provide an avenue for GREATER PARTICIPATION, DIALOGUE, COMMUNICATION AND SHARING of our experiences as members and Fair Trade Producer organizations.
Interventions include periodic dialogue, sharing of experiences, business-to-business forums, enabling participation at regional and global conferences and trade fairs.
:|: GREATER APPRECIATION FOR THE CONCEPT OF FAIR TRADE, understanding and compliance with the principles of World Fair Trade Organization (WFTO) among the members and growing the awareness of Fair Trade in the region.
In addition to awareness creation, WFTO Africa & Middle East also works closely with the membership to ensure that they maintain compliance to Fair Trade Principles and Standard. Such engagement include coaching, technical support, role modeling etc.
:|: ENHANCE THE CAPACITY of the members to transform their businesses into SUSTAINABLE, AND COMPETITIVE ENTERPRISES in the global market.
CAPACITY BUILDING program that provides Business Skills Training and Product Development workshops to members to assist them to improve their business. Africa has great potential and resources for craft and food products production. However, many producers lack capacity to produce quality products and professionally engage in competitive global markets. WFTO Africa & Middle East is working to develop a stronger program that will provide more specialized training based on needs assessments.
WFTO Africa & Middle East's market access function is carried out through gathering, packaging and dissemination of market and trend information, product development and design, participation in local, regional and international market fairs and facilitating buyer visits.
WFTO Africa & Middle East works through workshops and seminars, joint delegations to concerned parties, alliances with other regional chapters of WFTO, like-minded partner organisations and the media to provide a voice for producers to challenge policies and practices that reinforce trade injustices.
WFTO Africa & Middle East actively works to continually improve the region's contribution to the global fair trading conversation - both inside the global structures of WFTO - and in the broader interface with our partner organisations.


text:
singular-resources-logo-lockup-blue
How LinkedIn, Lyft, Poshmark, and Calm align teams for maximum ROI
By John Koetsier • August 28, 2018
In some fantasy world, growth marketers have all the cash, corporate support, creative assets, and analytics they need, and can do their jobs in splendid isolation. In the real world? No marketer is an island, every team is an integrated component of the overall organization, and marketing alignment is a tough challenge.
Which means that kindergarten lessons still apply.
And marketers need to play nice with others … for their own good.
Marketing alignment in fast-growing companies
That's exactly what we recently discussed with key executives at fast-growing Lyft, LinkedIn, Poshmark, and Calm during our recent UNIFY conference.
Specifically, we asked them how marketers should align internal teams to achieve ROI.
On the panel: Esther Hwang, Director of Growth at Poshmark, Ben Shanken, Director of Product and Growth at Lyft, Jake Bailey, Senior Manager, Digital Marketing and Strategy at LinkedIn, and Dun Wang, VP of Product and Growth at Calm. Fabien-Pierre Nicolas, Head of Marketing at SmartNews, moderated.
Fabien-Pierre Nicolas, SmartNews; Esther Hwang, Poshmark; Ben Shanken, Lyft; Jake Bailey, LinkedIn; Dun Wang, Calm.
Here's a summary of their insights.
Aligning with executive teams
Aligning with the executive can be challenging. Most CxOs don't know growth marketing, and they may also have a different time-frame for decision-making than campaign-driven marketers. Achieving marketing alignment requires tight coordination.
"At Calm we have three KPIs," says Calm VP Dun Wang. "It's purchase conversion, subscriber engagement, and subscriber renewals, so all of the conversations come back to those three metrics."
That simplifies conversations, because those three key performance indicators are identical all the way up and all the way down the organization. Every decision can be weighed by how it contributes to at least one, and hopefully multiple of the top KPIs.
At Lyft, with 1,600 employees, alignment requires structural thinking.
"We actually invest a lot in building a structure for how we think, and disseminating that structure across the whole company, so that people can be in line with how we think," says Ben Shanken, Director of Product and Growth.
But it's also about investment, and investment carries risk.
And that's something else to consider at the executive level.
"We think about things in terms of how much risk we want to take in terms of learning," says Shanken.
Aligning with finance teams
Marketing alignment with finance and the CFO matters too. And it's often not without some history.
"Historically the relationship between finance and marketing has been kind of contentious, because one is the money-spender and one is the money-protector," says Poshmark Director of Growth Esther Hwang.
That means marketers need to educate finance.
Finance teams typically don't understand growth activity or marketing, and nuance escapes them. For example, when one channel is killing it, finance might think: invest all your dollars there. Growth marketers, on the other hand, might know that channel, understand its capacity, and understand that there is not enough scale there to withstand doubling or tripling the budget.
But finance often sees things that marketers don't.
"At the same time the finance team is a really great ally," says Hwang. "From their vantage point they have a really great way of looking at certain blind spots that the marketing team might have. For example, at Poshmark it was the finance team that pointed out to us the difference in very long LTV for our male users versus our female users … which the growth team, operating much more short-term, weren't keeping as close an eye on."
That's relevant at LinkedIn too:
"From a finance perspective we have to understand the full evolution of a user," says Jake Bailey, Senior Manager, Digital Marketing and Strategy at LinkedIn. "We have finance partners that are very baked into our everyday engagement."
Lyft does the same thing: add a finance executive to the marketing and user acquisition group, says Ben Shanken. It's easier to run the numbers on LTV and budget allocations — and ensure tight feedback loops — when finance has a seat at the table.
Aligning with engineering teams
Science and art. Data and creativity. Marketing and engineering.
Sometimes it seems like marketing and engineering are oil and water. One promises, and the other has to deliver; one builds, and the other has to market. And they don't always speak the same language.
That's not the case in the world's best companies, however.
"We're fortunate to have very commercially minded engineers," says Calm's VP Dun Wang. "They want to know … if they're going to spend a week working on a feature, how does that affect the user experience and how does that tie back to more revenue for Calm? So we're super-transparent with that."
For Poshmark, it's all about the relationships.
"Our VP of Growth is an ex-engineer … who has a lot of personal relationships [with engineers]," Director Esther Hwang says. "He still makes it a habit to set up unstructured time with engineers … and that's proven to be very helpful."
Just one example: Poshmark has set up car pool routes that intentionally mix staff members across departments. In one case, a growth marketer complained to an engineer about the cost of marketing on Facebook. The engineer brainstormed a solution that involved using Facebook social logins as part of the registration flow. It was super-easy to implement, and had a significant benefit.
"That low-hanging fruit improved our registration conversion rate by about five points," Hwang says.
Lyft engineers collaboration right into standard workflow and employee organization, says Director of Product and Growth Ben Shanken.
"We have a social pod which is an engineer, a data scientist, a program manager, and a marketer," he says. "We want the engineer to be a channel manager [and] we want the manager to be a marketer."
First of all, Lyft has changed the career path of engineers from building technology to making an impact. And secondly, they've empowered engineers with ownership of metrics.
Marketing alignment … with other marketing teams
It may sound silly, but marketing does need to align with marketing. Growth marketers have different imperatives, techniques, technologies, and budgets than brand marketers. Performance marketers and user acquisition marketers look at the world differently. Creative teams are not always aligned with marketing managers.
It's about size.
"As you scale you're going to run into these more siloed teams in the marketing space," says LinkedIn's Jake Bailey. "You have to find a way to bring those together."
One way LinkedIn has done it is by creating an internal digital agency.
The agency is horizontal, and flows across silos. It leverages what is working in one team with the others, and derives a whole-company number for ROAS, return on ad spend.
"[This] allows us to work together to grow the business as a whole," Bailey says.
Lyft has a different way of solving a similar problem, and it involves sometimes intentionally building inefficiencies into the system. It sounds paradoxical — or nonsensical — but it's actually necessary.
"We have huge brand dollars that we do not control," says Ben Shanken, Lyft's Director of Product and Growth. "We can try to align our roadmaps … but every time we do that it sort of fails. It all comes down to agreeing on goals … if you do that, then it becomes easier to sequence how we do things."
One example: brand marketers tend to like the most efficient ways of buying brand: national advertising. But, if you want to be great at measurement, local spend is the way to go.
The solution: sometimes being less efficient at one goal (in this case, brand advertising) to enable long-term efficiencies in another goal (in this case, local performance-oriented advertising).
Aligning with creative teams
Mistakes are great teachers, and Lyft saw this first-hand.
"We did a really bad thing … we gave the marketing team and the creative team a goal to replace all creative within four weeks with winning creative," says Shanken. "They started cranking out huge amounts of creative, but the downside was they were cutting a lot of corners on analyzing this stuff … and rolling out creatives that weren't that amazing."
Lyft adjusted team OKRs (objectives and key results) and fixed the problem.
But this isn't easy, as Calm also learned.
"For us it was really hard to align creative and UA," says Dun Wang. "[There were] too many opinions on what ads we should launch and why … most of it not founded on data."
What helped Calm move faster was empowering user acquisition directors to lead creative as well. Each UA team received design resources … and UA managers were given some leeway in marketing.
"We're not so precious about the brand," Wang says.
Aligning with BI/Analytics
Growth marketers live and die by the numbers. So it's no surprise that the best marketers want super-tight relationships with business intelligence and analytics pros.
"Incorporating biz analytics into your process early is the key to success," says LinkedIn's Bailey. "Include them early and include them often. For us, they are the core of the team … without them nothing else would exist."
Lyft's Ben Shanken agrees:
"Data science is hugely important to each channel for us, especially as we start to automate and build programmatic," Shanken says. "Because they're building the models … they are arguably the most important part of the pod. They are the person making the actual model and algorithm working with the engineer and the marketer to translate logic into model."
The same is true at Poshmark and Calm, where Wang says that data analysts work on every project and with every team.
It's not often that you can get some of the world's top marketing experts and user acquisition leaders to open up about the core challenges of their jobs. Watch the whole video to get every last detail.
Go deeper: check out how top marketers use Singular to get the data-driven insights they need to accelerate their growth.
Stay up to date on the latest happenings in digital marketing
Simply send us your email and you're in! We promise not to spam you.

redpajama_set_name: RedPajamaCommonCrawl


The menu looked good online, with good prices, and when we went to pick up our takeaway the staff were very friendly and the inside dining nice if you want to eat in. But we weren't super impressed with the food. The Vegetarian Omelette could have been quite good except it was lightly burnt all over and you could taste this with every bite. It was full of nice veges and the gravy was tasty, but it's hard to get past that over-cooked taste. The Beef Strips with Plum Sauce was quite literally that – we had expected it would come with some veges but there was just carrot strips, but perhaps that was our mistake for expecting other veges in it. The vege fried rice and mixed vege stir fry were ok, but overall nothing spectacular.